Quantifying Information Leakage in Finite Order Deterministic Programs

Ji Zhu, Mudhakar Srivatsa

TL;DR

This paper tackles the problem of comparing information leakage from programs using information-theoretic metrics. It highlights how existing metrics can lead to conflicting and counter-intuitive results, proposing a novel, conflict-free approach based on the asymptotic behavior of leakage measures to provide a more robust comparison.

What Problem Does This Paper Address?

In software security, understanding how much sensitive information a program might reveal through its public output is crucial. This is where "information flow analysis" comes in. Researchers have turned to information theory, using metrics like Shannon entropy or min-entropy, to quantify this "information leakage." However, the authors point out a significant issue: these metrics, when applied to compare two different programs, can give contradictory results. For instance, one metric might suggest Program A leaks more than Program B, while another metric suggests the opposite. This inconsistency makes it difficult to reliably assess which program is more secure. The paper aims to resolve these conflicts and provide a consistent way to compare information leakage from deterministic programs.

Methods

The core of the paper's contribution lies in proposing a new method for comparing information leakage. Instead of relying on a single snapshot of leakage, they propose looking at the asymptotic behavior of leakage as the size of the secret input grows. Specifically, they analyze the limit of leakage measures as the input space size approaches infinity.

They formalize this by:

  • Defining a Program Model: They introduce a formal model for Single-Input Single-Output (SISO) deterministic programs, distinguishing between Finite Order Programs (FOPs) and Infinite Order Programs (IOPs).
  • Leveraging Renyi Entropy: They use Renyi entropy as a general framework, as it encompasses various existing entropy measures (Shannon, min-entropy, etc.) by varying a parameter $\alpha$. Information leakage is then defined as the mutual information between the secret input and the program output, calculated using Renyi entropy.
  • Proposing a Conflict-Free Metric: The key innovation is the proposed comparison metric. For two FOPs, C1 and C2, they compare the ratio of their leakage measures (using Renyi entropy with parameter $\alpha$) as the input size $|A|$ goes to infinity. If this ratio is consistently 0, $\infty$, or a finite non-zero constant across different $\alpha$ values, it indicates a clear relationship in leakage. They formalize this using limits and introduce algorithms (Algorithm 4.4 and 4.5) to determine if one program has higher leakage, lower leakage, or if they are on the same leakage level.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and uses example programs for illustration rather than real-world datasets.

Key Insights and Ideas

  • Conflicting Metrics are Common: The paper convincingly demonstrates with examples (PROG P1 vs. P2, PROG P3 vs. P4) that different information-theoretic metrics (based on different Renyi entropy parameters $\alpha$) can yield contradictory conclusions about which program leaks more information. This is a fundamental problem with existing approaches.
  • Asymptotic Behavior is Key: The authors argue that looking at how leakage behaves as the input size grows (i.e., its limit) provides a more stable and conflict-free basis for comparison. This is because the "noise" or variability introduced by specific input distributions tends to average out in the limit.
  • Renyi Entropy as a Unifying Framework: By using Renyi entropy, the paper shows that the conflicts arise not just from different metrics but from the inherent properties of these metrics across different parameter values.
  • Impossibility of Fine-Grained Comparison: A surprising result is that even with their refined approach, it might be impossible to achieve arbitrarily fine-grained comparisons between programs using Renyi entropy. There are fundamental limits to how distinguishable leakage can be.

Key Results

  • Demonstration of Conflicts: The paper provides concrete mathematical examples showing how Shannon entropy, min-entropy, and other Renyi entropy measures can disagree on the relative leakage of programs. For instance, for PROG P1 and P2, $\alpha=0$ suggests P1 leaks more, $\alpha=1$ suggests they leak similarly, and $\alpha=\infty$ suggests P2 leaks more.
  • Formalization of Conflict-Free Comparison: The paper introduces a formal framework and algorithms (Algorithm 4.4 and 4.5) that use the limit of leakage ratios to compare programs. This approach aims to resolve the conflicts observed with static leakage measures.
  • Leakage Level Definition: A definition for the "leakage level" of a FOP is proposed, based on the rate of convergence of its leakage measure as the input size grows.
  • Limits on Distinguishability: Lemma 4.7 shows that for any two distinct Renyi entropy parameters $\alpha$ and $\beta$, there exist programs where the ratio of their leakage measures can be arbitrarily large for one parameter and arbitrarily small for another, implying a fundamental limit to how finely leakage can be distinguished.

Limitations and Future Work

  • Focus on Deterministic Programs: The current work is limited to deterministic programs. Extending the analysis to non-deterministic programs would be a significant next step.
  • Theoretical Framework: While the paper provides a theoretical framework and algorithms, its practical application would require efficient computation of the required limits and distributions, which can be challenging for complex programs.
  • Incomparable Programs: The proposed algorithms acknowledge that some programs might remain incomparable, suggesting that a complete ordering of all programs by leakage might not always be possible with these metrics.
  • Further Exploration of Metrics: The paper focuses on Renyi entropy. Investigating other information-theoretic or non-information-theoretic metrics for leakage and their comparability would be valuable.
  • Practical Tooling: Developing tools that can automatically apply this analysis to real-world software would be a crucial future direction for practical impact.

Summary updated

Abstract

Information flow analysis is a powerful technique for reasoning about the sensitive information exposed by a program during its execution. While past work has proposed information theoretic metrics (e.g., Shannon entropy, min-entropy, guessing entropy, etc.) to quantify such information leakage, we argue that some of these measures not only result in counter-intuitive measures of leakage, but also are inherently prone to conflicts when comparing two programs P <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> and P <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> - say Shannon entropy predicts higher leakage for program P <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> , while guessing entropy predicts higher leakage for program P <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> . This paper presents the first attempt towards addressing such conflicts and derives solutions for conflict-free comparison of finite order deterministic programs.
BibTeX
@inproceedings{zhu2011quantifying,
  author = {Ji Zhu and Mudhakar Srivatsa},
  title = {{Quantifying Information Leakage in Finite Order Deterministic Programs}},
  booktitle = {ICC},
  year = {2011},
  url = {https://openreview.net/forum?id=rPcHTjzQ2Zk},
}
Figure