Evaluation Semantics of a Policy Query Language

Writing a policy in a general-purpose language is easy and produces a program with branches, loops, and returns. Writing it in a policy language produces something with a different shape: a set of rules, each of which is a query that either produces a value or produces nothing. The difference is not cosmetic. It determines what a policy can express, what happens when a field is missing, and why a rule that looks correct can permit everything.

Rego, the language used by Open Policy Agent, is the most widely deployed instance of this design, and its semantics are worth understanding on their own terms rather than as syntax to be copied from examples.

A rule is a query over two documents

Every evaluation has exactly two inputs: input, the thing being decided about, and data, the rest of the world the policy is allowed to read. A rule defines a value computed from those two documents. There is no mutable state, no sequencing, and no early return, because there is no execution order to return from.

package platform.images

default allow := false

allow if {
	input.review.object.kind == "Pod"
	not deny
}

deny contains msg if {
	some container in input.review.object.spec.containers
	not startswith(container.image, "registry.internal/")
	msg := sprintf("image %q is not from the internal registry", [container.image])
}

Read the body of deny as a conjunction of constraints, not as a sequence of statements. It succeeds if there exists at least one element of spec.containers whose image does not start with the prefix; when it succeeds, it contributes one element to the deny set. If no element satisfies the constraints, the rule produces nothing.

That “produces nothing” is the concept that separates policy languages from programming languages. A rule whose body cannot be satisfied is undefined, which is neither true nor false. allow above is undefined for a Pod with a bad image, and undefined is treated as false by whatever consumes the decision — but the distinction matters inside the language, because not tests for undefinedness rather than for the boolean false.

Undefined propagates, and that is the whole error model

Consider a rule that compares a field to a number. If the field is a string, or absent, the comparison is undefined rather than an error. There is no exception to catch and no stack trace; the enclosing rule body simply fails. In a policy that is written as a chain of required conditions, this behaviour is exactly right: a missing field means the condition does not hold, so the rule does not fire.

It is exactly wrong for a policy that is written as a chain of prohibitions. A rule that says “deny if the object has a field set to a forbidden value” does not fire when the field is missing, which is usually intended. A rule that says “deny unless the object has a required field” must be written as not has_field or as an explicit check, because the natural phrasing — comparing the field to something — is undefined and therefore silently passes. Most policy bugs of the “everything was allowed” kind are undefinedness bugs, not logic bugs.

default exists to make the top-level decision total. default allow := false gives allow a value whenever its body fails, so the consumer always receives a boolean. Without it, the decision document has a hole where allow should be, and a caller that reads the field and treats absence as permission inverts the policy. The convention of a default-deny top-level rule with accumulating deny rules underneath is not style; it is the only structure in which undefinedness is contained.

Complete rules conflict, partial rules accumulate

A complete rule assigns a single value: max_replicas := 10. If two definitions of the same complete rule both apply to the same input and produce different values, evaluation fails with a conflict. This is deliberate — an ambiguous decision is treated as an error rather than resolved by source order, because source order is not a semantic the language offers.

A partial rule defines a set or an object incrementally: deny contains msg if {...} may be contributed to by many separate rule bodies, in one file or across a package, and the result is the union. This is what makes policy composable. A platform team writes the base rules, a security team adds rules in a separate package that contributes to the same deny set, and neither needs to know about the other’s files. The consumer reads one set.

The same mechanism produces the most common authoring mistake: a partial rule with no matching body yields the empty set, which reads as “no violations” and is indistinguishable from “policy satisfied”. An empty deny set is a legitimate result, so nothing in the evaluation signals that a rule was accidentally shadowed by a typo in its package path.

Safety: binding, not ordering

Variables must be bound before they are used in a comparison or a negation. The language enforces this statically: a variable that appears only inside a not or only on the right side of a comparison is rejected as unsafe at compile time. The rule is about binding, not about textual order — reordering two expressions that both bind is harmless, while reordering an expression before the one that binds its variable is a compile error.

# Rejected: c is not bound by any positive expression
bad if {
	not c.image_matches_policy
}

# Accepted: c comes from iterating the input
good if {
	some c in input.review.object.spec.containers
	not c.image_matches_policy
}

This is a real constraint on how policies are written. A rule cannot be phrased as “for all containers, the condition holds” by negating an existential, because the negation has nothing to quantify over until a positive expression produces the binding. The every construct exists for that case, and it evaluates to true for an empty collection — a vacuous truth that is correct by the usual definition and surprising to anyone who expected “no containers” to be a failure.

Where the cost goes

There are no loops in the imperative sense, but there is iteration, and it is not free. A rule that iterates an array of n elements performs n comparisons per evaluation. A rule that iterates the same array inside another rule that also iterates it is quadratic. The cost model is that of a query planner over a document, and the same optimisation applies: index by key rather than scanning.

Concretely, a policy that answers “is this namespace allowed to use this registry” should look up data.registries[namespace] and compare a set, not scan a list of objects looking for a match. A lookup into an object is proportional to the depth of the path; a scan is proportional to the number of entries. For a decision evaluated on every admission request, the difference is the difference between a policy that costs microseconds and one that costs milliseconds, and the API server’s admission timeout is not generous.

Evaluation is memoised within a single query, so a rule referenced by several others is computed once. It is not memoised across queries, which is why the same policy evaluated per request re-does its work. The optimisation for that case is partial evaluation: given a known data document and a query template, the engine can produce a residual policy with the data-dependent branches already resolved, which is what bundle compilation does. The residual is smaller and has fewer lookups, at the cost of having to be rebuilt whenever data changes.

Recursion is not available. A rule cannot refer to itself, directly or through a cycle, and the compiler rejects the attempt. This bounds the evaluation by the structure of the documents rather than by any termination argument the author would have had to supply, and it means tree-shaped data must be traversed with walk or an explicit comprehension rather than a recursive function.

The same policy text means different things in different positions

A policy evaluated at admission receives an AdmissionReview with oldObject present only on updates and dryRun set when the request is a dry run. The same policy evaluated by a controller receives whatever the controller chooses to pass, and a policy evaluated in CI receives a parsed manifest that has not been through defaulting.

The rules do not change, but the input does, and every rule that depends on a field being present changes meaning with it. This is why a policy that passes its unit tests can still deny legitimate traffic on the first day of enforcement, and why the fixtures used in policy bundle testing have to be captured from the position where the policy will run. The evaluation semantics are stable; the document being evaluated is not. The consequences of getting the position wrong are the subject of what admission can decide, and the same undefinedness behaviour explains why a policy that stops matching is indistinguishable from a policy that is satisfied.