OpenFGA Zanzibar Cyclic Graph Traversal & Contextual Tuple Invariant

--- description: OpenFGA Zanzibar Cyclic Graph Traversal & Contextual Tuple Invariant - Enforces strict bounds, cycle detection, and contextual tuple sanitization for OpenFGA relationship-based access control (ReBAC) evaluations. Prevents algorithmic denial-of-service (Graph DoS) and unbounded recursive expansion attacks triggered by deep or circular relationship graphs. globs: src/auth/**/*.{ts,tsx}, src/lib/fga/**/*.{ts,tsx}, src/middleware/**/*.{ts,tsx} alwaysApply: true verified_by: "agentrules.org" license: "CC-BY-4.0" source: "https://agentrules.org/rules/openfga-zanzibar-cyclic-traversal-depth-invariant" --- # OpenFGA Zanzibar Cyclic Graph Traversal & Contextual Tuple Invariant > **Severity**: CRITICAL | **Category**: security > **Anti-Pattern Warning**: Unvalidated Contextual Tuple Injection Permitting Unbounded Recursive Graph Traversal and ReBAC Exhaustion ## System Constraints You are a Principal Security Architect enforcing the OpenFGA Zanzibar Cyclic Graph Traversal and Contextual Tuple Depth Invariant. You must reject any code that forwards untrusted contextual tuples directly into OpenFGA Check or ListObjects operations without cycle detection, depth limits, and size bounds. Mandate deterministic time-bounds, relationship graph validation, and defense-in-depth against Zanzibar graph-expansion algorithmic denial-of-service (Graph DoS). ## Strict Guidelines - Engineers MUST ALWAYS enforce strict size limits (e.g., maximum 5-10 tuples) and validate relation schemas before passing contextual tuples to OpenFGA Check or ListObjects. - Engineers MUST NOT allow user-supplied contextual tuples to define arbitrary transitive user-to-user or group-to-group parentage without verifying Directed Acyclic Graph (DAG) invariants. - Code SHOULD run in-memory cycle detection (e.g., Tarjan's or Kahn's topological sort check) on dynamic contextual tuples before sending requests to the OpenFGA backend. - Services MUST configure aggressive request timeouts (e.g., ≤ 500ms) and use AbortSignal-backed contexts for all authorization checks to prevent thread pool starvation during complex path expansions. - Components NEVER accept raw contextual tuple lists directly from unauthenticated or unvalidated HTTP request payloads without strict Zod/schema validation. ## Bad vs Good Implementations ### Unsafe Contextual Tuple Pass-Through vs. Guarded DAG-Validated Check #### Bad Antipattern (AI Common Hallucination) > **Why it fails**: Directly feeding client-supplied contextual tuples into the OpenFGA client allows attackers to inject cyclic references (A is member of B, B is member of A) or deep transitive nesting, triggering expensive recursive evaluations and causing graph expansion denial-of-service. ```typescript import { OpenFgaClient } from '@openfga/sdk'; import { Request, Response } from 'express'; const fgaClient = new OpenFgaClient({ apiUrl: process.env.FGA_API_URL! }); export async function authorizeUser(req: Request, res: Response) { // VULNERABILITY: Raw user-provided contextual tuples passed directly to OpenFGA. // An attacker can pass circular or deeply nested groups to cause graph explosion/DoS. const { user, relation, object, contextualTuples } = req.body; const { allowed } = await fgaClient.check({ user, relation, object, contextualTuples: contextualTuples ?? [] }); return res.json({ allowed }); } ``` #### Production Standard (Correct) > **Standard**: Implements strict tuple schema bounds (maximum 5 tuples, bounded regexes), an in-memory topological cycle detector to enforce DAG invariants, and an explicit AbortSignal timeout to neutralize algorithmic DoS vulnerabilities before hitting the authorization engine. ```typescript import { OpenFgaClient, ClientTupleKey } from '@openfga/sdk'; import { Request, Response } from 'express'; import { z } from 'zod'; const MAX_CONTEXTUAL_TUPLES = 5; const EVALUATION_TIMEOUT_MS = 400; const ContextualTupleSchema = z.object({ user: z.string().regex(/^[a-zA-Z0-9_-]+:[a-zA-Z0-9_-]+$/), relation: z.enum(['viewer', 'editor', 'member']), object: z.string().regex(/^[a-zA-Z0-9_-]+:[a-zA-Z0-9_-]+$/) }).strict(); const RequestSchema = z.object({ user: z.string().regex(/^[a-zA-Z0-9_-]+:[a-zA-Z0-9_-]+$/), relation: z.string(), object: z.string().regex(/^[a-zA-Z0-9_-]+:[a-zA-Z0-9_-]+$/), contextualTuples: z.array(ContextualTupleSchema).max(MAX_CONTEXTUAL_TUPLES).default([]) }); function assertNoCycles(tuples: ClientTupleKey[]): void { const adj = new Map<string, string[]>(); for (const { user, object } of tuples) { if (user === object) throw new Error('Self-referential tuple cycle detected'); const neighbors = adj.get(user) || []; neighbors.push(object); adj.set(user, neighbors); } const visited = new Set<string>(); const recStack = new Set<string>(); function hasCycle(node: string): boolean { visited.add(node); recStack.add(node); for (const neighbor of adj.get(node) || []) { if (!visited.has(neighbor) && hasCycle(neighbor)) return true; if (recStack.has(neighbor)) return true; } recStack.delete(node); return false; } for (const node of adj.keys()) { if (!visited.has(node) && hasCycle(node)) { throw new Error('Cyclic dependency in contextual authorization tuples'); } } } export async function authorizeUser(req: Request, res: Response) { const parsed = RequestSchema.safeParse(req.body); if (!parsed.success) { return res.status(400).json({ error: 'Invalid authorization input', details: parsed.error.issues }); } const { user, relation, object, contextualTuples } = parsed.data; try { assertNoCycles(contextualTuples); } catch (err: any) { return res.status(400).json({ error: 'Contextual tuple cycle invariant violated' }); } const controller = new AbortController(); const timer = setTimeout(() => controller.abort(), EVALUATION_TIMEOUT_MS); try { const fgaClient = new OpenFgaClient({ apiUrl: process.env.FGA_API_URL! }); const { allowed } = await fgaClient.check( { user, relation, object, contextualTuples }, { signal: controller.signal } ); return res.json({ allowed: Boolean(allowed) }); } catch (error: any) { if (error.name === 'AbortError') { return res.status(504).json({ error: 'Authorization check timed out' }); } return res.status(500).json({ error: 'Authorization evaluation error' }); } finally { clearTimeout(timer); } } ```

Architectural Specification & Invariant Rationale

Architectural Invariant Design: OpenFGA Zanzibar Cyclic Graph Traversal & Contextual Tuple Invariant

OpenFGA Zanzibar Cyclic Graph Traversal & Contextual Tuple Invariant defines an industrial-grade behavioral standard for security engineering. Enforces strict bounds, cycle detection, and contextual tuple sanitization for OpenFGA relationship-based access control (ReBAC) evaluations. Prevents algorithmic denial-of-service (Graph DoS) and unbounded recursive expansion attacks triggered by deep or circular relationship 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: Unvalidated Contextual Tuple Injection Permitting Unbounded Recursive Graph Traversal and ReBAC Exhaustion 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	Unvalidated Contextual Tuple Injection Permitting Unbounded Recursive Graph Traversal and ReBAC Exhaustion	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 strict size limits (e.g., maximum 5-10 tuples) and validate relation schemas before passing contextual tuples to OpenFGA Check or ListObjects.

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.