On Formally Bounding Information Leakage by Statistical Estimation
On Formally Bounding Information Leakage by Statistical Estimation
复制标题
通过统计估计对信息泄漏进行正式界定
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Michela Paolini
中科院分区：
文献类型：
--
作者：
Michele Boreale;Michela Paolini
我们研究的问题，给出正式的界限上的信息泄漏的确定性程序，当只有一个黑盒访问系统提供的，而鲜为人知的输入生成机制。在引入统计设置和定义信息泄漏估计的正式概念后，我们证明了，在没有关于输出分布的重要先验信息的情况下，没有这样的估计实际上可以存在，比输入域的穷举更好。此外，我们表明，困难的部分基本上是获得严格的上界。这促使我们考虑一个宽松的情况下，分析师被赋予一些控制输入分布：一个估计量的介绍，以高概率，给出了下限，而不考虑潜在的分布，和严格的上限，如果输入分布引起一个“接近均匀”的输出分布。然后，我们定义了两种方法，一个基于大都会蒙特卡罗和一个基于接受，可理想地采用这样的输入分布的样本，并讨论了一个实用的方法，基于它们。最后，我们通过一些实验来演示所提出的方法，包括对排序算法中缓存侧通道的分析。
We study the problem of giving formal bounds on the information leakage of deterministic programs, when only a black-box access to the system is provided, and little is known about the input generation mechanism. After introducing a statistical set-up and defining a formal notion of information leakage estimator, we prove that, in the absence of significant a priori information about the output distribution, no such estimator can in fact exist that does significantly better than exhaustive enumeration of the input domain. Moreover, we show that the difficult part is essentially obtaining tight upper bounds. This motivates us to consider a relaxed scenario, where the analyst is given some control over the input distribution: an estimator is introduced that, with high probability, gives lower bounds irrespective of the underlying distribution, and tight upper bounds if the input distribution induces a “close to uniform” output distribution. We then define two methods, one based on Metropolis Monte Carlo and one based on Accept-Reject, that can ideally be employed to sample from one such input distribution, and discuss a practical methodology based on them. We finally demonstrate the proposed methodology with a few experiments, including an analysis of cache side-channels in sorting algorithms.
DOI：
10.1109/csf.2013.20
发表时间：
2013
期刊：
--
影响因子：
--
作者：
Chothia T
通讯作者：
Chothia T