Lab 26: The Test Matrix (Milestone 14)

Background

Five of the six kinds of test already exist. This lab adds fuzzing, completes the property and compatibility suites, wires the whole thing into CI, and runs the panic audit.

The deliverable is a claim you can defend: no script input, however malformed, panics or hangs.

Why This Lab Matters

• A #[deny(unwrap_used)] is a hypothesis; a fuzzer is the experiment.
• The validator/VM pairing is Ember's actual security guarantee, and until there is a fuzz target asserting it, it is an assumption.
• Committed corpora turn crash reproducers into permanent regression tests.

Prerequisites

• Labs 24–25 complete.
• Testing Strategy read.
• Nightly toolchain installed (cargo-fuzz requires it).

Predict First

1. Which module do you expect the fuzzer to find a panic in first?
2. fuzz/run.rs feeds arbitrary bytes as source. What limits must it set, and why?
3. What is the assertion in bytecode_validate.rs, and why is it a pairing rather than a single property?
4. Your property test generates programs. What is the one meta-test it needs?
5. How many unwrap()s are in src/vm.rs right now? Guess, then count.

Step 1: The Panic Audit

#![allow(unused)]
fn main() {
// src/vm.rs, heap.rs, table.rs, lexer.rs, parser.rs, compiler.rs, strings.rs
#![deny(clippy::unwrap_used, clippy::expect_used, clippy::panic,
        clippy::unreachable, clippy::indexing_slicing)]
}

cargo clippy --all-targets -- -D warnings 2>&1 | grep -c 'unwrap_used\|indexing_slicing'

Work through every one. Each survivor becomes an #[allow] with a comment stating the invariant and what proves it:

#![allow(unused)]
fn main() {
// SAFETY-BY-VALIDATION: `validate()` proved every jump target is <= code.len()
// and `run()` is only reachable after `validate()`. See bytecode::validate rule 4.
#[allow(clippy::indexing_slicing)]
let op = chunk.code[ip];
}

Count them. Ember's answer should be a small number you can list in docs/limitations.md:

Unchecked indexing sites (each justified by a validator rule or an immediately
preceding check): 6, all in src/vm.rs's dispatch loop. See the comments.

That number being small and stated is what makes the no-panic claim credible.

Step 2: The Five Fuzz Targets

cargo install cargo-fuzz
cargo fuzz init

#![allow(unused)]
fn main() {
// fuzz/fuzz_targets/lex.rs
fuzz_target!(|data: &[u8]| {
    if let Ok(s) = std::str::from_utf8(data) { let _ = ember::lexer::tokenize(s); }
});

// fuzz/fuzz_targets/parse.rs — tokenize + parse
// fuzz/fuzz_targets/compile.rs — + compile, and VALIDATE the result:
fuzz_target!(|data: &[u8]| {
    if let Ok(s) = std::str::from_utf8(data) {
        if let Ok(proto) = ember::compile(s) {
            // Anything our own compiler produces must pass our own validator.
            // A failure here is a COMPILER bug found by a parser fuzzer.
            ember::bytecode::validate(&proto).expect("compiler emitted invalid bytecode");
        }
    }
});

// fuzz/fuzz_targets/run.rs — full execution under STRICT limits
fuzz_target!(|data: &[u8]| {
    if let Ok(s) = std::str::from_utf8(data) {
        let mut e = ember::Engine::builder()
            .limits(ember::Limits { instructions: 100_000, memory: 1 << 20, call_depth: 32,
                                    expr_depth: 64, ..Default::default() })
            .build();
        let _ = e.execute(s);       // Err is fine. Panic and hang are not.
    }
});

// fuzz/fuzz_targets/bytecode_validate.rs — THE pairing
fuzz_target!(|data: &[u8]| {
    if let Ok(proto) = ember::bytecode::deserialize(data) {
        if ember::bytecode::validate(&proto).is_ok() {
            // THE security property: anything the validator ACCEPTS, the VM can
            // EXECUTE without panicking. Neither half means much alone —
            // a validator that accepts nothing is vacuously safe, and a VM with
            // no validator in front of it is a liability.
            let mut vm = ember::Vm::with_limits(strict());
            let _ = vm.run_proto(proto);
        }
    }
});
}

The compile.rs target is the sleeper. It fuzzes the parser and asserts a property of the compiler, which finds "the compiler emits an unbalanced stack for this weird input" — a class the golden corpus will never reach.

Step 3: Structured Fuzzing

Arbitrary bytes rarely parse. To reach the VM you need inputs that are mostly valid:

#![allow(unused)]
fn main() {
// fuzz/fuzz_targets/run_structured.rs
use arbitrary::Arbitrary;

#[derive(Arbitrary, Debug)]
enum FuzzExpr { Int(i32), Add(Box<FuzzExpr>, Box<FuzzExpr>), Call(u8), Index(u8, u8), /* ... */ }

fuzz_target!(|program: FuzzProgram| {
    let src = program.to_source();      // ALWAYS syntactically valid
    let _ = engine_with_strict_limits().execute(&src);
});
}

Run both. The byte-level target finds lexer and parser bugs; the structured one gets past the front end and exercises the VM, the collector, and the metamethod paths.

Tip: Seed the byte-level corpus with tests/golden/**/*.ember. A fuzzer that starts from valid programs mutates its way into interesting invalid ones far faster than one starting from \0.

Step 4: Complete the Property Suite

Four properties, from the chapter, plus the meta-test that makes them meaningful:

#![allow(unused)]
fn main() {
#[test]
fn generated_programs_produce_output() {
    // A property test over silent programs reports confidence you have not earned.
    let sample = sample_programs(100, 4);
    let silent = sample.iter().filter(|p| !p.contains("print")).count();
    assert_eq!(silent, 0, "{silent}/100 generated programs produce no observable output");
}
}

And the metamorphic ones, which partially cover differential testing's shared-code blind spot:

#![allow(unused)]
fn main() {
proptest! {
    #[test] fn wrapping_in_if_true_changes_nothing(p in arb_program(4)) {
        prop_assert_eq!(run(&p), run(&format!("if true then\n{p}\nend")));
    }
    #[test] fn an_unused_local_changes_nothing(p in arb_program(4)) {
        prop_assert_eq!(run(&p), run(&format!("local _unused = 42\n{p}")));
    }
    #[test] fn a_do_block_changes_nothing(p in arb_program(4)) {
        prop_assert_eq!(run(&p), run(&format!("do\n{p}\nend")));
    }
}
}

The third one is sharper than it looks: wrapping in do ... end changes scope depth, slot allocation, and POP emission, so it exercises exactly the compiler machinery a hand-written test would not think to vary.

Step 5: Compatibility, and the Coupling

#![allow(unused)]
fn main() {
#[test] // --features lua-compat
fn corpus_agrees_with_real_lua_where_we_do_not_diverge() { /* Lab 12 */ }

#[test]
fn every_lua_divergence_is_documented() {
    for case in corpus().iter().filter(|c| c.diverges_from_lua) {
        assert!(divergence_ids_in_appendix().contains(&case.divergence_id),
                "{} opts out with an undocumented id", case.name);
    }
}
}

Without the second test, opting out becomes the path of least resistance and the appendix rots. This is the same coupling pattern as the threat-model meta-test: a document and a test file that must agree, checked by a third test.

Step 6: CI

Add the nine commands from the hardening checklist, split into per-commit and nightly:

# per commit (must be fast)
- run: cargo fmt --check
- run: cargo clippy --workspace --all-targets --all-features -- -D warnings
- run: cargo test --workspace --all-features
- run: cargo test --doc
- run: ./scripts/boundary-audit.sh
- run: cargo deny check
- run: cargo semver-checks check-release

# nightly (slow, thorough)
- run: cargo test --features gc-stress            # the whole corpus, ~1000x slower
- run: cargo audit
- run: for t in lex parse compile run bytecode_validate repl; do
         cargo fuzz run $t -- -max_total_time=600; done
- run: cargo llvm-cov --workspace --lcov --output-path lcov.info

gc-stress over the whole corpus belongs in nightly, not per-commit. It is the single most valuable slow test you have and running it per-commit would make people disable it.

The Trace

$ cargo fuzz run run -- -max_total_time=60
INFO: Running with entropic power schedule
#2      INITED cov: 1204 ft: 3410 corp: 41/2891b
#1024   NEW    cov: 1319 ft: 4102 corp: 63/7204b
...
==31337== ERROR: libFuzzer: deadly signal
    #4 ember::table::Table::set ...
    #5 ember::vm::Vm::run ...

Failing input: fuzz/artifacts/run/crash-a3f9c1

$ cargo fuzz fmt run fuzz/artifacts/run/crash-a3f9c1
local t = {} t[1e308 * 10] = 1

A NaN-ish float key that normalize did not reject, reaching HashKey::FloatBits with an infinity. Fix it, then — and this is the step people skip:

# 1. The reproducer becomes a REGRESSION TEST.
cp fuzz/artifacts/run/crash-a3f9c1 fuzz/corpus/run/
echo 'local t = {} t[1e308 * 10] = 1' > tests/golden/errors/infinite-table-key.ember
echo '!error kind=Runtime' > tests/golden/errors/infinite-table-key.expected

# 2. Commit BOTH — the corpus entry and the golden case.
git add fuzz/corpus/run tests/golden/errors

The corpus entry keeps the fuzzer near that region; the golden case makes the fix permanent and checks it in both backends.

And the pairing target, which is the one that proves the security property:

$ cargo fuzz run bytecode_validate -- -max_total_time=600
...
Done 4194304 runs in 601 second(s)

Ten minutes, no crashes. That is the evidence for "anything the validator accepts, the VM can execute safely" — and it is why Lab 22's bytecode cache is defensible.

Expected Output

$ cargo clippy --all-targets -- -D warnings
    Finished
$ rg -c '#\[allow\(clippy::indexing_slicing\)\]' src/
src/vm.rs:6

$ cargo test --workspace --all-features
test result: ok. 312 passed; 0 failed

$ cargo llvm-cov --summary-only
  src/vm.rs          96.2%
  src/compiler.rs    94.8%
  src/table.rs       91.4%
  src/heap.rs        89.7%
  ...

Do not chase the percentage. Chase the four specific lists from the chapter: every dispatch arm, every arith arm, every ErrorKind site, every trace_children branch.

Debugging Steps

The fuzzer finds a panic in five seconds

Expected on the first run. Fix it, add the corpus entry and the golden case, re-run.

cargo fuzz finds nothing after an hour

Your corpus is empty or your target rejects everything early. Seed from tests/golden/**/*.ember.

The compile.rs target asserts and it is your compiler's fault

That is the target working — a parser fuzzer found a compiler bug. Fix the compiler.

The property test passes instantly, always

The generator produces silent programs. The meta-test exists for this.

gc-stress per-commit makes CI take 40 minutes

Move it to nightly. Run a small subset per commit.

Coverage is 95% and a bug shipped anyway

Coverage measures execution, not assertion. A line executed by a test that asserts nothing is covered and untested.

Experiment

CLAIM. Structured fuzzing finds different bugs from byte-level fuzzing, and neither subsumes the other.

METHOD. Run run.rs (bytes) and run_structured.rs for one hour each, from empty corpora. Classify every crash by the module it was found in.

PREDICTION. Which target finds lexer/parser bugs? Which reaches the collector? Is there any overlap?

RESULT. A table in docs/learning/15-testing.md. The expected shape: bytes find front-end bugs and almost never reach the VM; structured finds VM, table, and GC bugs and never finds a lexer bug. Two targets because two populations of input, and knowing that is what stops you from running one and believing you fuzzed the runtime.

Test

#![allow(unused)]
fn main() {
#[test]
fn the_vm_has_no_unjustified_unchecked_indexing() {
    // A structural audit: every #[allow(clippy::indexing_slicing)] must be
    // immediately preceded by a comment beginning "SAFETY-BY-".
    let src = std::fs::read_to_string("src/vm.rs").unwrap();
    for (i, line) in src.lines().enumerate() {
        if line.contains("allow(clippy::indexing_slicing)") {
            let prev = src.lines().nth(i.saturating_sub(1)).unwrap_or("");
            assert!(prev.trim_start().starts_with("// SAFETY-BY-"),
                    "unjustified allow at src/vm.rs:{}", i + 1);
        }
    }
}

#[test]
fn anything_the_validator_accepts_the_vm_can_run() {
    // The pairing, as a deterministic test over the committed fuzz corpus.
    for entry in std::fs::read_dir("fuzz/corpus/bytecode_validate").unwrap() {
        let data = std::fs::read(entry.unwrap().path()).unwrap();
        if let Ok(p) = deserialize(&data) {
            if validate(&p).is_ok() {
                let _ = Vm::with_limits(strict()).run_proto(p);   // must not panic
            }
        }
    }
}

#[test]
fn every_committed_crash_reproducer_is_also_a_golden_case() {
    // A fix without a regression test is a fix that comes back.
    let artifacts = count_files("fuzz/corpus");
    let regressions = count_files("tests/golden/fuzz-regressions");
    assert!(regressions >= artifacts / 2,
            "{artifacts} corpus entries but only {regressions} regression cases");
}

#[test]
fn generated_programs_produce_output() { /* Step 4 */ }

#[test]
fn every_lua_divergence_is_documented() { /* Step 5 */ }

#[test]
fn every_dispatch_arm_is_covered_by_the_corpus() {
    // Run the corpus with per-opcode counters; assert every opcode executed
    // at least once. An uncovered arm is an opcode nobody tested.
    let mut seen = [0u64; OPCODE_COUNT];
    for case in corpus() { accumulate_opcode_counts(&case.src, &mut seen); }
    let missing: Vec<_> = (0..OPCODE_COUNT).filter(|&i| seen[i] == 0)
                                           .map(opcode_name).collect();
    assert!(missing.is_empty(), "opcodes never executed by the corpus: {missing:?}");
}
}

Challenge Extensions

1. Differential fuzzing. A target that runs both backends on generated programs and asserts agreement. The highest-yield target in the project, and it needs the structured generator.
2. A minimizer. cargo fuzz tmin shrinks a crash input; write a semantic minimizer for Ember source that removes statements and simplifies expressions while preserving the crash.
3. Mutation testing. cargo-mutants mutates your source and checks whether a test fails. A surviving mutant is a hole in the suite that coverage will not show you.
4. A Lua test-suite subset. Run the parts of Lua's own test suite that fall inside Ember's compatible subset. It is the strongest compatibility evidence available.
5. Continuous fuzzing. OSS-Fuzz or a nightly job with corpus persistence across runs. A fuzzer that resets every night finds the same shallow bugs forever.

Deliverables

• #![deny(clippy::unwrap_used, expect_used, panic, unreachable, indexing_slicing)] on the seven core modules.
• Every remaining #[allow] justified by a // SAFETY-BY- comment, with the audit test; the count stated in docs/limitations.md.
• Five byte-level fuzz targets plus one structured one, each run ≥10 minutes clean.
• compile.rs asserts that our compiler's output always validates.
• bytecode_validate.rs asserts the validator/VM pairing.
• Corpora seeded from the golden suite and committed.
• Every crash reproducer became a corpus entry and a golden regression case.
• The four property tests plus the produces-output meta-test.
• Compatibility testing with the documented-divergence coupling test.
• The opcode-coverage test passing.
• CI split into per-commit and nightly, with all eleven commands.
• The structured-vs-byte fuzzing experiment recorded.

Validation / Self-check

1. How many unchecked-indexing sites are in your VM, and what justifies each?
2. Why does the compile target assert a property of the compiler? What class of bug does that find?
3. State the validator/VM pairing and explain why neither half suffices.
4. Why do you need both byte-level and structured fuzzing? What does each find?
5. What must happen to every crash reproducer, and why both things?
6. Why is do ... end wrapping a sharper metamorphic property than if true then?
7. Why does opting out of the Lua comparison require naming a documented divergence?
8. Why is 95% coverage compatible with shipping a bug?

Next: Lab 27 — Benchmarks.