Lab 04 — Build a Coverage-Guided Fuzzer (with Dedup and Minimization)

Intensity: advanced. Instead of using a fuzzer, you build one — a working, deterministic, coverage-guided mutation fuzzer in pure Python, complete with crash deduplication by root-cause signature and delta-debugging minimization. By implementing the feedback loop yourself you will understand, at mechanism level, why coverage guidance turns fuzzing from blind luck into a guided evolutionary search, why "1000 crashes" is usually "3 bugs," and why every finding becomes a minimized regression test.

Prerequisites: Phase 01 (the memory-defect families, crash triage), Phase 08 WARMUP Chapters 2–7. Authorized-lab only — the target is a purpose-built buggy parser with seeded defects.

Table of Contents

• 1. Why Random Fuzzing Fails
• 2. Coverage Guidance — The Core Idea
• 3. The Instrumented Target
• 4. The Multi-Byte Coverage Wall
• 5. Crash Deduplication
• 6. Minimization (Delta Debugging)
• 7. Architecture of This Lab
• 8. Implementation Steps
• 9. Running and Expected Evidence
• 10. Mapping the Toy to Real Fuzzers
• 11. Hardening / Stretch Tasks
• 12. Common Mistakes
• 13. Interview Questions
• 14. Resume Bullet
• 15. References

1. Why Random Fuzzing Fails

A fuzzer feeds many inputs to a target and watches for crashes. The naive version generates random bytes. It fails almost immediately against any real program, because real parsers have gates: a magic-number check, a length field, a valid opcode. Random bytes get rejected at the first gate and never reach the interesting code. If reaching a bug requires even a 4-byte magic value, random search needs ~2³² tries to start.

The breakthrough that made fuzzing the most productive bug-finding technique in the industry is coverage guidance.

2. Coverage Guidance — The Core Idea

Instrument the target so that, for each input, you learn which code edges it executed. Then run a feedback loop:

pick an input from the corpus
  → mutate it (flip/insert/delete a byte)
  → run the (instrumented) target
  → did this input reach a NEW edge?
        yes → it is "interesting": KEEP it in the corpus
        no  → discard it
  → did it crash? → save the crash

The magic is in keeping interesting inputs. An input that gets one byte of the magic right, or reaches a new branch, is retained and bred from. Over many iterations the corpus evolves toward inputs that penetrate deeper into the program — a guided evolutionary search through the input space. This is exactly how libFuzzer and AFL++ work; the only difference from this lab is that they get coverage from compiler instrumentation (-fsanitize=fuzzer / AFL's instrumentation) instead of a Python set.

The function is_interesting(coverage, frontier) — "did this run reach an edge not in the global frontier?" — is the entire heart of the technique. It is two lines of code and it is the difference between finding nothing and finding everything.

3. The Instrumented Target

The provided target(data, coverage) is a small parser with three seeded bugs, and it reports the edges it traversed into the coverage set:

magic "FUZZ"  ── gate ──▶ opcode dispatch
   opcode 1 (length):  declared > remaining   →  CrashError("oob-read")   [BUG A]
   opcode 2 (divide):  divisor == 0           →  CrashError("div-zero")   [BUG B]
   opcode 3 (nested):  byte5==0x7F && byte6==0x7F → CrashError("deep-assert")  [BUG C]

Each CrashError carries a stable signature — the dedup key, modeling the top stack frame / faulting location a real triage tool would extract.

4. The Multi-Byte Coverage Wall

BUG C is the pedagogically important one. It requires two specific bytes (0x7F at offsets 5 and 6). A pure all-or-nothing check (byte5==0x7F && byte6==0x7F) gives the fuzzer no signal until both are right — a "coverage wall" that pure coverage feedback cannot climb, because no intermediate input is ever "interesting."

The target therefore emits a partial-progress edge e_nest_half when the first byte is correct. Now an input that gets byte 5 right becomes interesting and is retained; mutation can then complete byte 6. This is not a cheat — it is a faithful miniature of why real fuzzers add comparison instrumentation (AFL's CMP logging, libFuzzer's --use_cmp): they reward getting halfway through a multi-byte comparison so the search can climb byte by byte. The lab makes the wall, and the way over it, visible.

5. Crash Deduplication

A coverage-guided fuzzer finds the same bug through thousands of different inputs. Counting crashing inputs as bugs (a flagged Phase 08 mistake) wildly overstates the finding count. The fix: deduplicate by root-cause signature. This lab keys crashes by the CrashError signature, so no matter how many inputs trigger div-zero, it is one entry. The number of unique bugs is len(result.crashes) — here, at most 3.

6. Minimization (Delta Debugging)

A raw crashing input from a fuzzer is large and noisy. Minimization reduces it to the smallest input that still triggers the same signature, via delta debugging: try removing chunks (large, then progressively smaller), and keep a removal only if the crash signature is preserved. The minimized input is what becomes a crisp regression test (Phase 08 WARMUP, Chapter 9 — every fix ships with a regression built from the minimized crash). The lab's minimize reduces, e.g., a 40-byte div-zero crash to the 6-byte b"FUZZ\x02\x00".

7. Architecture of This Lab

seeds ──▶ fuzz(seeds, iterations, rng, guided)
              │   pick base → mutate → run_once → (coverage, signature)
              │      new signature?  → minimize → crashes[sig]
              │      guided & is_interesting? → frontier |= coverage; corpus.append
              ▼
        FuzzResult(corpus, edges, crashes, executions)

guided=False is an ablation: it never grows the corpus (always mutates the original seeds), modeling blind fuzzing — used to show that guidance reaches at least as many edges.

Everything is deterministic given a seeded random.Random, so the tests are stable.

8. Implementation Steps

Edit lab.py (the target, CrashError, run_once, and constants are provided):

1. mutate(data, rng) — one random mutation: bit-flip, set-interesting-byte, insert, or delete (keep ≥ 1 byte). The INTERESTING values include 0x7F, which is what lets the search reach BUG C.
2. is_interesting(coverage, frontier) — the one-liner: did this run reach a new edge?
3. minimize(crashing, signature) — delta-debug to the smallest input preserving the signature.
4. fuzz(...) — the loop: seed the corpus and frontier, then iterate (mutate a base, run, record + minimize new crashes, retain interesting inputs when guided). Return a FuzzResult.

9. Running and Expected Evidence

LAB_MODULE=solution pytest -q     # reference — all tests pass
pytest -q                          # your implementation

The suite proves the full pipeline: the target reports coverage and crashes; guided fuzzing finds all three seeded bugs within the iteration budget; thousands of crashes deduplicate to ≤ 3 signatures; each minimized crash still crashes with the same signature and is no longer than the seed; coverage guidance reaches ≥ the edges of blind fuzzing; and two runs with the same RNG seed are identical (determinism).

10. Mapping the Toy to Real Fuzzers

The lessons transfer directly: seed a real corpus with valid examples, add a dictionary for magic values, run coverage-guided with sanitizers, dedup by root cause, and minimize every crash into a regression.

11. Hardening / Stretch Tasks

• Add a dictionary of tokens (b"FUZZ", 0x7F) and a mutation that splices a dictionary entry — measure how much faster BUG C is found.
• Track per-edge hit counts (AFL buckets) so "reached this loop 8 times" is distinct from "once," and observe finer corpus growth.
• Add a fourth bug behind a checksum gate and show the fuzzer stalls until the harness recomputes the checksum — the classic harness fix for a coverage plateau.
• Implement corpus minimization (drop corpus entries whose coverage is subsumed) and report the minimal corpus.

12. Common Mistakes

• Counting crashing inputs as bugs. Dedup by signature; report unique bugs.
• Not retaining interesting inputs (writing a loop that always mutates the seed). That is blind fuzzing; coverage guidance is the corpus growth.
• Minimizing by removing only single bytes. Start with large chunks and shrink — far faster and reaches a smaller fixed point.
• A flaky / non-deterministic harness. Control the RNG and reset state, or crashes can't be reproduced or minimized (Phase 08 WARMUP, Chapter 4).
• "Coverage plateaued, run longer." Almost always a harness/corpus/structure problem (a gate the search can't pass) — not runtime.

13. Interview Questions

1. Explain coverage-guided fuzzing. Instrument the target for edge coverage; keep inputs that reach new edges in a corpus and breed from them, so mutation evolves inputs deeper into the program — a guided search, not random.
2. You found 4,000 crashes. How many bugs? Unknown until you deduplicate by root cause (stack hash / faulting site). Likely a handful; 4,000 is crashing inputs.
3. Why did coverage plateau at 40%? A gate the search can't pass: a multi-byte magic/checksum (needs comparison instrumentation or a dictionary, or recompute the checksum in the harness), a structure the mutator can't form (go structure-aware), a harness not reaching deep code, or a thin corpus — not "more runtime."
4. Why minimize a crash? It clarifies the root cause, removes noise, and produces a crisp, stable regression test that fails before the patch and passes after.
5. libFuzzer vs AFL++ — what's the same? Both are coverage-guided evolutionary fuzzers; the feedback loop (instrument → keep interesting → mutate → minimize) is identical. They differ in in-process vs fork model and mutation strategy, not in the core idea you built here.

14. Resume Bullet

Implemented a coverage-guided mutation fuzzer (libFuzzer/AFL++ model) in Python with edge-feedback corpus evolution, comparison-style partial-progress signals to climb multi-byte gates, root-cause crash deduplication, and delta-debugging minimization that turns crashes into regression tests.

15. References

• The Fuzzing Book (Zeller, Gopinathan, Böhme, Soremekun) — greybox/coverage-guided chapters.
• LLVM libFuzzer documentation; AFL++ documentation (instrumentation, CMP logging, afl-tmin).
• Michał Zalewski (lcamtuf), "American Fuzzy Lop" technical whitepaper.
• Andreas Zeller, "Delta Debugging" (minimization).
• Phase 08 WARMUP Chapters 2–7; Phase 01 WARMUP Chapter 12.