אִם יִרְצֶה הַשֵּׁם
"delete" and "destroy" operations are not edge cases. They are load-bearing elements of any real security architecture.
Standard security models, attack graphs, and compliance frameworks have quietly inherited a flawed assumption from a 1976 proof: that privileges, once granted, are never revoked. This monotonicity assumption produces safety conclusions that are demonstrably wrong. Fixing it is not a theoretical exercise. It changes how we build attack models, how we configure cloud IAM, and how we audit defense contractors.
1. The Monotonicity Flaw in HRU
In 1976, Harrison, Ruzzo, and Ullman (HRU) introduced the access matrix model, the foundation of formal access control analysis. Their key simplification: treat the system as monotonic. Once a right appears in the matrix, it stays. No delete, no destroy.
This made the safety problem tractable for a specific subclass of systems. It also baked a false assumption into decades of downstream work.
Tripunitara and Li (2013) found two errors in the original HRU proof. The first, and more consequential: HRU assumed mono-operational systems are monotonic for safety analysis. They are not. A system can transition from a secure state to an insecure one through a sequence that includes revoking and re-granting privileges, a path invisible to any analysis that ignores delete and destroy operations. Under the monotonicity assumption, this system would be classified "safe." It is not.
The distinction matters because it is not just a corner case. Any system where accounts are created, disabled, re-enabled, or reassigned (which is every production system) operates in the non-monotonic space that HRU's proof assumed away.
2. Attack Graphs Inherit the Problem
The monotonicity assumption did not stay in access control theory. It migrated into attack graph research.
Ammann, Wijesekera, and Kaushik (2002) introduced the monotonicity assumption explicitly into scalable attack graph generation. Their key insight was practical: if you assume an attacker never loses a capability once gained, you can reduce the computational complexity of graph generation from exponential to polynomial. The entire MulVAL lineage (Ou et al. 2006) and TVA tool family (Jajodia et al. 2005) inherited this assumption.
The cost: these graphs model privilege escalation but cannot represent privilege revocation, vulnerability patching, or system remediation. An attacker who loses access because a vulnerability was patched still appears to hold that access in the graph. The defender's actions are invisible.
For red team exercises and point-in-time vulnerability scans, this is acceptable. For modeling real-world defense over time, where patches ship, accounts get disabled, and firewall rules change, it produces attack graphs that overstate attacker capability and understate defender response.
3. SolarWinds: What Happens When You Don't Destroy
The 2020 SolarWinds compromise demonstrates what non-monotonic failure looks like in practice.
After gaining initial access through the SUNBURST backdoor in Orion Platform updates, the SVR operators created new accounts and established persistence mechanisms across compromised networks. CISA Emergency Directive 21-01 and Activity Alert AA20-352A both identified the removal of threat-actor-created accounts and persistence mechanisms as a primary remediation requirement. The attackers also abused SAML tokens to forge authentication credentials, creating what amounted to permanent access that survived credential rotation on the original compromised accounts.
The monotonicity problem here is concrete: organizations that treated access as monotonic (accounts exist until someone manually reviews them, permissions accumulate, service accounts persist indefinitely) gave the attackers exactly the environment they needed. The remediation guidance from CISA was explicitly non-monotonic: identify and destroy unauthorized accounts, revoke and rotate all credentials, rebuild compromised hosts from trusted sources.
Every step of the SolarWinds response was a delete or destroy operation. The organizations that lacked the tooling, processes, or authority to execute those operations stayed compromised longer.
4. Cloud IAM: Scale Makes It Worse
Amazon S3 bucket misconfigurations have caused enough data breaches to fill their own incident database. The root cause is not stupidity. It is the interaction of scale, complexity, and the assumption that permissions only flow one direction.
AWS addressed this with Zelkova, an automated reasoning engine built on SMT solvers that powers IAM Access Analyzer. Zelkova encodes IAM policy semantics into formal logic and checks properties exhaustively. It does not guess. It processes over a billion SMT queries daily (Backes et al. 2018, extended in the CAV 2022 paper by the same team). When Access Analyzer flags a bucket as publicly accessible, it has mathematically proved that at least one public request path exists.
The non-monotonic dimension: Zelkova can detect when a policy change removes access that was previously granted. This is precisely the "delete" operation that monotonic analysis cannot represent. Without it, you could tighten a bucket policy and have no formal assurance that the tightening actually worked.
5. CMMC 2.0: Compliance Catches Up
The Cybersecurity Maturity Model Certification framework for defense contractors has evolved to address non-monotonic access control.
CMMC 2.0 aligns with NIST SP 800-171 and organizes 110 controls across 14 domains. The access control domain (AC) includes 22 practices. Two are directly relevant:
AC.L2-3.1.1 (Authorized Access Control) requires limiting system access to authorized users, processes, and devices. The assessment guide specifies that this includes managing accounts across their full lifecycle: creation, modification, disabling, and removal. The "removal" requirement is an explicit destroy operation.
AC.L2-3.1.2 (Transaction and Function Control) limits what authorized users can do once they have access. This is not just about granting permissions. The control requires that permissions can be scoped, modified, and revoked as job functions change.
The earlier CMMC 1.0 (2020) mapped to a different control numbering scheme and lacked the NIST 800-171 alignment that makes these lifecycle requirements explicit. The shift to 2.0 reflects a growing recognition that access control is not a one-time gate. It is a continuous process of granting, modifying, and revoking.
The October 2024 CyberSheath report on the Defense Industrial Base illustrates how far practice lags behind policy. In their survey, 76% of DIB contractors believed they were CMMC-compliant, despite an average SPRS score of -12 out of 110. (Note: CyberSheath is a compliance vendor with commercial interest in the result, and this is survey data, not an audit. The directional finding, that self-assessed compliance far exceeds measured compliance, is consistent with DCMA DIBCAC audit results but should be read with that caveat.)
The gap between perceived and actual compliance maps directly to the monotonicity problem. Organizations that only build access (create accounts, grant permissions, onboard systems) without equally rigorous processes for destroying access (remove accounts, revoke permissions, decommission systems) will accumulate security debt that no self-assessment catches.
6. The Structural Argument
The thread connecting HRU, attack graphs, SolarWinds, cloud IAM, and CMMC is this: security is not a monotonically increasing property. Systems do not only get more permissive. They must also get less permissive. Any formal model, analysis tool, or compliance framework that cannot represent the removal of access is missing half the picture.
References
[1] Harrison, M. A., Ruzzo, W. L., & Ullman, J. D. (1976). Protection in operating systems. Communications of the ACM, 19(8), 461-471. https://doi.org/10.1145/360303.360333
[2] Tripunitara, M. V., & Li, N. (2013). The foundational work of Harrison-Ruzzo-Ullman revisited. IEEE Transactions on Dependable and Secure Computing, 10(1), 28-39. https://doi.org/10.1109/TDSC.2012.77
[3] Ammann, P., Wijesekera, D., & Kaushik, S. (2002). Scalable, graph-based network vulnerability analysis. Proceedings of the 9th ACM Conference on Computer and Communications Security, 217-224. https://doi.org/10.1145/586110.586140
[4] Backes, J., Bolignano, P., Cook, B., et al. (2018). Semantic-based automated reasoning for AWS access policies using SMT. Proceedings of the 18th International Conference on Formal Methods in Computer-Aided Design (FMCAD), 1-9. https://doi.org/10.23919/FMCAD.2018.8602994
[5] CISA. (2021). Activity Alert AA20-352A: Advanced Persistent Threat Compromise of Government Agencies, Critical Infrastructure, and Private Sector Organizations. https://www.cisa.gov/news-events/cybersecurity-advisories/aa20-352a
[6] CISA. (2021). Emergency Directive 21-01: Mitigate SolarWinds Orion Code Compromise. https://www.cisa.gov/news-events/directives/ed-21-01-mitigate-solarwinds-orion-code-compromise-closed
[7] DoD CIO. (2024). CMMC Assessment Guide, Level 2, Version 2.13. https://dodcio.defense.gov/CMMC/
[8] JPL Institutional Coding Standard for the C Programming Language. (2009). https://web.archive.org/web/20190219155254/http://lars-lab.jpl.nasa.gov/JPL_Coding_Standard_C.pdf
[9] CyberSheath. (2024). Cybersecurity Report 2024. https://cybersheath.com/report-2024/