PolTree: A Data Structure for Making Efficient Access Decisions in ABAC

In Attribute-Based Access Control (ABAC), a user is permitted or denied access to an object based on a set of rules (together called an ABAC Policy) specified in terms of the values of attributes of various types of entities, namely, user, object and environment. Efficient evaluation of these rules is therefore essential for ensuring decision making at on-line speed when an access request comes. Sequentially evaluating all the rules in a policy is inherently time consuming and does not scale with the size of the ABAC system or the frequency of access requests. This problem, which is quite pertinent for practical deployment of ABAC, surprisingly has not so far been addressed in the literature. In this paper, we introduce two variants of a tree data structure for representing ABAC policies, which we name as PolTree. In the binary version (B-PolTree), at each node, a decision is taken based on whether a particular attribute-value pair is satisfied or not. The n-ary version (N-PolTree), on the other hand, grows as many branches out of a given node as the total number of possible values for the attribute being checked at that node. An extensive experimental evaluation with diverse data sets shows the scalability and effectiveness of the proposed approach.