TL;DR
This paper introduces a novel model to quantify the security of CPU caches, specifically focusing on how information is absorbed and extracted by different cache replacement policies. By developing a formal framework and an algorithm, they provide the first systematic security analysis of common policies like LRU, FIFO, and PLRU, offering crucial insights for designing more secure hardware.
What Problem Does This Paper Address?
Modern computer architectures rely heavily on shared resources like caches to improve performance, energy efficiency, and cost. However, this sharing creates security vulnerabilities through side channels, where one program can infer information about another by observing its resource usage. While many attacks exploit CPU caches, there's a significant lack of formal methods to quantify the security implications of different cache designs, particularly their replacement policies. This gap makes it difficult for designers to make informed trade-offs between performance and security. The paper aims to fill this void by providing a principled way to measure how much information a cache can "absorb" from a program and how much an adversary can "extract" from it.
Methods
The authors model caches as Mealy machines, which are finite automata that map sequences of memory block accesses to sequences of cache hits and misses. They then define two key security metrics:
- Absorption: This quantifies the amount of information a program can leak into the cache. They model this by counting the number of reachable cache states given a set of possible program inputs (traces).
- Extraction: This quantifies the information an adversary can learn about the cache state by probing it (making memory accesses and observing latencies). They develop a novel model for adaptive adversaries who can strategically choose their probes based on previous observations. This model leads to an algorithm for computing the maximum information leakage.
They also introduce a formal definition of "footprint" (the number of distinct memory blocks a program accesses) to analyze absorption independently of specific programs. For extraction, they define "depleted probes" and "knowledge sets" to characterize the adversary's understanding of the cache state.
Datasets
Not discussed in the paper. The authors use theoretical models and simulations based on common cache replacement policies and abstract program behaviors. They do mention using CacheAudit static analyzer results for AES 256 in their experimental evaluation, but this is not a dataset in the traditional sense.
Key Insights and Ideas
- Cache replacement policies have a direct impact on security: The choice of replacement policy (LRU, FIFO, PLRU) significantly influences how much information is absorbed and how easily it can be extracted.
- Absorption and extraction are not always correlated: A policy that absorbs a lot of information doesn't necessarily make it easy to extract. FIFO, for instance, can absorb little information when the footprint is small, but this doesn't mean it's inherently secure.
- Empty vs. Filled Caches: The initial state of the cache (empty or filled) dramatically affects absorption. Empty caches generally lead to higher absorption, as new accesses are more likely to be misses and reveal more about the program's behavior.
- PLRU's peculiar behavior: PLRU can sometimes lead to higher absorption than LRU or FIFO, especially in empty caches, due to its complex way of managing cache lines and potentially leaving "holes."
- Adaptive adversaries are powerful: The paper's model for adaptive adversaries highlights that their ability to strategically probe the cache can significantly increase the amount of information they can extract.
- A unified framework for cache security: The paper provides a much-needed formal model and algorithmic tools to analyze cache security, moving beyond ad-hoc attack analyses.
Key Results
- Comparative Security Ranking: The security ranking of policies varies with memory demand. FIFO can be more secure with low demand, while LRU generally offers better security. PLRU often performs worse than LRU and FIFO.
- Absorption Bounds: They derive formulas for the absorbed information for LRU, FIFO, and PLRU under different conditions (filled/empty cache, footprint size). For example, for a filled cache, LRU's absorption is always maximal, while FIFO's absorption is zero when the footprint is smaller than associativity.
- Extraction Bounds: They establish upper bounds on the maximum information leakage for shared and disjoint memory attackers. For LRU and FIFO with a shared attacker, the leakage is bounded by $2^A$ (where A is associativity). For PLRU, leakage increases with footprint.
- Algorithm for Extraction: They present an algorithm that computes the maximum information leakage for any Mealy machine, which can be used to improve the precision of static analyzers like CacheAudit. This algorithm demonstrated significant improvements, yielding up to 50 bits more leakage for AES 256.
- Experimental Validation: Figures in the paper visually demonstrate these results, showing how absorption and extraction change with footprint and cache size for different policies and attacker types.
Limitations and Future Work
- Deterministic Model: The current model assumes deterministic programs and adversaries. Future work could extend the model to handle randomized replacement policies and probabilistic adversaries using Markov Decision Processes.
- Specific Attack Model: The paper focuses on a specific type of adaptive attacker. Exploring other attacker models or countermeasures could be valuable.
- Program-Dependent Analysis: While the paper provides program-independent analysis, its application to real programs (like AES) shows that the extracted information can be significantly higher than theoretical bounds suggest, indicating the importance of program-specific analysis.
- Tightness of Bounds: Some bounds, particularly for PLRU extraction, are noted as potentially not being tight. Further refinement of these bounds could be an area of future research.
Summary updated