Cars still run on the Controller Area Network (CAN), a shared bus where every message is trusted simply because it appears on the wire. Frames carry no sender address and no signature, and there is no room in an 8-byte frame to add one. The hardest attacks to catch are "timing-transparent" masquerades: a compromised unit rewrites a few payload bytes of a legitimate message ID while keeping its usual rhythm. Detectors trained to recognise known attacks do very badly on realistic traffic that contains such masquerades. On the ROAD dataset, a strong tree ensemble scores an average F1 of 0.3212 and misses masquerades outright (AI-Driven IDS on ROAD). The defence that does work, wiring a monitor to each unit's transmit pin, cannot be retrofitted to existing fleets (CANTXSec).
We propose a detector that needs no attack labels. It flags a window of raw frames when that window is far from every benign window seen in training, measured by a distance chosen so that payload tampering is large and ordinary driving variation is small. To make this run on a microcontroller, we borrow a tool from metric-embedding theory. A Fréchet embedding, whose coordinates are simply "distance from this point to a fixed reference set," represents such a distance with bounded error using only minimum-distance operations. We also ask directly whether this theory adds anything beyond a well-tuned nearest-neighbour baseline.
Core Claim
Against timing-transparent attacks, open-world detection reduces to two things: a metric on payload windows, and a way to compute distance to the benign set cheaply. We make two concrete claims.
The first is about the metric. We build it on raw frames, with no proprietary signal-decoding files, as an $\ell_1$ distance over per-ID bit-flip rates, byte-wise first differences and inter-arrival statistics. Because every $\ell_1$ metric is of negative type, the embedding results below apply without an extra fitting step. Negative type means the metric behaves like a squared Euclidean distance.
The second is about computation. A multi-scale Fréchet embedding computed against small benign nets gives a detection score whose runtime cost depends on how "low-dimensional" benign traffic is, not on how much traffic was recorded. A net here is a sparse subset such that every benign window lies within radius $r$ of some member. The score also has a provable guarantee: small benign drift cannot produce large score jumps.
Concretely, let $B$ be the stored benign windows and $d$ the payload metric. At dyadic scales $r_m = 2^m$ we keep random subsets $S_{m,j} \subset N_m$, where $N_m$ is an $r_m$-net of $B$. The coordinates are $f_{m,j}(x) = d(x, S_{m,j})$, and the detector compares $F(x)$ with stored embeddings of benign prototypes. Each coordinate is 1-Lipschitz in $d$ (moving $x$ by $\delta$ moves it by at most $\delta$). Replacing a set by its net member changes a coordinate by at most $r_m$. Together these give
$$|s(x) - s(x')| \le L \, d(x, x'),$$
where $s$ is the detection score and $L$ is a constant fixed by the number of coordinates and their scaling. Benign jitter of size $\delta$ in the metric therefore cannot raise the score by more than $L\delta$. That is exactly the guarantee false-positive-averse automotive engineers ask for when they reject statistical detectors (CANTXSec).
The guarantee does not run the other way for new points. That attacks land far from benign in embedding space is proven only on the reference set, and on test data it is an empirical question we measure.
What the Theory Buys, and What It Rules Out
Two results supply the method. Euclidean distortion and the sparsest cut shows that negative-type metrics embed into Euclidean space with $O(\sqrt{\log n \log\log n})$ distortion, where distortion is the worst-case factor by which distances are stretched or shrunk. Fréchet Embeddings of Negative Type Metrics shows that nearly the same bound, $O(\sqrt{\log n}\cdot\log\log n)$, is reachable using only distance-to-set coordinates and multi-scale random decompositions. It also shows that Fréchet embeddings cannot beat $\Omega(\sqrt{\log n})$. We reuse its construction, the scale-by-scale sets and padded clusters, but replace full subsets with nets. This is the step that turns an $n$-point construction into something that fits in ECU memory. Proving that the distortion degrades only by a constant under this replacement is our main theoretical task.
The hardness literature constrains the design rather than supplying it. Khot and Vishnoi use the Unique Games Conjecture to show that negative-type metrics need $(\log\log n)^{1/6-\delta}$ distortion into $\ell_1$. The same conjecture makes sparsest-cut partitioning inapproximable within any constant factor. Two design choices follow. We do not promise constant-factor preservation of detection margins, and we target Euclidean coordinates. We also avoid any pipeline that needs an optimal partition of driving states into operating modes, and use randomized padded decompositions instead.
More generally, conditional lower bounds of the kind surveyed in the fine-grained complexity literature imply that exact nearest-neighbour search in high intrinsic dimension cannot be made sublinear without structure. Brute-force distance-to-benign is therefore only practical because benign CAN traffic might be low-dimensional. We treat that as a hypothesis to measure, not an assumption.
Three papers motivate the proposal by exposing the gap. The ROAD comparison study separates timing-opaque attacks, which older detectors catch, from timing-transparent ones, which they miss (AI-Driven IDS on ROAD). Shape of the Cloak proves that timing-based sender fingerprints can be forged in software, which is why our metric puts its weight on payload content rather than clock skew. Chawla et al. document how overconfident closed-set models assign high confidence to unfamiliar inputs, which motivates a score defined by distance rather than by classifier confidence.
Research Program
We will build the payload metric per CAN ID over windows of $w$ consecutive frames, using only raw identifiers, bytes and timestamps. We will then measure the intrinsic dimension of benign ROAD and SynCAN traffic under this metric. We use doubling dimension, estimated from how net size grows as the radius shrinks. This number decides feasibility: if nets at the finest useful scale hold tens of thousands of points, the on-ECU story fails, and we will say so.
On the theory side, we will extend the Arora–Lee–Naor analysis to net-restricted coordinates. The target is distortion within a constant factor of the full construction, plus the explicit Lipschitz constant $L$ above.
On the systems side, we will implement the scorer in fixed-point C for an STM32-class microcontroller and a Raspberry Pi 4, the hardware used by Zhao et al.. Finally, we will build an adaptive attacker in the spirit of Shape of the Cloak's formal adversary. It rewrites payload bytes to shift a target signal as far as possible while keeping the detection score under threshold. This yields a curve of achievable physical effect against detection rate, which is more informative than a single F1.
Baselines
The naive reference is exact 1-nearest-neighbour distance to all stored benign windows under the same metric, run off-line without memory limits. It is not a competitor for deployment. It is the ceiling any compressed scorer is trying to reach. If our embedding falls well below it, compression is costing accuracy. If it matches, the remaining question is cost.
The strongest learned open-world competitor is ACGAN-AC-RFC-Th (Zhao et al.). It flags low-confidence samples from an auxiliary classifier as out-of-distribution and passes them to a GAN discriminator. On the HCRL Car-Hacking dataset it reports 99.23% macro F1, 99.28% F1 on held-out attack types, and 0.538 ms per sample on a Raspberry Pi 4. It has no reported result on ROAD. We will retrain it on ROAD with the same leave-one-attack-out splits and the same hyperparameter search budget in GPU-hours that our method's metric weights receive. We will also rerun it on HCRL to confirm we reproduce its published numbers before trusting our ROAD comparison.
The strongest lightweight unsupervised competitor is CANtropy (CANtropy). It applies PCA reconstruction error to 34 hand-crafted signal features and reports an average AUROC of 0.992 on SynCAN, with 80.52 ms of extraction and inference latency. We run it on SynCAN with its published features. On ROAD we run it only where decoded signals are available. We found no reported result on Lacuna for CANtropy on ROAD.
For closed-set supervised models, the reference point is LCCDE's average F1 of 0.3212 on ROAD (AI-Driven IDS on ROAD). We rerun LCCDE, Random Forest and LSTM on our splits so that the comparison uses the same held-out attacks. We found no reported result on Lacuna for any method restricted to the timing-transparent subset of ROAD, so that number will be new.
Two ablations isolate the key ingredient. The first replaces the multi-scale Fréchet coordinates with single-scale distance to $k$-means centroids at the same memory budget. The second replaces them with Nyström kernel features using the same number of landmarks. Beating the external baselines means two things together: higher timing-transparent F1 on ROAD than every retrained competitor at matched false-positive rate, and scoring latency under 1 ms on the microcontroller.
Why not just…?
Why not just run nearest-neighbour distance to benign traffic directly? This is the real threat, because our scorer is a compressed version of it. If benign traffic turns out to have low intrinsic dimension, a coreset nearest-neighbour search may be as fast as our embedding. In that case the contribution shrinks to the payload metric and the Lipschitz false-alarm bound. The exact-nearest-neighbour ceiling and the net-size measurements will show which regime we are in, and we will report it either way.
Why not just use distance to a handful of $k$-means centroids? Single-scale centroids are cheap, but they are blind to scale. A subtle plateau masquerade sits close to some centroid at the coarse scale that flooding needs. Multi-scale coordinates are meant to catch both. The centroid ablation at equal memory tests this directly. If it matches on SynCAN's plateau, continuous and playback masquerades, the multi-scale machinery is unnecessary.
Why not just retrain a deep out-of-distribution detector on ROAD? The evidence so far is discouraging. Deep models on ROAD show multiclass false-positive floods and unstable results across datasets (AI-Driven IDS on ROAD), and the ACGAN detector was validated only on timing-opaque HCRL attacks. It remains a fair possibility that retraining closes the gap, so we retrain it rather than cite it. The comparison that settles the matter is timing-transparent F1 on ROAD at matched false-positive rate, measured on the same splits for both methods.
Why not just use CANtropy's features with PCA? CANtropy needs manufacturer-specific signal-decoding files. It also detects with an 80.52 ms delay, well beyond the roughly 10 ms budget cited by Zhao et al., and a linear reconstruction model can be evaded by attacks that stay inside its principal subspace. The adaptive-attacker curve tests this third point for both methods under the same attacker budget.
Proposed Experiments
The main evaluation is on ROAD. We hold out each attack capture in turn, train only on the ambient captures, and report F1 and AUROC separately for timing-opaque and timing-transparent attacks at false-positive rates fixed to match the ambient drives. SynCAN tests fine-grained masquerades against CANtropy on its own benchmark. HCRL leave-one-out tests against ACGAN's published setting.
Four checks decide the proposal. First, the net-restricted embedding must come within a few AUROC points of exact nearest-neighbour; otherwise compression loses too much. Second, it must beat both the centroid and the Nyström ablations at equal memory; otherwise the Fréchet construction is decoration. Third, measured score changes under benign jitter must stay below the bound $L\delta$ on held-out ambient drives; otherwise the false-alarm guarantee is not holding in practice. Fourth, the adaptive attacker must be forced to reduce its achievable signal shift substantially relative to its effect against LCCDE and CANtropy. If the second check fails but the others pass, the paper becomes a payload-metric and deployability result, and we will present it that way.
References
- AI-Driven Intrusion Detection Systems (IDS) on the ROAD Dataset: A Comparative Analysis for Automotive Controller Area Network (CAN)
- CANTXSec: A Deterministic Intrusion Detection and Prevention System for CAN Bus Monitoring ECU Activations
- Euclidean distortion and the sparsest cut
- Fréchet Embeddings of Negative Type Metrics
- The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ1
- Shape of the Cloak: Formal Analysis of Clock Skew-Based Intrusion Detection System in Controller Area Networks
- Towards Improving the Trustworthiness of Hardware based Malware Detector using Online Uncertainty Estimation
- CAN Bus Intrusion Detection Based on Auxiliary Classifier GAN and Out-of-distribution Detection
- CANtropy: Time Series Feature Extraction-Based Intrusion Detection Systems for Controller Area Networks