Feasibility Analysis and Performance Optimization of the Conflict Test Algorithms for Searching Eviction Sets

Cache side-channel attacks have been widely utilized as an intermediate step in some comprehensive attacks. Eviction sets, especially the minimal eviction sets, are essential components of the conflict-based cache side-channel attacks. It is important to develop efficient search algorithms that incur the lowest latency with the highest success rate. Several fast search algorithms have been proposed in recent years, among which conflict test (CT) achieves the highest success rate with the lowest latency. In this paper, we have conducted the first systematic feasibility analysis of the CT algorithm. Besides failing on the commonly known cache architectures where the last-level cache (LLC) is exclusive or non-inclusive, CT is also found and verified failing on two inclusive LLC architectures if it is running in single-core mode. We have further explored three optimizations for improving the speed performance of the CT algorithm, two of which are newly proposed in this paper.