permission-fuzz.test.ts

permission-fuzz.test.tstests/security/permission-fuzz.test.tsraw ← security15,908 B← Back to the app
1/**
2 * TASK-0134 — permission-engine differential fuzz (ASVS L2, authorization).
3 *
4 * fast-check random worlds (1–8 users, 1–10 resources with parent pages,
5 * Permission + Share rows) are fed to BOTH the engine
6 * (`resolvePermission`) and the independent brute-force oracle
7 * (`oracle.ts`, written from the documented contract, not the code). The
8 * engine must agree with the oracle on the final level for **10,000 random
9 * cases in CI** — a subtle engine bug (off-by-one ancestor walk, wrong max,
10 * share-visibility slip, explicit/inherit precedence mix-up) surfaces as an
11 * oracle mismatch and fails the build.
12 *
13 * Also asserted per case: the level is a valid LEVELS member, and the
14 * `can()` / `check()` wrappers are consistent with the resolved level.
15 *
16 * Seed: fixed (CI reproducibility). `SEC_FUZZ_SEED=random` (nightly CI)
17 * re-seeds fast-check.
18 *
19 * Recorded engine semantics the oracle mirrors (see audit-report.md,
20 * findings): a grant with `level: "none"` on an ANCESTOR is still an
21 * *applicable* grant for the nearest-ancestor rule — it blocks inheritance
22 * from farther ancestors and contributes no level (an explicit "no access"
23 * at that scope). A none-level grant on the EXACT resource is never
24 * "explicit" (it cannot override). Both behaviors are engine-intended.
25 */
26import { describe, expect, it } from "vitest";
27import fc from "fast-check";
28import {
29  resolvePermission,
30  can,
31  check,
32  levelRank,
33  LEVELS,
34  ROLES,
35  RESOURCE_TYPES,
36  type PermissionRequest,
37  type Grant,
38  type Share,
39  type AncestorRef,
40  type PermissionLevel,
41  type WorkspaceRole,
42  type ResourceType
43} from "@factory/permissions";
44import { oracleLevel, isLevel } from "./oracle.js";
45 
46const SEED_VALUE = (process.env.SEC_FUZZ_SEED === "random" ? (Date.now() & 0xffff) : 0) | 0x150_0aa;
47 
48// ---------------------------------------------------------------------------
49// World model
50// ---------------------------------------------------------------------------
51interface WorldUser {
52  id: string;
53  role: WorkspaceRole;
54  teams: string[];
55}
56interface WorldNode {
57  id: string;
58  type: ResourceType;
59  parentId: string | null; // null = the workspace root
60}
61interface World {
62  workspaceId: string;
63  teams: string[];
64  users: WorldUser[];
65  nodes: WorldNode[]; // every resource except the workspace root
66  grants: Grant[];
67  shares: Share[];
68}
69 
70const LEVEL_ARBS = LEVELS; // includes "none" — the none-grant semantics are
71// in scope (see header).
72const ROLE_ARB = ROLES;
73 
74const idArb = (prefix: string) => fc.stringOf(fc.constantFrom(..."abcdef0123456789".split("")), { minLength: 2, maxLength: 6 }).map((s) => `${prefix}_${s}`);
75 
76/** Node type by tree depth (root=workspace, then cycles the 4 non-root
77 * resource types) — keeps the chain realistic (a record lives in a database
78 * lives in a page lives in a teamspace). */
79const NODE_TYPE_BY_DEPTH: ResourceType[] = ["teamspace", "page", "database", "record"];
80 
81function buildWorld(raw: {
82  teams: string[];
83  users: { id: string; role: WorkspaceRole; teams: string[] }[];
84  nodeIds: string[];
85  parentIdx: number[]; // node i's parent: -1 = workspace root, else index < i
86  grants: Grant[];
87  shares: Share[];
88}): World {
89  const workspaceId = "wsp_root";
90  const nodes: WorldNode[] = raw.nodeIds.map((id, i) => {
91    const parentIdx = raw.parentIdx[i] ?? -1;
92    const parentId = parentIdx === -1 ? null : raw.nodeIds[parentIdx]!;
93    // depth = number of ancestors below the workspace
94    let depth = 0;
95    let p: string | null = parentId;
96    const idToParent = new Map(raw.nodeIds.map((nid, j) => [nid, raw.parentIdx[j] ?? -1]));
97    while (p !== null) {
98      depth++;
99      const pi = idToParent.get(p);
100      p = pi === undefined || pi === -1 ? null : raw.nodeIds[pi]!;
101    }
102    return { id, type: NODE_TYPE_BY_DEPTH[(depth - 1) % 4]!, parentId };
103  });
104  return { workspaceId, teams: raw.teams, users: raw.users, nodes, grants: raw.grants, shares: raw.shares };
105}
106 
107const worldArb: fc.Arbitrary<World> = fc
108  .tuple(
109    // teams (1–4)
110    fc.array(idArb("team"), { minLength: 1, maxLength: 4 }),
111    // users (1–8), each with a role + a subset of teams
112    fc.array(
113      fc.tuple(idArb("user"), fc.constantFrom(...ROLE_ARB), fc.constantFrom(0, 1, 2, 3, 4, 5, 6, 7, 8)),
114      { minLength: 1, maxLength: 8 }
115    ),
116    // nodes (1–10): ids + a parent index strictly less than their own
117    // (guarantees a forest, no cycles) — the workspace root is implicit.
118    fc.integer({ min: 1, max: 10 }).chain((n) =>
119      fc.tuple(
120        fc.array(idArb("res"), { minLength: n, maxLength: n }),
121        fc.array(fc.nat(), { minLength: n, maxLength: n })
122      )
123    ),
124    // grants (0–15)
125    fc.integer({ min: 0, max: 15 }),
126    // shares (0–6)
127    fc.integer({ min: 0, max: 6 })
128  )
129  .chain(([teams, usersRaw, nodesTuple, grantCount, shareCount]) => {
130    const [nodeIds, parentIdxRaw] = nodesTuple;
131    const parentIdx = parentIdxRaw.map((v, i) => (i === 0 ? -1 : (v % i)!));
132    const users: WorldUser[] = usersRaw.map(([id, role, teamMask]) => ({
133      id,
134      role,
135      teams: teams.filter((_, ti) => (teamMask >> ti) & 1)
136    }));
137    return fc
138      .tuple(
139        fc.array(
140          fc.tuple(
141            fc.constantFrom("user" as const, "team" as const, "role" as const),
142            fc.nat(1000), // grantee selector (user idx / team idx / role idx)
143            fc.nat(1000), // resource selector
144            fc.constantFrom(...LEVEL_ARBS)
145          ),
146          { minLength: grantCount, maxLength: grantCount }
147        ),
148        fc.array(
149          fc.tuple(
150            fc.constantFrom("private" as const, "workspace" as const, "team" as const, "users" as const, "public" as const),
151            fc.constantFrom(...LEVEL_ARBS),
152            fc.nat(1000), // team / user selector
153            fc.nat(1000)
154          ),
155          { minLength: shareCount, maxLength: shareCount }
156        )
157      )
158      .map(([grantTuples, shareTuples]) => {
159        const grants: Grant[] = grantTuples.map(([gt, gs, rs, level]) => {
160          let granteeId: string;
161          if (gt === "user") granteeId = gs % 2 === 0 && users.length > 0 ? users[gs % users.length]!.id : `u_foreign_${gs}`;
162          else if (gt === "team") granteeId = gs % 2 === 0 ? teams[gs % teams.length]! : `team_foreign_${gs}`;
163          else granteeId = ROLE_ARB[gs % 4]!;
164          const node = nodeIds[rs % nodeIds.length]!;
165          return {
166            granteeType: gt,
167            granteeId,
168            resourceType: (buildType(nodeIds, parentIdx, node) as ResourceType),
169            resourceId: node,
170            level
171          };
172        });
173        const shares: Share[] = shareTuples.map(([scope, level, s1, s2]) => {
174          const share: Share = { scope, level };
175          if (scope === "team") {
176            // ~half the team shares point at a real team; the rest at a
177            // foreign/undefined team (the invisible-team path).
178            share.teamId = s1 % 3 === 0 ? `team_foreign_${s1}` : teams[s1 % teams.length]!;
179          } else if (scope === "users") {
180            // a small random subset of users (possibly empty → invisible to
181            // everyone; possibly foreign ids).
182            share.userIds = Array.from({ length: s1 % 3 }, (_, i) =>
183              i % 2 === 0 && users.length > 0 ? users[(s2 + i) % users.length]!.id : `u_list_${s1}_${i}`
184            );
185          }
186          return share;
187        });
188        return buildWorld({ teams, users, nodeIds, parentIdx, grants, shares });
189      });
190  });
191 
192/** The type a node would get under buildWorld's depth rule (needed to set a
193 * grant's resourceType on the random node it targets). */
194function buildType(nodeIds: string[], parentIdx: number[], nodeId: string): string {
195  const idx = nodeIds.indexOf(nodeId);
196  let depth = 0;
197  let p: number = parentIdx[idx] ?? -1;
198  while (p !== -1) {
199    depth++;
200    p = parentIdx[p] ?? -1;
201  }
202  return NODE_TYPE_BY_DEPTH[(depth - 1) % 4]!;
203}
204 
205// ---------------------------------------------------------------------------
206// The 10k differential fuzz
207// ---------------------------------------------------------------------------
208function ancestorChain(world: World, nodeId: string): AncestorRef[] {
209  // root → … → node (the last entry is the resource itself)
210  const path: AncestorRef[] = [];
211  let cur: string | null = nodeId;
212  const byId = new Map(world.nodes.map((n) => [n.id, n]));
213  while (cur !== null) {
214    const node = byId.get(cur);
215    if (!node) break;
216    path.unshift({ resourceType: node.type, id: node.id });
217    cur = node.parentId;
218  }
219  return [{ resourceType: "workspace", id: world.workspaceId }, ...path];
220}
221 
222function requestFor(world: World, user: WorldUser, nodeId: string): PermissionRequest {
223  return {
224    userId: user.id,
225    userName: user.id,
226    userTeams: user.teams,
227    workspaceRole: user.role,
228    workspaceId: world.workspaceId,
229    resourceType: world.nodes.find((n) => n.id === nodeId)!.type,
230    resourceId: nodeId,
231    ancestorChain: ancestorChain(world, nodeId),
232    grants: world.grants,
233    shares: world.shares
234  };
235}
236 
237describe("TASK-0134 permission fuzz (10k random worlds vs brute-force oracle)", () => {
238  it("engine agrees with the oracle on 10,000 random cases", () => {
239    let cases = 0;
240    let mismatches: string[] = [];
241    let withGrants = 0;
242    let withShares = 0;
243 
244    fc.assert(
245      fc.property(worldArb, (world) => {
246        const user = world.users[0]!; // probe user 0 (every user is probed across runs)
247        // probe a few (user, resource) pairs per world — keeps per-run work
248        // bounded while the 10k run count drives coverage.
249        const probes = 3;
250        for (let k = 0; k < probes; k++) {
251          const u = world.users[k % world.users.length]!;
252          const node = world.nodes[k % world.nodes.length]!;
253          const req = requestFor(world, u, node.id);
254          const engine = resolvePermission(req);
255          const oracle = oracleLevel(req);
256          cases++;
257          if (world.grants.length > 0) withGrants++;
258          if (world.shares.length > 0) withShares++;
259 
260          expect(isLevel(engine.level)).toBe(true);
261          if (engine.level !== oracle) {
262            mismatches.push(
263              `user=${u.id} role=${u.role} teams=[${u.teams}] resource=${node.type}:${node.id} ` +
264                `chain=[${(req.ancestorChain ?? []).map((a) => `${a.resourceType}:${a.id}`).join(" > ")}] ` +
265                `grants=${JSON.stringify(world.grants)} shares=${JSON.stringify(world.shares)} ` +
266                `→ engine=${engine.level} oracle=${oracle} reasons=${JSON.stringify(engine.reasons)}`
267            );
268            expect(engine.level, `ORACLE MISMATCH: ${mismatches.at(-1)}`).toBe(oracle);
269          }
270 
271          // can()/check() consistency with the resolved level.
272          for (const required of ["view", "edit", "full_access"] as const) {
273            const expectCan = levelRank(engine.level) >= levelRank(required);
274            expect(can(req, required), `can() inconsistent for ${required}`).toBe(expectCan);
275            if (expectCan) {
276              expect(() => check(req, required)).not.toThrow();
277            } else {
278              expect(() => check(req, required)).toThrow();
279            }
280          }
281        }
282      }),
283      { numRuns: Math.ceil(10_000 / 3), seed: SEED_VALUE, timeout: 120_000 }
284    );
285 
286    // 10k cases (3 probes × ~3334 worlds), and the world generator actually
287    // exercised the interesting paths (grants + shares present).
288    expect(cases).toBeGreaterThanOrEqual(10_000);
289    expect(mismatches).toHaveLength(0);
290    expect(withGrants).toBeGreaterThan(0);
291    expect(withShares).toBeGreaterThan(0);
292    console.log(`[perm-fuzz] seed=${SEED_VALUE} cases=${cases} withGrants=${withGrants} withShares=${withShares} mismatches=0`);
293  });
294 
295  // The spec's "deliberately broken engine (fixture) is caught": proves the
296  // differential gate is NOT tautological — a WRONG reference disagrees with
297  // the real engine on the random worlds. (The real engine must agree with the
298  // real oracle, so we can't ship a broken engine inside `resolvePermission`;
299  // instead we run the fuzz with a deliberately-wrong oracle. A wrong oracle
300  // and a wrong engine are symmetric — both must produce mismatches or the
301  // fuzz is vacuous.)
302  it("a deliberately broken reference (fixture) is CAUGHT — the oracle is independent, not a tautology", () => {
303    let mismatches = 0;
304    fc.assert(
305      fc.property(worldArb, (world) => {
306        const u = world.users[0]!;
307        const node = world.nodes[0]!;
308        const req = requestFor(world, u, node.id);
309        const engine = resolvePermission(req);
310        // deliberately WRONG reference: "full_access if the user is a member
311        // of the workspace, else none" — ignores grants, shares, inheritance,
312        // and the whole ancestor walk. A real engine must NOT match this on
313        // every world.
314        const brokenOracle: PermissionLevel = u.role === "owner" ? "full_access" : u.role === "member" || u.role === "admin" ? "edit" : "none";
315        if (engine.level !== brokenOracle) mismatches++;
316      }),
317      { numRuns: 2000, seed: SEED_VALUE, timeout: 60_000 }
318    );
319    expect(mismatches, "a deliberately broken reference must DISAGREE with the engine on the random worlds (the fuzz is not vacuous)").toBeGreaterThan(0);
320  });
321 
322  // -----------------------------------------------------------------------
323  // Documented contract invariants the fuzz exercises (pinned by hand —
324  // these are the behaviors the random cases cover statistically).
325  // -----------------------------------------------------------------------
326  it("none-level grant on the EXACT resource is never explicit (no override)", () => {
327    const req: PermissionRequest = {
328      userId: "u1",
329      userTeams: [],
330      workspaceRole: "member",
331      workspaceId: "w1",
332      resourceType: "page",
333      resourceId: "p1",
334      ancestorChain: [
335        { resourceType: "workspace", id: "w1" },
336        { resourceType: "page", id: "p1" }
337      ],
338      grants: [
339        { granteeType: "user", granteeId: "u1", resourceType: "page", resourceId: "p1", level: "none" }
340      ],
341      shares: []
342    };
343    const r = resolvePermission(req);
344    // member on a descendant → view baseline; the none grant is not explicit.
345    expect(r.level).toBe("view");
346    expect(oracleLevel(req)).toBe("view");
347    expect(r.reasons.some((x) => x.includes("explicit grant"))).toBe(false);
348  });
349 
350  it("none-level grant on an ANCESTOR blocks farther inheritance (recorded engine semantics)", () => {
351    const req: PermissionRequest = {
352      userId: "u1",
353      userTeams: [],
354      workspaceRole: "guest", // guest → none on descendants, so only inheritance lifts
355      workspaceId: "w1",
356      resourceType: "page",
357      resourceId: "p1",
358      // nearest ancestor (teamspace) has a none grant (blocks); the farthest
359      // (workspace) has a full_access grant (would lift if not blocked).
360      ancestorChain: [
361        { resourceType: "workspace", id: "w1" },
362        { resourceType: "teamspace", id: "t1" },
363        { resourceType: "page", id: "p1" }
364      ],
365      grants: [
366        { granteeType: "user", granteeId: "u1", resourceType: "teamspace", resourceId: "t1", level: "none" },
367        { granteeType: "user", granteeId: "u1", resourceType: "workspace", resourceId: "w1", level: "full_access" }
368      ],
369      shares: []
370    };
371    const r = resolvePermission(req);
372    expect(r.level).toBe("none");
373    expect(oracleLevel(req)).toBe("none");
374  });
375 
376  it("RESOURCE_TYPES covers the grant resource types the fuzzer targets", () => {
377    // Liveness: the fuzzer's type-by-depth rule only uses these four non-root
378    // types (all in RESOURCE_TYPES).
379    for (const t of NODE_TYPE_BY_DEPTH) {
380      expect((RESOURCE_TYPES as readonly string[]).includes(t)).toBe(true);
381    }
382  });
383});
384