Theory and Practice of Finding Eviction Sets

Explore the theory and practice of finding eviction sets in this IEEE Symposium on Security & Privacy conference talk. Delve into the systematic study of algorithms for identifying small eviction sets, a crucial primitive for various micro-architectural attacks. Learn about the formalization of the problem and the analysis of the probability that random virtual addresses form an eviction set. Discover novel algorithms based on threshold group testing that improve upon the current state-of-the-art by reducing random eviction sets to their minimal core in linear time. Examine the rigorous empirical evaluation that identifies and isolates factors affecting algorithm reliability in practice, such as adaptive cache replacement strategies and TLB thrashing. Gain insights into how these algorithms enable faster discovery of small eviction sets, even under previously impractical conditions. Cover topics including attacks, problem definition, contributions, baseline algorithms, threshold group testing, performance evaluation, robustness assessment, and conclusions.