Coverage-guided fuzzing

Deep dive

How it works

Parts:

• corpus — queue of seed inputs, grown only by inputs that add coverage
• mutator — bit flips, arithmetic, insert/delete, splice of two entries, dictionary tokens; stacked
• instrumented target — compiler-inserted probes on every branch edge
• coverage map — fixed-size byte array of edge hit counts, cleared per exec
• virgin map — every (edge, count bucket) seen so far; decides "new"
• scheduler — picks the entry and its mutation budget ("energy")
• oracle — crash, assertion, timeout or sanitizer report

1. Run the seeds, record their coverage in the virgin map.
2. Pick an entry (power schedule), mutate it into a candidate.
3. Clear the map, run the target on the candidate.
4. Bucket each count (AFL: 1, 2, 3, 4-7, 8-15, 16-31, 32-127, 128+); if any edge-bucket pair is not in the virgin map, add it and keep the candidate.
5. If the oracle fires, save and deduplicate (AFL: a crash is unique if its trace has an edge no earlier crash had, or lacks one all had).
6. Minimise: drop entries whose coverage others cover (afl-cmin, libFuzzer -merge=1), shrink inputs (afl-tmin, -minimize_crash=1).

 seeds -> [corpus] -> pick -> [mutate] -> candidate
              ^                               |
              | new edge/bucket?              v
          [virgin map] <-- [coverage map] <-- [instrumented target] --> crash? --> triage

AFL's probe is map[cur ^ prev]++; prev = cur >> 1 with a random compile-time cur per block: the XOR makes the id an edge (A to B differs from B to A), the shift keeps loops distinct. LLVM SanitizerCoverage offers trace-pc-guard (callback per edge) and inline-8bit-counters (inline increment in a per-module array; libFuzzer logs "inline 8-bit counters"). -fsanitize=fuzzer also enables trace-cmp, whose compare operands feed the mutator. AFL++ CmpLog is the input-to-state idea (Redqueen): a second, CmpLog-built binary logs compared operands and the mutator writes the expected value into the input, solving memcmp(buf, "FUZZ!", 5) in one step.

Power schedules set energy. AFLFast models fuzzing as a Markov chain and favours inputs on rarely exercised paths (Böhme et al., CCS 2016). AFL++ offers explore (default), fast, coe, lin, quad, exploit, rare; libFuzzer logs an entropic schedule.

Execution: libFuzzer calls LLVMFuzzerTestOneInput(data, size) in-process (fastest; state leaks between runs, a crash ends the run). AFL forks from a stopped, initialised process (fork server, 1.5-2x faster than exec per its docs); AFL++ persistent mode loops in-process. cargo-fuzz wraps libFuzzer for Rust.

Structure-aware: byte mutation mostly breaks grammars and checksums. Use a custom mutator, decode bytes into typed values (Rust arbitrary), or mutate protobuf messages (libprotobuf-mutator) and serialise them.

Code

Std-only toy: manual probes, 64 KiB map, AFL buckets, fixed-seed xorshift mutator. Compiled and run (release): prints guided: crash after 102318 execs, corpus 5; the blind assert (2 M execs, no crash) passes.

use std::time::Instant;

const MAP: usize = 1 << 16; // 64 KiB hit map, like AFL's shared bitmap

struct Rng(u64); // xorshift64, fixed seed => reproducible runs
impl Rng {
    fn next(&mut self) -> u64 {
        let mut x = self.0;
        x ^= x << 13; x ^= x >> 7; x ^= x << 17;
        self.0 = x;
        x
    }
    fn below(&mut self, n: usize) -> usize { (self.next() % n as u64) as usize }
}

/// Edge recorder: AFL's `map[cur ^ prev]++; prev = cur >> 1`.
struct Cov { map: Vec<u8>, prev: usize }
impl Cov {
    fn edge(&mut self, id: usize) {
        let i = (id ^ self.prev) & (MAP - 1);
        self.map[i] = self.map[i].saturating_add(1);
        self.prev = id >> 1;
    }
}

/// Toy target with hand-placed probes; "crashes" on the 5-byte magic prefix.
fn target(d: &[u8], c: &mut Cov) -> bool {
    c.edge(1);
    for (i, &m) in b"FUZZ!".iter().enumerate() {
        if d.get(i) == Some(&m) { c.edge(10 + i) } else { c.edge(100 + i); return false; }
    }
    true
}

/// AFL hit-count buckets 1,2,3,4-7,8-15,16-31,32-127,128+ -> one bit each.
fn bucket(n: u8) -> u8 {
    match n { 0 => 0, 1 => 1, 2 => 2, 3 => 4, 4..=7 => 8, 8..=15 => 16, 16..=31 => 32, 32..=127 => 64, _ => 128 }
}

struct Fuzzer { corpus: Vec<Vec<u8>>, virgin: Vec<u8>, rng: Rng, cov: Cov }
impl Fuzzer {
    fn new(seed: &[u8]) -> Self {
        Fuzzer { corpus: vec![seed.to_vec()], virgin: vec![0; MAP], rng: Rng(0x9E3779B97F4A7C15), cov: Cov { map: vec![0; MAP], prev: 0 } }
    }
    /// Run once; returns (crashed, found_new_coverage).
    fn exec(&mut self, d: &[u8]) -> (bool, bool) {
        self.cov.map.fill(0); self.cov.prev = 0;
        let crash = target(d, &mut self.cov);
        let mut new = false;
        for (v, &h) in self.virgin.iter_mut().zip(&self.cov.map) {
            let b = bucket(h);
            if b & !*v != 0 { *v |= b; new = true; }
        }
        (crash, new)
    }
    fn mutate(&mut self) -> Vec<u8> {
        let mut d = self.corpus[self.rng.below(self.corpus.len())].clone();
        for _ in 0..1 + self.rng.below(4) { // stacked ("havoc") mutations
            let n = d.len();
            match self.rng.below(5) {
                0 if n > 0 => { let i = self.rng.below(n * 8); d[i / 8] ^= 1 << (i % 8) } // bit flip
                1 if n > 0 => { let i = self.rng.below(n); d[i] = self.rng.next() as u8 }  // random byte
                2 if n > 0 => { let i = self.rng.below(n); d[i] = d[i].wrapping_add(self.rng.below(35) as u8).wrapping_sub(17) } // arithmetic
                3 if n < 32 => { let i = self.rng.below(n + 1); d.insert(i, self.rng.next() as u8) }
                _ => { // splice: head of this input + tail of another corpus entry
                    let o = self.corpus[self.rng.below(self.corpus.len())].clone();
                    d.truncate(self.rng.below(n + 1)); d.extend_from_slice(&o[self.rng.below(o.len() + 1)..]);
                }
            }
        }
        d.truncate(64); d
    }
    fn fuzz(&mut self, budget: u64) -> Option<(Vec<u8>, u64)> {
        let seed = self.corpus[0].clone();
        self.exec(&seed);
        for n in 1..=budget {
            let d = self.mutate();
            let (crash, new) = self.exec(&d);
            if crash { return Some((d, n)); }
            if new { self.corpus.push(d); } // keep: it reached something new
        }
        None
    }
}

/// Blind baseline: random bytes, no feedback.
fn blind(budget: u64) -> Option<u64> {
    let (mut rng, mut c) = (Rng(0x2545F4914F6CDD1D), Cov { map: vec![0; MAP], prev: 0 });
    for n in 1..=budget {
        let d: Vec<u8> = (0..1 + rng.below(16)).map(|_| rng.next() as u8).collect();
        if target(&d, &mut c) { return Some(n); }
    }
    None
}

fn main() {
    const BUDGET: u64 = 2_000_000;
    let mut f = Fuzzer::new(b"AAAA");
    let t = Instant::now();
    let (input, n) = f.fuzz(BUDGET).expect("guided fuzzer must find the crash");
    assert!(input.starts_with(b"FUZZ!"));
    println!("guided: crash after {n} execs, corpus {}, {:.0} execs/s", f.corpus.len(), n as f64 / t.elapsed().as_secs_f64());
    assert_eq!(blind(BUDGET), None); // chance per exec about 2^-40
}

Complexity and constants

Probe: load, add, store, plus a prior-location update. Per exec: clear and scan the 64 KiB map, which dominates for tiny targets. Measured on my Mac (release, order of): guided 17,000 execs/s; blind loop 30-40 M/s (no map; target exits at byte 1). Memory: map plus corpus. Cost drivers: target time, process creation, map scan.

Efficiency

Cost: exec = target runtime + map clear and scan; CPU-bound, plus fork and page faults in fork modes. Toy: about 58 µs/exec, mostly the 64 KiB clear and scan (measured, order of). Levers:

• persistent or in-process mode — avoids exec and fork per input ("much, much faster" per AFL++ docs) — pure functions on bytes.
• fork server instead of exec — 1.5-2x (AFL technical_details) — when the target has slow start-up.
• word-wise map scan or sparse reset — attacks the scan share of the 58 µs (my toy) — short targets.
• corpus minimisation — fewer redundant seeds (afl-cmin, -merge=1) — before long campaigns. Naive → standard → state of the art:
• blind random bytes, new process per input · almost no depth, kernel-bound
• AFL: edge map, fork server, havoc and splice · far deeper coverage per CPU-second
• in-process or persistent, CmpLog or value profile, energy schedules, structure-aware mutators · highest depth per CPU-hour

Implementation notes

• Build with ASan/UBSan (MSan for uninitialised reads); a silent out-of-bounds read is otherwise invisible. See sanitizers.
• Seed with small valid files, add -dict= tokens, keep inputs short (-max_len).
• libFuzzer: -rss_limit_mb defaults to 2048; -use_value_profile defaults to 0.
• Keep targets deterministic (no clocks, threads, global state) or "new" flickers.
• Bypass checksums in the harness; keep each minimised crash as a regression test.

Pitfalls

• Map collisions grow with target size (AFL docs: about 7 % at 10,000 branches).
• Plateaus at a checksum, magic compare or length field: dictionary, CmpLog, harness bypass or structure-aware mutator.
• No oracle, no finding: crashes cover memory-safety bugs; logic bugs need differential or invariant checks (e.g. perft counts for a move generator).

Variants and alternatives

In production

• OSS-Fuzz: continuous fuzzing of open-source projects; its docs cite Google's guided in-process fuzzing of Chrome components.
• Rust crates (parsers, codecs, runtimes) with cargo fuzz; compilers, JS engines, media stacks, network daemons, TLS libraries; firmware parsers harnessed off-device.
• Pair with input validation at boundaries.

Implementations

Sources

• Böhme, Pham, Roychoudhury, Coverage-based Greybox Fuzzing as Markov Chain, ACM CCS 2016. paper
• AFL, technical details. doc · AFL++, fuzzing in depth. doc
• LLVM, libFuzzer. doc · SanitizerCoverage. doc
• Google, Structure-aware fuzzing. doc
• OSS-Fuzz. docs