Untangle: A Principled Framework to Design Low-Leakage, High-Performance Dynamic Partitioning Schemes

Sharing a cache between processes is fast but leaks secrets, and letting each process resize its slice of the cache on demand leaks even more — yet exactly how much has been impossible to pin down, because what a program resizes and when it resizes are hopelessly entangled through timing; this work from Illinois and Tel Aviv untangles the two, splitting the leakage into a what part it can erase entirely by making resize decisions depend only on the instruction stream rather than the clock, and a when part it bounds with a worst-case covert-channel model — cutting measured leakage by 78 percent at the same performance.

Why this problem is worth solving

The vulnerability this work defends against is one of the most stubborn in modern hardware.

To reason about a leaky defense rigorously rather than by intuition, you need to turn leakage into a number.

What people did before, and where it broke

• Static partitioning. Give each process a fixed slice of the resource for its whole execution, so nothing about one process’s usage can reach another. Where it broke. It leaks nothing, but a fixed slice is wasteful when demand shifts over time, causing resource wastage for some and underprovisioning for others.
• Coarsen the dynamic scheme. Resize less frequently, or support fewer resizing actions, to leak less. Where it broke. It reduces leakage only by giving up the adaptivity that made dynamic partitioning valuable — a straight trade of performance for security.
• Fix resizing to a public schedule. Make the timing of resizes fixed and publicly known so the timing itself carries no secret. Where it broke. It removes the timing leakage but loses responsiveness to real demand, again trading performance for security.
• Bound leakage by assuming the worst case. When exact analysis is impossible, assume every resize trace that could theoretically occur is equally likely. Where it broke. It vastly overcounts — a scheme resizing every millisecond for a second is charged a full thousand bits — so the leakage budget empties far too soon and forbids the resizing that would have helped.
• The gap. Every path either surrendered performance to be safe or, when it tried to stay dynamic, could only bound the leakage so loosely that the guarantee throttled performance anyway. The missing piece was a way to measure the leakage of a dynamic scheme tightly and honestly — tight enough that a program could keep resizing under a real budget without the estimate itself becoming the bottleneck.

How Untangle works

The idea

Cut the one intractable number into two you can attack separately. The whole difficulty is that the exact leakage is a single quantity — the entropy of the resize traces — in which what a program does and when it does it are fused, and because the when is governed by unpredictable timing, the whole thing is written off as impossible to compute. Untangle’s first move is a clean decomposition: the chain rule of entropy splits that joint number exactly into an action term, the leakage from which resizes occur, and a scheduling term, the leakage from their timing given the actions. Neither half is easier than the whole by magic, but each yields to a different, tractable technique, whereas the fused quantity yielded to none. Taking a global quantity that is hopeless to analyze in one piece and decomposing it into parts that can each be handled and then recombined is the same discipline the scalable hardware-invariant-learning work covered elsewhere on this site is built on, replacing one intractable whole-system question with a set of smaller ones whose answers compose into the guarantee.

Make the decision depend on what the program did, not on when the clock happened to tick. The reason the action half was entangled with timing at all is that conventional schemes measure demand over a window of cycles and assess resizes on a wall-clock interval, so both the measurement and the moment of decision shift with the program’s unpredictable speed — and secret-dependent timing rides along. Untangle severs this by measuring demand as a purely architectural quantity, the unique lines touched over a fixed count of retired instructions, and by assessing resizes after a fixed amount of instruction progress rather than after a fixed amount of time. The action sequence then depends only on the retired instruction stream, immune to how fast that stream executed. Grounding a security property in what a program semantically does rather than in the microarchitectural timing it happens to exhibit is the same instinct the secure-speculation verification work covered elsewhere on this site follows, reasoning about the observable behavior a processor is permitted to expose rather than the timing accidents of a particular run.

When you cannot compute the leak, bound the strongest possible attacker instead. Even after the action half is eliminated, a residual leak remains in the timing of the resizes that do occur — and analyzing that timing exactly runs straight back into the intractable problem. Untangle sidesteps it with a worst-case argument: model the resize channel as a covert channel in which the victim is imagined as a cooperative sender deliberately encoding secrets in how long it holds a partition size. The maximum data rate of that channel is a provable ceiling on what any real, non-cooperative program could leak, computable from the channel alone and never from the program. Replacing an exact computation that cannot be done with a conservative, provable bound against the most capable adversary is the same posture the confidential-memory work covered elsewhere on this site takes, bounding an attacker’s success probability against a co-resident foe rather than trying to characterize every execution exactly.

Following the reasoning through Untangle

This is the case simple secret-tainting cannot fix, because the leak is through timing, not through the action or the data.

Why it works

• Splitting one tangled number into two makes each half tractable. The exact leakage is the joint entropy of what actions occur and when — a quantity no one could compute because the two are entangled through timing → but the chain rule of entropy cleanly separates it into a what-term and a when-term → so each can be attacked with a different technique instead of the whole being written off as intractable.
• Deciding from the instruction stream, not the clock, severs the tie to timing. If resizes are assessed every T cycles using cache hits over that window, secret-dependent timing changes what the program managed to do and thus the decision → but assessing every N retired instructions using a metric that counts only architectural events makes the decision depend on the instruction sequence alone → so the sequence of actions no longer moves with the unpredictable timing.
• Excluding secret-dependent work from the metric zeroes the what-leakage. Even a timing-independent decision still leaks if secret data changes the measured demand → but annotating the instructions that touch the resource under secret influence and dropping their contribution, and not counting secret-controlled code toward progress, makes the metric public-only → so for any public input exactly one action sequence is possible, and the action leakage is exactly zero.
• Modeling the residue as a covert channel bounds it without predicting timing. The remaining when-leakage seems to demand the same intractable timing analysis → but imagining the victim as a cooperative sender that encodes symbols in how long it holds a partition size gives a channel whose maximum data rate is a provable upper bound → so the worst-case leakage can be computed from the channel, never from the program.
• Slowing and blurring the channel, and crediting silent decisions, tightens the bound. A covert channel with unlimited freedom would still leak fast → but a minimum cooldown between resizes and a random delay on each action lower its data rate, and counting the ninety percent of assessments that leave the size unchanged as invisible shrinks it further → so the certified leakage drops enough to allow far more resizing under the same budget.

What it costs (trade-offs and scope)

• It is a framework evaluated in simulation on one resource. The contribution is the formal split and the covert-channel bound, demonstrated on last-level-cache partitioning in a cycle-level simulator; the paper deliberately does not present a detailed hardware implementation, and other structures are argued rather than shown.
• The 78 percent is measured against a maximally conservative baseline. The comparison is to a scheme that assumes every resize action is equally likely at every assessment; the improvement is real, but part of what it measures is how loose that worst-case assumption was in the first place.
• Zeroing the action leakage relies on sound annotations. The guarantee that secret-dependent work is excluded is only as good as the analysis that marks secret-dependent resource use and control flow. The paper assumes such annotations exist, from prior static-analysis tools or from conservatively annotating all secret-handling code.
• The scheduling bound is a worst-case covert channel, not the actual leak. It upper-bounds leakage by assuming a cooperative victim deliberately transmitting; a real, non-cooperative program leaks less, so the certified number is conservative by design and does not tell you what a given run actually revealed.
• The two mitigations trade performance for security. A longer cooldown and a wider random delay lower the leakage rate but slow the program; the evaluation tunes them to match the baseline’s performance, so at a fixed performance target it is the security that improves, and tightening security further costs speed.
• An active attacker raises the leakage. A powerful attacker can pressure the cache to force a visible resize at every assessment, pushing leakage to about 3.8 bits per assessment. The guarantee still holds — the budget is hit sooner and resizing is disabled, hurting performance not security — but the low headline numbers describe benign execution.
• It secures one specific channel. Untangle bounds the leakage of the partition-resizing decisions layered on top of an existing partitioning defense; it is not a standalone isolation mechanism, and it assumes a single fixed scheme and an idealized attacker who can see the exact resize trace.

The evaluation

Check yourself

Sources

The paper is “Untangle: A Principled Framework to Design Low-Leakage, High-Performance Dynamic Partitioning Schemes” by Zirui Neil Zhao, Adam Morrison, Christopher W. Fletcher, and Josep Torrellas, published at ASPLOS 2023, pages 770 to 787, DOI 10.1145/3582016.3582033. The authors are at the University of Illinois Urbana-Champaign and Tel Aviv University.

This explainer is written from the full 18-page text. Everything above comes from the paper’s own sections: the background on microarchitectural side channels, static versus dynamic partitioning, and the information-theoretic definitions of entropy and mutual information; the leakage model characterizing a dynamic partitioning scheme by its utilization metric, action heuristic, and resizing schedule, the three ways a resizing trace can leak (secret-dependent control flow, data flow, and timing), the intractability of exact leakage due to the entanglement of action and timing, and the resulting worst-case overestimation of prior work; the threat model of a mutually-distrusting peer with an idealized attacker who observes the exact resizing trace and a user-set leakage threshold that disables further resizing when reached; the Untangle framework decoupling the leakage via the chain rule into action leakage (the entropy of action sequences) and scheduling leakage (the expected entropy of timing given the actions), the two design principles (a timing-independent utilization metric such as unique-line footprint over retired instructions, and a progress-based resizing schedule) plus annotations that together eliminate the action leakage, and the covert-channel model that bounds the scheduling leakage without analyzing timing, with a cooldown time, a random action delay, and a Maintain-based optimization; and the evaluation in gem5 of static, time-based dynamic, Untangle, and shared last-level-cache schemes over SPEC17-and-OpenSSL workloads, reporting matched 1.11-to-1.14-times speedups over static partitioning, a 78-percent reduction in leakage per assessment (roughly 3.2 bits for the time-based scheme versus 0.4 to 1.0 bits for Untangle), 90 percent of assessments being Maintain, and a 3.8-bit worst-case under an active attacker.