# Understanding XACML combining algorithms

The XACML policy language uses three structural elements: policy sets, policies, and rules. A policy set can contain any number of policies and policy sets. Policies, in turn, can contain multiple rules. Rules define the desired effect, either of **Permit** or **Deny**.

If a policy contains multiple rules, and the rules return different decisions e.g. **Permit **and **Deny**, what should the policy return? Permit? Deny? Neither?

Similarly, if a policy set contains multiple policies (and policy sets) and those policies return different decisions, what should the policy set return?

This is where combining algorithms step in. They are here to help combine the decisions produced by different children of a parent policy (or policy set) into a single decision that the given policy will return to its own parent.

Technically speaking, there are two types of combining algorithms:

- policy combining algorithms: these are defined inside a policy set and serve to combine the results of policies and policy sets.
- rule combining algorithms: these are defined inside a policy and serve to combine the results of rules.

You can refer to the official definition of combining algorithms in the XACML 3.0 specification.

### Example

Imagine the following policy:

- Policy: role==manager AND action==view AND resourceType==document
- Rule 1: deny if documentOwner != userId
- Rule 2: permit

In simple English, the policy above means “*a manager can view a document he/she owns.*” But how do we know how to combine the **Deny **decision stemming from the lack of ownership with the **Permit** decision in the second rule? This is where we will add a rule combining algorithm. In this example, either of first-applicable or deny-overrides will work. Let’s see what these mean.

## Combining algorithms in detail

The latest core specification of XACML defines the list of combining algorithms. The full-blown identifiers can be found hereafter and in section B.9. Let’s walk through each one and explain their behavior.

- Standard combining algorithms
- urn:oasis:names:tc:xacml:3.0:rule-combining-algorithm:deny-overrides
- urn:oasis:names:tc:xacml:3.0:policy-combining-algorithm:deny-overrides
- urn:oasis:names:tc:xacml:3.0:rule-combining-algorithm:permit-overrides
- urn:oasis:names:tc:xacml:3.0:policy-combining-algorithm:permit-overrides
- urn:oasis:names:tc:xacml:1.0:rule-combining-algorithm:first-applicable
- urn:oasis:names:tc:xacml:1.0:policy-combining-algorithm:first-applicable
- urn:oasis:names:tc:xacml:1.0:policy-combining-algorithm:only-one-applicable
- urn:oasis:names:tc:xacml:3.0:rule-combining-algorithm:ordered-deny-overrides
- urn:oasis:names:tc:xacml:3.0:policy-combining-algorithm:ordered-deny-overrides
- urn:oasis:names:tc:xacml:3.0:rule-combining-algorithm:ordered-permit-overrides
- urn:oasis:names:tc:xacml:3.0:policy-combining-algorithm:ordered-permit-overrides
- urn:oasis:names:tc:xacml:3.0:rule-combining-algorithm:deny-unless-permit
- urn:oasis:names:tc:xacml:3.0:rule-combining-algorithm:permit-unless-deny
- urn:oasis:names:tc:xacml:3.0:policy-combining-algorithm:deny-unless-permit
- urn:oasis:names:tc:xacml:3.0:policy-combining-algorithm:permit-unless-deny

- Legacy combining algorithms
- urn:oasis:names:tc:xacml:1.0:rule-combining-algorithm:deny-overrides
- urn:oasis:names:tc:xacml:1.0:policy-combining-algorithm:deny-overrides
- urn:oasis:names:tc:xacml:1.0:rule-combining-algorithm:permit-overrides
- urn:oasis:names:tc:xacml:1.0:policy-combining-algorithm:permit-overrides
- urn:oasis:names:tc:xacml:1.1:rule-combining-algorithm:ordered-deny-overrides
- urn:oasis:names:tc:xacml:1.1:policy-combining-algorithm:ordered-deny-overrides
- urn:oasis:names:tc:xacml:1.1:rule-combining-algorithm:ordered-permit-overrides
- urn:oasis:names:tc:xacml:1.1:policy-combining-algorithm:ordered-permit-overrides

### XACML 3.0 combining algorithms

#### Deny overrides

This combining algorithm combines decisions in such a way that if any decision is a Deny, then that decision wins. The following identifiers are deny overrides combining algorithms:

- Rule: urn:oasis:names:tc:xacml:3.0:rule-combining-algorithm:deny-overrides
- Policy (set): urn:oasis:names:tc:xacml:3.0:policy-combining-algorithm:deny-overrides

In our example, if we use deny-overrides, and if the user trying to view the document does not own the document, then the user will not get access.

Deny overrides is one of the safest combining algorithms since it favors a Deny decision. However, if none of the children return a Deny decision, then the combining algorithm will never produce a Deny.

#### Permit overrides

This combining algorithm combines decisions in such a way that if any decision is a Permit, then that decision wins. The following identifiers are permit overrides combining algorithms:

- urn:oasis:names:tc:xacml:3.0:rule-combining-algorithm:permit-overrides
- urn:oasis:names:tc:xacml:3.0:policy-combining-algorithm:permit-overrides

In our example, if we use permit-overrides, and if the user trying to view the document does not own the document, then the user will get access nonetheless. It is clear that in this example, permit overrides is not the right combining algorithm to use.

The permit overrides combining algorithm can be interesting when:

- at least one child must return a Permit for access to be granted overall regardless of restrictions.
- one wants to return all the reasons why access is being denied. This is what one could call a “greedy deny overrides”. For instance if the reason for not being able to view a document is that (a) you are not the owner and (b) you are in the wrong department, then we could rework the previous example as follows. When any of the deny reason triggers, the response would be deny with all the applicable reasons for access being denied:
- Policy Set (deny overrides): role==manager AND action==view AND resourceType==document
- Policy 1 (permit overrides)
- Rule 1: deny if documentOwner != userId + Advice(“you are not the owner of the document”)
- Rule 2: deny if documentDepartment != userDepartment+ Advice(“you are not in the same department as the document”)

- Policy 2
- Rule 1: permit

- Policy 1 (permit overrides)

- Policy Set (deny overrides): role==manager AND action==view AND resourceType==document

#### First applicable

This combining algorithm combines decisions in such a way that the final decision returned is the first one produced either of Permit or Deny. The following identifiers are first applicable combining algorithms:

- urn:oasis:names:tc:xacml:1.0:rule-combining-algorithm:first-applicable
- urn:oasis:names:tc:xacml:1.0:policy-combining-algorithm:first-applicable

In our example, first applicable is also a good choice. First applicable is useful to shortcut policy evaluation. For instance, if a policy set contains a long series of not applicable policies and one applicable policy which returns either of Permit or Deny, then if that policy comes first and does produce Permit or Deny, the PDP will stop there and not process the other siblings.

#### Only one applicable

This combining algorithm exists only for policy sets to combine policy sets and policies. It cannot be used to combine rules. With this combining algorithm, in order for either of a Permit or Deny to be returned, then only one of the children must produce a valid decision – whether Deny or Permit. The following identifier is the only one applicable identifier:

- urn:oasis:names:tc:xacml:1.0:policy-combining-algorithm:only-one-applicable

A good example for only one applicable is as follows:

- global policy set (only one applicable)
- policy set about design documents
- policy set about purchase orders
- policy set about contracts

In the above example, all three policies are orthogonal and independent. Therefore an authorization request should only ever be about a single resource type hence the use of only one applicable.

In practice, it is more efficient and more common to use first applicable rather than only one applicable. The latter forces the PDP to check all 3 policies even if the first one already applied.

#### Ordered combining algorithms (ordered-deny-overrides and ordered-permit-overrides)

The ordered combining algorithms combine decisions in the same way as their (unordered) cousins. In addition they bring the guarantee that policies, policy sets, and rules are considered in the order in which they are defined. The need to define an ordered combining algorithm stems from the fact the XACML specification does not specify whether order matters in the deny-overrides and permit-overrides combining algorithms. The following identifiers are ordered combining algorithms:

- urn:oasis:names:tc:xacml:3.0:rule-combining-algorithm:ordered-deny-overrides
- urn:oasis:names:tc:xacml:3.0:policy-combining-algorithm:ordered-deny-overrides
- urn:oasis:names:tc:xacml:3.0:rule-combining-algorithm:ordered-permit-overrides
- urn:oasis:names:tc:xacml:3.0:policy-combining-algorithm:ordered-permit-overrides

We could rewrite the example using the ordered-deny-overrides or the ordered-permit-overrides algorithms. The result would be the same. Note that in the Axiomatics Policy Server, deny-overrides and ordered-deny-overrides are treated the same way. Similarly permit-overrides and ordered-permit-overrides are also treated the same way.

#### Deny unless permit and Permit unless deny combining algorithms

In XACML there are 4 possible decisions: Permit, Deny, NotApplicable, and Indeterminate. Sometimes, it is desirable to hide the NotApplicable and Indeterminate decisions to only allow for Permit or Deny. It makes the PEP logic potentially simpler.

To achieve this, one can use the deny unless permit or permit unless deny combining algorithms. The following are the relevant identifiers:

- urn:oasis:names:tc:xacml:3.0:rule-combining-algorithm:deny-unless-permit
- urn:oasis:names:tc:xacml:3.0:rule-combining-algorithm:permit-unless-deny
- urn:oasis:names:tc:xacml:3.0:policy-combining-algorithm:deny-unless-permit
- urn:oasis:names:tc:xacml:3.0:policy-combining-algorithm:permit-unless-deny

With these combining algorithms we guarantee that either Permit or Deny will be returned. In the following example, we can make sure Deny is returned if the authorization request is not about documents, purchase orders, or contracts:

- global policy set (deny unless permit)
- policy set about design documents
- policy set about purchase orders
- policy set about contracts

### Legacy combining algorithms

Before XACML 3.0 was published, there were older combining algorithms, now called legacy combining algorithms. These are:

- urn:oasis:names:tc:xacml:1.0:rule-combining-algorithm:deny-overrides
- urn:oasis:names:tc:xacml:1.0:policy-combining-algorithm:deny-overrides
- urn:oasis:names:tc:xacml:1.0:rule-combining-algorithm:permit-overrides
- urn:oasis:names:tc:xacml:1.0:policy-combining-algorithm:permit-overrides
- urn:oasis:names:tc:xacml:1.1:rule-combining-algorithm:ordered-deny-overrides
- urn:oasis:names:tc:xacml:1.1:policy-combining-algorithm:ordered-deny-overrides
- urn:oasis:names:tc:xacml:1.1:rule-combining-algorithm:ordered-permit-overrides
- urn:oasis:names:tc:xacml:1.1:policy-combining-algorithm:ordered-permit-overrides

In cases where an Indeterminate is produced these combining algorithms do not return whether the Indeterminate occured in a Permit or a Deny scenario. This Permit or Deny annotation may be important when evaluating policies.

This is why Axiomatics strongly recommends the legacy algorithms **not be used** in any of the policies.

### Optional combining algorithms

In addition to the combining algorithms belonging to the core specification, a new combining algorithm was recently defined within the OASIS XACML Technical Committee. Its draft specification can be found here.

Its identifier is:

- urn:oasis:names:tc:xacml:3.0:policy-combining-algorithm:on-permit-apply-second

## Combining algorithms truth tables

Deny-overrides | 1. First choose the column below | ||||||

2. Then choose the row | Permit | Deny | NotApplicable | Indeterminate (D) | Indeterminate (P) | Indeterminate (DP) | |

Permit | Permit | Deny | Permit | Indeterminate (D) | Permit | Indeterminate (DP) | |

Deny | Deny | Deny | Deny | Deny | Deny | Deny | |

NotApplicable | Permit | Deny | NotApplicable | Indeterminate (D) | Indeterminate (P) | Indeterminate (DP) | |

Indeterminate (D) | Indeterminate (D) | Deny | Indeterminate (D) | Indeterminate (D) | Indeterminate | Indeterminate (DP) | |

Indeterminate (P) | Permit | Deny | Indeterminate (P) | Indeterminate (DP) | Indeterminate (P) | Indeterminate (DP) | |

Indeterminate (DP) | Indeterminate (DP) | Deny | Indeterminate (DP) | Indeterminate (DP) | Indeterminate (DP) | Indeterminate (DP) | |

Permit-overrides | 1. First choose the column below | ||||||

2. Then choose the row | Permit | Deny | NotApplicable | Indeterminate (D) | Indeterminate (P) | Indeterminate (DP) | |

Permit | Permit | Permit | Permit | Permit | Permit | Permit | |

Deny | Permit | Deny | Deny | Deny | Indeterminate (P) | Indeterminate (DP) | |

NotApplicable | Permit | Deny | NotApplicable | Indeterminate (D) | Indeterminate (P) | Indeterminate (DP) | |

Indeterminate(D) | Permit | Deny | Indeterminate (D) | Indeterminate (D) | Indeterminate (DP) | Indeterminate (DP) | |

Indeterminate (P) | Permit | Indeterminate (P) | Indeterminate (P) | Indeterminate (DP) | Indeterminate (P) | Indeterminate (DP) | |

Indeterminate (DP) | Permit | Indeterminate (DP) | Indeterminate (DP) | Indeterminate (DP) | Indeterminate (DP) | Indeterminate (DP) | |

deny-unless-permit | 1. First choose the column below | ||||||

2. Then choose the row | Permit | Deny | NotApplicable | Indeterminate (D) | Indeterminate (P) | Indeterminate (DP) | |

Permit | Permit | Permit | Permit | Permit | Permit | Permit | |

Deny | Permit | Deny | Deny | Deny | Deny | Deny | |

NotApplicable | Permit | Deny | Deny | Deny | Deny | Deny | |

Indeterminate (D) | Permit | Deny | Deny | Deny | Deny | Deny | |

Indeterminate (P) | Permit | Deny | Deny | Deny | Deny | Deny | |

Indeterminate (DP) | Permit | Deny | Deny | Deny | Deny | Deny | |

Permit-unless-deny | 1. First choose the column below | ||||||

2. Then choose the row | Permit | Deny | NotApplicable | Indeterminate (D) | Indeterminate (P) | Indeterminate (DP) | |

Permit | Permit | Deny | Permit | Permit | Permit | Permit | |

Deny | Deny | Deny | Deny | Deny | Deny | Deny | |

NotApplicable | Permit | Deny | Permit | Permit | Permit | Permit | |

Indeterminate (D) | Permit | Deny | Permit | Permit | Permit | Permit | |

Indeterminate (P) | Permit | Deny | Permit | Permit | Permit | Permit | |

Indeterminate (DP) | Permit | Deny | Permit | Permit | Permit | Permit | |

first-applicable | 1. First choose the column below | ||||||

2. Then choose the row | Permit | Deny | NotApplicable | Indeterminate (D) | Indeterminate (P) | Indeterminate (DP) | |

Permit | Permit | Deny | Permit | Indeterminate (D) | Indeterminate (P) | Indeterminate (DP) | |

Deny | Permit | Deny | Deny | Indeterminate (D) | Indeterminate (P) | Indeterminate (DP) | |

NotApplicable | Permit | Deny | NotApplicable | Indeterminate (D) | Indeterminate (P) | Indeterminate (DP) | |

Indeterminate (D) | Permit | Deny | Indeterminate (D) | Indeterminate (D) | Indeterminate (P) | Indeterminate (DP) | |

Indeterminate (P) | Permit | Deny | Indeterminate (P) | Indeterminate (D) | Indeterminate (P) | Indeterminate (DP) | |

Indeterminate (DP) | Permit | Deny | Indeterminate (DP) | Indeterminate (D) | Indeterminate (P) | Indeterminate (DP) | |

ordered-deny-overrides | 1. First choose the column below | ||||||

2. Then choose the row | Permit | Deny | NotApplicable | Indeterminate (D) | Indeterminate (P) | Indeterminate (DP) | |

Permit | Permit | Deny | Permit | Indeterminate | Permit | ||

Deny | Deny | Deny | Deny | Deny | Deny | Deny | |

NotApplicable | Permit | Deny | NotApplicable | Indeterminate (D) | Indeterminate (P) | Indeterminate (DP) | |

Indeterminate (D) | Indeterminate | Deny | Indeterminate (D) | Indeterminate (D) | Indeterminate (D) | Indeterminate (DP) | |

Indeterminate (P) | Permit | Deny | Indeterminate (P) | Indeterminate (D) | Indeterminate (P) | Indeterminate (DP) | |

Indeterminate (DP) | Indeterminate (DP) | Deny | Indeterminate (DP) | Indeterminate (D) | Indeterminate (D) | Indeterminate (DP) | |

ordered-permit-overrides | 1. First choose the column below | ||||||

2. Then choose the row | Permit | Deny | NotApplicable | Indeterminate (D) | Indeterminate (P) | Indeterminate (DP) | |

Permit | Permit | Permit | Permit | Permit | Permit | Permit | |

Deny | Permit | Deny | Deny | Deny | Indeterminate (P) | Indeterminate (DP) | |

NotApplicable | Permit | Deny | NotApplicable | Indeterminate (D) | Indeterminate (P) | Indeterminate (DP) | |

Indeterminate(D) | Permit | Deny | Indeterminate (D) | Indeterminate (D) | Indeterminate (DP) | Indeterminate (DP) | |

Indeterminate (P) | Permit | Indeterminate (P) | Indeterminate (P) | Indeterminate (DP) | Indeterminate (P) | Indeterminate (DP) | |

Indeterminate (DP) | Permit | Indeterminate (DP) | Indeterminate (DP) | Indeterminate (DP) | Indeterminate (DP) | Indeterminate (DP) | |

only-one-applicable | 1. First choose the column below | ||||||

2. Then choose the row | Permit | Deny | NotApplicable | Indeterminate (D) | Indeterminate (P) | Indeterminate (DP) | |

Permit | Indeterminate | Indeterminate | Permit | Indeterminate (D) | Indeterminate (P) | Indeterminate (DP) | |

Deny | Indeterminate | Indeterminate | Deny | Indeterminate (D) | Indeterminate (P) | Indeterminate (DP) | |

NotApplicable | Permit | Deny | NotApplicable | Indeterminate (D) | Indeterminate (P) | Indeterminate (DP) | |

Indeterminate (D) | Indeterminate (D) | Indeterminate (D) | Indeterminate (D) | Indeterminate (D) | Indeterminate (DP) | Indeterminate (DP) | |

Indeterminate (P) | Indeterminate (P) | Indeterminate (P) | Indeterminate (P) | Indeterminate (DP) | Indeterminate (P) | Indeterminate (DP) | |

Indeterminate (DP) | Indeterminate (DP) | Indeterminate (DP) | Indeterminate (DP) | Indeterminate (DP) | Indeterminate (DP) | Indeterminate (DP) | |

Note: the combining algorithm ‘only-one-applicable’ is only available for policy sets. |

## Combining algorithms supported in the Axiomatics Policy Server

The Axiomatics Policy Server supports all the core combining algorithms, the legacy combining algorithms, and the optional combining algorithms as described in this article.