Files
alexm 401084bab3
Test / gate (push) Failing after 19m0s
Initial commit
2026-11-12 22:23:54 -05:00

468 lines
26 KiB
JavaScript

#!/usr/bin/env node
// SPDX-FileCopyrightText: 2026 Scientific Computing Studio, LLC
// SPDX-License-Identifier: Apache-2.0
/**
* Fuzz the prover with programs nobody wrote: "proved" must be a proof (AGENTS.md, rule 5).
*
* Each program is a PROCEDURE P(A, B, L) made at random from the notation's loops, branches, calls and contracts,
* with helpers it may call. The prover is asked about every obligation; then P is run on random arguments with the
* contracts checked. A finding is an obligation the prover marked proved that a run breaks: a run that stops with
* the same kind of failure on the same line (the same column for an ASSERT, the same half of an INVARIANT or a
* DECREASES). Units the prover could not finish (partial) are not counted. A finding is a soundness bug in
* src/engines/pseudo/: write its program into library/pseudo/prover/ with a `// MUST-NOT-PROVE:` header first
* (docs/engines.md#soundness), then fix the rule.
*
* What the programs use (each a "feature" that --without can switch off, to see which one a finding needs):
*
* core INTEGER arithmetic (DIV, MOD, MIN, MAX, ABS), lists (APPEND, REMOVE, indexing, IN), IF, FOR with a
* literal STEP, WHILE, FOR EACH, REPEAT, BREAK and CONTINUE, INVARIANTs on FOR and WHILE, ASSERTs,
* calls with REQUIRE, ENSURE, BYREF and OLD, calls on the right of AND and OR
* foreach an INVARIANT in FOR EACH repeat an INVARIANT in REPEAT
* step a FOR whose STEP is an expression case CASE OF with values, ranges and OTHERWISE
* float FLOAT and FLOAT32 variables, conversions and comparisons
* sized INT8, UINT8 and INT16 variables and their arithmetic (a result out of range stops the run)
* impure FUNCTIONs that draw a random number (RANDINT, RAND) or read INPUT, called more than once
*
* node scripts/prove-fuzz.mjs [--seed N] [--programs N] [--runs N] [--budget-ms N] [--time S]
* [--without f1,f2] [--only-program N] [--keep DIR] [--no-reduce] [--dist DIR] [--json]
*
* --seed the programs come from this seed and the program's number, so a finding is reproduced by
* --seed S --only-program N (default 1)
* --programs how many programs (default 300) --runs runs of each program (default 24)
* --budget-ms the prover's time for each routine, as tests/prover-soundness.test.mjs gives it a budget
* (default 1500); a slower machine may prove less, never more
* --time stop making programs after this many seconds and report what was done (default: no limit)
* --keep DIR write each finding, reduced, as a regression-ready .pseudo file in DIR
* --no-reduce report each finding as generated instead of the smallest program that still shows it
* --dist DIR test another build of core than dist/ (an older one, to see that the fuzzer finds its known bugs)
*
* Exit status: 0 when nothing was found, 1 when a proved obligation was broken, 2 on a usage error or a missing
* build (dist/). The same seed and options give the same programs and the same runs.
*/
import fs from 'node:fs';
import path from 'node:path';
import { fileURLToPath, pathToFileURL } from 'node:url';
const ROOT = fileURLToPath(new URL('..', import.meta.url));
const argv = process.argv.slice(2);
const opt = (name, dflt = null) => { const i = argv.indexOf(`--${name}`); return i >= 0 ? argv[i + 1] : dflt; };
const flag = (name) => argv.includes(`--${name}`);
const DIST = path.resolve(opt('dist', path.join(ROOT, 'dist')));
const dist = (p) => pathToFileURL(path.join(DIST, p)).href;
const num = (name, dflt) => {
const v = opt(name);
if (v === null) return dflt;
const n = Number(v);
if (!Number.isInteger(n) || n < 0) { console.error(`prove-fuzz: --${name} wants a whole number, and got ${v}`); process.exit(2); }
return n;
};
if (!fs.existsSync(path.join(DIST, 'engines', 'pseudo', 'vcgen.js'))) { console.error(`prove-fuzz: no build at ${DIST}; run \`pixi run build\` first`); process.exit(2); }
const { studyOf } = await import(dist('services/pseudo.js'));
const { verify } = await import(dist('engines/pseudo/vcgen.js'));
const { run, evaluateConstant, valueFits } = await import(dist('engines/pseudo/interp.js'));
const { parseExpression } = await import(dist('engines/pseudo/parse.js'));
export const FEATURES = ['core', 'foreach', 'repeat', 'step', 'case', 'float', 'sized', 'impure'];
const SEED = num('seed', 1);
const PROGRAMS = Math.min(num('programs', 300), 100000);
const RUNS = Math.min(num('runs', 24), 1000);
const BUDGET_MS = num('budget-ms', 1500);
const TIME_S = num('time', 0);
const ONLY = opt('only-program') === null ? null : num('only-program', 0);
const KEEP = opt('keep');
const without = new Set((opt('without') || '').split(',').filter(Boolean));
for (const f of without) if (!FEATURES.includes(f) || f === 'core') { console.error(`prove-fuzz: --without takes ${FEATURES.slice(1).join(', ')}; got ${f}`); process.exit(2); }
const on = (f) => !without.has(f);
/** The verifier's obligation kinds against the runtime error kinds a run reports (as tests/prover-soundness.test.mjs). */
const RUNTIME_KIND = {
index: 'index', slice: 'index', key: 'key', divide: 'divide', argument: 'value',
require: 'require', ensure: 'ensure', assert: 'assert',
'invariant-init': 'invariant', 'invariant-keep': 'invariant',
'decreases-bound': 'decreases', 'decreases-step': 'decreases',
};
const PHASE = { 'invariant-init': 'init', 'invariant-keep': 'keep', 'decreases-bound': 'bound', 'decreases-step': 'step' };
/* ------------------------------------------------------------------ */
/* Random numbers: one stream per program, from the seed and its number */
/* ------------------------------------------------------------------ */
function mulberry(seed) {
let s = seed >>> 0;
return () => { s = (s + 0x6D2B79F5) >>> 0; let t = s; t = Math.imul(t ^ (t >>> 15), t | 1); t ^= t + Math.imul(t ^ (t >>> 7), t | 61); return ((t ^ (t >>> 14)) >>> 0) / 4294967296; };
}
const mix = (a, b) => (Math.imul(a ^ 0x9E3779B9, 0x85EBCA6B) ^ Math.imul(b + 0x632BE59B, 0xC2B2AE35)) >>> 0;
let rnd = mulberry(1);
const ri = (lo, hi) => lo + Math.floor(rnd() * (hi - lo + 1));
const pick = (xs) => xs[Math.floor(rnd() * xs.length)];
const chance = (p) => rnd() < p;
/* ------------------------------------------------------------------ */
/* Programs */
/* ------------------------------------------------------------------ */
const HELPERS = {
core: `FUNCTION Twice(N : INTEGER) RETURNS INTEGER
ENSURE RESULT == 2 * N
RETURN N + N
ENDFUNCTION
PROCEDURE Bump(BYREF V : INTEGER, D : INTEGER)
REQUIRE D >= 0
ENSURE V >= OLD(V) AND V == OLD(V) + D
V <- V + D
ENDPROCEDURE
FUNCTION Last(Q : LIST OF INTEGER) RETURNS INTEGER
REQUIRE LENGTH(Q) > 0
ENSURE RESULT == Q[LENGTH(Q) - 1]
RETURN Q[LENGTH(Q) - 1]
ENDFUNCTION
`,
impure: `
FUNCTION Roll() RETURNS INTEGER
ENSURE RESULT >= 0 AND RESULT < 4
RETURN RANDINT(0, 4)
ENDFUNCTION
FUNCTION Draw() RETURNS FLOAT
RETURN RAND(1.0)
ENDFUNCTION
FUNCTION ReadOne() RETURNS INTEGER
DECLARE V : INTEGER
INPUT V
RETURN V
ENDFUNCTION
`,
};
/** The state of the program being made: loop counters in scope, how deep in loops, names used. */
let g;
function intLeaf() {
const xs = ['A', 'B', 'X', 'Y', 'LENGTH(L)', 'LENGTH(M)', ...g.counters, String(ri(-3, 5)), String(ri(0, 3))];
if (on('sized') && chance(0.15)) xs.push('S8'); // one sized type in INTEGER expressions: two sized types do not mix
return pick(xs);
}
function intE(d) {
if (d <= 0 || chance(0.35)) return intLeaf();
const r = rnd();
if (r < 0.22) return `${intE(d - 1)} + ${intE(d - 1)}`;
if (r < 0.36) return `${intE(d - 1)} - ${intE(d - 1)}`;
if (r < 0.46) return `${ri(-2, 3)} * (${intE(d - 1)})`;
if (r < 0.54) return `(${intE(d - 1)}) DIV ${ri(2, 3)}`;
if (r < 0.62) return `(${intE(d - 1)}) MOD ${ri(2, 4)}`;
if (r < 0.68) return `MIN(${intE(d - 1)}, ${intE(d - 1)})`;
if (r < 0.74) return `MAX(${intE(d - 1)}, ${intE(d - 1)})`;
if (r < 0.78) return `ABS(${intE(d - 1)})`;
if (r < 0.83) return `Twice(${intE(d - 1)})`;
if (r < 0.88) return `${pick(['L', 'M'])}[${intE(d - 1)}]`;
if (r < 0.91) return `(${intE(d - 1)}) DIV (${intE(d - 1)})`;
if (on('impure') && r < 0.95) return pick(['Roll()', 'Roll()', 'ReadOne()']);
if (on('float') && r < 0.98) return `${pick(['FLOOR', 'CEIL', 'ROUND', 'INT'])}(${floatE(1)})`;
return intLeaf();
}
function floatE(d) {
const leaves = ['F', 'F', 'FLOAT64(G)', '0.5', '2.0', '1.5', 'A * 1.0', 'X / 2', '0.0'];
if (on('impure')) leaves.push('Draw()');
if (d <= 0 || chance(0.3)) return pick(leaves);
const r = rnd();
if (r < 0.2) return `${floatE(d - 1)} + ${floatE(d - 1)}`;
if (r < 0.35) return `${floatE(d - 1)} - ${floatE(d - 1)}`;
if (r < 0.5) return `${floatE(d - 1)} * ${pick(['0.5', '2.0', '-1.0', '0.1'])}`;
if (r < 0.62) return `${floatE(d - 1)} / ${pick(['2.0', '4.0', '3.0'])}`;
if (r < 0.72) return `ABS(${floatE(d - 1)})`;
if (r < 0.80) return `MIN(${floatE(d - 1)}, ${floatE(d - 1)})`;
if (r < 0.88) return `MAX(${floatE(d - 1)}, ${pick([floatE(d - 1), 'X', 'A'])})`;
return `SQRT(ABS(${floatE(d - 1)}))`;
}
function cond(d) {
const r = rnd();
if (d <= 0 || r < 0.55) return `${intE(1)} ${pick(['==', '!=', '<', '<=', '>', '>='])} ${intE(1)}`;
if (r < 0.68) return `${cond(d - 1)} AND ${cond(d - 1)}`;
if (r < 0.80) return `${cond(d - 1)} OR ${cond(d - 1)}`;
if (r < 0.86) return `NOT (${cond(d - 1)})`;
// a call on the right of AND or OR: the run calls it only when the left side lets it
if (r < 0.93) return pick([`LENGTH(M) > 0 AND Last(M) ${pick(['>=', '<', '=='])} ${intE(1)}`, `LENGTH(M) == 0 OR Last(M) ${pick(['>=', '<'])} ${intE(1)}`, `${intE(1)} > 0 AND Twice(${intE(1)}) > ${intE(1)}`]);
return `${intE(1)} IN ${pick(['L', 'M'])}`;
}
function claim(exclude = null) {
const cs = g.counters.filter((c) => c !== exclude);
const c = cs.length ? pick(cs) : 'X';
const forms = [
`${c} >= 0`, `${c} < LENGTH(L)`, 'LENGTH(M) >= 0', `LENGTH(M) == ${c}`, `LENGTH(M) <= ${c}`, `X >= ${ri(-2, 2)}`, 'X <= Y', 'X == Y', 'Y >= A',
'X >= A', `${c} <= B`, `${c} < B`, 'X MOD 2 == 0', 'X DIV 2 <= X', 'Y == 2 * X', 'LENGTH(M) > 0', 'X + Y >= 0', `${c} >= A`, `${c} <= A`, '1 == 2',
'FORALL K IN [0, LENGTH(M)) : M[K] >= 0', 'X IN M', 'LENGTH(M) == LENGTH(L)', 'LENGTH(M) <= LENGTH(L)', `X == A + ${c}`,
];
if (on('float')) forms.push('F >= 0.0', 'F <= 1.5', 'G == FLOAT32(F)', 'FLOAT64(G) == F', 'FLOAT64(G) <= F', 'F >= X', 'ABS(F) >= 0.0', 'FLOOR(F) <= CEIL(F)', 'G * 2.0 == G + G', 'F == A', 'G == X', 'G <= 1.5', 'G + 1.0 > G');
if (on('sized')) forms.push('S8 <= 127', 'S8 >= 0', 'S8 <= 100', 'U8 >= 0', 'U8 <= 250', 'X == S8', 'H16 >= INT16(S8)', 'S8 + 1 > S8', 'U8 - 1 < U8', 'H16 == X');
if (on('impure')) forms.push('Roll() == Roll()', 'Roll() < 4', 'Roll() >= X', 'Draw() < 1.0', 'ReadOne() == ReadOne()');
return chance(0.75) ? pick(forms) : cond(1);
}
function block(n, ind, depth) {
const out = [];
for (let i = 0; i < n; i++) out.push(...stmt(ind, depth));
return out;
}
function featureStmt(p) {
const fs_ = FEATURES.slice(1).filter((f) => on(f) && ['float', 'sized', 'case', 'impure'].includes(f));
if (!fs_.length) return null;
const f = pick(fs_);
if (f === 'float') {
const r = rnd();
if (r < 0.45) return [`${p}F <- ${floatE(2)}`];
if (r < 0.75) return [`${p}G <- ${pick([`FLOAT32(${floatE(1)})`, 'FLOAT32(X)', 'G * 2.0', 'G + 0.1', 'MAX(G, FLOAT32(X))', 'FLOAT32(F)', 'G / 3.0'])}`];
return [`${p}X <- ${pick(['FLOOR(F)', 'CEIL(F)', 'ROUND(F)', 'INT(F)', 'INT(G)', 'ROUND(G)'])}`];
}
if (f === 'sized') {
const r = rnd();
if (r < 0.25) return [`${p}S8 <- S8 ${pick(['+', '-'])} ${ri(1, 60)}`];
if (r < 0.45) return [`${p}S8 <- ${pick(['X', 'A', 'INT8(X)', 'LENGTH(L)', 'S8 * 2', '-S8', 'ABS(S8)', 'MAX(S8, X)', 'INT8(U8)'])}`];
if (r < 0.65) return [`${p}U8 <- ${pick(['U8 + 1', 'U8 - 1', 'X', 'UINT8(ABS(S8))', 'U8 * 2', 'UINT8(A)', 'LENGTH(M)'])}`];
if (r < 0.80) return [`${p}H16 <- ${pick(['H16 + INT16(S8)', 'INT16(S8) * INT16(S8)', 'H16 * 100', 'X * 1000', 'INT16(U8) + INT16(S8)'])}`];
return [`${p}X <- ${pick(['S8', 'U8 + 0', 'H16 DIV 2', 'U8', 'X + S8'])}`];
}
if (f === 'case') {
const v = pick(['X', 'Y', 'A', 'B MOD 3']);
const arms = [`${p}CASE OF ${v}`, `${p} ${ri(-1, 1)} : ${pick(['X', 'Y'])} <- ${intE(1)}`];
if (chance(0.6)) arms.push(`${p} ${ri(2, 3)} TO ${ri(3, 6)} : ${pick(['X', 'Y'])} <- ${intE(1)}`);
if (chance(0.3)) arms.push(`${p} ${ri(7, 8)}, Twice(${pick(['A', 'B'])}) : ${pick(['X', 'Y'])} <- ${intE(1)}`);
if (chance(0.7)) arms.push(`${p} OTHERWISE : ${pick(['X', 'Y'])} <- ${intE(1)}`);
arms.push(`${p}ENDCASE`);
return arms;
}
// impure
return [`${p}${pick(['X', 'Y'])} <- ${pick(['Roll()', 'Roll() + Roll()', 'ReadOne()', 'Roll() - X', 'ReadOne() + Roll()'])}`];
}
function stmt(ind, depth) {
const p = ' '.repeat(ind);
if (chance(0.3)) { const f = featureStmt(p); if (f) return f; }
const r = rnd();
if (r < 0.18) return [`${p}${pick(['X', 'Y'])} <- ${intE(2)}`];
if (r < 0.27) return [`${p}APPEND(M, ${intE(1)})`];
if (r < 0.31) return [`${p}IF LENGTH(M) > 0 THEN`, `${p} REMOVE(M, ${pick(['0', 'LENGTH(M) - 1'])})`, `${p}ENDIF`];
if (r < 0.34) return [`${p}CALL Bump(${pick(['X', 'Y'])}, ${chance(0.7) ? ri(0, 3) : intE(1)})`];
if (r < 0.36) return [`${p}IF LENGTH(M) > 0 THEN`, `${p} X <- Last(M)`, `${p}ENDIF`];
if (r < 0.52) return [`${p}ASSERT ${claim()}`];
if (g.loopDepth > 0 && r < 0.56) return [`${p}IF ${cond(1)} THEN`, `${p} ${pick(['BREAK', 'CONTINUE'])}`, `${p}ENDIF`];
if (depth <= 0) return [`${p}${pick(['X', 'Y'])} <- ${intE(1)}`];
if (r < 0.67) {
const o = [`${p}IF ${cond(1)} THEN`, ...block(ri(1, 2), ind + 4, depth - 1)];
if (chance(0.5)) o.push(`${p}ELSE`, ...block(ri(1, 2), ind + 4, depth - 1));
o.push(`${p}ENDIF`);
return o;
}
if (r < 0.80) {
const name = ['I', 'J', 'I2', 'J2'].find((c) => !g.counters.includes(c));
if (!name) return [];
let step = pick([null, null, null, 2, 3, -1, -2]);
if (on('step') && chance(0.35)) step = pick(['1 + 1', 'MAX(1, A)', '(B MOD 3) + 1', 'ABS(A) + 1', '-(1 + 1)', '-MAX(1, B)', '0 - 1']);
const lo = pick(['0', '0', 'A', intE(1), '1']); const hi = pick(['LENGTH(L)', 'B', 'A', intE(1), String(ri(0, 6))]);
const down = typeof step === 'number' ? step < 0 : typeof step === 'string' && /^-|^0 - /.test(step);
const head = step === null ? `FOR ${name} <- ${lo} TO ${hi}` : down ? `FOR ${name} <- ${hi} TO ${lo} STEP ${step}` : `FOR ${name} <- ${lo} TO ${hi} STEP ${step}`;
g.counters.push(name); g.loopDepth++;
const inv = chance(0.5) ? [`${p} INVARIANT ${claim()}`] : [];
const body = block(ri(1, 3), ind + 4, depth - 1);
g.counters.pop(); g.loopDepth--;
return [`${p}${head}`, ...inv, ...body, `${p}NEXT ${name}`];
}
if (r < 0.88) {
g.loopDepth++;
const bound = pick(['B', 'LENGTH(L)', String(ri(1, 5)), 'A']);
const inv = chance(0.5) ? [`${p} INVARIANT ${claim()}`] : [];
const body = block(ri(1, 2), ind + 4, depth - 1);
g.loopDepth--;
return [`${p}WHILE X < ${bound}`, ...inv, ...body, `${p} X <- X + ${ri(1, 2)}`, `${p}ENDWHILE`];
}
if (r < 0.94) {
const name = `E${++g.eachN}`;
// a FOR EACH INVARIANT may not name the loop variable (the checker says so), so its claim leaves it out
const inv = on('foreach') && chance(0.6) ? [`${p} INVARIANT ${claim(name)}`] : [];
g.counters.push(name); g.loopDepth++;
const body = block(ri(1, 2), ind + 4, depth - 1);
g.counters.pop(); g.loopDepth--;
return [`${p}FOR EACH ${name} IN ${pick(['L', 'M', `[${intE(0)}, ${intE(0)})`])}`, ...inv, ...body, `${p}NEXT ${name}`];
}
g.loopDepth++;
const rinv = on('repeat') && chance(0.6) ? [`${p} INVARIANT ${claim()}`] : [];
const body = block(ri(1, 2), ind + 4, depth - 1);
g.loopDepth--;
return [`${p}REPEAT`, ...rinv, ...body, `${p} Y <- Y + 1`, `${p}UNTIL Y >= ${pick(['B', '3', 'A', 'LENGTH(L)'])}`];
}
/** Program number n of the seed, as text. */
function program(n) {
rnd = mulberry(mix(SEED, n));
g = { counters: [], eachN: 0, loopDepth: 0 };
const req = chance(0.5) ? [` REQUIRE ${pick(['A >= 0', 'B >= A', 'LENGTH(L) > 0', 'A >= 0 AND B >= 0', 'B > 0'])}`] : [];
const decl = [' DECLARE X : INTEGER', ' DECLARE Y : INTEGER', ' DECLARE M : LIST OF INTEGER'];
const init = [` X <- ${pick(['0', 'A', '1', 'B'])}`, ` Y <- ${pick(['0', 'A', 'X', '2 * X'])}`];
if (on('float')) { decl.push(' DECLARE F : FLOAT', ' DECLARE G : FLOAT32'); init.push(` F <- ${pick(['1.5', '0.0', 'A * 1.0', '0.5', '0.1'])}`, ` G <- ${pick(['FLOAT32(F)', '0.0', '1.0'])}`); }
if (on('sized')) { decl.push(' DECLARE S8 : INT8', ' DECLARE U8 : UINT8', ' DECLARE H16 : INT16'); init.push(' S8 <- 0', ` U8 <- ${ri(0, 3)}`, ' H16 <- 0'); }
const body = block(ri(2, 5), 4, 2);
const lines = ['PROCEDURE P(A : INTEGER, B : INTEGER, L : LIST OF INTEGER)', ...req, ...decl, ...init, ...body, ...(chance(0.5) ? [` ASSERT ${claim()}`] : []), 'ENDPROCEDURE'];
return `${HELPERS.core}${on('impure') ? HELPERS.impure : ''}\n${lines.join('\n')}\n`;
}
/** The arguments and the INPUT lines of run t of program n, and the seed RANDINT and RAND draw from. */
function runInputs(n, t) {
rnd = mulberry(mix(mix(SEED, n), t + 0x51ED));
const args = [ri(-3, 6), ri(-3, 6), Array.from({ length: ri(0, 4) }, () => ri(-2, 5))];
const input = Array.from({ length: 8 }, () => String(ri(-2, 4)));
return { call: `P(${args[0]}, ${args[1]}, [${args[2].join(', ')}])`, input, seed: t + 1 };
}
/* ------------------------------------------------------------------ */
/* Proving and running */
/* ------------------------------------------------------------------ */
function resolve(program, text) {
const p = parseExpression(text);
const sub = program.subs.get(p.expr.name.toUpperCase());
const args = p.expr.args.map((a, i) => { const v = evaluateConstant(program, a); if (!valueFits(sub.params[i].type, v)) throw new Error(`${text}: argument ${i + 1} does not fit`); return v; });
return { name: sub.name, args };
}
/**
* Prove a program, then run it as runs() says; return what was proved and the first finding, if any.
* @param {string} src the program
* @param {{ call: string, input: string[], seed: number }[]} runs the runs to make
*/
export function examine(src, runs, budgetMs = BUDGET_MS) {
const st = studyOf(src);
if (!st.ok) return { parsed: false };
const program = st.program.program;
let rep;
try { rep = verify(program, { budgetMs }); } catch (e) { return { parsed: true, crashed: String(e?.message || e) }; }
const all = rep.units.filter((u) => !u.partial).flatMap((u) => u.obligations);
const proved = all.filter((o) => o.status === 'proved');
const out = { parsed: true, proved: proved.length, partial: rep.units.filter((u) => u.partial).length, runs: 0, stopped: 0, rejected: 0, finding: null };
if (!proved.length) return out;
const pReq = program.subs.get('P')?.requires?.map((r) => r.line) ?? [];
for (const r of runs) {
let tr;
try { tr = run(program, { call: resolve(program, r.call), input: r.input, maxSteps: 3000, contracts: true, seed: r.seed, record: false }); } catch { continue; }
out.runs++;
const e = tr.error;
if (!e) continue;
if (e.kind === 'require' && pReq.includes(e.line)) { out.rejected++; continue; } // P's own REQUIRE turned the arguments away
out.stopped++;
// the obligations this stop is about: same kind and line, the same column for an ASSERT, the same phase for an
// INVARIANT or DECREASES; a finding only when every one of them is proved, so a proved neighbor is not blamed
const same = all.filter((o) => (RUNTIME_KIND[o.kind] || o.kind) === e.kind && o.line === e.line
&& (e.kind !== 'assert' || e.col === undefined || o.col === e.col)
&& (!e.phase || !PHASE[o.kind] || PHASE[o.kind] === e.phase));
if (same.length && same.every((o) => o.status === 'proved')) {
out.finding = { obligation: { kind: same[0].kind, line: same[0].line, col: same[0].col, label: same[0].label }, run: r, stop: { kind: e.kind, line: e.line, phase: e.phase, message: String(e.message) } };
break;
}
}
return out;
}
/** The runs of program n. */
const runsOf = (n) => Array.from({ length: RUNS }, (_, t) => runInputs(n, t));
/**
* The smallest program, line by line, that still shows a finding of the same kind under the same runs: drop one
* line (or a whole block with its body) at a time, keep the drop when a finding of that kind remains.
*/
function reduce(src, runs, kind) {
let lines = src.split('\n');
const holds = (ls) => { const r = examine(ls.join('\n'), runs); return r.finding && r.finding.obligation.kind === kind ? r : null; };
const indent = (l) => l.match(/^ */)[0].length;
const OPEN = /^\s*(IF|FOR|WHILE|REPEAT|CASE|FUNCTION|PROCEDURE)\b/;
const CLOSE = /^\s*(ENDIF|NEXT|ENDWHILE|UNTIL|ENDCASE|ENDFUNCTION|ENDPROCEDURE)\b/;
// the last line of the block line i opens (the line itself when it opens none)
const blockEnd = (ls, i) => {
if (!OPEN.test(ls[i])) return i;
for (let j = i + 1; j < ls.length; j++) {
if (indent(ls[j]) === indent(ls[i]) && CLOSE.test(ls[j])) return j;
if (ls[j].trim() && indent(ls[j]) < indent(ls[i])) break;
}
return i;
};
let changed = true; let tries = 0;
while (changed && tries < 400) {
changed = false;
for (let i = lines.length - 1; i >= 0 && tries < 400; i--) {
if (!lines[i].trim() || /^\s*(ENDIF|NEXT|ENDWHILE|UNTIL|ENDCASE|ENDFUNCTION|ENDPROCEDURE|ELSE|PROCEDURE P)\b/.test(lines[i])) continue;
const j = blockEnd(lines, i);
const cand = [...lines.slice(0, i), ...lines.slice(j + 1)];
tries++;
if (holds(cand)) { lines = cand; changed = true; }
}
}
const tidy = lines.join('\n').replace(/\n{3,}/g, '\n\n').replace(/^\n+/, '');
const last = examine(tidy, runs);
return last.finding ? { src: tidy, result: last } : { src: lines.join('\n'), result: examine(lines.join('\n'), runs) };
}
/* ------------------------------------------------------------------ */
/* The run */
/* ------------------------------------------------------------------ */
if (process.argv[1] && path.resolve(process.argv[1]) === fileURLToPath(import.meta.url)) {
const started = Date.now();
const counts = { programs: 0, accepted: 0, withProved: 0, proved: 0, partial: 0, runs: 0, stopped: 0, rejected: 0, crashed: 0 };
const findings = [];
const numbers = ONLY !== null ? [Number(ONLY)] : Array.from({ length: PROGRAMS }, (_, i) => i);
let timedOut = false;
for (const n of numbers) {
if (TIME_S && Date.now() - started > TIME_S * 1000) { timedOut = true; break; }
const src = program(n);
const runs = runsOf(n);
counts.programs++;
if (ONLY !== null && !flag('json')) console.log(src);
const r = examine(src, runs);
if (!r.parsed) continue;
counts.accepted++;
if (r.crashed) { counts.crashed++; findings.push({ n, crash: r.crashed, src }); continue; }
counts.partial += r.partial;
if (!r.proved) continue;
counts.withProved++; counts.proved += r.proved; counts.runs += r.runs; counts.stopped += r.stopped; counts.rejected += r.rejected;
if (r.finding) {
const red = flag('no-reduce') ? { src, result: r } : reduce(src, [r.finding.run], r.finding.obligation.kind);
findings.push({ n, ...(red.result.finding ?? r.finding), src: red.src });
}
}
const seconds = ((Date.now() - started) / 1000).toFixed(0);
const features = FEATURES.filter(on).join(', ');
if (flag('json')) {
console.log(JSON.stringify({ seed: SEED, features: FEATURES.filter(on), budgetMs: BUDGET_MS, seconds: Number(seconds), timedOut, counts, findings }, null, 2));
} else {
console.log(`prove-fuzz seed ${SEED}: ${counts.programs} programs (${features}) in ${seconds} s${timedOut ? ` (stopped at --time ${TIME_S})` : ''}`);
console.log(` ${counts.accepted} accepted by the checker, ${counts.withProved} with something proved: ${counts.proved} proved obligations`);
console.log(` ${counts.runs} runs, ${counts.stopped} stopped by a failed check, ${counts.rejected} turned away by P's REQUIRE; ${counts.partial} routines the prover did not finish (not counted)`);
for (const f of findings) {
console.log('');
if (f.crash) { console.log(`PROVER CRASH in program ${f.n}: ${f.crash}`); console.log(f.src); continue; }
const o = f.obligation;
console.log(`FINDING in program ${f.n} (reproduce: node scripts/prove-fuzz.mjs --seed ${SEED} --only-program ${f.n}${without.size ? ` --without ${[...without].join(',')}` : ''})`);
console.log(` ${o.kind}@${o.line} "${o.label}" is proved, and ${f.run.call} (run seed ${f.run.seed}) stops at line ${f.stop.line}: ${f.stop.message.slice(0, 200)}`);
console.log(` the program${flag('no-reduce') ? '' : ', reduced'}:`);
console.log(f.src.split('\n').map((l) => ` ${l}`).join('\n'));
}
console.log('');
console.log(findings.length ? `${findings.length} finding(s): a proved obligation a run breaks is a soundness bug (docs/engines.md#soundness)` : 'nothing found');
}
if (KEEP && findings.length) {
fs.mkdirSync(KEEP, { recursive: true });
for (const f of findings) {
if (f.crash) continue;
const head = [`// Found by prove-fuzz, seed ${SEED}, program ${f.n}: ${f.obligation.kind}@${f.obligation.line} is proved and a run breaks it.`,
`// CALL: ${f.run.call}`, ...f.run.input.map((l) => `// INPUT: ${l}`), ...(f.run.seed !== 1 ? [`// A random number this run draws comes from seed ${f.run.seed}; the soundness test runs a program with seed 1.`] : []),
];
// the header moves every line down by its own length: name the obligation where it will be
head.push(`// MUST-NOT-PROVE: ${f.obligation.kind}@${f.obligation.line + head.length + 1}`);
const file = path.join(KEEP, `prove-fuzz-${SEED}-${f.n}.pseudo`);
fs.writeFileSync(file, `${head.join('\n')}\n${f.src.trimEnd()}\n`);
console.log(`wrote ${file}`);
}
}
process.exit(findings.length ? 1 : 0);
}