XACML Implementers Guide
Informational Document 3.0-011.1, 2511 Mayrch 201103
Document identifier:
xacml-implement-guide-3.01.1.doc
Location:
Editor:
Rich Levinson, Oracle Corporation
Hal Lockhart, BEA Systems, <>
Contributors:
Anne Anderson, Sun Microsystems
Hal Lockhart, Oracle Corporation
Abstract:
This document contains notes, which may be useful to implementers of the XACML Specification. It is not normative in any way.
Status:
This document is expected to be added to periodically on no particular schedule.
Committee members should send comments and contributions on this specification to the list. Others should subscribe to and send comments and contributions to the list. To subscribe, send an email message to with the word "subscribe" as the body of the message.
Table of Contents
1 Introduction 3
2 XACML 3.0 Implementation Guidelines 4
2.1 PolicySet, Policy, and Rule Combining Algorithms 4
2.1.1 Background on combining algorithms issues with Indeterminate 4
3 XACML 1.0->2.0 Implementation Guidelines 7
3.1 "Notional" Request context 7
3.1.1 Suggestions 7
3.2 Functions 7
3.3 Bags 7
3.4 Date and time arithmetic functions 7
3.5 Combining algorithms 8
3.6 MatchId 8
3.7 Hierarchical resources 8
3.8 Subject categories 8
4 References 9
)
1 Introduction 2
2 "Notional" Request context 2
2.1 Suggestions 2
3 - Functions 3
4 Bags 3
5 - Date and time arithmetic functions 3
6 - Combining algorithms 3
7 - MatchId 4
8 - Hierarchical resources 4
9 - Subject categories 4
10 References 4
Appendix A. Notices 4
1 Introduction
These are potential topics to go into an XACML Implementer’s Guide. The intent is to alert implementers to subtleties of the specification that need particular attention in order to avoid problems.
2 XACML 3.0 Implementation Guidelines
3 This section is intended to include implementation considerations based on the XACML 3.0 Specification
4 PolicySet, Policy, and Rule Combining Algorithms
5 In XACML 3.0 some changes were made to address issues that have been raised about the way Indeterminate values were processed, the specifics of which, were not handled consistently between Rule and Policy combining, as well as between opposite-biased algorithms, such as deny-overrides vs permit-overrides. Since these were “rules’, the inconsistencies were not regarded as “errors” per se’, but unnecessary conceptual discrepancies that caused policy designers to be asking why such discrepancies were found, and when understood there was no substantive basis requested that things be made more consistent to make policy design easier to create and maintain.
6 (An example reference is: Ninghui Li, etal, “A Formal Language for Specifying Policy Combining Algorithms in Access Control”. https://www.cerias.purdue.edu/assets/pdf/bibtex_archive/2008-9-report.pdf)
7 Background on combining algorithms issues with Indeterminate
8 The following discussion will focus on the “deny-overrides” combining algortithm, however all the principles discussed apply “permit-overrides” as well as the ordered versions of those algorithms, as well as some others that will be discussed individually.
9 Therefore, in order to be specific, the fundamental principle that we are concerned with is that in a deny-overrides Policy, as soon as a Rule is encountered that is both Applicable and evaluates to Deny, there is no point in processing more Rules, at least as far as determining the final result is concerned, because the final result will be Deny for this Policy.
10 The reason this principle is important is that one can then skip processing the remaining Rules, which can save a lot of processing time, which in some situations can result in critical performance degradation if the principle is not taken advantage of.
11 To give a concrete, although exaggerated example, consider:
12 A Policy that has 100 Rules.
13 There are 10 Rules that have an Effect of Deny, and 90 Rules that have an Effect of Permit.
14 If the first Rule that is processed is a Deny, then, in general, there are 2 choices that are available for how to continue processing:
15 One could continue processing all the remaining Rules, and end up with 100 results, which would include 10 Deny’s and 90 Permit’s. One could then submit this collection of results to the deny-overrides combining algorithm, which would then return a result of Deny as soon as it found any result that equaled Deny. In this case, all 100 Rules were evaluated and the set of results then processed by the combining algorithm.
16 An alternative mechanism would be that rather than first evaluating the Rules and then passing in the results, one could instead simply pass in a set of 100 references, each pointing to one of the 100 Rules. The combining algortith, itself, could then process the Rules, and as soon as it found a Deny, it could then return the result of Deny, without having to process the remaining Rules.
17 A somewhat philosophical issue arises at this point as to distinction between the description of the combining algorithm as a specification vs the description of the algorithm as an implementation.
18 From the point of view of the specification, the algorithm is about “combining” and the logic contained within the specification should focus on that aspect alone.
19 From the point of view of the implementation, if the implementers look at the specification, and it says to pass in 100 Decisions to the algorithm, then they are faced with the issue that the only way to pass in the Decisions is to first evaluate the Rules in order to obtain the Decisions.
20 Unfortunately, in software engineering, issues such as the above are not clearly and unambiguously resolved in any manner that all parties can generally agree, so, in order to make progress, generally the involved parties will focus on what needs to be done to get by the issue and to continue making progress. This is the path the XACML TC chose in order to move forward.
21 Therefore, in the discussion that follows, in order to focus on explaining the implementation strategy for the combining algorithms, the situation will simply be explained and the decisions described so that users of the specification can understand how to best decide to implement the algorithms. The purpose of providing this background and explanation is to help implementers avoid possible erroneous conclusions they might reach without this guidance.
22 The reason for the above discussion is that the algorithms for deny-overrides (etc) have changed in XACML 3.0 in the sense that they are now described from the point of view of the specification and only include information about the combining and do not contain information about possible optimizations. By contrast in XACML 2.0, the algorithms did contain optimization information, and therefore may be considered to have been written from the perspective of the implementation.
23 To be specific, the following will show explicitly how these differences look in the specifications.
24 XACML 2.0 Rule and Policy combining algorithms
25 First, in XACML 2.0, there is a deny-overrides rule-combining-algorithm plus a deny-overrides policy-combining-algorithm.
26 The XACML 2.0 deny-overrides-rule-combining-algorithm pseudo-code looks like this:
27 Decision denyOverridesRuleCombiningAlgorithm(Rule[] rules) {
28 for (i=0; i<rules.length(); i++) {
29 Decision decision = evaluate(rules[i]);
30 if (decision == Deny) {
31 return Deny;
32 }
33 …
34 }
35 …
36 return NotApplicable;
37 }
38 The most important thing to notice here, for the purposes of this discussion, is that what is passed in to the algorithm is a collection of Rules, which are then evaluated one at a time in the for{} loop. As soon as a Rule is found that equals Deny, then the loop immediately terminates. Thus, the optimization of not processing Rules unnecessarily, as described above is “built-in” to the description of the XACML 2.0 deny-overrides rule-combining-algorithm.
39 A similar situation exist in XACML 2.0 for the deny-overrides policy-algorithm, which looks like this:
Decision denyOverridesPolicyCombiningAlgorithm(Policy[] policies) {
for (i=0; i<policies.length(); i++) {
Decision decision = evaluate(policies[i]);
if (decision == Deny) {
return Deny;
}
…
}
…
return NotApplicable;
}
40 Again, just as in the previous algorithm, as soon as this algorithm encounters a Deny, the for{} loop is broken out of, the result returned and any remaining policies are unevaluated.
41 XACML 3.0 Rule and Policy combining algorithms
42 In XACML 3.0 the situation appears, on the surface, to be different than 2.0, however, this is not actually the case because what has changed is the perspective of the specification and not its substance.
43 In XACML 3.0 Rule and Policy combining are no longer distinguished, at least from a combining perspective, and so a single algorithm is used to describe both situations:
44 A Policy combining a set of child Rules.
45 A PolicySet combining a set of child Policies and PolicySets.
46 Therefore, in XACML 3.0, the input to the combining algorithm does not distinguish between policies, policysets, and rules, and is only concerned with the set of decision that is passed in. Therefore the XACML 3.0 deny-overrides algorithm looks like this:
Decision denyOverridesDecisionCombiningAlgorithm(Decision[] decisions) {
for (i=0; i<decisions.length(); i++) {
Decision decision = decisions[i];
if (decision == Deny) {
return Deny;
}
…
}
…
return NotApplicable;
}
47 There are two major distinctions to consider when looking at the above XACML 3.0 algorithm, as compared to the XACML 2.0 algorithms.
48 The input has no indications whether the individual Decision items come from a PolicySet, Policy, or a Rule, or some mix of those.
49 The first line of the loop, no longer has an “evaluate” method that is being applied to the input.
50 Here again is where the distinction between the implementation perspecitive and the specification perspective becomes important.
51 From the specification perspective, this algorithm is only about combining Decision items, not about optimizing how one obtains the Decision items.
52 However, from an implementation perspective, this algorithm appears to require that a collection of Decision items first be calculated (evaluated), and then submitted to the combining algorithm. If this were to literally be taken to be the case, it would now be impossible to optimize the algorithm, because the optimization itself is entangled with the details of the algorithm and cannot be readily separated out.
53 As a result of this situation, this document has been produced to help developers understand how to deal with this specification. Again, the focus here is to explain what can be done, and not to try to resolve the issues between specification of abstract algorithms vs implementation and optimization of concrete algorithms.
54 Recommended implementation strategy
55 In order to preserve the structure of the XACML 3.0 algorithms, and, at the same time, allow for optimization of those algorithms, the following general approach is suggested:
56 Prior to calling the combining algorithm, wrap each of the decision-producing child nodes (which include PolicySet, Policy, and Rule nodes) of the current node (which will either be a PolicySet or Policy node) within what we will call a Decision object. For example, one could create a Decision object with the following constructor:
57 Decision decision = new Decision(node[i]);
58 Therefore a collection of child Decision nodes can be accumulated, which do not require actually evaluating the node that they contain.
59 Then one can pass the collection of unprocessed nodes to the XACML 3.0 combining algorithm.
60 Now, in order to get the Decision for the current node in the algorithm’s loop, all one needs to do is execute the following statement:
61 Decision decision = decisions[i].getDecision();
62 Now, the “magic” is that the getDecision() method can be implemented, such that if the evaluate() method has not yet been applied to the node that was passed in to the constructor, then that evaluate() method can be executed now in order to obtain the actual Decision value.
63 Similarly, since the return “value” from the algorithm is also a Decision object, the callerwill also have to use the getDecision() method to get the value, however, this time, since evaluate has already been called the Decision object would simply return the value that was calculated on the first access and not do the evaluate again.
64
65 XACML 1.0->2.0 Implementation Guidelines
66 "Notional" Request context
· Request context can not be treated as static XML document
· AttributeSelector evaluation can not depend on just XPath processing because even if the XPath expression does not return an attribute value, it will be necessary to invoke some sort of "attribute locator" to look for the referenced attribute in external databases.
66.1 Suggestions
· Parse input Request.xml as a starting point for evaluation of AttributeDesignator (AD) and AttributeSelector (AS) references.
· Define an "attribute retrieval" interface that takes as input an AD or AS and returns the matching attribute value, error, or "not found" result. The implementation of this interface first looks for referenced AD or AS in the parsed Request.xml. If attribute not found there, then implementation invokes an external attribute location API. This API should support plugins for different ways of locating attributes. The plugins should be configurable for particular LDAP repository locations, etc.
67 Functions
· x500Name-equal: can this use a standard Java method?
· rfc822Name-equal: local part is case-sensitive, domain-part is not case-sensitive
68 Bags
· A singleton bag is NOT the same as an instance of the datatype contained in the bag. All the equality predicates, arithmetic functions, string conversion functions, numeric data-type conversion functions, Boolean functions, arithmetic comparison functions, date and time arithmetic functions, non-numeric comparison functions, and special match functions take only primitive data types as arguments. They must return Indeterminate if a bag or singleton bag is used as input.
69 Date and time arithmetic functions
o Can these use implementations in "XQuery 1.0 and XPath 2.0 Functions and Operators"?
70 Combining algorithms
· Note that the policy-combining version of each algorithm is different from the rule-combining version.
· policy-combining version of Deny-overrides can NEVER return Indeterminate under any conditions.
· First-Applicable: The "applicability" test is based solely on evaluation of the Target. The first rule, policy, or policyset whose Target evaluates to "true" is evaluated, and that result is returned even if the evaluation of the condition for the rule(s) evaluates to "NotApplicable". Thus it is perfectly possible to return a result of "NotApplicable" from a "First-Applicable" combining algorithm even if there were subsequent rules or policies that would have returned Permit or Deny.