Replacement Non-Interference for Speculative Execution

When a modern CPU guesses wrong about a branch, it discards the results of the wrongly executed instructions — but not their side effects. Defenses and formal checkers have converged on a comforting assumption: if the discarded instructions never leave the cache with new lines, and never change which addresses are touched, nothing leaks. That assumption is false. Two results make this concrete. Cache replacement policies — the hardware bookkeeping that decides which line to evict next — are updated even on clean cache hits, and an attacker who shares a cache set can read that bookkeeping, achieving up to 600 Kbps per set on Intel hyperthreads (Leaking Information Through Cache LRU States in Commercial Processors and Secure Caches). And mis-speculated instructions, even when barred from touching the cache directly, contend for shared execution resources and delay older instructions, so the order in which legitimate loads hit the cache becomes secret-dependent — and because replacement policies are non-commutative (accessing $A$ then $B$ leaves different state than $B$ then $A$), that reordered order is written permanently into eviction metadata (Speculative interference attacks: breaking invisible speculation schemes). This defeats "invisible speculation" hardware and, worse, it is invisible to formal checkers.

The proposal here is to close that verification blind spot, and to do it in a way that scales. The core claim is twofold. First, the standard security property for speculative code — Speculative Non-Interference, whose observer watches only memory addresses and control flow (Spectector: Principled Detection of Speculative Information Flows) — must be extended with a replacement-state observer, because two runs with byte-identical architectural traces can leave different eviction orderings. Second, checking that extended property by brute force over large out-of-order execution windows is hopeless (the state space of possible orderings explodes), so the practical detector should be a learned model over instruction dependency graphs whose validity across window sizes is guaranteed by sparse graph limit theory rather than hoped for. Instruction dependency graphs are extremely sparse — each instruction reads two or three operands, so edges grow linearly with instructions — which is exactly the regime where classical dense graph limit theory collapses and where the newer sparse machinery (graph operators, and $\sqrt{|E|}$ spectral scaling) was built to work (Limits, approximation and size transferability for GNNs on sparse graphs via graphops; Modeling Sparse Graph Sequences and Signals Using Generalized Graphons).

Core Claim

Define a program $P$ to satisfy Replacement Non-Interference (RNI) if any two executions of $P$ with identical architectural traces — same addresses, same jump targets — induce the same distribution over final replacement-stack orderings in every cache set:

$$ \text{arch}(\sigma) = \text{arch}(\sigma') \;\Rightarrow\; \text{ord}(\sigma) = \text{ord}(\sigma') $$

where $\text{ord}(\sigma)$ is the eviction-priority permutation left behind by run $\sigma$. RNI strictly refines the observer of Spectector: Principled Detection of Speculative Information Flows, which stops at the antecedent and would certify as secure exactly the interference gadgets that Speculative interference attacks: breaking invisible speculation schemes demonstrated on Intel Kaby Lake hardware. The refinement is not free: the SPECTECTOR authors themselves flag path explosion on loops and indirect jumps, and tracking permutations of replacement state per speculation branch multiplies that space. Our answer is structural. The dependency-graph formalism of New Models for Understanding and Reasoning about Speculative Execution Attacks — which models attacks as small ordered graphs of Authorization, Secret Access, Send, and Receive nodes, and proves races occur exactly when a dependency path is missing — captures interference attacks only if we add a new implicit edge type: a reorder edge between two operations whose relative completion order is perturbable by shared-resource contention, feeding a non-commutative replacement update rather than an explicit Send node. On small graphs this gives an exact symbolic RNI checker. On large graphs, where symbolic checking dies, we learn a message-passing predictor of reorder-induced leak potential, and we can say something no fixed-window model can: by the graphop transferability theory of Limits, approximation and size transferability for GNNs on sparse graphs via graphops, a spatial message-passing network trained on $n$-node windows approximates its limit-object behavior with worst-case error $O(n^{-1/2})$ (they observe $O(n^{-1})$ empirically on polymer graphs), so a detector validated at one scale carries quantified guarantees to another. We deliberately avoid spectral graph networks here, because the same literature shows the spectral gap is not continuous under operator convergence, and Modeling Sparse Graph Sequences and Signals Using Generalized Graphons shows spectra only stabilize under $\sqrt{|E|}$ normalization — a constraint our design respects.

Research Program

Three deliverables. The first is the formal layer: the RNI definition above, the reorder-edge extension of the dependency-graph model, and an exact symbolic RNI checker runnable on bounded windows (tens to a few hundred micro-ops). Its job is ground truth, not scale — it labels small execution graphs with whether contention there can permute replacement order, using the interference gadget constructions of Speculative interference attacks: breaking invisible speculation schemes as known-positive cases and the priority-stack model of Leaking Information Through Cache LRU States in Commercial Processors and Secure Caches as the semantics of the leaked state. The second is the learned layer: a graph-network leak predictor in the style of GRANITE: A Graph Neural Network Model for Basic Block Throughput Estimation — which already showed that graph networks over instruction dependency graphs predict out-of-order execution better and faster than sequence models — but trained on RNI labels rather than throughput, and built to the sparse-limit specification (spatial message passing, $\sqrt{|E|}$-normalized operators) so its cross-scale behavior is covered by transferability bounds rather than extrapolation. The third is deployment: a hit-based observation probe for black-box fuzzing. Hide and Seek with Spectres: Efficient discovery of speculative information leaks with random testing finds leaks by serializing fences and watching for cache allocations, which discards precisely the test cases whose only footprint is replacement metadata on hits; grafting the pointer-chase probe of Leaking Information Through Cache LRU States in Commercial Processors and Secure Caches onto its observation filter extends coverage to the order-based channel class.

Proposed Experiments

Experiment 1 validates the false-negative claim directly. We extend the 240-microbenchmark Spectre v1 corpus used by Spectector: Principled Detection of Speculative Information Flows with variants whose leak is purely order-based (same addresses, same control flow, contention-reordered hits) and run SPECTECTOR unmodified. The expected result: it certifies these as secure. Our exact RNI checker must flag all of them at zero false positives on the original benign set. The file reports that SPECTECTOR's verification cost was "comparable to the cost of discovering symbolic paths" with no scalar runtime; no reported result found on Lacuna for SPECTECTOR's absolute verification time, so we will establish our own runtime baseline on identical hardware.

Experiment 2 tests transferability, the reason the sparse-limit machinery is in the proposal at all. In gem5 we simulate out-of-order windows of $n$ micro-ops for $n$ from 32 to 4096, label each window's induced replacement-stack permutation (Kendall tau distance between eviction orderings with and without an injected contention event), and train the predictor at $n \le 256$ only. We then measure prediction error as a function of test-time $n$ and fit the decay exponent, comparing against the $O(n^{-1/2})$ worst-case bound proven in Limits, approximation and size transferability for GNNs on sparse graphs via graphops (which observed $O(n^{-1})$ empirically on synthetic polymer graphs). The decisive comparison is against the same architecture trained without the sparse-limit treatment on a fixed window size, which should degrade as test windows grow. For sanity we verify the $\sqrt{|E|}$ spectral stabilization on our execution graphs, echoing the stability reported for Ogbn-arXiv subgraphs in Modeling Sparse Graph Sequences and Signals Using Generalized Graphons.

Experiment 3 closes the loop on hardware and on fuzzing. On an Intel Kaby Lake testbed matching Speculative interference attacks: breaking invisible speculation schemes, we use the predictor to rank candidate windows from real binaries and measure the correlation between predicted reorder sensitivity and the observed LRU channel — for calibration, Leaking Information Through Cache LRU States in Commercial Processors and Secure Caches reports 600 Kbps per set on Intel hyperthreads and roughly 2 bps in time-sliced settings, so channel reconstruction bit-error rate is the metric. In the fuzzing campaign we run the extended observation filter of Hide and Seek with Spectres under its reported conditions (a 100x testing speedup, a campaign that took 16 hours instead of over 2 months) and count order-based leaks found with and without the probe. Finally, we use detector output for a targeted defense: serialize only reorder-critical edges, and measure CPI on SPEC CPU2006 in gem5 against the reference point that wholesale FIFO/Random replacement costs under a 2% CPI increase (Leaking Information Through Cache LRU States) and that the heavy-handed interference defense of Speculative interference attacks costs 1.58x on the Spectre model and 5.38x on the Futuristic model on SPEC CPU2017. Selective serialization should land far below the latter while eliminating what FIFO/Random cannot: reordering leakage through structures beyond the data-cache replacement stack, such as the way predictors of Take A Way: Exploring the Security Implications of AMD's Cache Way Predictors and the eviction-count tracking that defeats randomized caches in Randomized Last-Level Caches Are Still Vulnerable to Cache Side-Channel Attacks! But We Can Fix It.

Baselines

The do-nothing reference is SPECTECTOR's Speculative Non-Interference check exactly as published (Spectector: Principled Detection of Speculative Information Flows), run on the extended microbenchmark corpus with no observer changes. It is the right null because our central formal claim is that it is blind to order-based leaks; beating it means flagging every planted interference-LRU variant it certifies, at zero added false positives on code it already handles, and we will run it on identical binaries with the same symbolic budget. The strongest learned competitor is the GRANITE architecture (GRANITE: A Graph Neural Network Model for Basic Block Throughput Estimation), which reports an average test error of 6.9% on throughput prediction over the Ithemal and BHive datasets and is the best documented evidence that graph networks beat sequence models on dependency-structured execution. We will retrain it from scratch on our RNI labels with the same data, compute, and tuning budget as our predictor, and evaluate both at the training window size and far beyond it; beating it means matching its in-distribution detection quality while showing flat error as window size grows where its fixed-window training degrades. The strongest black-box competitor is the Revizor-style fuzzing campaign of Hide and Seek with Spectres with its original observation filter, run on the same machine and test-case budget as our probe-augmented version; beating it means discovering order-based leaks its filter structurally cannot see. Finally, an ablation isolates the key ingredient: the identical network trained on a single fixed window without the $\sqrt{|E|}$ normalization and transferability treatment, plus an RNI checker run with the replacement-state term removed — the first shows whether the sparse-limit design or merely "a GNN" does the work, the second confirms that the observer term, not the graph frontend, is what catches the leaks.

Why not just…?

Why not just use sequence models or fixed-window graphs? For a single window size, that might suffice, and we treat it as a live threat rather than a strawman: GRANITE already beat the LSTM-based Ithemal by 1.7 absolute points and ran 3.0x faster on GPUs, so if the task were bounded, a plain graph network would be the sensible choice. The graph limit machinery earns its place only through Experiment 2: if the fixed-window ablation's error does not grow outside its training scale, or our transferability exponent is far worse than $n^{-1/2}$, the theory is decorative and we would report that honestly. What the ablation cannot get from any fixed-window design is a guarantee — Limits, approximation and size transferability for GNNs on sparse graphs via graphops provides the bound, and dense-graphon analysis of these sparse traces would degenerate to a trivial empty limit, as the vanishing-density problem in Modeling Sparse Graph Sequences and Signals Using Generalized Graphons and the exchangeability impasse noted in Bayesian nonparametric models of sparse and exchangeable random graphs make clear.

Why not just switch the cache to FIFO or Random replacement? This is the most serious objection, and for the pure hit-based LRU channel it nearly wins: Leaking Information Through Cache LRU States showed in gem5 that FIFO or Random eliminates that channel with under a 2% CPI increase on SPEC CPU2006. But it does not cover the class we target. Interference attacks reorder accesses through MSHRs, reservation stations, and execution ports before the cache is ever touched, and the defense evaluated against that reordering cost 1.58x to 5.38x on SPEC CPU2017 (Speculative interference attacks) — so accurate detection is the cheaper path to selective mitigation. Way-predictor collisions (Take A Way) and the eviction-count tracking that betrays randomized caches (Randomized Last-Level Caches Are Still Vulnerable) are further members of the same metadata-leak family that policy swaps leave intact. Our defense experiment measures whether detector-guided serialization beats both endpoints: cheaper than 1.58x, broader than FIFO/Random.

Why not just extend SPECTECTOR's observer model directly? On small gadgets, this would work, and we will run it as a baseline rather than argue it away — a hand-extended symbolic checker on our small-window corpus is exactly Experiment 1's exact RNI checker. The question is scale. The SPECTECTOR authors themselves report path explosion on loops and indirect jumps, and their observer deliberately abstracts away microarchitectural detail to stay tractable; enumerating replacement-state permutations across every speculation branch in a deep out-of-order window multiplies the state the solver must explore. If the direct extension somehow verifies our largest windows within a comparable time budget, the learned layer is unnecessary and the proposal collapses to a (still useful) observer-model fix — that outcome would itself be a finding, and Experiment 2's runtime measurements against our own established SPECTECTOR timing baseline settle it empirically rather than by assertion.

Decisive Checks

The proposal stands or falls on three measurements. SPECTECTOR, unmodified, must certify at least one planted order-based gadget that our RNI checker flags — the false negative made concrete. The trained-at-small-$n$ predictor's error must decay no slower than roughly $n^{-1/2}$ beyond its training scale while the fixed-window ablation degrades — the sparse-limit ingredient vindicated. And the probe-augmented fuzzing campaign must surface leaks, on hardware, that the original observation filter misses. If all three hold, the field gets a verification property that matches what attackers actually do to replacement metadata, and a detector that scales with programs rather than with analyst patience.