Runtime Improvement of Role Based Access Control

In this article, I'll discuss the runtime improvement of the widely used Role Based Access Control (RBAC) CASBIN-CPP library. After analyzing the library code, it's evident that the current implementation isn't optimized for scalability. Consequently, I proposed a runtime improvement via a pull request (PR), which has been accepted into the library.

This improvement:

• gains x300 run time decreasing on the middle-sized number of policies.
• makes objects independent of policies number inside the mode

Casbin library-related problem statement

Role-based access control is the widely used security model that allows making specific actions to the specific resource by a specific subject when permission is granted.

We can imagine a table of permissions that makes this model work:

On checking the permissions in the table we can decide whether the access to perform specific action will be granted or not. To emulate this behavior, CASBIN tries to find appropriate permissions to make the decision. This searching process of matched policies is named “enforce” and has settings that:

• works with requests for incompletely defined policies

• works with policies that deny access, not just permit it

• works with grouping policies that can represent the assignment of a subject (user) to act on resources indirectly by role-to-subject assignment at a separate table.

• works with a table that expects any order of policy from the grants table to match

• works with the first matched policy to detect the first match and not consider the rest of the grants table

The number of modes CASBIN-CPP uses makes it flexible in usage. Previous versions of CASBIN-CPP are noticeably slower in real-time when processing the simplest grants table model during the "enforcement" process. This issue has been identified by me and several others, as indicated by reports on the CASBIN-CPP Github repository.

The older version's library has linear real-time complexity(O(P)) for the simplest basic model.

Casbin library structure

Let’s talk about the CASBIN-CPP library structure to define why low performance happens and what should be done to make it performant on the usage of the basic model.

To find the most valuable parts and overview of interconnections let’s look at the following image:

Casbin model

From a configuration point of view Casbin-cpp works with the mathematical model.

This model represents:

• “p”: policy table to match requests or not

• “g”: grouping policies table to match indirect requests ( with roles usage) or not

• “r”: request parameters list - to represent user request for enforcement

• “m”: matcher structure - to define product of request and “g”&”p” rows product that be treated as match

It is the most crucial part of the design. To make data be treated and stored uniformly, an older version of Casbin-Cpp stores all of these model parts as std::vectorstd::vector>.

This type of storage makes it possible to apply any request for any possible strategy of enforcement uniformly - by checking matching row by row of the policies table. But for specific cases as base model, it is better to use another collection that makes match detection much faster.

Casbin evaluator

Evaluator is a class that defines the matching of specific policies table rows to the user enforcement request and the matching strategy relies on a model ( that can obtain it from config ). The evaluator covers line-by-line matching and return resolution:

• Does policy match the request?

• Does policy not match the request?

Casbin effector

The Effector class is utilized to determine whether the results from the Evaluator, which match policies traversed by the will, can be considered as the final decision for enforcing a user request. It gathers the matching results from individual policy rows into a collection. Subsequently, it can make a decision based on:

• single match on allowing policy is enough to return true on enforcement

• match should be continues by all of the policies to detect policies that will deny action

• and so on

The effector needs to have evaluator results and have matcher equations to work. In some cases as a “basic model” , the first occurrence of allowing policy is enough to make a positive decision on enforcement of user request.

Casbin enforcer

The Enforcer class integrates all encapsulated class behaviors. It retrieves policies from the model and generates an Evaluator to obtain decisions for each policy's table row. It then passes the results individually to the Effector to determine whether there is a match between the user request and the model. To achieve this, it iterates through the policy collection in a cycle.

Casbin traverse policy

Traversing through policies in Casbin-Cpp involves going through each policy one by one. This process is efficient when the first element of the table aligns with the final decision. However, if it doesn't, traversal requires checking all rows of the policies table to find a match. In the basic model, it's feasible to simply retrieve the matching element from the collection without the need for traversal.

Casbin benchmark tests

The benchmark used with the old version of Casbin-Cpp involved a small number of policies, resulting in minimal time for request enforcement detection. This setup was fair for identifying the lowest possible enforcement time. However, real-life scenarios differ significantly. Request distribution doesn't rely solely on the first elements of the table. Even if requests follow a normal distribution pattern, benchmark results shouldn't be used as a target for making estimations.

Prototyping of runtime improvement solution

The main idea of the Casbin-Cpp modification is to store policies in the collection that makes a find policy for basic models with O(1) run time complexity (i.e. std::unordered_set ). This collection is very similar to std::vector in terms of interface but searchin of the element can happen much faster.

I have implemented the modification of Casbin-Cpp that:

• contains the compilation flag that uses std::unordered_set or std::vector.
• contains a representative benchmark that shows real enforcement time for the basic model in scale.
• uses custom class that filters policies collection to have collection with just 1 element if match possible

After the benchmark, I got following results that encouraged me to make the PR to Casbin-Cpp.

Table 1. Casbin-cpp benchmark old version vs prototype

Design of runtime improving solution

The prototype serves as the initial means to determine if the target criterion can be achieved. However, to integrate it seamlessly within the library, additional steps are necessary. Primarily, the unit tests of Casbin-cpp were designed to utilize specific implementations of std::vector.

Several changes were made to facilitate future modifications:

1. Usage of std::vectorstd::vectorstd::string was replaced with type aliases to enhance flexibility.

2. Container-specific methods were replaced with independent ones; for instance, operator[] was eliminated in favor of iterators.

This preparation simplified the integration of std::unordered_set. By transitioning the type alias to std::unordered_set, both test and main code compilation was successful. However, a specific matching mode was overlooked, leading to a redesign of the solution.

The Priority mode matcher in Casbin-cpp expects user-defined policies to be treated in a specific order. The first matched allow or deny policy determines the enforcement effect. This mode cannot utilize std::unordered_set as the base collection, as it alters the element order during traversal using iterators, which conflicts with the user-defined order.

It's evident that direct use of std::unordered_set isn't feasible. A plausible solution is to introduce a new abstract collection of policies within the model. This collection, named PoliciesValues, is designed to have:

• iterable collection
• with ability to add / erase / find an elements ( with O(1) when suitable - base model only )

This wrapping collection can be created:

• in 2 modes with encapsulated std::vector or with encapsulated std::unordered_set.

• on construction of the model matcher will be considered to detect “base mode construction”

• matcher will be read next after request structure, policy structure, grouping policy structure definition

• on existence of grouping policies or not detecting that matcher equation not expects direct request to policy parameters matching std::vector will be used for construction of PoliciesValues wrapping collection

• otherwise std::unordered_set will be used for construction of PoliciesValues wrapping collection

One more important detail is that the enforcement collection wrapper will have no difference from the outside. That is why additional methods that show the type of internal collection have been added. On the enforcement side, an additional filtering class has been added - it makes searching of policy by user request if the collection supports hashing (i.e. wraps std::unordered_set ).

Os independent implementation notes.

Casbin-cpp is an independent library that can be compiled with several compilers on OS-es like OsX / Windows / Linux. That makes work with code more complex:

• Its not possible to use std::variant easily on OSx cause of internal standard limitations
• clang and gnu compilers work differently with initialization lists, so aligning the short clang code to gnu compilers took place.

Conclusion

It was an interesting journey that brought behavior runtime closer to possible limit.

This PRI made has been merged at Casbin-cpp v1.55.

I hope you have a nice time using the new Casbin-cpp :)