Optimized Authorization Rules with Trie
Security is one of the most important aspects while developing an application. However, it isn’t a hard thing to do to add this security aspect to our application nowadays. There are many plugins available out there that can be used so easily by all developers. Whatever the language or the framework used to develop, those kind of plugins will be available and suitable to support the application security. This is because almost all (if not all) developers will need this security in order to secure the application they build. We can take spring security as an example to support security aspect for application build with Spring or Spring Boot.
Unfortunately, as the application is getting bigger and has a lot of traffic, we can’t just rely on the available plugin out there. It is sometimes not sufficient to support our application in terms of performance and flexibility for example. One of those cases is URL authorization rules checking that we will discuss in this article.
URL Authorization Rules on Spring Security
It is quite easy to implement this URL authorization rules using spring security, we can just set this up like the one in following picture.
By setting up that config, all those URLs will be secured by spring security and can only be accessed by requests that have suitable authority. For all incoming requests, spring security will check those requests (HTTP method, URL, and User Authority) against the rules that have been defined.
The check will be done by iterating all the defined rules. For each rule, it will be checked whether the request’s URL and request’s HTTP method is matched with URL and HTTP method on this rule. If it’s matched, it will decide if this request is authorized by checking the request’s user authority against allowed authorities on this rule. Iterating all the rules means spring security will need to do the check as many as the number of defined rules. As on previous example we have 8 rules defined, therefore spring security will need to do 8 URL checks in the worst case.
After knowing how this spring security works to handle this URL authorization rules, we will definitely realize that this approach will not be suitable if our application will have so many rules. Our application will be overwhelmed by only this authorization check part because all incoming request need to checked against so many defined rules one by one.
URL Authorization Rules with Trie
After realizing previous issue, there are several things that can be done to overcome this issue. One of those is to store the rules in Trie (or also called prefix tree) and the check will be done by searching the request’s URL to this trie.
Trie
Trie is a tree data structure where in each node store a letter. From this tree we can easily retrieve any available words by traversing down from the root node to any terminal node.
Above picture depicts how words: ALGO, API, BOM, BOR, BOS, BOSAN are stored in a trie. We can see that each node store a letter. We can also notice that there are some black nodes and some blue nodes. Blue nodes here mean that those nodes are terminal nodes which represent the last letter from one of the words above.
Lets say we want to search word BO, we can traverse from root and move to one of its child which store letter B and from this node continue to its child which store letter O. As we notice that this node with letter O is a black node, it means BO isn’t a valid word (from words given above). However, if we continue the search to move again to one of children of this O node. We can reach a node with letter S. This time we have reached one of terminal nodes (blue nodes) which means that BOS is a valid word.
Storing URL Authorization Rules in Trie
We can also utilize trie for URL authorization rules check like what spring security does. We can store the rules in trie as the following picture:
As we have stored all the rules in a trie, we can do authorization check by searching the request’s URL to the trie. The search process pretty much similar like how we search a word on an ordinary trie like what we have discussed previously. We only need do a bit modification on a trie search because we usually will use wildcards on the URL rule. The most used wildcards are * and ** (ant pattern).
Here is a step on how search is done for an example request url /api/products/id01/inventories.
By utilizing trie to store the authorization rules, the check will no longer iterate all the defined rules one by one. For each incoming request we only need to search the URL in trie and the check time complexity won’t depend on how many the rules is anymore.
