MIRAGE: Mitigating Conflict-Based Cache Attacks with a Practical Fully-Associative Design

Shared caches in modern processors are vulnerable to conflict-based attacks, whereby an attacker monitors the access pattern of a victim by engineering cache-set conflicts. Recent mitigations propose a randomized mapping of addresses to cache locations to obfuscate addresses that can conflict with a target address. Unfortunately, such designs continue to select eviction candidates from a small subset of the resident cache lines, which makes such designs vulnerable to algorithms that can quickly identify the conflicting addresses. This paper presents Mirage, a practical design for a fully associative cache, wherein eviction candidates are selected randomly from among all the lines resident in the cache, to be immune to set-conflicts. A key challenge in naively adopting such designs for large shared caches (containing tens of thousands of lines) is the complexity of cache-lookup, as that can require searching through all the lines resident in the cache in such designs. Mirage practically enables a fully-associative design, while maintaining the access latency similar to a traditional set-associative cache using: (1) Pointer-based indirection from the tag-store to the data-store, which allows a newly installed address to evict data of any resident line, (2) Skewed-associative tag-store with extra invalid tags, wherein incoming addresses can be installed without set-conflicts, and (3) Load-aware placement that maximizes the availability of sets with invalid tags, to eliminate set-conflicts. Our analysis shows Mirage provides the global-eviction property of a fully-associative cache throughout the system lifetime (violations of full-associativity, i.e set-conflicts, occur less than once in 10^4 to 10^17 years), offering a principled defense against set-conflict based attacks. Mirage incurs negligible slowdown (0.3%) and 12-15% extra storage compared to the recently proposed Scatter-Cache.