Modern computer architectures rely on caches to reduce the latency gapbetween the CPU and main memory. While indispensable for performance, cachespose a serious threat to security because they leak information about memoryaccess patterns of programs via execution time. In this paper, we present a novel approach for reasoning about the securityof cache algorithms with respect to timing leaks. The basis of our approach isthe notion of leak competitiveness, which compares the leakage of two cachealgorithms on every possible program. Based on this notion, we prove thefollowing two results: First, we show that leak competitiveness is symmetric in the cachealgorithms. This implies that no cache algorithm dominates another in terms ofleakage via a program's total execution time. This is in contrast toperformance, where it is known that such dominance relationships exist. Second, when restricted to caches with finite control, theleak-competitiveness relationship between two cache algorithms is eitherasymptotically linear or constant. No other shapes are possible.
展开▼
