  Shared processor caches are vulnerable to conflict-based side-channel
attacks, where an attacker can monitor access patterns of a victim by evicting
victim cache lines using cache-set conflicts. Recent mitigations propose
randomized mapping of addresses to cache lines to obfuscate the locations of
set-conflicts. However, these are vulnerable to new attacks that discover
conflicting sets of addresses despite such mitigations, because these designs
select eviction-candidates from a small set of conflicting lines.
  This paper presents Mirage, a practical design for a fully associative cache,
wherein eviction candidates are selected randomly from all lines resident in
the cache, to be immune to set-conflicts. A key challenge for enabling such
designs in large shared caches (containing tens of thousands of cache lines) is
the complexity of cache-lookup, as a naive design can require searching through
all the resident lines. Mirage achieves full-associativity while retaining
practical set-associative lookups by decoupling placement and replacement,
using pointer-based indirection from tag-store to data-store to allow a newly
installed address to globally evict the data of any random resident line. To
eliminate set-conflicts, Mirage provisions extra invalid tags in a
skewed-associative tag-store design where lines can be installed without
set-conflict, along with a load-aware skew-selection policy that guarantees the
availability of sets with invalid tags. Our analysis shows Mirage provides the
global eviction property of a fully-associative cache throughout system
lifetime (violations of full-associativity, i.e. set-conflicts, occur less than
once in 10^4 to 10^17 years), thus offering a principled defense against any
eviction-set discovery and any potential conflict based attacks. Mirage incurs
limited slowdown (2%) and 17-20% extra storage compared to a non-secure cache.
