One of the key researches in the domain of quantitative information flow (QIF) is to effectively estimate information leaks in a system in order to prevent adversarial attacks. Most existing approaches are based on the white-box approach. However, this approach is often impractical due to the size or complexity of its internals, or the presence of unknown factors. This and other challenges forced a shift in focus to investigate methods for measuring a system’s leakage in a black-box manner.

Thus far, the only approach for the black-box estimation has been founded on the frequentist paradigm, which cannot be scaled to real-world problems and be applied to systems with continuous outputs (e.g., time side channels, network traffic). To address that problem, EPFL’s Giovanni Cherubin and coauthors have proposed to leverage 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.

In their paper, which was presented at the IEEE Symposium on Security and Privacy (2019), the researchers took cognizance of a fundamental equivalence between ML and black-box leakage estimation to demonstrate that any ML rule from a certain class (the universally consistent rules) can be used to estimate with arbitrary precision the leakage of a system. More specifically, their work is based on the nearest neighbor principle, which significantly reduces the number of black-box queries required for a precise estimation and exploits a metric on the output space to achieve a considerably faster convergence than frequentist approaches. The research adds a completely new class of estimators that can be used in practical applications.

Based on their findings, the researchers have developed a tool called F-BLEAU (Fast Black-box Leakage Estimation AUtomated). The tool computes nearest neighbor and frequentist estimates, and selects the one converging faster. F-BLEAU considers a generic system as a black-box, taking secret inputs and returning outputs accordingly, and it measures how much the outputs “leak” about the inputs.

F-BLEAU is available as an open source software at https://github.com/gchers/fbleau

Giovanni Cherubin is Postdoctoral Fellow in Machine Learning and Security at EPFL. He is the recipient of an EcoCloud post-doctoral fellowship since October 2018, and his work on F-BLEAU was supported by that fellowship.


G. Cherubin, K. Chatzikokolakis and C. Palamidessi, “F-BLEAU: Fast Black-Box Leakage Estimation,” 2019 IEEE Symposium on Security and Privacy (SP), San Francisco, CA, USA, 2019, pp. 835-852, doi: 10.1109/SP.2019.00073.

Full text pdf at https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=8835250