F-BLEAU: Fast Black-Box Leakage Estimation

Giovanni Cherubin, Konstantinos Chatzikokolakis, Catuscia Palamidessi

TL;DR

F-BLEAU is a novel tool that uses machine learning—specifically Nearest Neighbor rules—to estimate information leakage in black-box systems. By exploiting the geometric patterns in a system's outputs, it achieves much faster convergence than traditional statistical methods and can handle continuous output spaces (like precise timing or network traffic) where previous tools failed.

What Problem Does This Paper Address?

In computer security, we often need to quantify "information leakage": how much a secret input (like a cryptographic key or a user's location) can be guessed by observing a system's output (like execution time or obfuscated coordinates).

The gold standard for this is the Bayes risk, which represents the minimum error an ideal attacker would make. However, calculating this for "black-box" systems—where we don't know the internal logic—is hard. The traditional "frequentist" approach involves running the system many times and counting how often specific input-output pairs occur. This works for small systems but fails miserably when the output space is large or continuous, as the number of required samples explodes.

Methods

The authors propose a shift from pure statistics to Machine Learning (ML). They identify a fundamental equivalence: the error rate of a "universally consistent" learning rule is, by definition, an estimate of the Bayes risk.

The paper focuses on Nearest Neighbor (NN) and $k_n$-Nearest Neighbor ($k_n$-NN) rules. Unlike frequentist methods that treat every output as a unique category, NN rules exploit a metric (a notion of distance). If two outputs are "close" to each other, they are likely produced by the same secret. This allows the estimator to "fill in the gaps" for outputs it hasn't seen before, drastically reducing the amount of data needed.

The tool, F-BLEAU (Fast Black-box Leakage Estimation AUtomated), implements these ML rules alongside the traditional frequentist approach. Because the "No Free Lunch" theorem states that no single algorithm is best for every possible dataset, F-BLEAU evaluates multiple estimators and selects the one that converges the fastest for a given system.

Datasets

The authors evaluated F-BLEAU using three types of data:

  1. Synthetic Systems: Controlled environments using Geometric noise (common in differential privacy), Multimodal distributions, and "Spiky" contrived examples designed to make ML rules fail.
  2. Location Privacy (Gowalla): A real-world dataset of user check-ins in San Francisco. They tested how well F-BLEAU could estimate the leakage of three privacy-preserving mechanisms: Planar Geometric, Planar Laplacian (which is continuous), and Blahut-Arimoto.
  3. Side-Channel Analysis: Timing data from e-Passport RFID chips, where an attacker tries to determine if a passport belongs to a specific person based on response times.

Key Insights and Ideas

  • ML as an Estimator: The "aha moment" is realizing that any universally consistent classifier is essentially a leakage estimator. This opens the door to using decades of ML research for security quantification.
  • The Power of Metrics: Frequentist methods are "blind" to the similarity between outputs. By using a metric (like Euclidean distance), NN methods can generalize from a few samples, which is crucial for high-dimensional or continuous data.
  • Handling the Continuous: Traditional tools like leakiEst struggle with continuous outputs (like time) because they require "binning" data into discrete buckets. $k_n$-NN handles continuous data natively.
  • The "Spiky" Exception: The authors honestly demonstrate that if a system is maliciously designed so that "nearby" outputs correspond to completely different secrets, NN methods will perform worse than frequentist ones—though they still eventually converge.

Key Results

  • Speedup: In synthetic geometric systems with 10,000 possible outputs, NN converged with just 333 examples, while the frequentist approach required over 35,000.
  • Real-World Effectiveness: On the Gowalla dataset, F-BLEAU successfully estimated leakage for the Planar Laplacian mechanism. Traditional frequentist tools were marked as "N/A" because they cannot formally handle continuous domains.
  • Sensitivity: In the e-Passport timing study, F-BLEAU detected significant leakage (indicating a successful attack with ~54% accuracy) in cases where the state-of-the-art tool leakiEst reported "no evidence of leakage" due to the small sample size (~1k examples).

Limitations and Future Work

  • Confidence Intervals: Currently, F-BLEAU provides a point estimate but does not provide formal confidence intervals (e.g., "we are 95% sure the leakage is between X and Y"). The authors note this is a difficult theoretical challenge for continuous systems.
  • Continuous Secrets: The paper focuses on discrete secret spaces (classification). Future work could extend this to continuous secret spaces (regression), such as estimating the leakage of a precise physical coordinate.
  • Advanced ML Models: While this paper focuses on Nearest Neighbors due to their theoretical guarantees, the framework could potentially incorporate Support Vector Machines (SVMs) or Neural Networks.

Summary updated

Abstract

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.
BibTeX
@inproceedings{cherubin2019f,
  author = {Giovanni Cherubin and Konstantinos Chatzikokolakis and Catuscia Palamidessi},
  title = {{F-BLEAU: Fast Black-Box Leakage Estimation}},
  booktitle = {IEEE Symposium on Security and Privacy},
  year = {2019},
  doi = {10.1109/sp.2019.00073},
}

Loading related content...

Figure