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


Wei Song, Institute of Information Engineering, CAS; Peng Liu, Pennsylvania State University


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(w2n) 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.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

@inproceedings {242066,
author = {Wei Song and Peng Liu},
title = {Dynamically Finding Minimal Eviction Sets Can Be Quicker Than You Think for {Side-Channel} Attacks against the {LLC} },
booktitle = {22nd International Symposium on Research in Attacks, Intrusions and Defenses (RAID 2019)},
year = {2019},
isbn = {978-1-939133-07-6},
address = {Chaoyang District, Beijing},
pages = {427--442},
url = {https://www.usenix.org/conference/raid2019/presentation/song},
publisher = {USENIX Association},
month = sep