Changelog:

DateDescription
07/09/2023Add chapter “Accessing undefined value in negated expression”

This post summarizes my journey of learning Rego. While much of the information overlaps with the official Rego reference, it is structured like a “getting started” guide for Rego newbies. The emphasis is put on the programming paradigms (logic versus procedural) which is helpful for programmers used to imperative languages such as Python or Java.

Normal links (e.g. Wikipedia) lead to further information while links in square brackets (e.g. [1]) are sources of statements made in this post.

All code snippets in this post have been run with OPA v0.54.0.

Thanks to Jasper Van der Jeugt reading a draft of this blog post and suggesting improvements.

Introduction to Rego

The Open Policy Agent (“OPA”) project gained a lot of attention since its acceptance as a graduate project of the CNCF [0]. OPA is a general-purpose policy engine used to enforce authorization frameworks. Its policies are defined in a query language called Rego which is in the focus of this post.

Rego is based on Datalog, a declarative logic query language. It provides constructs for pattern matching, filtering and iteration. Rego is comparable to SQL as both are general-purpose query languages. However, SQL is designed to work with tabular data and Rego operates on JSON-formatted data.
Being a declarative logic query language gives Rego some properties atypical to other programming languages. These properties are essential to understand Rego.

Declarative Programming

Declarative programming expresses the logic and rules of a problem without explicitly describing the steps to solve it. It focuses on the what, rather than the how. In contrast, a more popular programming paradigm is called “imperative” where instructions change a program’s state to produce a result. Common examples of declarative languages are SQL ([1], p. 79) or HTML [2]. Infrastructure-as-code languages, such as HCL, typically use the declarative approach as well, although often mixed with imperative elements [3]. In fact, many programming languages allow to mix both paradigms, but typically lean more towards imperative programming, such as Python [4].

An imperative programming example (Python):

def is_even(x):
    remainder = x % 2

    if remainder == 0:
        return True

    return False

A declarative logic programming example (Rego):

is_even {
      remainder == 0
      remainder = input % 2
}

[playground]

The order of statements within a rule do not matter in Rego.

Logic Programming

Datalog applies the logic programming paradigm, which is a specific form of declarative programming and is based on formal logic [5], [6]. Logic programs consist of so-called facts and rules that establish relations and constraints to describe the problem domain. In Rego, said facts and rules are expressed using the Horn clause, which is a logical formula also used in Datalog [6].
An inference engine then derives the solution to the problem by determining the order of execution. In other words, the engine translates code into a number of logic formulas that it then solves. This architecture greatly counters side-effects, demonstrates robustness and makes it much more suitable for formal verification.

In the case of Rego, OPA acts as the inference engine among other responsibilities. To improve termination guarantees of Rego, amid other measures, efforts have been taken to prevent some forms of recursion [7], [8]. In addition, as a consequence of the previously discussed design choices, Rego enjoys decidability as another crucial computational property [9]. Decidability ensures that the decision-making process during policy evaluation will always produce a result. Therefore, Rego policies will not get stuck and optimize time complexity. This robustness of Rego is probably one of the key reasons to use it in combination with OPA. It can be part of any critical path of a business application, performing its duties reliably.

As previously mentioned, Rego consists of facts and rules. Each statement in the code represents a logical rule. If a logical rule cannot be resolved, there is no need for further code evaluation. Consequently, every line of code must be “truthy”. Rego inherits this behavior, because it roots in Datalog, so it is not an Rego-specific. Yet it is relevant for Rego policy authors. To understand why awareness of this behavior is important, read chapter “Pitfalls”.

Existential Quantification

Logical quantifiers in programming define the scope of a statement over a collection of items.

Rego applies existential quantification (think of FOR ANY), which means that checking if a condition is true for at least one item in a collection.

Imperative programming languages do not inherently apply quantification like it is done in logic programming. However, they provide constructs that allow to check if a condition is true for all items in a collection which behaves like universal quantification (think of FOR ALL).

In both cases, a loop iterates over a collection and changes its behavior when it is trying to find some items matching the conditions (existential quantification) or trying to verify the conditions for all items (universal quantification).

The idea of existential quantification is implemented by identifying “all variable assignments” that satisfy a condition of a query [10].

What might sound abstract now will be discussed in more practical context in the following chapters.

Existential quantification is an unfamiliar concept for many programmers, hence it can lead to logic bugs as discussed in chapter “Pitfalls”.

Entrypoint

Rego does not have a “main” function that starts its execution. Instead, OPA is configured with an entrypoint. An entrypoint is a string that points to Rego rules, for example data.mypolicies.deny. This entrypoint requests OPA to query all deny Rego rules in namespace mypolicies, create a union of all rule results and return it. Multiple entrypoints can be provided. If rule conditions are not met, the rule is considered “unresolvable” and is not included in the final result.

In order to run OPA, it is not enough to provide only an entrypoint. An input document that serves as a global variable inside Rego containing all the data from external sources is required as well.

Optimization

It might seem premature to mention Rego optimizations at this point, but there is one in particular that is worth pointing out as it can lead to unexpected behavior.

The optimization is called “Early Exit in Rule Evaluation” and can potentially be the source of a logic bug. The official documentation describes the measure well and in detail. However, it is an advanced topic that might not be considered when entering the world of Rego. To prevent faulty code, the chapter “Pitfalls” covers this risk and suggests workarounds.

The delicate part of the optimization is described as following:

When “early exit” is possible for a (set of) rules, iterations inside that rule will be cancelled as soon as one binding matches the rule body:

package earlyexit.iteration

p {
    some p
    data.projects[p] == "project-a"
}

Since there’s no possibility that could change the outcome of data.earlyexit.iteration.p once a variable binding is found that satisfies the conditions, no further iteration will occur. – OPA documentation

In other words, OPA will stop looping over data.projects once it finds an item equal to the string project-a, which is a direct consequence of existential quantification. This is sensible and correct–however, being aware of this behavior is important.

Equality

Rego has three types or equality operators, each with different meaning:

==the comparison operator, used to compare variable values
:=the assignment operator, used to assign values to variables
=the unification operator, used to combine assignment and comparison

The = operator first does the assignment and then the comparison. If the assignment fails, OPA compares the values regardless:

# input
[1, 2, 5]

# code
default allow := false

allow {
	input[_] = 5        # assignment fails, comparison evaluates to `true`
                        # (`input[_] := 5` creates error "cannot assign to ref")
}

# output
{
    "allow": true
}

[playground]

Unless there is a reason to use the = operator, it’s recommended to avoid it [13]. Instead, use the := operator for assignments and the == operator for comparisons.

Policies, Rules & Functions

Before diving into this chapter, it’s helpful to know the Rego data structures scalar values, strings, composite values & comprehensions.

Policies

A policy is a higher-level concept in Rego that refers to a set of rules defining behavior and constraints for a system. For example, the following document is a policy, containing the Rego rules allow & deny:

package mypolicy

allow {
    input.name == "bar"
}

deny {
    input.name == "foo"
}

Rules

Rules produce so-called “virtual documents”, which are data structures computed at runtime. Read more about rules here. For example:

# input
[
    "world-a",
    "universe-a",
    "world-b",
    "universe-b"
]

# code
worlds[world] {
    item := input[_]            # loop over `input`
    startswith(item, "world")
    world := item               # var `world` is return value
}

universes[universe] {
    item := input[_]
    startswith(item, "universe")
    universe := item
}

# output
{
    "universes": [
        "universe-a",
        "universe-b"
    ],
    "worlds": [
        "world-a",
        "world-b"
    ]
}

[playground]

If no return value is defined, Rego rules return true as the documentation states:

If the value is omitted, it defaults to true. – doc

Therefore the following two rules behave the same:

deny := true if {   # rule header
    true            # rule body
}

deny {              # optimized rule header
    true
}

As mentioned previously, rules only complete execution if all conditions in the body are met. Consequently, the following rule returns nothing:

allow := true {
    false
}

Rules that return data of type set or object are called incremental rules and use a slightly different syntax:

# input
[
    "a",
    "b",
    "c",
    "c"
]

# code
return_set[item] {
	item := input[_]
}

return_object[key] := value {
	value := input[key]
}

# output
{
    "return_object": {
        "0": "a",
        "1": "b",
        "2": "c",
        "3": "c"
    },
    "return_set": [
        "a",
        "b",
        "c"
    ]
}

[playground]

Rego rules do not support parameters (e.g. return_set(param1) is invalid rule code), but [functions][#functions] can be used instead.

Existential Quantification

While existential quantification was introduced in chapter “Introduction” from a theoretical standpoint, this chapter discusses its application.

OPA behavior for rule execution is defined as following:

When evaluating rule bodies, OPA searches for variable bindings that make all of the expressions true. – doc

How does universal quantification work in imperative languages? An example using Python:

for n in numbers:           # think "FOR ALL" items `n` in numbers
    if n % 2 == 0:
        print(n)

This code snippet finds even numbers in array numbers. The same task can be accomplished in Rego as well. For example:

even_numbers[n] {
    n := input[_]
    n % 2 == 0       # think "FOR ANY" item `n` in inputs
}

In the above example, the keyword some is used to declare variable n. OPA tries to find any number n from array input which meets the condition of being even. If true, the variable binding of n is returned.

By identifying all matching variable bindings, OPA determines whether the existential quantification is satisfied or not.

It is not mandatory to declare variables using some, although the explicitness can be beneficial for clarity and comprehensibility.

Another example to find all values in an object starting with string 1:

# input
{
    "a": "1a",
    "b": "2b",
    "c": "1c"
}

# code
prefixed[item] {
	item := input[_]
    startswith(item, "1")
}

# output
{
    "prefixed": [
        "1a",
        "1c"
    ]
}

[playground]

The line item := input[_] iterates over the input document. The second input item b does not meet the rule condition startswith(l, "1"). OPA does not abort execution of the loop, but ignores the iteration outcome and skips to the next item c to continue “search for all variable bindings”.

This behavior is beneficial, but has the potential for a logic bug as discussed in chapter “Pitfalls”.

Functions

Functions in Rego look similar to rules, but behave differently:

greet(name) := msg {
    msg := sprintf("Hello %s!", [name])
}

greeting := greet("Bob")    # returns "Hello Bob!"

A function without parameters is not supported, because such a definition is interpreted as a rule:

greet() := msg {
    msg := "Hello"
}

greet()         # creates error "rego_parse_error:
                # rule argument list must take at least one argument"

Because rules represent virtual documents and functions do not, they need to be accessed differently:

# input
[
    [1, 1],
    [2, 2],
    [3, 3]
]

# code
add_function(inp) := result {                   # define function
    result := [ sum |                           # create array comprehension
        arr := inp[_]
        sum := arr[0] + arr[1]
    ]
}

output := add_function(input)                   # store result of function

dummy_rule_iterate_function_output[item] {
    item := output[index]                       # work with function result
}

add_rule = result {                             # define rule
    result := [ sum |                           # create array comprehension
        arr := input[_]
        sum := arr[0] + arr[1]
    ]
}

dummy_rule_iterate_rule[item] {
    item := add_rule[index]                     # work with rule result
}

# output
"add_rule": [
        2,
        4,
        6
    ],
"output": [
        2,
        4,
        6
    ]

[playground]

Both rules and functions can be used to share functionality between policies.

Control Flow

Basics

Constructing logic that checks for multiple conditions is done by listing all conditions line-by-line:

# input
{
    "name": "foo"
}

# code
my_rule {
    startswith(input.name, "f")   # first condition (AND..)
    endswith(input.name, "o")     # second condition
}

# output
{
    "my_rule": true
}

[playground]

To create a control flow with different scenarios in which a rule should evaluate to true, simply define the rule (rule header must be the same for every definition) multiple times. If any of the rules evaluate to true, the return value will be true. If the rules return collections, a union of all items is returned where the rule conditions are met.

In the following example, the my_rule rules return a boolean:

# input
{
    "name": "foo"
}

# code
my_rule {
    count(input.name) == 3
}

my_rule {
    input.name == "foobar"    # not true; aborts execution
}

# output
{
    "my_rule": true
}

[playground]

The if/else construct can be implemented similarly to imperative languages by using the else keyword:

# input
{
    "name": "foo"
}

# code
my_rule := msg {
    input.name == "foo"
    msg := "Hello foo!"
} else := msg {
    msg := "Hello anonymous"
}

# output
{
    "my_rule": "Hello foo!"
}

[playground]

Negation logic is implemented using the not keyword:

# input
{
    "a": "1a",
    "b": "2b",
    "c": "1c"
}

# code
prefixed[item] {
	item := input[_]
    not startswith(item, "1")
}

# output
{
    "prefixed": [
        "2b"
    ]
}

[playground]

The not operator is used for logical negation, while the != operator is used for value comparison to check for inequality.

Loops

Loops are called iterations in Rego and are well documented. However, loops are usually not needed as existential quantification is used instead.

Syntax Ambiguity

Rego uses the same syntax to iterate over as well as access values in sets, objects and arrays. Therefore, it is essential to be aware of the involved data structures. Depending on the data structure, the control flow behavior changes while using the same syntax:

# input
{
    "array": [0, 3, 5],
    "object": {"foo": "bar"}
}

# code
iterate_array[msg] {                          # returns array of strings
    value := input.array[index]               # loop over array
    msg := sprintf("%d: %d", [index, value])
}

access_key_in_object := v {                   # returns string
    v := input.object["foo"]                  # get value by key "foo"
}

create_set := s {
    s := { v |
        v := input.array[_]
    }
}

iterate_set[v] {                              # returns array of integers
    create_set[v]                             # iterate over set
}

check_key_in_object {                         # returns `true`
    input.object["foo"]                       # check if key "foo" exists
}

[playground]

By reading a statement without context, it is not always possible to derive the semantics of Rego code.

Example 1:

var3 := var1[var2]

If the data structure of var1 is an…

arraythen var1 will the iterated, var2 is assigned each index and var3 the value (assuming var2 hasn’t been assigned a value before)
objectthen var2 must be a key and var3 is the value

Example 2:

var1[var2]

If the data structure of var1 is a(n)…

arraythen var1 will be iterated and var2 contains the index
objectthen it will be checked if key var2 exists in var1
setthen var1 will be iterated and var2 contains the each item

💡 Know your data structure.

Pitfalls

Defects find their ways into every code base. Using automation to detect and prevent them is an effective measure which should be part of any Rego development process.

Two useful tools to achieve this:

  • OPA ships with the builtin command check which assists identifying compile errors & code smells.
  • Styra, the company behind OPA, released regal – a Rego linter that analyses source code for a variety of issues ranging from code style to bugs.

Exit-Early Optimization

As discussed in chapter “Optimization”, Rego exits early if it can determine the final result before running all code in its entirety.

Given a scenario where an author wants to create a policy that only allows access if all connections from the user to the company originate from any of its branch offices:

# input
[
    "on-prem",
    "remote",
    "on-prem",
    "on-prem"
]

# code
default allow := false

allow {
    input[_] == "on-prem"
}

# output
{
    "allow": true
}

[playground]

This policy results in true, despite one connection coming from a remote origin. This behavior might be elusive to programmers that are unfamiliar with logic programming.

For example, in Python the code might look similar to the below example and work as intended:

origins = ['on-prem', 'remote', 'on-prem', 'on-prem']

def allow():
    for origin in origins:
        if origin != 'on-prem':
            return 1

    return 0

if __name__ == '__main__':
    raise SystemExit(allow())

The logic bug lies in the early-exit optimization of Rego. As soon as Rego is able to evaluate rule conditions of allow to true, it stops. And this is the case, because the existential quantification is satisfied when origin is bound to on-prem in the first iteration. This is quite different from imperative programming where the condition for every item of origins is evaluated before making a decision.

Universal quantification (FOR ALL) must be applied to fix the bug.

One remediation option is to use a comprehension:

default allow := false

allow {
    all_allows := [ allowed |
        origin := input[_]
        origin == "on-prem"
        allowed := true
    ]

    count(all_allows) == count(input)
}

[playground]

Another remediation option is to use the every-keyword (introduced in OPA v0.38.0) [14] [15]:

import future.keywords.every

default allow := false

allow {
    every origin in input {
        origin  == "on-prem"
    }
}

[playground]

A third option is to flip the rule logic using negation:

# input
[
    "remote",
    "on-prem",
    "on-prem"
]

# code
default deny := false

deny {
    input[_] != "on-prem"
}

# output
{
    "deny": true
}

[playground]

This deny rule will return true as expected in case any of the user connections originate from outside a company office.

However, using the keyword every is the most appropriate option, because it intentionally enforces universal quantification and hence expresses the policy author’s intentions more descriptively and consciously [14].

💡 Whenever a rule is being created that contains an iteration, the policy author should reflect whether universal or existential quantification creates the intended behavior.

undefined values

Chapter “Introduction” explains how code execution stops if a line of code does not evaluate to true. To be explicit, whenever a logic rule cannot be resolved because its condition is not met, the rule won’t return false as programmers used to imperative programming languages might expect, instead code execution simply stops. This is also true for undefined values or attributes [17].

Rego code evaluates to undefined, for example, when accessing a non-existent namespace or object attribute.

This might lead to unintended behavior and is potentially difficult to debug:

# input
{
    "message": "world"
}

# code
deny {
	input.mesage == "world"
}

# output
{}

[playground]

The attribute input.mesage contains a typo and does not exist. Rego only knows at runtime if this attribute exists or is undefined, hence OPA will just silently stop when evaluating this line.

In order to troubleshoot this type of issue, it’s usually helpful to have multiple print() statements (read more here) across the code base to narrow down the erroneous line of code. Remember to verify package namespaces as well.

Another approach to identify the erroneous line is to disable (comment) large parts of the code base and re-enable them step by step until the issue reveals itself.

JSON “true”

The input document to OPA is JSON-formatted data, which supports both boolean and string data structures [18]. As praxis shows, it can happen that booleans are represented as strings (e.g. "true") which could lead to unintended policy decisions. For example:

# input
{
    "privileged": "true"
}

# code
deny {
    input.privileged == true
}

# output
{}

[playground]

A potential remediation could be a helper function that accounts for strings:

# input
{
    "privileged": "true"
}

# code
is_true(b) := ret {
    is_boolean(b)
    b
    ret := b
} else := ret {
    b == "true"
    ret := true
} else = false {
    true
}

deny {
    is_true(input.privileged)
}

# output
{
    "deny": true
}

[playground]

Testing

Testing is crucial to ensure expected policy behavior. OPA provides a test command that supports executing tests conveniently.

Given the following policy (file policy.rego):

package mypolicy

deny {
    input.privileged == true
}

It is simple to implement tests (file policy_tests.rego):

package mypolicy

test_deny_privileged {
    deny with input as {"privileged": true}
}

test_deny_unprivileged {
    not deny with input as {"privileged": false}
}

The command ./opa test policy.rego policy_tests.rego runs the tests and displays the result: PASS: 2/2.

Debugging

Debugging is important for any type of coding project. OPA provides a REPL and an eval command that can be instrumented for debugging. However, a typical debugger like gdb that allows to step through the code and inspect symbols does not exist yet. Consequently, printing values of variables is still an important debugging approach.

In this example, the tests from the previous chapter “Testing” are extended by a test case that executes the policy with input "true":

test_deny_string {
    deny with input as {"privileged": "true"}
}

As expected, the test case fails:

$ ./opa test policy.rego policy_test.rego
policy_test.rego:
data.mypolicy.test_deny_string: FAIL (85.375µs)
--------------------------------------------------------------------------------
PASS: 2/3
FAIL: 1/3

To investigate the issue, the value of input.privileged can be displayed using print():

deny {
    print(sprintf("value of `privileged`: %v", [input]))
    input.privileged == true
}

When executing the test case again, the value is shown:

$ ./opa test policy.rego policy_test.rego
policy_test.rego:
data.mypolicy.test_deny_string: FAIL (88.875µs)

  value of `privileged`: {"privileged": "true"}

--------------------------------------------------------------------------------
PASS: 2/3
FAIL: 1/3

The output now reveals the data structure of input.privileged, which is string instead of boolean and a fix can be created.

OPA provides the print() function since OPA release v0.34.0. Fortunately, print() does not stop on undefined values but displays <undefined> instead.

A useful 3rd-party tool to easily debug code, test policies and more is fregot.

Common Errors

Complete rules must not produce multiple outputs

This error occurs if one or more rules of the same definition take the same input and produce unequal output, for example:

# input
-

# code
a_rule := res {
	res := "b"
}

a_rule := res {
	res := "c"
}

# output
policy.rego:7: eval_conflict_error: complete rules must not produce multiple outputs

[playground]

The first definition of a_rule returns "b" while the second definition returns "c" which is non-deterministic behavior.

Often, all return values are valid and a union of them is the expected output. This can be achieved, by returning a set instead:

# input
-

# code
a_rule[res] {
	res := "b"
}

a_rule[res] {
	res := "c"
}

# output
{
    "a_rule": [
        "b",
        "c"
    ]
}

[playground]

Another common option is to merge both rules into one and return a collection. If neither option leads to the intended solution, the logic of the policy might need to be revised.

Accessing undefined value in negated expression

Accessing an undefined value in a negated expression can lead to unexpected behavior. For example, a developer might intend to verify if an attribute of an object has been set to true:

# input
{}

# code
func2(p) {
	p == true
}

deny {
	not func2(input.doesnotexist)
}

# output
{}

[playground]

The expected output is that deny returns true, which is not the case. The negation does not handle the expression evaluating to undefined and execution stops. This seems to happen due to implementation details of negation in OPA.

Two alternative approaches can be used to achieve the expected behavior:

# input
{}

# code
deny1 {
	not input.doesnotexist == true
}

func1(p) {
	func2(p.doesnotexist)
}

func2(p) {
	p == true
}

deny2 {
	not func1(input)
}

# output
{
    "deny1": true,
    "deny2": true
}

[playground]

A rule of thumb is to keep negated expressions as short and simple as possible.

OPA for Critical Paths

Rego and OPA present reliable instruments to create & evaluate policies. The decidability and termination guarantees provide assurance and allow to build powerful authorization frameworks that can be part of any critical paths of business applications.

However, using Rego comes at a cost as many programmers are not familiar with some of the involved concepts of logic programming such as existential quantification or the exit-early optimization of OPA discussed in chapter “Introduction”.
As a consequence, programmers are required to go through an initially steep learning curve acting as a barrier to entry. In addition, considering the potential pitfalls, the cost of adopting OPA should be put into scale and compared with alternative approaches such as choosing an imperative programming language instead with a more mature developer tool ecosystem and access to many more programmers (of course, imperative languages are not immune to pitfalls either).
For example, when creating software where the risk of side-effects is acceptable and time-to-market is crucial, the decision of choosing Rego should be made consciously of its consequences.