Role Based Access Control and Big O

Didapptic.com is a research based web application that measures Android and iOS Apps from a didactic point of view. Actually, we work on a new release in order to provide a fresh layout and smarter handling of app data. Among other things, the new release introduces also a new user management handling which allows and/or permits actions to users.

Role Based Access Control

Multiple solutions for managing users and their permission are introduced in the past. Wikipedia lists some of them who have proven themselves as suitable when systems scale in their number of users and/or permissions. There is Mandatory Access Control which defines permissions based on properties and rules that belong to actions. A second approach is Discretionary Access Control where the decision of permitting an action to an user is based on the identity on the user. The last approach is “Role-Based Access Control” where roles belong to users and permissions are assigned to roles. In this post, we want to discuss the later approach.

I want to show our own implementation of “Role Based Access Control”, where permissions are not directly assigned to users, but to roles. Assigning roles to users allows a better permission handling since permissions are not assigned to users directly, but only accessed through their roles. Doing this user access management becomes a matter of simply assigning roles to users. This makes things easy when adding a new user, changing their roles or reorganizing a whole unit.

Since I have implemented (small) user management systems multiple times in the past, it was obvious to create a small library in the hope that it could also be used in future projects. This post is an approach to demonstrate simple-RBAC, which denotes my own solution and is a simple and lightweight solution. The source code is available on GitHub under the MIT license as well as a Composer package on Packagist.

Simple-RBAC

First things first: The library is a small piece of code. As stated above, I wanted to create a package which I can use without reinventing the wheel every time. Simple-RBAC is a lightweight “Role Based Access Control” solution where permissions are assigned to roles and roles to users. It is definetly extendable in the future, but focusses actually on determining the whether one user is permitted to perform one action or not.

A key question for me during the design of a solution is about performance. How performant is the system for 1 / n / ∞ input data? Considering that we have 3 types of input: Users, roles and permissions.

A naive solution would iterate over all users, followed by roles and permissions. This would result in O(u) * O(r) * O(p) = O(u * r *p) runtime which is quite bad. We have to find a better solution. Luckily there are algorithms and data structures for this purpose.

Hash Tables are a first candidate as their average search complexity is O(1). However, this depends on a well implemented hash function. A good hash function would avoid hash collisions and the look-up would simply consist of O(1) for creating the hash and O(1) for accessing the appropriate bucket in which the value is located. The worst case scenario, where a badly implemented hash function chains all values in the same bucket, would result in iterating over the bucket and in O(n). As we have 3 types of input data, using hash tables for users, roles and permissions could mean O(1) * O(1) * O(1) = O(1) but also O(u * r * p).

However, my intuition says that a better solution is available: Binary Search Trees.

Binary Search Tree’s

Since it is appropriate to index each user, role and permission object instance in numerical order (e.g. by managed them as the primary key of a database table) which provides a very good base for comparing them, Binary Search Tree’s are very suitable for quick look-up in great data sets. The look-up/serach complexity for a Binary Search Tree is O(log n) which is quite better than O(n) in worst case for hash tables.

Let’s recall how we organize users, roles and permissions. Permissions are not directly assigned to users, but to roles. And roles are assigned to users. While validating user permissions, we only have a user instance with all roles in that the user resides and a “permission” containing all roles in that the permission is in for which we want to know whether the user is authorized to perform an action or not.

As you have noticed, the user and permission instance provide roles. Those roles are organized as Binary Search Trees. If we find a intersection sub set that contains at least one element which is not the empty set, we have found a role in which the user is that is permitted to perform the action.

Practical Implementation

That’s enough theory. Lets dive into the implementation. Simple-RBAC provides the “IDataProvider” interface that has to be implemented in order to provide the necessary information. As defined above, the library is (actually) desgined to verify the permissions of only one user and therefore, user look-up operation is O(1). The user instance contains all roles organized as a Binary Search Tree. The same applies to the permission: since we want to verify one permission, we only need to retrieve the permission details including all users.

But how is an effective look-up and a comparison of two Binary Search Tree’s structured? The answer is “Traversal”.

We first traverse the user’s roles tree with an Pre-Order traversal. Pre-Order traversal visits the root first, then the left and then the right node. This is a little more advantageous than In-Order or Post-Order traversal as Pre-Order checks the node first before going deep into the tree.

When visiting a node, we get the role which is the nodes value. We then can simply make a binary search on the permission’s role tree. If the permission’s roles tree contains the id, we found a role that is assigned to the user and the permission is part of. The job is done and the user is allowed to perform the action!

User/permission look-up has a complexity of O(1) as reasoned above. In-Order traversal has a complexity of O(n) and the Binary Search Tree look-up has O(log m). This results in O(1) + O(1) + O(n) * O(log m) = O(n) * O(log m) = O(n * log m).

Conclusion

Even if the naive approach takes into account that we do not need to look-up a user/permission, its complexity results in O(n) * O(m). The hash table approach has an amortized complexity of O(1) * O(1), and O(n) * O(m) = O(n * m) in worst case, which is less performant than the proposed Binary Search Tree approach.

The above proposed solution has one disadvantage which can not be influenced by this library: PHPAlgorithms, the library that provides the Binary Search Tree and the traversal algorithms, is actually not able to break a traversal when the value is found. This means that the whole tree is completely traversed, even when the desired value is found. Even if “traversing” means exactly going through the whole tree, PHPAlgorithms could offer an optional way to end the traversing prematurely.

Simple-RBAC is available on GitHub and Packagist. The library is in active development and may not cover all requirements of a fully matured Role Based Access Control System. At least, it fits didapptic.com’s requirements, for which it was designed for now.

Update 1

While implementing simple-rbac for didapptic.com, I realized that this library gets bad in runtime when I create a tree out of an ordered list. Selecting all permissions from a database with an “ORDER BY permission_id” clause returns a ascending ordered list. Adding the permissions to a binary tree results in a extremely unbalanced tree. 

unbalanced binary tree

The solution is quite simple: retrieve the middle element of your list, make it as the root, set middle – 1 as left and middle + 1 as right. Repeat this operation until there are no elements left. PHPAlgorithms implements this approach with the createFromArrayWithMinimumLength() method.