# Noise-Free Security Assessment of Eviction Set Construction Algorithms with Randomized Caches
## 7 Random Eviction Last-Level Cache  
### Overview  
As described in Section 6, the Prime-Prune-Probe could bypass randomized lower-level caches by observing the last-level cache eviction patterns. This algorithm used a _Prune  
Figure 11: (**a**) The success rate of the Prime–Prune–Probe algorithm with different candidate set sizes. (**b**) The number of congruent addresses in the reduced eviction set when using the Prime–Prune–Probe algorithm with a randomized L1 cache.  
Figure 10: (**a**) The success rate of the group testing algorithm with different candidate set sizes. (**b**) The number of congruent addresses in the reduced eviction set when using the group testing algorithm with a randomized L1 cache.  
filter to remove all addresses that were subject to self-eviction. At the end of the Prune filter, the candidate set should not have contained any addresses that collided with each other. In this way, a purely deterministic decision could be made about which cache set was accessed in the Probe phase. This algorithm could then determine eviction sets in the shortest possible time by bypassing randomization, even when the mapping changed more frequently. Thus, it seemed natural to add random evictions in the last-level cache to disturb the Prune filter's operation. This should have made it more difficult (ideally impossible) for an attacker to construct an eviction set.  
The concept of adding non-deterministic eviction is well known [59; 60]. The idea is to evict one or more lines randomly from the cache at a given interval of time. We can use the Prime+Probe attack as an example to understand the intuition behind it. During the Probe step, the attacker accesses the eviction set and measures the memory access latency. In this way, the attacker can determine which cache sets the victim has accessed. However, when the cache eviction is not deterministic, the attacker cannot know whether the cache line was evicted randomly by the random eviction policy or by the victim's accesses. This can make the attacker's observations noisy and thus, mitigate against conflict-based cache attacks.  
We added a random eviction mechanism to the last-level cache model of our simulation framework. It supported two security parameters: the eviction frequency \(f\) and the number of evicted lines \(n\). Every \(f\) memory accesses, \(n\) cache lines were randomly generated. For example, for a cache with the random eviction strategy parameters \((f,n)=(5,1)\), a random cache line would be evicted every five memory accesses. Intuitively, the lower the eviction frequency, the more robust the cache. Depending on the two values of \(f\) and \(n\), the performance counters were used to count the number of memory accesses. Every \(f\) accesses, a pseudo-random number generator generated a random cache set and a cache way for each line among the \(n\). After the requests were sent to the cache, when the line was found in the cache and modified, it was written back to the upper-level caches or to the main memory to ensure memory coherence. Otherwise, it was sufficient to invalidate the cache line by setting the validity bit to 0.