OpenFGA Bounded Graph Traversal & Cycle-Detection Depth Invariant

--- description: OpenFGA Bounded Graph Traversal & Cycle-Detection Depth Invariant - Protects distributed authorization engines against catastrophic query latency spikes, resource exhaustion, and Denial of Service (DoS) caused by circular or unbounded nested group expansions. Mandates deterministic max-depth limits, visited-set cycle detection, and strict timeouts for all relationship tuple lookups and custom graph expansions. Enforces validation guards in both application-layer tuple ingestion pipelines and custom authorization middleware. globs: src/auth/**/*.{ts,js}, src/services/auth/**/*.{ts,js}, src/fga/**/*.{ts,js}, src/lib/permissions/**/*.{ts,js} alwaysApply: true verified_by: "agentrules.org" license: "CC-BY-4.0" source: "https://agentrules.org/rules/openfga-bounded-traversal-cycle-detection-invariant" --- # OpenFGA Bounded Graph Traversal & Cycle-Detection Depth Invariant > **Severity**: CRITICAL | **Category**: security > **Anti-Pattern Warning**: Unbounded recursive traversal of nested group tuples without visited-set tracking or hard depth caps ## System Constraints You are a Principal Security Architect enforcing the OpenFGA Bounded Graph Traversal and Cycle-Detection Depth Invariant. In any authorization system resolving transitive relationships (e.g., nested groups, parent-child hierarchies, or role inheritances), you must enforce strict, deterministic graph-traversal bounds. Every traversal step must track visited nodes to abort cyclic relationships immediately, respect a non-negotiable maximum resolution depth, and execute under a hard contextual deadline/timeout. Never allow unchecked recursive expansion or open-ended transitive queries. ## Strict Guidelines - Engineers MUST ALWAYS enforce a strictly bounded depth (e.g., maxDepth <= 5) and contextual abort signal/timeout when resolving transitive OpenFGA relationships or nested groups. - Engineers MUST ALWAYS maintain an immutable or explicit visited node set (Set<string>) during traversal to immediately short-circuit circular references (A -> B -> A). - Engineers MUST NOT permit unbounded or deeply nested group ingestion without cycle detection validation at the point of relationship tuple writes. - Services MUST fail closed with a deterministic AuthorizationEvaluationTimeoutError or CycleDetectedError rather than letting engine queries hang indefinitely or recurse until stack overflow. - Components NEVER issue unchecked recursive Check or Expand calls without bounded batching and contextual deadline propagation. ## Bad vs Good Implementations ### Transitive Group Membership Resolution with Depth Guard & Visited Cycle Detection #### Bad Antipattern (AI Common Hallucination) > **Why it fails**: This implementation lacks visited node tracking, maximum recursion depth bounds, and timeout handling. A cyclic relationship (group:A parent group:B and group:B parent group:A) induces an infinite evaluation loop, exhausting memory, starving the Node.js event loop, and triggering Denial of Service. ```typescript import { OpenFgaClient } from '@openfga/sdk'; export async function isUserInGroupUnbounded( fga: OpenFgaClient, userId: string, groupId: string ): Promise<boolean> { // Anti-pattern: Unbounded recursion with no visited set, no depth limit, and no timeout const { allowed } = await fga.check({ user: `user:${userId}`, relation: 'member', object: `group:${groupId}`, }); if (allowed) return true; // Query sub-groups recursively without depth caps or cycle detection const { tuples } = await fga.read({ user: `group:${groupId}`, relation: 'parent', }); for (const tuple of tuples) { const parentGroupId = tuple.key.object.replace('group:', ''); // Infinite loop occurs if groupA -> groupB -> groupA if (await isUserInGroupUnbounded(fga, userId, parentGroupId)) { return true; } } return false; } ``` #### Production Standard (Correct) > **Standard**: Enforces deterministic limits: MAX_TRAVERSAL_DEPTH caps the graph expansion depth, a visited Set guards against infinite cyclic loops by immediately rejecting repeated nodes, and an AbortSignal enforces a hard timeout budget across transitive evaluation calls. ```typescript import { OpenFgaClient } from '@openfga/sdk'; const MAX_TRAVERSAL_DEPTH = 5; const TRAVERSAL_TIMEOUT_MS = 250; export class TraversalDepthExceededError extends Error { constructor(maxDepth: number) { super(`Authorization traversal exceeded maximum bounded depth of ${maxDepth}`); this.name = 'TraversalDepthExceededError'; } } export class CycleDetectedError extends Error { constructor(nodeId: string) { super(`Authorization graph cycle detected at node: ${nodeId}`); this.name = 'CycleDetectedError'; } } export async function isUserInGroupBounded( fga: OpenFgaClient, userId: string, groupId: string, depth = 0, visited = new Set<string>(), signal?: AbortSignal ): Promise<boolean> { if (depth > MAX_TRAVERSAL_DEPTH) { throw new TraversalDepthExceededError(MAX_TRAVERSAL_DEPTH); } const nodeKey = `group:${groupId}`; if (visited.has(nodeKey)) { throw new CycleDetectedError(nodeKey); } visited.add(nodeKey); const effectiveSignal = signal ?? AbortSignal.timeout(TRAVERSAL_TIMEOUT_MS); const checkResult = await fga.check( { user: `user:${userId}`, relation: 'member', object: nodeKey, }, { signal: effectiveSignal } ); if (checkResult.allowed) { return true; } const { tuples } = await fga.read( { user: nodeKey, relation: 'parent', }, { signal: effectiveSignal } ); for (const tuple of tuples) { const parentGroupId = tuple.key.object.replace('group:', ''); const inParent = await isUserInGroupBounded( fga, userId, parentGroupId, depth + 1, new Set(visited), effectiveSignal ); if (inParent) return true; } return false; } ```

Architectural Specification & Invariant Rationale

Architectural Invariant Design: OpenFGA Bounded Graph Traversal & Cycle-Detection Depth Invariant

OpenFGA Bounded Graph Traversal & Cycle-Detection Depth Invariant defines an industrial-grade behavioral standard for security engineering. Protects distributed authorization engines against catastrophic query latency spikes, resource exhaustion, and Denial of Service (DoS) caused by circular or unbounded nested group expansions. Mandates deterministic max-depth limits, visited-set cycle detection, and strict timeouts for all relationship tuple lookups and custom graph expansions. Enforces validation guards in both application-layer tuple ingestion pipelines and custom authorization middleware. 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 traversal of nested group tuples without visited-set tracking or hard depth caps 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 traversal of nested group tuples without visited-set tracking or hard depth caps	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 a strictly bounded depth (e.g., maxDepth <= 5) and contextual abort signal/timeout when resolving transitive OpenFGA relationships or nested groups.

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.