PaperlayerView exact revision on arXiv

Source-linked AI summary

Theory and Practice of Finding Eviction Sets

Pepe Vila, Boris Köpf, José Francisco Morales

arXiv:1810.01497v2cs.CR

TL;DR

Finding small eviction sets is important for several microarchitectural attacks, but the algorithms for doing so had not been systematically studied. The paper formalizes the problem, analyzes random-set probabilities, and develops threshold-group-testing algorithms for linear-time reduction. Its evaluation shows faster discovery and identifies practical conditions affecting reliability, including adaptive replacement and TLB thrashing.

  • Problem

    Algorithms for finding small eviction sets lacked a systematic analysis despite their importance to cache side-channel, rowhammer, and speculative-execution attacks.

  • Method

    The paper formalizes eviction-set discovery, analyzes random-set probabilities, and applies threshold group testing to reduce eviction sets to minimal cores.

  • Results

    The algorithms reduce eviction sets in linear time rather than quadratic time and enable finding small eviction sets much faster than before.

  • Takeaways & Limitations

    Eviction sets can be computed in scenarios without control over cache-set mapping, while the evaluation identifies conditions under which the algorithms succeed or fail.

Abstract

from arXiv · show

Many micro-architectural attacks rely on the capability of an attacker to efficiently find small eviction sets: groups of virtual addresses that map to the same cache set. This capability has become a decisive primitive for cache side-channel, rowhammer, and speculative execution attacks. Despite their importance, algorithms for finding small eviction sets have not been systematically studied in the literature. In this paper, we perform such a systematic study. We begin by formalizing the problem and analyzing the probability that a set of random virtual addresses is an eviction set. We then present novel algorithms, based on ideas from threshold group testing, that reduce random eviction sets to their minimal core in linear time, improving over the quadratic state-of-the-art. We complement the theoretical analysis of our algorithms with a rigorous empirical evaluation in which we identify and isolate factors that affect their reliability in practice, such as adaptive cache replacement strategies and TLB thrashing. Our results indicate that our algorithms enable finding small eviction sets much faster than before, and under conditions where this was previously deemed impractical.

I. INTRODUCTION

Modern microarchitectural attacks depend on efficiently finding small eviction sets, but existing methods lacked systematic analysis. This paper formalizes the problem, develops linear-time reduction algorithms, and evaluates their reliability and practical performance.

  • Motivation: Finding minimal eviction sets is fundamental to cache side-channel, rowhammer, and speculative-execution attacks, yet prior algorithms lacked in-depth analysis of complexity, performance, correctness, and scope.Eviction sets let attackers control cache state and probe whether a victim modified it.
  • Approach: The paper provides the first systematic study of eviction-set discovery, combining formal problem analysis, novel algorithms, and empirical evaluation.The study addresses both theoretical and practical aspects of the problem.
  • Theory: The probability that random virtual addresses form an eviction set rises rapidly with set size, motivating a two-step process that first obtains a sufficiently large set and then reduces it.Small address sets are unlikely to be eviction sets, while larger sets provide favorable starting points for reduction.
  • Algorithms: Threshold-group-testing ideas reduce an eviction set of size n to its minimal core using O(n) memory accesses, improving over the quadratic state of the art.The algorithms use cache-side-channel tests as an oracle for deciding whether address groups are eviction sets.
  • Evaluation: On Intel Skylake, execution time grows linearly in practice, producing significant speed-ups and enabling eviction-set computation without control of virtual-to-cache-set mapping.The evaluation also isolates TLB and cache-replacement effects, identifying both highly reliable and degraded operating conditions.
  • Implications: The paper supplies an evaluation tool for the tests and algorithms and identifies conditions relevant to improving robustness and developing principled countermeasures.Its practical analysis covers adaptive replacement behavior and TLB-related effects.

B. Virtual Memory

Virtual memory translates virtual addresses to physical addresses through page tables, while cache-set congruence depends on physical set and slice bits. The paper defines eviction sets as address collections with enough congruent members to evict a target or arbitrary cache content.

  • B. Virtual Memory: Virtual addresses are translated to physical addresses by the MMU using page tables, with TLBs caching recent translations.Four-level page walks serve 4KB pages; 2MB huge pages can use a page-directory entry directly.
  • B. Virtual Memory: Cache congruence requires virtual addresses’ translated physical addresses to share both set-index and slice bits.Addresses sharing only set-index bits are partially congruent.
  • B. Virtual Memory: An eviction set for x excludes x and contains at least a addresses mapping to x’s cache set; an arbitrary eviction set contains a removable member satisfying that condition.Sequentially accessing enough congruent addresses is intended to evict prior cache content.
  • B. Virtual Memory: The eviction-set intuition depends on cache replacement policies in which a sequence of a misses evicts previous content.The stated condition holds for permutation-based policies such as LRU, FIFO, and PLRU, but is only partially satisfied by modern policies.

B. Testing Eviction Sets

The paper models collision probability for addresses sharing user-controlled set-index bits and uses timing-based eviction tests to detect congruence without physical-address information. Control over page-derived bits determines the remaining collision difficulty.

  • B. Testing Eviction Sets: User programs test eviction sets through cache-timing measurements because physical-address bits are unavailable.The tests rely on distinguishing cache hits from misses using a clock.
  • B. Testing Eviction Sets: Test 2 iterates over a set twice and classifies it using the second iteration’s total time, but is susceptible to timing noise.The first iteration populates the cache before the second measurement.
  • B. Testing Eviction Sets: Test 3 improves arbitrary-set testing by timing each second-iteration access and counting misses individually.This reduces the window for spurious measurement effects but increases executed instructions.
  • B. Testing Eviction Sets: Random candidate sets are chosen to agree on all γ controllable set-index bits, leaving uncontrolled set-index and slice bits to determine collisions.The analysis assumes virtual-to-physical translation is random on those uncontrolled bits, representing a worst case for the adversary.
  • B. Testing Eviction Sets: For the Skylake example, collision probability is 2^-3 with huge pages, 2^-7 with 4KB pages, and 2^-13 without set-index control.These cases correspond respectively to γ=10, γ=6, and γ=0.

Probability of a Set to be an Eviction Set for x:

The paper derives probabilities and search costs for random eviction sets, showing that arbitrary-set eviction becomes likely faster than specific-address eviction as set size grows. These results motivate first finding a large set and then reducing it.

  • Probability of a Set to be an Eviction Set for x:: A set is an eviction set for a specific address when at least a members map to that address’s cache set.The specific-address probability is modeled with a binomial random variable.
  • Probability of a Set to be an Eviction Set for x:: The arbitrary-address probability treats addresses as balls distributed across cache-set bins and asks whether any bin exceeds a addresses.The exact cumulative multinomial calculation is approximated using Poisson distributions because it is expensive for large N.
  • Probability of a Set to be an Eviction Set for x:: The multinomial probability grows faster with set size than the binomial probability, so a set is more likely to evict an arbitrary address than a specific address.Figure 3 compares the arbitrary and specific models for P(C)=2^-7.
  • Probability of a Set to be an Eviction Set for x:: The expected cost of finding an initial eviction set is O(N/p(N)) memory accesses when testing candidate sets of size N costs O(N).The factor 1/p(N) is the expected number of candidate sets tested.
  • Probability of a Set to be an Eviction Set for x:: Small candidate sets require many trials, while sufficiently large sets expose the linear cost of each test.Figure 4 compares huge-page, 4KB-page, and no-control adversaries through their different collision probabilities.
  • Probability of a Set to be an Eviction Set for x:: Because random small sets are unlikely to evict, the standard strategy first finds a large eviction set and then reduces it to a minimal core.The paper reports a linear-memory-access reduction method, replacing the usual quadratic baseline and enabling larger initial sets.

A. The Baseline Algorithm

The baseline algorithm repeatedly tests whether removing one address preserves eviction, recording addresses whose removal breaks eviction until a minimal core remains. This procedure is correct but requires quadratic memory accesses, motivating a linear-time alternative.

  • A. The Baseline Algorithm: The baseline algorithm is presented as prior work whose quadratic cost raises the question of whether hiding physical-address mapping can prevent small eviction-set computation.The broader literature commonly first finds a large eviction set and then reduces it to a minimal core.
  • A. The Baseline Algorithm: Algorithm 1 tests whether removing each candidate preserves eviction, records indispensable addresses, and removes candidates until the minimal core remains.The test includes already identified congruent addresses, allowing the scan to continue even when fewer than a cache's associativity remain.
  • A. The Baseline Algorithm: The baseline reduces an eviction set of size N in O(N^2) memory accesses.The quadratic bound follows because there can be O(N) iterations and each eviction test can access O(N) addresses.
  • A. The Baseline Algorithm: Variants that reinsert tested addresses remain asymptotically quadratic but add redundancy intended to combat errors.The cited variant continues until the set reaches the cache associativity size.

2) A Linear-Time Algorithm for Computing Minimal Eviction Sets:

The paper recasts eviction testing as threshold group testing and uses this connection to reduce candidate sets to minimal eviction sets with linear memory-access complexity. The same asymptotic improvement extends to eviction sets for arbitrary addresses.

  • 2) A Linear-Time Algorithm for Computing Minimal Eviction Sets:: Testing whether S evicts x is a threshold group test for congruence, with thresholds l = a − 1 and u = a.The test is positive when at least a addresses in S are congruent with x and negative otherwise.
  • 2) A Linear-Time Algorithm for Computing Minimal Eviction Sets:: Threshold group testing identifies p positive elements using O(p log |S|) tests by repeatedly discarding a suitable partition subset.Each iteration reduces the candidate set by a factor of approximately p/(p+1), rather than by a constant.
  • 2) A Linear-Time Algorithm for Computing Minimal Eviction Sets:: Algorithm 2 reduces an eviction set S to its minimal core using O(a^2N) memory accesses, which is linear in N for fixed associativity.Its recursion partitions the set, performs tests on subsets, and recurses on one surviving subset; the resulting recurrence is Θ(N).
  • 2) A Linear-Time Algorithm for Computing Minimal Eviction Sets:: Arbitrary-address eviction sets are more likely than specific-address sets, so reduction can begin with smaller candidate sets when the target address is irrelevant.Both reduction algorithms can be adapted by replacing the specific-address test with an arbitrary-address test.
  • 2) A Linear-Time Algorithm for Computing Minimal Eviction Sets:: For arbitrary target addresses, the group-testing algorithm retains O(N) memory-access complexity, while the baseline remains O(N^2).The bounds coincide with the specific-address case because both eviction tests are linear in the tested-set size.

D. Computing Minimal Eviction Sets for Many Virtual Addresses

The paper extends minimal-eviction-set computation to pools containing many virtual addresses by repeatedly finding one set, scanning for congruent addresses, and removing them. The evaluation isolates hardware and memory-translation factors that affect reliability and timing.

  • D. Computing Minimal Eviction Sets for Many Virtual Addresses: A pool P can be processed by finding one arbitrary-address eviction set, using it to test individual addresses, and repeating until no further sets remain.With linear reduction, a linear scan, and a constant number of cache sets, the procedure requires O(|P|) memory accesses.
  • D. Computing Minimal Eviction Sets for Many Virtual Addresses: The study evaluates robustness and execution time because adaptive replacement, TLB activity, cache and TLB misses, and implementation details fall outside the theoretical model.The experiments test when reductions are reliable and whether memory-access complexity predicts real-time performance.
  • D. Computing Minimal Eviction Sets for Many Virtual Addresses: Experiments run on Intel Skylake and Haswell systems, using address pools selected to simulate different levels of control over cache-set index bits.The setup includes huge pages, 4KB pages, and no control over set-index bits.
  • D. Computing Minimal Eviction Sets for Many Virtual Addresses: Adaptive replacement policies can reduce eviction and reduction rates because targeted sets may not match the assumed model or may be influenced by accesses to other sets.Skylake cache set zero is used as a comparatively controlled setting for isolating this effect.
  • D. Computing Minimal Eviction Sets for Many Virtual Addresses: TLB misses can create false-positive eviction tests through page walks that implicitly access memory and may evict the target address.Linked-list access patterns and randomized order are used to reduce hardware-prefetching effects, while repeated timing measurements reduce jitter.

B. Evaluating Robustness

Experiments show that reliability depends on cache replacement behavior and TLB activity, while the novel reduction exhibits linear runtime and substantial practical speedups over the quadratic baseline. Under controlled conditions, empirical behavior generally follows the theoretical analysis, with deviations for huge pages and noisy settings.

  • B. Evaluating Robustness: With interference mitigated, Skylake eviction and reduction rates closely match each other and the theoretical prediction for small pages, while huge-page rates remain below prediction.The idealized evaluation targets cache set zero and mitigates TLB, replacement-policy, prefetching, and jitter effects.
  • B. Evaluating Robustness: Replacement-policy effects substantially reduce eviction and reduction rates on Haswell and on nonzero Skylake cache sets.The reported decrease is attributed to model mismatch and interference from accesses to other cache sets.
  • B. Evaluating Robustness: For small pages, reduction rates decline beyond N > 1500 as TLB thrashing creates false positives, whereas huge-page translations avoid this specific capacity threshold.The threshold coincides with Skylake's reported TLB capacity of 1536 entries.
  • B. Evaluating Robustness: The orange baseline curve grows quadratically with initial-set size, whereas the blue novel-algorithm curve grows linearly.Measured absolute times include constant factors from repeated timing measurements and metric-collection overhead.
  • B. Evaluating Robustness: For large sets, the novel reduction outperforms the quadratic baseline; at size 3000, the measured improvement is a factor of 10.For small sets, the reduction advantage is less relevant, while repeated attempts to find an initial eviction set can dominate total cost.
  • B. Evaluating Robustness: For small pages, linear-time reduction lowers the cost of computing eviction sets by more than 7×, while the limit case improves over the quadratic baseline by more than two orders of magnitude.The comparison uses attacker-optimized initial set sizes for huge pages, 4KB pages, and the limit case.

D. Performance in Practice

The algorithms provide substantial practical speedups for computing minimal eviction sets, including under TLB noise and adaptive replacement policies, though replacement behavior can affect effectiveness.

  • D. Performance in Practice: A 4000-address initial set is used for performance comparisons because it is likely to be an eviction set, avoiding repeated resampling.The comparison follows the assumption that attackers prefer a sufficiently large initial set.
  • D. Performance in Practice: For huge pages, group-testing reduction takes 0.003 seconds versus 0.014 seconds for the baseline, a 5× improvement.The initial set size is N = 192, chosen to yield an eviction probability close to 1.
  • D. Performance in Practice: For 4KB pages, group-testing reduction takes 0.245 seconds versus 5.060 seconds for the baseline, a 20× improvement.Finding all minimal eviction sets in the buffer takes 9.339 seconds with group testing versus more than 100 seconds for the baseline.
  • D. Performance in Practice: 5-20× faster execution in practical scenarios demonstrates substantial speedups over existing reduction algorithms.The reported improvements cover huge-page and 4KB-page settings.
  • D. Performance in Practice: Adaptive replacement policies can introduce false positives and false negatives, while partially congruent inputs improve reduction robustness.These effects complicate practical reliability even when execution time remains favorable.

A. Adaptive Replacement Policies

The study finds that adaptive replacement behavior varies across Intel microarchitectures and cache sets, strongly affecting reduction reliability and execution time.

  • A. Adaptive Replacement Policies: The experiments analyze arbitrary and partially congruent eviction sets per set index using huge pages to control target bits and reduce TLB effects.The study compares these conditions to isolate interference across cache sets.
  • A. Adaptive Replacement Policies: On Skylake, 16 of 1024 sets per slice have reduction rates consistently above 95%, while follower sets show lower reduction despite high eviction rates.The follower-set behavior indicates both false positives and false negatives in the eviction test.
  • A. Adaptive Replacement Policies: Haswell shows no cache sets with consistently high reduction rates, suggesting dynamic leader selection rather than Skylake-like static leaders.The comparison concerns reductions on arbitrary eviction sets.
  • A. Adaptive Replacement Policies: For partially congruent eviction sets, eviction and reduction rates approach the predicted optimum on both Haswell and Skylake.Reduction robustness increases with the proportion of partially congruent addresses, indicating interference from neighboring cache sets in arbitrary sets.
  • A. Adaptive Replacement Policies: Lower reduction rates produce longer execution times because errors trigger additional backtracking steps.Figure 12 links the lowest execution times, below 0.12s, to sets with higher reduction rates.
  • A. Adaptive Replacement Policies: A detailed algorithmic analysis of adaptive replacement policies remains outside the paper’s scope, motivating future work on policy control and noisy group testing.The paper suggests exploiting leader sets and using noisy-testing techniques to handle uncertainty.

VII. RELATED WORK

Prior work uses eviction sets across cache, DRAM, deduplication, and speculative-execution attacks, but largely lacks a systematic algorithmic treatment of finding minimal sets.

  • VII. RELATED WORK: Small eviction sets are a fundamental primitive for cache attacks, Rowhammer, memory-deduplication attacks, Meltdown, and Spectre.They support manipulating cache state and probing whether a victim modified it.
  • VII. RELATED WORK: Prior methods include static, dynamic, and hybrid constructions using physical-address information, huge pages, page-aligned buffers, or timing measurements.These approaches target settings ranging from bare-metal systems to sandboxed environments.
  • VII. RELATED WORK: Existing heuristics can work well in practice but may have quadratic asymptotic cost, while modern replacement policies make eviction less reliable.The paper’s linear-time algorithms address the stated complexity gap, while replacement-policy effects remain relevant.
  • VII. RELATED WORK: The paper claims the first treatment of adversaries with less than 12 controlled physical-address bits and introduces techniques supporting purely dynamic approaches.This distinguishes the work from methods relying on large pages or known physical mappings.
  • VII. RELATED WORK: Randomized set-index designs aim to make cache attacks and small-eviction-set discovery harder, but their security analyses consider quadratic attackers.The paper notes that linear-time algorithms may affect how those designs should be evaluated.
  • VII. RELATED WORK: Earlier approaches commonly combine a large initial eviction set with successive reduction, but lack in-depth analysis of complexity, performance, correctness, and scope.This gap motivates treating minimal-eviction-set discovery as an algorithmic problem.

APPENDIX

This appendix discusses huge pages and analyzes a recurrence for reducing eviction sets, including its termination condition and approximation assumptions.

  • A. Huge Pages: Huge pages use contiguous 2MB or 1GB physical chunks instead of regular 4KB pages, reducing page walks but potentially increasing memory fragmentation.The appendix distinguishes explicit huge-page requests from transparent huge pages managed by the kernel.
  • A. Huge Pages: Browser allocations generally lack huge-page backing unless transparent huge pages are configured as always, limiting their practical use for finding eviction sets.The passage identifies default browser systems as the relevant boundary.
  • B. Analysis: The reduction analysis models runtime with a recurrence and rewrites it as a geometric progression until the remaining size reaches the termination condition.The derivation uses a logarithm to determine the exponent of the last iteration.
  • B. Analysis: The analysis ignores the ceiling operator because its implementation error is bounded by a small factor and treated as negligible.This is an explicit approximation assumption in the runtime analysis.

C. Pidgeonhole Principle

This section applies a pigeonhole argument to show that partitioning a set into a+1 blocks preserves at least a elements associated with P after removing one suitable block.

  • C. Pidgeonhole Principle: If |S ∩ P| ≥ a, partitioning S into a+1 blocks guarantees a block whose removal leaves at least a elements of S ∩ P.The proposition establishes the existence of the removable block used by the reduction argument.
  • C. Pidgeonhole Principle: When |S ∩ P| = a, one partition block must be disjoint from P, so removing it preserves all a relevant elements.This is the proof's boundary case.
  • C. Pidgeonhole Principle: The proof derives a contradiction by assuming every block removal leaves fewer than a elements of S ∩ P, then summing the resulting inequalities.The notation p_i = |T_i ∩ P| and x = |S ∩ P| supports the reformulation.
  • TLB Background: Modern Intel CPUs use separate instruction and data TLBs, second-level TLBs, and TLBs associated with different page-table levels.The section points to Haswell and Skylake parameter summaries in Table II.
Loading 1810.01497v2…