Xengine: a fast and scalable XACML policy evaluation engine

ABSTRACT

XACML has become the de facto standard for specifying access control policies for various applications, especially web services. With the explosive growth of web applications deployed on the Internet, XACML policies grow rapidly in size and complexity, which leads to longer request processing time. This paper concerns the performance of request processing, which is a critical issue and so far has been overlooked by the research community. In this paper, we propose XEngine, a scheme for efficient XACML policy evaluation. XEngine first converts a textual XACML policy to a numerical policy. Second, it converts a numerical policy with complex structures to a numerical policy with a normalized structure. Third, it converts the normalized numerical policy to tree data structures for efficient processing of requests. To evaluate the performance of XEngine, we conducted extensive experiments on both real-life and synthetic XACML policies. The experimental results show that XEngine is orders of magnitude more efficient than Sun PDP, and the performance difference between XEngine and Sun PDP grows almost linearly with the number of rules in XACML policies. For XACML policies of small sizes (with hundreds of rules), XEngine is one to two orders of magnitude faster than the widely deployed Sun PDP. For XACML policies of large sizes (with thousands of rules), XEngine is three to four orders of magnitude faster than Sun PDP.

REFERENCES

• 1: Sun's XACML implementation. http://sunxacml.sourceforge.net/, 2005.
• 2: XEngine: A Fast and Scalable XACML Policy Evaluation Engine. Technical Report MSU-CSE-08-2, Department of Computer Sciences and Engineering, Michigan State University, East Lansing, Michigan, March 2008. http://www.cse.msu.edu/~alexliu/publications/xengine/xengtech.pdf
• 3: Qunfeng Dong , Suman Banerjee , Jia Wang , Dheeraj Agrawal , Ashutosh Shukla, Packet classifiers in ternary CAMs can be smaller, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 26-30, 2006, Saint Malo, France
• 4: Kathi Fisler , Shriram Krishnamurthi , Leo A. Meyerovich , Michael Carl Tschantz, Verification and change-impact analysis of access-control policies, Proceedings of the 27th international conference on Software engineering, May 15-21, 2005, St. Louis, MO, USA [doi>10.1145/1062455.1062502]
• 5: Mohamed G. Gouda , Xiang-Yang Alex Liu, Firewall Design: Consistency, Completeness, and Compactness, Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS'04), p.320-327, March 24-26, 2004
• 6: Vladimir Kolovski , James Hendler , Bijan Parsia, Analyzing web access control policies, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242664]
• 7: E. Martin, T. Xie, and T. Yu. Defining and measuring policy coverage in testing access control policies. In Proc. of the 8th Int. Conf. on Information and Communications Security (ICICS-06), pages 139--158, 2006.
• 8: P. Mazzoleni , E. Bertino , B. Crispo , S. Sivasubramanian, XACML policy integration algorithms: not to be confused with XACML policy combination algorithms!, Proceedings of the eleventh ACM symposium on Access control models and technologies, June 07-09, 2006, Lake Tahoe, California, USA [doi>10.1145/1133058.1133089]
• 9: OASIS eXtensible Access Control Markup Language (XACML) V2.0 Specification Set http://www.oasis-open.org/committees/xacml/. 2007.
• 10: L. Qiu, G. Varghese, and S. Suri. Fast firewall implementations for software-based and hardware-based routers. In Proc. the 9th Int. Conf. on Network Protocols (ICNP), 2001.
• 11: Michael Carl Tschantz , Shriram Krishnamurthi, Towards reasonability properties for access-control policy languages, Proceedings of the eleventh ACM symposium on Access control models and technologies, June 07-09, 2006, Lake Tahoe, California, USA [doi>10.1145/1133058.1133081]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Access controls

General Terms:
Algorithms, Performance, Security

Keywords:
XACML, access control, policy decision point (PDP), policy enforcement point (PEP), policy evaluation, web server