XACML NG - Text Representation

[steven-legg]

Introduction

This is an experiment in creating a domain-specific language, i.e. a text representation, for XACML artifacts. The end goal would be to provide complete coverage of all the features in XACML NG so that any policy in any representation can be translated to and from this text representation; this isn’t there yet.

I particularly wanted to push the envelope by considering how the capabilities introduced by the Entities profile might be represented. I’ve chosen examples out of the Entities profile and the Separation of Duties profile as test cases.

Before presenting the examples here are some notes on the text representation.

An identifier in the XML representation, which was exclusively a URI in XACML 3.0 but can now make use of shorties, is encapsulated in double quotes. The identifier can still be within double quotes in the text representation. However, in the case where the identifier is just a shortie name it can appear without the quotes.

These are equivalent representations of the identifier for the string data-type:

"http://www.w3.org/2001/XMLSchema#string"
"{string}"
"string"
string

The last form would be the common usage, but we need to retain the full URI as an option because shorties are not required.

In the XML representation it is always clear whether a name is a variable name or a shortie because the name appears in an XML attribute that fixes the context, e.g., a name in a VariableId XML attribute is a variable name and a name in a DataType XML attribute is a shortie. However, in a text representation of a policy these XML attribute cues will be missing, so we need another way to tell them apart. For this text representation I am choosing to distinguish variable names by prefixing a ‘$’ character to the variable name. Variable names are not shorties, though they may end up matching the same pattern.

Even with shorties, an AttributeDesignator or EntityAttributeDesignator is far from convenient in a concise text representation of an expression. We would rather have a simple mnemonic name stand in for an AttributeDesignator or EntityAttributeDesignator instead of quoting the Category, AttributeId and DataType on every usage. EntityAttributeDesignator doesn’t necessarily specify a category so it turns out cleaner to associate an attribute name with just the AttributeId and DataType (and Issuer and MustBePresent, if desired) and nominate the category separately. This is the declaration of the product-code attribute used in the first example:

attribute product-code = {
  AttributeId "urn:example:xacml:product-code",
  DataType "http://www.w3.org/2001/XMLSchema#integer"
}

No issuer is specified and MustBePresent defaults to false. With appropriate shorties the declaration can become:

attribute product-code = {
  AttributeId product-code,
  DataType integer
}

The product-code attribute is a resource attribute so the text representation of an AttributeDesignator for this attribute prepends the identifier for the resource category:

resource.product-code

The shortie for the resource category is assumed to be ‘resource’.

Despite the attribute name being the same as a shortie in this example there is no ambiguity because an attribute name in the text representation is always preceded by a ‘.’ while a shortie never is. Most attributes are associated with only one data-type so it is convenient to use the AttributeId shortie as the attribute name as well in such cases.

With the attribute declared we can now look at the text representation of an expression. An Apply expression is represented in the familiar style of a function call with the function identifier first followed by a comma-separated list of argument expressions within parentheses. The function identifier can be, and typically would be, represented by a shortie.

Certain frequently-used functions have alternative representations as operators. The and and or functions can be represented by the and and or infix operators. The not function can be represented by the not unary operator. The type-equal functions can be represented by the = operator (the type is determined by the arguments). Similarly for the relational operators <, <=, > and >=. The type-add, type-subtract, type-multiply and type-divide functions can be represented by the +, -, * and / operators.

Precedence rules are required for these operators in the absence of parentheses. The following table defines the operator precedence from high to low.

Operator Precedence
()
not, - (negation)
*, /
+, - (subtraction)
>, <, >=, <=
=
and
or

Operators with the same precedence are applied from left to right in an expression. The precedence for the not operator follows typical programming language convention but I’m not convinced that is best for us. We can’t ‘not’ an arithmetic expression, so a precedence between = and and makes more sense.

A parser that follows the ABNF given later will automatically associate arguments according to these precedence rules.

We might also represent integer-mod by % and string-equal-ignore-case by ~=.

The ForAny quantified expression is represented by the keyword any followed by the variable name, domain expression and iterant expression within parentheses and separated by colons. The ForAll, Select and Map quantified expressions follow the same pattern.

Now for the examples. The examples in the Entities Profile are isolated expressions. The Separation of Duties Profile has full policies.

Entities Profile Figure 7

This is the XACML 3.0 expression as it appears in Figure 7 of the Entities Profile with the XML entity references expanded out:

<ForAny VariableId="product-code" xmlns="urn:oasis:names:tc:xacml:3.0:core:schema:wd-17">
  <AttributeDesignator
    Category="urn:oasis:names:tc:xacml:3.0:attribute-category:resource"
    AttributeId="urn:example:xacml:product-code"
    DataType="http://www.w3.org/2001/XMLSchema#integer"
    MustBePresent="false"/>
  <Apply FunctionId="urn:oasis:names:tc:xacml:1.0:function:and">
    <Apply FunctionId="urn:oasis:names:tc:xacml:1.0:function:integer-greater-than-or-equal">
      <VariableReference VariableId="product-code"/>
      <AttributeValue DataType="http://www.w3.org/2001/XMLSchema#integer"
        >100</AttributeValue>
    </Apply>
    <Apply FunctionId="urn:oasis:names:tc:xacml:1.0:function:integer-less-than-or-equal">
      <VariableReference VariableId="product-code"/>
      <AttributeValue DataType="http://www.w3.org/2001/XMLSchema#integer"
        >200</AttributeValue>
    </Apply>
  </Apply>
</ForAny>

Here is a rewriting of the expression for XACML 4.0. The URIs are replaced with shorties and the MustBePresent XML attribute is omitted (default false).

<ForAny VariableId="product-code"
  xmlns="urn:oasis:names:tc:xacml:3.0:core:schema:wd-17">
  <AttributeDesignator
    Category="resource" AttributeId="product-code" DataType="integer"/>
  <Apply FunctionId="and">
    <Apply FunctionId="integer-greater-than-or-equal">
      <VariableReference VariableId="product-code"/>
      <AttributeValue DataType="integer">100</AttributeValue>
    </Apply>
    <Apply FunctionId="integer-less-than-or-equal">
      <VariableReference VariableId="product-code"/>
      <AttributeValue DataType="integer">200</AttributeValue>
    </Apply>
  </Apply>
</ForAny>

A preamble will declare the product-code attribute:

attribute product-code = {
  AttributeId product-code,
  DataType integer
}

A text representation of the expression without using any infix operators is:

any($product-code : resource.product-code :
  and(integer-greater-than-or-equal($product-code, 100),
    integer-less-than-or-equal($product-code, 200)))

With infix operators:

any($product-code : resource.product-code :
  $product-code >= 100 and $product-code <= 200)

The infix operators have single values as arguments (not bags) but if we apply a general assumption of implied existential quantification (the any expression above is explicit existential quantification) we can compare bags to single values and bags to bags. This assumption reduces the text expression to:

resource.product-code >= 100 and resource.product-code <= 200

Entities Profile Figure 9

This is the XACML 3.0 expression as it appears in Figure 9 of the Entities Profile with the XML entity references expanded out:

<ForAny VariableId="relationship" xmlns="urn:oasis:names:tc:xacml:3.0:core:schema:wd-17">
  <AttributeDesignator
    Category="urn:oasis:names:tc:xacml:1.0:subject-category:access-subject"
    AttributeId="urn:example:xacml:attribute:relationship"
    DataType="urn:oasis:names:tc:xacml:3.0:data-type:entity"
    MustBePresent="false"/>
  <Apply FunctionId="urn:oasis:names:tc:xacml:1.0:function:and">
    <Apply FunctionId="urn:oasis:names:tc:xacml:1.0:function:string-equal">
      <Apply FunctionId="urn:oasis:names:tc:xacml:1.0:function:string-one-and-only">
        <Apply FunctionId="urn:oasis:names:tc:xacml:3.0:function:attribute-designator">
          <VariableReference VariableId="relationship"/>
          <AttributeValue DataType="http://www.w3.org/2001/XMLSchema#anyURI"
            >urn:example:xacml:attribute:relationship-kind</AttributeValue>
          <AttributeValue DataType="http://www.w3.org/2001/XMLSchema#anyURI"
            >http://www.w3.org/2001/XMLSchema#string</AttributeValue>
          <AttributeValue DataType="http://www.w3.org/2001/XMLSchema#boolean"
            >true</AttributeValue>
        </Apply>
      </Apply>
      <AttributeValue DataType="http://www.w3.org/2001/XMLSchema#string"
        >employee</AttributeValue>
    </Apply>
    <Apply FunctionId="urn:oasis:names:tc:xacml:1.0:function:date-greater-than-or-equal">
      <Apply FunctionId="urn:oasis:names:tc:xacml:1.0:function:date-one-and-only">
        <AttributeDesignator
          Category="urn:oasis:names:tc:xacml:3.0:attribute-category:environment"
          AttributeId="urn:oasis:names:tc:xacml:1.0:environment:current-date"
          DataType="http://www.w3.org/2001/XMLSchema#date"
          MustBePresent="true"/>
      </Apply>
      <Apply FunctionId="urn:oasis:names:tc:xacml:1.0:function:date-one-and-only">
        <Apply FunctionId="urn:oasis:names:tc:xacml:3.0:function:attribute-designator">
          <VariableReference VariableId="relationship"/>
          <AttributeValue DataType="http://www.w3.org/2001/XMLSchema#anyURI"
            >urn:example:xacml:attribute:start-date</AttributeValue>
          <AttributeValue DataType="http://www.w3.org/2001/XMLSchema#anyURI"
            >http://www.w3.org/2001/XMLSchema#date</AttributeValue>
          <AttributeValue DataType="http://www.w3.org/2001/XMLSchema#boolean"
            >true</AttributeValue>
        </Apply>
      </Apply>
    </Apply>
    <Apply FunctionId="urn:oasis:names:tc:xacml:3.0:function:any-of">
      <Function FunctionId="urn:oasis:names:tc:xacml:1.0:function:string-equal"/>
      <AttributeValue DataType="http://www.w3.org/2001/XMLSchema#string"
        >non-profit</AttributeValue>
      <Apply FunctionId="urn:oasis:names:tc:xacml:3.0:function:attribute-designator">
        <Apply FunctionId="urn:oasis:names:tc:xacml:1.0:function:anyURI-one-and-only">
          <Apply FunctionId="urn:oasis:names:tc:xacml:3.0:function:attribute-designator">
            <VariableReference VariableId="relationship"/>
            <AttributeValue DataType="http://www.w3.org/2001/XMLSchema#anyURI"
              >urn:example:xacml:attribute:organization</AttributeValue>
            <AttributeValue DataType="http://www.w3.org/2001/XMLSchema#anyURI"
              >http://www.w3.org/2001/XMLSchema#anyURI</AttributeValue>
          </Apply>
        </Apply>
        <AttributeValue DataType="http://www.w3.org/2001/XMLSchema#anyURI"
          >urn:example:xacml:attribute:organization-type</AttributeValue>
        <AttributeValue DataType="http://www.w3.org/2001/XMLSchema#anyURI"
          >http://www.w3.org/2001/XMLSchema#string</AttributeValue>
      </Apply>
    </Apply>
  </Apply>
</ForAny>

Here is a rewriting of the expression for XACML 4.0. The URIs are replaced with shorties, the attribute-designator function is replaced by the EntityAttributeDesignator expression and the MustBePresent XML attribute is omitted (default false).

<ForAny VariableId="relationship" xmlns="urn:oasis:names:tc:xacml:3.0:core:schema:wd-17">
  <AttributeDesignator
    Category="access-subject" AttributeId="relationship" DataType="entity"/>
  <Apply FunctionId="and">
    <ForAny VariableId="relationship-kind">
      <EntityAttributeDesignator AttributeId="relationship-kind" DataType="string">
        <VariableReference VariableId="relationship"/>
      </EntityAttributeDesignator>
      <Apply FunctionId="string-equal">
        <VariableReference VariableId="relationship-kind"/>
        <AttributeValue DataType="string">employee</AttributeValue>
      </Apply>
    </ForAny>
    <ForAny VariableId="start-date">
      <EntityAttributeDesignator AttributeId="start-date" DataType="date">
        <VariableReference VariableId="relationship"/>
      </EntityAttributeDesignator>
      <Apply FunctionId="any-of">
        <Function FunctionId="date-greater-than-or-equal"/>
        <AttributeDesignator
          Category="environment" AttributeId="current-date" DataType="date"/>
        <VariableReference VariableId="start-date"/>
      </Apply>
    </ForAny>
    <ForAny VariableId="organization">
      <EntityAttributeDesignator AttributeId="organization" DataType="anyURI">
        <VariableReference VariableId="relationship"/>
      </EntityAttributeDesignator>
      <Apply FunctionId="any-of">
        <Function FunctionId="string-equal"/>
        <AttributeValue DataType="string">non-profit</AttributeValue>
        <EntityAttributeDesignator AttributeId="organization-type" DataType="string">
          <VariableReference VariableId="organization"/>
        </EntityAttributeDesignator>
      </Apply>
    </ForAny>
  </Apply>
</ForAny>

A preamble will declare the attributes used in this example:

attribute relationship = {
  AttributeId relationship,
  DataType entity
}

attribute relationship-kind = {
  attributeId relationship-kind,
  dataType string
}

attribute start-date = {
  attributeId start-date,
  dataType string
}

attribute current-date = {
  attributeId current-date,
  dataType date
}

attribute organization = {
  attributeId organization,
  dataType anyURI
}

attribute organization-type = {
  attributeId organization-type,
  dataType string
}

A text representation of the expression is:

any($relationship : access-subject.relationship :
  any($relationship-kind : $relationship.relationship-kind :
    $relationship-kind = "employee") and
  any($start-date : $relationship.start-date :
    any-of(date-greater-than-or-equal, environment.current-date, $start-date) and
  any($organization : $relationship.organization :
    any-of(string-equal, "non-profit", $organization.organization-type)))

The any-of functions are explicit existential quantification, as are the any expressions. They can all be simplified:

access-subject.relationship.relationship-kind = "employee" and
environment.current-date >= access-subject.relationship.start-date and
access-subject.relationship.organization.organization-type = "non-profit"

This example shows referencing through related and nested entries.

Entities Profile Figure 11

This is the XACML 3.0 expression as it appears in Figure 11 of the Entities Profile with the XML entity references expanded out:

<ForAny VariableId="approved-export" xmlns="urn:oasis:names:tc:xacml:3.0:core:schema:wd-17">
  <AttributeDesignator
    Category="urn:oasis:names:tc:xacml:3.0:attribute-category:environment"
    AttributeId="urn:example:xacml:attribute:approved-export"
    DataType="urn:oasis:names:tc:xacml:3.0:data-type:entity"
    MustBePresent="false"/>
  <Apply FunctionId="urn:oasis:names:tc:xacml:1.0:function:and">
    <Apply FunctionId="urn:oasis:names:tc:xacml:1.0:function:string-is-in">
      <Apply FunctionId="urn:oasis:names:tc:xacml:1.0:function:string-one-and-only">
        <AttributeDesignator
          Category="urn:oasis:names:tc:xacml:3.0:attribute-category:resource"
           AttributeId="urn:example:xacml:attribute:product-type"
          DataType="http://www.w3.org/2001/XMLSchema#string"
          MustBePresent="false"/>
      </Apply>
      <Apply FunctionId="urn:oasis:names:tc:xacml:3.0:function:attribute -designator">
        <VariableReference VariableId="approved-export"/>
        <AttributeValue DataType="http://www.w3.org/2001/XMLSchema#anyURI"
          >urn:example:xacml:attribute:ae--product--type</AttributeValue>
        <AttributeValue DataType="http://www.w3.org/2001/XMLSchema#anyURI"
          >http://www.w3.org/2001/XMLSchema#string</AttributeValue>
      </Apply>
    </Apply>
    <Apply FunctionId="urn:oasis:names:tc:xacml:1.0:function:string-is-in">
      <Apply FunctionId="urn:oasis:names:tc:xacml:1.0:function:string-one-and-only">
        <AttributeDesignator
          Category="urn:oasis:names:tc:xacml:3.0:attribute-category:action"
          AttributeId="urn:example:xacml:attribute:destination"
          DataType="http://www.w3.org/2001/XMLSchema#string"
          MustBePresent="false"/>
      </Apply>
      <Apply FunctionId="urn:oasis:names:tc:xacml:3.0:function:attribute -designator">
        <VariableReference VariableId="approved-export"/>
        <AttributeValue DataType="http://www.w3.org/2001/XMLSchema#anyURI"
          >urn:example:xacml:attribute:ae-destination</AttributeValue>
        <AttributeValue DataType="http://www.w3.org/2001/XMLSchema#anyURI"
          >http://www.w3.org/2001/XMLSchema#string</AttributeValue>
      </Apply>
    </Apply>
  </Apply>
</ForAny>

Here is a rewriting of the expression for XACML 4.0. The URIs are replaced with shorties, the attribute-designator function is replaced by the EntityAttributeDesignator expression and the MustBePresent XML attribute is omitted (default false).

<ForAny VariableId="approved-export" xmlns="urn:oasis:names:tc:xacml:3.0:core:schema:wd-17">
  <AttributeDesignator
    Category="environment" AttributeId="approved-export" DataType="entity"/>
  <Apply FunctionId="and">
    <Apply FunctionId="any-of-any">
      <Function FunctionId="string-equal"/>
      <AttributeDesignator
        Category="resource" AttributeId="product-type" DataType="string"/>
      <EntityAttributeDesignator AttributeId="ae-product-type" DataType="string">
        <VariableReference VariableId="approved-export"/>
      </EntityAttributeDesignator>
    </Apply>
    <Apply FunctionId="any-of-any">
      <Function FunctionId="string-equal"/>
      <AttributeDesignator
        Category="action" AttributeId="destination" DataType="string"/>
      <EntityAttributeDesignator AttributeId="ae-destination" DataType="string">
        <VariableReference VariableId="approved-export"/>
      </EntityAttributeDesignator>
    </Apply>
  </Apply>
</ForAny>

A preamble will declare the attributes used in this example:

attribute approved-export = {
  AttributeId approved-export,
  DataType entity
}

attribute product-type = {
  AttributeId product-type,
  DataType string
}

attribute ae-product-type = {
  AttributeId ae-product-type,
  DataType string
}

attribute destination = {
  AttributeId destination,
  DataType string
}

attribute ae-destination = {
  AttributeId ae-destination,
  DataType string
}

The product-type and ae-product-type are effectively the same thing in different entities and could be unified as a single attribute in practice. The profile kept them separate for clarity. Similarly for the destination and ae-destination attributes.

A text representation of the expression is:

any($approved-export : environment.approved-export :
  any-of-any(string-equal, resource.product-type, $approved-export.ae-product-type) and
  any-of-any(string-equal, action.destination, $approved-export.ae-destination))

Switching to implicit existential quantification:

resource.product-type = environment.approved-export.ae-product-type and
action.destination = environment.approved-export.ae-destination

Entities Profile Figure 12

This is the XACML 3.0 expression as it appears in Figure 12 of the Entities Profile with the XML entity references expanded out:

<ForAll VariableId="product-type" xmlns="urn:oasis:names:tc:xacml:3.0:core:schema:wd-17">
  <AttributeDesignator
    Category="urn:oasis:names:tc:xacml:3.0:attribute-category:resource"
    AttributeId="urn:example:xacml:attribute:product-type"
    DataType="http://www.w3.org/2001/XMLSchema#string"
    MustBePresent="false"/>
  <ForAll VariableId="destination">
    <AttributeDesignator
      Category="urn:oasis:names:tc:xacml:3.0:attribute-category:action"
      AttributeId="urn:example:xacml:attribute:destination"
      DataType="http://www.w3.org/2001/XMLSchema#string"
      MustBePresent="false"/>
    <ForAny VariableId="approved-export">
      <AttributeDesignator
        Category="urn:oasis:names:tc:xacml:3.0:attribute-category:environment"
        AttributeId="urn:example:xacml:attribute:approved-export"
        DataType="urn:oasis:names:tc:xacml:3.0:data-type:entity"
        MustBePresent="false"/>
      <Apply FunctionId="urn:oasis:names:tc:xacml:1.0:function:and">
        <Apply FunctionId="urn:oasis:names:tc:xacml:;1.0:function:string-is-in">
          <VariableReference VariableId="product-type"/>
          <Apply FunctionId="urn:oasis:names:tc:xacml:3.0:function:attribute-designator">
            <VariableReference VariableId="approved-export"/>
            <AttributeValue
              DataType="http://www.w3.org/2001/XMLSchema#anyURI"
              >urn:example:xacml:attribute:ae-product-type</AttributeValue>
            <AttributeValue
              DataType="http://www.w3.org/2001/XMLSchema#anyURI"
              >http://www.w3.org/2001/XMLSchema#string</AttributeValue>
          </Apply>
        </Apply>
        <Apply FunctionId="urn:oasis:names:tc:xacml:1.0:function:string-is-in">
          <VariableReference VariableId="destination"/>
          <Apply FunctionId="urn:oasis:names:tc:xacml:3.0:function:attribute-designator">
            <VariableReference VariableId="approved-export"/>
            <AttributeValue
              DataType="http://www.w3.org/2001/XMLSchema#anyURI"
              >urn:example:xacml:attribute:ae-destination</AttributeValue>
            <AttributeValue
              DataType="http://www.w3.org/2001/XMLSchema#anyURI"
              >http://www.w3.org/2001/XMLSchema#string</AttributeValue>
          </Apply>
        </Apply>
      </Apply>
    </ForAny>
  </ForAll>
</ForAll>

Here is a rewriting of the expression for XACML 4.0. The URIs are replaced with shorties, the attribute-designator function is replaced by the EntityAttributeDesignator expression and the MustBePresent XML attribute is omitted (default false).

<ForAll VariableId="product-type" xmlns="urn:oasis:names:tc:xacml:3.0:core:schema:wd-17">
  <AttributeDesignator
    Category="resource" AttributeId="product-type" DataType="string"/>
  <ForAll VariableId="destination">
    <AttributeDesignator
      Category="action" AttributeId="destination" DataType="string"/>
    <ForAny VariableId="approved-export">
      <AttributeDesignator
        Category="environment" AttributeId="approved-export" DataType="entity"/>
      <Apply FunctionId="and">
        <Apply FunctionId="string-is-in">
          <VariableReference VariableId="product-type"/>
          <EntityAttributeDesignator AttributeId="ae-product-type" DataType="string">
            <VariableReference VariableId="approved-export"/>
          </EntityAttributeDesignator>
        </Apply>
        <Apply FunctionId="string-is-in">
          <VariableReference VariableId="destination"/>
          <EntityAttributeDesignator AttributeId="ae-destination" DataType="string">
            <VariableReference VariableId="approved-export"/>
          </EntityAttributeDesignator>
        </Apply>
      </Apply>
    </ForAny>
  </ForAll>
</ForAll>

A preamble (the same as the preceding example) will declare the attributes used in this example:

attribute product-type = {
  AttributeId product-type,
  DataType string
}

attribute destination = {
  AttributeId destination,
  DataType string
}

attribute approved-export = {
  AttributeId approved-export,
  DataType entity
}

attribute ae-product-type = {
  AttributeId ae-product-type,
  DataType string
}

attribute ae-destination = {
  AttributeId ae-destination,
  DataType string
}

A text representation of the expression is:

all($product-type : resource.product-type :
  all($destination : action.destination :
    any($approved-export : environment.approved-export :
      string-is-in($product-type, $approved-export.ae-product-type) and
      string-is-in($destination, $approved-export.ae-destination))))

Switching to implicit existential quantification:

all($product-type : resource.product-type :
  all($destination : action.destination :
      $product-type = environment.approved-export.ae-product-type and
      $destination = environment.approved-export.ae-destination))

The preceding examples dealt with standalone expressions. The next example is a complete policy.

Separation of Duties Profile Example 8.1

This is the XACML 3.0 policy as it appears in example 8.1 of the Separation of Duties Profile with the XML entity references expanded out:

<Policy xmlns="urn:oasis:names:tc:xacml:3.0:core:schema:wd-17"
  PolicyId="http://example.com/SoD/purchase-orders" Version="1.0"
  RuleCombiningAlgId="urn:oasis:names:tc:xacml:3.0:rule-combining-algorithm:deny-overrides">

  <Description>
    Policy for SoD constraints applicable to purchase orders.
  </Description>

  <!-- The target restricts applicability to purchase order resources. -->
  <Target>
    <AnyOf>
      <AllOf>
        <Match
          MatchId="urn:oasis:names:tc:xacml:3.0:function:anyURI-starts-with">
          <AttributeValue
            DataType="http://www.w3.org/2001/XMLSchema#string"
            >http://example.com/purchase-order/</AttributeValue>
          <AttributeDesignator
            Category="urn:oasis:names:tc:xacml:3.0:attribute-category:resource"
            AttributeId="urn:oasis:names:tc:xacml:1.0:resource:resource-id"
            DataType="http://www.w3.org/2001/XMLSchema#anyURI"
            MustBePresent="false"/>
        </Match>
      </AllOf>
    </AnyOf>
  </Target>

  <!-- Create a bag containing only relevant action history records. -->
  <VariableDefinition VariableId="relevant-history">
    <Select VariableId="record">
      <AttributeDesignator
        Category="urn:oasis:names:tc:xacml:3.0:attribute-category:resource"
        AttributeId="urn:oasis:names:tc:xacml:3.0:sod:attribute:history"
        DataType="urn:oasis:names:tc:xacml:3.0:data-type:entity"
        MustBePresent="false"/>
      <Apply FunctionId="urn:oasis:names:tc:xacml:1.0:function:and">

        <!-- Matching constraint-id. -->
        <Apply FunctionId="urn:oasis:names:tc:xacml:1.0:function:string-is-in">
          <AttributeValue
            DataType="http://www.w3.org/2001/XMLSchema#string"
            >purchase-order</AttributeValue>
          <!-- Fetch the constraint-id from the action history record. -->
          <Apply FunctionId="urn:oasis:names:tc:xacml:3.0:function:attribute-designator">
            <VariableReference VariableId="record"/>
            <AttributeValue
              DataType="http://www.w3.org/2001/XMLSchema#anyURI"
              >urn:oasis:names:tc:xacml:3.0:sod:attribute:constraint-id</AttributeValue>
            <AttributeValue
              DataType="http://www.w3.org/2001/XMLSchema#anyURI"
              >http://www.w3.org/2001/XMLSchema#string</AttributeValue>
          </Apply>
        </Apply>

        <!-- Matching transaction-id. -->
        <Apply FunctionId="urn:oasis:names:tc:xacml:1.0:function:anyURI-at-least-one-member-of">
          <!-- Fetch the transaction-id from the action history record. -->
          <Apply FunctionId="urn:oasis:names:tc:xacml:3.0:function:attribute-designator">
            <VariableReference VariableId="record"/>
            <AttributeValue
              DataType="http://www.w3.org/2001/XMLSchema#anyURI"
              >urn:oasis:names:tc:xacml:3.0:sod:attribute:transaction-id</AttributeValue>
            <AttributeValue
              DataType="http://www.w3.org/2001/XMLSchema#anyURI"
              >http://www.w3.org/2001/XMLSchema#anyURI</AttributeValue>
          </Apply>
          <!-- The resource-id is used as the transaction-id. -->
          <AttributeDesignator
            Category="urn:oasis:names:tc:xacml:3.0:attribute-category:resource"
            AttributeId="urn:oasis:names:tc:xacml:1.0:resource:resource-id"
            DataType="http://www.w3.org/2001/XMLSchema#anyURI"
            MustBePresent="false"/>
        </Apply>

      </Apply>
    </Select>
  </VariableDefinition>

  <!-- A reusable test that the current action is 'raise'. -->
  <VariableDefinition VariableId="action-is-raise">
    <Apply FunctionId="urn:oasis:names:tc:xacml:1.0:function:string-is-in">
      <AttributeValue
        DataType="http://www.w3.org/2001/XMLSchema#string"
        >raise</AttributeValue>
      <AttributeDesignator
        Category="urn:oasis:names:tc:xacml:3.0:attribute-category:action"
        AttributeId="urn:oasis:names:tc:xacml:1.0:action:action-id"
        DataType="http://www.w3.org/2001/XMLSchema#string"
        MustBePresent="false"/>
    </Apply>
  </VariableDefinition>

  <!-- A reusable test that the current action is 'approve'. -->
  <VariableDefinition VariableId="action-is-approve">
    <Apply FunctionId="urn:oasis:names:tc:xacml:1.0:function:string-is-in">
      <AttributeValue
        DataType="http://www.w3.org/2001/XMLSchema#string"
        >approve</AttributeValue>
      <AttributeDesignator
        Category="urn:oasis:names:tc:xacml:3.0:attribute-category:action"
        AttributeId="urn:oasis:names:tc:xacml:1.0:action:action-id"
        DataType="http://www.w3.org/2001/XMLSchema#string"
        MustBePresent="false"/>
    </Apply>
  </VariableDefinition>

  <!-- Rules applicable to raising a purchase order. -->

  <Rule RuleId="raise-only-once" Effect="Deny">
    <Description>
      Make sure the purchase order hasn't already been raised.
    </Description>
    <Condition>
      <Apply FunctionId="urn:oasis:names:tc:xacml:1.0:function:and">
        <VariableReference VariableId="action-is-raise"/>
        <ForAny VariableId="record">
          <VariableReference VariableId="relevant-history"/>
          <Apply FunctionId="urn:oasis:names:tc:xacml:1.0:function:string-is-in">
            <AttributeValue
              DataType="http://www.w3.org/2001/XMLSchema#string"
              >raise</AttributeValue>
            <Apply FunctionId="urn:oasis:names:tc:xacml:3.0:function:attribute-designator">
              <VariableReference VariableId="record"/>
              <AttributeValue
                DataType="http://www.w3.org/2001/XMLSchema#anyURI"
                >urn:oasis:names:tc:xacml:1.0:action:action-id</AttributeValue>
              <AttributeValue
                DataType="http://www.w3.org/2001/XMLSchema#anyURI"
                >http://www.w3.org/2001/XMLSchema#string</AttributeValue>
            </Apply>
          </Apply>
        </ForAny>
      </Apply>
    </Condition>
  </Rule>

  <Rule RuleId="raise-purchase-order" Effect="Permit">
    <Description>
      Allow a purchase order to be raised by any employee.
    </Description>
    <Condition>
      <Apply FunctionId="urn:oasis:names:tc:xacml:1.0:function:and">
        <VariableReference VariableId="action-is-raise"/>
        <Apply FunctionId="urn:oasis:names:tc:xacml:1.0:function:any-of">
          <Function FunctionId="urn:oasis:names:tc:xacml:1.0:function:rfc822Name-match"/>
          <AttributeValue
            DataType="http://www.w3.org/2001/XMLSchema#string"
            >example.com</AttributeValue>
          <AttributeDesignator
            Category="urn:oasis:names:tc:xacml:1.0:subject-category:access-subject"
            AttributeId="urn:oasis:names:tc:xacml:1.0:subject:subject-id"
            DataType="urn:oasis:names:tc:xacml:1.0:data-type:rfc822Name"
            MustBePresent="false"/>
        </Apply>
      </Apply>
    </Condition>
    <ObligationExpressions>
      <!-- Return an action history record for the raise action. -->
      <ObligationExpression ObligationId="urn:oasis:names:tc:xacml:3.0:sod:obligation:add-history"
        FulfillOn="Permit">

        <AttributeAssignmentExpression
          AttributeId="urn:oasis:names:tc:xacml:1.0:resource:resource-id">
          <AttributeDesignator
            Category="urn:oasis:names:tc:xacml:3.0:attribute-category:resource"
            AttributeId="urn:oasis:names:tc:xacml:1.0:resource:resource-id"
            DataType="http://www.w3.org/2001/XMLSchema#anyURI"
            MustBePresent="false"/>
        </AttributeAssignmentExpression>

        <AttributeAssignmentExpression
          AttributeId="urn:oasis:names:tc:xacml:1.0:subject:subject-id">
          <AttributeDesignator
            Category="urn:oasis:names:tc:xacml:1.0:subject-category:access-subject"
            AttributeId="urn:oasis:names:tc:xacml:1.0:subject:subject-id"
            DataType="urn:oasis:names:tc:xacml:1.0:data-type:rfc822Name"
            MustBePresent="false"/>
        </AttributeAssignmentExpression>

        <AttributeAssignmentExpression
          AttributeId="urn:oasis:names:tc:xacml:1.0:action:action-id">
          <AttributeValue DataType="http://www.w3.org/2001/XMLSchema#string"
            >raise</AttributeValue>
        </AttributeAssignmentExpression>

        <AttributeAssignmentExpression
          AttributeId="urn:oasis:names:tc:xacml:3.0:sod:attribute:constraint-id">
          <AttributeValue DataType="http://www.w3.org/2001/XMLSchema#string"
            >purchase-order</AttributeValue>
        </AttributeAssignmentExpression>

        <!-- The resource-id is used as the transaction-id. -->
        <AttributeAssignmentExpression
          AttributeId="urn:oasis:names:tc:xacml:3.0:sod:attribute:transaction-id">
          <AttributeDesignator
            Category="urn:oasis:names:tc:xacml:3.0:attribute-category:resource"
            AttributeId="urn:oasis:names:tc:xacml:1.0:resource:resource-id"
            DataType="http://www.w3.org/2001/XMLSchema#anyURI"
            MustBePresent="false"/>
        </AttributeAssignmentExpression>

        <!-- Save the raiser's department attribute for
             later use in approval validation. -->
        <AttributeAssignmentExpression
          AttributeId="urn:example:xacml:department">
          <AttributeDesignator
            Category="urn:oasis:names:tc:xacml:1.0:subject-category:access-subject"
            AttributeId="urn:example:xacml:department"
            DataType="http://www.w3.org/2001/XMLSchema#string"
            MustBePresent="false"/>
        </AttributeAssignmentExpression>

      </ObligationExpression>
    </ObligationExpressions>
  </Rule>

  <!-- Rules applicable to approving a purchase order. -->

  <Rule RuleId="approve-only-raised" Effect="Deny">
    <Description>
      Make sure the purchase order has been raised.
    </Description>
    <Condition>
      <Apply FunctionId="urn:oasis:names:tc:xacml:1.0:function:and">
        <VariableReference VariableId="action-is-approve"/>
        <Apply FunctionId="urn:oasis:names:tc:xacml:1.0:function:not">
          <ForAny VariableId="record">
            <VariableReference VariableId="relevant-history"/>
            <Apply FunctionId="urn:oasis:names:tc:xacml:1.0:function:string-is-in">
              <AttributeValue
                DataType="http://www.w3.org/2001/XMLSchema#string"
                >raise</AttributeValue>
              <Apply FunctionId="urn:oasis:names:tc:xacml:3.0:function:attribute-designator">
                <VariableReference VariableId="record"/>
                <AttributeValue
                  DataType="http://www.w3.org/2001/XMLSchema#anyURI"
                  >urn:oasis:names:tc:xacml:1.0:action:action-id</AttributeValue>
                <AttributeValue
                  DataType="http://www.w3.org/2001/XMLSchema#anyURI"
                  >http://www.w3.org/2001/XMLSchema#string</AttributeValue>
              </Apply>
            </Apply>
          </ForAny>
        </Apply>
      </Apply>
    </Condition>
  </Rule>

  <Rule RuleId="approve-only-once" Effect="Deny">
    <Description>
      Make sure the purchase order hasn't already been approved.
    </Description>
    <Condition>
      <Apply FunctionId="urn:oasis:names:tc:xacml:1.0:function:and">
        <VariableReference VariableId="action-is-approve"/>
        <ForAny VariableId="record">
          <VariableReference VariableId="relevant-history"/>
          <Apply FunctionId="urn:oasis:names:tc:xacml:1.0:function:string-is-in">
            <AttributeValue
              DataType="http://www.w3.org/2001/XMLSchema#string"
              >approve</AttributeValue>
            <Apply FunctionId="urn:oasis:names:tc:xacml:3.0:function:attribute-designator">
              <VariableReference VariableId="record"/>
              <AttributeValue
                DataType="http://www.w3.org/2001/XMLSchema#anyURI"
                >urn:oasis:names:tc:xacml:1.0:action:action-id</AttributeValue>
              <AttributeValue
                DataType="http://www.w3.org/2001/XMLSchema#anyURI"
                >http://www.w3.org/2001/XMLSchema#string</AttributeValue>
            </Apply>
          </Apply>
        </ForAny>
      </Apply>
    </Condition>
  </Rule>

  <Rule RuleId="not-raised-by-approver" Effect="Deny">
    <Description>
      Make sure the purchase order wasn't raised by the prospective approver.
    </Description>
    <Condition>
      <Apply FunctionId="urn:oasis:names:tc:xacml:1.0:function:and">
        <VariableReference VariableId="action-is-approve"/>
        <ForAny VariableId="record">
          <VariableReference VariableId="relevant-history"/>
          <Apply FunctionId="urn:oasis:names:tc:xacml:1.0:function:and">
            <Apply FunctionId="urn:oasis:names:tc:xacml:1.0:function:string-is-in">
              <AttributeValue
                DataType="http://www.w3.org/2001/XMLSchema#string"
                >raise</AttributeValue>
              <Apply FunctionId="urn:oasis:names:tc:xacml:3.0:function:attribute-designator">
                <VariableReference VariableId="record"/>
                <AttributeValue
                  DataType="http://www.w3.org/2001/XMLSchema#anyURI"
                  >urn:oasis:names:tc:xacml:1.0:action:action-id</AttributeValue>
                <AttributeValue
                  DataType="http://www.w3.org/2001/XMLSchema#anyURI"
                  >http://www.w3.org/2001/XMLSchema#string</AttributeValue>
              </Apply>
            </Apply>
            <Apply
              FunctionId="urn:oasis:names:tc:xacml:1.0:function:rfc822Name-at-least-one-member-of">
              <AttributeDesignator
                Category="urn:oasis:names:tc:xacml:1.0:subject-category:access-subject"
                AttributeId="urn:oasis:names:tc:xacml:1.0:subject:subject-id"
                DataType="urn:oasis:names:tc:xacml:1.0:data-type:rfc822Name"
                MustBePresent="false"/>
              <Apply FunctionId="urn:oasis:names:tc:xacml:3.0:function:attribute-designator">
                <VariableReference VariableId="record"/>
                <AttributeValue
                  DataType="http://www.w3.org/2001/XMLSchema#anyURI"
                  >urn:oasis:names:tc:xacml:1.0:subject:subject-id</AttributeValue>
                <AttributeValue
                  DataType="http://www.w3.org/2001/XMLSchema#anyURI"
                  >urn:oasis:names:tc:xacml:1.0:data-type:rfc822Name</AttributeValue>
              </Apply>
            </Apply>
          </Apply>
        </ForAny>
      </Apply>
    </Condition>
  </Rule>

  <Rule RuleId="approve-purchase-order" Effect="Permit">
    <Description>
      Allow a purchase order to be approved by
      the raiser's department manager.
    </Description>
    <Condition>
      <Apply FunctionId="urn:oasis:names:tc:xacml:1.0:function:and">
        <VariableReference VariableId="action-is-approve"/>

        <!-- Approver is a department head. -->
        <Apply FunctionId="urn:oasis:names:tc:xacml:1.0:function:string-is-in">
          <AttributeValue DataType="http://www.w3.org/2001/XMLSchema#string"
            >Department Head</AttributeValue>
          <AttributeDesignator
            Category="urn:oasis:names:tc:xacml:1.0:subject-category:access-subject"
            AttributeId="urn:example:xacml:job-title"
            DataType="http://www.w3.org/2001/XMLSchema#string"
            MustBePresent="false"/>
        </Apply>

        <ForAny VariableId="record">
          <VariableReference VariableId="relevant-history"/>
          <!-- Raiser and approver are in the same department. -->
          <Apply
            FunctionId="urn:oasis:names:tc:xacml:1.0:function:string-at-least-one-member-of">
            <!-- Fetch approver's department. -->
            <AttributeDesignator
              Category="urn:oasis:names:tc:xacml:1.0:subject-category:access-subject"
              AttributeId="urn:example:xacml:department"
              DataType="http://www.w3.org/2001/XMLSchema#string"
              MustBePresent="false"/>
            <!-- Fetch raiser's department. -->
            <Apply FunctionId="urn:oasis:names:tc:xacml:3.0:function:attribute-designator">
              <VariableReference VariableId="record"/>
              <AttributeValue
                DataType="http://www.w3.org/2001/XMLSchema#anyURI"
                >urn:example:xacml:department</AttributeValue>
              <AttributeValue
                DataType="http://www.w3.org/2001/XMLSchema#anyURI"
                >http://www.w3.org/2001/XMLSchema#string</AttributeValue>
            </Apply>
          </Apply>
        </ForAny>

      </Apply>
    </Condition>
    <ObligationExpressions>
      <!-- Return an action history record for the approve action. -->
      <ObligationExpression ObligationId="urn:oasis:names:tc:xacml:3.0:sod:obligation:add-history"
        FulfillOn="Permit">

        <AttributeAssignmentExpression
          AttributeId="urn:oasis:names:tc:xacml:1.0:resource:resource-id">
          <AttributeDesignator
            Category="urn:oasis:names:tc:xacml:3.0:attribute-category:resource"
            AttributeId="urn:oasis:names:tc:xacml:1.0:resource:resource-id"
            DataType="http://www.w3.org/2001/XMLSchema#anyURI"
            MustBePresent="false"/>
        </AttributeAssignmentExpression>

        <AttributeAssignmentExpression
          AttributeId="urn:oasis:names:tc:xacml:1.0:subject:subject-id">
          <AttributeDesignator
            Category="urn:oasis:names:tc:xacml:1.0:subject-category:access-subject"
            AttributeId="urn:oasis:names:tc:xacml:1.0:subject:subject-id"
            DataType="urn:oasis:names:tc:xacml:1.0:data-type:rfc822Name"
            MustBePresent="false"/>
        </AttributeAssignmentExpression>

        <AttributeAssignmentExpression
          AttributeId="urn:oasis:names:tc:xacml:1.0:action:action-id">
          <AttributeValue DataType="http://www.w3.org/2001/XMLSchema#string"
            >approve</AttributeValue>
        </AttributeAssignmentExpression>

        <AttributeAssignmentExpression
          AttributeId="urn:oasis:names:tc:xacml:3.0:sod:attribute:constraint-id">
          <AttributeValue DataType="http://www.w3.org/2001/XMLSchema#string"
            >purchase-order</AttributeValue>
        </AttributeAssignmentExpression>

        <AttributeAssignmentExpression
          AttributeId="urn:oasis:names:tc:xacml:3.0:sod:attribute:transaction-id">
          <AttributeDesignator
            Category="urn:oasis:names:tc:xacml:3.0:attribute-category:resource"
            AttributeId="urn:oasis:names:tc:xacml:1.0:resource:resource-id"
            DataType="http://www.w3.org/2001/XMLSchema#anyURI"
            MustBePresent="false"/>
        </AttributeAssignmentExpression>

      </ObligationExpression>
    </ObligationExpressions>
  </Rule>
</Policy>

Here is a rewriting of the policy for XACML 4.0. The URIs are replaced with shorties, the attribute-designator function is replaced by the EntityAttributeDesignator expression, the Target is converted to a boolean expression and the MustBePresent XML attribute is omitted (default false).

<Policy xmlns="urn:oasis:names:tc:xacml:3.0:core:schema:wd-17"
  PolicyId="http://example.com/SoD/purchase-orders" Version="1.0"
  CombiningAlgId="deny-overrides">

  <ShortiesReference>http://example.com/myShorties</ShortiesReference>

  <Description>
    Policy for SoD constraints applicable to purchase orders.
  </Description>

  <!-- The target restricts applicability to purchase order resources. -->
  <Target>
    <Apply FunctionId="any-of">
      <Function FunctionId="anyURI-starts-with"/>
      <AttributeValue DataType="string"
        >http://example.com/purchase-order/</AttributeValue>
      <AttributeDesignator
        Category="resource" AttributeId="resource-id" DataType="anyURI"/>
    </Apply>
  </Target>

  <!-- Create a bag containing only relevant action history records. -->
  <VariableDefinition VariableId="$relevant-history">
    <Select VariableId="$record">
      <AttributeDesignator
        Category="resource" AttributeId="history" DataType="entity"/>
      <Apply FunctionId="and">

        <!-- Matching constraint-id. -->
        <Apply FunctionId="string-is-in">
          <AttributeValue DataType="string">purchase-order</AttributeValue>
          <!-- Fetch the constraint-id from the action history record. -->
          <EntityAttributeDesignator AttributeId="constraint-id" DataType="string">
            <VariableReference VariableId="$record"/>
          </EntityAttributeDesignator>
        </Apply>

        <!-- Matching transaction-id. -->
        <Apply FunctionId="anyURI-at-least-one-member-of">
          <!-- Fetch the transaction-id from the action history record. -->
          <EntityAttributeDesignator AttributeId="transaction-id" DataType="anyURI">
            <VariableReference VariableId="$record"/>
          </EntityAttributeDesignator>
          <!-- The resource-id is used as the transaction-id. -->
          <AttributeDesignator
            Category="resource" AttributeId="resource-id" DataType="anyURI"/>
        </Apply>

      </Apply>
    </Select>
  </VariableDefinition>

  <!-- A reusable test that the current action is 'raise'. -->
  <VariableDefinition VariableId="$action-is-raise">
    <Apply FunctionId="string-is-in">
      <AttributeValue DataType="string">raise</AttributeValue>
      <AttributeDesignator
        Category="action"AttributeId="action-id" DataType="string"/>
    </Apply>
  </VariableDefinition>

  <!-- A reusable test that the current action is 'approve'. -->
  <VariableDefinition VariableId="$action-is-approve">
    <Apply FunctionId="string-is-in">
      <AttributeValue DataType="string">approve</AttributeValue>
      <AttributeDesignator
        Category="action" AttributeId="action-id" DataType="string"/>
    </Apply>
  </VariableDefinition>

  <!-- Rules applicable to raising a purchase order. -->

  <Rule RuleId="raise-only-once" Effect="Deny">
    <Description>
      Make sure the purchase order hasn't already been raised.
    </Description>
    <Condition>
      <Apply FunctionId="and">
        <VariableReference VariableId="$action-is-raise"/>
        <ForAny VariableId="$record">
          <VariableReference VariableId="$relevant-history"/>
          <Apply FunctionId="string-is-in">
            <AttributeValue DataType="string">raise</AttributeValue>
            <EntityAttributeDesignator AttributeId="action-id" DataType="string">
              <VariableReference VariableId="$record"/>
            </EntityAttributeDesignator>
          </Apply>
        </ForAny>
      </Apply>
    </Condition>
  </Rule>

  <Rule RuleId="raise-purchase-order" Effect="Permit">
    <Description>
      Allow a purchase order to be raised by any employee.
    </Description>
    <Condition>
      <Apply FunctionId="and">
        <VariableReference VariableId="$action-is-raise"/>
        <Apply FunctionId="any-of">
          <Function FunctionId="rfc822Name-match"/>
          <AttributeValue DataType="string">example.com</AttributeValue>
          <AttributeDesignator
            Category="access-subject" AttributeId="subject-id" DataType="rfc822Name"/>
        </Apply>
      </Apply>
    </Condition>
    <!-- Return an action history record for the raise action. -->
    <NoticeExpression Id="add-history" AppliesTo="Permit">

      <AttributeAssignmentExpression AttributeId="resource-id">
        <AttributeDesignator
          Category="resource" AttributeId="resource-id" DataType="anyURI"/>
      </AttributeAssignmentExpression>

      <AttributeAssignmentExpression AttributeId="subject-id">
        <AttributeDesignator
          Category="access-subject" AttributeId="subject-id" DataType="rfc822Name"/>
      </AttributeAssignmentExpression>

      <AttributeAssignmentExpression AttributeId="action-id">
        <AttributeValue DataType="string">raise</AttributeValue>
      </AttributeAssignmentExpression>

      <AttributeAssignmentExpression AttributeId="constraint-id">
        <AttributeValue DataType="string">purchase-order</AttributeValue>
      </AttributeAssignmentExpression>

      <!-- The resource-id is used as the transaction-id. -->
      <AttributeAssignmentExpression AttributeId="transaction-id">
        <AttributeDesignator
          Category="resource" AttributeId="resource-id" DataType="anyURI"/>
      </AttributeAssignmentExpression>

      <!-- Save the raiser's department attribute for
           later use in approval validation. -->
      <AttributeAssignmentExpression AttributeId="department">
        <AttributeDesignator
            Category="access-subject" AttributeId="department" DataType="string"/>
      </AttributeAssignmentExpression>

    </NoticeExpression>
  </Rule>

  <!-- Rules applicable to approving a purchase order. -->

  <Rule RuleId="approve-only-raised" Effect="Deny">
    <Description>
      Make sure the purchase order has been raised.
    </Description>
    <Condition>
      <Apply FunctionId="and">
        <VariableReference VariableId="$action-is-approve"/>
        <Apply FunctionId="not">
          <ForAny VariableId="$record">
            <VariableReference VariableId="$relevant-history"/>
            <Apply FunctionId="string-is-in">
              <AttributeValue DataType="string">raise</AttributeValue>
              <EntityAttributeDesignator AttributeId="action-id" DataType="string">
                <VariableReference VariableId="$record"/>
              </EntityAttributeDesignator>
            </Apply>
          </ForAny>
        </Apply>
      </Apply>
    </Condition>
  </Rule>

  <Rule RuleId="approve-only-once" Effect="Deny">
    <Description>
      Make sure the purchase order hasn't already been approved.
    </Description>
    <Condition>
      <Apply FunctionId="and">
        <VariableReference VariableId="$action-is-approve"/>
        <ForAny VariableId="$record">
          <VariableReference VariableId="$relevant-history"/>
          <Apply FunctionId="string-is-in">
            <AttributeValue DataType="string">approve</AttributeValue>
            <EntityAttributeDesignator AttributeId="action-id" DataType="string">
              <VariableReference VariableId="$record"/>
            </EntityAttributeDesignator>
          </Apply>
        </ForAny>
      </Apply>
    </Condition>
  </Rule>

  <Rule RuleId="not-raised-by-approver" Effect="Deny">
    <Description>
      Make sure the purchase order wasn't raised by the prospective approver.
    </Description>
    <Condition>
      <Apply FunctionId="and">
        <VariableReference VariableId="$action-is-approve"/>
        <ForAny VariableId="$record">
          <VariableReference VariableId="$relevant-history"/>
          <Apply FunctionId="and">
            <Apply FunctionId="string-is-in">
              <AttributeValue DataType="string">raise</AttributeValue>
              <EntityAttributeDesignator AttributeId="action-id" DataType="string">
                <VariableReference VariableId="$record"/>
              </EntityAttributeDesignator>
            </Apply>
            <Apply FunctionId="rfc822Name-at-least-one-member-of">
              <AttributeDesignator
                Category="access-subject" AttributeId="subject-id" DataType="rfc822Name"/>
              <EntityAttributeDesignator AttributeId="subject-id" DataType="rfc822Name">
                <VariableReference VariableId="$record"/>
              </EntityAttributeDesignator>
            </Apply>
          </Apply>
        </ForAny>
      </Apply>
    </Condition>
  </Rule>

  <Rule RuleId="approve-purchase-order" Effect="Permit">
    <Description>
      Allow a purchase order to be approved by
      the raiser's department manager.
    </Description>
    <Condition>
      <Apply FunctionId="and">
        <VariableReference VariableId="$action-is-approve"/>

        <!-- Approver is a department head. -->
        <Apply FunctionId="string-is-in">
          <AttributeValue DataType="string">Department Head</AttributeValue>
          <AttributeDesignator
            Category="access-subject" AttributeId="job-title" DataType="string"/>
        </Apply>

        <ForAny VariableId="$record">
          <VariableReference VariableId="$relevant-history"/>
          <!-- Raiser and approver are in the same department. -->
          <Apply FunctionId="string-at-least-one-member-of">
            <!-- Fetch approver's department. -->
            <AttributeDesignator
              Category="access-subject" AttributeId="department" DataType="string"/>
            <!-- Fetch raiser's department. -->
            <EntityAttributeDesignator AttributeId="department" DataType="string">
              <VariableReference VariableId="$record"/>
            </EntityAttributeDesignator>
          </Apply>
        </ForAny>

      </Apply>
    </Condition>
    <!-- Return an action history record for the approve action. -->
    <NoticeExpression Id="add-history" AppliesTo="Permit">

      <AttributeAssignmentExpression AttributeId="resource-id">
        <AttributeDesignator
          Category="resource" AttributeId="resource-id" DataType="anyURI"/>
      </AttributeAssignmentExpression>

      <AttributeAssignmentExpression AttributeId="subject-id">
        <AttributeDesignator
          Category="access-subject" AttributeId="subject-id" DataType="rfc822Name"/>
      </AttributeAssignmentExpression>

      <AttributeAssignmentExpression AttributeId="action-id">
        <AttributeValue DataType="string">approve</AttributeValue>
      </AttributeAssignmentExpression>

      <AttributeAssignmentExpression AttributeId="constraint-id">
        <AttributeValue DataType="string">purchase-order</AttributeValue>
      </AttributeAssignmentExpression>

      <AttributeAssignmentExpression AttributeId="transaction-id">
        <AttributeDesignator
          Category="resource" AttributeId="resource-id" DataType="anyURI"/>
      </AttributeAssignmentExpression>

    </NoticeExpression>
  </Rule>
</Policy>

A preamble will declare the attributes used in this example:

attribute resource-id = {
  AttributeId resource-id,
  DataType anyURI
}

attribute history = {
  AttributeId history,
  DataType entity
}

attribute constraint-id = {
  AttributeId constraint-id,
  DataType string
}

attribute transaction-id = {
  AttributeId transaction-id,
  DataType anyURI
}

attribute action-id = {
  AttributeId action-id,
  DataType string
}

attribute subject-id = {
  AttributeId subject-id,
  DataType rfc822Name
}

attribute department = {
  AttributeId department,
  DataType string
}

attribute job-title = {
  AttributeId job-title,
  DataType string
}

attribute transaction-id = {
  AttributeId transaction-id,
  DataType anyURI
}

A text representation of the policy is:

Policy {
  PolicyId "http://example.com/SoD/purchase-orders",
  Version 1.0,
  CombiningAlgId deny-overrides,

  ShortiesReference "http://example.com/myShorties",

  Description "Policy for SoD constraints applicable to purchase orders.",

  # The target restricts applicability to purchase order resources.
  Target
    any-of(anyURI-starts-with, "http://example.com/purchase-order", resource.resource-id), 

  # Create a bag containing only relevant action history records.
  VariableDefinition {
    VariableId $relevant-history,
    Definition
      select($record : resource.history :

        # Matching constraint-id.
        string-is-in("purchase-order",
          # Fetch the constraint-id from the action history record.
          $record.constraint-id) and
        # Matching transaction-id.
        anyURI-at-least-one-member-of(
          # Fetch the transaction-id from the action history record.
          $record.transaction-id
          # The resource-id is used as the transaction-id.
          resource.resource-id))
  }

  # A reusable test that the current action is 'raise'.
  VariableDefinition {
    VariableId $action-is-raise,
    Definition string-is-in("raise", action.action-id)
  }

  # A reusable test that the current action is 'approve'.
  VariableDefinition {
    VariableId $action-is-approve,
    Definition string-is-in("approve", action.action-id)
  }

  # Rules applicable to raising a purchase order.

  Rule {
    RuleId "raise-only-once",
    Effect Deny,
    Description "Make sure the purchase order hasn't already been raised.",
    Condition
      $action-is-raise and
      any($record : $relevant-history : string-is-in("raise", $record.action-id))
  }

  Rule {
    RuleId "raise-purchase-order",
    Effect Permit,
    Description "Allow a purchase order to be raised by any employee.",
    Condition
        $action-is-raise and
        any-of(rfc822Name-match, "[example.com](http://example.com/)", access-subject.subject-id),
    # Return an action history record for the raise action.
    NoticeExpression {
      Id add-history,
      AppliesTo Permit,

      AttributeAssignmentExpression {
        AttributeId resource-id,
        Expression resource.resource-id
      },

      AttributeAssignmentExpression {
        AttributeId subject-id,
        Expression access-subject.subject-id
      },

      AttributeAssignmentExpression {
        AttributeId action-id,
        Expression "raise"
      },

      AttributeAssignmentExpression {
        AttributeId constraint-id,
        Expression "purchase-order"
      },

      # The resource-id is used as the transaction-id.
      AttributeAssignmentExpression {
        AttributeId transaction-id,
        Expression resource.resource-id
      },

      # Save the raiser's department attribute for later use in approval validation.
      AttributeAssignmentExpression {
        AttributeId department,
        Expression access-subject.department
      }
    }
  }

  # Rules applicable to approving a purchase order.

  Rule {
    RuleId "approve-only-raised",
    Effect Deny,
    Description "Make sure the purchase order has been raised.",
    Condition
        $action-is-approve and
        not any($record : $relevant-history : string-is-in("raise", $record.action-id))
  }

  Rule {
    RuleId "approve-only-once",
    Effect Deny,
    Description "Make sure the purchase order hasn't already been approved.",
    Condition
      $action-is-approve and
      any($record : $relevant-history : string-is-in("approve", $record.action-id))
  }

  Rule {
    RuleId "not-raised-by-approver",
    Effect Deny,
    Description "Make sure the purchase order wasn't raised by the prospective approver.",
    Condition
      $action-is-approve and
      any($record : $relevant-history :
        string-is-in("raise", $record.action-id) and
        rfc822Name-at-least-one-member-of(access-subject.subject-id,
            $record.subject-id))
  }

  Rule {
    RuleId "approve-purchase-order",
    Effect Permit,
    Description "Allow a purchase order to be approved by the raiser's department manager.",
    Condition
        $action-is-approve and
        # Approver is a department head.
        string-is-in("Department Head", access-subject.job-title) and
        any("$record : $relevant-history :
          # Raiser and approver are in the same department.
          string-at-least-one-member-of(
            # Fetch approver's department.
            access-subject.department,
            # Fetch raiser's department.
            $record.department)

    # Return an action history record for the approve action.
    NoticeExpression {
      Id add-history,
      AppliesTo Permit,

      AttributeAssignmentExpression {
        AttributeId resource-id,
        Expression resource.resource-id
      },

      AttributeAssignmentExpression {
        AttributeId subject-id,
        Expression access-subject.subject-id
      },

      AttributeAssignmentExpression {
        AttributeId action-id,
        Expression "approve"
      },

      <AttributeAssignmentExpression {
        AttributeId constraint-id,
        Expression "purchase-order"
      },

      AttributeAssignmentExpression {
        AttributeId transaction-id,
        Expression resource.resource-id
      }
    }
  }
}

Switching to implicit existential quantification:

Policy {
  PolicyId "http://example.com/SoD/purchase-orders",
  Version 1.0,
  CombiningAlgId deny-overrides,

  ShortiesReference "http://example.com/myShorties",

  Description "Policy for SoD constraints applicable to purchase orders.",

  # The target restricts applicability to purchase order resources.
  Target
    anyURI-starts-with("http://example.com/purchase-order", resource.resource-id), 

  # Create a bag containing only relevant action history records.
  VariableDefinition {
    VariableId $relevant-history,
    Definition
      select($record : resource.history :

        # Matching constraint-id.
        # Fetch the constraint-id from the action history record.
        $record.constraint-id = "purchase-order" and
          
        # Matching transaction-id.
        # Fetch the transaction-id from the action history record.
        # The resource-id is used as the transaction-id.
        $record.transaction-id = resource.resource-id)
  }

  # A reusable test that the current action is 'raise'.
  VariableDefinition {
    VariableId $action-is-raise,
    Definition action.action-id = "raise"
  }

  # A reusable test that the current action is 'approve'.
  VariableDefinition {
    VariableId $action-is-approve,
    Definition action.action-id = "approve"
  }

  # Rules applicable to raising a purchase order.

  Rule {
    RuleId "raise-only-once",
    Effect Deny,
    Description "Make sure the purchase order hasn't already been raised.",
    Condition
      $action-is-raise and
      $relevant-history.action-id = "raise"
  }

  Rule {
    RuleId "raise-purchase-order",
    Effect Permit,
    Description "Allow a purchase order to be raised by any employee.",
    Condition
        $action-is-raise and
        rfc822Name-match("[example.com](http://example.com/)", access-subject.subject-id),
    # Return an action history record for the raise action.
    NoticeExpression {
      Id add-history,
      AppliesTo Permit,

      AttributeAssignmentExpression {
        AttributeId resource-id,
        Expression resource.resource-id
      },

      AttributeAssignmentExpression {
        AttributeId subject-id,
        Expression access-subject.subject-id
      },

      AttributeAssignmentExpression {
        AttributeId action-id,
        Expression "raise"
      },

      AttributeAssignmentExpression {
        AttributeId constraint-id,
        Expression "purchase-order"
      },

      # The resource-id is used as the transaction-id.
      AttributeAssignmentExpression {
        AttributeId transaction-id,
        Expression resource.resource-id
      },

      # Save the raiser's department attribute for later use in approval validation.
      AttributeAssignmentExpression {
        AttributeId department,
        Expression access-subject.department
      }
    }
  }

  # Rules applicable to approving a purchase order.

  Rule {
    RuleId "approve-only-raised",
    Effect Deny,
    Description "Make sure the purchase order has been raised.",
    Condition
        $action-is-approve and
        not ($relevant-history.action-id = "raise")
  }

  Rule {
    RuleId "approve-only-once",
    Effect Deny,
    Description "Make sure the purchase order hasn't already been approved.",
    Condition
      $action-is-approve and
      $relevant-history.action-id = "approve"
  }

  Rule {
    RuleId "not-raised-by-approver",
    Effect Deny,
    Description "Make sure the purchase order wasn't raised by the prospective approver.",
    Condition
      $action-is-approve and
      $relevant-history.action-id = "raise" and
      access-subject.subject-id = $relevant-history.subject-id
  }

  Rule {
    RuleId "approve-purchase-order",
    Effect Permit,
    Description "Allow a purchase order to be approved by the raiser's department manager.",
    Condition
        $action-is-approve and
        # Approver is a department head.
        access-subject.job-title = "Department Head" and
        # Raiser and approver are in the same department.
        access-subject.department = $relevant-history.department

    # Return an action history record for the approve action.
    NoticeExpression {
      Id add-history,
      AppliesTo Permit,

      AttributeAssignmentExpression {
        AttributeId resource-id,
        Expression resource.resource-id
      },

      AttributeAssignmentExpression {
        AttributeId subject-id,
        Expression access-subject.subject-id
      },

      AttributeAssignmentExpression {
        AttributeId action-id,
        Expression "approve"
      },

      <AttributeAssignmentExpression {
        AttributeId constraint-id,
        Expression "purchase-order"
      },

      AttributeAssignmentExpression {
        AttributeId transaction-id,
        Expression resource.resource-id
      }
    }
  }
}

The collection of attribute assignment expressions is almost like an entity value constructor. We don’t currently have an entity value constructor (other than for literal values) but maybe we can exploit a synergy here.

Notation Defined in ABNF

Here is the ABNF definition of the grammar used for these examples. It provides substantial coverage but is not complete or unambiguous. The notation for attribute values definitely needs more work.

The simple pattern for shortie names is not intended to be final. If we get serious about a text representation then there are some reserved words here that should be prohibited as shortie names.

I’ve used commas to separate fields. I haven't looked closely at whether they have value in resolving ambiguity.

; Note: single-quoted ABNF strings are case exact,
; double-quoted ABNF strings are case insensitive.

; White-space between tokens is allowed. Consecutive
; alphanumeric identifiers must be separated by white-space.

orExpression  = andExpression *( S 'or' S andExpression )
andExpression = equalityExpression *( S 'and' S equalityExpression )

equalityExpression = relationalExpression
                   / equalityExpression S "=" S relationalExpression

relationalExpression = additiveExpression
                     / relationalExpression S relationalOperator S
                           additiveExpression

relationalOperator = "<" / "<=" / ">" / ">="

additiveExpression = multiplicativeExpression
                   / additiveExpression S ( "+" / "-" ) S
                         multiplicativeExpression )

multiplicativeExpression = unaryExpression
                         / multiplicativeExpression S ( "*" / "/" )
                               S unaryExpression )

unaryExpression = primaryExpression
                / 'not' S unaryExpression
                / "-" S unaryExpression

primaryExpression = "(" S orExpression S ")"
                  / quantifiedExpression
                  / AttributeDesignator
                  / EntityAttributeDesignator
                  / variable
                  / functionCall
                  / attributeValue

attributeValue = stringValue
               / integerValue
               / doubleValue
               / booleanValue
               / dateTimeValue
               / dayTimeDurationValue
               / yearMonthDurationValue
               / dateValue
               / timeValue
               / anyURIValue
               / hexBinaryValue
               / base64BinaryValue
               / rfc822NameValue
               / x500NameValue
               / xpathExpressionValue
               / ipAddressValue
               / dnsNameValue
               / entityValue

stringValue = DQUOTE *char DQUOTE
integerValue = "0" / NONZERODIGIT *DIGIT
booleanValue = 'true' / 'false'

dateTimeValue = SQUOTE year "-" month "-" day
                  "T" timeOfDay [ timeZone ] SQUOTE

dateValue = SQUOTE year "-" month "-" day [ timeZone ] SQUOTE
timeValue = SQUOTE timeOfDay [ timeZone ] SQUOTE
timeOfDay = hour ":" minute
            [ ":" second [ "." fractionalSeconds ] ]

year  = [ "-" ] ( "0" 3DIGIT / NONZERODIGIT 3*DIGIT )
month = "0" NONZERODIGIT / "10" / "11" / "12"
day   = "0" NONZERODIGIT / "1" DIGIT / "2" DIGIT / "30" / "31"

hour           = "0" DIGIT / "1" DIGIT / "20" / "21" / "22" / "23"
minute         = oneToFiftyNine
second         = oneToFiftyNine
oneToFiftyNine = ( "0" / "1" / "2" / "3" / "4" / "5" ) DIGIT

fractionalSeconds = 1*12DIGIT

timeZone = "Z"
         / ( "+" / "-" ) hour ":" minute
         / "+14:00"
         / "-14:00"

yearMonthDurationValue = SQUOTE [ "-" ] "P" (
                         yearDuration [ monthDuration ]
                         / monthDuration } SQUOTE

yearDuration  = 1*DIGIT "Y"
monthDuration = 1*DIGIT "M"

dayTimeDurationValue = SQUOTE [ "-" ] "P" (
                       dayDuration [ "T" timeDuration ]
                       / "T" timeDuration ) SQUOTE

dayDuration  = 1*DIGIT "D"
timeDuration = hourDuration [ minuteDuration ] [ secondDuration ]
             / minuteDuration [ secondDuration ]
             / secondDuration

hourDuration   = 1*DIGIT "H"
minuteDuration = 1*DIGIT "M"
secondDuration = 1*DIGIT [ "." 1*DIGIT ] "S"

anyURIValue = uri

entityValue = OPEN [ entityAttribute *( SEP entityAttribute ) ] CLOSE

entityAttribute = attribute "[" S attributeValue
                    *( SEP attributeValue ) S "]"

EntityAttributeDesignator = primaryExpression S "." S attribute

AttributeDesignator = category S "." S attribute
category            = identifier
attribute           = attributeName / attributeDefinition
attributeName       = ALPHA *( ALPHA / DIGIT / "-" )
attributeDefinition = "{" S AttributeId
                        SEP DataType
                        [ SEP Issuer ]
                        [ SEP MustBePresent ] S "}"
AttributeId         = 'AttributeId' S identifier
DataType            = 'DataType' S identifier
Issuer              = 'Issuer' S string
MustBePresent       = 'MustBePresent' S ( 'true' / 'false' )

variable = "$" ALPHA *( ALPHA / DIGIT / "-" )

functionCall = functionName S "(" S [ parameters ] S ")"
parameters   = orExpression *( SEP orExpression )
functionName = identifier

identifier      = uri / shortIdentifier
uri             = DQUOTE *uriChar DQUOTE
shortIdentifier = ALPHA *( ALPHA / DIGIT / "-" )

quantifiedExpression = ( 'any' / 'all' / 'select' / 'map' )
    "(" S variable S ":" S primaryExpression S ":" S orExpression S ")"

ALPHA  = %x41-5A / %x61-7A 
DIGIT  = %x30-39
NONZERODIGIT = %x31-39
DQUOTE = %x22
SQUOTE = %x27

OPEN =  "{" S
SEP = S "," S
CLOSE = S "}"

S       = *( SPACE / TAB / CR / LF / comment )
SPACE   = %x20
TAB     = %x09 
CR      = %x0D 
LF      = %x0A 
comment = "#" *(%x20-7F / SPACE / TAB )  ; all characters to end-of-line

attributeDeclaration = 'attribute' S attributeName S '=' S
                         attributeDefinition

policy = 'Policy' S OPEN
           'PolicyId' S string
           SEP 'Version' S version
           SEP 'CombiningAlgId' S identifier
           [ SEP 'MaxDelegationDepth' S integer ]
           *( SEP 'ShortiesReference' S uri )
           [ SEP 'Description' S string ]
           [ SEP 'Target' S orExpression ]
           *( SEP variableDefinition
              / SEP policy
              ; / SEP policyReference
              ; / SEP CombinerParameters
              / SEP rule )
           *( SEP noticeExpression )
         CLOSE

variableDefinition = 'VariableDefinition' S OPEN
                       'VariableId' S variable
                       SEP 'Definition' S orExpression
                     CLOSE

rule = 'Rule' S OPEN
         'RuleId' S string
         SEP 'Effect' S effect
         [ SEP 'Description' S string ]
         [ SEP 'Condition' S orExpression ]
         *( SEP noticeExpression )
       CLOSE

effect = 'Permit' / 'Deny'

noticeExpression = 'NoticeExpression' S OPEN
                     'Id' S identifier
                     [ SEP 'AppliesTo' S effect ]
                     [ SEP 'Condition' S orExpression ]
                     *( SEP attributeAssignmentExpression )
                   CLOSE

attributeAssignmentExpression = 'AttributeAssignmentExpression' S OPEN
                                  'AttributeId' S identifier
                                  [ SEP 'Category' S identifier ]
                                  [ SEP 'Issuer' S string ]
                                  SEP 'Expression' S orExpression
                                CLOSE

Implicit Existential Quantification and Determinism

The concept of implicit existential quantification (IEQ) allows for significant simplification of expressions but it also results in policies that don't have a single, definitive translation into the other syntaxes. Consider the case of an attribute compared to another attribute. First I need to define the attributes :

attribute owned-device = {
  AttributeId owned-device,
  DataType string
}

attribute approved-device = {
  AttributeId approved-device,
  DataType string
}

Suppose I want to test if the access-subject owns an approved device for the resource. With IEQ I can simply write:

access-subject.owned-device = resource.approved-device

This doesn't have a direct translation into, e.g., XML, because IEQ isn't a feature of the XML representation, but there are eight obvious, semantically equivalent expressions without IEQ that do have a direct translation:

string-at-least-one-member-of(access-subject.owned-device, resource.approved-device)

any-of-any(string-equal, access-subject.owned-device, resource.approved-device)

any($od  : access-subject.owned-device : string-is-in($od, resource.approved-device))

any($od  : access-subject.owned-device : any-of(string-equal, $od, resource.approved-device))

any($od  : access-subject.owned-device : any($ad : resource.approved-device : $od = $ad))

any($ad  : resource.approved-device : string-is-in($ad, access-subject.owned-device))

any($ad  : resource.approved-device : any-of(string-equal, $ad, access-subject.owned-device))

any($ad  : resource.approved-device : any($od : access-subject.owned-device : $ad = $od))

There are other more exotic ways of getting the same effect.

So to translate the simple equality expression with IEQ into XML I have to choose one of the equivalent expressions without IEQ. So there are at least eight different outcomes from translating the simple equality expression. Going in the opposite direction, an expression in XML corresponding to one of those eight possibilities could be directly translated without loss, but the desirable outcome would be the simplest expression, which is the one with IEQ. Round-tripping that expression by translating back to XML would probably come up with something different from the original XML (though semantically equivalent), so it's lossy.

Translating between the text representation without IEQ and the other representations, and between the other representations, is one to one. Translating to and from the text representation with IEQ is many to many.