Dynamic Eviction Set Algorithms and Their Applicability to Cache Characterisation

Eviction sets are groups of memory addresses that map to the same cache set. They can be used to perform efficient information-leaking attacks against the cache memory, so-called cache side channel attacks. In this project, two different algorithms that find such sets are implemented and compared. The second of the algorithms improves on the first by using a concept called group testing. It is also evaluated if these algorithms can be used to analyse or reverse engineer the cache characteristics, which is a new area of application for this type of algorithms. The results show that the optimised algorithm performs significantly better than the previous state-of-the-art algorithm. This means that countermeasures developed against this type of attacks need to be designed with the possibility of faster attacks in mind. The results also shows, as a proof-of-concept, that it is possible to use these algorithms to create a tool for cache analysis