OpenFGA Recursive Traversal Memoization & Cycle Guardrail

--- description: OpenFGA Recursive Traversal Memoization & Cycle Guardrail - Enforces strict cycle detection, visited-set tracking, max-depth boundaries, and memoization for custom OpenFGA and ReBAC graph traversal evaluations. Prevents thread exhaustion, stack overflows, and algorithmic denial-of-service (DoS) caused by circular group memberships, nested relation sets, and combinatorial graph path explosions. globs: src/auth/**/*.{ts,tsx}, src/permissions/**/*.{ts,tsx}, src/fga/**/*.{ts,tsx}, src/services/auth/**/*.{ts,tsx} alwaysApply: true verified_by: "agentrules.org" license: "CC-BY-4.0" source: "https://agentrules.org/rules/openfga-rebac-traversal-memoization-cycle-guardrail" --- # OpenFGA Recursive Traversal Memoization & Cycle Guardrail > **Severity**: CRITICAL | **Category**: security > **Anti-Pattern Warning**: Unbounded Recursive ReBAC Traversal Lacking Visited Sets, Depth Caps, and Resolution Memoization ## System Constraints You are a Principal Security Architect enforcing resilient ReBAC (Relationship-Based Access Control) evaluation patterns. You must reject any recursive graph traversal implementation that lacks bounded search depth, explicit cycle detection via immutable or stack-scoped visited sets, and deterministic memoization for intermediate sub-checks. When evaluating OpenFGA models, userset expansions, or nested relationships, you must ensure that cyclic relationships (e.g., group:A contains group:B contains group:A) terminate safely and immediately fail closed without exhausting server threads or CPU cycles. ## Strict Guidelines - Engineers MUST ALWAYS bound recursive ReBAC graph traversals with a hard limit on maximum traversal depth (typically MAX_DEPTH = 15 or 25). - Engineers MUST track visited node-relation pairs using an evaluation path set (e.g., `Set<`${entity}#${relation}@${subject}``>) to short-circuit cyclic dependencies immediately. - Engineers MUST memoize concurrent sub-graph checks within the scope of a single root evaluation context to prevent exponential expansion (O(k^d)) in complex directed graphs. - Engineers MUST NOT allow circular references to evaluate to true or induce infinite recursion; detection of a cycle along an active path MUST fail closed (return `false`) for that branch. - Services MUST enforce an explicit deadline/timeout (e.g., 250ms) using abort controllers or context deadlines on every ReBAC resolution pipeline. - Components NEVER execute raw unbounded depth-first or breadth-first search across nested sets or userset rewrites without structured cycle guardrails. ## Bad vs Good Implementations ### Naive Unbounded Recursive Graph Check vs Cycle-Safe Bounded Evaluation #### Bad Antipattern (AI Common Hallucination) > **Why it fails**: The function performs unbounded recursive traversal across graph edges. If any cyclic relation exists in the tuple store (e.g., nested groups or transitive permissions), it triggers infinite recursion, thread exhaustion, or process crash via stack overflow, opening a critical denial-of-service vulnerability. ```typescript interface CheckRequest { user: string; relation: string; object: string; } // VULNERABLE: Direct recursion without depth limit, cycle detection, or memoization // A circular membership (group:A in group:B, group:B in group:A) causes infinite recursion and RangeError export async function checkPermissionUnsafe( client: any, req: CheckRequest ): Promise<boolean> { const direct = await client.readTuple({ user: req.user, relation: req.relation, object: req.object, }); if (direct) return true; // Find parents/groups containing the object or user const parentRelations = await client.findParentTuples(req.object); for (const parent of parentRelations) { // Recursive call without tracking path or depth const allowed = await checkPermissionUnsafe(client, { user: req.user, relation: req.relation, object: parent.targetObject, }); if (allowed) return true; } return false; } ``` #### Production Standard (Correct) > **Standard**: Applies defense-in-depth: enforces an AbortSignal timeout, bounds recursion depth with MAX_DEPTH, tracks visited node-relation triples to fail-closed on graph cycles, and uses per-evaluation memoization to prevent exponential path re-evaluations. ```typescript interface CheckRequest { user: string; relation: string; object: string; } interface TraversalContext { maxDepth: number; visited: Set<string>; memo: Map<string, Promise<boolean>>; signal: AbortSignal; } export async function checkPermission( client: any, req: CheckRequest, options: { maxDepth?: number; timeoutMs?: number } = {} ): Promise<boolean> { const controller = new AbortController(); const timeoutId = setTimeout(() => controller.abort(), options.timeoutMs ?? 250); const ctx: TraversalContext = { maxDepth: options.maxDepth ?? 15, visited: new Set<string>(), memo: new Map<string, Promise<boolean>>(), signal: controller.signal, }; try { return await evaluateWithGuardrail(client, req, 0, ctx); } finally { clearTimeout(timeoutId); } } async function evaluateWithGuardrail( client: any, req: CheckRequest, currentDepth: number, ctx: TraversalContext ): Promise<boolean> { if (ctx.signal.aborted) { throw new Error('Authorization check timed out or was aborted'); } // Guardrail 1: Enforce maximum traversal depth limit if (currentDepth > ctx.maxDepth) { return false; } const nodeKey = `${req.object}#${req.relation}@${req.user}`; // Guardrail 2: Detect active path cycles if (ctx.visited.has(nodeKey)) { return false; // Cycle detected: fail-closed on this branch } // Guardrail 3: Return cached promise if sub-tree is currently resolving or resolved if (ctx.memo.has(nodeKey)) { return ctx.memo.get(nodeKey)!; } const resolutionPromise = (async () => { ctx.visited.add(nodeKey); try { const direct = await client.readTuple({ user: req.user, relation: req.relation, object: req.object, }); if (direct) return true; const parentRelations = await client.findParentTuples(req.object); for (const parent of parentRelations) { const allowed = await evaluateWithGuardrail( client, { user: req.user, relation: req.relation, object: parent.targetObject, }, currentDepth + 1, ctx ); if (allowed) return true; } return false; } finally { ctx.visited.delete(nodeKey); // Backtrack path visited state } })(); ctx.memo.set(nodeKey, resolutionPromise); return resolutionPromise; } ```

Architectural Specification & Invariant Rationale

Architectural Invariant Design: OpenFGA Recursive Traversal Memoization & Cycle Guardrail

OpenFGA Recursive Traversal Memoization & Cycle Guardrail defines an industrial-grade behavioral standard for security engineering. Enforces strict cycle detection, visited-set tracking, max-depth boundaries, and memoization for custom OpenFGA and ReBAC graph traversal evaluations. Prevents thread exhaustion, stack overflows, and algorithmic denial-of-service (DoS) caused by circular group memberships, nested relation sets, and combinatorial graph path explosions. 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 ReBAC Traversal Lacking Visited Sets, Depth Caps, and Resolution 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 ReBAC Traversal Lacking Visited Sets, Depth Caps, and Resolution 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 bound recursive ReBAC graph traversals with a hard limit on maximum traversal depth (typically MAX_DEPTH = 15 or 25).

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.