Introduction
Authorization is an interesting domain in that it so frequently blurs the distinctions that we often draw between data and code. Sometimes a rule expresses a piece of data directly, such as who may do what to which resource. Other times a rule expresses logic, or code: this actor may do that to some resource if certain other conditions are also met, such as the actor or resource belonging to some model type. To handle complex authorization policies, a system should handle both points of view efficiently and naturally, and in this post we'll show how we aimed to do that when building oso, an open-source policy engine for authorization.
Rules as Data
An authorization policy specifies the requirements for authorization as rules. The rules may be in the form of permissions data, like an ACL: a (long) list of who can do what. In its simplest form, this may be only a few bits per rule, such as in traditional Unix file permissions. Or it may come in the form of a matrix like this one:
{% c-block language="polar" %}
allow,alice,read,/reports/alice/
allow,alice,read,/reports/bob/
allow,bhavik,read,/reports/bhavik/
allow,bob,read,/reports/bob/
allow,marjory,read,/reports/alice/
allow,marjory,read,/reports/bhavik/
allow,marjory,read,/reports/bob/
allow,marjory,read,/reports/marjory/
{% c-block-end %}
This matrix encodes which users of a system may access what paths. Here we've chosen to represent the matrix as CSV, but the encoding is irrelevant; this kind of authorization data is easily encoded in any authorization system, or handled directly by application code.
Another way to encode this kind of matrix is as a list of simple rule definitions, one per row:
{% c-block language="polar" %}
allow("alice", "read", "/reports/alice/");
allow("alice", "read", "/reports/bob/");
allow("bhavik", "read", "/reports/bhavik/");
allow("bob", "read", "/reports/bob/");
allow("marjory", "read", "/reports/alice/");
allow("marjory", "read", "/reports/bhavik/");
allow("marjory", "read", "/reports/bob/");
allow("marjory", "read", "/reports/marjory/");
{% c-block-end %}
Here the encoding is the oso rule language, Polar, but again the encoding is not really germane. The point is that what we previously thought of as data has now become code in a declarative programming language. It's not very interesting code, but it is simple and direct, and makes an easy target for translation from nearly anything else. We'll come back and make it more interesting shortly, but let's take it on its own terms for now.
Since this policy is primarily data and we are treating it as such, we will undoubtedly run into inherent problems around handling data. For example, what happens as the permissions matrix grows in size? Even with naïve algorithms, a small matrix should pose no performance problem. But as with any other type of data, the tools needed to cope with it vary as the data grows. If the list is very large or if frequent dynamic updates are required, some kind of database is going to be most appropriate.
What we've done in oso is made it so that you shouldn't need to prematurely deal with these issues. By the time performance becomes a limiting factor, it should be the case that other data management problems are more pressing.
To handle largish data-heavy policies with oso, we implemented a simple indexing scheme over constant data. The speedups come from eliminating most or all rules from consideration up front with just a few hash lookups. We have seen it deliver very large speedups in authorization decisions on certain kinds of realistic policies, and our microbenchmarks confirm the expected behavior.
We call this the pre-filter, since its job is to keep the "main" filter — the general rule selection and sorting process we'll discuss shortly — from even considering most rules. It is able to do its job by considering the parts of rules purely as data, while still respecting the semantics of the rules as code.
Rules as code
Data used to make authorization decisions is never random, and so almost always has exploitable structure. As usual in technology, we can exploit that structure through abstraction.
Let's look again at our simple permissions matrix. One simple pattern that should be evident is captured by the informal rule "etheveryone may read their own reports". We can capture this formally with oso as:
{% c-block language="polar" %}
allow(actor: String, "read", resource: String) if
resource.split("/") = ["", "reports", actor, ""];
{% c-block-end %}
This rule is universally quantified over all string-valued actors and resources, and so replaces a potentially infinite set of data rules. If we wish to quantify over more specific classes of actors and resources from our application, we can refine the type restrictions:
{% c-block language="polar" %}
allow(actor: Reporter, "read", resource: Report) if
resource.author = actor;
{% c-block-end %}
This allows extremely fine-grained decisions without a large blowup in policy size.
These kinds of rules behave very differently than the data rules we saw earlier. They may have data embedded in them (e.g., the {% c-line %}"read"{% c-line-end %} action, the {% c-line %}"reports"{% c-line-end %} path segment), but they are inherently code. These rules are executed or called with a list of arguments as part of an authorization query, not just matched as data. They may contain arbitrary logical expressions, which are encoded here as Horn clauses, but once again the encoding is inessential — the essential feature is the interpretation process, where the rules are treated as meaning-bearing expressions of a logical language rather than opaque or "quoted" data. Types or classes in such a language denote structured sets of data, semantically related through subtyping.
The inherent problems of handling code are well known, and solving them is our daily bread & butter as software developers. All of the fundamental techniques developed over the years to handle these issues — abstraction, modularity, types, etc. — are relevant and useful in the authorization domain.
What we've done with oso is to make not only the application's data, but also its code and abstractions available in the DSL. Let's take types as an example. We saw above how types defined by the application can be used to make specialized authorization decisions: by annotating parameters with a {% c-line %}parameter: Type{% c-line-end %} specializer, and then using our knowledge of the type in the body of the rule to call specific methods or access certain attributes.
To support this particular abstraction, the system must do some work under the hood. For each specializer, query-time machinery must check whether a given argument is of the specialized type; we use a foreign function interface (FFI) to call into the application for an answer. Rules with parameter lists that match the given arguments are in this way selected or filtered from the list of possible rules.
After the applicable rules have been selected, we must then decide in what order to execute them. Sometimes it doesn't matter, but in the presence of exceptions and overrides for specific classes, it can. We therefore sort the applicable rules by specificity (i.e., by whether one type is more specific than another with respect to a given argument), and execute the most specific rule first. This allows more specific rules to selectively override less specific ones.
This filtering and sorting process is relatively slow compared to an index lookup. This is what makes the pre-filter we discussed earlier so effective in speeding up data-heavy policies; the fewer rules that need to be selected for applicability and sorted, the faster the call sequence executes. But in exchange for a somewhat expensive calling sequence, we can leverage available abstractions over our data, namely the types in our domain model. And by utilizing optimizations from our view of rules as data, we can make them affordable in realistic policies that freely mix code with data.
Rules Redux
We have now seen authorization rules from two points of view. Viewed as code, rules are interpreted or run, and so have an essentially dynamic character. Viewed as data, they may be indexed ahead of time, thus exploiting their static characteristics. So which is it? Are rules code or data, fish or fowl?
The answer of course, is both: code and data are dual, and no one point of view is primary. But switching points of view can sometimes lead us to opportunities for optimization that may be hard to see from the other, and knowing when you're dealing with which makes it easier to reason about trade-offs and which techniques to apply.
