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

Abstract

<title>Abstract</title> 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.

Affiliated Institutions

• ITMO University RU

Related Publications