Skip to content
→ All work

Case study 23 / 37

AST-StateFuzzer

A structure-aware fuzzer that generates and mutates typed syntax trees, checks them with differential oracles, and shrinks every failure to a readable reproducer.

Status
Experimental
Period
2026
Domain
Tools · Experiments
Language
Rust
Last push
26 OCT 2026
License
MIT OR Apache-2.0
Source of claims
README.md, docs/ARCHITECTURE.md, docs/COVERAGE.md, docs/LIMITATIONS.md, docs/LANGUAGE.md, CHANGELOG.md, src/fuzz/rng.rs, tests/, .github/workflows/ci.yml

A Rust fuzzer aimed at type checkers, optimizers and interpreters rather than lexers. It targets Mini, a small language implemented in the repository, generating mostly well-typed programs, checking round-trip, type-soundness and optimizer-equivalence oracles, and minimising failures with grammar-aware passes that only propose valid smaller programs.

01/The problem

Byte-level fuzzers find memory-safety bugs in parsers, but most of their inputs to a compiler die in the lexer. Bugs in type checkers and optimizers need valid, mostly well-typed programs and an oracle that can tell a wrong answer from a right one.

02/The system

A Rust fuzzer aimed at type checkers, optimizers and interpreters rather than lexers. It targets Mini, a small language implemented in the repository, generating mostly well-typed programs, checking round-trip, type-soundness and optimizer-equivalence oracles, and minimising failures with grammar-aware passes that only propose valid smaller programs.

Fuzzing loop (README)7 components
  • Rng::fork to Typed generator
  • Rng::fork to AST mutators
  • Corpus to AST mutators
  • Typed generator to Oracles
  • AST mutators to Oracles
  • Oracles to Feature coverage
  • Feature coverage to Corpus
  • Oracles to Minimizer

03/Implementation

  1. 01Mini: lexer, recursive-descent parser with 1 MiB and nesting-200 limits, canonical printer, static type checker, fuel-bounded interpreter and a constant-folding optimizer.
  2. 02A type-aware generator with depth, block and statement budgets, plus eight AST mutation operators including subtree replace, hoist and corpus splicing.
  3. 03Oracles for print → parse round trip, type soundness and optimizer equivalence; crashes captured with panic location; timeouts by fuel or wall clock.
  4. 04Execution-feature coverage feedback, deduplication by stable failure signature, and a JSON report with reproducer and minimised program.
  5. 05A grammar-aware minimiser (statement ddmin, unwrapping, hoisting, literal shrinking) that keeps the exact failure signature.

04/Engineering

Planted bugs as the acceptance test

Four deliberately introduced bugs must each be found from seed 1 within 20,000 iterations and shrunk to at most 10 nodes; a separate test asserts zero findings on the correct implementation.

(seed, iteration) names an input exactly

Each iteration uses Rng::fork(seed, i) on a pinned xoshiro256** stream, so any finding can be regenerated on any platform.

Measured, not claimed

Test-suite coverage is measured with cargo llvm-cov, and the suite plus 60-second libFuzzer runs of both targets pass under AddressSanitizer.

05/Interface

No product screenshots are published for this project. The visual above is a code-driven representation of how it behaves, built from the repository source — not a screenshot.

06/Tech stack

  • Rust
  • xoshiro256**
  • Differential testing
  • Delta debugging
  • libFuzzer (optional)
  • AddressSanitizer

07/Result

Verified outcomes

  • Per the README: 96.9% line and 95.8% region coverage of the crate; CI on Linux, macOS and Windows; MIT OR Apache-2.0.

Known limitations

  • Only Mini is supported; there is no plug-in interface for other grammars yet.
  • Coverage feedback is semantic, not control-flow; programs run in process; single-threaded.
  • No unplanted bug has been found in Mini, which is evidence for the implementation, not proof.

08/Links

GitHub repository ↗

Related work

Next case study

Emberline →