Skip to main content
← Back to list
01Issue
FeatureShippedSwamp CLI
Assigneesstack72

Relationships

#1029 serve-auth: CEL cost-bounding for grant conditions

Opened by stack72 · 7/8/2026· Shipped 7/8/2026

Parent

Sub-issue of #662 (serve authentication & authorization). Phase 2, Track B item 1.

Summary

Add cost-bounding to the CEL grant condition evaluator so that expensive or malicious conditions are rejected at write time. This hardens the authorization system before rule packs land (Track B item 2), where untrusted third-party conditions will be evaluated in the authorization path.

The sealed CEL environment and write-time validation already exist (#670). This issue adds limits on top of the existing validation.

What to build

All checks are enforced at write time (grant creation, file reconciliation, pack enablement) via `validateGrantCondition` in `src/infrastructure/cel/grant_condition_environment.ts`. Existing grants created before these limits are unaffected — only new grants are validated.

1. AST depth limit (≤ 24)

Parse the condition, walk the AST tree, reject if max depth exceeds 24. This protects the parser itself and keeps conditions readable.

A condition approaching the cap is a signal the policy concept belongs in the data model (a tag, a resource attribute), not in the expression.

2. Comprehension nesting limit (≤ 2)

Count nested comprehensions in the parsed AST. CEL's `in` operator, `exists`, `all`, and `filter` all use comprehensions. Nesting ≤ 2 caps the polynomial degree — the highest-leverage single rule since it bounds the cost of any condition directly.

3. Per-condition cost budget

Estimate the cost of a condition from AST node count and comprehension sizes. Reject if the estimated worst-case cost exceeds a budget. The budget is in deterministic units (AST-node evaluations / comprehension iterations) — never wall-clock, which would make the same grant pass on an idle server and fail under load.

The write-time static estimation rejects any condition whose worst case exceeds the budget, so the author sees the error at grant creation, not at runtime.

4. `matches()` regex validation

The `matches()` function uses backtracking JS RegExp (not RE2). Two guards:

  • Pattern must be a string literal — enforced in the write-time pass. The regex sits in plain sight next to the grant. Data values can never become patterns (otherwise `matches(name, tags.pattern)` would hand whoever names a resource control of the regex).
  • Regex complexity check — reject patterns with known catastrophic backtracking signatures (nested quantifiers like `(a+)+$`, excessive alternation). Static analysis of the regex pattern at write time.

5. Aggregate per-decision budget

Cap the total cost across all conditions evaluated in a single `decide()` call. This prevents rule volume (hundreds of cheap conditions from a pack) from recomposing what per-condition limits prevent.

Enforce in `GrantBasedAccessDecisionService.decide()` — if aggregate evaluation cost exceeds the budget, fail the decision (deny) and log loudly. This is a runtime check, not a write-time check.

Key invariants

  • Write-time validation catches errors at authoring. A bad condition fails when the admin creates the grant, not silently at runtime.
  • Existing grants are unaffected. Limits only apply to new grants created after this change ships.
  • One ratchet governs all values. Raising a limit later is free; lowering one invalidates grants already in the field. Start generous-but-bounded, never unbounded.
  • The sealed environment is the prerequisite. The seal (no I/O, no extension functions, no data/vault/env receivers) is what makes cost-bounding meaningful — a host function would be the escape hatch out of all guarantees. The seal already exists from #670.

Implementation

All changes in `src/infrastructure/cel/grant_condition_environment.ts` (validation) and `src/domain/access/grant_based_access_decision_service.ts` (aggregate budget).

The `validateGrantCondition` function currently checks:

  • Source length ≤ 1KB
  • CEL syntax (parse)
  • CEL type checking (check against the kind's declared environment)

Add to the same function:

  • AST depth check
  • Comprehension nesting check
  • Per-condition cost estimation
  • `matches()` regex validation

The aggregate budget is a separate check in `decide()`.

Tests

  • Condition at AST depth 24 → accepted
  • Condition at AST depth 25 → rejected with clear error
  • Condition with comprehension nesting 2 → accepted
  • Condition with comprehension nesting 3 → rejected
  • Condition exceeding cost budget → rejected
  • `matches()` with simple literal pattern → accepted
  • `matches()` with catastrophic backtracking pattern → rejected
  • `matches()` with non-literal pattern argument → rejected
  • Aggregate budget exceeded across multiple conditions → decision fails (deny)
  • Existing grants (created before limits) continue to evaluate normally

Out of scope

  • Rule packs — Track B item 2 (depends on this)
  • Runtime wall-clock timeout — already exists as detection-only (from previous security hardening)
  • Extension-registered CEL functions — permanently sealed, not an open question

References

  • CEL grant environment: `src/infrastructure/cel/grant_condition_environment.ts`
  • Grant condition validation: `validateGrantCondition` in same file
  • Decision service: `src/domain/access/grant_based_access_decision_service.ts`
  • Policy snapshot condition evaluator: `src/domain/access/policy_snapshot.ts`
  • Design doc discussion: #662 phase breakdown (CEL cost-bounding section)
02Bog Flow
✓OPEN✓TRIAGED✓IN PROGRESS✓SHIPPED+ 1 MOREASSIGNED+ 5 MOREREVIEW+ 4 MOREPR_MERGED+ 1 MORENOTIFICATION_SKIPPED

Shipped

7/8/2026, 4:11:28 PM

Click a lifecycle step above to view its details.

03Sludge Pulse
stack72 assigned stack727/8/2026, 12:54:47 AM

Sign in to post a ripple.