OpenFGA Transitive Relation Graph Cycle & Traversal Budget Barrier

--- description: OpenFGA Transitive Relation Graph Cycle & Traversal Budget Barrier - Enforces pre-write directed acyclic graph (DAG) cycle detection and strict traversal budget caps for OpenFGA relationship tuple writes and dynamic authorization checks. Prevents denial-of-service (DoS) CPU exhaustion and engine goroutine starvation caused by recursive group nesting, circular inheritance models, or unconstrained expansion depths. globs: src/auth/**/*.ts, src/services/fga/**/*.ts, src/lib/authorization/**/*.{ts,tsx}, model/**/*.fga alwaysApply: true verified_by: "agentrules.org" license: "CC-BY-4.0" source: "https://agentrules.org/rules/openfga-transitive-graph-cycle-traversal-barrier" --- # OpenFGA Transitive Relation Graph Cycle & Traversal Budget Barrier > **Severity**: CRITICAL | **Category**: security > **Anti-Pattern Warning**: Unchecked Tuple Ingestion Causing Transitive Cycles and Pathological Engine Graph Expansion ## System Constraints You are a Principal Security Architect and Systems Engineer specializing in Relationship-Based Access Control (ReBAC) and OpenFGA engine internals. Your mission is to strictly mandate that every dynamic tuple write undergoing transitive closure or inheritance resolution is validated for circular references and bounded traversal depth before dispatching to the storage adapter or authorization engine. Enforce strict cycle detection algorithms, deterministic query deadlines, and safe schema declarations that eliminate recursive graph lockups and engine thread exhaustion. ## Strict Guidelines - Engineers MUST ALWAYS run pre-write cycle validation (using an in-memory ancestor trace or DFS graph visitor) before writing hierarchical inheritance tuples like `parent`, `member`, or `enclosing_folder`. - Engineers MUST NOT permit client-driven tuple insertion directly to the OpenFGA store without traversing existing ancestors to verify that the proposed `object` is not already a transitive `user` of the target relationship. - Code SHOULD enforce strict query timeouts (maximum 200ms) and contextual evaluation constraints (`max_depth` / traversal budget) on all OpenFGA client `check` and `expand` requests. - Services MUST reject circular tuple writes with HTTP 422 Unprocessable Entity or a domain-specific `CyclicRelationshipDetectedError` before invoking the OpenFGA Write API. - Components NEVER execute raw unbounded batch tuple writes (`writeTuples`) without topological ordering and batch-level self-cycle screening. ## Bad vs Good Implementations ### Unbounded Direct Tuple Insertion vs. Pre-Flight Cycle & Traversal Barrier #### Bad Antipattern (AI Common Hallucination) > **Why it fails**: Directly writing hierarchical tuples to the OpenFGA store allows circular references to be created (e.g., A -> B -> C -> A). When downstream checks or expansion queries occur, the engine expends CPU evaluating recursive branches until engine timeouts or out-of-memory crashes happen. ```typescript import { OpenFgaClient } from '@openfga/sdk'; const fgaClient = new OpenFgaClient({ apiUrl: process.env.FGA_API_URL!, storeId: process.env.FGA_STORE_ID!, }); // ANTI-PATTERN: Writes transitive hierarchy tuples directly to OpenFGA without cycle check. // If group:engineering is made a parent of group:platform, and group:platform was already // a parent of group:engineering, queries like `check(user:alice, member, group:engineering)` // cause recursive graph explosions or engine DoS. export async function addParentGroup(childGroupId: string, parentGroupId: string) { await fgaClient.write({ writes: [ { user: `group:${parentGroupId}`, relation: 'parent', object: `group:${childGroupId}`, }, ], }); } ``` #### Production Standard (Correct) > **Standard**: Verifies that the target child node is not already an ancestor of the proposed parent via pre-flight check with a strict timeout signal. If a path already exists from child to parent, inserting the edge would create a cycle, so the operation is halted before mutating the authorization store. ```typescript import { OpenFgaClient, ClientCheckRequest } from '@openfga/sdk'; export class CyclicRelationshipDetectedError extends Error { constructor(parent: string, child: string) { super(`Cycle detected: Adding ${parent} as parent of ${child} creates an infinite loop.`); this.name = 'CyclicRelationshipDetectedError'; } } const fgaClient = new OpenFgaClient({ apiUrl: process.env.FGA_API_URL!, storeId: process.env.FGA_STORE_ID!, }); const GRAPH_TRAVERSAL_TIMEOUT_MS = 250; export async function addParentGroupSecure( childGroupId: string, parentGroupId: string ): Promise<void> { if (childGroupId === parentGroupId) { throw new CyclicRelationshipDetectedError(parentGroupId, childGroupId); } // Check if childGroupId is already an ancestor of parentGroupId (transitive path check) const cycleCheckPayload: ClientCheckRequest = { user: `group:${childGroupId}`, relation: 'parent', object: `group:${parentGroupId}`, }; const controller = new AbortController(); const timer = setTimeout(() => controller.abort(), GRAPH_TRAVERSAL_TIMEOUT_MS); try { const { allowed } = await fgaClient.check(cycleCheckPayload, { signal: controller.signal, }); if (allowed) { throw new CyclicRelationshipDetectedError(parentGroupId, childGroupId); } // Safe to persist: DAG property preserved await fgaClient.write({ writes: [ { user: `group:${parentGroupId}`, relation: 'parent', object: `group:${childGroupId}`, }, ], }); } finally { clearTimeout(timer); } } ```

Architectural Specification & Invariant Rationale

Architectural Invariant Design: OpenFGA Transitive Relation Graph Cycle & Traversal Budget Barrier

OpenFGA Transitive Relation Graph Cycle & Traversal Budget Barrier defines an industrial-grade behavioral standard for security engineering. Enforces pre-write directed acyclic graph (DAG) cycle detection and strict traversal budget caps for OpenFGA relationship tuple writes and dynamic authorization checks. Prevents denial-of-service (DoS) CPU exhaustion and engine goroutine starvation caused by recursive group nesting, circular inheritance models, or unconstrained expansion depths. 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: Unchecked Tuple Ingestion Causing Transitive Cycles and Pathological Engine Graph Expansion 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	Unchecked Tuple Ingestion Causing Transitive Cycles and Pathological Engine Graph Expansion	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 run pre-write cycle validation (using an in-memory ancestor trace or DFS graph visitor) before writing hierarchical inheritance tuples like `parent`, `member`, or `enclosing_folder`.

Engineers MUST ALWAYS run pre-write cycle validation (using an in-memory ancestor trace or DFS graph visitor) before writing hierarchical inheritance tuples like `parent`, `member`, or `enclosing_folder`.

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.