Reconciling Belief and Vulnerability in Information Flow

Sardaouna Hamadou, Vladimiro Sassone, Catuscia Palamidessi

Abstract

Traditional methods for measuring information leakage, such as Shannon entropy, often fail to capture the actual risk of an attacker guessing a secret in a single attempt. While min-entropy (vulnerability) addresses this "one-try" risk, it typically assumes the attacker has either no prior knowledge or perfectly accurate information. This paper introduces a unified framework that reconciles subjective attacker beliefs with objective vulnerability. By proposing the belief-vulnerability metric, the authors provide a realistic way to quantify security in environments where an attacker's background information may be inaccurate or biased.

Introduction

In computer security, quantifying how much a program leaks about a secret is a fundamental challenge. For years, Shannon entropy was the standard metric, but it primarily measures average uncertainty, which does not directly translate to the probability of a successful "one-try" attack. The community subsequently shifted toward min-entropy, or vulnerability, to focus on this immediate risk.

However, a critical gap remained: standard vulnerability models assume an attacker's prior knowledge is perfectly aligned with reality. In practice, attackers often rely on "extra information"—such as public records or previous data breaches—which can be outdated or incorrect. This research bridges the gap between the "Belief" approach (subjective knowledge) and the "Vulnerability" approach (objective risk).

The Unified Framework: Belief-Vulnerability

The core contribution of this work is the definition of belief-vulnerability ($V(A : B)$). In this model, $A$ represents the secret and $B$ represents the attacker's background information. The framework distinguishes between the attacker's subjective belief ($\beta$) about the distribution of secrets and the actual distribution ($\rho$).

Belief matrix $p_\beta(b|a)$ representing the attacker's subjective assumptions about the secret.

As shown in the belief matrix above, the attacker's assumptions about the relationship between their background information $b$ and the secret $a$ can be explicitly modeled. The attacker chooses their guess based on $\beta$, but their success is determined by the ground truth $\rho$.

Modeling Information Channels

To evaluate this framework, the authors analyze how an attacker's belief is updated after observing a program's output ($O$). This "a posteriori" analysis is crucial because program outputs can serve as a "sanity check" for the attacker. If an observation is impossible under their current belief, they may revert to a more objective analysis.

Channel matrix $p(o|a)$ representing the conditional probability of observations given a secret.

The channel matrix above illustrates how secrets map to observations in a synthetic program. By combining these channel probabilities with belief distributions, the authors can calculate the precise leakage of a system. They introduce $\omega$-accurate beliefs to mathematically bound how much an attacker's uncertainty changes based on the accuracy of their initial information.

Key Insights

The study reveals several counter-intuitive properties of information flow:

  • Belief as a Shield: Inaccurate background knowledge can actually enhance security. If an attacker is convinced of a falsehood, they are less likely to guess the true secret than if they had no information at all.
  • The Correction Effect: Program outputs can inadvertently help an attacker by contradicting their wrong beliefs, forcing them to discard inaccurate assumptions and potentially making the program more vulnerable than it appeared under a "no-knowledge" model.
  • Shannon Entropy's Limitations: The authors demonstrate that programs with identical Shannon leakage can have vastly different vulnerabilities when attacker beliefs are considered.

Conclusion

This research provides a robust mathematical foundation for understanding information leakage in the presence of imperfect knowledge. By unifying belief and vulnerability, the authors offer a more nuanced toolset for security analysts. Future work will focus on extending this model to multi-try "guessing entropy" scenarios and developing automated tools to scale these calculations for complex, real-world protocols.

Summary updated

Abstract

Belief and vulnerability have been proposed recently to quantify information flow in security systems. Both concepts stand as alternatives to the traditional approaches founded on Shannon entropy and mutual information, which were shown to provide inadequate security guarantees. In this paper we unify the two concepts in one model so as to cope with (potentially inaccurate) attackers' extra knowledge. To this end we propose a new metric based on vulnerability that takes into account the adversary's beliefs.
BibTeX
@inproceedings{hamadou2010reconciling,
  author = {Sardaouna Hamadou and Vladimiro Sassone and Catuscia Palamidessi},
  title = {{Reconciling Belief and Vulnerability in Information Flow}},
  booktitle = {IEEE Symposium on Security and Privacy},
  year = {2010},
  doi = {10.1109/sp.2010.13},
}
Figure