Date Added: Feb 2012
The latency gap between caches and main memory has been successfully exploited for recovering sensitive input to programs, such as cryptographic keys from implementation of AES and RSA. So far, there are no practical general-purpose countermeasures against this threat. In this paper, the authors propose a novel method for automatically deriving upper bounds on the amount of information about the input that an adversary can extract from a program by observing the CPU's cache behavior. At the heart of their approach is a novel technique for efficient counting of concretizations of abstract cache states that enables one to connect state-of-the-art techniques for static cache analysis and quantitative information-flow.