F-BLEAU: Fast Black-Box Leakage Estimation
F-BLEAU: Fast Black-Box Leakage Estimation
复制标题
F-BLEAU：快速黑盒泄漏估计
DOI：
10.1109/sp.2019.00073
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
C. Palamidessi
中科院分区：
文献类型：
--
作者：
Giovanni Cherubin;K. Chatzikokolakis;C. Palamidessi
我们考虑的问题是衡量一个系统在多大程度上揭示了其秘密输入。我们在黑匣子环境中工作：我们假设事先不知道系统的内部结构，我们运行系统以选择秘密，并从各自的输出测量其泄漏。我们的目标是估计贝叶斯风险，从中可以得出一些最流行的泄漏度量(例如，最小熵泄漏)。估计这些泄漏度量的最先进方法是频率主义范式，它通过观察系统输入和输出的频率来近似系统的内部。不幸的是，这不适用于具有大输出空间的系统，因为它需要过多的输入-输出示例。因此，它也不能应用于具有连续输出的系统(例如，时间侧信道、网络流量)。在本文中，我们利用机器学习(ML)和黑盒泄漏估计之间的相似之处来证明可以使用一类ML方法来估计系统的贝叶斯风险：普遍一致的学习规则；这些规则可以利用输入输出示例中的模式来改善估计的收敛，同时保持形式上的最优性保证。我们关注其中的一组规则，最近邻规则；我们证明了当附近的输出往往由相同的秘密产生时，它们显著减少了精确估计所需的黑盒查询的数量；此外，其中一些规则可以处理具有连续输出的系统。我们说明了这些技术在合成数据和真实数据上的适用性，并将它们与基于频率法的最先进的工具Leakiest进行了比较。
We consider the problem of measuring how much a system reveals about its secret inputs. We work in the black-box setting: we assume no prior knowledge of the system's internals, and we run the system for choices of secrets and measure its leakage from the respective outputs. Our goal is to estimate the Bayes risk, from which one can derive some of the most popular leakage measures (e.g., min-entropy leakage). The state-of-the-art method for estimating these leakage measures is the frequentist paradigm, which approximates the system's internals by looking at the frequencies of its inputs and outputs. Unfortunately, this does not scale for systems with large output spaces, where it would require too many input-output examples. Consequently, it also cannot be applied to systems with continuous outputs (e.g., time side channels, network traffic). In this paper, we exploit an analogy between Machine Learning (ML) and black-box leakage estimation to show that the Bayes risk of a system can be estimated by using a class of ML methods: the universally consistent learning rules; these rules can exploit patterns in the input-output examples to improve the estimates' convergence, while retaining formal optimality guarantees. We focus on a set of them, the nearest neighbor rules; we show that they significantly reduce the number of black-box queries required for a precise estimation whenever nearby outputs tend to be produced by the same secret; furthermore, some of them can tackle systems with continuous outputs. We illustrate the applicability of these techniques on both synthetic and real-world data, and we compare them with the state-of-the-art tool, leakiEst, which is based on the frequentist approach.
DOI：
10.1109/csf.2013.20
发表时间：
2013
期刊：
--
影响因子：
--
作者：
Chothia T
通讯作者：
Chothia T
DOI：
10.1007/978-3-642-28756-5_47
发表时间：
2012
期刊：
--
影响因子：
--
作者：
Basler G
通讯作者：
Basler G