Safety Analysis in the NGAC Model

Brian Tan; Ewan S. D. Davies; Indrakshi Ray; Mahmoud A. Abdelgawad

REVIEW

Safety Analysis in the NGAC Model

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

Computational Complexity · Submitted 9 May 2025 · 29 references

Pith's verdict: The coNP-completeness proof for NGAC safety has a missing-create-commands bug in the key reduction, but the DACC abstraction and algorithm are solid and worth a careful revision.

T0 · AI review

How this review was made: An AI referee (deepseek-v4-flash) read the paper on August 15, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 3 major objections · 5 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv ID2505.06406 (version 1)

Pith IDLVISTTV2, Pith's permanent record of this paper and its review

CitationBrian Tan, Ewan S. D. Davies, Indrakshi Ray, Mahmoud A. Abdelgawad. "Safety Analysis in the NGAC Model." arXiv:2505.06406 (2025). https://pith.science/paper/LVISTTV2

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

Colleague,

The paper claims that the co-safety problem for NGAC is coNP-complete, but the main hardness reduction is broken. In Theorem 3.5, the construction only adds create commands for edges that appear in constraints; the connector edges from the 3COL reduction (s→v1, color_i→v_{i+1}, color_n→t) have no create commands, so they can never be created from the initial state. Since any s-t path in those instances uses those edges, the "Yes" direction of the DACC≤coSP reduction fails: a Yes DACC instance maps to a No coSP instance. The stated bijection between valid subgraphs and reachable states is false. This is the only proof of NP-hardness for coSP, so the headline coNP-completeness claim is unsupported as written. The fix is easy (add unconditional create commands for unconstrained edges), but the proof currently does not contain it.

That said, the paper has real merits. The DACC abstraction is a clean way to separate the graph-theoretic core of safety from the NGAC machinery, and the 3COL-to-DACC reduction is correct and concise. The MIS-enumeration algorithm in Section 4 is a sensible application of known results (Moon-Moser, Makino-Uno) and the complexity analysis is honest. Section 5 makes a useful negative point: realistic mutual-exclusion structures produce nearly worst-case numbers of maximal independent sets, so the algorithm is unlikely to help in practice. The writing is clear and the related work is handled carefully.

Two smaller issues. Lemma 3.4 claims coSP∈NP but does not bound the certificate sequence length; under assumptions 1–3 any reachable state can be reached in polynomially many operations, so this is repairable but should be stated. Also, the algorithm's supergraph construction in Section 4 is fine on its own, but it highlights the same issue: the model's actual supergraph would not contain the unconstrained edges of the 3COL-derived instance, which is exactly the flaw.

Who should read this? Access-control researchers will find the DACC formulation and the negative result about separable duties interesting. Complexity theorists may see it as another data point in the HRU-style safety analysis line. But as a complexity paper, it is not reliable until the reduction is fixed.

My recommendation: send it to peer review, but with the expectation of major revision. The core idea is salvageable and likely correct after adding the missing create commands. Don't desk-reject; but don't accept as-is either.

Referee report

Major objections (3)

[Theorem 3.5 (§3)] The construction of the command set COM adds create commands only for edges appearing in E(C), so edges that occur in no constraint have no create command. In the DACC instance produced by Theorem 3.3, the connector edges s→v1, each R_i→v_{i+1}, and R_n→t are unconstrained, and they are absent from the initial state (AU = {(u,s)}). Hence no sequence of commands can ever make them present, and the claimed bijection between valid subgraphs of Γ and reachable states of the user DAG is false. In particular, a Yes instance of DACC, whose witnessing s-t path must use these connector edges, is mapped to a No instance of coSP, so the Yes direction of the reduction is unproved and the NP-hardness conclusion of Theorem 3.5 does not follow. This gap is load-bearing: the paper's headline coNP-completeness claim depends entirely on this reduction.
[Lemma 3.4 (§3)] The certificate for coSP consists of a tuple and a sequence S of commands, but no polynomial bound on |S| is given. Because commands may create and destroy the same edge repeatedly, an arbitrarily long S can exist even for a fixed finite input, so the verification procedure is not guaranteed to run in polynomial time in the size of the input. The lemma therefore does not establish coSP ∈ NP as written; a normalization argument or an explicit polynomial bound on the witness sequence is needed.
[Lemma 4.2 and §4.2.2] The claimed correspondence between valid subgraphs of the constructed supergraph Γ and reachable states of M requires the initial state G0 to satisfy the constraints encoded in C. If G0 already contains two edges that a create command declares mutually exclusive, then G0 itself is reachable but not a valid subgraph, so the induction base case in the proof of Lemma 4.2 fails. Without an explicit initial-state consistency assumption or a modified construction, the correctness proof of Algorithm 1 is incomplete for models whose initial states contain conflicting edges.

Minor objections (5)

[§1] The statement that "proving coSP∈NP is trivial" is misleading given the missing certificate-length bound in Lemma 3.4, and should be revised.
[Lemma 4.1] The notation μ(C) is used both for the set of maximal independent sets and for its cardinality; the running-time expression should write |μ(C)| explicitly.
[Lemma 4.1] The bound O(1.45^{n^2}) uses n for the number of vertices of Γ, while the preceding line uses n for the number of vertices and m for the number of edges; the exponent should be stated as |V|^2 for clarity.
[Algorithm 1] In line 4, it should be stated explicitly that the existence test is for a directed s-t path in G′, not merely an undirected path.
[§5] The example of three mutually exclusive attributes leading to a triangle in C is correct, but the text says the attributes are "pairwise" mutually exclusive; it would be clearer to state that a group of k mutually exclusive attributes forms a clique of size k, which for k=3 is a triangle.

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

The paper proves that safety analysis for NGAC access-control models is coNP-complete under mono-operational commands, so no polynomial-time checker can exist unless P=NP.

The reading

This paper tries to pin down the computational difficulty of checking whether an NGAC access-control policy can ever grant a new access. It defines the co-safety problem—does some command sequence create a new path from a user to a resource—and claims that for mono-operational commands under three mild assumptions, co-safety is NP-complete, hence safety is coNP-complete. The argument goes through a graph abstraction called directed acyclic constrained connectivity (DACC), which asks whether a directed acyclic graph has an s-t path in a subgraph that respects mutual-exclusion constraints on edges; the paper reduces 3-coloring to DACC and DACC to co-safety. If this is right, general NGAC safety cannot be checked in polynomial time unless P=NP. The paper also gives an exponential algorithm based on enumerating maximal independent sets and shows that mutually exclusive attributes, common in separation of duty, make its running time close to worst case.

What carries the argument

The central object is DACC: a directed acyclic graph $\Gamma$ with a constraint graph $C$ whose vertices are edges of $\Gamma$ and whose edges forbid pairs of $\Gamma$-edges from coexisting; a valid subgraph is one whose edge set is an independent set in $C$. The argument runs on the claimed bijection between valid subgraphs of $\Gamma$ and reachable states of the NGAC model, which turns command sequences into static path-finding. On the algorithmic side, the load-bearing mechanism is enumeration of maximal independent sets of $C$: every maximal valid subgraph is obtained this way, and the extremal bound $3^{n/3}<1.45^n$ on the number of maximal independent sets gives the worst-case runtime.

Extended reading notes

Core claim

The paper's central discovery, on its own terms, is Theorem 3.5: the co-safety problem for NGAC models is NP-complete in the mono-operational setting with assumptions 1–3, which makes the safety problem coNP-complete. The proof is a reduction chain from 3-coloring to DACC, and from DACC to co-safety by embedding the DAG inside the user-attribute subgraph of an NGAC state, with commands that add or remove edges according to the constraints. The paper further claims that reachable NGAC states correspond exactly to valid subgraphs of that DAG, so searching for an unsafe command sequence reduces to finding a path in a valid subgraph. If this correspondence holds, no polynomial-time safety-checking algorithm exists for general NGAC models unless P=NP.

Load-bearing premise

The whole reduction assumes that every edge of the embedded graph $\Gamma$ that can lie on an $s$-$t$ path has a command that can create it, but the construction only adds create commands for edges appearing in the constraint graph; edges outside the constraints have only destroy commands, so the claimed reachable-state correspondence is not established.

Editorial extensions

If this is right

If the main theorem holds, no polynomial-time algorithm can decide whether a general NGAC policy is safe under mono-operational commands, unless P=NP.
Any future safety checker must either restrict the model further or accept exponential worst-case time; the certificate for an unsafe answer is a user-resource-right triple plus a command sequence.
For NGAC instances whose constraint graph has polynomially many maximal independent sets, the paper's algorithm decides safety in polynomial time.
Mutually exclusive attribute groups, common in separation-of-duty policies, produce disjoint cliques in the constraint graph, putting realistic models near the worst case for the algorithm.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the missing create commands for constraint-free connector edges are added, the NP-completeness proof likely goes through; as written, the constructed model cannot produce the very $s$-$t$ path it relies on, so the reduction needs repair.
The same DACC abstraction could be applied to other attribute-based access-control languages whose commands guard edge creation, suggesting a general route from policy languages to constrained path-finding.
The near-worst-case behavior on disjoint cliques suggests that parameterizing by the number and size of mutually exclusive attribute groups, rather than by total graph size, may yield fixed-parameter tractable safety analysis.

Original abstract

We study the safety problem for the next-generation access control (NGAC) model. We show that under mild assumptions it is 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.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 2,872 input tokens.

What the abstract itself states, as probabilities: claims first 0.04 · states limitation 0.93 · human participants 0.03 · controlled comparison 0.14 · randomized assignment 0.01 · states quantitative result 0.42 · compares with prior results 0.80 · mentions code or data availability 0.03.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

We study the safety problem for the next-generation access control (NGAC) model. We show that under mild assumptions it is 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.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	We study the safety problem for the next-generation access control (NGAC) model.	contribution 0.60	0.86	0.05	asserted 0.76
s1	We show that under mild assumptions it is coNP-complete, and under further realistic assumptions we give an algorithm for the safety problem that significantly outperforms naive brute force search.	result 0.78	0.96	0.79	asserted 1.00
s2	We also show that real-world examples of mutually exclusive attributes lead to nearly worst-case behavior of our algorithm.	result 0.67	0.92	0.08	asserted 1.00

What kind of paper the classifier reports this is: theoretical result 0.92 · evidence from proof or derivation 0.99.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

Figures

**Figure 1.** Reduction from DACC to coSP. 4 ALGORITHM In this section, we will introduce an algorithm that solves the safety problem for the NGAC model significantly faster than naive bruteforce search. We will first give an algorithm to solve DACC, and then explain how we can transform a safety problem input to an input for DACC to use the algorithm. 4.1 Solving DACC Let (𝐺,𝐶, 𝑠, 𝑡) be an input to DACC. Since we are trying to find a path in a valid subgraph of 𝐺, it suffices to enumerate maximal valid subgraphs of 𝐺. This is because adding edges to a valid subgraph cannot destroy the path we a

Figures reproduced from arXiv:2505.06406 by the authors.

References

Works cited (29)

[1]

Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. 2025. More Asymmetry Yields Faster Matrix Multiplication. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Proceedings. Society for Industrial and Applied Mathematics, 2005–

View on Pith 2025
[2]

P.E. Ammann and R.S. Sandhu. 1991. Safety analysis for the extended schematic protection model. In Proceedings. 1991 IEEE Computer Society Symposium on Research in Security and Privacy . IEEE Comput. Soc. Press, Oakland, CA, USA, 87–97. isbn: 978-0-8186-2168-0. doi: 10.1109/RISP.1991.130777

View on Pith arXiv 1991
[3]

ANSI INCITS. 2020. Information Technology - Next Generation Access Control (NGAC). ANSI

View on Pith 2020
[4]

Matt Bishop. 2003. Computer Security: Art and Science . Addison-Wesley Profes- sional. isbn: 978-0-201-44099-7

View on Pith 2003
[5]

Timothy A. Budd. 1983. Safety in grammatical protection systems.International Journal of Computer & Information Sciences , 12, 6, 413–431. doi: 10.1007/BF009 77968

View on Pith doi:10.1007/bf009 1983
[6]

Erzhuo Chen, Vladislav Dubrovenski, and Dianxiang Xu. 2023. Coverage-Based Testing of Obligations in NGAC Systems. In Proceedings of the 28th ACM Sym- posium on Access Control Models and Technologies (SACMAT ’23). Association for Computing Machinery, New York, NY, USA, 169–179. doi: 10.1145/3589608 .3593832

View on Pith doi:10.1145/3589608 2023
[7]

Erzhuo Chen, Vladislav Dubrovenski, and Dianxiang Xu. 2021. Mutation Anal- ysis of NGAC Policies. In Proceedings of the 26th ACM Symposium on Access Control Models and Technologies. ACM, Virtual Event Spain, 71–82. isbn: 978-1- 4503-8365-3. doi: 10.1145/3450569.3463563

View on Pith arXiv 2021
[8]

Dorothy Elizabeth Robling Denning. 1982. Cryptography and Data Security . Addison-Wesley, Reading, Mass.isbn: 978-0-201-10150-8

View on Pith 1982
[9]

H.N. Gabow, S.N. Maheshwari, and L.J. Osterweil. 1976. On Two Problems in the Generation of Program Test Paths. IEEE Transactions on Software Engineering , SE-2, 3, 227–231. doi: 10.1109/TSE.1976.233819

View on Pith arXiv 1976
[10]

Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-completeness . A Series of Books in the Mathematical Sciences. W. H. Freeman, New York.isbn: 978-0-7167-1045-5

View on Pith 1979
[11]

Michael A. Harrison, Walter L. Ruzzo, and Jeffrey D. Ullman. 1976. Protection in operating systems. Commun. ACM, 19, 8, 461–471. doi: 10.1145/360303.360333

View on Pith arXiv 1976
[12]

A. K. Jones, R. J. Lipton, and L. Snyder. 1976. A Linear time algorithm for deciding security. In 17th Annual Symposium on Foundations of Computer Science (SFCS 1976). IEEE, Houston, TX, USA, 33–41. doi: 10.1109/SFCS.1976.1

View on Pith doi:10.1109/sfcs.1976.1 1976
[13]

Ninghui Li and Mahesh V. Tripunitara. 2006. Security analysis in role-based access control. ACM Transactions on Information and System Security , 9, 4, 391–420. doi: 10.1145/1187441.1187442

View on Pith arXiv 2006
[14]

Ninghui Li, Mahesh V. Tripunitara, and Ziad Bizri. 2007. On mutually exclusive roles and separation-of-duty. ACM Trans. Inf. Syst. Secur. , 10, 2, 5–es. doi: 10.1145/1237500.1237501

View on Pith arXiv 2007
[15]

R. J. Lipton and L. Snyder. 1977. A Linear Time Algorithm for Deciding Subject Security. Journal of the ACM, 24, 3, 455–464. doi: 10.1145/322017.322025

View on Pith arXiv 1977
[16]

Kazuhisa Makino and Takeaki Uno. 2004. New Algorithms for Enumerating All Maximal Cliques. In Algorithm Theory - SW AT 2004. Torben Hagerup and Jyrki Katajainen, (Eds.) Springer, Berlin, Heidelberg, 260–272. isbn: 978-3-540- 27810-8. doi: 10.1007/978-3-540-27810-8_23

View on Pith doi:10.1007/978-3-540-27810-8_23 2004
[17]

Raymond E Miller and David E Muller. 1960. A Problem of Maximum Con- sistent Subsets. Tech. rep. RC-240. IBM Research, JT Watson Research Center, Yorktown Heights, NY

View on Pith 1960
[18]

J. W. Moon and L. Moser. 1965. On cliques in graphs. Israel Journal of Mathe- matics, 3, 1, 23–28. doi: 10.1007/BF02760473

View on Pith doi:10.1007/bf02760473 1965
[19]

Rajeev Motwani, Rina Panigrahy, Vijay Saraswat, and Suresh Ventkatasubrama- nian. 2000. On the decidability of accessibility problems (extended abstract). In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Comput- ing. ACM, Portland Oregon USA, (May 2000), 306–315.isbn: 978-1-58113-184-0. doi: 10.1145/335305.335341

View on Pith arXiv 2000
[20]

Charles P. Pfleeger, Shari Lawrence Pfleeger, and Lizzie Coles-Kemp. 2024. Security in Computing. (Sixth edition ed.). Addison-Wesley, Boston Amsterdam London. isbn: 978-0-13-789121-4

View on Pith 2024
[21]

R.S. Sandhu and P. Samarati. 1994. Access control: principle and practice. IEEE Communications Magazine, 32, 9, 40–48. doi: 10.1109/35.312842

View on Pith doi:10.1109/35.312842 1994
[22]

Ravinderpal Singh Sandhu. 1992. Undecidability of safety for the schematic protection model with cyclic creates. Journal of Computer and System Sciences , 44, 1, 141–159. doi: 10.1016/0022-0000(92)90008-7

View on Pith doi:10.1016/0022-0000(92)90008-7 1992
[23]

J.A. Solworth and R.H. Sloan. 2004. A layered design of discretionary access controls with decidable safety properties. In IEEE Symposium on Security and Privacy, 2004. Proceedings. 2004 . IEEE, Berkeley, CA, USA, 56–67. isbn: 978-0- 7695-2136-7. doi: 10.1109/SECPRI.2004.1301315

View on Pith Pith review arXiv 2004
[24]

Masakazu Soshi. 2000. Safety Analysis of the Dynamic-Typed Access Matrix Model. In Computer Security - ESORICS 2000 . Frédéric Cuppens, Yves Deswarte, Dieter Gollmann, and Michael Waidner, (Eds.) Springer, Berlin, Heidelberg, 106–121. isbn: 978-3-540-45299-7. doi: 10.1007/10722599_7

View on Pith doi:10.1007/10722599_7 2000
[25]

Masakazu Soshi, Mamoru Maekawa, and Eiji Okamoto. 2004. The dynamic- typed access matrix model and decidability of the safety problem. IEICE Trans- actions on Fundamentals, E87-A, 1, 190–203

View on Pith 2004
[26]

Mahesh V. Tripunitara and Ninghui Li. 2013. The Foundational Work of Harrison- Ruzzo-Ullman Revisited. IEEE Transactions on Dependable and Secure Comput- ing, 10, 1, 28–39. doi: 10.1109/TDSC.2012.77

View on Pith doi:10.1109/tdsc.2012.77 2013
[27]

Vincent Vatter. 2011. Maximal Independent Sets and Separating Covers. The American Mathematical Monthly, 118, 5, 418. doi: 10.4169/amer.math.monthly .118.05.418

View on Pith doi:10.4169/amer.math.monthly 2011
[28]

David R. Wood. 2011. On the number of maximal independent sets in a graph. Discrete Mathematics & Theoretical Computer Science , Vol. 13 no. 3, Combina- torics, 543. doi: 10.46298/dmtcs.543

View on Pith doi:10.46298/dmtcs.543 2011
[2039]

doi: 10.1137/1.9781611978322.63

View on Pith doi:10.1137/1.9781611978322.63

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.

[1] [1]

Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. 2025. More Asymmetry Yields Faster Matrix Multiplication. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Proceedings. Society for Industrial and Applied Mathematics, 2005–

View on Pith 2025

[2] [2]

P.E. Ammann and R.S. Sandhu. 1991. Safety analysis for the extended schematic protection model. In Proceedings. 1991 IEEE Computer Society Symposium on Research in Security and Privacy . IEEE Comput. Soc. Press, Oakland, CA, USA, 87–97. isbn: 978-0-8186-2168-0. doi: 10.1109/RISP.1991.130777

View on Pith arXiv 1991

[3] [3]

ANSI INCITS. 2020. Information Technology - Next Generation Access Control (NGAC). ANSI

View on Pith 2020

[4] [4]

Matt Bishop. 2003. Computer Security: Art and Science . Addison-Wesley Profes- sional. isbn: 978-0-201-44099-7

View on Pith 2003

[5] [5]

Timothy A. Budd. 1983. Safety in grammatical protection systems.International Journal of Computer & Information Sciences , 12, 6, 413–431. doi: 10.1007/BF009 77968

View on Pith doi:10.1007/bf009 1983

[6] [6]

Erzhuo Chen, Vladislav Dubrovenski, and Dianxiang Xu. 2023. Coverage-Based Testing of Obligations in NGAC Systems. In Proceedings of the 28th ACM Sym- posium on Access Control Models and Technologies (SACMAT ’23). Association for Computing Machinery, New York, NY, USA, 169–179. doi: 10.1145/3589608 .3593832

View on Pith doi:10.1145/3589608 2023

[7] [7]

Erzhuo Chen, Vladislav Dubrovenski, and Dianxiang Xu. 2021. Mutation Anal- ysis of NGAC Policies. In Proceedings of the 26th ACM Symposium on Access Control Models and Technologies. ACM, Virtual Event Spain, 71–82. isbn: 978-1- 4503-8365-3. doi: 10.1145/3450569.3463563

View on Pith arXiv 2021

[8] [8]

Dorothy Elizabeth Robling Denning. 1982. Cryptography and Data Security . Addison-Wesley, Reading, Mass.isbn: 978-0-201-10150-8

View on Pith 1982

[9] [9]

H.N. Gabow, S.N. Maheshwari, and L.J. Osterweil. 1976. On Two Problems in the Generation of Program Test Paths. IEEE Transactions on Software Engineering , SE-2, 3, 227–231. doi: 10.1109/TSE.1976.233819

View on Pith arXiv 1976

[10] [10]

Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-completeness . A Series of Books in the Mathematical Sciences. W. H. Freeman, New York.isbn: 978-0-7167-1045-5

View on Pith 1979

[11] [11]

Michael A. Harrison, Walter L. Ruzzo, and Jeffrey D. Ullman. 1976. Protection in operating systems. Commun. ACM, 19, 8, 461–471. doi: 10.1145/360303.360333

View on Pith arXiv 1976

[12] [12]

A. K. Jones, R. J. Lipton, and L. Snyder. 1976. A Linear time algorithm for deciding security. In 17th Annual Symposium on Foundations of Computer Science (SFCS 1976). IEEE, Houston, TX, USA, 33–41. doi: 10.1109/SFCS.1976.1

View on Pith doi:10.1109/sfcs.1976.1 1976

[13] [13]

Ninghui Li and Mahesh V. Tripunitara. 2006. Security analysis in role-based access control. ACM Transactions on Information and System Security , 9, 4, 391–420. doi: 10.1145/1187441.1187442

View on Pith arXiv 2006

[14] [14]

Ninghui Li, Mahesh V. Tripunitara, and Ziad Bizri. 2007. On mutually exclusive roles and separation-of-duty. ACM Trans. Inf. Syst. Secur. , 10, 2, 5–es. doi: 10.1145/1237500.1237501

View on Pith arXiv 2007

[15] [15]

R. J. Lipton and L. Snyder. 1977. A Linear Time Algorithm for Deciding Subject Security. Journal of the ACM, 24, 3, 455–464. doi: 10.1145/322017.322025

View on Pith arXiv 1977

[16] [16]

Kazuhisa Makino and Takeaki Uno. 2004. New Algorithms for Enumerating All Maximal Cliques. In Algorithm Theory - SW AT 2004. Torben Hagerup and Jyrki Katajainen, (Eds.) Springer, Berlin, Heidelberg, 260–272. isbn: 978-3-540- 27810-8. doi: 10.1007/978-3-540-27810-8_23

View on Pith doi:10.1007/978-3-540-27810-8_23 2004

[17] [17]

Raymond E Miller and David E Muller. 1960. A Problem of Maximum Con- sistent Subsets. Tech. rep. RC-240. IBM Research, JT Watson Research Center, Yorktown Heights, NY

View on Pith 1960

[18] [18]

J. W. Moon and L. Moser. 1965. On cliques in graphs. Israel Journal of Mathe- matics, 3, 1, 23–28. doi: 10.1007/BF02760473

View on Pith doi:10.1007/bf02760473 1965

[19] [19]

Rajeev Motwani, Rina Panigrahy, Vijay Saraswat, and Suresh Ventkatasubrama- nian. 2000. On the decidability of accessibility problems (extended abstract). In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Comput- ing. ACM, Portland Oregon USA, (May 2000), 306–315.isbn: 978-1-58113-184-0. doi: 10.1145/335305.335341

View on Pith arXiv 2000

[20] [20]

Charles P. Pfleeger, Shari Lawrence Pfleeger, and Lizzie Coles-Kemp. 2024. Security in Computing. (Sixth edition ed.). Addison-Wesley, Boston Amsterdam London. isbn: 978-0-13-789121-4

View on Pith 2024

[21] [21]

R.S. Sandhu and P. Samarati. 1994. Access control: principle and practice. IEEE Communications Magazine, 32, 9, 40–48. doi: 10.1109/35.312842

View on Pith doi:10.1109/35.312842 1994

[22] [22]

Ravinderpal Singh Sandhu. 1992. Undecidability of safety for the schematic protection model with cyclic creates. Journal of Computer and System Sciences , 44, 1, 141–159. doi: 10.1016/0022-0000(92)90008-7

View on Pith doi:10.1016/0022-0000(92)90008-7 1992

[23] [23]

J.A. Solworth and R.H. Sloan. 2004. A layered design of discretionary access controls with decidable safety properties. In IEEE Symposium on Security and Privacy, 2004. Proceedings. 2004 . IEEE, Berkeley, CA, USA, 56–67. isbn: 978-0- 7695-2136-7. doi: 10.1109/SECPRI.2004.1301315

View on Pith Pith review arXiv 2004

[24] [24]

Masakazu Soshi. 2000. Safety Analysis of the Dynamic-Typed Access Matrix Model. In Computer Security - ESORICS 2000 . Frédéric Cuppens, Yves Deswarte, Dieter Gollmann, and Michael Waidner, (Eds.) Springer, Berlin, Heidelberg, 106–121. isbn: 978-3-540-45299-7. doi: 10.1007/10722599_7

View on Pith doi:10.1007/10722599_7 2000

[25] [25]

Masakazu Soshi, Mamoru Maekawa, and Eiji Okamoto. 2004. The dynamic- typed access matrix model and decidability of the safety problem. IEICE Trans- actions on Fundamentals, E87-A, 1, 190–203

View on Pith 2004

[26] [26]

Mahesh V. Tripunitara and Ninghui Li. 2013. The Foundational Work of Harrison- Ruzzo-Ullman Revisited. IEEE Transactions on Dependable and Secure Comput- ing, 10, 1, 28–39. doi: 10.1109/TDSC.2012.77

View on Pith doi:10.1109/tdsc.2012.77 2013

[27] [27]

Vincent Vatter. 2011. Maximal Independent Sets and Separating Covers. The American Mathematical Monthly, 118, 5, 418. doi: 10.4169/amer.math.monthly .118.05.418

View on Pith doi:10.4169/amer.math.monthly 2011

[28] [28]

David R. Wood. 2011. On the number of maximal independent sets in a graph. Discrete Mathematics & Theoretical Computer Science , Vol. 13 no. 3, Combina- torics, 543. doi: 10.46298/dmtcs.543

View on Pith doi:10.46298/dmtcs.543 2011

[29] [2039]

doi: 10.1137/1.9781611978322.63

View on Pith doi:10.1137/1.9781611978322.63