We consider the problem of measuring how much a system reveals about its
secret inputs. We work under 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, additive, and multiplicative 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.

本文研究了在黑盒条件下测量系统对其秘密输入的泄露量问题，提出了使用 ML 方法来估计系统的贝叶斯风险，并展示了最近邻规则的应用，以降低黑盒查询的数量，并处理连续输出的系统。