一句话：提出 leak competitiveness 比较缓存算法时序泄漏，证明算法间无泄漏支配关系，有限控制下关系仅线性或常数。
现代处理器依赖缓存缩小 CPU 与主存延迟差距，但缓存会通过执行时间泄漏程序访存模式，带来安全风险。本文研究如何比较不同缓存算法在时序泄漏方面的安全性，提出 leak competitiveness 概念：它在所有可能程序上比较两个缓存算法所泄漏的信息。基于该概念，作者证明两个结果：leak competitiveness 对缓存算法是对称的，因此不存在某个缓存算法在程序总执行时间泄漏上支配另一个算法，这与性能上已知的支配关系形成对比；其次，在有限控制的缓存上，两算法间的 leak competitiveness 关系只能渐近线性或常数，不存在其他形状。该工作为缓存算法时序泄漏分析提供了统一的理论框架。
Modern computer architectures rely on caches to reduce the latency gap between the CPU and main memory. While indispensable for performance, caches pose a serious threat to security because they leak information about memory access patterns of programs via execution time. In this paper, we present a novel approach for reasoning about the security of cache algorithms with respect to timing leaks. The basis of our approach is the notion of leak competitiveness, which compares the leakage of two cache algorithms on every possible program. Based on this notion, we prove the following two results: First, we show that leak competitiveness is symmetric in the cache algorithms. This implies that no cache algorithm dominates another in terms of leakage via a program's total execution time. This is in contrast to performance, where it is known that such dominance relationships exist. Second, when restricted to caches with finite control, the leak-competitiveness relationship between two cache algorithms is either asymptotically linear or constant. No other shapes are possible.
@article{paperbot821,
title = {On the Incomparability of Cache Algorithms in Terms of Timing Leakage},
author = {Pablo Cañones and Boris Köpf and Jan Reineke},
journal = {Logical Methods in Computer Science},
volume = {Volume 15, Issue 1},
year = {2019},
doi = {10.23638/lmcs-15(1:21)2019}
}