Title: Security Analysis of Cache Replacement Policies,
Abstract: Modern computer architectures share physical resources between different
programs in order to increase area-, energy-, and cost-efficiency.
Unfortunately, sharing often gives rise to side channels that can be exploited
for extracting or transmitting sensitive information. We currently lack
techniques for systematic reasoning about this interplay between security and
efficiency. In particular, there is no established way for quantifying security
properties of shared caches.
In this paper, we propose a novel model that enables us to characterize
important security properties of caches. Our model encompasses two aspects: (1)
The amount of information that can be absorbed by a cache, and (2) the amount
of information that can effectively be extracted from the cache by an
adversary. We use our model to compute both quantities for common cache
replacement policies (FIFO, LRU, and PLRU) and to compare their isolation
properties. We further show how our model for information extraction leads to
an algorithm that can be used to improve the bounds delivered by the CacheAudit
static analyzer.