WEP: Compiler Fuzzing

Context

The campaign exists to find wado-compiler bugs — wrong code above all, crashes as well.

Two axes are independent: where inputs come from, and what decides that an input found a bug. Most fuzzing supplies inputs and has only "it crashed" for an oracle, which is the weaker half of what a compiler needs: a compiler's worst bugs are silent, and a program that miscompiles still exits zero.

The position this WEP records is deliberate about which axis is scarce. The oracle is strong; the input source is a fixed corpus.

Decision

The oracle is metamorphic

builtin::black_box(false) is a condition no pass can decide: the NIR optimizer treats the call as opaque, wir_build carries it into the WIR as WirInstr::BlackBox, and codegen emits the argument where the call stood. A block behind such a guard is unreachable at run time, and the whole pipeline still compiles it: every NIR pass, every WIR pass, and codegen. Injecting one into a working program must leave that program's output untouched, and a difference is a wrong-code bug.

The guard reaches the emitted Wasm, and the engine folds it there. A mutant therefore costs some code size. In exchange the campaign covers the WIR passes and codegen, which a barrier ending at wir_build never reached.

There is no second compiler to compare against, and the fixture's recorded expectation is not the oracle either — the program before injection is. That is what lets the campaign judge a program it was never told the answer for, and it is why the oracle transfers unchanged to inputs from any source.

Inputs are transformed, not generated

The corpus is the repository's own Wado, drawn from a set of roots: the e2e fixtures, the stdlib modules that carry test blocks, and the example/ programs. Every mutant is an existing program plus guards; nothing invents a program. Compiler coverage is therefore bounded by what that material happens to exercise, which is the known cost of this choice. The roadmap states the condition for lifting it.

A root states what a source does not: which files under it are programs, and how one is run. A fixture's __DATA__ section says that for the fixtures, so theirs is the root that reads one; elsewhere the root decides — a stdlib module under the test world, an example under wasi:cli/command. It also decides what is material: a source the world it runs under cannot enter — a stdlib module with no test block, an example/ library with no export fn run — exports nothing an injection could move, and is not drawn at all.

Reach is widened by guard shape and payload shape

These are the two knobs, and they are ordered by the analysis family each attacks rather than by novelty.

Guard shape decides what the surrounding control flow looks like: a branch (if) or a loop (while). Only the loop reaches the loop passes.

Payload decides what the dead region does to the live program:

• An opaque write to every writable binding in scope makes the dead region mutate live state, which is what the alias and mod/ref analyses behind licm, store_load_forward, field_scalarize, copy_prop and sroa rest on. It needs a writable binding, so it reaches only part of the corpus.
• An opaque read of every binding in scope makes live values appear used. It demands no mutability, so it reaches every site, and it attacks liveness, DCE, escape analysis and value-copy elision instead.
• Statements harvested from elsewhere in the same function reach the rest, at the cost of a free-variable analysis to keep them type-correct.

Each combination of the two is its own subject, injected alone against the same baseline: a fixture the compiler refuses one payload or one shape at stays in the campaign under the others.

Calibration precedes mutation

A fixture must be a valid oracle before it can be a subject. Calibration injects an empty guard of each shape everywhere and keeps the fixtures whose observable behaviour is unmoved; one that moves observes something an injection perturbs — a column, an allocation address, a generated test-export name — and is recorded with that reason rather than silently dropped. It judges one shape at a time. The corpus records which shapes each source answers for, and the mutation stage runs only those.

A fixture whose own output moves between runs of the same program is a separate case, and conflating it with a guard's doing is how a campaign learns to cry wolf. A divergence re-runs the baseline first, and a baseline that disagrees with itself is recorded as nondeterministic.

A finding is reduced before it is reported

Injecting one site per compile is tens of thousands of compile-and-run cycles, which neither CI nor a laptop carries. A mutant therefore carries every site at once, and a divergence or a crash is delta-debugged back to the guards that cause it, with the reduced mutant written out as source that can be read and re-run. Without this a finding names a file; with it, a statement.

Injection sites are structural

A site is a statement boundary inside a function or test body, and it must start a token — a position inside a string literal parses after a guard is spliced in, so the parse check alone cannot see it. Guards are written on a single line, so code after an injection keeps the line numbers it had and a fixture that prints an assertion diagnostic is not disturbed.

CI is a campaign, not a gate

Schedule and dispatch only, never a PR trigger: the run takes far longer than a review, and a finding is a bug report rather than a reason to block a change. Work is sharded so every run covers the whole corpus, and findings fail the run.

Roadmap

Ordered by yield per cost. Each run reports the corpus it drew and the sites each shape and payload reached.

• [x] Opaque read payload. Its first full run found three bugs: two colliding mangled names (&&T spelled as &T, a generic newtype spelled without its arguments) and a closure capture handed the box where the field holds the value.
• [ ] Retry a payload the compiler refuses without the bindings the error names. A resource binding whose read is a move costs a fixture the whole read payload; the report names each one under dropped combinations, so the cost of leaving this undone is on the page.
• [ ] Recompile determinism as a second oracle: compile each fixture twice and compare the Wasm byte for byte. Catches what no output comparison can see.
• [x] while builtin::black_box(false) { … } as a second guard shape. A source is calibrated for each shape and loses one at a time, as it does a payload. The loop's own value block puts a reference in a call argument, which is the shape the O2 bug below needed.
• [x] Calibrate and mutate at O1, O2 and Os as well as O0 and O3. O2 is what a release build and wado test run, and it was not covered. WADO_EMI_LEVELS trades levels for corpus when a run has a time budget. The first run of the two found a wrong-code bug at each of the new levels: at O1 a stale local type in the value pool, which emitted a struct.get of one struct type on another; at O2 a field constant forwarded over the mutation a callee made through a reference, which turned an assertion into an unconditional trap. Both were invisible at O0 and O3.
• [x] Draw the corpus from the stdlib and example/ too. Its first run put the stdlib's own tests under O3, which nothing else does — wado test runs them at O2 — and the baselines that failed there were two wrong-code bugs the fixtures never reached.
• [ ] Draw the corpus from the packages (package-gale and its siblings) too. A package is many files behind a manifest, so the runner needs to resolve dependencies and to compile an entry while one module below it carries the injection — neither of which a single-file subject asks for.
• [ ] Harvested-statement payload.
• [ ] Name the pass behind a finding by bisecting WADO_LIST_PASSES with WADO_SKIP_PASS, and write the reduced program out as a fixture.

When to generate programs

A generator is the higher ceiling and is deferred, not rejected. The condition for building one is that guard and payload shapes stop producing findings over a full corpus run — until then the cheaper knob is still paying, and a generator would be optimising the end that is not scarce.

The oracle transfers to generated programs unchanged. The work is the generator itself: it must emit programs that type-check, terminate, are deterministic and produce observable output, which is what the oracle requires of any subject. Generating from the typed AST, so well-typedness holds by construction, is the approach this design assumes.