Adaptive reordering and clustering-based framework for efficient XACML policy evaluation

The adoption of XACML as the standard for specifying access control policies for various applications, especially web services is vastly increasing. This calls for high performance XACML policy evaluation engines. A policy evaluation engine can easily become a bottleneck when enforcing XACML policies with a large number of rules. In this paper we propose an adaptive approach for XACML policy optimization. We apply a clustering technique to policy sets based on the K-means algorithm. In addition to clustering we find that, since a policy set has a variable number of policies and a policy has a variable number of rules, their ordering is important for efficient execution. By clustering policy sets and reordering policies and rules in a policy set and policies respectively, we formulated and solved the optimal policy execution problem. The proposed clustering technique categorizes policies and rules within a policy set and policy respectively in respect to target subjects. When a request is received, it is redirected to applicable policies and rules that correspond to its subjects; hence, avoiding unnecessary evaluations from occurring. We also propose a usage based framework that computes access request statistics to dynamically optimize the ordering access control to policies within a policy set and rules within a policy. Reordering is applied to categorized policies and rules from our proposed clustering technique. To evaluate the performance of our framework, we conducted extensive experiments on XACML policies. We evaluated separately the improvement due to categorization and to reordering techniques, in order to assess the policy sets targeted by our techniques. The experimental results show that our approach is orders of magnitude more efficient than standard Sun PDP.