Prune+PlumTree - Finding Eviction Sets at Scale

Prune+PlumTree - Finding Eviction Sets at Scale

Speakers: Tom Kessous, Ben-Gurion University; Niv Gilboa

Conference: IEEE S&P

YouTube: https://www.youtube.com/watch?v=9XqKYEt-arI

Overview

The talk "Prune+PlumTree - Finding Eviction Sets at Scale" by Tom Kessous and Niv Gilboa introduces a groundbreaking algorithm designed to rapidly identify a large number of eviction sets within a CPU cache. An eviction set is a critical component for cache side-channel attacks, representing a collection of memory addresses that all map to the same cache set and are sufficient to evict any other line residing in that set. This research is particularly significant because while previous algorithms focused on finding a single eviction set, many advanced attacks require knowledge of multiple, or even all, eviction sets across the cache.

The existing methodology for mapping an entire cache involves repeatedly executing single-eviction-set discovery algorithms, a process that scales poorly with cache size. Prune+PlumTree addresses this fundamental limitation by providing a novel, highly efficient approach that can map over 98% of an Intel CPU's L3 cache in mere milliseconds. This dramatic speedup — outperforming state-of-the-art methods by two to three orders of magnitude — has profound implications for the practicality and potency of cache side-channel attacks, making them more accessible and scalable for adversaries.

The work not only presents a theoretically sound algorithm with proven asymptotic tightness for Least Recently Used (LRU) replacement policies but also demonstrates its robust implementation on modern Intel CPUs, which employ complex and non-deterministic cache replacement policies. By overcoming significant practical challenges related to these intricate hardware behaviors and measurement errors, Prune+PlumTree represents a substantial leap forward in the understanding and exploitation of cache architectures, underscoring the persistent vulnerability of contemporary systems to such attacks.

Background

▶ Watch: Introduction to eviction sets and their importance (0:00)

Modern CPUs rely heavily on cache memory to bridge the speed gap between the processor and main memory. These caches are typically organized in a set-associative architecture, meaning they are divided into S cache sets, and each set can hold W ways or memory lines. A specific memory address maps to a particular cache set, but within that set, it can reside in any of the W ways. When a new memory line needs to be brought into a full cache set, one of the existing lines must be evicted, a decision governed by the cache's replacement policy (e.g., LRU, pseudo-LRU, or more complex variants).

The timing differences between a cache hit (fast access) and a cache miss (slow access) form the basis of cache side channels. These channels allow an attacker to infer a victim's memory access patterns, and consequently, sensitive data. A cornerstone technique in this domain is the Prime+Probe attack. In this attack, the adversary first "primes" a specific cache set by filling it with their own data (an eviction set). When a victim process accesses memory that maps to this same cache set, it may evict some of the attacker's primed data. The attacker then "probes" their eviction set, measuring access times to determine which of their lines were evicted, thereby inferring the victim's activity.

Finding eviction sets is crucial for these attacks. Historically, cache side channels have been leveraged in a wide array of high-profile vulnerabilities and exploits. These include:

• Meltdown (by Lipp et al.) and Spectre (by Kocher et al.), which exploit speculative execution to leak protected memory.
• Foreshadow (by Van Bulck et al.), which extracts sensitive information from Intel SGX enclaves.
• Attacks extracting cryptographic keys (by Yarom and Falkner, Li et al.).
• Leaking user input (by Schwarzl et al.), derandomizing ASLR (by Oren et al.), spying on browsing activity (by Oren et al.), detecting co-residency in cloud environments (by Zhang et al.), and creating fast cross-core covert channels (by Maurice et al.).

The development of algorithms to find eviction sets has evolved significantly. The initial baseline eviction set algorithm (by Li et al.) ran with a time complexity of S²W², which is quadratic in the cache size. Subsequent improvements included the group elimination algorithm (by Irazoqui et al., and Krishnan et al.), reducing complexity to SW³, and further refinements (by Song and Lee, and Gu et al.) bringing it down to SW². The most recent state-of-the-art for finding a single eviction set was the Prime+Probe algorithm (by Poonal, Gru, and Verdant), achieving a linear time complexity of SW.

However, a critical limitation of all these prior algorithms is that they are designed to find only a single eviction set for a given target address. Many advanced cache attacks, such as template attacks that monitor multiple cache sets or certain Spectre variants that translate a byte of memory into one of 256 cache sets, inherently require knowledge of multiple, or even all, eviction sets. Even when monitoring a single cache set for a specific activity pattern, an attacker often needs to discover most of the eviction sets and test each one. The conventional approach of repeating a single-eviction-set algorithm S times to map the entire cache results in an overall time complexity of S²W, which remains prohibitively slow for large caches, highlighting the need for a more scalable solution.

Key Findings

▶ Watch: Introducing Prune+PlumTree: finding multiple eviction sets (4:00)

The research presented in "Prune+PlumTree" delivers several significant contributions that collectively advance the state of the art in cache side-channel attack primitives:

1. Novel Algorithm for Scalable Eviction Set Discovery: The core contribution is the introduction of the Prune+PlumTree algorithm, which efficiently finds S eviction sets (i.e., maps a substantial portion of the entire cache) in a time complexity of SW log S. This theoretical efficiency is achieved under the assumption of a Least Recently Used (LRU) replacement policy. This represents a drastic improvement over the S²W complexity of repeatedly applying single-eviction-set algorithms.

1. Unprecedented Performance on Modern Intel CPUs: The algorithm was implemented and evaluated on the L3 caches of Intel CPUs across 8th, 9th, and 10th generations. The implementation successfully mapped over 98% of the cache in approximately 40 to 60 milliseconds. This performance is two to three orders of magnitude faster than existing state-of-the-art algorithms, such as the group elimination algorithm (which took 25-71 seconds) and the R-based algorithm (7-48 seconds) for comparable tasks. For instance, in an experiment with a 9th-generation Intel CPU featuring over 16,000 cache sets, Prune+PlumTree mapped almost 100% of these sets in approximately 7 seconds, whereas previous methods could only map 256 eviction sets in about 11 seconds.

1. Adaptation for Complex Replacement Policies: Recognizing that modern Intel CPUs employ complex, non-deterministic replacement policies (e.g., a version of quad-LRU with "leader" and "follower" sets, and dynamic policy selection based on miss rate), the authors developed a robust variant of Prune+PlumTree. This adaptation involves applying specific memory access patterns to manipulate the replacement policy and using repetition in both the prune and plum tree stages to mitigate system and measurement errors, ensuring effective operation despite hardware complexities.

1. Variant for Random Replacement Policy: The paper also details a variant of the Prune+PlumTree algorithm tailored for a random replacement policy, achieving a time complexity of SW² log S. This demonstrates the algorithm's flexibility and applicability beyond LRU-like policies.

1. Asymptotic Tightness Proof: The authors provide a formal proof demonstrating that the SW log S runtime of Prune+PlumTree for LRU replacement policy is asymptotically tight. This theoretical result confirms that, under its specified conditions, the algorithm is as efficient as possible, indicating a fundamental limit to eviction set discovery speed.

These findings collectively establish Prune+PlumTree as a transformative tool for cache analysis, dramatically reducing the time and resources required to map cache structures, thereby enabling more sophisticated and practical cache side-channel attacks.

Technical Deep Dive

▶ Watch: Understanding the Prime+Probe cache side channel attack (5:20)

The Prune+PlumTree algorithm builds upon the principles of the Prime+Probe technique and introduces novel mechanisms for efficient, large-scale eviction set discovery. The objective is to find a minimal eviction set: W memory addresses that all map to the same cache set.

At its core, the algorithm operates in two main stages: the Prune stage and the PlumTree stage.

The Prune Stage

The Prune stage is inspired by the Prime+Probe algorithm for finding a single eviction set. Its goal is to obtain a union of minimal eviction sets.

1. Candidate Pool Generation: The algorithm begins by sampling S W log S random memory addresses. This larger pool is referred to as the candidates.
2. Priming: These candidate addresses are then "primed" into the cache. This means accessing them in a specific order to ensure as many as possible are brought into the cache.
3. Pruning: Following the priming, the candidate pool is traversed again. Any address that experiences a cache miss is discarded. The addresses that result in a cache hit are retained. The crucial observation here is that the remaining, "pruned" candidates form a union of minimal eviction sets. That is, for each cache set, the pruned set contains exactly W addresses that map to it, even if these addresses are intermingled.

To understand the pruning logic, consider the prior Prime+Probe algorithm:

• A pool of random addresses is collected.
• This pool is primed into the cache. Some addresses reside in the cache, others remain in RAM.
• The prune stage discards addresses that experienced a cache miss, leaving only those that were successfully cached. These remaining addresses can be stored simultaneously in the cache.
• Then, a specific target address Z is primed. If Z maps to, say, cache set 3, its insertion evicts the Least Recently Used (LRU) line from set 3.
• Probing the remaining pool again will reveal cache misses only for addresses belonging to set 3 (because Z displaced one, and subsequent probes could displace others in an LRU chain). These missed addresses constitute an eviction set for set 3.

The Prune stage of Prune+PlumTree effectively performs a similar initial pruning across all sets, leading to a large set C containing W addresses for each cache set, but without distinguishing which addresses belong to which set.

The PlumTree Stage

The PlumTree stage is where the union of eviction sets obtained from the Prune stage is separated into N distinct minimal eviction sets. This stage leverages a binary tree structure and a key property known as LRU thrashing.

1. Representatives: The algorithm samples an additional S random memory addresses, designated as representatives. These representatives are crucial for guiding the partitioning process.
2. Binary Tree Construction: The core idea is to inductively divide the set of candidates (C) and representatives into two smaller, corresponding groups, recursively, until each leaf node of the tree represents a distinct eviction set.
3. LRU Thrashing Property: This property is fundamental to how PlumTree distinguishes eviction sets. Suppose addresses A, G, L, and C all map to the same cache set and are arranged in LRU order (A being LRU). If a new address Z is primed into this set, it evicts A. When A is subsequently accessed, it causes a cache miss, but its access also evicts G (as A becomes MRU, and G becomes LRU). Probing G then evicts L, and so on. This chain reaction means that a single traversal of addresses A, G, L, C would result in four cache misses. This "thrashing" behavior is a powerful signal for identifying members of the same eviction set.

PlumTree Walkthrough:

• Start at the root of the binary tree with the full set of candidates (union of eviction sets) and representatives.
• Divide Step: Take half of the current representatives (e.g., W and Z from a set W, X, Y, Z). Prime these chosen representatives into the cache.
• Test Candidates: Immediately after priming the representatives, test all the current candidates.
• Partitioning:
• Candidates that experience a cache miss are grouped and assigned to the left child node. These misses indicate that the primed representatives evicted some of these candidates, suggesting they belong to the same cache sets as the primed representatives.
• Candidates that experience a cache hit are grouped and assigned to the right child node. These hits imply they were not evicted by the representatives, suggesting they belong to different cache sets.
• Recursive Subdivision: This process is repeated recursively for each child node. Each node maintains its own subset of candidates and representatives that correspond to each other.
• Leaf Nodes: The recursion continues until a leaf node is reached, at which point the candidates within that node constitute a distinct minimal eviction set.

Adaptation to Intel CPUs

Modern Intel CPUs present significant challenges due to their complex cache replacement policies, which are often non-deterministic and vary based on cache activity (e.g., employing "leader" and "follower" sets, and dynamically choosing between more LRU-susceptible or thrash-resistant policies). Additionally, system noise and measurement errors can interfere with the precise timing required for cache side channels.

The authors overcome these challenges by:

• Pattern Manipulation: Applying specific memory access patterns to manipulate the CPU's replacement policy, forcing it into a more predictable state that is susceptible to LRU thrashing, which Prune+PlumTree relies upon.
• Repetition: Repeating both the Prune and PlumTree stages multiple times. Instead of building just one tree, several trees are constructed. This repetition helps to eliminate measurement errors and filter out noise, ensuring the robustness and accuracy of the discovered eviction sets.

The combination of the efficient Prune stage to gather a union of eviction sets and the PlumTree stage's intelligent, recursive partitioning leveraging LRU thrashing, makes Prune+PlumTree exceptionally fast and effective even on intricate modern hardware.

Demo / Proof of Concept

▶ Watch: Prune+PlumTree algorithm: overview of two stages (8:10)

While the talk did not feature a live software demonstration in the traditional sense, the "run demo" described for the PlumTree stage meticulously explained the conceptual execution of the algorithm, particularly how the LRU thrashing property and binary tree division work to isolate individual eviction sets. The true "proof of concept" lies in the robust implementation and comprehensive evaluation of Prune+PlumTree on real-world Intel CPUs.

The authors evaluated their algorithm against two prominent state-of-the-art methods: the group elimination algorithm and the R-based algorithm. The experiments were conducted on the L3 caches of Intel CPUs from the 8th, 9th, and 10th generations. A key detail in the evaluation was the concept of a "paged eviction set," defined as an eviction set consisting of addresses starting at offset zero within a memory page. The researchers noted that on Intel CPUs, 64 distinct eviction sets can be interpolated from a single paged eviction set. Therefore, their comparison focused on mapping these paged eviction sets first, and then deriving the full cache mapping.

The results demonstrated a dramatic performance advantage for Prune+PlumTree:

• Coverage and Speed: Prune+PlumTree successfully mapped more than 98% of the target L3 cache in a remarkably short runtime of 40 to 60 milliseconds.
• State-of-the-Art Comparison:
• The group elimination algorithm required 25 to 71 seconds to achieve similar mapping coverage.
• The R-based algorithm improved upon this, but still took 7 to 48 seconds.
• Prune+PlumTree consistently outperformed these methods by two to three orders of magnitude.

To further push the evaluation, an experiment was conducted on a 9th-generation Intel CPU, which features over 16,000 cache sets. The goal was to assess the algorithm's performance in discovering all eviction sets independently, simulating a "random cache" configuration where each set might need individual discovery.

• Paged Eviction Sets: For finding paged eviction sets, Prune+PlumTree achieved almost 100% mapping coverage after just 5 PlumTrees and a total runtime of 40 milliseconds.
• All Eviction Sets Independently: For finding all eviction sets independently, the algorithm succeeded in mapping almost 100% of the over 16,000 eviction sets in approximately 7 seconds. To put this into context, the state-of-the-art algorithms could only map 256 eviction sets in roughly 11 seconds. This stark comparison highlights Prune+PlumTree's unparalleled efficiency and scalability for comprehensive cache mapping.

The empirical results unequivocally validate the theoretical claims of Prune+PlumTree, showcasing its practical viability and superior performance in real-world, complex CPU environments.

Defensive Implications

▶ Watch: PlumTree stage: separating eviction sets using a binary tree (9:20)

The advent of the Prune+PlumTree algorithm significantly escalates the capabilities of attackers employing cache side-channel attacks, creating new challenges for defenders. The ability to map an entire CPU cache with high accuracy and at unprecedented speeds (milliseconds to single-digit seconds) lowers the bar for practical exploitation and expands the scope of potential attacks.

Here are the key defensive implications:

1. Increased Practicality of Attacks: Previously, the time-consuming nature of mapping an entire cache (S²W complexity) often limited cache side-channel attacks to specific, targeted scenarios or required extensive pre-computation. Prune+PlumTree makes comprehensive cache mapping a rapid, on-the-fly operation. This means attackers can quickly gain a detailed understanding of cache topology, facilitating more sophisticated and dynamic attacks, including those against cloud environments where rapid reconnaissance is crucial.

1. Enhanced Template Attacks and Reconnaissance: The algorithm's efficiency in finding multiple eviction sets makes template attacks far more feasible. An attacker can now quickly build a comprehensive set of "templates" (e.g., access patterns for cryptographic operations or user input) across many cache sets, then rapidly monitor a victim's activity for matches. This also allows for more effective reconnaissance, enabling attackers to quickly identify areas of interest within the cache that might correspond to sensitive operations.

1. Challenges for Existing Mitigations: Current mitigations against cache side channels, such as constant-time programming, cache partitioning, disabling hyperthreading, and hardware enclaves like Intel SGX, remain relevant. However, the increased speed and scale of eviction set discovery mean these mitigations face a more formidable adversary. For example, even with SGX, the ability to quickly map the cache could aid in more effective Foreshadow-like attacks or side-channel leakage from enclaved code.

1. Persistent Vulnerability of Modern Hardware: Despite the complex, non-deterministic cache replacement policies in modern Intel CPUs, Prune+PlumTree demonstrates that these complexities can be effectively overcome through pattern manipulation and repetition. This highlights that hardware-level obfuscation or dynamic policies alone may not be sufficient to prevent advanced cache side-channel analysis, underscoring a persistent architectural vulnerability.

1. Need for Advanced Hardware-Level Defenses: The research reinforces the urgent need for more robust, hardware-level mitigations that fundamentally alter or randomize cache behavior in ways that are difficult to predict or manipulate. Solutions like cache randomization or more aggressive cache flushing mechanisms might need to be re-evaluated and strengthened to counter algorithms like Prune+PlumTree.

In summary, Prune+PlumTree represents a significant advancement in offensive cache analysis techniques. Defenders must acknowledge this enhanced capability and consider its implications for their security posture, potentially leading to a re-evaluation of existing side-channel mitigations and the exploration of novel defensive strategies.

Key Takeaways

• Dramatic Speedup: The Prune+PlumTree algorithm finds S eviction sets in SW log S time for LRU caches, outperforming state-of-the-art methods by two to three orders of magnitude on modern Intel CPUs (e.g., mapping >98% of L3 cache in 40-60 milliseconds).
• Scalable Eviction Set Discovery: Unlike previous algorithms focused on single eviction sets, Prune+PlumTree efficiently addresses the critical need of finding multiple or all eviction sets, crucial for advanced cache side-channel attacks like template attacks.
• Robustness on Complex Hardware: The algorithm effectively operates on modern Intel CPUs with intricate, non-deterministic cache replacement policies by employing pattern manipulation and repetition to mitigate system noise and measurement errors.
• Leverages LRU Thrashing: The PlumTree stage cleverly utilizes the LRU thrashing property and a binary tree structure to recursively partition a union of eviction sets into distinct individual sets.
• Asymptotically Tight: The algorithm's SW log S runtime for LRU is proven to be asymptotically tight, indicating its fundamental efficiency and optimal performance under these conditions.
• Elevated Threat Landscape: This research significantly enhances the practicality and scalability of cache side-channel attacks, necessitating a re-evaluation of existing defensive strategies and a focus on more robust hardware-level mitigations.

About the Speaker(s)

Tom Kessous is affiliated with Ben-Gurion University, where he conducted this joint research. His work, as presented in this talk, focuses on the intricate details of CPU cache architectures and the development of highly efficient algorithms for security analysis.

Niv Gilboa is recognized as a co-author of the "Prune+PlumTree" research. His contributions were integral to the development and evaluation of the innovative algorithm presented in the talk.