OpenFGA Sub-Graph Recursive Resolution Budgeting and Memoization Invariant

--- description: OpenFGA Sub-Graph Recursive Resolution Budgeting and Memoization Invariant - Enforces deterministic depth horizons, node evaluation budgets, and memoized subproblem evaluation caches across recursive OpenFGA relation checks. Prevents algorithmic authorization denial-of-service (Auth-DoS) and thread pool exhaustion driven by cyclical or deeply nested transitive relationship graphs. globs: src/**/authz/**/*.{ts,tsx,js,jsx}, src/**/fga/**/*.{ts,tsx,js,jsx}, src/**/permissions/**/*.{ts,tsx,js,jsx}, lib/auth/**/*.{ts,tsx,js,jsx} alwaysApply: true verified_by: "agentrules.org" license: "CC-BY-4.0" source: "https://agentrules.org/rules/openfga-subgraph-recursive-resolution-budgeting" --- # OpenFGA Sub-Graph Recursive Resolution Budgeting and Memoization Invariant > **Severity**: CRITICAL | **Category**: security > **Anti-Pattern Warning**: Unbounded Recursive Authorization Traversals Lacking Depth Caps and Subproblem Memoization ## System Constraints You are a Principal Security Architect enforcing the OpenFGA Sub-Graph Recursive Resolution Budgeting Invariant. Authorization graphs with deep or circular relations (e.g., nested groups, parent-folder hierarchies, transitive viewer delegation) are vulnerable to algorithmic denial of service without deterministic traversal horizons. You must enforce strict depth limits, node evaluation budgets, and subproblem memoization across all OpenFGA client evaluation wrappers. ## Strict Guidelines - Engineers MUST ALWAYS enforce an explicit execution budget (both maximum recursion depth and total node evaluation budget) on all composite OpenFGA relationship traversals. - Engineers MUST NOT issue raw, unbudgeted recursive relationship expansions or nested tuple checks within application loops without memoizing intermediate (user, relation, object) subproblems. - Code SHOULD propagate an immutable evaluation context carrying remaining budget counters, abort signals, and a memoization cache across all recursive check branches. - Services MUST fail closed with a deterministic `AuthorizationBudgetExceededError` whenever a graph traversal exhausts either the maximum depth or total evaluation count. - Components NEVER execute concurrent un-deduplicated identical sub-graph checks; inflight evaluation promises MUST be coalesced across concurrent authorization branches. ## Bad vs Good Implementations ### Unbounded Recursive Relation Expansion vs. Budgeted Memoized Evaluation #### Bad Antipattern (AI Common Hallucination) > **Why it fails**: The check recursively walks 'parent' relationships without a depth ceiling, node traversal counter, cycle detection, or subproblem memoization. A cyclical relationship graph or deeply nested tree creates exponential network calls, saturating the OpenFGA store and leading to authorization denial-of-service. ```typescript import { OpenFgaClient } from '@openfga/sdk'; export async function checkNestedPermission( fgaClient: OpenFgaClient, user: string, relation: string, object: string ): Promise<boolean> { // Anti-Pattern: Unbounded recursion without depth limits, cycle detection, or memoization const { allowed } = await fgaClient.check({ user, relation, object, }); if (allowed) return true; // Naively traverse parent relationships recursively; cyclic or deep graphs induce Auth-DoS const { tuples } = await fgaClient.read({ object, relation: 'parent', }); for (const tuple of tuples) { const parentAllowed = await checkNestedPermission( fgaClient, user, relation, tuple.key.user ); if (parentAllowed) return true; } return false; } ``` #### Production Standard (Correct) > **Standard**: Implements deterministic recursive invariants: bounds graph walk with `maxDepth` and `maxEvaluations`, eliminates duplicate subproblems via `memo` map (preventing exponential fan-out), and tracks `visited` set to short-circuit cycles safely. Fails closed with `AuthorizationBudgetExceededError`. ```typescript import { OpenFgaClient } from '@openfga/sdk'; export class AuthorizationBudgetExceededError extends Error { constructor(message: string) { super(message); this.name = 'AuthorizationBudgetExceededError'; } } export interface ResolutionBudget { readonly maxDepth: number; readonly maxEvaluations: number; currentDepth: number; evaluationsConsumed: number; } export interface ResolutionContext { budget: ResolutionBudget; memo: Map<string, Promise<boolean>>; visited: Set<string>; } export async function checkNestedPermissionBudgeted( fgaClient: OpenFgaClient, user: string, relation: string, object: string, context?: ResolutionContext ): Promise<boolean> { const ctx: ResolutionContext = context ?? { budget: { maxDepth: 8, maxEvaluations: 50, currentDepth: 0, evaluationsConsumed: 0 }, memo: new Map(), visited: new Set(), }; // Invariant 1: Cycle detection const nodeKey = `${user}#${relation}@${object}`; if (ctx.visited.has(nodeKey)) { return false; // Cycle detected: fail-safe cycle termination } // Invariant 2: Subproblem memoization / inflight coalescing const cached = ctx.memo.get(nodeKey); if (cached !== undefined) { return cached; } // Invariant 3: Deterministic budget horizons if (ctx.budget.currentDepth >= ctx.budget.maxDepth) { throw new AuthorizationBudgetExceededError(`Depth limit exceeded: ${ctx.budget.currentDepth}`); } if (++ctx.budget.evaluationsConsumed > ctx.budget.maxEvaluations) { throw new AuthorizationBudgetExceededError(`Evaluation budget exceeded: ${ctx.budget.evaluationsConsumed}`); } ctx.visited.add(nodeKey); const evaluationPromise = (async (): Promise<boolean> => { const { allowed } = await fgaClient.check({ user, relation, object, contextualTuples: [], }); if (allowed) return true; const { tuples } = await fgaClient.read({ object, relation: 'parent', }); const nextCtx: ResolutionContext = { budget: { ...ctx.budget, currentDepth: ctx.budget.currentDepth + 1 }, memo: ctx.memo, visited: new Set(ctx.visited), }; for (const tuple of tuples) { const parentAllowed = await checkNestedPermissionBudgeted( fgaClient, user, relation, tuple.key.user, nextCtx ); if (parentAllowed) return true; } return false; })(); ctx.memo.set(nodeKey, evaluationPromise); return evaluationPromise; } ```

Architectural Specification & Invariant Rationale

Architectural Invariant Design: OpenFGA Sub-Graph Recursive Resolution Budgeting and Memoization Invariant

OpenFGA Sub-Graph Recursive Resolution Budgeting and Memoization Invariant defines an industrial-grade behavioral standard for security engineering. Enforces deterministic depth horizons, node evaluation budgets, and memoized subproblem evaluation caches across recursive OpenFGA relation checks. Prevents algorithmic authorization denial-of-service (Auth-DoS) and thread pool exhaustion driven by cyclical or deeply nested transitive relationship graphs. Modern software architectures require strict adherence to deterministic patterns to guarantee high availability, maintainability, and zero security vulnerabilities.

Framework Paradigm Shift & Drift MechanicsLLMs are trained on millions of open-source repositories containing outdated code, legacy idioms, and unpatched antipatterns. When coding assistants generate implementations for this stack, they default to common statistical tokens: Unbounded Recursive Authorization Traversals Lacking Depth Caps and Subproblem Memoization Without an explicit system instruction file, developers spend hours debugging silent failures.

Failure Modes & Production Blast Radius

Hazard Analysis: What Breaks Without This Rule

The following failure modes have been cataloged from hundreds of hours of production code reviews where AI assistants produced non-compliant implementations:

Failure Mode	AI Symptom (The Anti-Pattern)	Severity	Production Impact & Remedy
AI Hallucination & Deprecation Drift	Unbounded Recursive Authorization Traversals Lacking Depth Caps and Subproblem Memoization	Critical	Violating this industrial standard introduces regression bugs, security risks, and unexpected runtime failures in production. Enforce explicit behavioral system directives across all AI coding assistants in your repository.
Silent Architecture Inconsistency	AI assistants produce mixed paradigms across files, creating fragmented codebase conventions.	Medium	Increases cognitive load during code reviews and leads to maintenance debt across engineering teams. Pin project conventions in .cursor/rules, CLAUDE.md, and AGENTS.md so all team agents follow identical guardrails.

Architectural Directives in Detail

Step-by-Step Production Directives

Each rule constraint below is injected into the AI agent's system prompt to establish deterministic boundaries:

Engineers MUST ALWAYS enforce an explicit execution budget (both maximum recursion depth and total node evaluation budget) on all composite OpenFGA relationship traversals.

Rationale:AI models frequently generate unconstrained code here because statistical language distributions lack project-specific architectural context. Mandating this directive ensures that generated code adheres to verified industrial production requirements.