What's the Over/Under? Probabilistic Bounds on Information Leakage

2018/02/22 by Ian Sweet, Jose Manuel Calderon Trilla, Sweet, Ian +7
Computer Science · #FOS: Computer and information sciences #Programming Languages (cs.PL) #cs.PL

paper · pdf · doi:10.48550/arxiv.1802.08234

arxiv created 2018/02/22 · arxiv updated 2018/02/23

Abstract

Quantitative information flow (QIF) is concerned with measuring how much of a secret is leaked to an adversary who observes the result of a computation that uses it. Prior work has shown that QIF techniques based on abstract interpretation with probabilistic polyhedra can be used to analyze the worst-case leakage of a query, on-line, to determine whether that query can be safely answered. While this approach can provide precise estimates, it does not scale well. This paper shows how to solve the scalability problem by augmenting the baseline technique with sampling and symbolic execution. We prove that our approach never underestimates a query's leakage (it is sound), and detailed experimental results show that we can match the precision of the baseline technique but with orders of magnitude better performance.

Related

• Source-level reasoning for quantitative information flow
• An Algebraic Approach for Reasoning About Information Flow
• A new measure for dynamic leakage based on quantitative information flow
• On the Compositionality of Dynamic Leakage and Its Application to the Quantification Problem
• Bits Leaked per Query: Information-Theoretic Bounds on Adversarial Attacks against LLMs