Mathematical optimization provides a principled approach to access control problems that require selecting the best alternative from a set of possibilities. In this paper, we introduce integer programming formulations for two relationship-based access control (ReBAC) problems: (i) the established policy mining problem and (ii) a novel approach to testing the correctness of mined policies while minimizing the number of required authorization checks. While existing approaches rely on specialized heuristics or machine learning-based methods that often become unwieldy with complex constraints, our integer programming formulation elegantly captures these complexities through algebraic equations, ensuring exact solutions. Experimental results show that for policy testing, our approach reduces the number of required authorization test cases by over $90 \%$ compared to existing methods and that this reduction scales with system size, significantly improving efficiency in growing systems.

Using access control policy rules with deny effects (i.e., negative authorization) can be preferred to using complemented conditions in the rules as they are often easier to comprehend in the context of large policies. However, the two constructs have different impacts on the expressiveness of a rule-based access control model. We investigate whether policies expressible using complemented conditions can be expressed using deny rules instead. The answer to this question is not always affirmative. In this paper, we propose a practical approach to address this problem for a given policy. In particular, we develop theoretical results that allow us to pose the problem as a set of queries to an SAT solver. Our experimental results using an off-the-shelf SAT solver demonstrate the feasibility of our approach and offer insights into its performance based on access control policies from multiple domains.

Obtaining an accurate specification of the access control policy enforced by an application is essential in ensuring that it meets our security/privacy expectations. This is especially important as many of real-world applications handle a large amount and variety of data objects that may have different applicable policies. We investigate the problem of automated learning of access control policies from web applications. The existing research on mining access control policies has mainly focused on developing algorithms for inferring correct and concise policies from low-level authorization information. However, little has been done in terms of systematically gathering the low-level authorization data and applications' data models that are prerequisite to such a mining process. In this paper, we propose a novel black-box approach to inferring those prerequisites and discuss our initial observations on employing such a framework in learning policies from real-world web applications.

Mining algorithms for relationship-based access control policies produce policies composed of relationship-based patterns that justify the input authorizations according to a given system graph. The correct functioning of a policy mining algorithm is typically tested based on experimental evaluations, in each of which the miner is presented with a set of authorizations and a system graph, and is expected to produce the corresponding ground truth policy. In this paper, we propose formal properties that must exist between the system graph and the ground truth policy in an evaluation test so that the miner is challenged to produce the exact ground truth policy. We show that failure to verify these properties in the experiment leads to inadequate evaluation, i.e., not truly testing whether the miner can handle the complexity of the ground truth policy. We also argue that following these properties would provide a computational advantage in the evaluations. We propose algorithms to identify and correct violations of these properties in system graphs. We also present our observations regarding these properties and their enforcement using a set of experimental studies.

Access control policies are crucial in securing data in information systems. Unfortunately, often times, such policies are poorly documented, and gaps between their specification and implementation prevent the system users, and even its developers, from understanding the overall enforced policy of a system. To tackle this problem, we propose the first of its kind systematic approach for learning the enforced authorizations from a target system by interacting with and observing it as a black box. The black-box view of the target system provides the advantage of learning its overall access control policy without dealing with its internal design complexities. Furthermore, compared to the previous literature on policy mining and policy inference, we avoid exhaustive exploration of the authorization space by minimizing our observations. We focus on learning relationship-based access control (ReBAC) policy, and show how we can construct a deterministic finite automaton (DFA) to formally characterize such an enforced policy. We theoretically analyze our proposed learning approach by studying its termination, correctness, and complexity. Furthermore, we conduct extensive experimental analysis based on realistic application scenarios to establish its cost, quality of learning, and scalability in practice.

Recent access control models such as attribute-based access control and relationship-based access control allow flexible expression of authorization policies using the concepts of rules and conditional expressions. The independent nature of policy rules from each other and the amount of flexibility that they enjoy (e.g., the type of conditional expressions they support and whether they can permit or deny matching requests) make those policies quite expressive. But how expressive are they? Do we need to enable all possible flexibilities in a rule-based model to achieve the maximum possible expressiveness? Answering such questions is essential in making informed decisions when designing new models or choosing existing models for implementation. In this paper, we propose an approach towards answering those questions by developing a novel theory for capturing the semantics of rule-based policies depending on their support of different constructs such as flexibility of conditional expressions, rule modalities, and conflict resolution. Our formal policy semantics model enjoys an intuitive design that can capture the semantics of various rule-based policies. We show the well-formedness properties of such semantics and how they can be used to analyze the expressive power of a number of rule-based models.

Understanding access control policies is essential in understanding the security behavior of systems. However, often times, a complete and accurate specification of the enforced access control policy in a system is not available. In fact, scale and complexity of a system, or unavailability of its source code, may prevent users and even its developers from having access to such accurate specification. In this paper, we propose a novel, systematic approach for learning access control policies where target systems are treated as black boxes. In particular, we show how we can construct a deterministic finite automaton (DFA) characterizing the relationship-based access control (ReBAC) policy of a system by interacting with its access control engine using minimal number of access requests. Our experiments on realistic application scenarios and their promising results demonstrate the feasibility, scalability and efficiency of our learning approach.

Relationship-based access control (ReBAC) provides a flexible approach to specify policies based on relationships between system entities, which makes them a natural fit for many modern information systems, beyond online social networks. In this paper we are concerned with the problem of mining ReBAC policies from lower-level authorization information. Mining ReBAC policies can address transforming access control paradigms to ReBAC, reformulating existing ReBAC policies as more information becomes available, as well as inferring potentially unknown policies. Particularly, we propose a systematic algorithm for mining ReBAC authorization policies, and a first of its kind approach to mine graph transition policies that govern the evolution of ReBAC systems. Experimental evaluation manifests efficiency of the proposed approaches.

Mining access control policies can reduce the burden of adopting more modern access control models by automating the process of generating policies based on existing authorization information in a system. Previous work in this area has focused on mining positive authorizations only. That includes the literature on mining role-based access control policies (which are naturally about positive authorization) and even more recent work on mining attribute-based access control (ABAC) policies. However, various theoretical access control models (including ABAC), specification standards (such as XACML), and implementations (such as operating systems and databases) support negative authorization as well as positive authorization. In this paper, we propose a novel approach to mine ABAC policies that may contain both positive and negative authorization rules. We evaluate our approach using two different policies in terms of correctness, quality of rules (conciseness), and time. We show that while achieving the new goal of supporting negative authorizations, our proposed algorithm outperforms existing approach to ABAC mining in terms of time.