In this article, Cerbos engineer Dennis Buduev describes the internals of the new query plan API introduced in Cerbos 0.12.0.

Cerbos helps you offload hardcoded authorization logic out of your source code and maintain them as human-readable, auditable, version-controlled policies that can be instantly updated without re-deploying the applications that rely on them. It is a stateless service with a simple API that processes application-provided information about the action, the principal (the user or service performing the action) and the resource they are trying to act on. The service responds with an ALLOW/DENY decision based on the policy rules in effect.

While this works exceedingly well for most access control decisions that a typical application needs to make, one area where it requires extra work from the developer is when a list of resources needs to be constructed containing only those objects that the current principal has access to. Even though Cerbos APIs support batch requests, when the requirement is to filter a large number of records, it is not efficient to extract all of that data from the data source only for most of it to be discarded. It also makes pagination tricky to implement because the remaining number of records could be less than the desired page size after filtering.

With the latest release of Cerbos, we introduced a new experimental query planner API to help address this problem efficiently in a language-agnostic way. This article describes how we designed and developed that API.

Let's consider a small example to frame the problem using Cerbos terminology.

A sales manager using inventory management software wants to view items sold in the year's second quarter. For simplicity, let's assume that the business rule is that a sales manager can view a sold item if that manager works in a region where the item was sold. A Cerbos policy rule to describe this behaviour could be declared as follows:

- actions: ["view"]
  roles: ["sales_manager"]
  condition:
    match:
      expr: request.resource.attr.region == request.principal.attr.region
  effect: EFFECT_ALLOW

The rule above specifies that a principal (the sales manager in our case) with the role "sales_manager" can perform the view action on a resource instance (a sold item) if the region attribute of the resource instance matches the region attribute of the principal. For single items, it is easy to obtain the decision from Cerbos because all the necessary information is already available to the application. It just needs to verify that the policy allows it. However, when the application needs to fetch a list of items – say, for example, the sales from the second quarter – it becomes complicated because the data set needs to be filtered by the criteria (second quarter sales) and then further trimmed down to only those items that the current principal can view. It is fair to say that the policy rule applies an authorization filter to the data set.

To efficiently retrieve the data, we need a way to combine the authorization filter with the data filter. It has to be done in a language-agnostic and data-store-agnostic way – which complicates things even more. To simplify this task, we decided to break it down into two stages:

1. Cerbos, upon request, transforms the relevant policy rules into an intermediate easily-parsable format.
2. The client's adapter parses the response and generates the additional predicates it needs to add to the data filter.

Cerbos policy rules can have optional conditions that can be used to express business rules for granting or denying permission to perform particular actions. The conditions are written using Google’s Common Expression Language (CEL) – which is a fast and lightweight expression language designed to easily define constraint rules. It focuses on simplicity, speed, termination guarantees and being able to run embedded in applications. CEL evaluates in linear time and is mutation and side-effect free. CEL expressions look nearly identical to equivalent expressions in C family languages such as C++, Go, Java, and TypeScript.

Cerbos uses the cel-go package to process policy conditions. It is a mature library used by many established projects such as Kubernetes, Google Cloud Firestore / Cloud Storage security rules [link], and Caddy to name a few. It integrates nicely with Cerbos because CEL has first class support for protocol buffers – which Cerbos makes use of extensively for data interchange. CEL-go’s protocol buffer support makes it very easy to integrate in a type-safe and efficient way.

Cerbos policy conditions must evaluate to TRUE or FALSE. Conditions can be arbitrarily nested and combined using AND, OR, NOT logical operators. In the following example, three CEL expressions are combined with AND operations to form a single logical expression:

condition:
  match:
    all:
      of:
        - expr: R.attr.status == "PENDING_APPROVAL"
        - expr: "UK" in R.attr.geographies
        - expr: R.attr.active

With these points in mind, let's revisit the condition in the policy rule that gives a sales manager permission to view a sales record:

request.resource.attr.region == request.principal.attr.region

Under normal circumstances, all these variables are known because the API request contains information about both the resource and the principal. However, when it comes to the question of which resources a principal has access to, we only have information about the principal. Let’s say that the principal’s region is “UK”. Then we end up with the partially evaluated expression request.resource.attr.region == "UK". This is the authorization filter that the application developer needs to apply in order to obtain the list of resources that principal has access to.

To use the query planner API, a client makes a request containing the following information:

• all information about the principal
• action
• resource kind
• optionally, known resource attributes. In our example, it is the quarter the item was sold in but the policy rule does not make use of that information to make the decision.

The endpoint gets back with a response as follows:

• If the policy can be fully evaluated (i.e. no unknown variables) and the result is ALLOW, that means that there is no authorization filter to apply. The response would be a special case called ALWAYS_ALLOW.
• If the policy can be fully evaluated (i.e. no unknown variables) and the result is DENY then that means that the principal is not allowed to perform the action on any resource of that kind. The response would be a special case called ALWAYS_DENY.
• If the policy can only be partially evaluated, then the unknown variables and the constraints on their values form the authorization filter (query plan). It is a CONDITIONAL response that includes the conditions to be satisfied.

Let's dive into the details of building a query plan.

The query plan response is a recursive tree-like data structure that describes the conditions to be satisfied. The plan for the sales manager scenario discussed above looks like the following (when represented in YAML):

expression:
  operator: eq
  operands:
    - variable: request.resource.attr.region
    - value: "UK"

Consider the following example for a more complicated authorization filter:

expression:
  operator: and
  operands:
    - expression:
        operator: eq
        operands:
          - variable: request.resource.attr.status
          - value: "PENDING_APPROVAL"
    - expression:
        operator: ne
        operands:
          - variable: request.resource.attr.owner
          - value: "maggie"

The above tree is a representation of the expression ((request.resource.attr.status == "PENDING_APPROVAL") AND (request.resource.attr.owner != "maggie"))

So how do we find the partially evaluated expressions to be included in the query plan? The following (simplified) snippet illustrates how the cel-go library makes this fairly easy.

var expression string
...
ast, _ := env.Compile(expression)
prg, _ := env.Program(ast, cel.EvalOptions(cel.OptPartialEval, cel.OptTrackState))
vars, _ := cel.PartialVars(knownVars, unknowns)
val, details, _ := prg.Eval(vars)
if types.IsUnknown(val) {
  residual, _ := env.ResidualAst(ast, details)
  // return residual a.k.a. partial AST
}
if b, ok := val.Value().(bool); ok {
  // return evaluated value
}
// return error

Here cel.PartialVars is used to create an argument for a subsequent evaluation step. The evaluation result would have type unknown if the expression contains references to unknown attributes. Then we can use Env.ResidualAst to get the partially evaluated expression's abstract syntax tree (AST) and transform it into the tree structure of the query plan response.

Cerbos policies can have a global variables section to make it easier to share common conditions or values between multiple policy rules. A variable expression can contain anything that a condition expression can have. Normally these variables are evaluated independently of the rules and are available in the CEL environment’s scope. However, when producing the query plan, we have to first inline these declarations into the conditions that refer to them because we need to produce a single expression tree for the plan.

The cel-go library does not provide a way to perform inlining so we had to do it manually by patching the CEL ASTs of the conditions. CEL AST type does not export internals but, fortunately, it is possible to get a protobuf serializable (hence having exported fields) instance of the parsed/checked expression corresponding to the AST. Patching that is relatively straightforward except for the need to re-assign IDs of AST nodes. This was done by performing a depth-first traversal of the tree.

As we mentioned before, a policy condition is a logical operation over CEL expressions – which could be fully or partially evaluated. Whether an expression can be fully evaluated is determined by its variables and their values:

• x + y < 10 : If both x and y have known values, then the expression can be fully evaluated to TRUE or FALSE, otherwise it can only be partially evaluated.
• x + y < 10 && z : If x or y have unknown values, but if z is known to be FALSE, then the entire expression evaluates to FALSE no matter what values of x and y are.

If an expression is a part of a condition and can be fully evaluated, it is possible to optimize the condition. We implemented the following optimizations:

• Short-circuiting: FALSE AND expr1 equals FALSE. Likewise, TRUE OR expr1 simplifies to TRUE. In both cases, we can skip the expr1 evaluation altogether.
• Sub-expression elimination: the expression TRUE AND expr1 AND expr2 is equivalent to expr1 AND expr2.
• Logical operation elimination: TRUE AND expr1 is equivalent to expr1. Here we are deleting an operation. Likewise, NOT TRUE / NOT FALSE is converted to FALSE/TRUE, respectively.

Derived roles are a concept in Cerbos that provide a way to augment traditional RBAC roles with contextual data to obtain more specialised, virtual roles that can be reused across Cerbos policies. They add an extra dimension to the query planner algorithm because we need to consider which derived roles would be activated for the principal and add the conditions from those roles into the mix as well. Fortunately, combining derived roles conditions is as simple as joining them using the AND operator.

The Query Plan API is available in Cerbos v0.12.0 as an experimental feature. Over the next few release cycles, we plan to do further optimizations on the generated AST and refine the plan representation based on feedback from users before promoting it to a stable API.