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_1$ and $P_2$ -- say Shannon entropy predicts higher leakage for program $P_1$, while guessing entropy predicts higher leakage for program $P_2$. This paper presents the first attempt towards addressing such conflicts and derives solutions for conflict-free comparison of finite order deterministic programs.
Introduction
In computer security, information flow analysis helps researchers understand how much a program's public output reveals about its secret inputs. To quantify this, researchers typically use entropy measures. However, a major problem exists: different metrics often disagree. For example, Shannon entropy might suggest Program A is leakier than Program B, while "guessing entropy" suggests the opposite. These contradictions make it nearly impossible for engineers to objectively decide which version of a program is more secure.
This paper aims to move beyond these ad-hoc choices by providing a mathematically rigorous, consistent way to compare program security. The authors introduce a novel, conflict-free framework for comparing "Finite Order Deterministic Programs" (FOPs) by analyzing the leakage level—the rate at which information leakage converges as the size of the secret input increases.
Methodology
The authors focus on Single-Input Single-Output (SISO) Deterministic Programs. They specifically define Finite Order Programs (FOPs) as those where the number of possible public outputs remains finite and constant, even as the size of the secret input grows (like a password checker that only ever outputs "True" or "False").
Key methodological steps include:
- Renyi Entropy Framework: The authors use Renyi entropy ($H_\alpha$) as a generalized metric that encompasses Shannon entropy, min-entropy, and others by varying a parameter $\alpha$.
- Conflict Proof: They mathematically prove that for any two different entropy measures, there will always exist pairs of programs where the measures conflict.
- Asymptotic Comparison: Instead of comparing leakage at a single fixed input size, they propose comparing the limit of leakage as the secret input size ($|A|$) approaches infinity.
- Relative Leakage Metric: They developed an algorithm that uses the ratio of leakage between two programs to determine which is "leakier" in a way that remains consistent regardless of which specific entropy measure ($\alpha$) is used.
Key Insights and Results
The authors show that conflicts between metrics aren't just rare edge cases; they are a fundamental mathematical property of entropy measures. The core insight is that for finite programs, the absolute amount of leaked information is less important than the rate at which security improves as you increase the "security parameter" (e.g., making a password longer).
Using synthetic examples (P1 through P7), the authors demonstrated several key results:
- Formalized Leakage Levels: Programs are categorized into "Leakage Levels" denoted by $\Theta$. For example, a program that leaks a constant amount of information regardless of input size has a leakage level of $\Theta(1)$.
- Conflict-Free Algorithm: The proposed comparison algorithm provides a consistent "Program A is leakier than B" result for a wide class of deterministic programs, resolving contradictions found in prior literature.
- Intuition Alignment: In cases where traditional Shannon entropy gave "counter-intuitive" results (suggesting a binary search was safer than a partial password leak), the new metric correctly aligned with standard security intuition.
Limitations and Future Work
While the framework is robust for FOPs, it faces challenges with oscillating programs (where behavior switches based on input size parity) because the limit does not converge. Additionally, the current model is strictly for deterministic programs; extending this to probabilistic programs remains a challenge. Finally, "Infinite Order Programs," where the output space grows with the input space (like encryption algorithms), require a different analytical approach.
Summary updated