Cycle-Safe Graph Evaluation and Traversal Guardrails for OpenFGA and Zanzibar ReBAC

--- description: Cycle-Safe Graph Evaluation and Traversal Guardrails for OpenFGA and Zanzibar ReBAC - Enforces deterministic cycle detection, bounded traversal depth, and evaluation memoization across dynamic multi-tenant relationship-based access control (ReBAC) graphs. Prevents denial-of-service and stack overflow vulnerabilities caused by circular delegation chains, mutually recursive group memberships, or unbounded transitive closures in tuple evaluation engines. globs: src/**/authz/**/*.{ts,js,go,py}, src/**/permissions/**/*.{ts,js,go,py}, src/**/fga/**/*.{ts,js,go,py} alwaysApply: true verified_by: "agentrules.org" license: "CC-BY-4.0" source: "https://agentrules.org/rules/openfga-zanzibar-cycle-safe-tuple-graph-evaluation-standard" --- # Cycle-Safe Graph Evaluation and Traversal Guardrails for OpenFGA and Zanzibar ReBAC > **Severity**: CRITICAL | **Category**: backend > **Anti-Pattern Warning**: Unbounded Recursive Traversal and Cycle-Prone Graph Resolution in ReBAC Engine ## System Constraints You are a Principal Security and Distributed Systems Architect enforcing the OpenFGA Zanzibar Cycle-Safe Tuple Graph Evaluation Standard. You must mandate cycle-breaking path tracking, strict max-depth budgets, and memoized sub-graph resolution across all relationship-based authorization evaluations to completely eliminate DoS and stack exhaustion risks. ## Strict Guidelines - Engineers MUST ALWAYS pass a traversal context containing a visited evaluation path (`Set<string>` composed of `tenant:object#relation@subject`) down every recursive branch. - Engineers MUST immediately abort evaluation and return `false` (or cycle error) when encountering an already visited graph node in the current traversal path. - Engineers MUST NOT rely on unbounded recursion or implicit database cascade logic when evaluating nested relations or transitive closures (e.g., `member from parent_group`). - Services MUST enforce a hard-coded maximum depth threshold (e.g., `MAX_REBAC_DEPTH = 15`) and fail closed with a deterministic `AuthorizationDepthExceededError`. - Code SHOULD leverage concurrency-safe singleflight resolution or query-level sub-tree memoization to avoid redundant database reads for shared ancestors. - Authorization models MUST NOT define direct or indirect reflexive relations without cycle-safe canonical normalization. ## Bad vs Good Implementations ### Cycle Detection and Max-Depth Guardrail in ReBAC Tuple Traversal #### Bad Antipattern (AI Common Hallucination) > **Why it fails**: The check recursively traverses parent objects without maintaining a visited set or enforcing a maximum depth ceiling. Circular relationships (e.g., group A member of group B, and group B member of group A) cause unbounded recursion, leading to call-stack exhaustion, OpenFGA connection pool starvation, and application DoS. ```typescript import { OpenFgaClient } from '@openfga/sdk'; interface CheckContext { tenantId: string; user: string; relation: string; object: string; } export class NaiveRebacAuthorizer { constructor(private readonly fga: OpenFgaClient) {} // VULNERABLE: Infinite recursion on circular group memberships // (e.g., group:A -> group:B -> group:A) causing process crash or DoS. async checkUserAccess(ctx: CheckContext): Promise<boolean> { const response = await this.fga.check({ user: ctx.user, relation: ctx.relation, object: ctx.object, }); if (response.allowed) { return true; } // Naive manual traversal of parent relations without cycle or depth tracking const parents = await this.findParentContainers(ctx.tenantId, ctx.object); for (const parent of parents) { const allowed = await this.checkUserAccess({ tenantId: ctx.tenantId, user: ctx.user, relation: ctx.relation, object: parent, }); if (allowed) return true; } return false; } private async findParentContainers(tenantId: string, object: string): Promise<string[]> { return []; } } ``` #### Production Standard (Correct) > **Standard**: The implementation tracks evaluation paths with a canonical string key (`tenant:object#relation@user`) using an immutable-style accumulated `Set`. It enforces an explicit `MAX_EVALUATION_DEPTH` to abort runaway traversals and fails closed if a loop or cycle is detected. ```typescript import { OpenFgaClient } from '@openfga/sdk'; interface CheckContext { tenantId: string; user: string; relation: string; object: string; } export class DepthExceededError extends Error { constructor(depth: number) { super(`ReBAC graph evaluation exceeded max depth budget of ${depth}`); this.name = 'DepthExceededError'; } } export class CycleSafeRebacAuthorizer { private static readonly MAX_EVALUATION_DEPTH = 15; constructor(private readonly fga: OpenFgaClient) {} async checkUserAccess( ctx: CheckContext, visitedPath: ReadonlySet<string> = new Set<string>(), currentDepth: number = 0 ): Promise<boolean> { if (currentDepth > CycleSafeRebacAuthorizer.MAX_EVALUATION_DEPTH) { throw new DepthExceededError(CycleSafeRebacAuthorizer.MAX_EVALUATION_DEPTH); } const canonicalKey = `${ctx.tenantId}:${ctx.object}#${ctx.relation}@${ctx.user}`; // Deterministic cycle detection: fail-closed if cycle detected if (visitedPath.has(canonicalKey)) { return false; } const nextVisited = new Set(visitedPath); nextVisited.add(canonicalKey); const { allowed } = await this.fga.check({ user: ctx.user, relation: ctx.relation, object: ctx.object, }); if (allowed) { return true; } const parents = await this.findParentContainers(ctx.tenantId, ctx.object); for (const parent of parents) { const isAllowed = await this.checkUserAccess( { tenantId: ctx.tenantId, user: ctx.user, relation: ctx.relation, object: parent, }, nextVisited, currentDepth + 1 ); if (isAllowed) return true; } return false; } private async findParentContainers(tenantId: string, object: string): Promise<string[]> { return []; } } ```

Architectural Specification & Invariant Rationale

Architectural Invariant Design: Cycle-Safe Graph Evaluation and Traversal Guardrails for OpenFGA and Zanzibar ReBAC

Cycle-Safe Graph Evaluation and Traversal Guardrails for OpenFGA and Zanzibar ReBAC defines an industrial-grade behavioral standard for backend engineering. Enforces deterministic cycle detection, bounded traversal depth, and evaluation memoization across dynamic multi-tenant relationship-based access control (ReBAC) graphs. Prevents denial-of-service and stack overflow vulnerabilities caused by circular delegation chains, mutually recursive group memberships, or unbounded transitive closures in tuple evaluation engines. 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 Cycle-Prone Graph Resolution in ReBAC Engine 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 Cycle-Prone Graph Resolution in ReBAC Engine	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 a traversal context containing a visited evaluation path (`Set<string>` composed of `tenant

Engineers MUST ALWAYS pass a traversal context containing a visited evaluation path (`Set<string>` composed of `tenant:object#relation@subject`) down every recursive branch.

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.