Attribute-Based Policy Evaluation and Combining Algorithms

Role-based control answers “which role does this principal hold” and stops there. Attribute-based control answers a wider question: given any set of properties of the principal, the resource, the action, and the environment, does the request satisfy policy? The generalization buys expressiveness and pays for it in evaluation complexity, in the number of ways a decision can fail to be a plain yes or no, and in a specification whose combining semantics are subtle enough that two conforming implementations can disagree about the same policy.

The request context and where attributes come from

An ABAC decision starts from a request context: a structured record naming the subject, the resource, the action, and the environment, each carrying attributes. A subject might carry a department, a clearance level, and a set of project memberships. A resource might carry a classification, an owner, and a retention date. The environment might carry the time of day, the network zone, and whether the connection is authenticated with a hardware token.

Attributes are not usually stored in the policy. They are resolved at decision time from policy information points: a directory, an HR system, a resource catalogue, a token. This indirection is the model’s strength, because a change in the HR system propagates into every decision without editing policy, and its principal operational risk, because the decision now depends on services that can be slow, unavailable, or wrong.

The specification distinguishes attributes that are required for a decision from those that are merely available. When a policy references an attribute the resolver cannot supply, the result is not a deny; it is indeterminate, a distinct outcome that carries the reason. Conflating indeterminate with deny is a common shortcut and it changes behaviour: an outage in an attribute source becomes a blanket refusal rather than a partial evaluation.

Rules, targets, and the four effects

A policy is a tree. At the leaf, a rule has an effect of Permit or Deny and an optional condition. Rules are grouped into policies, which have targets, and policies are grouped into policy sets, which also have targets. A target is a coarse predicate evaluated against the request context; if it does not match, the whole subtree is skipped without evaluating conditions. The target exists as a performance device as much as a semantic one, and it is the reason a policy set with a hundred unrelated policies does not cost a hundred condition evaluations per request.

Each rule, policy, and policy set evaluates to one of four values: Permit, Deny, NotApplicable, or Indeterminate. NotApplicable means the target did not match or no rule applied. Indeterminate means evaluation could not complete, typically from a missing attribute or an error in a condition. The four-valued algebra is the part of the model most often simplified away by implementers, and simplifying it is where behaviour diverges.

A condition can reference attributes and combine them with comparison and set functions. The specification defines a data-type system with functions for string, boolean, integer, double, date and time, and the URI and DNS name types, plus higher-order functions over bags. Bags matter: an attribute is a multiset of values, so a condition asking whether the subject’s project set contains the resource’s project is a set intersection test rather than an equality test on a scalar.

Combining algorithms and their disagreements

When a policy set contains several policies, a combining algorithm reduces their effects to one. The standard defines a family, and the differences are not cosmetic.

Deny-overrides returns Deny if any element returns Deny; otherwise Permit if any returns Permit; otherwise NotApplicable. Permit-overrides is the mirror. First-applicable evaluates elements in declaration order and returns the first non-NotApplicable result. Deny-unless-permit returns Deny for anything that is not an explicit Permit, which is the strictest of the common choices. Permit-unless-deny is its mirror.

The interesting divergence is how each treats Indeterminate. Under deny-overrides, an Indeterminate element combined with a Permit element yields Indeterminate, not Permit, because a later Deny could have overridden it. Under first-applicable, an Indeterminate element stops evaluation and the result is Indeterminate, even if a later element would have returned a definite Deny. Under permit-overrides, an Indeterminate combined with a Deny also yields Indeterminate.

Implementations that flatten Indeterminate to NotApplicable before combining get a different answer in exactly these mixed cases. The specification defines extended versions of several algorithms that make the treatment of Indeterminate explicit, and choosing between the base and extended form is a decision the policy author is supposed to make deliberately.

The practical consequence is that a policy set is only portable between engines if the authors have agreed on which algorithm and which Indeterminate convention is in force. A set tested under deny-overrides in one product and deployed under first-applicable in another can permit requests the tests rejected, with no change to any policy document. Pinning the algorithm identifier in the policy set, rather than inheriting a platform default, is the only way to keep the two in step.

<PolicySet PolicySetId="ps:records" PolicyCombiningAlgId="...:deny-overrides">
  <Target>
    <AnyOf><AllOf><Match MatchId="...:string-equal">
      <AttributeValue DataType="...:string">patient-record</AttributeValue>
      <AttributeDesignator Category="...:resource"
                           AttributeId="resource-type" MustBePresent="true"/>
    </Match></AllOf></AnyOf>
  </Target>
  <Policy PolicyId="p:treating-physician" RuleCombiningAlgId="...:deny-overrides">
    <!-- rules here -->
  </Policy>
</PolicySet>

Note MustBePresent="true" on the designator: it converts a missing attribute from NotApplicable into Indeterminate. That single attribute is often the difference between a policy that fails closed and one that silently stops applying when an attribute source is misconfigured.

Obligations, advice, and the enforcement gap

A decision can carry obligations: actions the enforcement point must perform for the decision to be honoured. A permit may be conditional on logging the access, on masking certain fields in the response, or on attaching a watermark. Advice is the weaker form: information the enforcement point may act on.

Obligations are where the specification’s clean decision model meets implementation reality. The decision point returns “Permit with obligation to log”; if the enforcement point cannot log, the correct behaviour is to treat the permit as not usable. Many enforcement points instead return the resource and drop the obligation, which converts an audited access into an unaudited one while the policy author believes otherwise. The obligation is part of the decision, not a comment on it.

The same gap appears with attribute freshness. The decision is a function of attribute values at evaluation time. If the enforcement point caches decisions, it caches the attribute state as well, and any attribute change, including a revocation, is invisible until the cache entry expires. The time-to-revoke is therefore set by the cache lifetime, and that number belongs in the policy documentation rather than in a tuning file.

What the model costs

Evaluation is worst-case proportional to the size of the policy tree, though targets prune most of it in practice. Attribute resolution adds a latency term per distinct attribute, and those terms are usually network round trips. A decision that consults four sources is four chances at a timeout, and the timeout policy is itself a security decision: fail closed on a slow directory and the system becomes unavailable during an outage of a system that has nothing to do with the request.

Authoring is the other cost. A policy set with deny-overrides semantics has no local reasoning property: adding a policy can only remove permissions, never add them, which is safe but makes incremental grants impossible without restructuring. First-applicable restores locality at the price of order-dependence, where moving a policy changes outcomes and the order is not visible in any single policy’s text.

The expressiveness that motivates ABAC also makes it hard to answer questions about it. “Who can read this record” is a query over all policies and all possible attribute assignments, and the general problem is not decidable in useful time for a rich condition language. Practical systems answer it by evaluating against a snapshot of current attributes, which is a different question from the one auditors usually mean. Where the requirement is provable confinement rather than declarative policy, the capability approach gives a stronger structural answer, and where the policy must be reasoned about as a program, policy-as-code engines take over.