Source-linked AI summary
Mining Attribute-Based Access Control Policies from Logs
Zhongyuan Xu, Scott D. Stoller
TL;DR
Manual ABAC policy development is costly, and existing ACL or RBAC policies may be unavailable while logs reveal only partial entitlements. The paper introduces an algorithm that mines ABAC policies from logs and attribute data, achieving strong policy reconstruction in evaluated case studies and synthetic policies despite incomplete logs.
Problem
ACL or RBAC policies may be unavailable, while logs provide only a lower bound on entitlements and therefore require mining methods that permit over-assignments.
Method
The algorithm builds candidate rules from logged user-permission tuples, generalizes them with attribute constraints, then merges, simplifies, and selects high-quality rules.
Results
At 100% log completeness, all four case study policies were reconstructed exactly, while synthetic-policy semantic similarity was 0.99; semantic similarity exceeded 0.85 at 60% completeness or higher.
Takeaways & Limitations
The mined policy is sufficiently similar to the desired policy to serve as a useful starting point for policy administrators even when logs reflect only a fraction of entitlements.
Takeaways & Limitations
The current noise detector does not distinguish over-assignment noise from attribute noise, leaving analysts to determine the source of suspected errors.
Abstract
from arXiv · showhide
Attribute-based access control (ABAC) provides a high level of flexibility that promotes security and information sharing. ABAC policy mining algorithms have potential to significantly reduce the cost of migration to ABAC, by partially automating the development of an ABAC policy from information about the existing access-control policy and attribute data. This paper presents an algorithm for mining ABAC policies from operation logs and attribute data. To the best of our knowledge, it is the first algorithm for this problem.
1 Introduction
ABAC policy mining addresses the difficulty and expense of manually developing initial policies, especially when existing policies are unavailable and logs provide incomplete entitlement information. The paper presents an algorithm that mines ABAC policies from logs and attribute data while permitting over-assignments.
- Manual development of an initial ABAC policy can be difficult and expensive, motivating partially automated migration to ABAC.
- Unlike the active RBAC policy-mining area, relatively little work had addressed ABAC policy mining from logs.
- Operation logs provide an alternative policy source when ACL or RBAC policies are unavailable because access control is encoded in programs or non-computerized mechanisms.
- Logs generally provide only a lower bound on entitlements, so mined policies must be allowed to include over-assignments not reflected in the logs.
- The algorithm seeds candidate rules from user-permission tuples, generalizes them with attribute constraints, then merges, simplifies, and selects high-quality rules.
- Evaluation on handwritten case studies and synthetic policies demonstrates effectiveness even when logs reflect only a fraction of entitlements.
2 ABAC policy language
The paper uses an ABAC language built around user and resource attributes, attribute expressions, constraints, operations, and rules. Its semantics determine which user-resource-operation tuples a rule or policy permits.
- The adopted ABAC language contains common constructs but excludes arithmetic inequalities and negation, which are left for future work.
- User and resource attribute data are represented by functions, with attributes partitioned into single-valued and multi-valued categories.
- Attribute expressions characterize users or resources by constraining attribute values, while ⊤ indicates that an attribute is unconstrained.
- For multi-valued user attributes, satisfaction uses set containment so a user may possess specified capabilities and additional values.
- A constraint is a conjunction of atomic relationships between user and resource attributes, such as specialties ⊇topics or teams ∋ treatingTeam.
- A user-permission tuple records a user, resource, and operation, and the relation induced by a rule or policy contains the tuples satisfying it.
- A rule combines user- and resource-attribute expressions, operations, and a constraint, and a policy is a set of such rules over the defined users, resources, and operations.
3 Problem Definition
The mining problem takes users, resources, operations, attribute data, and an operation log as input, then seeks a high-quality ABAC rule set. Quality balances policy concision with over- and under-assignments relative to logged permissions.
- An operation log is a sequence of timestamped user-resource-operation entries, inducing a user-permission relation by removing timestamps.
- The mining input contains users, resources, operations, user and resource attributes, attribute data, and an operation log; the goal is to maximize policy quality.
- Policy quality rewards smaller weighted structural complexity because concise policies are considered more manageable.
- Over-assignments are policy-permission tuples absent from the log relation, whereas under-assignments are logged tuples absent from the policy relation.
- The quality metric combines structural complexity with weighted over-assignment and under-assignment terms.
- Relative tuple frequency weights under-assignments independently of monitoring duration and reflects how often permissions occur in the log.
- The presentation assumes attribute data remains unchanged during the log period, although changing attributes can be accommodated by redefining quality over covered log entries.
4 Algorithm
The algorithm summarizes logs as user-permission relations and frequencies, builds rules from uncovered seeds, generalizes them using attribute relationships, and then improves and selects the resulting candidates. Its quality measures reward coverage and compactness while penalizing over-assignments.
- Algorithm overview: The algorithm ignores log-entry order and summarizes the log using the induced user-permission relation and tuple frequencies.
- Algorithm overview: The top-level procedure repeatedly selects an uncovered tuple as a seed, generates candidate rules, and tracks tuples not yet covered by candidate rules.
- Candidate construction: addCandRule constructs user- and resource-attribute expressions, generalizes the resulting rule, and adds the generalized candidate to Rules.
- Candidate construction: computeUAE characterizes a user set while preferring attribute expressions that avoid uid and removing redundant supersets in multi-valued conjuncts.
- Rule generalization: generalizeRule replaces attribute conjuncts with relationships, producing a more general rule whose induced permissions form a superset of the original rule’s permissions.
- Quality and refinement: Rule quality favors covering more currently uncovered tuples and having smaller size, with a penalty for over-assignments weighted by w′.
- Quality and refinement: The algorithm can use frequency-sensitive and ILP-based rule-quality variants in addition to its basic metric.
- Quality and refinement: mergeRules removes redundant rules or merges pairs when the resulting policy improves quality and introduces no over-assignments.
5 Functions to Simplify Rules
The algorithm simplifies mined rules by removing unnecessary values, conjuncts, constraints, operations, and redundant rules while preserving validity and reducing WSC. It also generalizes and merges rules when possible, with the example illustrating both over-assignment avoidance and exact recovery of the original rule.
- Simplifying Rules: simplifyRules repeatedly applies elimination functions to simplify rules in place and reports whether any rule changed.It invokes elimRedundantSets, elimConjuncts, elimElements, and elimConstraints across the rule set.
- Simplifying Rules: elimElements removes elements from multi-valued attribute sets when validity is preserved, without decreasing the tuples satisfying a rule.This follows from the subset-based semantics for multi-valued user attributes.
- Generalization and Merging: mergeRules removes redundant rules and merges compatible rule pairs, while generalization replaces attribute conjuncts with constraints to broaden coverage.Merging and generalization are accepted only when the resulting policy remains valid for the relevant user-permission relation.
- Simplifying Rules: elimOverlapVal and elimOverlapOp reduce WSC by removing values or operations already covered by higher-quality rules.Each removal is conditioned on structural and coverage relationships with another rule.
- Example: In the university example, a merged rule was discarded because it introduced an over-assignment, and simplification produced a rule identical to the original policy rule.The example shows simplification eliminating a rule covered by another after the unsafe merge was rejected.
- Noise Detection: When logs contain suspected over-assignment noise, low-quality rules can be omitted using a threshold and frequency-sensitive quality metrics.This allows generated policies to contain under-assignments rather than propagating suspected noise into the policy.
6 Evaluation Methodology
The evaluation uses synthetic operation logs and attribute data derived from handwritten and synthetic ABAC policies, then compares mined policies with their originals using syntactic and semantic similarity. Log generation includes both straightforward sampling and an efficient summary-based approach, while noise evaluation accounts for attribute-related changes.
- Evaluation setup: The study evaluates policy-mining algorithms on synthetic operation logs generated from handwritten and synthetic ABAC policies, enabling comparison with the original policies.The authors note that evaluation on actual logs and attribute data remains future work.
- Evaluation setup: Four case studies cover university, health care, project management, and online video access-control policies.The case studies contain relatively small but non-trivial policies; the first three have about 10 ± 1 rules, while online video has 6.
- Evaluation setup: Synthetic attribute datasets for the first three case studies are parameterized by N, representing departments or wards, while online video uses no synthetic dataset because its rules are simpler.The generated datasets contain more instances associated with each department or ward than the manually written datasets.
- Log generation: The straightforward log generator samples rules and satisfying user-permission tuples until a specified completeness is reached, using distributions over rules, operations, users, and resources.Completeness is the fraction of policy user-permission tuples appearing in at least one log entry.
- Log generation: Because skewed distributions make high-completeness logs inefficient to generate, experiments use a log-summary approach that exploits the mining algorithm’s insensitivity to log-entry order.Alternative user, resource, and operation distributions provide less control but are simpler and more convenient.
- Metrics: Policy quality is assessed with syntactic similarity and semantic similarity, although high syntactic similarity is not always desirable for unnecessarily complicated synthetic policies.Syntactic similarity compares rule structure, whereas semantic similarity compares the entitlements granted by the policies.
- Noise: Noise evaluation includes permission changes caused by attribute noise because the current detector does not distinguish attribute noise from over-assignment noise.Policy analysts must determine whether reported suspected errors reflect permissions, attributes, or false alarms.
7 Experimental Results
The algorithm performs well as log completeness increases, reconstructing policies accurately while compensating for missing entitlement information. It also outperforms the ILP- and ATM-based alternatives in the reported comparisons.
- At 100% log completeness, all four case-study policies are reconstructed exactly, while synthetic-policy semantic similarity reaches 0.99.The case-study syntactic and semantic similarities are both 1.
- Syntactic similarity exceeds 0.91 at 60% completeness and 0.94 at 70%; mined synthetic policies are also 17% simpler by WSC at full completeness.The mined policies retain 0.99 semantic similarity to the synthetic policies despite their lower structural complexity.
- Semantic similarity exceeds 0.85 at 60% completeness and 0.94 at 80%, reaching 0.95 at 60% in the five-example average.This corresponds to compensating for 87.5% of the incompleteness in that example.
- Over-assignments remain below 0.03 at completeness of at least 60%, while under-assignments stay below 0.05 from 60% for case studies and 80% for synthetic policies.The reported semantic differences arise more from under-assignments than over-assignments.
- Comparison of Rule Quality Metrics: The rule-quality metric Qrul is moderately better overall than Qfreq and significantly better overall than QILP.The comparison covers case studies with manually written attribute data and synthetic policies.
- Comparison with Inductive Logic Programming: The proposed algorithm exactly reconstructs all four manually attributed case studies at full completeness, whereas Progol semantic similarity ranges from 0.37 to 0.93.Progol was configured to learn from positive examples because absent user-permission tuples were omitted as negative examples.
8 Related Work
Prior work covers RBAC policy mining, machine-learning approaches, and related log-based methods, but the paper addresses ABAC mining from logs as a distinct problem. Existing approaches differ in their treatment of attributes, policy structure, and required inputs.
- Prior work on ABAC mining from logs was not identified, so the paper discusses related problems instead.
- The authors’ ACL-based ABAC miner preserves its overall structure when adapted to logs, with differences described elsewhere.
- Association-rule methods are poorly suited because they seek statistically supported probabilistic rules rather than complete, minimum-sized policy coverage.
- Machine-learning approaches learn user-role classifiers from attributes and assignments, whereas ABAC mining does not require pre-specified roles.
- Other log-mining work introduces roles from co-exercised permissions or infers likely RBAC policies, but does not provide the same ABAC setting.
- A related generative approach requires specifying the desired number of rules, which is difficult to predict.
9 Conclusion
The paper concludes that its log- and attribute-based ABAC mining algorithm can produce a useful starting policy despite incomplete reconstruction. Future work targets richer policy constructs, parameter tuning, input-characteristic analysis, and noisy logs.
- Experiments on case studies and synthetic policies show effectiveness even when logs reflect only a fraction of entitlements.
- Although the desired policy is not reconstructed perfectly, the mined policy is sufficiently similar to support administrators developing that policy.
- Future work includes arithmetic inequalities, negation, and improved automated tuning of parameters such as w′o.
- The authors also plan to characterize effectiveness by input and policy complexity and evaluate performance with noisy logs.
A Rule Quality Metric Based On Inductive Logic Programming
This section adapts an inductive-logic-programming quality metric for evaluating candidate ABAC rules and partly generated policies. The method estimates final policy quality while rules are generated incrementally.
- Progol’s IPL algorithm repeatedly generalizes an example into a hypothesized rule and removes examples covered by that rule until none remain.
- When learning from positive data, Progol’s compression metric evaluates theory quality using positive examples, theory size, and a normalization constant.
- Because the complete theory is unknown during generation, policy quality for the eventual rule set is estimated by extrapolation from the rules added so far.
- The adapted algorithm computes candidate-rule quality with the IPL metric while incrementally building both candidate and final rule sets.
- During rule modification, the algorithm evaluates quality using the current candidate-rule set as an estimate of the entire policy.