Privacy Audit as Bits Transmission: (Im)possibilities for Audit by One Run

SoK: So, You Think You Know All About Secure Randomized Caches?

Speakers: Anubhav Bhatla (Indian Institute of Technology Bombay); Hari Rohit Bhavsar (Indian Institute of Technology Bombay); Sayandeep Saha (Indian Institute of Technology Bombay); Biswabandan Panda (Indian Institute of Technology Bombay)

Conference: USENIX Security

YouTube: N/A (This is a peer-reviewed paper, not a recorded talk.)

Overview

This Systematization of Knowledge (SoK) paper, titled "SoK: So, You Think You Know All About Secure Randomized Caches?", delivers a comprehensive and systematic analysis of the microarchitectural modifications, termed "security knobs," employed in state-of-the-art secure randomized Last-Level Cache (LLC) designs. Authored by Anubhav Bhatla, Hari Rohit Bhavsar, Sayandeep Saha, and Biswabandan Panda from the Indian Institute of Technology Bombay, this distinguished artifact award-winning work addresses a critical gap in the understanding of how individual design choices contribute to the overall security posture of randomized caches against prevalent side-channel attacks.

The core objective of this research is to deconstruct complex secure cache designs into their fundamental components and evaluate their isolated and combined impact on security, particularly against conflict-based attacks and occupancy-based attacks. By examining five key knobs—skewing, extra invalid tags, high associativity, replacement policy, and remapping—the authors provide clarity on their effectiveness. The paper concludes that no single knob offers a holistic security guarantee; instead, effective protection emerges only from specific, often intricate, combinations of these microarchitectural modifications, while others yield minimal or no security benefits.

The significance of this work cannot be overstated. Shared LLCs are a prime target for side-channel attacks, which can leak sensitive data like cryptographic keys. While numerous randomized cache designs have been proposed as defenses, their security guarantees are typically evaluated as a monolithic whole. This SoK empowers cache designers and security analysts with a modular understanding of randomized caches, enabling them to make informed decisions for building more robust, efficient, and secure systems tailored to specific threat models and resource constraints.

Background

The Last-Level Cache (LLC), a shared resource across multiple CPU cores, is a performance-critical component that mitigates the latency of off-chip memory access. However, its shared nature makes it a fertile ground for side-channel attacks, which exploit timing differences between cache hits and misses to infer sensitive information. Over the past decade, these attacks have demonstrated the ability to extract cryptographic keys [6, 11, 24], user data in cloud environments [17], and even neural network architectures [44].

Broadly, LLC side-channel attacks can be categorized into three types: flush-based, conflict-based, and occupancy-based. Flush-based attacks, like Flush+Reload [46], rely on shared memory where an attacker flushes a cache line and observes if a victim reloads it, inferring victim access. These attacks are typically mitigated in modern randomized caches by incorporating a Security Domain ID (SDID) per cache line, preventing cross-SDID flushing. This paper, therefore, focuses primarily on conflict-based and occupancy-based attacks.

Conflict-based attacks (also known as eviction-based attacks) exploit the deterministic address-to-set mapping in traditional set-associative caches. Attackers construct an eviction set, a collection of addresses that all map to the same LLC set. By "priming" a cache set with their own data and then "probing" it after a victim's execution (as in the Prime+Probe attack [24]), attackers can observe which of their lines were evicted by victim accesses, thereby inferring victim memory patterns (Figure 1 in paper). The challenge for attackers in randomized caches is that addresses can map to multiple possible sets, making it difficult to find addresses that are always congruent. Attackers instead target partial congruence, where addresses are congruent with a certain probability. Eviction set generation algorithms, such as Single Holdout [24], Group Elimination [29, 41], Conflict Testing [34], and Prime, Prune and Test [34], have varying complexities and efficiencies in constructing these sets.

Occupancy-based attacks, in contrast, do not require eviction sets. They involve an attacker filling a significant portion of the LLC with their own data and then observing changes in their LLC working set due to victim activity. This allows for coarse-grained information leakage, such as in website fingerprinting [32], where an attacker estimates the proportion of cache lines accessed by a victim process.

In response to these threats, randomized cache designs have emerged as a promising defense. Early designs like RPCache [42] and CEASER [28] randomized address-to-set mapping but were quickly compromised by more sophisticated attacks [26, 29, 34]. Subsequent generations introduced more complex modifications: CEASER-S [29] and Scatter-Cache [43] adopted skewed associative designs where cache ways are partitioned into multiple skews, each with a unique set mapping, and addresses are randomly assigned to a skew. Mirage [30] and Maya [7] introduced load-aware insertion and global random eviction, further reducing set-associative evictions (SAEs). More recent designs, like SassCache [19], have even attempted to mitigate occupancy-based attacks through soft partitioning.

Despite the proliferation of these secure randomized cache designs, a significant gap in the literature persists: a lack of systematic evaluation, or ablation study, of the individual microarchitectural modifications, or "security knobs," that constitute these designs. Each new generation often introduces multiple modifications, but their isolated contributions to security, and their interactions, remain largely unquantified. This work aims to fill that void, providing a granular understanding of which knobs are effective, under what conditions, and how they combine to provide meaningful security guarantees.

Key Findings

This SoK systematically dissects and evaluates the microarchitectural security knobs of randomized caches, yielding several critical findings regarding their individual and combined effectiveness against conflict-based and occupancy-based side-channel attacks.

First, the research identifies skewing as the most versatile and fundamental knob, asserting its necessity in all randomized cache designs (Section 6). Skewing significantly reduces the eviction rate for a given eviction set size (Figure 3), making it harder for attackers to cause deterministic evictions. The choice of skew selection policy, whether random skew selection (RS) or load-aware skew selection (LA), has a limited impact on security, with LA providing only marginal benefits, primarily when the cache is not entirely full (Figure 4, Section 3.2.2).

A crucial insight is that decoupling the tag and data store (a feature in designs like Mirage [30] and Maya [7]) provides no measurable security benefit (Section 3.3.1). Its primary impact is on overhead in terms of indirection pointers and design complexity, rather than enhancing security. The security attributed to such designs stems from the extra invalid tags they accommodate, not the decoupling itself.

Regarding extra invalid tags, the study reveals that they are not a standalone security knob; they are only effective when paired with skews, global eviction, and load-aware skew selection (Figure 6, Section 3.3.2). Without this specific combination, extra invalid tags offer no advantage over simply operating a non-skewed cache at lower capacity (Figure 5). This complex interaction implies that while extra invalid tags can provide strong security against conflict-based attacks by making the cache behave closer to a fully associative cache, they introduce significant design complexity and do not inherently offer protection against occupancy-based attacks.

The paper highlights high associativity (extending beyond conventional 16-way designs up to 128 ways) as a powerful and relatively simpler knob for mitigating conflict-based attacks (Section 3.4). Even with just two skews, increasing associativity dramatically reduces the eviction rate, maintaining it near zero for considerably larger eviction sets (Figure 8). This effect is further amplified when combined with load-aware skew selection, extra invalid tags, and global eviction (Figure 9). High-associativity designs require fewer other knobs to achieve strong security, but typically necessitate remapping to invalidate constructed eviction sets.

The replacement policy significantly influences security against conflict-based attacks. Random replacement policies perform demonstrably worse than deterministic policies like Least Recently Used (LRU), Re-Reference Interval Prediction (RRIP), and Randomized Pseudo Least Recently Used (RPLRU) (Figure 10, Figure 11). For conflict-based attacks, LRU and RRIP, which leverage reuse information, make it much harder for an eviction set to evict a target, especially with global eviction, as the target becomes the most recently used item.

Finally, the paper critically examines the impact of these knobs on occupancy-based attacks (Section 4). A key finding is that the knobs primarily designed for conflict-based attacks (skewing, invalid tags, high associativity) offer little to no inherent protection against occupancy-based threats (Figure 15). Instead, solutions like soft partitioning (e.g., SassCache [19]) or ideal static way-based partitioning are required. Interestingly, for occupancy attacks, deterministic replacement policies (like LRU) perform worse than random ones (Figure 16), due to deterministic self-evictions providing more signal to the attacker. Furthermore, local eviction policies provide better security than global ones for low-occupancy-based attacks, a vulnerability demonstrated in designs like Mirage [30] (Figure 17).

In summary, there is no "clear winner" among the knob combinations. High-associativity designs offer a compelling trade-off between design complexity and security for conflict-based attacks, while designs leveraging extra invalid tags achieve strong security but with greater complexity. However, both largely fail to defend against occupancy-based attacks, underscoring the need for dedicated solutions in this domain.

Technical Deep Dive

The core of this SoK lies in its systematic approach to dissecting the microarchitectural components of secure randomized cache designs, termed security knobs. The authors identify five primary knobs: skewing, extra invalid tags, high associativity, replacement policy, and remapping. Each knob, and its potential sub-knobs, is evaluated using rigorous metrics and a custom simulation framework. The goal is to understand not just if a knob works, but why and to what extent.

The evaluation methodology employs two primary metrics for conflict-based attacks:

1. Eviction rate (Metric-I): Defined as the fraction of times a target address is evicted by an eviction set of a given size, over n=1000 iterations. This metric directly reflects the probability of detecting a secret-dependent victim access in attacks like Prime+Probe. To avoid algorithmic bias, initial eviction rates assume an oracle-provided eviction set, later validated against real-world algorithms.
2. Number of evictions to generate an eviction set (Metric-II): This metric quantifies the "difficulty" of constructing an eviction set of a specific size using state-of-the-art algorithms [26,34], directly influencing the necessary remapping period.

For occupancy-based attacks, the evaluation uses cryptographic benchmarks like AES (OpenSSL implementation with T-tables) and modular exponentiation, measuring the number of encryptions required to distinguish between two secret keys. For low-occupancy attacks, the metric is guessing entropy, representing the expected number of guesses an attacker needs for a correct key.

The simulation setup utilizes an extended version of the open-source behavioral cache simulation model from [35], configured with a 2MB LLC and a baseline 16-way associativity, unless otherwise specified.

Security Knobs and Their Impact:

1. Skewing (Section 3.2):

• Mechanism: In a Skew-k cache, an address can map to one of k possible sets, each belonging to a different "skew." This obfuscates cache accesses.
• Random Skew Selection (RS): An incoming cache line is inserted into a randomly chosen skew. As shown in Figure 3, increasing k (e.g., from Skew-2 to Skew-16) generally reduces the eviction rate for a fixed eviction set size. However, even with multiple skews, a non-zero eviction rate persists, indicating potential leakage. The eviction probability pe for random replacement is given by 1−(1−1/nw)^(|E|/k), where nw is total ways, |E| is eviction set size, and k is number of skews.
• Load-aware Skew Selection (LA): An incoming line is inserted into the skew with the largest remaining capacity. Figure 4 demonstrates that LA provides a marginal security improvement over RS, but this gain diminishes with more skews. Its effectiveness is highly dependent on the cache state, primarily providing benefit when the cache is not yet full.

1. Extra Invalid Tags (Section 3.3):

• Mechanism: Designs like Mirage [30] provision extra invalid tags to ensure an incoming cache line can always find space without causing an SAE. This is achieved by maintaining a threshold for valid entries and triggering eviction when exceeded.
• Decoupling Tag and Data Store: The paper definitively states that decoupling the tag and data store, as seen in Mirage, has no security impact (Section 3.3.1). Its purpose is solely to accommodate extra invalid tags, incurring overhead without security benefit.
• Dependency on Skews: Extra invalid tags are ineffective without skews (Figure 5). A non-skewed cache with invalid tags simply acts as a lower-capacity CEASER cache.
• Interplay with Eviction and Skew Selection: Crucially, extra invalid tags are only effective when combined with global eviction (GE) and load-aware skew selection (LA) (Figure 6). Combinations with random skew selection (GE+RS+Inv) or local eviction (LE+LA+Inv, LE+RS+Inv) show no security advantage (Figure 5, Figure 7). This specific "GE+LA+Inv" combination works because LA distributes insertions, and GE, in conjunction with invalid tags, prevents any single skew from becoming full, thereby maintaining a low eviction rate.

1. High Associativity (Section 3.4):

• Mechanism: Increasing the number of ways (W) in a cache set. Prior work explored up to 16 ways, but this study extends to 128 ways.
• Effectiveness: High associativity is a powerful knob. Figure 8 demonstrates that increasing associativity from 16 to 128 ways in a Skew-2 cache drastically reduces the eviction rate, keeping it near zero for very large eviction sets (up to ≈270 entries for Skew-2-Ass128). This knob acts as a dominant factor, requiring a significantly larger eviction set to evict a target.
• Combination: High associativity combined with LA, extra invalid tags, and GE can achieve near-zero eviction probability even for large eviction sets (Figure 9), albeit with increased complexity.

1. Replacement Policy (Section 3.5):

• Policies Evaluated: Random (Ran), Least Recently Used (LRU), Randomized Pseudo Least Recently Used (RPLRU) [37], and Re-Reference Interval Prediction (RRIP) [16].
• Local Eviction (High Associativity Context): For highly associative skewed caches without invalid tags, random replacement performs significantly worse than LRU, RRIP, and RPLRU (Figure 10). This is because random eviction makes it easier to evict a target even without completely filling a set, as each entry has a 1/nw probability of eviction. LRU-like policies, which use reuse information, make eviction much harder.
• Global Eviction (Invalid Tags Context): When combined with extra invalid tags and global eviction, global LRU and global RRIP policies outperform global random eviction (Figure 11). This is because global LRU makes the target address the most recently used entry upon access, requiring the entire cache to be filled before it can be evicted by an eviction set.

1. Remapping (Section 3.6):

• Necessity: Remapping changes the address-to-set mapping by updating the block cipher key, invalidating any previously constructed eviction sets. It's crucial when eviction sets can be built within a finite time.
• Remapping Period (R): This is a performance-security trade-off. A longer period improves performance but gives attackers more time.
• Evaluation (Metric-II): Figure 12 shows the number of LLC evictions required to construct eviction sets achieving a 30% eviction rate. High-associativity designs significantly increase this number. For Skew-2-Ass64, 3.7 million LLC evictions are needed, resulting in a remapping period R ≈ 103. For Skew-2-Ass128, 7.8 million evictions are needed, yielding R ≈ 228. This contrasts sharply with Skew-16, which requires only 2.6 million evictions and R ≈ 39.
• Eviction Set Algorithms: Conflict Testing [34] is found to be more efficient than Prime, Prune and Probe [26], requiring fewer LLC evictions for comparable eviction set sizes (Table 2).
• Cache Size Impact: While the eviction rate for high-associativity designs is largely unaffected by cache size (Figure 13), the number of evictions required to construct an eviction set increases linearly with cache size (Figure 14). For a 96MB cache, Skew-2-Ass128 would require approximately 381 million LLC evictions.

Occupancy-Based Attacks (Section 4):

• Limited Efficacy of Conflict-Mitigating Knobs: The study confirms that knobs designed for conflict-based attacks (skewing, invalid tags, high associativity) offer minimal protection against occupancy-based attacks (Figure 15). Designs like CEASER-S, Mirage, and Skew-2-Ass128 perform similarly to a fully associative random replacement (FA-RR) cache.
• Replacement Policy Impact: In contrast to conflict-based attacks, random replacement policies generally offer better security against full-occupancy attacks than deterministic ones like LRU (Figure 16). This is because deterministic self-evictions provide a clearer signal of victim access patterns, whereas random evictions introduce noise.
• Partitioning Solutions: SassCache [19] (a soft-partitioning design) and especially static way-based partitioning provide significantly better security against occupancy-based attacks (Figure 15), as they offer a degree of isolation between security domains.
• Low-Occupancy Attacks: For low-occupancy scenarios, local eviction policies are superior to global ones. Mirage, with its global random eviction, is particularly vulnerable to low-occupancy attacks [13], performing worse than ScatterCache and CEASER-S. High-associativity designs (Skew-2-Ass64 and Skew-2-Ass128) show similar resilience to SassCache and ScatterCache in these scenarios (Figure 17).

Demo / Proof of Concept

This paper presents a Systematization of Knowledge (SoK) derived from extensive simulation experiments and analytical models, rather than a live demonstration or a traditional proof-of-concept exploit. The authors leveraged and extended several open-source simulation models to conduct their rigorous evaluation.

Specifically, the results for eviction rates and eviction set generation (Figures 3-14 and Table 2) were obtained using an extended version of the behavioral cache simulation model from [35]. Simulations for occupancy-based attacks (Figures 15-16) were performed by extending the CacheFX simulator [18]. For the analysis of low-occupancy-based attacks (Figure 17), an extended simulation model from [13] was utilized.

The authors have publicly released all their modifications and accompanying scripts (available at https://doi.org/10.5281/zenodo.15529618) to ensure full reproducibility of their findings during artifact evaluation and for broader research community use. This commitment to open science allows other researchers to replicate and build upon their detailed analyses of security knobs in randomized cache designs.

Defensive Implications

The systematic analysis presented in this SoK offers crucial insights for both hardware architects designing future processors and security analysts evaluating existing systems. The findings highlight the nuanced interplay of microarchitectural features in achieving robust cache security.

For cache designers, the primary implication is that a piecemeal approach to security is insufficient. While skewing is unequivocally a foundational knob that should be integrated into all randomized cache designs, its effectiveness is enhanced or diminished by its interaction with other features. High associativity, particularly extending beyond 16 ways, emerges as a powerful and relatively simpler mechanism to significantly boost resilience against conflict-based attacks, requiring fewer additional complex knobs. This makes it a compelling option for designs seeking strong conflict-based attack mitigation with manageable overhead. However, designers must recognize that high-associativity designs will likely still require remapping to maintain security over time, necessitating careful consideration of the remapping period.

Conversely, while extra invalid tags can provide strong security against conflict-based attacks by mimicking fully associative behavior, they demand a specific and complex combination of other knobs (skews, global eviction, and load-aware skew selection) to be effective. This complexity, coupled with the inherent storage, area, and power overheads (as noted by Maya [7]), must be weighed against the security benefits. Furthermore, designers employing global eviction strategies (e.g., Mirage) should be acutely aware of their vulnerability to low-occupancy-based attacks, prompting a re-evaluation of such policies.

The choice of replacement policy is also critical. For conflict-based attacks, deterministic policies like LRU or RRIP are demonstrably superior to random policies. However, this preference reverses for full-occupancy-based attacks, where random eviction can introduce more noise and deter attackers. This highlights a fundamental trade-off: a policy optimized for one attack class may inadvertently weaken defenses against another.

For security analysts and system architects, the paper underscores that "secure randomized cache" is not a monolithic concept. Designs optimized solely for conflict-based attacks will generally provide little to no protection against occupancy-based attacks. This implies that evaluating system security against side channels requires understanding the specific attack vectors being considered. To mitigate occupancy-based attacks, dedicated solutions like soft partitioning (e.g., SassCache) or more robust static hardware partitioning are essential, as the general-purpose security knobs for conflict mitigation are largely ineffective in this domain. Analysts should scrutinize designs for their specific defenses against both attack classes and recognize that a system might be secure against Prime+Probe but vulnerable to website fingerprinting or key recovery via occupancy channels.

Ultimately, this SoK provides a granular understanding of the randomized cache design space, enabling the development of more tailored and robust defenses. It emphasizes the need for future cache architectures to explicitly account for the distinct challenges posed by both conflict-based and occupancy-based attacks, potentially through a combination of effective knob configurations and dedicated partitioning mechanisms.

Key Takeaways

• Skewing is a Universal Knob: Skewing is identified as the most versatile and essential microarchitectural knob, significantly reducing eviction rates and thus serving as a fundamental component for all secure randomized cache designs.
• High Associativity Offers Potent, Simpler Security: Extending cache associativity to higher levels (e.g., 64 or 128 ways) provides strong security against conflict-based attacks with fewer accompanying knobs, making it a powerful and relatively less complex design choice, though it generally necessitates remapping.
• Extra Invalid Tags Demand Complex Combinations: While extra invalid tags can achieve strong conflict-based attack mitigation, their effectiveness is highly conditional, requiring specific combinations with skews, global eviction, and load-aware skew selection; they also introduce design complexity and overhead without inherent benefits against occupancy attacks.
• Replacement Policies Have Dual Impact: Deterministic replacement policies like LRU and RRIP are superior for defending against conflict-based attacks, but paradoxically, random replacement policies can offer better resilience against full-occupancy-based attacks by introducing more noise.
• Occupancy Attacks Require Dedicated Defenses: Knobs designed primarily for conflict-based attacks offer limited to no protection against occupancy-based attacks; dedicated solutions like soft or hard partitioning are crucial for effective mitigation, and global eviction policies can increase vulnerability to low-occupancy attacks.
• Decoupling Tag/Data Stores Lacks Security Value: Decoupling the tag and data store offers no measurable security benefit, primarily adding overhead and complexity, and its perceived security contribution is solely due to the presence of extra invalid tags it enables.

About the Speaker(s)

The authors of this distinguished Systematization of Knowledge paper are Anubhav Bhatla, Hari Rohit Bhavsar, Sayandeep Saha, and Biswabandan Panda, all affiliated with the Indian Institute of Technology Bombay. Their collective expertise lies at the forefront of hardware security, with a particular focus on microarchitectural side-channel attacks and the development of robust defensive mechanisms for modern computing systems. This research, presented at USENIX Security 2025, reflects their commitment to a deeper, more systematic understanding of secure cache designs, moving beyond black-box evaluations to analyze the granular impact of individual architectural modifications. Their work provides invaluable insights for advancing the security of shared resources like the Last-Level Cache, contributing significantly to the academic discourse and practical implementation of secure hardware.