Deny-monotone composition of hierarchical access control policies in distributed systems: a formal algebraic approach

Deny-monotone composition of hierarchical access control policies in distributed systems: a formal algebraic approach | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article Deny-monotone composition of hierarchical access control policies in distributed systems: a formal algebraic approach Mahamdou Sidibe This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-8290081/v1 This work is licensed under a CC BY 4.0 License Status: Posted Version 1 posted You are reading this latest preprint version Abstract Modern distributed systems built from microservices, multi-cloud deployments and edge nodes rely on fine-grained access control policies that combine attribute-based access control (ABAC) [1] with the principles of Zero Trust Architecture (ZTA) [2]. In practice, access control decisions are made by multiple policy decision points (PDPs) and policy enforcement points (PEPs) deployed across regions and administrative domains. Standard policy combining algorithms such as permit-overrides and firstapplicable in XACML 3.0 [3] are defined for flat collections of policies and do not guarantee monotonicity across hierarchical levels, nor robustness under asynchronous replication without global coordination. Building on the formal model developed in the author’s dissertation on hierarchical access control in distributed storage and processing systems [4], this paper introduces a formal algebraic framework for deny-monotone composition of hierarchical access control policies. We first refine the decision domain D = {na, permit, deny} with a strictness order na ⪯ permit ⪯ deny and define a conflict-resolution operator ⊗ (deny-overrides) as max⪯, obtaining a commutative, associative, idempotent and monotone operation. On top of this decision algebra we define a policy algebra P built from atomic policies Permit[φ] and Deny[φ] and boolean connectives, with a disjunctive normal form (DNF) representation suitable for complexity analysis. For a partially ordered set of levels (L,≤) we define an inter-level aggregation operatorMthat folds per-level decisions along the set of ancestors Anc(ℓ) of any level ℓ. We prove that M is well defined (independent of the choice of linear extension of Anc(ℓ)), and establish the main deny-monotonicity theorem: any pointwise strengthening of component policies can only make the aggregated decision stricter, and the presence of a single deny at any ancestor level absorbs the result. We also provide a formal counterexample showing that a hierarchical variant of permit-overrides violates deny-monotonicity and may introduce privilege escalation. We present an algorithm AGGREGATE(F, ℓ, q) for computing M(F, ℓ)(q) with short-circuiting on deny and analyse its worst-case and average-case complexity for policies in DNF. The engineering part combines an M/M/1 queueing model for PDP latency [5] with real-world inter-region latency data from AWS Network Manager and public measurements of AWS region distances [6, 7], embedded in the manuscript as CSV and plotted with pgfplots. This allows us to quantify the impact of deny-absorption on the p95 end-to-end latency of PDP/PEP chains. We discuss practical implications for Zero Trust architectures [2], connections with CRDT-based replication of decision structures [8], and outline extensions towards fixed-point semantics in the presence of priority cycles. Theoretical Computer Science Algebra Information Theory hierarchical access control deny-overrides attribute-based access control (ABAC) Zero Trust Architecture CRDT distributed systems formal methods algorithmic complexity Full Text Additional Declarations The authors declare no competing interests. Cite Share Download PDF Status: Posted Version 1 posted You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-8290081","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":555966782,"identity":"0e34949a-d57c-435a-bd73-8f8a4015602b","order_by":0,"name":"Mahamdou Sidibe","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAABLElEQVRIie2PMWuDQBiGTw50OTMnpMS/oARSpJT+lYhQJ8HRoUggYBchawP5EVcEoVMNH7RDD1yFW9o9AUOXQCH0xBQKmtJuHe4Z7o7jffi+FyGJ5D+CkQn1bdYHQWgkflBfvM/U3yrjL4WcVEQYf1ecGToqp/LGLb6HIMyMc+3FqTYhePRZX5e7OCK9vpujfZi1RoAawB3j1kPip4MVA59Cz7WXMRC1fz1VEsbbWxET9JgrNPfpUI/Bz4BMhnqWE5UwEytxSzHmtXLgV7TYph9C8SaNEgmlqLoUBLUy4w4t/ayeMj0qmKhagrqUpssTd2m5zewV86xHIGN7eRBdtNhcd3QxFpC+Bzf8khZ+Wm7CC2OwYFZZsWhkzPHb6z5sL/Yz+R/zEolEImn4BAl9dhjemj0PAAAAAElFTkSuQmCC","orcid":"https://orcid.org/0000-0003-0456-4148","institution":"ITMO University: Nacional'nyj issledovatel'skij universitet ITMO","correspondingAuthor":true,"prefix":"","firstName":"Mahamdou","middleName":"","lastName":"Sidibe","suffix":""}],"badges":[],"createdAt":"2025-12-05 18:04:55","currentVersionCode":1,"declarations":{"humanSubjects":false,"vertebrateSubjects":false,"conflictsOfInterestStatement":false,"humanSubjectEthicalGuidelines":false,"humanSubjectConsent":false,"humanSubjectClinicalTrial":false,"humanSubjectCaseReport":false,"vertebrateSubjectEthicalGuidelines":false},"doi":"10.21203/rs.3.rs-8290081/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-8290081/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":98420878,"identity":"cba23655-9308-4078-9a26-b15bdb646e98","added_by":"auto","created_at":"2025-12-17 16:17:07","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":336930,"visible":true,"origin":"","legend":"","description":"","filename":"Denymonotone.pdf","url":"https://assets-eu.researchsquare.com/files/rs-8290081/v1_covered_5ebfa2b4-3e9c-4cbb-ad6e-824d0b877a45.pdf"}],"financialInterests":"The authors declare no competing interests.","formattedTitle":"\u003cp\u003eDeny-monotone composition of hierarchical access control policies in distributed systems: a formal algebraic approach\u003c/p\u003e","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":true,"hideJournal":true,"highlight":"","institution":"ITMO University","isAcceptedByJournal":false,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":true,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true},"keywords":"hierarchical access control, deny-overrides, attribute-based access control (ABAC), Zero Trust Architecture, CRDT, distributed systems, formal methods, algorithmic complexity","lastPublishedDoi":"10.21203/rs.3.rs-8290081/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-8290081/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003eModern distributed systems built from microservices, multi-cloud deployments and\u003c/p\u003e\n\u003cp\u003eedge nodes rely on fine-grained access control policies that combine attribute-based\u003c/p\u003e\n\u003cp\u003eaccess control (ABAC) [1] with the principles of Zero Trust Architecture (ZTA) [2]. In\u003c/p\u003e\n\u003cp\u003epractice, access control decisions are made by multiple policy decision points (PDPs)\u003c/p\u003e\n\u003cp\u003eand policy enforcement points (PEPs) deployed across regions and administrative\u003c/p\u003e\n\u003cp\u003edomains. Standard policy combining algorithms such as permit-overrides and firstapplicable\u003c/p\u003e\n\u003cp\u003ein XACML 3.0 [3] are defined for flat collections of policies and do not\u003c/p\u003e\n\u003cp\u003eguarantee monotonicity across hierarchical levels, nor robustness under asynchronous\u003c/p\u003e\n\u003cp\u003ereplication without global coordination.\u003c/p\u003e\n\u003cp\u003eBuilding on the formal model developed in the author’s dissertation on hierarchical\u003c/p\u003e\n\u003cp\u003eaccess control in distributed storage and processing systems [4], this paper introduces\u003c/p\u003e\n\u003cp\u003ea formal algebraic framework for deny-monotone composition of hierarchical access\u003c/p\u003e\n\u003cp\u003econtrol policies. We first refine the decision domain D = {na, permit, deny} with\u003c/p\u003e\n\u003cp\u003ea strictness order na ⪯ permit ⪯ deny and define a conflict-resolution operator ⊗\u003c/p\u003e\n\u003cp\u003e(deny-overrides) as max⪯, obtaining a commutative, associative, idempotent and\u003c/p\u003e\n\u003cp\u003emonotone operation. On top of this decision algebra we define a policy algebra P\u003c/p\u003e\n\u003cp\u003ebuilt from atomic policies Permit[φ] and Deny[φ] and boolean connectives, with a\u003c/p\u003e\n\u003cp\u003edisjunctive normal form (DNF) representation suitable for complexity analysis.\u003c/p\u003e\n\u003cp\u003eFor a partially ordered set of levels (L,≤) we define an inter-level aggregation\u003c/p\u003e\n\u003cp\u003eoperatorMthat folds per-level decisions along the set of ancestors Anc(ℓ) of any level\u003c/p\u003e\n\u003cp\u003eℓ. We prove that M is well defined (independent of the choice of linear extension of\u003c/p\u003e\n\u003cp\u003eAnc(ℓ)), and establish the main deny-monotonicity theorem: any pointwise strengthening\u003c/p\u003e\n\u003cp\u003eof component policies can only make the aggregated decision stricter, and the\u003c/p\u003e\n\u003cp\u003epresence of a single deny at any ancestor level absorbs the result. We also provide\u003c/p\u003e\n\u003cp\u003ea formal counterexample showing that a hierarchical variant of permit-overrides\u003c/p\u003e\n\u003cp\u003eviolates deny-monotonicity and may introduce privilege escalation.\u003c/p\u003e\n\u003cp\u003eWe present an algorithm AGGREGATE(F, ℓ, q) for computing M(F, ℓ)(q) with\u003c/p\u003e\n\u003cp\u003eshort-circuiting on deny and analyse its worst-case and average-case complexity\u003c/p\u003e\n\u003cp\u003efor policies in DNF. The engineering part combines an M/M/1 queueing model\u003c/p\u003e\n\u003cp\u003efor PDP latency [5] with real-world inter-region latency data from AWS Network\u003c/p\u003e\n\u003cp\u003eManager and public measurements of AWS region distances [6, 7], embedded in\u003c/p\u003e\n\u003cp\u003ethe manuscript as CSV and plotted with pgfplots. This allows us to quantify\u003c/p\u003e\n\u003cp\u003ethe impact of deny-absorption on the p95 end-to-end latency of PDP/PEP chains.\u003c/p\u003e\n\u003cp\u003eWe discuss practical implications for Zero Trust architectures [2], connections with\u003c/p\u003e\n\u003cp\u003eCRDT-based replication of decision structures [8], and outline extensions towards\u003c/p\u003e\n\u003cp\u003efixed-point semantics in the presence of priority cycles.\u003c/p\u003e","manuscriptTitle":"Deny-monotone composition of hierarchical access control policies in distributed systems: a formal algebraic approach","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2025-12-09 04:11:54","doi":"10.21203/rs.3.rs-8290081/v1","editorialEvents":[{"type":"communityComments","content":0}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"e5fcdc2d-d037-4d63-a1a5-358cb0f3704d","owner":[],"postedDate":"December 9th, 2025","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[{"id":59316624,"name":"Theoretical Computer Science"},{"id":59316625,"name":"Algebra"},{"id":59316626,"name":"Information Theory"}],"tags":[],"updatedAt":"2025-12-09T04:11:54+00:00","versionOfRecord":[],"versionCreatedAt":"2025-12-09 04:11:54","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-8290081","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-8290081","identity":"rs-8290081","version":["v1"]},"buildId":"8U1c8b4HqxoKbykW_rLl7","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}