Arbitrary recursion using dynamic data references

[jaspervdj]

Expected behavior

OPA ensures non-recursion during Rego evaluation. This is important to maintain some guarantees about productivity and determination; and in general helps static analysis of Rego queries.

Actual behavior

OPA can be tricked into performing recursion by accessing the data document in ways that cannot be determined at compile time.

Steps to reproduce the problem

As an example, we'll just use a single rule that is self-recursive:

package recursion

# This value is not necessarily "known" at compile-time: it can be the
# result of a proper rule with some evaluation logic; possibly depending on
# the input document.
pkg = "recursion"

# A recursion check cannot be performed here.
foo[x] {
  data[pkg]["foo"][x]
}

# Evaluating this will hang forever.
test_foo {
  foo[1]
}

To reproduce, you can use:

opa test recursion.rego

While this is a simple example; there are some complex things that become possible using this trick, e.g. dynamic dispatch to different packages or rules.

This is tested using opa-v0.10.7

Additional info

I think there are two ways in which this can be fixed.

1. Maintain stack information in the topdown evaluator so that recursion can be detected and execution aborted.
2. Stricten up the rules around references and renaming so that cases like the above become illegal.

Option (2) should be preferred in my opinion:

• That way the problem is solved for all backends rather than just the ones that choose to implement this check (I'm somewhat thinking about WASM and topdown here).
• Some future backends (e.g. conversion to SQL and GraphQL-style queries) may not allow these sort of arbitrary references to other queries.

How can we do (2)? I think this should be part of renaming & import resolution.

References can be long chains of known and unknown things:

data.full.package.name.rule_name[idx].attributes["port"]
importname[rule_name][0]

At compile time, these can be analyzed in a straightforward left-to-right direction. Any reference should then either:

• Be a statically known rule followed by some arbitrary references. These are fine by construction.

• Or; it is a reference to data that is not known at compile time. In that case, this reference should only be allowed to refer to actual data (base documents), not rules (virtual documents).

[tsandall]

@jaspervdj thanks for filing this. I agree that this should be caught at compile-time.

The compiler traverses the rule graph for each rule and if a path back to the rule is found then recursion is detected. The problem is that when the rule graph is built the compiler is using the GroundPrefix function to lookup immediate dependencies. We could change this to use ConstantPrefix instead. The downside of using ConstantPrefix is that dynamic dispatch (if it's currently being used) will break.

What we could do to address the downside is add a helper function onto the compiler that would return rules that could match non-constant references. For example, given rules at data.a.b.c.d.R1, data.a.b.c.e.R2, and data.a.b.R3:

GetRulesDynamic(data.a.b[x]) => data.a.b.c.d.R1, data.a.b.c.e.R2, data.a.b.R3
GetRulesDynamic(data.a.b[x].d) => data.a.b.c.d.R1, data.a.b.R3

The variable x could be a reference and the behaviour would be the same.

[jaspervdj]

@tsandall Agreed -- I'm happy to have a look at changing this to ConstantPrefix.

The idea of exhaustively checking all rules that it might match sounds great and is something I hadn't thought about. I will let you know if I need some help with the codebase there, but it looks pretty clean.

[tsandall]

Sounds good. I'd expect the first step will be to add the new helper function to list rules that could match. If the ref operand is not a constant then we can enumerate all of the rules at that point in the rule tree. Once the end of the ref is reached all of the rules underneath that node in the rule tree need to be collected. Once that helper exists, we can update the rule graph build step to use it.

…

On Thu, Jul 25, 2019 at 7:36 AM Jasper Van der Jeugt < ***@***.***> wrote: @tsandall <https://github.com/tsandall> Agreed -- I'm happy to have a look at changing this to ConstantPrefix. The idea of exhaustively checking all rules that it might match sounds great and is something I hadn't thought about. I will let you know if I need some help with the codebase there, but it looks pretty clean. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#1565?email_source=notifications&email_token=AAB2KJLMRYZ2PEQQ6I54C4LQBGF2JA5CNFSM4ID2SFJKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD2ZGWKQ#issuecomment-515009322>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAB2KJLGEPQ25HRBHTJYTTLQBGF2JANCNFSM4ID2SFJA> .

-- -Torin

[tsandall]

Fixed by 44ffb08