TL;DR
This paper introduces "Valued Authorization Policy Existence Problem" (Valued APEP), a more practical version of existing authorization policy problems. Instead of just saying "no policy exists," Valued APEP finds the "least bad" policy by minimizing a cost function that penalizes constraint violations. The authors also develop new theoretical tools and experimental methods to analyze and solve these problems efficiently.
What Problem Does This Paper Address?
In computer systems, authorization policies define who can access what resources. These policies can become complex, especially with "constraints" that add further restrictions (e.g., "Chinese walls" or "separation of duty"). The "Authorization Policy Existence Problem" (APEP) tries to find a policy that satisfies all these rules. However, in real-world scenarios, a perfect policy might not exist. In such cases, simply returning "no" isn't helpful. Administrators need to know the best possible policy, even if it's not perfect. This "best" policy is one that violates the rules the least, where "least bad" is quantified by a numerical "weight" or "cost." This paper addresses this by introducing Valued APEP, which finds a policy with the minimum possible violation cost.
Methods
The core of the paper is the introduction of Valued APEP, a generalization of APEP. Instead of a binary "yes/no" answer, Valued APEP returns an authorization policy that minimizes a defined weight function. This weight function sums up the costs of violating various constraints and user authorization rules. The authors delve into the parameterized complexity of Valued APEP, a field that analyzes problem difficulty based on specific parameters (like the number of resources or users). They introduce the concept of a "user profile" for authorization relations, which helps analyze constraints that are "user-independent" (meaning their satisfaction doesn't depend on the specific identities of users). This user profile concept is crucial for developing efficient algorithms and proving complexity results. They also propose two Mixed Integer Programming (MIP) formulations for solving Valued APEP, one "naive" and one that leverages the user profile concept.
Datasets
Not discussed in the paper. The authors do mention creating a "pseudo-random instance generator" for their experiments, specifically designed around the concept of T-resiliency of WSP.
Key Insights and Ideas
- "Least Bad" is Better Than "No": The most significant insight is the shift from a purely satisfiability-based problem (APEP) to a cost-minimization problem (Valued APEP). This makes the problem much more practical for real-world security and workflow management.
- User Profiles as a Powerful Abstraction: The introduction of "user profiles" is a key theoretical contribution. It provides a way to abstract away user identities for user-independent constraints, simplifying complexity analysis and enabling more efficient algorithms. This is analogous to how patterns are used in workflow satisfiability problems.
- FPT-Aware Formulations Matter: The experimental results highlight that even for problems with known theoretical FPT (Fixed-Parameter Tractable) properties, the formulation used for general-purpose solvers (like MIP solvers) is critical. An "FPT-aware" formulation that exploits the problem's structure can dramatically outperform a naive one.
Key Results
- Valued APEP Complexity: The paper establishes parameterized complexity results for Valued APEP, showing it's fixed-parameter tractable under certain constraint restrictions (t-wbounded and user-independent) but intractable otherwise.
- Improved APEP Complexity: The user profile concept leads to improved complexity results for APEP itself, particularly for certain constraint types.
- Experimental Performance: The "User-Profile formulation" for Valued APEP demonstrated significantly better performance than a "Naive formulation" in computational experiments, exhibiting FPT-like running times. The UP formulation scaled much better with instance size.
- T-Resiliency Modeling: The paper shows how Valued APEP can be used to model and address "T-resiliency" in workflows, a concept related to ensuring business continuity even when a certain number of users are unavailable.
Limitations and Future Work
- Constraint Restrictions: The FPT results for Valued APEP are contingent on specific restrictions on the constraints (t-wbounded and user-independent). The paper notes that most practical constraints satisfy these, but further investigation into other constraint types is warranted.
- Generalizing APEP: The authors suggest exploring other problems in access control that can be encoded as APEP instances.
- Weight Function Design: Developing appropriate weight functions for new encodings is an area for future work, aiming to provide more useful (weighted) solutions.
- Trade-offs: The paper opens the door for further work on quantifying trade-offs between violating security policies and ensuring business continuity, which is crucial for practical risk management.
- Solver Performance: While the UP formulation showed FPT-like behavior, the paper acknowledges that the formulation size can still be exponential in the parameter k (number of resources), limiting scalability for very large k.
Summary updated