OpenFGA Graph Traversal Cycle Detection and Depth Ceilings

--- description: OpenFGA Graph Traversal Cycle Detection and Depth Ceilings - Enforces strict recursion depth ceilings and memoized visited-path sets during OpenFGA relational tuple expansion and check operations. Prevents Denial of Service (DoS), catastrophic algorithmic complexity (O(N^k)), and recursive stack overflow vulnerabilities caused by self-referential or cyclic relational hierarchies (e.g., recursive team-in-team or nested group-membership graphs). globs: src/authz/**/*.{ts,js}, src/services/fga/**/*.{ts,js}, src/lib/authorization/**/*.{ts,js}, src/middleware/auth/**/*.{ts,js} alwaysApply: true verified_by: "agentrules.org" license: "CC-BY-4.0" source: "https://agentrules.org/rules/openfga-tuple-cycle-breaker" --- # OpenFGA Graph Traversal Cycle Detection and Depth Ceilings > **Severity**: CRITICAL | **Category**: security > **Anti-Pattern Warning**: Unbounded Recursive Resolution of Nested Relational Tuples Without Path Memoization or Depth Limits ## System Constraints You are a Principal Software Architect enforcing zero-trust authorization safety. When processing or traversing OpenFGA relationship tuples, nested sets, or group hierarchies, you must enforce deterministic bounded graph traversals. You MUST mandate explicit max-depth ceilings, immutable visited path tracking, and short-circuiting circuit breakers to prevent infinite recursion, thread exhaustion, and Denial-of-Service attacks via relational cycles. ## Strict Guidelines - Engineers MUST ALWAYS pass an explicit, immutable cycle-detection tracking set (visited path state) through every recursive authorization resolution pass. - Engineers MUST ALWAYS enforce a hard compile-time or static configuration depth ceiling (e.g., MAX_DEPTH = 25) that terminates graph traversals immediately upon violation. - Engineers MUST NOT rely on default call-stack unwinding or runtime stack-depth limits (V8 max call stack) as an authorization cycle-breaker. - Services MUST abort evaluation and emit an explicit CycleDetectedError or MaxTraversalDepthExceededError when duplicate nodes within the same evaluation branch are encountered. - Code SHOULD leverage OpenFGA contextual tuples with pre-computed transitive closure caches where applicable to avoid deeply nested live traversals. - Components NEVER execute unbounded breadth-first search (BFS) or depth-first search (DFS) on arbitrary user-managed group assignment graphs without rate-limiting and timeouts. ## Bad vs Good Implementations ### Naive Recursive Group Membership Resolution vs. Cycle-Protected Graph Traversal #### Bad Antipattern (AI Common Hallucination) > **Why it fails**: The naive implementation contains neither recursion depth limits nor a visited-node set. In the event of circular group nesting, this results in infinite recursive network requests, latency amplification, potential stack overflow exceptions, and distributed Denial of Service against the authorization plane. ```typescript import { OpenFgaClient } from '@openfga/sdk'; interface ResolutionContext { user: string; targetGroup: string; } // ANTI-PATTERN: Unbounded recursion without visited node tracking or max-depth check. // Cyclic graphs (Group A -> Group B -> Group A) trigger RangeError: Maximum call stack size exceeded // or cause continuous downstream OpenFGA API query exhaustion. export async function isMemberOfGroup(fga: OpenFgaClient, ctx: ResolutionContext): Promise<boolean> { const response = await fga.read({ tuple_key: { user: `user:${ctx.user}`, relation: 'member', object: `group:${ctx.targetGroup}` } }); if (response.tuples && response.tuples.length > 0) { return true; } // Check parent groups recursively const parentTuples = await fga.read({ tuple_key: { relation: 'parent', object: `group:${ctx.targetGroup}` } }); for (const tuple of parentTuples.tuples ?? []) { const parentGroupId = tuple.key.user.replace('group:', ''); if (await isMemberOfGroup(fga, { user: ctx.user, targetGroup: parentGroupId })) { return true; } } return false; } ``` #### Production Standard (Correct) > **Standard**: Implements an immutable path set (`visitedPath`) along the search branch to catch self-referential loops in O(1) time before calling external services, combined with a strict recursion ceiling (`maxDepth`) to guarantee deterministic bounded runtime. ```typescript import { OpenFgaClient } from '@openfga/sdk'; export class CycleDetectedError extends Error { constructor(node: string) { super(`Circular reference detected in OpenFGA traversal at node: ${node}`); this.name = 'CycleDetectedError'; } } export class MaxTraversalDepthExceededError extends Error { constructor(depth: number) { super(`OpenFGA traversal exceeded safe depth ceiling: ${depth}`); this.name = 'MaxTraversalDepthExceededError'; } } interface SafeTraversalOptions { readonly maxDepth?: number; readonly currentDepth?: number; readonly visitedPath?: ReadonlySet<string>; } const DEFAULT_MAX_DEPTH = 15; export async function isMemberOfGroupSafely( fga: OpenFgaClient, user: string, targetGroup: string, options: SafeTraversalOptions = {} ): Promise<boolean> { const maxDepth = options.maxDepth ?? DEFAULT_MAX_DEPTH; const currentDepth = options.currentDepth ?? 0; const visitedPath = options.visitedPath ?? new Set<string>(); if (currentDepth > maxDepth) { throw new MaxTraversalDepthExceededError(currentDepth); } const groupKey = `group:${targetGroup}`; if (visitedPath.has(groupKey)) { throw new CycleDetectedError(groupKey); } // Execute direct check first using OpenFGA native single-flight check const { allowed } = await fga.check({ tuple_key: { user: `user:${user}`, relation: 'member', object: groupKey } }); if (allowed) { return true; } // Propagate path tracking immutably to isolate branches const nextVisitedPath = new Set(visitedPath).add(groupKey); const parentTuples = await fga.read({ tuple_key: { relation: 'parent', object: groupKey } }); for (const tuple of parentTuples.tuples ?? []) { const parentGroupId = tuple.key.user.replace('group:', ''); const isMember = await isMemberOfGroupSafely(fga, user, parentGroupId, { maxDepth, currentDepth: currentDepth + 1, visitedPath: nextVisitedPath }); if (isMember) { return true; } } return false; } ```

Architectural Specification & Invariant Rationale

Architectural Invariant Design: OpenFGA Graph Traversal Cycle Detection and Depth Ceilings

OpenFGA Graph Traversal Cycle Detection and Depth Ceilings defines an industrial-grade behavioral standard for security engineering. Enforces strict recursion depth ceilings and memoized visited-path sets during OpenFGA relational tuple expansion and check operations. Prevents Denial of Service (DoS), catastrophic algorithmic complexity (O(N^k)), and recursive stack overflow vulnerabilities caused by self-referential or cyclic relational hierarchies (e.g., recursive team-in-team or nested group-membership 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 Resolution of Nested Relational Tuples Without Path Memoization or Depth Limits 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 Resolution of Nested Relational Tuples Without Path Memoization or Depth Limits	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 pass an explicit, immutable cycle-detection tracking set (visited path state) through every recursive authorization resolution pass.

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.