Localizing Timing Side-Channel Leaks with Residual Spatio-Temporal Graph Models

Modern systems make themselves fast by adapting to what they are computing: they cache repeated prompts, let easy inputs exit a neural network early, and compress redundant memory. The catch is that whenever speed depends on secrets — whose prompt was seen before, whose record was in the training set — the elapsed time itself becomes a message that an observer can read. Today's audits treat each measurement point as an isolated number: a statistical test on one endpoint's latency, or clustering on one response time. But real deployments are not one endpoint. A secret-dependent delay at one machine ripples outward through shared caches, queues, and schedulers, and shows up — diluted and delayed — at neighboring machines. This proposal argues that timing leakage in distributed systems is a propagation phenomenon over an infrastructure graph, and that we should detect and localize it with models built for exactly that: spatio-temporal graph neural networks, which learn how signals move across a fixed topology of nodes through time.

The core obstacle is a known empirical trap. A recent audit of spatio-temporal forecasting benchmarks showed that once each node's own recent history is accounted for, neighbors add little predictive signal on standard datasets, and simple per-node statistical models beat most graph neural networks there A Critical Audit of Spatiotemporal Forecasting Benchmark Datasets and Baselines. Timing data is precisely the kind of data that triggers this trap: a component's latency is mostly explained by its own recent load, with contention effects buried underneath. So the proposal is not "apply a graph network to latency traces." It is a two-stage design — subtract each node's own temporal behavior first, then learn graph propagation only on what remains — validated against the explicit possibility that there is nothing spatial left to model.

Core Claim

The claim has three parts. First, formulation: timing side-channel leakage in multi-component systems should be posed as joint detection and localization on a graph — given per-node latency time series over a known deployment topology, decide whether a secret-dependent behavior exists and identify which node or edge carries it. Existing methods answer only the first half. Second, method: a residual spatio-temporal architecture, which we call Ripple, in which a per-node temporal forecaster removes each component's autocorrelated baseline and a graph model with adaptive routing learns how anomalous residuals propagate. Third, regime of validity: in clean, single-endpoint settings, simple scalar statistics are already near-optimal — we must match them there, not beat them — and the value of the graph model should emerge specifically under multi-tenant noise and multi-hop propagation, which is the regime practitioners actually face.

Formally, let $y_{i,t}$ be the observed latency at component $i$ and time $t$, and let $f_i$ be a per-node temporal predictor trained on benign traffic. Ripple computes residuals and leak scores as

$$r_{i,t} = y_{i,t} - f_i\big(y_{i,t-1},\dots,y_{i,t-T}\big), \qquad s_{i,t} = \phi\big(\{r_{j,t'}:\ j\in\mathcal{N}_i,\ t'\le t\},\ A\big),$$

where $\mathcal{N}_i$ is the neighborhood of node $i$ in the deployment topology $A$, and $\phi$ is a graph attention module whose per-node contribution can be switched off by a gating network. The score $s_{i,t}$ is trained so that the node carrying the secret-dependent behavior ranks highest. The design directly imports two documented lessons: the audit's finding that a graph network trained on the residuals of a per-node statistical model is the configuration that actually wins when spatial signal exists A Critical Audit of Spatiotemporal Forecasting Benchmark Datasets and Baselines, and TESTAM's demonstration that routing some nodes to a purely temporal "identity expert" is essential where spatial aggregation injects noise TESTAM: A Time-Enhanced Spatio-Temporal Attention Model with Mixture of Experts.

Where Prior Work Stops

Four lines of work come closest, and each stops one step short. The nearest is FG-SAT, which builds a graph over packets in an encrypted traffic flow — nodes are packets, edges follow TCP window and acknowledgment logic — and classifies the flow with GraphSAGE and graph attention, reaching 89.79% accuracy across 72 environmental shifts FG-SAT: Efficient Flow Graph for Encrypted Traffic Classification under Environment Shifts. But each flow is a single static graph instance built for classification of traffic metadata; it does not model a persistent topology of system components evolving over continuous time, and it does not target execution-latency leaks at all. Second, the NAS-stealing attack reconstructs a proprietary neural architecture from CPU cache-timing traces with 0% error, but through hand-crafted structural invariants and a static lookup table of matrix-multiply durations — the graph is the target of that work, never the tool, and the authors themselves note the reliance on clean, isolated traces How to 0wn the NAS in Your Spare Time. Third, ScaAR extracts private input attributes from electromagnetic emissions of edge accelerators with a 1D convolutional network, reaching 92.8% accuracy on MNIST classes, but concedes it cannot identify which hardware unit causes the leak and leaves concurrent-process noise unresolved Real-world Edge Neural Network Implementations Leak Private Interactions Through Physical Side Channel. Fourth, the prompt-cache audit detects cross-tenant cache sharing in commercial language model APIs with a two-sample Kolmogorov–Smirnov test on time-to-first-token, at precision 0.80–0.90, finding 8 of 17 providers caching and 7 of 17 sharing caches globally — an existence test with no power to say where or through what path the leak travels Auditing Prompt Caching in Language Model APIs. What motivates the spatial view is older: shared hardware multiplexing inherently produces measurable performance cross-talk between co-resident processes The Confinement Problem: 40 Years Later, and learned components embedded in system infrastructure open analogous shared-resource channels Learned-Database Systems Security. On the method side, we reuse architectural machinery rather than invent it: graph-convolution-inside-recurrent cells from T-GCN T-GCN: A Temporal Graph Convolutional Network for Traffic Prediction, decoupled spatial-temporal attention with gated fusion from GMAN GMAN: A Graph Multi-Attention Network for Traffic Prediction], and the general recipe of temporal graph learning A Primer on Temporal Graph Learning. Notably, spatio-temporal graph models have already been applied to distributed cloud microservice graphs for forecasting Jun Huang 0003 et al. — evidence the modeling machinery fits this domain, but that work forecasts load, not leakage.

Research Program

Three artifacts get built. The first is a testbed, which we call LeakBench, that composes three independently documented leak sources into one distributed pipeline deployed as containers on shared machines with a fixed, known dependency topology. The leak sources are: prompt-prefix caching, where a cache hit versus miss shifts time-to-first-token exactly as audited in commercial APIs Auditing Prompt Caching in Language Model APIs; multi-exit early exiting, where training members exit a multi-exit BERT at shallower layers than non-members, so latency reveals membership Auditing Membership Leakages of Multi-Exit Networks and adversarial inputs can be forced to maximum depth SlowBERT: Slow-down Attacks on Input-adaptive Multi-exit BERT]; and memory compression, where decompression latency varies with the compressibility of co-located records Practical Timing Side-Channel Attacks on Memory Compression]. A secret is toggled at one designated node; observers at all nodes record latency series; ground truth is which node and edge carry the secret at each time. Controlled background load generators let us sweep noise from clean to heavily contended, and we vary the hop distance between the leaking node and the observer.

The second artifact is Ripple itself: a per-node forecaster $f_i$ (a small GRU, with SARIMA as a check, avoiding the default first-order differencing that the audit showed corrupts comparisons A Critical Audit of Spatiotemporal Forecasting Benchmark Datasets and Baselines), followed by a GMAN-style spatial-temporal attention block over residuals with a TESTAM-style gate that can route a node to identity, adaptive, or attention experts TESTAM: A Time-Enhanced Spatio-Temporal Attention Model with Mixture of Experts]. The third artifact is the analysis: an audit-style partial spatial correlation study of the residuals, which tells us before any deep learning whether the testbed actually contains learnable cross-node signal.

Proposed Experiments

The architectural sanity check comes first, on public data: Ripple's residual-plus-graph pipeline is evaluated on METR-LA, where the audit reports that a graph network trained on SARIMA residuals reached a mean absolute error of 3.32 A Critical Audit of Spatiotemporal Forecasting Benchmark Datasets and Baselines; GMAN itself reports up to a 4% MAE improvement over prior methods at the one-hour horizon GMAN: A Graph Multi-Attention Network for Traffic Prediction]. Matching the 3.32 hybrid confirms our backbone captures spatial signal when it exists. We also check the recurrent variant on SZ-taxi, where T-GCN reports 57.8% RMSE reduction versus GCN and 3.3% versus GRU at the 15-minute horizon T-GCN: A Temporal Graph Convolutional Network for Traffic Prediction.

The main experiments run on LeakBench. Detection is scored by precision and recall of the binary "is a leak present" decision, and localization by top-1 and top-3 accuracy of identifying the leaking node, plus time-to-detection. The noise sweep is the decisive curve: we expect all methods to converge in the clean regime (scalar statistics report nearly 100% exit-depth prediction accuracy in clean environments Auditing Membership Leakages of Multi-Exit Networks] and 0.80–0.90 hit/miss precision for cache auditing Auditing Prompt Caching in Language Model APIs]), and the graph model's advantage to widen with background load and with hop distance from the leak to the observer. Attribution quality is scored by whether the model's learned attention mass sits on the true propagation edges.

Baselines

The do-nothing reference point is no monitoring at all, under which every leak in LeakBench goes through undetected; slightly above it sits a fixed per-node latency threshold alarm, which we include to show how background load alone triggers false positives once noise is introduced. The strongest scalar competitor is the audit methodology itself: a two-sample Kolmogorov–Smirnov test per observation point on the hit/miss latency distributions, precisely as deployed across 17 commercial API providers with reported precision of 0.80–0.90 Auditing Prompt Caching in Language Model APIs], together with the K-means and kernel-density clustering on scalar latency used to infer exit depth SlowBERT: Slow-down Attacks on Input-adaptive Multi-exit BERT] Auditing Membership Leakages of Multi-Exit Networks]. These are the strongest competitors on the detection question and will be run on the exact same traces, per node, with the same significance threshold; beating them means strictly higher precision at matched recall in the noisy regimes, plus any nonzero localization ability, since these methods localize nothing by construction.

The strongest existing graph-based competitor is FG-SAT, the only prior work that builds graphs over timing-bearing side-channel metadata FG-SAT: Efficient Flow Graph for Encrypted Traffic Classification under Environment Shifts]. We adapt it faithfully: per-timestamp graphs over LeakBench nodes with its GraphSAGE-plus-attention classifier and its Jensen–Shannon divergence feature filtering, which contributed a 7.44% accuracy boost in its own setting. For fairness, it sees identical traces and topology, an equal tuning budget in random-search trials, and a parameter cap within an order of magnitude of its reported ~43k parameters; it reports 89.79% accuracy on its own 72-shift benchmark, so it is no strawman. Beating it means higher top-1 localization accuracy at no detection cost, at comparable per-decision runtime (FG-SAT processes 100 flows in 4.82 ms, a bar we should approach on far fewer, longer series).

Two ablations isolate the ingredients. Removing all spatial edges and gating every node to the identity expert yields a per-node temporal residual detector — if it matches Ripple, the graph is not earning its keep. Removing the residual subtraction (running the graph model on raw latencies) isolates the hybrid design; the audit's evidence says this variant should degrade toward or below linear baselines A Critical Audit of Spatiotemporal Forecasting Benchmark Datasets and Baselines]. Finally, a ScaAR-style 1D convolutional network on the concatenated latency vector Real-world Edge Neural Network Implementations Leak Private Interactions Through Physical Side Channel] tests whether any black-box sequence model, graph-agnostic, suffices; it reports 92.8% attribute accuracy in its own domain, so it too is a serious baseline, and the comparison turns specifically on source attribution rather than raw detection.

Why not just…?

Why not just run the existing KS-test audit at every node? This is the cheapest serious alternative, and it wins outright in clean settings — 0.80–0.90 precision on real commercial APIs, and near-100% exit-depth recovery when the environment is quiet. But it treats each observation as an independent scalar draw from a hit-or-miss distribution, so it cannot say which node leaked, cannot combine evidence across neighbors, and is exactly the kind of statistic that environmental shifts corrupt; FlowPrint-style scalar statistics degraded severely under shift while the graph approach held 89.79% FG-SAT: Efficient Flow Graph for Encrypted Traffic Classification under Environment Shifts]. Our noise sweep will quantify this directly; if KS-per-node holds up under contention, we will report that honestly and the localization claim will carry the proposal alone.

Why not just fit a SARIMA per node and alarm on the residuals? This is the most real threat, and we treat it as such rather than arguing around it. The audit proved temporal autocorrelation dominates standard spatio-temporal datasets and that tuned SARIMA beat most graph networks on WikiMaths A Critical Audit of Spatiotemporal Forecasting Benchmark Datasets and Baselines], and TESTAM's identity expert beat spatial modeling on uncoupled nodes TESTAM: A Time-Enhanced Spatio-Temporal Attention Model with Mixture of Experts]. That is why the per-node-residual ablation is a first-class baseline, not an afterthought, and why the partial-correlation pre-check on LeakBench residuals runs before any model training: if contention-induced residual coupling is marginal at realistic noise levels, the spatial claim collapses and the correct output of this project is a careful negative result plus a characterization of when graph structure is and is not needed. The audit's own hybrid result on METR-LA (MAE 3.32, beating pure variants) is our evidence that the residual coupling can be real when topology genuinely couples nodes A Critical Audit of Spatiotemporal Forecasting Benchmark Datasets and Baselines].

Why not just make everything constant-time and be done? TimeGuard-style uniform execution mitigates the multi-exit membership attacks perfectly, as its authors report Auditing Membership Leakages of Multi-Exit Networks]. But the price is the entire point of the optimizations: forcing every input to maximum depth is precisely the up-to-4.57× latency inflation SlowBERT demonstrates as an attack outcome SlowBERT: Slow-down Attacks on Input-adaptive Multi-exit BERT], and SCHMIT's whole program exists because full elimination carries prohibitive overhead — it instead buys over 100× min-guess entropy improvement at a bounded 50% overhead Quantitative Mitigation of Timing Side Channels]. Detection and localization are also prerequisites for spending a delay budget well, and extending SCHMIT's budget allocation across the graph, guided by Ripple's per-node leak scores, is the natural follow-on this proposal sets up.

Why not just use a 1D CNN on the traces? ScaAR's 1D convolutional profiler is the established tool and reaches 92.8% in its domain, but its authors state plainly that the black-box waveform view makes it impossible to isolate which hardware unit leaks Real-world Edge Neural Network Implementations Leak Private Interactions Through Physical Side Channel]. Our attribution metric — learned attention mass on true propagation edges versus top-1 node identification — is designed so this baseline fails specifically on the axis the proposal cares about, and if it instead attributes correctly, that too would be a finding worth reporting.

Decisive Checks

Four checks decide the proposal. The pre-registered partial-correlation analysis on LeakBench residuals must show non-trivial cross-node coupling at realistic noise levels, or the project pivots to documenting its absence. In the clean regime, Ripple must match the scalar statistics (roughly the 0.80–0.90 precision and near-100% exit-depth recovery they report) rather than lose ground. Across the noise sweep, the performance gap between Ripple and every scalar baseline must widen monotonically with background load and hop distance. And the edge-removal ablation must show that the graph ingredient, not the per-node forecaster, supplies the localization gain — with all comparisons run at matched data, matched tuning budget, and matched parameter scale.