TL;DR
This paper tackles the challenge of preventing sensitive information leaks in dynamic program analysis by generalizing the "permissive-upgrade" technique to arbitrary security lattices. This advancement allows for more precise and less restrictive information flow control, enabling programs to run to completion even when intermediate variables are influenced by sensitive data, as long as they aren't misused later.
What Problem Does This Paper Address?
Dynamic information flow control (IFC) aims to prevent sensitive data from leaking through a program's execution. A common technique, the "no-sensitive-upgrade" (NSU) check, is sound but overly restrictive: it halts a program if a variable's security label is "upgraded" (becomes more sensitive) due to a control dependency on sensitive data, even if that variable's new, sensitive value is never actually used. To address this, the "permissive-upgrade" (PU) check was introduced. PU allows such upgrades but marks the variable as "partially-leaked." The program is only stopped later if this partially-leaked variable is used in a way that could reveal sensitive information (e.g., as a branch condition).
However, existing PU techniques are limited to simple "low-high" security lattices and their pointwise products. This paper addresses the gap by developing a novel and non-trivial generalization of permissive-upgrade to arbitrary security lattices, which are more complex and realistic. This generalization is crucial for applying PU to a wider range of systems and security policies.
Methods
The core contribution is the development of a generalized permissive-upgrade mechanism for arbitrary security lattices. This involves:
- Introducing "*-ed" Labels: For each security level
Ain the lattice, a new labelA*is introduced, signifying "partially-leaked A." ThisA*label indicates that the variable's value might be sensitive, but its "pure" (non-partially-leaked) label is bounded below byA. - Defining New Assignment Rules: The paper introduces two new assignment rules (
assn-1andassn-2) that handle the propagation and creation of theseA*labels. These rules are carefully designed to be sound and permissive.assn-1handles cases where overwriting a variable is safe, whileassn-2deals with potentially sensitive overwrites by introducingA*labels. - Developing a Generalized Store Equivalence: To prove the soundness of the generalized PU, a new definition of store equivalence (
~A) is introduced. This definition is crucial for capturing when two program states are indistinguishable to an adversary at a given security level, especially when dealing with partially-leaked values. This definition is more complex than previous ones and accounts for various interactions between pure andA*labels. - Formal Proof of Termination-Insensitive Noninterference (TINI): The paper provides a rigorous proof that the generalized permissive-upgrade system guarantees TINI, a standard security property in IFC. This proof relies on a set of lemmas that establish properties of expression evaluation, label preservation, and confinement.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- The Power of "Partially-Leaked" Labels: The core idea is that marking a variable as "partially-leaked" (
A*) is sufficient to prevent information leaks if the variable is never used in a sensitive context (like a branch condition). This allows programs to proceed when a simple NSU check would halt them. - Arbitrary Lattices Require More Sophisticated Labels: Generalizing PU beyond simple two-point lattices necessitates a more nuanced labeling scheme. The introduction of
A*labels and their specific interaction rules are key to handling complex lattice structures. - Incomparability of Generalizations: The paper highlights that the generalization to arbitrary lattices (puA) and the generalization to pointwise products of two-point lattices (puP) are not strictly better than each other. Each can be more permissive than the other in different scenarios, suggesting that the choice of generalization depends on the specific lattice structure.
- The Devil is in the Details of Equivalence: Proving the soundness of PU for arbitrary lattices hinges on a carefully crafted definition of store equivalence. The paper's definition accounts for the subtle ways in which partially-leaked values can be distinguished or indistinguishable to an adversary.
Key Results
- A Sound and Permissive Generalization: The paper successfully constructs a generalization of permissive-upgrade that applies to arbitrary security lattices.
- Non-Trivial Rules and Definitions: The authors demonstrate that this generalization is non-trivial, requiring new assignment rules and a sophisticated definition of store equivalence.
- Formal Proof of TINI: The generalized system is proven to satisfy Termination-Insensitive Noninterference (TINI), a crucial security guarantee.
- Demonstrated Incomparability: Examples are provided showing that the new arbitrary lattice generalization (puA) and the pointwise product generalization (puP) are incomparable in terms of permissiveness on powerset lattices.
Limitations and Future Work
- Complexity of the Equivalence Relation: The paper acknowledges that the definition of store equivalence for arbitrary lattices is complex. While proven sound, its practical implementation and understanding might require further work.
- Comparison with Other Approaches: While the paper compares its arbitrary lattice generalization (puA) with the pointwise product generalization (puP), further exploration of its relationship with other IFC techniques could be beneficial.
- Practical Implementation: The paper focuses on the formalization of the generalized permissive-upgrade. Future work could involve implementing this generalized system in a real-world programming language or runtime environment.
- Performance Implications: While permissive-upgrade aims to improve permissiveness, the overhead of managing more complex labels and equivalence relations in a dynamic setting would be an important area for future investigation.
Summary updated