Alexander Spangher, Zihan Xue, Te-Lin Wu, Mark Hansen, Jonathan May. Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers). 2024.

Conflict-based cache side-channel attacks against the last-level cache (LLC) is a widely exploited method for information leaking. Cache randomization has recently been accepted as a promising defense. Most of recent designs randomize skewed caches rather than classic set-associative caches; however, skewed caches incur substantial performance overhead both in area and runtime. We cautiously argue that randomized set-associative caches can be sufficiently strengthened and possess a better chance to be adopted in the near future. For the first time, a dynamically randomized set-associative cache has been implemented in the LLC of a Linux capable multicore processor. A single-cycle hash logic is designed for randomizing the cache set indices. A multi-step relocation scheme is used to reduce the cost in remapping the cache layout. The randomized cache layout is remapped periodically for limiting the time window available to attackers. An attack detector is implemented to catch attacks in action and consequently trigger extra remaps. The evaluation results show that the randomized LLC has been sufficiently strengthened to thwart all existing fast algorithms for searching eviction sets with only marginal runtime overhead, and small area and power overhead.

Eviction sets are essential components of the conflict-based cache side-channel attacks. However, it is not an easy task to construct eviction sets on modern Intel processors. As a promising defense against conflict-based cache side-channels, dynamic cache randomization makes the construction of eviction sets even more difficult by periodically randomizing the mapping between addresses and cache set indices. It forces attackers to develop fast search algorithms to find an eviction set at runtime with the lowest latency. Several fast search algorithms have been proposed in recent years. By using these algorithms, attackers regain the capability of launching useful attacks on dynamically randomized caches. Consequently, a detector was recently introduced to catch the fast search algorithms in action according to the uneven distribution of cache evictions. All existing fast search algorithms fail to work.

Cache randomization has recently been revived as a promising defense against conflict-based cache side-channel attacks. As two of the latest implementations, CEASER-S and ScatterCache both claim to thwart conflict-based cache side-channel attacks using randomized skewed caches. Unfortunately, our experiments show that an attacker can easily find a usable eviction set within the chosen remap period of CEASER-S and increasing the number of partitions without dynamic remapping, such as ScatterCache, cannot eliminate the threat. By quantitatively analyzing the access patterns left by various attacks in the LLC, we have newly discovered several problems with the hypotheses and implementations of randomized caches, which are also overlooked by the research on conflict-based cache side-channel attacks.However, cache randomization is not a false hope and it is an effective defense that should be widely adopted in future processors. The newly discovered problems are corresponding to flaws associated with the existing implementation of cache randomization and are fixable. Several new defense ideas are proposed in this paper. Our experiments show that all the newly discovered problems are fixed within the current performance budget. We also argue that randomized set-associative caches can be sufficiently strengthened and possess a better chance to be actually adopted in commercial processors than their skewed counterparts because they introduce less overhaul to the existing cache structure.