Asymptotic Analysis

[ashutosh-narkar]

It would helpful if a policy author or the OPA administrator could restrict how complex user-provided policies are allowed to be. This would enable the OPA admin or top-level policy author to inject user-provided policies while at the same time ensuring acceptable performance. Those controls could be enforced globally, per-package, or perhaps per-module. Global and per-package make the most sense to start.

Initially the following complexity restrictions would be valuable:

• Linear in the size of the policy
• Linear in the policy and the input
• Linear in the policy and the input and external data
• Sub-linear in the policy (e.g. rules must enable the Rule-indexing to kick-in)

For per-package complexity restrictions the user might write:

package kubernetes.admission
complexity O(policy * input * data)

deny[msg] { … }

Initial investigation implies that it may be useful to define complexity restrictions based on the slice of external data as well, leading to complexity restrictions that mention the path.

complexity O(policy * input * data.foo)

For global complexity restrictions, we could invent a new command line parameter (and Go library argument), e.g.

opa eval … --complexity "O(policy * input * data)"

This restriction should be a compile-time restriction, meaning that when the user loads the policy she gets an error if the policy fails to meet the complexity restriction.

[stale[bot]]

This issue has been automatically marked as inactive because it has not had any activity in the last 30 days.