Method for analyzing an XACML policy

1. A method of analyzing XACML (eXtensible Access Control Markup Language) code comprising one or more XACML policies, the method comprising:

storing the code in an electronic memory;

for each rule in the code, constructing in disjunctive normal form an expression of a path through the code to the rule;

tagging one or more elements of one or more of the paths;

determining whether any rules in the code have an effect of deny; and

for every XACML policy in the code, determining which type of combining algorithm the policy includes.

2. The method of claim 1 , wherein said determining which type of combining algorithm the policy includes comprises:

determining whether every XACML policy in the code includes a combining algorithm of the deny-overrides type.

3. The method of claim 1 , further comprising:

determining whether the code comprises a policyset element.

4. The method of claim 1 , further comprising:

identifying values for one or more attributes referenced in the code; and

determining which actions, if any, are permitted by the code in association with the identified attribute values.

5. The method of claim 4 , wherein said determining which actions are permitted comprises:

for each disjunctive normal form expression of a rule, determining whether a condition of the rule is satisfied by the identified attribute values.

6. The method of claim 1 , further comprising:

identifying values for one or more attributes referenced in the code; and

determining whether any rules in the code are redundant.

7. The method of claim 6 , wherein said determining whether any rules are redundant comprises:

for each pair of terms within each disjunctive normal form expression:

comparing the terms for logical equivalence; and

for each pair of disjunctive normal form expressions:

comparing the expressions for logical equivalence;

wherein two terms in a disjunctive normal form expression are equivalent if they return the same result for the identified attribute values; and

wherein two disjunctive normal form expressions are equivalent if they return the same result for the identified attribute values.

8. The method of claim 1 , further comprising:

identifying values for one or more attributes referenced in the code; and

attempting to determine whether any pair of the rules in the code are inconsistent.

9. The method of claim 8 , wherein said determining whether any pair of the rules in the code are inconsistent comprises:

for every rule that evaluates to deny for the identified attribute values, determining whether a different rule evaluates to permit for the identified attribute values.

10. The method of claim 8 , wherein said determining whether any pair of the rules in the code are inconsistent comprises:

for every rule that evaluates to permit for the identified attribute values, determining whether a different rule evaluates to deny for the identified attribute values.

11. The method of claim 1 , further comprising:

for each pair of XACML policies in the code, determining whether both policies will return permit for a given set of attribute values.

12. The method of claim 11 , wherein said determining whether both policies will return permit for a given set of attribute values comprises:

testing the policies for logical equivalence;

wherein two policies are logically equivalent if they return the same result for the given set of attribute values.

13. The method of claim 1 , further comprising:

for each policy in the code, attempting to refactor the policy into sub-policies, wherein each said sub-policy comprises a single rule pertaining to one value of a specified attribute.

14. The method of claim 13 , wherein said refactoring the policy into sub-policies comprises:

for each value of the specified attribute:

creating a sub-policy comprising a form of the rule in which the specified attribute posses said value; and

inserting in the sub-policy a target element containing a subjectmatch element that matches said value;

creating an additional sub-policy comprising a form of the rule in which the specified attribute is omitted;

wherein the additional sub-policy does not contain a target element.

15. The method of claim 13 , wherein said constructing in disjunctive normal form an expression of a path through the code to the rule comprises:

for every target element in the path, generating a policy target expression expressing the target element in disjunctive normal form;

if the rule comprises a target element, generating a rule target expression expressing the target element in disjunctive normal form;

generating a condition expression expressing a condition element of the rule in disjunctive normal form; and

combining the policy target expressions, the rule target expression and the condition expression to form said disjunctive normal form of the expression of the path through the code to the rule.

16. A computer-readable medium storing instructions that, when executed by a computer, cause the computer to perform a method of analyzing XACML (eXtensible Access Control Markup Language) logic comprising one or more XACML policies, the method comprising:

storing the code in an electronic memory;

for each rule in the code, constructing in disjunctive normal form an expression of a path through the code to the rule;

tagging one or more elements of one or more of the paths;

determining whether any rules in the code have an effect of deny; and

for every XACML policy in the code, determining which type of combining algorithm the policy includes.