Dynamically Finding Minimal Eviction Sets Can Be Quicker Than You Think for Side-Channel Attacks against the LLC

Minimal eviction sets are essential for conflict-based cache side-channel attacks targeting the last-level cache. In the most restricted case where attacker have no control over the mapping from virtual addresses to cache sets, finding rather than computing minimal eviction sets become the only solution. It was believed that finding minimal eviction sets is a long process until a recent discovery finding that they can be found in linear time.

This paper focuses on further improving the speed of finding minimal eviction sets. A systematic analysis of the existing algorithms has been done using an ideal cache model. Our analysis shows: The latency upper bound of finding minimal eviction sets can be further reduced from O(w²n) to O(wn); the average latency is seriously less than the upper bound; the latency assumption used by recent defences is significantly overestimated. Practical experiments are produced on three modern processors. Using a handful of new techniques proposed in this paper, including using concurrent multithread execution to circumvent the thrashing resistant cache replacement policies, we demonstrates that minimal eviction sets can be found within a fraction of a second on all processors, including a latest Coffee Lake one. It is also the first time to show that it is possible to find minimal eviction sets with totally random addresses without fixing the page offset bits.