OpenFGA Recursive Relation Traversal Depth Ceiling & Cycle Prevention

--- description: OpenFGA Recursive Relation Traversal Depth Ceiling & Cycle Prevention - Enforces deterministic depth ceilings, cycle detection, and strict contextual tuple validation across Zanzibar-style OpenFGA relation models and query clients. Unbounded graph expansions across transitive relations (such as nested group memberships or hierarchical folders) allow malicious or degenerate multi-tenant graphs to trigger exponential fan-out, backend memory exhaustion, and distributed denial-of-service cascades. globs: src/authz/**/*.ts, src/services/authz/**/*.ts, src/lib/openfga/**/*.ts, model/**/*.fga alwaysApply: true verified_by: "agentrules.org" license: "CC-BY-4.0" source: "https://agentrules.org/rules/openfga-recursive-traversal-depth-ceiling" --- # OpenFGA Recursive Relation Traversal Depth Ceiling & Cycle Prevention > **Severity**: CRITICAL | **Category**: security > **Anti-Pattern Warning**: Unbounded Recursive Transitive Relations and Contextual Tuples Triggering Zanzibar Denial-of-Service ## System Constraints You are a Principal Software Architect enforcing enterprise authorization security and resilience across OpenFGA and Zanzibar implementations. You must mandate strict depth boundaries, cycle guards, and pre-traversal validation whenever relation graphs allow transitive or hierarchical expansion. Refuse any architecture that permits unbounded recursive resolution, unvalidated cyclic contextual tuples, or unconstrained graph depth during authorization evaluations. ## Strict Guidelines - Engineers MUST configure explicit resolution ceilings (e.g., max resolve depth ≤ 25) at both server configuration (`OPENFGA_RESOLVE_CHECK_REQUEST_LIMIT`) and client-side wrapper layers. - Engineers MUST validate directed acyclic graph (DAG) invariants prior to persisting relation tuples that represent hierarchical structures (e.g., `parent`, `member`, `enclosing_container`). - Code MUST sanitize and limit dynamic contextual tuples supplied in check and expand calls, rejecting recursive self-references and limiting the injected tuple count to a deterministically bounded payload. - Services MUST implement explicit timeout deadlines and circuit-breaker handling around OpenFGA `check`, `expand`, and `listObjects` operations to gracefully handle depth exhaustion or latency degradation. - Components NEVER execute unbounded graph traversals over tenant-controlled relation hierarchies without applying memoized cycle detection and telemetry alarms on graph expansion ceilings. ## Bad vs Good Implementations ### Enforcing Graph Depth Ceilings and Cycle Detection in OpenFGA Client Calls #### Bad Antipattern (AI Common Hallucination) > **Why it fails**: This implementation passes unvalidated user-provided contextual tuples directly to the OpenFGA client with no cycle detection, no limit on contextual tuple volume, no execution timeout, and no validation of recursion boundaries. Malicious tenants can supply circular or deeply nested relation tuples that cause exponential branch exploration, exhausting authorization service workers. ```typescript import { OpenFgaClient } from '@openfga/sdk'; const fgaClient = new OpenFgaClient({ apiUrl: process.env.FGA_API_URL, storeId: process.env.FGA_STORE_ID, }); // ANTI-PATTERN: Unbounded contextual tuples passed directly from user input // No cycle detection, no depth limits, no timeout, susceptible to graph traversal bombs export async function checkAccessUnsafe( userId: string, relation: string, objectId: string, dynamicTuples: Array<{ user: string; relation: string; object: string }> ): Promise<boolean> { const response = await fgaClient.check({ user: `user:${userId}`, relation, object: objectId, contextualTuples: dynamicTuples, }); return Boolean(response.allowed); } ``` #### Production Standard (Correct) > **Standard**: The hardened implementation guarantees safety by pre-validating contextual tuples against a maximum payload size, enforcing cycle detection using depth-first cycle verification on relation edges, and bounding authorization evaluation with an strict AbortController deadline to guarantee deterministic bounds and prevent ReDoS cascades. ```typescript import { OpenFgaClient, ClientCheckRequest } from '@openfga/sdk'; const MAX_CONTEXTUAL_TUPLES = 16; const MAX_TRAVERSAL_TIMEOUT_MS = 800; const fgaClient = new OpenFgaClient({ apiUrl: process.env.FGA_API_URL!, storeId: process.env.FGA_STORE_ID!, }); interface TupleKey { user: string; relation: string; object: string; } function assertAcyclicContext(tuples: TupleKey[]): void { if (tuples.length > MAX_CONTEXTUAL_TUPLES) { throw new Error(`Contextual tuple count exceeds threshold: ${tuples.length} > ${MAX_CONTEXTUAL_TUPLES}`); } const adjacency = new Map<string, Set<string>>(); for (const { user, object } of tuples) { if (user === object) { throw new Error(`Self-referential cycle detected on tuple node: ${user}`); } if (!adjacency.has(user)) adjacency.set(user, new Set()); adjacency.get(user)!.add(object); } const visited = new Set<string>(); const inStack = new Set<string>(); function hasCycle(node: string): boolean { visited.add(node); inStack.add(node); for (const neighbor of adjacency.get(node) ?? []) { if (!visited.has(neighbor) && hasCycle(neighbor)) return true; if (inStack.has(neighbor)) return true; } inStack.delete(node); return false; } for (const node of adjacency.keys()) { if (!visited.has(node) && hasCycle(node)) { throw new Error(`Graph cycle detected involving node: ${node}`); } } } export async function checkAccessSafe( userId: string, relation: string, objectId: string, dynamicTuples: TupleKey[] = [] ): Promise<boolean> { assertAcyclicContext(dynamicTuples); const checkPayload: ClientCheckRequest = { user: `user:${userId}`, relation, object: objectId, contextualTuples: dynamicTuples, }; const controller = new AbortController(); const timer = setTimeout(() => controller.abort(), MAX_TRAVERSAL_TIMEOUT_MS); try { const response = await fgaClient.check(checkPayload, { signal: controller.signal, }); return Boolean(response.allowed); } catch (err: unknown) { if ((err as Error).name === 'AbortError') { throw new Error('Authorization evaluation exceeded traversal depth/time budget'); } throw err; } finally { clearTimeout(timer); } } ```

Architectural Specification & Invariant Rationale

Architectural Invariant Design: OpenFGA Recursive Relation Traversal Depth Ceiling & Cycle Prevention

OpenFGA Recursive Relation Traversal Depth Ceiling & Cycle Prevention defines an industrial-grade behavioral standard for security engineering. Enforces deterministic depth ceilings, cycle detection, and strict contextual tuple validation across Zanzibar-style OpenFGA relation models and query clients. Unbounded graph expansions across transitive relations (such as nested group memberships or hierarchical folders) allow malicious or degenerate multi-tenant graphs to trigger exponential fan-out, backend memory exhaustion, and distributed denial-of-service cascades. 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 Transitive Relations and Contextual Tuples Triggering Zanzibar Denial-of-Service 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 Transitive Relations and Contextual Tuples Triggering Zanzibar Denial-of-Service	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 configure explicit resolution ceilings (e.g., max resolve depth ≤ 25) at both server configuration (`OPENFGA_RESOLVE_CHECK_REQUEST_LIMIT`) and client-side wrapper layers.

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.