MileSan: Detecting Exploitable Microarchitectural Leakage via Differential Hardware-Software Taint Tracking

TL;DR

MileSan is an RTL sanitizer that detects arbitrary exploitable information leakage by checking for the architecturally-observable differences between architectural and microarchitectural information flows. We built RandOS, a fuzzer that employs MileSan for program generation and leakage detection, and found 19 new leakages (of which 13 were assigned CVEs) across 5 RISC-V CPUs. Below is a video of RandOS discovering leakage using MileSan:

Motivation

Microarchitectural performance optimizations introduce information flows inside CPU implementations that exceed those defined by the Instruction Set Architecture (ISA). Microarchitectural vulnerabilities, such as constant-time violations and various classes of transient execution attacks, are subsets of these excessive information flows. We observe that an exploitable microarchitectural leakage is an excessive information flow that can affect the time it takes for the CPU to execute a particular instruction, creating a timing covert channel. We thus desing MileSan, the first RTL sanitizer that detects exploitable microarchitectural leakage by checking for the architecturally-observable differences between architectural and microarchitectural information flows.

The Overfitting Problem

Existing pre-silicon microarchitectural fuzzers overfit in three fundamental ways:

  1. They overfit to particular microarchitectural structures by manually tagging the ones where information may leak from or to. The former misses out on other leaky structures, the latter may result in detecting unexploitable cases of information leakage.
  2. They overfit to particular vulnerabilities by bootstrapping program generation with seeds that trigger known vulnerabilities. They consequently fail to generate test cases that are sufficiently different to trigger new vulnerabilities.
  3. They overfit to particular classes of vulnerabilities by basing program generation on suitable templates. As such, they cannot trigger vulnerabilities that do not match their templates.

The crux of the overfitting problem is the lack of a generic mechanism for detecting exploitable information leakage without making assumptions on the information leakage path or the shape of the programs that can trigger the information leakage

Architectural and Microarchitectural Information Flows

Architectural Information Flows (AIFs) are information flows derived from the ISA. E.g., an arithmetic instruction propagates information flows from their source registers to their destination registers, and a conditional branch propagates taint from the source register to the PC. However, the latter causes an architectural taint explosion, as all architectural elements in the CPU depend on the PC’s value in one way or another and thus get tainted within a few cycles. This blinds all microarchitectural leakage and therefore needs to be avoided.

Microarchitectural Information Flows (MIFs) are the logical information flows in the CPU’s microarchitectural implementation. In CPUs, MIFs are a superset of AIFs, as any information flow that is architecturally observable materializes in the microarchitecture, which concretely implements the architectural specification. However, microarchitectural performance optimizations introduce additional information flows that affect timing, i.e., the timed sequence of PC values. When such an information flow is tainted, it causes a microarchitectural taint explosion.

MileSan

The Microarchitectural leakage Sanitizer (MileSan) is a new solution that utilizes the insight that microarchitectural information leakage vulnerabilities can be detected based on the difference between architectural and microarchitectural information flows from the secret.

  1. It calculates architectural flows with (static) software-level taint tracking when considering the program and secret memory locations.
  2. It computes microarchitectural flows through (dynamic) hardware-level information flow tracking when executing such programs and considering the same secret memory locations.
  3. It checks for the propagation of such flows to the program counter (i.e., causing microarchitectural taint explosions) to detect excessive microarchitectural information flows that are architecturally visible.

This allows MileSan to detect microarchitectural leakage for arbitrary test programs and CPU implementations, without making assumptions on the microarchitecture or software that triggers the leakage.

RandOS

RandOS is a new microarchitectural fuzzer that generates random programs with strictly determined architectural information flow of secret data. The programs span across privilege levels and address space layouts, akin to random operating systems. Only a subset of pairs of privileges and layouts, which we refer to as taint source domains, are granted access to tainted data. This enables the detection of microarchitectural leakage within and across security domains using MileSan. Below a visualization of the resulting access policies.

Leakage identification

RandOS generates long and complex programs and therefore comes with leakage identification facilities to facilitate triaging. Given an leaky RandOS program, they determine the following:

  • The architecturally executed code sections responsible for the leakage.
  • The microarchitecturally relevant (e.g., transiently executed) code sections required to trigger the leakage.
  • The leaked memory addresses.

Discovered vulnerabilities

We discovered 19 new vulnerabilities, of which 13 were assigned CVEs at the time of writing. The vulnerabilities include transient execution vulnerabilities, as well as constant-time violations. See below for the complete list of new vulnerabilities.

Paper and code:

MileSan will be presented at CCS’25 and is, together with RandOS, readily available here.

Frequently Asked Questions

I am using one of the CPUs where you discovered a vulnerability. Am I affected?

It depends on your application. We provide details on the discovered vulnerabilities and how they can be exploited in our full paper.

Does MileSan only work on RISC-V?

The principles of MileSan are universal and not limited to any ISA. However, as of now, we have only implemented MileSan for RISC-V.

MileSan does not report leakage for my PoC program and CPU implementation. Can I be sure my CPU is not affected?

Yes, mostly. MileSan inherits the formal guarantees from the underlying IFT mechanism. However, although we have not encountered such cases, simulator bugs (as reported here) could in theory result in false negatives.

After patching all the discovered vulnerabilities, MileSan does not report any further leakage for programs generated by RandOS. Can I be sure that my CPU perfectly secure?

No. When using MileSan with RandOS, it only guarantees security of the CPU with respect to the (non-exhaustive) set of test cases generated by RandOS.

Is MileSan scalable to arbitrary design complexities?

MileSan’s scalability is limited by the underlying IFT mechanism only. The current implementation supports CellIFT and HybridIFT, where the latter allows application to very large CPUs, such as OpenC910.

Acknowledgements

This work was supported by the Swiss State Secretariat for Education, Research and Innovation under contract number MB22.00057 (ERC-StG PROMISE).