Safety Analysis in the NGAC Model

Brian Tan, Ewan S. D. Davies, Indrakshi Ray, Mahmoud A. Abdelgawad · 2025

Read Safety Analysis in the NGAC Model by Brian Tan, Ewan S. D. Davies, Indrakshi Ray, Mahmoud A. Abdelgawad (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-06406.txt.

Introduction

Access control decides who may do what in a computer system, and the NGAC model is a modern, graph-based way to set those rules. Brian Tan and co-authors study its safety problem in this 2025 paper: can a given user ever gain a right they do not start with? Knowing whether that question is even tractable matters for trusting the model.

The team shows that, under mild assumptions, the problem is coNP-complete, so no fast general method is likely to exist. Under further realistic assumptions, they give an algorithm that beats brute force search by a wide margin. They also show that real-world patterns of mutually exclusive attributes can push their method close to its worst case, which marks where care is needed.

Catalog record

CREATORBrian Tan, Ewan S. D. Davies, Indrakshi Ray, Mahmoud A. Abdelgawad
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE44 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-06406

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Safety Analysis in the NGAC Model Brian Tan, Ewan S. D. Davies, Indrakshi Ray, Mahmoud A. Abdelgawad Abstract . We study the safety problem for the next-generation access control (NGAC) model. We show that under mild assumptions it is 𝖼𝗈𝖭𝖯 \mathsf{coNP} -complete, and under further realistic assumptions we give an algorithm for the safety problem that significantly outperforms naive brute force search. We also show that real-world examples of mutually exclusive attributes lead to nearly worst-case behavior of our algorithm. DOI: 10.1145/3734436.3734444 Conference: Proceedings of the 30th ACM Symposium on Access Control Models and Technologies; July 8–10, 2025; Stony Brook, NY Proceedings of the 30th ACM Symposium on Access Control Models and Technologies (SACMAT ’25), July 8–10, 2025, Stony Brook, NY, USA ISBN: 979-8-4007-1503-7/2025/07 CCS: Security and privacy Access control CCS: Theory of computation Problems, reductions and completeness † † cc-license: by 1. Introduction Access control policies (ACPs) are an essential technology in cybersecurity. Broadly, given some users and resources, an ACP guarantees the legitimate access of resources by authorized users as well as preventing unauthorized access. There are several widely-accepted ACP frameworks including Role-Based Access Control (RBAC) and Attribute-Based Access Control (ABAC). We study a prominent example of ABAC, the Next Generation Access Control (NGAC) model published by the American National Standards Institute ANSI INCITS, 2020 . Roughly, the state of an NGAC model is equivalent to a directed graph (digraph) whose vertices comprise sets of users, user attributes, resource attributes, resources, and policy classes. The edges of the digraph correspond to relations on the vertices that fall into one of four categories: obligations, prohibitions, associations, and assignments. Given a state, we say that a user u can access a resource r if there is a path from u to r in the associated digraph. An important feature of the NGAC model in applications is the provision for commands (also known as obligations ) that, subject to some conditions, change the state of the model. For example, a command could introduce or delete vertices and edges in the digraph after checking a condition such as the existence of an edge in the current state. The dynamic nature of an NGAC model means that formal analysis is nontrivial, and in this work we are interested in a notion of safety for such models. For us, an NGAC model is safe if the execution of any available obligations cannot modify the state in such a way that a new access path from some user u to a resource r is created. The precise definition is somewhat technical, we defer a formal statement to Section 2 . The safety problem ( \mathrm{SP} ) is the problem of determining, given a description of an NGAC model, whether the model is safe in this sense. An important subtlety is that safety is represented as the absence of some concrete structure in the model, namely a sequence of commands whose execution results in a new access path. Thus, it is convenient to consider the complementary problem that could naturally be called the unsafety problem or more technically the co-safety problem ( \mathrm{coSP} ). Our main contributions are to give a rigorous definition for the safety problem (and co-safety problem) in the NGAC model, and to show that co-safety is an \mathsf{NP} -complete decision problem (in the mono-operational case, see below). We achieve this in two steps, first abstracting the dynamic nature of co-safety in the NGAC model into a problem of path-finding subject to constraints in a static digraph that we call directed acyclic constrained connectivity ( \mathrm{DACC} ). We then reduce 3-coloring ( \mathrm{3COL} ) to this decision problem, showing that co-safety is NP-complete via the relation \mathrm{3COL}\leq_{p}\mathrm{DACC}\leq_{p}\mathrm{coSP} where \mathrm{A}\leq_{p}\mathrm{B} represents the standard notion that there is a polynomial-time reduction from problem \mathrm{A} to problem \mathrm{B} . That \mathrm{3COL} can be reduced to the co-safety problem in the NGAC model shows that \mathrm{coSP} is \mathsf{NP} -hard, and proving that \mathrm{coSP}\in\mathsf{NP} is trivial. While the fact that a problem equivalent to \mathrm{DACC} is \mathsf{NP} -complete has been discussed in the literature before (cf. Problem GT54 in Garey and Johnson’s comprehensive book Garey & Johnson, 1979 and the paper Gabow et al., 1976 ), since \mathrm{DACC} is not a well-known \mathsf{NP} -complete problem we give the short proof for completeness. Our secondary contributions are to exploit the graph-theoretic nature of the safety problem for the NGAC model to give an algorithm for the safety problem that significantly outperforms naive brute-force search. Though our algorithm is exponential-time in general, it is adaptive to a graph-theoretic property known as the number of maximal independent sets (MIS) in a natural “supergraph” constructed from the NGAC model. That is, if the specific NGAC model being studied yields supergraph that has a polynomially-bounded number of MIS then our algorithm decides the safety problem in polynomial time. We also investigate the real-world implications of this result by considering natural structures that occur in real-world NGAC models. Here, our findings are negative and we give a natural class of NGAC models which encode the structure known by the classic combinatorial result typically attributed to Moon and Moser Miller & Muller, 1960 ; Moon & Moser, 1965 to yield the worst possible case for the number of MIS. These observations link the complexity of safety in the NGAC model to a large body of work in extremal combinatorics and the algorithmic study of enumerating MIS. Writing \mu(C) for the set of MIS in a simple graph C , we know Miller & Muller, 1960 ; Moon & Moser, 1965 that |\mu(C)|\leq 1.45^{|V(C)|} , and this forms the basis of the worst-case time complexity of our algorithm. Naive search for (maximal) independent sets in C takes much longer: time \Omega(2^{|{V(C)}|}) . 1.1. Related work The kind of safety problem we study here has a long and rich history in cybersecurity. The foundational work of Harrison, Ruzzo and Ullman Harrison et al., 1976 defines an ACP framework whose state consists of sets of rights in the entries of a matrix indexed by subject-object pairs. We refer to this widely studied model, which appears in many introductory texts Bishop, 2003 ; Denning, 1982 ; Pfleeger et al., 2024 , as the HRU model. As with the more modern NGAC model, the HRU model is dynamic and features state-changing commands. In part due to the flexibility of the HRU model, the safety problem for the model is rather subtle. Harrison, Ruzzo and Ullman themselves demonstrated Harrison et al., 1976 that different natural formulations of the safety problem for the HRU model can be \mathsf{NP} -complete or even undecidable. One of the restrictions that permits the \mathsf{NP} -completeness proof is that commands are mono-operational (which we explain later), and we make an analogous assumption in our main result too. Aside from the fact that natural variations on safety can have such wildly different computational complexities, the challenges of safety analysis are further evidenced by the comprehensive review the HRU model due to Tripunitara and Li Tripunitara & Li, 2013 . Tripunitara and Li refined the definitions of safety problems for the HRU model from the original work to resolve several ambiguities. They also corrected several errors in widely-circulated proofs

Read the complete text