EXT REE : T OWARDS S UPPORTING E XPLAINABILITY IN ATTRIBUTE - BASED ACCESS C ONTROL
arXiv:2604.12850v1 [cs.CR] 14 Apr 2026
Shanampudi Pranaya Chowdary Indian Institute of Technology Kharagpur, India [email protected]
Shamik Sural Indian Institute of Technology Kharagpur, India [email protected]
A BSTRACT With increasing emphasis on transparency in digital governance, users expect more than silence when their access requests are denied by a system. However, authorization methods are notorious for their inability to provide any form of meaningful feedback under such situations. This paper shows a direction towards how the problem of explainability can be mitigated in the context of Attribute-based Access Control (ABAC), arguably the most researched topic in access control in recent years. We introduce EXTree, which represents ABAC policies optimized for both fast evaluation (Efficiency) and human-centric feedback (eXplainability) in the form of a Tree. Two strategic dimensions are investigated, namely, Feedback Evaluation Strategies — how to craft actionable explanations when access is denied, and Tree Construction Strategies — how the policy trees should be structured for efficient yet interpretable decisions. Through extensive experiments, we compare entropy-based, changeability-based, and randomly generated trees across multiple configurations. Our results demonstrate that EXTree, built for efficiency and interpretability, can bridge the gap between complex authorization logic and human understanding. Keywords Attribute-based Access Control (ABAC), Explainability, EXTree, Policy Enforcement
1
Introduction
Access control research has evolved significantly over the years. While traditional models like Role-based Access Control (RBAC) [19] work well with stable organizational hierarchies, modern computing environments require more flexible approaches. This led to the emergence of Attribute-based Access Control (ABAC) [7], which evaluates access rights using fine-grained user attributes, resource properties, and environmental conditions. Practical implementations of ABAC, however, face the critical challenge of providing meaningful feedback when access is denied. In organizational settings, users frequently ask questions like ”Why was I denied access?” and ”What do I need to change?” [8]. The need is for an automated, intelligent response to such queries without needing human intervention. The challenge lies not simply in explaining a denial, but in efficiently identifying feasible corrective actions that users can realistically perform. Naı̈vely enumerating possible policy changes is computationally expensive and often produces impractical suggestions. This brings about the need for feedback mechanisms that balance actionability with system performance. Additionally, feedback should avoid revealing sensitive policy details. Based on these challenges, there are three fundamental research questions in ABAC explainability as enumerated below: (i) RQ1: What constitutes actionable feedback for denied ABAC requests (ii) RQ2: How to generate meaningful explanations that respect practical attribute constraints (iii) RQ3: How to provide feedback efficiently without compromising ABAC system performance To address these questions, we propose EXTree (Efficient and eXplainable Tree), which is an explainability-aware architecture that integrates attribute changeability with efficient decision making. The key innovation lies in organizing policies around attribute changeability costs, such that the system can identify feasible transitions as low-cost paths
EXTree: Towards Supporting Explainability in Attribute-based Access Control
from deny states to allow states. This approach facilitates structured, actionable feedback generation. We evaluate our framework using synthetic as well as realistic ABAC datasets, comparing various tree-construction strategies and feedback mechanisms. Our results demonstrate that change-aware tree construction significantly improves the quality of explanations without affecting computational efficiency, particularly in large-scale deployments where traditional approaches tend to become intractable. The rest of the paper is organized as follows. In Section 2, we introduce some of the relevant background material. The structure and design of EXTree is presented in Section 3. Details of all the experiments and their results are discussed in Section 4. We review related work in Section 5 and finally conclude in Section 6.
2
Preliminaries
In this section, we introduce some of the background material relevant to our work. 2.1
ABAC Definition and Notations
The development of access control systems has evolved through several paradigms. Discretionary Access Control (DAC) introduced the concept of ownership-based permissions, where resource owners determine access rights [18]. RBAC [19] groups permissions into roles, improving scalability and reducing administrative overhead in organizational settings. As systems became more dynamic, Attribute-based Access Control (ABAC) emerged as a more flexible model [7]. Unlike the static role assignments used in RBAC, ABAC makes access decisions based on a rich set of attributes for users, resources, and the surrounding environment. ABAC is comprised of the following fundamental components: • U : A finite set of users in the system • O: A finite set of protected objects or resources • E: A set of environmental conditions • OP : The set of allowable operations on objects Each entity category is characterized by its attribute sets: U A = {au1 , au2 , . . . , aun }, EA = {ae1 , ae2 , . . . , aep }
OA = {ao1 , ao2 , . . . , aom },
For each attribute axi where x ∈ {u, o, e}, we define: x x x • A value domain Vix = {vi1 , vi2 , . . . , vik } x x • A mapping function fi : X → Vi ∪ {#} where X ∈ {U, O, E} • The special value # denotes undefined or unknown attributes
An access control policy P = {r1 , r2 , . . . , rl } consists of rules, where each rule ri is formally represented as: ri = ⟨cui , coi , cei , opi ⟩ Here, cxi represents conjunctions of predicates over the respective attribute sets, and opi ∈ OP specifies the permitted operation. Each predicate is of the form axj rel v, where rel ∈ {=, ̸=, <, >, ≤, ≥} and v ∈ Vjx ∪ {#, ∗}, with “∗” denoting a wildcard that matches any value. An access request q is a mapping from a subset of attributes in U A ∪ OA ∪ EA to concrete values in their domains. Evaluation of q against P determines which rule(s) ri ∈ P are satisfied. To ground the above notation, consider a minimal ABAC policy with user attributes U A = {role, department, clearance, training over}. For this policy, access is permitted under the following rules: • r1 = ⟨role = admin, ∗, ∗, op⟩ • r2 = ⟨role = intern ∧ clearance = medium, ∗, ∗, op⟩ • r3 = ⟨role = manager ∧ clearance = low ∧ department = HR, ∗, ∗, op⟩ Consider the access request q = (role = manager ∧ clearance = medium ∧ department = HR, ∗, op), which is denied under this policy. 2
EXTree: Towards Supporting Explainability in Attribute-based Access Control
2.2
Policy Evaluation Architectures
The industry standard XACML provides a widely used framework for implementing ABAC policies [16]. It defines core components such as the Policy Decision Point (PDP) and Policy Enforcement Point (PEP), which together handle policy evaluation and enforcement. In practice, however, the performance of the PDP can become a bottleneck as the number and complexity of policy rules increase [3]. Several formal approaches have been explored to improve policy analysis and verification. For example, Ordered Binary Decision Diagrams (OBDDs) provide compact and canonical representations that support efficient policy analysis [4]. Answer Set Programming (ASP) has also been used to reason about properties such as policy completeness and conflict detection [15]. While these approaches improve correctness and verifiability, they often introduce additional computational overhead. The PolTree framework [11] takes a different approach by organizing policies in a hierarchical structure. Instead of evaluating policies sequentially, PolTree represents them as a decision tree where internal nodes correspond to attributes and leaf nodes represent access decisions. This structure allows requests to be evaluated more efficiently while also making it easier to trace how a particular decision was reached. Experimental results demonstrate significant performance improvements over conventional methods, particularly in systems with a large number of rules.
3
Structure and Design of EXTree
We argue that a sequential representation and enforcement of ABAC rules as described in Section 2.1, are not amenable to efficient evaluation or towards meaningful and graded explainability. Hence, hierarchical structuring of rules is imperative so that some form of ordering can be imposed on the list of attributes. Towards this, we propose EXTree that attempts to capture the required features in a unified manner. This section describes the structure of EXTree and how it is built, along with the relevant design considerations. It also presents the algorithm for supporting explainability in EXTree. 3.1
EXTree Representation
An EXTree T is an n-ary hierarchical structure for evaluation of ABAC policies as shown in Figure 1. This structural organization has some similarity with the PolTree framework [11], which also arranges ABAC policies as decision trees over attributes for efficient evaluation. EXTree retains this core representation but extends it with explainabilityoriented metadata and traversal mechanisms, as described in the following sections. The structure of EXTree satisfies the following criteria. • Each non-leaf node is labeled with an attribute a ∈ U A ∪ OA ∪ EA. • Each outgoing edge from a node represents a possible value or predicate outcome for that attribute. • Each leaf node stores the subset of policy rules from P consistent with the predicates along its root–leaf path. Evaluation of an access request q proceeds top–down starting from the root. Each node’s attribute is compared against the corresponding value in q with traversal continuing along the matching edge. If no matching edge or wildcard exists, the search halts and the decision defaults to deny, reflecting that no rule in P satisfies all constraints along the path. allow(op), if a path to an allow leaf exists; Decision(q) = (1) deny, otherwise. As the system models only allow policies, each leaf corresponds to one or more permissible operations. When an access request q reaches a leaf, the operations stored there define the actions granted to the requester. Denial arises implicitly from the absence of a valid path from the root to a leaf level node. If wildcard branches are present, evaluation may backtrack when the exact-value path fails, exploring more general branches. This retracing mechanism ensures that specific rules take precedence, while generalized ones apply only when no exact match is found. Retracing introduces negligible overhead since wildcard branches are rare, keeping search time approximately linear in the number of attributes. At each internal node, exactly one attribute is tested, and outgoing branches correspond to mutually exclusive values of that attribute (apart from optional wildcards). Each rule is placed only in subtrees consistent with its predicates. Therefore, a request that satisfies a rule will necessarily traverse a path that allows that rule. 3
EXTree: Towards Supporting Explainability in Attribute-based Access Control
Figure 1: Hierarchical representation of the example ABAC policy introduced in Section 2.1. Internal nodes correspond to attribute tests and leaf nodes represent allow decisions. The highlighted (in bold) path illustrates the evaluation trace for the denied request and, the deny node is marked in red.
Figure 1 shows the hierarchical representation of the policy introduced in Section 2.1. Internal nodes correspond to attribute tests, while leaf nodes represent allow decisions. Requests are evaluated by traversing the tree top–down until a matching leaf is reached or no valid path exists. For simplicity, we assume a single operation for all rules and requests in this example and hence, the operation attribute is omitted from this EXTree representation. To enable explainability and actionable feedback (i.e., to address research question RQ1), we introduce a meta-policy M in EXTree comprised of two functions [5] that augment the base ABAC model: i. Visibility Function Vis(a, actor) ∈ [0, 1]
(2)
quantifies how much information about attribute a may be disclosed to a particular actor (user, administrator, or requester). A value of 1 indicates full visibility, 0 indicates full confidentiality, and intermediate values encode partial or probabilistic disclosure. ii. Change Cost Function ChangeCost(a, vfrom , vto ) ∈ [0, ∞)
(3)
represents the estimated difficulty or effort required to modify an attribute a from vfrom to vto . This may be accounting for monetary cost, time or administrative work required. When generating feedback, the system focuses on attributes that the requester can realistically modify. Attributes with lower change costs are therefore preferred, subject to the constraints defined by the visibility function earlier. A normalized attribute-level measure can be defined as: ca − cmin C(a) = , Changeability(a) = 100(1 − C(a)) cmax − cmin
(4)
where ca is the raw assigned difficulty score and cmin , cmax are system-specific bounds. Table 1 lays down a fallback set of values for attributes if required. This baseline reflects a pragmatic assumption: environmental conditions are transient and system-controlled, user attributes are modifiable but bureaucratic, while object attributes are largely immutable once provisioned. Such default priors can later be adapted via monitoring, feedback or empirical policy usage statistics. 4
EXTree: Towards Supporting Explainability in Attribute-based Access Control
Table 1: Default Change Cost Profiles
3.2
Category
Characteristics
Environmental (E)
High volatility, system-controlled
Cost Range
User (U)
Moderate mutability, administrative oversight
50-90
Object (O)
Low mutability, security-critical
80-100
0-40
EXTree Design Considerations
In this sub-section, we present two major design considerations while building an EXTree from ABAC rules. 3.2.1
Attribute Splitting Criterion
Since EXTree inherits its core hierarchical representation from the PolTree framework [11], a natural baseline for tree construction is the entropy-based splitting heuristic commonly used in decision tree. Entropy measures the uncertainty or impurity of a dataset—zero when all samples share the same outcome, and a maximum value when classes are evenly split. In decision trees, it quantifies how mixed the decision outcomes are at a node: H(S) = −pallow log2 (pallow ) − pdeny log2 (pdeny ),
H(S) ∈ [0, 1]
(5)
where pallow and pdeny denote the proportions of allowed and denied requests. The splitting attribute is typically chosen to maximize information gain—the largest reduction in entropy: Gain(S, A) = H(S) −
X v∈Values(A)
|Sv | H(Sv ) |S|
(6)
Each internal node represents an attribute predicate (e.g., Department = HR), and the leaves denote permit/deny outcomes. The Highest-Entropy-First heuristic seeks attributes that most evenly divide policies, aiming for shallower and faster evaluation trees. However, ABAC attributes are often semantically correlated (for example, role and clearance), so the entropy across attributes do not always differ much. Moreover, in EXTree each level evaluates a distinct attribute, which means the depth of the tree is naturally limited by the number of attributes available. Because of these properties, we hypothesize that entropy-based splitting may not offer much advantage beyond what the hierarchical structure itself achieves. To explore this further, we compare several alternative splitting strategies: Highest-Entropy-First, Lowest-Entropy-First, Changeability-Based, and Random. 3.2.2
Feedback Strategy Evaluation
To address RQ2, this sub-section introduces four feedback generation strategies for EXTree that explore different trade-offs between feedback interpretability with computational efficiency. Each strategy begins at a deny node and searches the EXTree for reachable allow nodes through permissible attribute modifications (Figure 1). The deny node captures the deepest point in the policy tree that the request satisfies, making it the natural starting point for generating minimal corrective feedback. Actionable Feedback. In this work, we define actionable feedback for a denied ABAC request as a bounded set of attribute modifications that transforms the request from a deny outcome to an allow outcome. Among feasible explanations, lower cumulative changeability cost corresponds to more actionable feedback, as it prioritizes attributes that users can realistically modify. In practice, attributes vary in mutability due to organizational constraints: attributes such as roles or security clearances are often fixed, whereas contextual or procedural attributes may be modified with lower effort. Changeability cost provides a principled way to distinguish feasible modifications from impractical ones. Accordingly, EXTree is primarily designed to support near-miss denials—cases where a request narrowly fails policy constraints and feasible corrective modification is realistic. While the primary focus is user-facing remediation, the EXTree structure and feedback strategies also support administrative analysis and policy debugging. Two search-limiting constraints ensure tractability for high-dimensional ABAC policies: • Depth limit (max depth): restricts traversal distance from the deny node • Change limit (max changes): restricts maximum attribute modifications in feedback 5
EXTree: Towards Supporting Explainability in Attribute-based Access Control
(a) Depth-first
(b) Depth-best
(c) Change-first
(d) Change-best
Figure 2: Visualization of feedback search strategies on the example EXTree. The denied request (role = manager, department = HR, clearance = medium) terminates at the deny red node. Visited nodes are highlighted in yellow, red edges denote attribute deviations from the request, and the selected feedback path is shown in bold. The feedback cost is the sum of the changeability costs along the selected path. Depending on the termination policy, strategies either return the first valid allow node encountered (greedy) or exhaustively evaluate all feasible candidates and return the minimum-cost solution. The four strategies evaluated are depth-first, depth-best, change-first, change-best. Algorithm and Complexity Algorithm 1 performs a bounded search around the deny node to identify reachable allow nodes that require minimal attribute modifications. The EXTree is treated as a graph, allowing traversal both upward (constraint relaxation) and downward (constraint addition). Change cost is accumulated only when traversing to child nodes whose predicates are violated by the request; traversal toward parent nodes does not increase cost. The search is constrained by a maximum traversal depth D = max depth and a maximum number of attribute changes K = max changes. The choice of strategy determines the candidate expansion order, prioritizing either proximity to the deny node (depth-based) or lower cumulative changeability cost (change-based). Greedy variants terminate upon encountering the first valid allow node, while exhaustive variants enumerate all feasible candidates within these bounds. Let A denote the number of distinct attributes in the policy and b the maximum branching factor of the EXTree. Since each level of the tree corresponds to a test on a distinct attribute, the tree height is bounded by A. In the worst case, a depth-limited traversal explores O(bD ) nodes. Independently, the number of feasible change configurations is bounded by the number of ways to select and modify up to K attributes out of A, where each modified attribute can take up to b values: K X A k b = O (Ab)K . k k=0
Accounting for traversal across at most A levels of the tree for each change configuration, the total number of explored states is bounded by M = O min(bD , AK+1 bK ) . Change-based strategies incur an additional O(log M ) overhead due to priority queue operations, whereas depth-based strategies rely on constant-time stack operations. Although the worst-case search is exponential in bounds D and K, 6
EXTree: Towards Supporting Explainability in Attribute-based Access Control
in practice, early termination and tight change limits significantly reduce the explored search space, as observed empirically. Particularly since typical branching factors are modest (b ≈ 2-5) and change limits are small (K ≤ 3). Algorithm 1 Feedback Path Search in EXTree 1: Input: Policy tree T , meta-policy, deny node nd , request r, user u, strategy S, limits (max depth, max changes) 2: Output: (S ∗ , c∗ ) where S ∗ is the suggested attribute changes and c∗ is the total cost, or null 3: Initialize candidate collection C: 4: stack if S ∈ {depth first, depth best}, priority queue (by increasing cost) if S ∈
{change first, change best} 5: Insert (nd , 0, 0, ∅) into C ▷ (node, cost, depth, change set) 6: c∗ ← ∞, S ∗ ← ∅ 7: while C not empty do 8: Pop (n, c, d, S) from C ▷ best according to strategy 9: if n visited then 10: continue 11: Mark n visited 12: if d > max depth or |S| > max changes then 13: continue 14: if n is ALLOW then 15: if S ∈ {depth first, change first} then 16: return (S, c) 17: else if c < c∗ then 18: c∗ ← c, S ∗ ← S 19: if n has a parent p then ▷ Relax constraint: move to parent (no cost added) 20: Insert (p, c, d + 1, S) into C 21: Let a be the attribute tested on edge (n → ·) ▷ Add constraint: move to children (may incur cost) 22: for all children n′ of n do 23: if visibility[a][u] = 0 then 24: continue 25: c′ ← c, S ′ ← S 26: if r[a] does not equal the value on edge (n → n′ ) then 27: c′ ← c + change cost[a] 28: S ′ ← S ∪ {a : r[a]} 29: Insert (n′ , c′ , d + 1, S ′ ) into C 30: return (S ∗ , c∗ )
Feedback Strategies The four feedback strategies represent distinct philosophies of search control—ranging from greedy, time-sensitive heuristics to exhaustive, globally optimal traversals. We illustrate their behavior using the same policy and denied request introduced earlier. Figure 1 shows the corresponding EXTree and the evaluation trace. We assign fixed changeability costs to attributes to reflect their relative difficulty of modification. Specifically, the costs used in the example are: training over = 20, department = 50, clearance = 70, and role = 80. The search is constrained by max changes = 2 and max depth = 3. Depth-first Search This strategy traverses the EXTree in a depth-first manner and terminates immediately upon encountering the first allow node within the allowed depth limit. It prioritizes speed over optimality, generating fast but potentially suboptimal feedback as shown in Figure 2a. For the example request, depth-first search suggests modifying clearance from medium to low, producing an allow decision with a cumulative changeability cost of 70. Depth-best Search Unlike the greedy variant, the depth-best strategy performs a complete traversal of all candidate paths within the given depth limit and returns the allow node with the minimal cumulative changeability cost as shown in Figure 2b. It provides more accurate and interpretable feedback at the expense of higher computational overhead. For the 7
EXTree: Towards Supporting Explainability in Attribute-based Access Control
example request, depth-best search also suggests clearance from medium to low, producing an allow decision with a cumulative changeability cost of 70. Change-first Search This strategy prioritizes attribute modification feasibility over structural traversal depth. Starting from the deny node, it explores changes to low-cost attributes first and terminates upon reaching the first valid allow node that respects the max changes constraint as shown in Figure 2c. For the example request, change-first search suggests changing the department attribute from HR to Finance, resulting in an allow decision with a cumulative changeability cost of 50. Change-best Search The exhaustive variant searches all reachable allow nodes within the change limit and returns the minimum-cost modification as shown in Figure 2d. This provides globally optimal feedback and is suitable for administrative or audit settings where completeness matters more than response time. For the example request, this exhaustive search also identifies modifying department from HR to Finance as the optimal correction, resulting in a cost of 50. As is evident from the design of EXTree, RQ1 is sufficiently addressed by formally defining what constitutes actionable feedback in the ABAC setting. Visibility-Constrained Feedback. In realistic organizational settings, certain policy rules encode sensitive information—internal classification thresholds, administrative roles, or confidential resource attributes—that cannot be disclosed without violating security constraints. Visibility constraints are inherently user-dependent, whereas EXTree construction is policy-centric and user-agnostic. Incorporating visibility during tree construction would therefore require rebuilding the tree per user, which is impractical. We instead enforce visibility as an evaluation-time constraint during feedback generation. Our current implementation uses a binary visibility model, where attributes are either visible or hidden. This captures the common use case, while richer visibility models are left for future work. Each edge corresponding to an attribute–value predicate a is assigned a binary visibility flag va ∈ {0, 1}. For a candidate explanation path P = {a1 , . . . , ak }, the visibility-aware cost is: ( ∞, ∃ai ∈ P s.t. vai = 0, Cv (P ) = Pk C(a ), otherwise. i i=1 Paths traversing hidden predicates are excluded from consideration by assigning infinite traversal cost during evaluation, without modifying the underlying EXTree structure.
4
Experimental Results
In this section, we carry out extensive experiments to study the performance of EXTree under various conditions. 4.1
Datasets
We evaluate EXTree using two synthetic ABAC datasets and one realistic dataset from the ABACLab repository [1]. Synthetic datasets. Two datasets were generated using the publicly available generator of [13], augmented with 30– 50% wildcard predicates to simulate realistic policy overlap. Synthetic–1 provides a balanced baseline (1000 users, 1000 objects, 1000 policies), while Synthetic–2 scales entity and policy counts to evaluate performance under larger rule sets. Both maintain an approximate 70:30 allow-to-deny ratio. Realistic dataset. The Healthcare Access dataset from ABACLab [1, 2] models fine-grained access control in a healthcare setting, incorporating role hierarchies, sensitivity levels, and contextual attributes. Although smaller in size, it captures realistic attribute correlations and policy semantics. Further details regarding parameter choices and generator setup are provided in Appendix A.1. 4.2
Effect of Splitting Criterion on EXTree Efficiency
This section studies the effect of different splitting criteria on the efficiency of EXTree. Each dataset was evaluated using 10,000 random queries simulating realistic access requests. Metrics recorded include tree generation time, total number of nodes, average decision latency, and total query time. 8
EXTree: Towards Supporting Explainability in Attribute-based Access Control
In Tables 2 and 3, we report results for the splitting heuristics introduced in Section 3.2.1. Across datasets and metrics, no heuristic consistently outperforms the others. While Lowest-Entropy-First trees often contain fewer nodes, this does not translate to lower query latency. In some cases, smaller trees give rise to higher decision times due to unbalanced partitions, whereas larger trees benefit from more uniform branching. Overall, the performance of all heuristics falls within a narrow range. This suggests that the main efficiency gain comes from the hierarchical organization itself rather than the specific splitting rule. Such a behavior can be explained by the structural properties of ABAC policy trees. Since each level tests a distinct attribute, the tree depth is bounded by the total number of attributes. This ensures that different splitting heuristics cannot create very deep or highly skewed trees, limiting the benefits of entropy-based optimization. In addition, many ABAC attributes are semantically related (e.g., department, clearance, resource type), which limits variation across possible splits. Table 2: Synthetic Dataset Performance Comparison for Four Splitting Criteria Dataset
Synthetic-1
Synthetic-2
Heuristic
Nodes Allowed Denied Avg. Time (s)
Highest Entropy
13,983
6,976
3,024
1.68 × 10−5
Lowest Entropy
11,999
6,976
3,024
2.93 × 10−5
Highest Change Cost 14,216
6,976
3,024
2.93 × 10−5
Random
14,205
6,976
3,024
2.93 × 10−5
Highest Entropy
12,090
7,037
2,963
3.23 × 10−5
Lowest Entropy
9,753
7,037
2,963
3.64 × 10−5
Highest Change Cost 14,187
7,037
2,963
2.89 × 10−5
7,037
2,963
1.72 × 10−5
Random
14,208
Table 3: Realistic ABAC Dataset Performance Comparison for Four Splitting Criteria Heuristic
Nodes Allowed Denied Avg. Time (s) Total Time (s)
Lowest Entropy
250
41
34
3.45 × 10−6 2.58 × 10−4
Highest Entropy
361
41
34
4.78 × 10−6
3.58 × 10−4
Highest Change Cost
254
41
34
5.56 × 10−6
4.17 × 10−4
34
−6
3.56 × 10−4
Random
320
41
4.74 × 10
We see that the choice of splitting criterion has negligible impact on runtime performance. This allows EXTree construction to prioritize interpretability metrics such as changeability cost or attribute visibility—without sacrificing decision-making efficiency. The main improvement in access evaluation time comes from the hierarchical structure itself, allowing EXTree to optimize for interpretability without affecting performance. 4.3
Feedback Strategy Results
The feedback generation strategies depend on two parameters: the maximum traversal depth (max depth) and the maximum number of allowed attribute modifications (max changes). These parameters govern the trade-off between feedback coverage, complexity, and computational cost, and must be selected on a per-dataset basis due to variations in policy size and structure. The method used for selecting these parameters, and their overall effect on results is given in Appendix A.2. Strategy Evaluation Using the identified parameters, we now evaluate and compare the four feedback generation strategies introduced in Section 3.2.2. The evaluation uses the following six metrics: • Average Cost: Average cumulative changeability cost of modified attributes. Lower costs indicate more feasible changes. 9
EXTree: Towards Supporting Explainability in Attribute-based Access Control
Table 4: Performance of different feedback strategies on the Synthetic-2 dataset (max depth = 30, max changes = 8). Tree Type
Strategy
Avg. Cost Avg. Time (ms) Found Fraction Nodes Expanded Avg. Depth Avg. #Changes
Entropy
Depth-first Depth-best Change-first Change-best
490.16 462.68 462.68 462.68
17.47 22.21 25.93 29.00
0.82 0.82 0.82 0.82
5198.95 6789.90 5858.08 6789.92
15.99 18.00 18.00 18.00
7.62 7.49 7.49 7.49
Depth-first Depth-best High-Cost-First Change-first Change-best
322.51 213.63 213.63 213.63
1.98 22.89 2.42 29.60
1.00 1.00 1.00 1.00
520.68 6960.61 460.75 6960.61
8.54 14.05 14.05 14.05
6.62 4.02 4.02 4.02
• Average Time (ms): Average time per denied request, measuring computational efficiency. • Found Fraction: Ratio of denied requests yielding valid feedback paths. A value of 1.0 indicates complete coverage. • Nodes Expanded: Average number of nodes visited during traversal, measuring search complexity. • Average Depth: Average distance between deny and the final allow node chosen. • Average Number of Changes: Average number of attributes needing modification. Lower values mean more actionable feedback. Experiments were performed on all datasets using two tree types: entropy-based trees (optimized for decision efficiency) and high-cost-first trees (optimized for interpretability). Tables 4 and 5 present detailed performance statistics. The Synthetic-1 dataset is omitted from the tabulated results. For this dataset, entropy-based trees fail to produce actionable feedback under the selected traversal and modification limits, resulting in a zero success rate across all strategies. Notably, change-aware tree constructions on the same dataset still achieve high feedback coverage (0.95). This highlights the role of the policy tree structure in supporting explainability, and addresses RQ2 on how meaningful explanations can be generated under practical attribute constraints. Two consistent trends emerge across all datasets: (i) Superiority of Change-first: The change-first strategy consistently achieves the lowest computation time without sacrificing explanation quality. Because the search proceeds greedily over attributes, feasible low-cost corrections are typically found early. In deeper trees, it avoids unnecessary exploration, and typically expands fewer nodes than alternative strategies. (ii) Synergy with High-Cost-First Trees: When the tree is structured using high change-cost attributes near the root, change -first becomes even more effective. The attribute ordering guides the search toward simpler corrections, often resulting in shallow traversal depth and only a few attribute modifications. In practice, this produces concise and interpretable feedback. Depth-based strategies occasionally achieve slightly better optimal costs, but they do so by expanding many more nodes, which introduces significant computational overhead. In contrast, change -first provides a better balance between efficiency and explanation quality, making it more suitable for real-time decision support. The strong coverage and low-cost feedback produced by change-based strategies show how meaningful explanations can be generated under practical constraints, addressing research questions RQ1 and RQ2. 4.4
EXTree Construction Evaluation
Building on the findings from the previous sub-section, we next evaluate how different policy tree constructions influence feedback efficiency and explanation quality. The change first strategy is held constant, and the optimal (max depth, max change) values from Table 11 are applied to each tree type. 10
EXTree: Towards Supporting Explainability in Attribute-based Access Control
Table 5: Performance of different feedback strategies on the ABACLab Healthcare dataset (max depth = 5, max changes = 3). Tree Type
Strategy
Avg. Cost Avg. Time (ms) Found Fraction Nodes Expanded Avg. Depth Avg. #Changes
Entropy
Depth-first Depth-best Change-first Change-best
125.00 90.91 88.64 88.64
0.05 0.08 0.05 0.14
1.00 1.00 1.00 1.00
19.14 37.00 13.45 42.95
3.36 4.32 4.36 4.36
2.27 1.41 1.36 1.36
Depth-first Depth-best High-Cost-First Change-first Change-best
123.64 88.64 88.64 88.64
0.04 0.10 0.04 0.11
1.00 1.00 1.00 1.00
16.73 32.50 9.86 35.91
3.27 3.68 3.68 3.68
2.27 1.36 1.36 1.36
Experimental Setup Three tree construction methods are analyzed: • Entropy-based: At each node, attributes with the highest entropy are selected for splitting, following the standard information-theoretic principles. • High-cost-first: Attributes with high modification costs are prioritized closer to the root node. • Low-cost-first: Attributes with low modification costs are prioritized closer to the root node. The same datasets and denied requests from the previous section are used to ensure consistency and enable direct comparison. EXTree Construction Results Table 6 presents performance metrics for each tree construction method across the three datasets. Table 7 compares three tree construction strategies—Entropy-based, High-Cost-First, and Low-Change-Cost—across all datasets using the change-first feedback strategy. The results show that different heuristics lead to different trade-offs in efficiency and solution quality. Table 6: Comparative performance of tree construction heuristics. Dataset
Tree Type
Avg. Cost
Time (ms)
Success
Nodes
Depth
Changes
Entropy Synthetic-1 High-Cost-First (4, 30) Low-Cost-First
– 133.78 107.07
– 1.23 7.57
0.00 0.95 0.93
– 270.55 1853.82
– 14.05 15.56
– 3.64 3.66
Entropy Synthetic-2 High-Cost-First (8, 30) Low-Cost-First
445.59 210.53 200.10
23.77 2.22 10.90
0.80 1.00 1.00
5582.13 445.23 2308.55
17.41 14.43 15.43
7.19 3.78 3.98
Entropy Healthcare High-Cost-First (3, 5) Low-Cost-First
88.64 88.64 75.45
0.05 0.04 0.13
1.00 1.00 1.00
13.45 9.86 22.86
4.36 3.68 3.55
1.36 1.36 1.00
High-Cost-First trees achieve the best overall balance of efficiency and effectiveness. By prioritizing attributes with higher modification costs, they eliminate expensive solution branches early, creating a natural pruning effect. This leads to fewest node expansions (9.86–445.23) and the lowest runtimes (0.04–2.22 ms), while keeping the search depth moderate (3.68–14.43). Although these trees do not always produce the absolute lowest-cost policies, they consistently reach near-optimal solutions quickly. Low-Change-Cost trees adopt the opposite approach. Because inexpensive attributes are explored first, the search tends to move deeper and broader into the tree before finding a feasible correction. In some cases this slightly improves solution cost—for example, on Synthetic-2 the average cost drops to 200.10 compared to 210.53 for High-Cost-First. 11
EXTree: Towards Supporting Explainability in Attribute-based Access Control
Table 7: Aggregate performance comparison of policy tree construction heuristics across all datasets using the change-first strategy. Normalized scores are computed as the ratio of best cost to actual cost within each dataset (higher is better). Metrics are averaged only over datasets where solutions were found, and success is reported separately. Tree Type
Norm. Score Time (ms) Depth Success
Entropy-based
0.65
11.91
10.89
0.60
High-Cost-First
0.87
1.23
10.72
0.98
Low-Cost-First
0.94
6.20
11.51
0.98
However, the improvement is small and comes with much higher computation, requiring roughly five times more node expansions and longer runtimes. Entropy-based trees perform the weakest overall. Since splits are chosen based on information gain rather than modification cost, the resulting tree structure is better suited for classification than for cost-aware search. As a result, the search expands more nodes, produces higher-cost policies, and tends to generate deeper solution paths (e.g., 17.41 compared to 14.43 and 15.43 on Synthetic-2). The search therefore spreads across many branches without consistently moving toward low-cost corrections. Intuitive Explanation Figures 3a and 3c show two EXTrees constructed from the same policy introduced in Section 2.1. In the highchange-cost-first construction, attributes that are expensive or difficult to modify appear closer to the root, whereas attributes with lower changeability cost are placed deeper in the tree. In contrast, the low-change-cost-first construction places easily modifiable attributes near the root. The request considered here is r = (role = intern, department = General, clearance = low, training over = no), which evaluates to a deny decision under the policy. Although the cost of the path from the deny node to an allow leaf is identical for both trees, the number of nodes traversed differs significantly. The high-change-cost-first EXTree (Figure 3a) requires traversing fewer nodes to locate an appropriate allow node, even though both trees have the same depth. This difference arises because attributes that are more changeable (i.e., lower change cost) are intentionally positioned closer to the leaves, where denials are more likely to occur. Consequently, once a denial is encountered, the subsequent local search is confined to attributes that the requester can modify feasibly, leading to rapid generation of meaningful feedback (Figure 3b). In contrast, when attributes with low change cost are placed near the root (Figure 3c), the evaluation path for most requests is determined by easily modifiable attributes early on. This results in deeper subtrees dominated by high-cost or immutable attributes, which not only reduce the relevance of the branch to the request but also make corrective feedback harder to generate (Figure 3d). In general, placing high-change-cost attributes near the EXTree root yields two distinct advantages. (i) Branch relevance: Early splits occur on stable, user-invariant attributes (e.g., role, department), ensuring that the evaluation path corresponds closely to the requester’s fundamental context and (ii) Feedback efficiency: The remaining attributes along the path from a deny node to the nearest allow node are those that are most easily changeable, reducing both traversal effort and overall change cost. Therefore, EXTrees constructed using a high-change-cost-first criterion naturally align with the goal of producing low-cost, relevant feedback. This design balances efficiency with explainability. 4.5
Effect of Visibility Constraints
We evaluate the impact of visibility-aware filtering by restricting access to attribute–value predicates, while keeping the underlying EXTree unchanged. Visibility is modeled as a binary property of attribute–value pairs. For this experiment, the same visibility assignment is applied uniformly across all users to isolate the effect of restricted disclosure. We increase the fraction of hidden attribute–value predicates across the policy. During feedback generation, paths traversing hidden predicates are rendered infeasible by assigning infinite cost. Table 8 summarizes the effect of decreasing visibility on feedback generation for the Synthetic-1 dataset. As visibility decreases, the fraction of requests for which a valid explanation exists drops sharply; below approximately 30% visibility, no feasible explanation paths remain. Similar qualitative trends are observed across other datasets. 12
EXTree: Towards Supporting Explainability in Attribute-based Access Control
(a) High-change-cost-first EXTree (evaluation).
(b) High-change-cost-first EXTree (feedback).
(c) Low-change-cost-first EXTree (evaluation).
(d) Low-change-cost-first EXTree (feedback).
Figure 3: Comparison of EXTree construction strategies using the policy introduced in Section 2.1 and the denied request (role = intern, department = General, clearance = low, training over = no). Although both trees have identical depth, their construction significantly affects the amount of search required to generate actionable feedback.
Table 8: Average impact of decreasing visibility on feedback generation performance in Synthetic-1 Dataset, aggregated across all search strategies. Visibility Found (%) Avg Score Avg Nodes Avg Time (ms) 100% 90% 80% 70% 60% 50% 40% ≤30%
100 100 100 82 59 53 13 0
186.7 205.1 203.1 255.4 284.9 301.0 301.3 –
2478 2268 750 399 137 556 226 0
10.2 7.0 1.8 1.0 0.4 1.4 0.6 0
Crucially, visibility constraints introduce no measurable computational overhead. Average feedback generation time remains stable—and often decreases slightly—as visibility is reduced from 100% to 50%, remaining within submillisecond bounds. This is explained by the early exclusion of infeasible paths via infinite traversal cost. Average explanation cost increases as visibility decreases, reflecting the elimination of lower-cost paths that traverse hidden predicates and the selection of higher-cost feasible alternatives. Despite reduced feasibility, node expansion and traversal depth remain bounded until explanations disappear entirely. Find an illustrative example in Appendix A.3. Discussion Entropy-based trees provide rich feedback options due to their balanced splits, but require deeper traversal to reach valid allow nodes. High-change-cost-first trees lead to more interpretable feedback—users receive guidance on modifying high-impact attributes early in the path. Conversely, low-change-cost-first trees offer the simplest, low-effort fixes but at the expense of feedback completeness. The combination of the change first strategy with the high13
EXTree: Towards Supporting Explainability in Attribute-based Access Control
Table 9: Comparison of ABAC systems with respect to Explainability Support. System
Denial Explanation Actionable Feedback Scalability Privacy Control
KNOW [8] CUE [5] PolTree [11] Margrave [4] LLMAC [23] EXTree (This Work)
✓ ✓ × × ✓ ✓
× × ✓ × × ✓
✓ ✓ × × × ✓
✓ ✓ × × × ✓
Explanation Mechanism OBDD-based reasoning XACML policy analysis Hierarchical policy tree Decision-diagram verification LLM-based explanation Policy tree + bounded local search
change-cost-first EXTree structure provides the most effective feedback mechanism for explainable ABAC systems producing concise and meaningful feedback while maintaining low response latency, thereby addressing RQ3.
5
Related Work
With increasingly complex models being used in computer security and a growing societal demand for transparency in automated decision making, explainability has emerged as an important consideration in access control. Yet, explicit denial-feedback mechanisms remain rare in ABAC systems. As Miller [9] argues, effective explanations must be selective, contrastive, and contextually relevant. In access control, this translates to providing clear, actionable feedback rather than exposing the full policy logic. The earliest systems to provide structured denial feedback are KNOW [8] and CUE [5]. KNOW computes minimal sufficient policy changes using OBDD-based reasoning and regulates disclosure through meta-policies. CUE enhances XACML infrastructures with user-oriented feedback by distinguishing mutable and immutable attributes. While both frameworks improve usability, feedback is derived through global policy traversal (decision-diagram reasoning or policy scanning), which limits scalability in large-scale deployments. Other lines of work focus on efficient policy evaluation or formal verification rather than user-facing feedback. PolTree [11] introduces hierarchical indexing for efficient ABAC decision-making but does not support explanation. Margrave [4] translates policies into decision diagrams for verification and semantic differencing, producing counterexamples for administrators rather than user-facing denial explanations. With new access control models being developed, there is renewed interest in exploring explainability in security systems more broadly [21]. Mehri et al. [6] motivate the need for explainable access control and outline key research challenges, but do not introduce a concrete feedback mechanism. Rodrı́guez et al. [17] propose DEBAC, which employs explainable boosting machines to compute interpretable trust scores in WLAN environments; however, it does not compute minimal corrective attribute changes for denied access. More recently, LLM-based approaches such as LLMAC propose generating natural-language explanations for access decisions using large language models. While such systems improve interpretability at the presentation layer, explanations are derived through statistical inference rather than structured policy reasoning and do not provide bounded, minimal-change guarantees within the policy model itself. Related work in identity management and data governance [14], explainable intrusion detection systems [12, 10] and surveys on explainable cybersecurity [20], underscores the importance of transparency, though these efforts operate outside the ABAC denial-feedback setting. Unlike OBDD-based or policy-scanning explanation layers, EXTree incorporates explainability directly into the hierarchical policy structure itself. Feedback generation is expressed as a bounded local search around the deny node, optimizing changeability costs while respecting visibility constraints. To the best of our knowledge, no existing ABAC framework formulates explainability as a bounded search process designed explicitly for scalable feedback generation. Table 9 summarizes the key distinctions.
6
Conclusion and Future Directions
This paper demonstrates that efficiency and explainability need not be competing objectives by proposing EXTrees for ABAC. While traditional feedback mechanisms require expensive scans of the policy after a denial, EXTrees encode attribute dependencies directly in the tree structure, allowing the system to produce interpretable feedback focused on actionable attribute changes while keeping computation lightweight. As a result, efficient policy evaluation and transparent feedback can be achieved within the same architecture. There are several directions for future work. A natural next step is to evaluate EXTree on real-world ABAC systems, where attributes may be correlated and constraints depend on context. This would help understand practical applicability. Another direction is extending EXTree to support richer policy semantics, such as rule-combining operators (e.g., 14
EXTree: Towards Supporting Explainability in Attribute-based Access Control
permit-overrides and deny-overrides) used in XACML. These operators could be supported by encoding precedence constraints in the tree during construction or traversal. Adaptive feedback strategies can be explored that adjust based on user behavior and attribute information, potentially using machine learning to tune system parameters over time. Finally, supporting incremental updates would allow the tree to be updated as policies change, without rebuilding it from scratch, making it more effective in dynamic environments. We hope this work encourages further exploration of structural approaches to transparency in authorization systems.
References [1]
[2]
[3]
[4] [5]
[6] [7] [8]
[9] [10]
[11] [12]
[13]
[14]
[15] [16] [17]
[18]
ABAC-Lab-Admin. ABAC-Lab: repository of ABAC policy datasets (University, Workforce, Healthcare, ...) https://github.com/ABAC- Lab- Admin/ABAC- Lab. Datasets folder includes Healthcare dataset used in ABAC research. 2025. Thang Bui et al. “ABAC Lab: An Interactive Platform for Attribute-based Access Control Policy Analysis, Tools, and Datasets [Dataset/Tool Paper]”. In: 30th ACM Symposium on Access Control Models and Technologies. USA, 2025, pp. 111–116. DOI: 10.1145/3734436.3734441. Bernard Butler et al. “XACML policy performance evaluation using a flexible load testing framework”. In: Proceedings of the 17th ACM Conference on Computer and Communications Security. CCS ’10. Chicago, Illinois, USA: ACM, 2010, pp. 648–650. DOI: 10.1145/1866307.1866385. K. Fisler et al. “Verification and change-impact analysis of access-control policies”. In: 27th International Conference on Software Engineering. 2005, pp. 196–205. DOI: 10.1109/ICSE.2005.1553562. Sunil Kumar Ghai et al. “Cue: a framework for generating meaningful feedback in XACML”. In: 3rd ACM Workshop on Assurable and Usable Security Configuration. ACM, 2010, pp. 9–16. DOI: 10.1145/1866898. 1866901. Gelareh Hasel Mehri et al. “Towards Explainable Access Control [BlueSky Paper]”. In: 2025 ACM Symposium on Access Control Models and Tehnologies. July 2025, pp. 117–126. DOI: 10.1145/3734436.3734439. Vincent C Hu et al. “Guide to attribute based access control (ABAC) definition and considerations”. In: NIST Special Publication 800.162 (2014). Apu Kapadia et al. “Know Why Your Access Was Denied: Regulating Feedback for Usable Security”. In: 11th ACM Conference on Computer and Communications Security. 2004, pp. 52–61. DOI: 10 . 1145 / 1030083 . 1030092. Tim Miller. “Explanation in artificial intelligence: Insights from the social sciences”. In: Artificial Intelligence 267 (2019), pp. 1–38. DOI: https://doi.org/10.1016/j.artint.2018.07.007. Vincent Zibi Mohale and Ibidun Christiana Obagbuwa. “A systematic review on the integration of explainable artificial intelligence in intrusion detection systems to enhancing transparency and interpretability in cybersecurity”. In: Frontiers in Artificial Intelligence Volume 8 (2025). DOI: 10.3389/frai.2025.1526221. Ronit Nath et al. “PolTree: A Data Structure for Making Efficient Access Decisions in ABAC”. In: ACM Symposium on Access Control Models and Technologies. 2019, pp. 25–35. DOI: 10.1145/3322431.3325102. Subash Neupane et al. Explainable Intrusion Detection Systems (X-IDS): A Survey of Current Methods, Challenges, and Opportunities. 2022. arXiv: 2207 . 06236 [cs.CR]. URL: https : / / arxiv . org / abs / 2207 . 06236. Proteet Paul and Shamik Sural. “Towards Efficient Evaluation of ABAC Policies using High-Dimensional Indexing Techniques”. In: Third IEEE International Conference on Trust, Privacy and Security in Intelligent Systems and Applicationss. 2021, pp. 243–251. DOI: 10.1109/TPSISA52974.2021.00027. Srinivas Potluri. “Policy-Aware Secure Data Governance in Distributed Information Systems Using Explainable AI Models”. In: International Journal of AI, BigData, Computational and Management Studies 6.3 (July 2025), pp. 1–10. DOI: 10.63282/3050-9416.IJAIBDCMS-V6I3P101. Mohsen Rezvani et al. “Analyzing XACML policies using answer set programming”. In: International Journal of Information Security 18 (Aug. 2019), pp. 465–479. DOI: 10.1007/s10207-018-0421-5. Erik Rissanen. eXtensible Access Control Markup Language (XACML) Version 3.0. Tech. rep. 2013. URL: https://docs.oasis-open.org/xacml/3.0/xacml-3.0-core-spec-os-en.html. Lucı́a Cabanillas Rodrı́guez et al. “DEBAC: Dynamic Explainable Behavior-Based Access Control”. In: 2025 Joint European Conference on Networks and Communications & 6G Summit. 2025, pp. 733–738. DOI: 10 . 1109/EuCNC/6GSummit63408.2025.11037037. Ravi S. Sandhu and Pierangela Samarati. “Access control: principle and practice”. In: IEEE Communications Magazine 32.9 (1994), pp. 40–48. DOI: 10.1109/35.312842. 15
EXTree: Towards Supporting Explainability in Attribute-based Access Control
[19] [20]
Ravi S. Sandhu et al. “Role-based access control models”. In: IEEE Computer 29.2 (1996), pp. 38–47. Anshika Sharma et al. “A comprehensive review of explainable AI in cybersecurity: Decoding the black box”. In: ICT Express 11.6 (2025), pp. 1200–1219. DOI: https://doi.org/10.1016/j.icte.2025.10.004. [21] Luca Viganò and Daniele Magazzeni. “Explainable Security”. In: IEEE European Symposium on Security and Privacy Workshops. 2020, pp. 293–300. DOI: 10.1109/EuroSPW51379.2020.00045. [22] E. Yuan and J. Tong. “Attributed based access control (ABAC) for Web services”. In: IEEE International Conference on Web Services. 2005, p. 569. DOI: 10.1109/ICWS.2005.25. [23] Sharif Noor Zisad and Ragib Hasan. “LLMAC: A Global and Explainable Access Control Framework with Large Language Model”. In: IEEE 23rd Consumer Communications & Networking Conference. IEEE, Jan. 2026, pp. 1–6. DOI: 10.1109/ccnc65079.2026.11366514.
A
Appendix
A.1
Dataset Details
This study employs two synthetic datasets for experimentation and one realistic dataset from the ABACLab repository [1] to ensure real-world relevance. The synthetic datasets were generated using the publicly available github repository of [13]. For simulating realistic policy overlaps, we introduced wildcards in 30–50% of attribute values. Synthetic–1 provides a balanced baseline with 1000 users, objects, and policies, each defined by six attributes with Table 10: Summary of datasets used in evaluation. nu : users; no : objects; ne : environment entities; ua , oa , ea : user/object/environment attributes; nv∗ : values per attribute; np : policies; nops : operations or granted permissions. Dataset
nu
no
ne ua oa ea nvu nvo nve
Synthetic–1 1000 1000 10 6 Synthetic–2 2000 1500 20 8 Healthcare (ABACLab) 21 16 – 6
6 6 8 6 7 –
4 5 –
4 5 –
4 4 –
np
nops
1000 3 2000 1 6 43
four possible values. Synthetic–2 increases the number of entities to evaluate scalability. The parameters are chosen to produce realistic datasets while keeping the experiments manageable, avoiding cases where policies are either too sparse or too dense [22, 7]. Request sets maintain an approximate 70:30 accept-to-deny ratio. The Healthcare Access Dataset from ABACLab [1, 2] models access control scenarios in healthcare environments, with policies defined by staff roles, patient sensitivity levels, and contextual attributes such as emergency status. Full parameter settings are shown in Table 10. A.2
Parameter Optimization
We perform a systematic grid search for each dataset over max depth and max changes to analyze their effect. Figure 4 illustrates this process for the Synthetic-2 dataset. The grid search varies max depth ∈ {3, 5, 10, 20, 30, 50, 75, 100} and max changes ∈ {1, 2, 3, 5, 10, 15, 20}. Each heatmap cell represents a specific (max depth, max changes) configuration, where color intensity indicates the average cumulative changeability cost of the feedback when a solution is found. Black regions correspond to parameter settings where no actionable feedback is generated, while dark regions indicate simpler and more interpretable feedback. Comparing tree constructions, entropy-based trees produce higher costs and larger infeasible regions, whereas change-aware constructions reduce both feedback cost and the number of infeasible configurations. Among feedback strategies, change-based search consistently achieves lower costs and smaller infeasible regions than depth-based variants, suggesting better coverage and feedback quality under similar parameters. As modification limits increase, all strategies are able to resolve progressively harder denied requests that require more complex attribute changes, which naturally raises the average feedback cost. This increase reflects improved coverage rather than reduced efficiency. With very small limits, feedback is concise but applies only to requests close to an allow state, while larger limits improve feasibility at the expense of more complex and less interpretable feedback. The selected parameter values therefore balance coverage with feedback simplicity, as summarized in Table 11. A.3
Visibility Constraints in Effect
To illustrate the effect of visibility constraints, Figure 5 presents a concrete policy tree example. The request corresponds to a user with role=manager, clearance=medium, department=HR, and training over=yes, requesting access to 16
EXTree: Towards Supporting Explainability in Attribute-based Access Control
(a) Entropy-based
(b) High-change-cost-first
(c) Low-change-cost-first
Figure 4: Cumulative feedback cost heatmaps grouped by tree construction strategy. Within each block, the four feedback strategies (top-left to bottom-right) are: depth-best, depth-first, change-best, and change-first. Table 11: Optimal parameters found through grid search. Dataset Optimal (max changes, max depth) Synthetic-1 Synthetic-2 ABACLab Healthcare
(4, 30) (8, 30) (3, 5)
a medium-sensitivity resource; the initial decision is D ENY. Without visibility constraints (Figure 5a), the minimumcost explanation modifies the department attribute from HR to Finance, yielding a total cost of 50. When visibility constraints are applied (Figure 5b), specific attribute–value pairs (clearance=medium, clearance=high, and department=Finance) are hidden. Paths going through these predicates are now infeasible due to infinite traversal cost, eliminating the earlier optimal explanation. Feedback generation instead selects an alternative feasible path that modifies clearance from medium to low at a higher cost of 70. This example shows how visibility constraints can be enforced in evaluation without changing policy structure.
17
EXTree: Towards Supporting Explainability in Attribute-based Access Control
(a) Without visibility constraints
(b) With visibility constraints
Figure 5: Effect of visibility constraints.
18