Valued Authorization Policy Existence Problem

Jason Crampton, Eduard Eiben, Gregory Z. Gutin, Daniel Karapetyan, Diptapriyo MajumdarSACMAT 2021 · OpenReview

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

Abstract

Problems of satisfiability and resiliency in workflows have been widely studied in the last decade. Recent work has shown that many such problems may be viewed as special cases of the authorization policy existence problem (APEP), which returns an authorization policy if one exists and "No'' otherwise. A solution may not exist because of the restrictions imposed by the base authorization relation and constraints that form part of the input to APEP. However, in many practical settings it would be more useful to obtain a "least bad" policy than just a "No", where "least bad'' is characterized by some numerical value associated with the policy indicating the extent to which the policy violates the base authorization relation and constraints. Accordingly, we introduce the Valued APEP, which returns an authorization policy of minimum weight, where the (non-negative) weight is determined by the constraints violated by the returned solution (and is 0 if all constraints are satisfied). We then establish a number of results concerning the parameterized complexity of Valued APEP. We prove that the problem is fixed-parameter tractable if the set of constraints satisfies two restrictions, but is intractable if only one of these restrictions holds. (Most constraints known to be of practical use satisfy these restrictions.) We introduce the notion of a user profile for a weighted constraint, which enables us to prove a powerful result, a corollary of which improves on known complexity results for APEP. Finally, we consider Valued APEP when restricted to particular sub-classes of constraints and show that instances of such problems can be reduced to the valued workflow satisfiability problem, enabling us to exploit known algorithms to solve these particular instances.
BibTeX
@inproceedings{crampton2021valued,
  author = {Jason Crampton and Eduard Eiben and Gregory Z. Gutin and Daniel Karapetyan and Diptapriyo Majumdar},
  title = {{Valued Authorization Policy Existence Problem}},
  booktitle = {SACMAT},
  year = {2021},
  url = {https://openreview.net/forum?id=Lcexvn4bHZ},
}
Figure