Add depth validation for ASTs loaded through ParsedExprToAst / CheckedExprToAst

[0xASTRA]

Summary

cel-go currently applies recursion/depth limits during string parsing, but the same kind of depth validation does not appear to be enforced when expressions are loaded from pre-built AST protos through APIs such as ParsedExprToAst / CheckedExprToAst.

This means callers that store, deserialize, or otherwise ingest CEL ASTs directly can bypass the parser recursion guard and pass a deeply nested AST into later phases such as checking or program construction.

In extreme cases, this can lead to unbounded recursive traversal and a Go runtime stack overflow rather than a normal returned error.

Affected path

The issue is not about normal CEL source parsing. The parser already has recursion limiting.

The affected scenario is non-parser AST ingestion, for example:

cel.ParsedExprToAst(...)
cel.CheckedExprToAst(...)
env.Check(...)
env.Program(...)

A caller may reasonably use these APIs to load previously parsed or checked expressions from storage. If the stored AST is deeply nested, later recursive traversal in the checker / planner can reach excessive depth.

Expected behavior

ASTs loaded through proto/native conversion APIs should be subject to a bounded expression-depth validation step before recursive checking or planning.

If an AST exceeds the supported maximum depth, cel-go should return an ordinary error, similar in spirit to parser depth-limit failures.

Actual behavior

The parser depth guard is bypassed when the input is already an AST/proto. Later recursive processing can traverse the AST without an equivalent depth limit.

For sufficiently nested inputs, this can crash the host process with:

fatal error: stack overflow

instead of returning a recoverable error.

Suggested fix

Add depth validation for ASTs entering through non-parser ingestion paths, ideally reusing the same limit as the parser default.

Possible approaches:

1. Add a reusable AST depth validator in the common AST layer.
2. Call it from ParsedExprToAst / CheckedExprToAst, or from the public Check() / Program() construction path.
3. Ensure checker and planner recursive traversals cannot exceed the configured maximum expression depth.
4. Add a regression test using a moderately deep synthetic AST that exceeds the configured limit but does not attempt to exhaust the process stack.

The default parser recursion limit appears to be 250, so using the same default for loaded ASTs would keep behavior consistent.

Security / reliability impact

Any embedder that accepts stored or serialized CEL ASTs from untrusted or semi-trusted storage can currently receive an unrecoverable process crash instead of a validation error.

This is especially relevant for systems that treat stored CEL ASTs as policy objects and compile or load them in a long-running service.

Notes

I originally reported this through Google Bug Hunters, and they confirmed that since this is not being tracked for reward, it is acceptable to proceed publicly through GitHub.

[TristonianJones]

Any embedder that accepts stored or serialized CEL ASTs from untrusted or semi-trusted storage can currently receive an unrecoverable process crash instead of a validation error.

For posterity, it is a really bad idea to accept CEL ASTs from untrusted users. This is an anti-pattern to be avoided. If you accept ASTs rather than user strings you open yourself up to so many vulnerabilities it's not useful.

[wilyan09007]

That makes sense, and I agree, users should submit CEL strings rather than ASTs.

My intent with #1334 is just defensive hardening: loaded ASTs from ParsedExprToAst / CheckedExprToAst can currently reach Check / Program and crash on extreme depth instead of returning an error.

The PR adds a bounded depth check there, using the parser's existing 250 default. Let me know if I'm misunderstanding the intended contract for these APIs.