Highly parallel evaluation of XACML policies

• US 8,677,453 B2
• Filed: 05/19/2008
• Issued: 03/18/2014
• Est. Priority Date: 05/19/2008
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Chang, David, Bagepalli, Nagaraj, Narayan, Harsha, Patra, Abhijit
• Primary Examiner(s): Arani, Taghi
• Assistant Examiner(s): PLECHA, THADDEUS J
• Application Number:
  US12/123,227
• Publication Number:
  US 20090288136A1
• Time in Patent Office: 2,129 Days
• Field of Search: 726/1, 707/764
• US Class Current: 726/3
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 21/6227 where protection concerns the structure of data, e.g. records, types, queries
• CPC Class Codes: G06F 2221/2141 Access rights, e.g. capability lists, access control lists, access tables, access matrices
• CPC Class Codes: H04L 63/101 Access control lists [ACL]

Abstract

Techniques for highly parallel evaluation of XACML policies are described herein. In one embodiment, attributes are extracted from a request for accessing a resource including at least one of a user attribute and an environment attribute. Multiple individual searches are concurrently performed, one for each of the extracted attributes, in a policy store having stored therein rules and policies written in XACML, where the rules and policies are optimally stored using a bit vector algorithm. The individual search results associated with the attributes are then combined to generate a single final result using a predetermined policy combination algorithm. It is then determined whether the client is eligible to access the requested resource of the datacenter based on the single final result, including performing a layer-7 access control process, where the network element operates as an application service gateway to the datacenter. Other methods and apparatuses are also described.

Claims

1. A method comprising:

at an application service appliance device, receiving a request from a client device to access an application server;

extracting from the request a plurality of attributes comprising a user attribute identifying a user of the client device and an environment attribute identifying an environment associated with the user;

performing a plurality of individual searches concurrently, one for each of the attributes, in order to generate a plurality of individual search results, for one or more policies in a policy store to determine whether the policies, when compared to a corresponding one of the attributes, indicate that the client device is authorized to access the application server, wherein each of the policies is grouped into one or more policy sets and each policy has a plurality of child rules, and wherein a combining algorithm of each of the policies specifies that when one of the child rules produces an evaluation result, a corresponding policy also produces a same evaluation result without having to further evaluate the request;

combining the plurality of individual search results associated with the attributes;

generating a single final result from the combining;

determining whether the client device is eligible to access the application server based on the single final result; and

performing an open system interconnection (OSI) layer-7 access control process on packets of the request from the client device.

2. The method of claim 1, wherein performing the plurality of individual searches comprises performing the individual searches using a particular type of data structure designed for a type of content associated with respective individual searches.

3. The method of claim 2, wherein performing the plurality of individual searches comprises performing the individual searches using the data structure having an interval tree hierarchy based on one or more numeric operators.

4. The method of claim 3, wherein performing comprises performing the individual searches based on the numeric operators that comprise at least one of “

<

”

, “

( )”

, “

[ ]”

, “

>

”

, “

<

=”

, “

>

=”

, and “

==”

.

5. The method of claim 2, wherein performing the plurality of individual searches comprises performing the individual searches using the data structure having an Aho-Corasick deterministic finite automation (DFA) hierarchy based on one or more substrings.

6. The method of claim 2, wherein performing the plurality of individual searches using the data structure comprises performing the individual searches using the data structure having a Patricia tree hierarchy based on one or more prefixes.

7. The method of claim 1, wherein combining the plurality of individual search results comprises combining the plurality of individual search results using a policy combination algorithm which includes one of a deny-override algorithm and a permit override algorithm.

8. The method of claim 1, wherein extracting comprises extracting the plurality of user attributes which comprise one of a uniform resource locator (URL), time, document, action, source internet protocol (IP) address, access method, user identifier and role attribute.

9. The method of claim 1, wherein performing the plurality of individual searches comprises performing the plurality of individual searches for one or more policies stored in the policy store using a bit vector algorithm and written in an extensible access control markup language (XACML).

10. A machine-readable storage device having instructions stored therein, which when executed by a processor, cause the processor to:

extract from a request received from a client device to access an application server a plurality of attributes comprising a user attribute identifying a user of the client device and an environment attribute identifying an environment associated with the user;

perform a plurality of individual searches concurrently, one for each of the attributes in order to generate a plurality of individual search results for one or more policies in a policy store to determine whether the policies, when compared to a corresponding one of the attributes, indicate that the client device is authorized to access the application server, wherein each of the policies is grouped into one or more policy sets and each policy has a plurality of child rules, and wherein a combining algorithm of each of the policies specifies that when one of the child rules produces an evaluation result, a corresponding policy also produces a same evaluations result without having to further evaluate the request;

combine the plurality of individual search results associated with the attributes;

generate a single final result from the combined individual search results;

determine whether the client device is eligible to access the application server based on the single final result; and

perform an open system interconnection (OSI) layer-7 access control process on packets of the request from the client device.

11. The machine-readable storage device of claim 10, wherein the instructions that cause the processor to perform the plurality of individual searches comprise instructions that cause the processor to perform the individual searches using a particular type of data structure designed for a type of content associated with respective individual searches.

12. The machine-readable storage device of claim 11, wherein the instructions that cause the processor to perform the plurality of individual searches comprise instructions that cause the processor to perform the individual searches using the data structure having an interval tree hierarchy based on one or more numeric operators.

13. The machine-readable storage device of claim 12, wherein the instructions that cause the processor to perform the plurality of individual searches comprise instructions that cause the processor to perform the individual searches based on the numeric operators that comprise at least one of “

<

”

, “

( )”

, “

[ ]”

, “

>

”

, “

<

=”

, “

>

=”

, and “

==”

.

14. The machine-readable storage device of claim 11, wherein the instructions that cause the processor to perform the plurality of individual searches comprise instructions that cause the processor to perform the individual searches using the data structure having an Aho-Corasick deterministic finite automation (DFA) hierarchy based on one or more substrings.

15. The machine-readable storage device of claim 11, wherein the instructions that cause the processor to perform the plurality of individual searches comprise instructions that cause the processor to perform the individual searches using the data structure having a Patricia tree hierarchy based on one or more prefixes.

16. The machine-readable storage device of claim 10, wherein the instructions that cause the processor to combine the plurality of individual search results comprise instructions that cause the processor to combine the individual search results using a policy combination algorithm which includes one of a deny-override algorithm and a permit override algorithm.

17. An apparatus comprising:

a memory configured to store a policy store with a plurality of policies accessible by one or more processors;

a network service processor; and

an application service processor coupled to the network service processor and the policy store and configured to;

receive a request from a client device to access an application server;

extract from the request a plurality of attributes comprising a user attribute identifying a user of the client device and an environment attribute identifying an environment associated with the user;

perform a plurality of individual searches concurrently, one for each of the attributes, in order to generate a plurality of individual search results, for one or more policies in the policy store to determine whether the policies, when compared to a corresponding one of the attributes, indicate that the client device is authorized to access the application server, wherein each of the policies is grouped into one or more policy sets and each policy has a plurality of child rules, and wherein a combining algorithm of each of the policies specifies that when one of the child rules produces an evaluation result, a corresponding policy also produces a same evaluation result without having to further evaluate the request;

combine the plurality of individual search results associated with the attributes;

generate a single final result from the combined individual search results;

determine whether the client device is eligible to access the application server based on the single final result; and

perform an open system interconnection (OSI) layer-7 access control process on packets of the request from the client device.

18. The apparatus of claim 17, wherein the application service processor is further configured to perform the plurality of individual searches using the data structure designed for a type of content associated with respective individual searches.

19. The apparatus of claim 18, wherein the application service processor is further configured to perform the plurality of individual searches based on the data structure having an interval tree hierarchy based on one or more numeric operators, including at least one of “

<

”

, “

( )”

, “

[ ]”

, “

>

”

, “

<

=”

, “

>

=”

, and “

==”

.

20. The apparatus of claim 18, wherein the application service processor is further configured to perform the plurality of individual searches using the data structure having an Aho-Corasick deterministic finite automation (DFA) hierarchy based on one or more substrings.

21. The apparatus of claim 18, wherein the application service processor is further configured to perform the plurality of individual searches using the data structure having a Patricia tree hierarchy based on one or more prefixes.

22. The apparatus of claim 17, wherein the application service processor is further configured to combine the plurality of individual search results using a policy combination algorithm which includes one of a deny-override algorithm and a permit override algorithm.