TL;DR
This paper introduces a novel approach to automatically analyze the security of complex trust management policies by translating them into a format understandable by model checking tools. This allows for the verification of critical security properties, like preventing unauthorized access, even when policies are dynamically updated by untrusted parties, a problem that is often computationally intractable with traditional methods.
What Problem Does This Paper Address?
In modern distributed systems, trust management (TM) is crucial for controlling access to resources. TM systems often rely on delegation, where one entity grants authority to another. This delegation mechanism offers scalability but introduces significant security challenges. Resource owners need to ensure that their policies remain secure even when untrusted or semi-trusted entities modify parts of the global policy state. Specifically, they need to answer questions like "Could someone outside the organization gain access due to policy changes made by external parties?" The existing trust management language, RT, has efficient algorithms for simple queries, but more complex and useful questions become computationally intractable. This paper aims to bridge this gap by providing a practical and automated method for analyzing these complex security properties.
Methods
The core of this paper's contribution lies in its novel translation methodology. The authors propose to leverage model checking, a powerful automated technique for verifying system properties, to analyze RT policies. The process involves several key steps:
- Maximum Relevant Policy Set (MRPS) Construction: To handle the potentially infinite state space of RT policies, the authors define an MRPS. This is a finite set of policy statements and principals that are relevant to a specific query. This step is crucial for making the problem tractable for model checkers.
- SMV Model Translation: The RT policy, along with the MRPS, is translated into a model understandable by the SMV (Symbolic Model Verifier) tool. This involves representing statements as bit vectors and roles as derived variables.
- Initialization and Next State Relations: The initial state of the model reflects the initial policy. Transitions between states are modeled by allowing non-permanent statement bits to be nondeterministically assigned, simulating policy changes.
- Role Dependency Graph (RDG) Analysis: The authors utilize RDGs to visually represent relationships between roles and principals. This helps in identifying circular dependencies and potential optimizations.
- Handling Circular Dependencies: RT policies can have self-referential or circular statements. The paper describes methods for detecting and "unrolling" these circular dependencies to ensure they can be processed by SMV, which cannot handle circular definitions directly.
- Chain Reduction: Optimizations are applied to reduce the state space by identifying logically equivalent states or policy statements.
The novelty lies in the specific translation rules from RT constructs (Type I, II, III, IV statements) to SMV specifications and the systematic approach to managing the state space explosion inherent in model checking.
Datasets
Not discussed in the paper. The paper uses a fictitious company's access control policy as a case study, which is presented in Figure 14.
Key Insights and Ideas
- Model Checking as a Practical Solution: The paper demonstrates that model checking, despite its potential for state explosion, can be a practical and automated solution for analyzing complex trust management policies, especially for questions that are computationally intractable with traditional methods.
- MRPS for Tractability: The concept of a Maximum Relevant Policy Set (MRPS) is a key innovation that makes the problem finite and thus amenable to model checking. It intelligently prunes the policy space to only what's necessary for a given query.
- Bridging Formalisms: The paper effectively bridges the gap between a domain-specific language (RT) and a general-purpose verification tool (SMV), allowing for the reuse of existing, mature analysis tools.
- Handling Dynamic Policies: The approach inherently handles the dynamic nature of trust management policies by modeling transitions between states, allowing for analysis of properties that hold over time.
- Counterexamples for Debugging: A significant benefit of model checking is its ability to provide concrete counterexamples when a property fails, which is invaluable for debugging and understanding policy flaws.
Key Results
The paper presents a case study of an access control policy for a fictitious company, "Widget Inc." The analysis involved verifying properties such as:
- Whether the marketing strategy and operations plan are only available to employees.
- Whether everyone with access to the operations plan also has access to the marketing plan.
The translation from RT to SMV took approximately 9.9 seconds. The first two properties were verified in about 400 ms. The second property was found to be false in approximately 480 ms, with a counterexample provided. This demonstrates the feasibility and efficiency of the proposed approach for analyzing complex security properties.
Limitations and Future Work
- State Explosion Problem: While the MRPS and other optimizations help, the paper acknowledges that it is still possible to create an MRPS with a state space so large that role containment cannot be verified in a useful amount of time.
- Tight Bound for MRPS Principals: The authors mention that finding a tighter bound for the number of additional principals needed in the MRPS is a desirable future work direction.
- Extended RT Variants: Future work includes extending the approach to handle negated policy statements and other variants of RT.
- Optimization using RDG: Further optimization of the preprocessing step using RDGs to reduce state space and the number of statements/principals is planned.
- Disconnected Graphs: While the current translation approach works correctly for disconnected graphs, analyzing them using RDGs could provide further optimization insights.
Summary updated