XEngine: A Fast and Scalable XACML Policy Evaluation Engine

Project Links

  Project Page
  License

Hosted By SourceForge.net

Welcome to XEngine Project!

• XEngine converts the hierarchical structure of an XACML policy to a flat structure.
• XEngine converts multiple combine algorithms to one combining algorithm.
• XEngine uses a tree struture to efficiently process requests.

For detailed information about XEngine, please check XEngine-Sigmetrics2008.pdf and XEngine-Full.pdf.

This project was developed by Fei Chen and Alex X. Liu from Department of Computer Science and Engineer at Michigan State University, and JeeHyun Hwang and Tao Xie from Automated Software Engineering Research Group at North Carolina State University. Fei Chen (feichen@cse.msu.edu) and Alex X. Liu (alexliu@cse.msu.edu) currently maintain the project. If you have any questions or suggestions about this project, feel free to contact with them.

This project is supported by the National Science Foundation under Grant No. 0845513. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

Introduction to XEngine

Typical XACML based access control works as follows. A subject(e.g., modify) on a protected resource (e.g., grades). The subject submits this request to the Policy Enforcement Point (PEP) that manages the protected resource. The PEP formulates such a request using the XACML request language. Then, the PEP sends the XACML request down to the Policy Decision Point (PDP), which stores a user specified access control policy written in the XACML policy language. The PDP checks the request with its XACML policy and determines whether the XACML request should be permitted or denied. Finally, the PDP formulates the decision in XACML response language and sends it to the PEP, which enforces the decision.

However, commercial implementations of XACML policy evaluation engines such as Sun XACML PDP, which performs brute force searching by comparing a request with all the rules in a policy, still represent the state-of-the-art. To our best knowledge, there is no prior research work on improving the performance of XACML policy evaluation engines.

Making XACML policy evaluation more efficient is difficult from many aspects. First, XACML policies have complex structures. For example, XACML policies can be specified recursively. An XACML policy consists of a policy set and a policy set consists of a sequence of policies or policy sets. Second, an XACML policy often has conflicting policies or rules, and they are resolved by four possible mechanisms: First-Applicable, Only-One-Applicable, Permit-Overrides, and Deny-Overrides. It is natural for an XACML policy evaluation engine to examine all the rules in an XACML policy before making the final decision for a request. Third, in XACML policies, the predicates that a request needs to be checked upon are scattered. Every policy set, policy, or rule has its own predicate. Fourth, in XACML, a request could be multi-valued. For example, the subject of a request could be a principal who is both a professor and a student. Last but not the least, in XACML policies, a rule may be multi-valued. For example, a rule in an XACML policy may specify that the subject must be both a professor and a student. In retrospect, the high complexity of XACML policies makes brute force searching appear to be the natural way of processing requests.

We developed XEngine, a fast and scalable XACML policy evaluation engine. XEngine has three key ideas. First, XEngine converts all strings in an XACML policy to numerical values. In processing requests, XEngine also converts the strings in a request to their corresponding numerical values. We call this technique XACML policy numericalization. Second, XEngine converts a numericalized XACML policy with a hierarchical structure and multiple complex conflict resolution mechanisms into an equivalent policy with a flat structure and only one conflict resolution mechanism, which is First-Applicable. We call this technique XACML policy normalization. Third, XEngine further converts a numericalized and normalized policy to a tree structure, and uses it to efficiently process numericalized requests.

XEngine is orders of magnitude faster than Sun PDP, and the performance difference between XEngine and Sun PDP grows almost linearly with the number of rules in an XACML policy. For XACML policies of small sizes (with hundreds of rules), XEngine is two orders of magnitude faster than Sun PDP for single-valued requests and one order of magnitude faster than Sun PDP for multi-valued requests. For XACML policies of large sizes (with thousands of rules), the experimental results show that XEngine is three to four orders of magnitude faster than Sun PDP for both single-valued and multi-valued requests.

XEngine outperforms the standard XACML policy evaluation engines (such as Sun PDP) for three main reasons. First, in checking whether a request satisfies a predicate, XEngine uses efficient numerical comparison thanks to XACML policy numericalization. Second, when it receives a request, XEngine find the correct decision without comparing the request with every rule in the policy due to the XACML policy normalization technique. Third, XACML numericalization and normalization open many new opportunities for building efficient data structures for fast request processing. In this paper, we present two approaches to fast processing of requests: the decision diagram approach and the forwarding table approach.