formula-fuzz.test.ts

formula-fuzz.test.tstests/security/formula-fuzz.test.tsraw ← security11,366 B← Back to the app
1/**
2 * TASK-0134 — formula-engine fuzz (ASVS L2, injection / resource-exhaustion).
3 *
4 * 10,000 random expressions over the engine's OWN grammar (nesting depth
5 * 1–40 — deliberately above the parser's MAX_NESTING of 16 to exercise its
6 * depth guard — random property names incl. nonexistent, random function
7 * trees over the Phase-6 closed function set, a node budget of 2000 so no
8 * generated string can exhaust memory before the engine sees it).
9 *
10 * Generator design (recorded): a deterministic, SEEDED grammar generator
11 * (xorshift32) driven by `fc.property` seed tuples — NOT a fast-check
12 * recursive arbitrary tree. A recursive arbitrary at depth 40 is
13 * exponential in structure size (branching ≈ arity per level) and OOMed the
14 * module at collection; the PRNG builder is linear in node count and fully
15 * reproducible given the seed. `fc.assert` still drives 10k runs, shrinking,
16 * and the seed knob (`SEC_FUZZ_SEED=random`, nightly).
17 *
18 * Assertions (spec):
19 *   - **no crash**: every parse/eval either succeeds or throws FormulaError
20 *     (only FormulaError may escape — an uncaught TypeError/RangeError is a
21 *     crash and fails the suite);
22 *   - **no unbounded time / memory**: the whole 10k run stays far under the
23 *     test timeout (a hang would blow it); each eval is inside the engine's
24 *     own 100k-op / 50 ms budgets by construction (node budget 2000);
25 *   - **worst-case family**: a deliberately oversized expression (100.5k-node
26 *     `and(true, …)`) MUST hit the op limit with `FORMULA_TIMEOUT` — the
27 *     guard is asserted by error type, not "didn't crash".
28 */
29import { describe, expect, it } from "vitest";
30import fc from "fast-check";
31import {
32  parseFormula,
33  evaluateFormula,
34  FormulaError,
35  EVAL_OP_LIMIT,
36  EVAL_TIMEOUT_MS
37} from "@factory/database-engine/formula";
38import type { FormulaContext } from "@factory/database-engine/formula";
39 
40// ---------------------------------------------------------------------------
41// Seed: fixed for CI (10k reproducible runs); random in nightly.
42// ---------------------------------------------------------------------------
43const BASE_SEED = process.env.SEC_FUZZ_SEED === "random" ? (Date.now() & 0xffff) : 0x134_f00d;
44 
45// ---------------------------------------------------------------------------
46// The Phase-6 closed function table — the generator draws from the SAME set
47// the engine resolves against (packages/database-engine/src/formula/
48// functions.ts). Arity is fixed per name.
49// ---------------------------------------------------------------------------
50const FUNC_ARITY: Record<string, number> = {
51  if: 3, and: 3, or: 3, not: 1, sum: 1, average: 1, min: 1, max: 1,
52  dateAdd: 3, dateBetween: 2, now: 0, concat: 3, replace: 3, contains: 2,
53  length: 1, prop: 1
54};
55const FUNC_NAMES = Object.keys(FUNC_ARITY);
56 
57const KNOWN_PROPS: Record<string, unknown> = {
58  Amount: 42, Price: 19.99, Status: "Done", Title: "Hello", Note: "a string",
59  DueDate: "2025-06-15", Started: "2025-06-01", Active: true, Tags: ["a", "b"]
60};
61const KNOWN_TYPES: Record<string, string> = {
62  Amount: "number", Price: "number", Status: "text", Title: "title",
63  Note: "text", DueDate: "date", Started: "date", Active: "checkbox", Tags: "multi_select"
64};
65const PROP_NAMES = Object.keys(KNOWN_PROPS);
66const UNKNOWN_PROPS = ["Statu", "Quantiti", "Duedate", "Isdone", "Xyz", "amount2"];
67 
68const OPS = ["+", "-", "*", "/", "==", "!=", "<", "<=", ">", ">=", "and", "or"] as const;
69const STR_LITS = ['"a"', '"b"', '"Done"', '"x"', '"Open"'] as const;
70const DATE_LITS = ['"2025-06-01"', '"2025-07-01"', '"2025-06-15"', "now()"] as const;
71const PROP_ALPHA = "abcdefghijklmnopqrstuvwxyz0123456789";
72 
73// ---------------------------------------------------------------------------
74// Deterministic seeded generator. xorshift32 (seed must be nonzero).
75// ---------------------------------------------------------------------------
76function makeRng(seed: number): () => number {
77  let s = (seed >>> 0) || 0x9e3779b9;
78  return () => {
79    s ^= s << 13; s >>>= 0;
80    s ^= s >> 17;
81    s ^= s << 5; s >>>= 0;
82    return s / 0x100000000;
83  };
84}
85function pick<T>(rng: () => number, arr: readonly T[]): T {
86  return arr[Math.floor(rng() * arr.length)]!;
87}
88 
89/** A safe property-name string (alphanumeric only — never breaks a literal). */
90function propName(rng: () => number): string {
91  const r = rng();
92  if (r < 0.5) return pick(rng, PROP_NAMES);
93  if (r < 0.8) return pick(rng, UNKNOWN_PROPS);
94  const n = 1 + Math.floor(rng() * 8);
95  let out = "";
96  for (let i = 0; i < n; i++) out += PROP_ALPHA[Math.floor(rng() * PROP_ALPHA.length)]!;
97  return out;
98}
99 
100function leaf(rng: () => number): string {
101  const r = rng();
102  if (r < 0.3) return String(Math.floor(rng() * 2001) - 1000);
103  if (r < 0.42) return rng() < 0.5 ? "true" : "false";
104  if (r < 0.5) return "null";
105  if (r < 0.64) return pick(rng, STR_LITS);
106  if (r < 0.76) return pick(rng, DATE_LITS);
107  return `prop("${propName(rng)}")`;
108}
109 
110/**
111 * Recursive grammar build. `depth` is a hard cap (top level draws 1–40);
112 * `budget` is a node-count cap (2000) so no generated string can exhaust
113 * memory before the engine parses it — the budget path is covered by the
114 * dedicated worst-case family tests, not by the fuzzer's own strings.
115 */
116function genExpr(rng: () => number, depth: number, budget: { left: number }): string {
117  budget.left--;
118  if (depth <= 1 || budget.left <= 0) return leaf(rng);
119  const r = rng();
120  if (r < 0.45) return leaf(rng);
121  if (r < 0.8) {
122    const l = genExpr(rng, depth - 1, budget);
123    const op = pick(rng, OPS);
124    const rr = genExpr(rng, depth - 1, budget);
125    return `(${l} ${op} ${rr})`;
126  }
127  const name = pick(rng, FUNC_NAMES);
128  const arity = FUNC_ARITY[name]!;
129  if (arity === 0) return `${name}()`;
130  const args: string[] = [];
131  for (let i = 0; i < arity; i++) {
132    args.push(name === "prop" ? `prop("${propName(rng)}")` : genExpr(rng, depth - 1, budget));
133  }
134  return `${name}(${args.join(", ")})`;
135}
136 
137function ctxFor(): FormulaContext {
138  return {
139    now: Date.parse("2025-06-15T12:00:00Z"),
140    properties: { ...KNOWN_PROPS },
141    propertyTypes: { ...KNOWN_TYPES }
142  };
143}
144 
145const ALLOWED_CODES = new Set(["PARSE", "TYPE", "RUNTIME", "UNKNOWN_FUNCTION", "FORMULA_TIMEOUT"]);
146 
147function assertFormulaError(e: unknown, where: string, src: string): void {
148  if (!(e instanceof FormulaError)) {
149    throw new Error(
150      `[formula-fuzz] ${where} threw a non-FormulaError (a crash — the engine must not leak ` +
151        `TypeError/RangeError): ${e instanceof Error ? e.name + ": " + e.message : String(e)} | src=${src}`
152    );
153  }
154  if (!ALLOWED_CODES.has(e.code)) {
155    throw new Error(`[formula-fuzz] unexpected FormulaError code "${e.code}" | src=${src}`);
156  }
157}
158 
159describe("TASK-0134 formula fuzz (10k expressions, no crash / no hang)", () => {
160  it("10,000 random expressions: only FormulaError may escape, always bounded", () => {
161    const t0 = Date.now();
162    let ok = 0;
163    let typedErrors = 0;
164    let timeouts = 0;
165    let parseErrors = 0;
166    let maxMs = 0;
167 
168    fc.assert(
169      fc.property(
170        fc.tuple(fc.nat(), fc.nat(), fc.nat()),
171        ([a, b, c]) => {
172          const rng = makeRng(((a ^ Math.imul(b, 0x9e3779b9) ^ Math.imul(c, 0x85ebca6b)) >>> 0) | BASE_SEED);
173          const depth = 1 + (a % 40);
174          const src = genExpr(rng, depth, { left: 2000 });
175          const perEvalT0 = Date.now();
176          let ast: unknown;
177          try {
178            ast = parseFormula(src);
179          } catch (e) {
180            assertFormulaError(e, "parse", src);
181            if (e instanceof FormulaError && e.code === "PARSE") parseErrors++;
182            typedErrors++;
183            maxMs = Math.max(maxMs, Date.now() - perEvalT0);
184            return;
185          }
186          try {
187            const r = evaluateFormula(ast as never, ctxFor());
188            expect(typeof r.steps).toBe("number");
189            ok++;
190          } catch (e) {
191            assertFormulaError(e, "eval", src);
192            typedErrors++;
193            if (e instanceof FormulaError && e.code === "FORMULA_TIMEOUT") timeouts++;
194          }
195          maxMs = Math.max(maxMs, Date.now() - perEvalT0);
196        }
197      ),
198      { numRuns: 10_000, seed: BASE_SEED, timeout: 120_000 }
199    );
200 
201    const totalMs = Date.now() - t0;
202    // The whole run must stay far under the 2-min test timeout (a hang blows
203    // it). ~1–2 s typical for 10k bounded evals.
204    expect(totalMs).toBeLessThan(120_000);
205    // The generator must actually exercise the error paths — including the
206    // parser's depth guard (depths 17–40 → PARSE), so parseErrors > 0 is a
207    // liveness check that the depth knob is being used.
208    expect(ok + typedErrors).toBe(10_000);
209    expect(typedErrors).toBeGreaterThan(0);
210    expect(parseErrors).toBeGreaterThan(0);
211    console.log(
212      `[formula-fuzz] baseSeed=${BASE_SEED} ok=${ok} typedErrors=${typedErrors} (parse=${parseErrors}, timeouts=${timeouts}) maxEvalMs=${maxMs} totalMs=${totalMs}`
213    );
214  });
215 
216  it("worst-case family: oversized expression hits FORMULA_TIMEOUT (op limit), never hangs", () => {
217    // The documented worst case: a wide `and(true, …)` whose node count
218    // exceeds EVAL_OP_LIMIT. The guard must reject it as a typed
219    // FORMULA_TIMEOUT, not hang or throw an uncaught error. A FROZEN clock
220    // isolates the op budget from the wall-clock budget.
221    const N = EVAL_OP_LIMIT + 500;
222    let src = "and(";
223    for (let i = 0; i < N; i++) src += "true, ";
224    src = src.slice(0, -2) + ")";
225 
226    const t0 = Date.now();
227    let caught: unknown;
228    try {
229      evaluateFormula(parseFormula(src) as never, ctxFor(), { now: () => 0 });
230    } catch (e) {
231      caught = e;
232    }
233    const elapsed = Date.now() - t0;
234    expect(caught).toBeInstanceOf(FormulaError);
235    expect((caught as FormulaError).code).toBe("FORMULA_TIMEOUT");
236    expect((caught as FormulaError).message).toMatch(/op limit/i);
237    expect(elapsed).toBeLessThan(2_000); // never hangs
238 
239    // The wall-clock budget is the OTHER guard (cheap-but-slow): assert the
240    // engine enforces the documented constants.
241    expect(EVAL_TIMEOUT_MS).toBe(50);
242    expect(EVAL_OP_LIMIT).toBe(100_000);
243  });
244 
245  it("wide concat family (many prop refs) is bounded by the output/op guard", () => {
246    // The spec's named pathological family: a wide `concat(prop(…), …)` chain
247    // that builds a large output. Depth is capped by the parser (16), so the
248    // realistic worst case is a WIDE concat — the 1MB output guard (RUNTIME)
249    // or the op limit (FORMULA_TIMEOUT) must fire, never an unbounded string
250    // build. 200k args → ~200k node visits → op limit.
251    const parts: string[] = [];
252    for (let i = 0; i < 200_000; i++) parts.push(`prop("Note")`);
253    const src = `concat(${parts.join(", ")})`;
254    const t0 = Date.now();
255    let caught: unknown;
256    let value: unknown;
257    try {
258      const r = evaluateFormula(parseFormula(src) as never, ctxFor(), { now: () => 0 });
259      value = r.value.v;
260    } catch (e) {
261      caught = e;
262    }
263    const elapsed = Date.now() - t0;
264    if (caught !== undefined) {
265      expect(caught).toBeInstanceOf(FormulaError);
266      expect(ALLOWED_CODES.has((caught as FormulaError).code)).toBe(true);
267    } else {
268      expect(typeof value).toBe("string");
269    }
270    expect(elapsed).toBeLessThan(2_000);
271  });
272});
273