OpenFGA Zanzibar-Style Cycle Detection & Bounded Depth Evaluation Standard

--- description: OpenFGA Zanzibar-Style Cycle Detection & Bounded Depth Evaluation Standard - Enforces deterministic cycle detection, breadth/depth-budget constraints, and visited-node memoization during ReBAC relationship-tuple evaluation. Prevents Denial-of-Service, thread starvation, and call-stack exhaustion caused by circular group memberships, nested folder hierarchies, and unbounded userset graph expansions. globs: src/auth/**/*.ts, src/authorization/**/*.ts, src/services/fga/**/*.ts, src/security/rebac/**/*.ts alwaysApply: true verified_by: "agentrules.org" license: "CC-BY-4.0" source: "https://agentrules.org/rules/openfga-rebac-cycle-detection-bounded-depth" --- # OpenFGA Zanzibar-Style Cycle Detection & Bounded Depth Evaluation Standard > **Severity**: CRITICAL | **Category**: backend > **Anti-Pattern Warning**: Unbounded Recursive Traversal and Missing Visited-State Tracking in Graph Authorization Queries ## System Constraints You are a Principal Engineer enforcing the OpenFGA Zanzibar-Style Cycle Detection & Bounded Depth Evaluation Standard. Mandate that all ReBAC and graph-based authorization algorithms implement hard depth budgets, branch-level path tracking to detect cycles, and safe short-circuiting semantics. Prevent any unbounded recursion or unmemoized sub-problem expansion. ## Strict Guidelines - Engineers MUST ALWAYS enforce a strictly bounded depth budget (e.g., maximum depth of 25) across all recursive userset and tuple evaluations. - Engineers MUST ALWAYS track traversal history using an immutable or branch-scoped visited set containing composite keys of the form `${targetType}:${targetId}#${relation}`. - Services MUST gracefully short-circuit circular branches with a safe negative result (or dedicated cycle diagnostic) rather than permitting recurring evaluation of previously traversed nodes. - Services MUST throw a typed, operational error (e.g., MaxDepthExceededException) when evaluation depth reaches the configured limit to trip circuit breakers and alert telemetry. - Engineers MUST NOT implement ReBAC graph traversal using bare, unconstrained recursive functions or Promise.all expansions without concurrency throttling and depth propagation. - Code SHOULD leverage sub-problem memoization (resolving identical canonical check requests within a single query context) to optimize multi-hop evaluation lattices. ## Bad vs Good Implementations ### Zanzibar Relationship Traversal with Depth Bounds & Cycle Guardrails #### Bad Antipattern (AI Common Hallucination) > **Why it fails**: The check method lacks both recursion depth limits and visited-node cycle detection. If group A belongs to group B and group B belongs to group A, an authorization check triggers infinite recursive calls, saturating CPU cycles and eventually crashing the Node.js process with a RangeError: Maximum call stack size exceeded. ```typescript import { TupleStore } from './tuple-store'; interface CheckRequest { user: string; relation: string; object: string; } export class NaiveRebacResolver { constructor(private store: TupleStore) {} // VULNERABLE: Infinite recursion on circular memberships (e.g., group:A in group:B, group:B in group:A) // Causes call stack exhaustion, unhandled promise rejections, and server thread lock. async check(req: CheckRequest): Promise<boolean> { const directTuples = await this.store.find({ object: req.object, relation: req.relation, }); for (const tuple of directTuples) { if (tuple.user === req.user) { return true; } // Blindly recurse on usersets without cycle detection or depth tracking if (tuple.user.includes('#')) { const [nestedObject, nestedRelation] = tuple.user.split('#'); const hasAccess = await this.check({ user: req.user, relation: nestedRelation, object: nestedObject, }); if (hasAccess) return true; } } return false; } } ``` #### Production Standard (Correct) > **Standard**: The refactored implementation uses an immutable path-tracking context (`visitedPath`) to identify cyclic references at zero runtime risk, terminating cyclical evaluations immediately. It also introduces a hard maximum depth boundary (`maxDepth: 25`) with a typed `MaxDepthExceededError`, preventing resource exhaustion and unbounded traversal attacks. ```typescript import { TupleStore, Tuple } from './tuple-store'; export class MaxDepthExceededError extends Error { constructor(depth: number, target: string) { super(`Evaluation exceeded max depth of ${depth} while resolving ${target}`); this.name = 'MaxDepthExceededError'; } } interface CheckRequest { user: string; relation: string; object: string; } interface EvaluationContext { currentDepth: number; maxDepth: number; visitedPath: ReadonlySet<string>; } export class ResilientRebacResolver { private static readonly DEFAULT_MAX_DEPTH = 25; constructor(private readonly store: TupleStore) {} async check(req: CheckRequest): Promise<boolean> { return this.evaluate(req, { currentDepth: 0, maxDepth: ResilientRebacResolver.DEFAULT_MAX_DEPTH, visitedPath: new Set<string>(), }); } private async evaluate(req: CheckRequest, ctx: EvaluationContext): Promise<boolean> { if (ctx.currentDepth > ctx.maxDepth) { throw new MaxDepthExceededError(ctx.maxDepth, `${req.object}#${req.relation}`); } const nodeKey = `${req.object}#${req.relation}`; // Cycle Detection: If already visited in the current resolution chain, abort this branch if (ctx.visitedPath.has(nodeKey)) { return false; } const branchVisited = new Set(ctx.visitedPath).add(nodeKey); const tuples = await this.store.find({ object: req.object, relation: req.relation }); for (const tuple of tuples) { if (tuple.user === req.user) { return true; } // Computed userset resolution (e.g., user is 'group:eng#member') if (tuple.user.includes('#')) { const [nestedObject, nestedRelation] = tuple.user.split('#'); const granted = await this.evaluate( { user: req.user, relation: nestedRelation, object: nestedObject, }, { currentDepth: ctx.currentDepth + 1, maxDepth: ctx.maxDepth, visitedPath: branchVisited, } ); if (granted) return true; } } return false; } } ```

Architectural Specification & Invariant Rationale

Architectural Invariant Design: OpenFGA Zanzibar-Style Cycle Detection & Bounded Depth Evaluation Standard

OpenFGA Zanzibar-Style Cycle Detection & Bounded Depth Evaluation Standard defines an industrial-grade behavioral standard for backend engineering. Enforces deterministic cycle detection, breadth/depth-budget constraints, and visited-node memoization during ReBAC relationship-tuple evaluation. Prevents Denial-of-Service, thread starvation, and call-stack exhaustion caused by circular group memberships, nested folder hierarchies, and unbounded userset graph expansions. 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 and Missing Visited-State Tracking in Graph Authorization Queries 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 and Missing Visited-State Tracking in Graph Authorization Queries	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 budget (e.g., maximum depth of 25) across all recursive userset and tuple evaluations.

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.