Abstract
Language-based information flow security aims to decide whether an action-observable program can unintentionally leak confidential information if it has the authority to access confidential data. Recent concerns about declassification policies have provided many choices for practical intended information release, but more precise enforcement mechanisms for these policies are insufficiently studied. In this paper, we propose a security property on the where-dimension of declassification and present an enforcement based on automated verification. The approach automatically transforms the abstract model with a variant of self-composition and checks the reachability of illegal-flow states after transformation. The self-composition is equipped with a store-match pattern to reduce the state space and to model the equivalence of declassified expressions. Evaluation shows that our approach is more precise than type-based enforcement.
Introduction
In information flow security, the standard of Noninterference posits that secret inputs should never influence public outputs. However, this is often too restrictive for practical applications. Programs frequently need to release some sensitive information to function—such as a password checker returning a boolean result. This intentional release is known as declassification.
The primary challenge lies in defining where and how this release occurs without permitting accidental leaks. Traditional enforcement often relies on type systems, which are efficient but frequently "over-approximate," rejecting secure programs because they appear suspicious. This research focuses on the where-dimension of declassification, ensuring information is only downgraded at specific, authorized points.
Methodology
The authors propose Where-Security, a property verified through automated reachability analysis. The framework utilizes three core components:
- Symbolic Pushdown Systems (SPDS): Programs are modeled as SPDS to represent sequential logic with complex control flows and procedures accurately.
- Self-Composition: Security is checked by running two instances of the program side-by-side. If secret inputs differ but public outputs remain identical (except at authorized declassification points), the program is deemed secure.
- Store-Match Pattern: To combat the "state space explosion" typical of self-composition, the authors introduced a "store-match" optimization. This pattern avoids duplicating output channels and uses a specialized "match" operation to verify the equivalence of declassified values across runs, significantly pruning the search space.
Evaluation and Benchmarks
The method was evaluated using a suite of benchmark programs (P0 through P7) designed to challenge traditional security models with scenarios like conditional leaks and password authentication.
By moving from rigid type-checking to context-aware reachability analysis, the system can distinguish between "tainted" variables in different execution branches. This allows the enforcement mechanism to accept secure programs that type-based systems would otherwise reject.
Key Results
The implementation, built on the Moped model-checking engine, demonstrated significant improvements in both precision and efficiency:
- Higher Precision: The mechanism successfully validated secure programs (such as P2, P6, and P7) that traditional type-based systems incorrectly flagged as insecure.
- Efficiency Gains: The store-match pattern achieved an average 41.4% reduction in verification costs (time and state space) compared to standard transformation techniques.
Conclusion
While this approach significantly advances enforcement for the where-dimension of declassification, it does not yet fully address other dimensions like "what" is released (e.g., delimited release). Future work aims to integrate these dimensions into the reachability analysis framework to provide a more holistic, automated security tool.
Summary updated