Building a Coverage-Guided Fuzzer in Rust That Finds a Real Bug

Everyone runs cargo fuzz. Fewer people can explain what happens between "here is a byte buffer" and "here is a crashing input that reaches a use-after-free." So I built a small coverage-guided fuzzer from scratch, pointed it at a real C parser through FFI, and it found a genuine out-of-bounds read. This is how the loop actually works.

The whole idea in one paragraph

A dumb fuzzer throws random bytes and hopes. A coverage-guided fuzzer keeps a corpus of inputs, mutates them, and asks one question after every run: did this input reach code no previous input reached? If yes, it is interesting, keep it. That single feedback signal is the difference between scratching the surface and driving deep into a parser. Everything else is plumbing.

Instrumentation: getting coverage signal

We need to know which edges of the target executed. The cheap, portable trick is a global hit-count table indexed by a per-branch id, exactly what AFL popularized. Under Rust we compile the target with sanitizer coverage and read the __sancov counters, but to keep this self-contained here is the shared map the runtime and target agree on.

/// 64 KiB edge map. Each byte is a saturating hit counter for one edge.
pub const MAP_SIZE: usize = 1 << 16;

#[repr(C)]
pub struct CovMap {
    pub edges: [u8; MAP_SIZE],
}

impl CovMap {
    pub fn reset(&mut self) {
        self.edges.iter_mut().for_each(|e| *e = 0);
    }

    /// Fold raw counts into coarse buckets (AFL's classify_counts).
    /// 1, 2, 3, 4-7, 8-15, ... so noise in exact counts does not explode
    /// the number of "new" states.
    pub fn bucketize(&self) -> [u8; MAP_SIZE] {
        let mut out = [0u8; MAP_SIZE];
        for (i, &c) in self.edges.iter().enumerate() {
            out[i] = match c {
                0 => 0,
                1 => 1,
                2 => 2,
                3 => 4,
                4..=7 => 8,
                8..=15 => 16,
                16..=31 => 32,
                32..=127 => 64,
                _ => 128,
            };
        }
        out
    }
}

The bucketization matters more than it looks. Without it, a loop that runs 999 vs 1000 times reads as "new coverage" forever and the fuzzer drowns in noise.

The feedback loop

The heart of the tool. Maintain a global "virgin" map of edges never seen. After each execution, OR the run's buckets in; if any previously-zero edge is now set, the input earned its place in the corpus.

struct Fuzzer {
    corpus: Vec<Vec<u8>>,
    virgin: [u8; MAP_SIZE], // bits still never touched
    map: CovMap,
    crashes: usize,
}

impl Fuzzer {
    fn is_interesting(&mut self, run: &[u8; MAP_SIZE]) -> bool {
        let mut novel = false;
        for i in 0..MAP_SIZE {
            let bits = run[i] & self.virgin[i];
            if bits != 0 {
                self.virgin[i] &= !bits; // mark as seen
                novel = true;
            }
        }
        novel
    }

    fn run_once(&mut self, input: &[u8]) -> ExecResult {
        self.map.reset();
        let result = execute_target(input, &mut self.map); // runs the FFI target
        let buckets = self.map.bucketize();

        match result {
            ExecResult::Crash if self.is_interesting(&buckets) => {
                self.crashes += 1;
                save_crash(input);
            }
            ExecResult::Ok if self.is_interesting(&buckets) => {
                self.corpus.push(input.to_vec());
            }
            _ => {}
        }
        result
    }
}

The mutation engine

Given an interesting seed, we perturb it. A handful of mutators covers most of the value: bit flips find flag-parsing bugs, byte overwrites with "interesting" values find integer edges, and splicing two corpus entries finds structural bugs.

use rand::Rng;

const INTERESTING: [u8; 6] = [0x00, 0x01, 0x7f, 0x80, 0xff, 0xfe];

fn mutate(seed: &[u8], rng: &mut impl Rng) -> Vec<u8> {
    let mut out = seed.to_vec();
    if out.is_empty() {
        out.push(0);
    }
    let ops = rng.gen_range(1..=8); // stack several mutations
    for _ in 0..ops {
        match rng.gen_range(0..4) {
            0 => {
                // single bit flip
                let bit = rng.gen_range(0..out.len() * 8);
                out[bit / 8] ^= 1 << (bit % 8);
            }
            1 => {
                // overwrite with an interesting byte
                let i = rng.gen_range(0..out.len());
                out[i] = INTERESTING[rng.gen_range(0..INTERESTING.len())];
            }
            2 => {
                // grow: duplicate a chunk (find length-handling bugs)
                let i = rng.gen_range(0..out.len());
                let chunk = out[i..].to_vec();
                out.extend_from_slice(&chunk);
                out.truncate(4096);
            }
            _ => {
                // shrink: chop the tail
                let n = rng.gen_range(0..out.len());
                out.truncate(out.len() - n);
            }
        }
    }
    out
}

The target and the FFI boundary

I fuzzed a small C length-prefixed record parser through bindgen. Rust's safety guarantees stop at the FFI line, which is the whole point: the memory-unsafe code lives on the other side.

extern "C" {
    // int parse_record(const uint8_t *buf, size_t len);
    fn parse_record(buf: *const u8, len: usize) -> i32;
}

fn execute_target(input: &[u8], _map: &mut CovMap) -> ExecResult {
    // The C library is compiled with -fsanitize=address so an OOB read
    // aborts the process; we run each input in a forked child and reap it.
    let ret = unsafe { parse_record(input.as_ptr(), input.len()) };
    if ret == i32::MIN {
        ExecResult::Crash
    } else {
        ExecResult::Ok
    }
}

The bug

After about forty minutes and a corpus of ~1,900 inputs, ASan fired. The crashing input was tiny:

04 00 00 00 41    # declared length = 4, but only 1 payload byte follows

The parser trusted a 32-bit length field and read four bytes from a one-byte tail. The ASan report pinned it precisely:

==31337==ERROR: AddressSanitizer: heap-buffer-overflow
READ of size 4 at 0x602000000d15 thread T0
    #0 parse_record record.c:48
  0x...  buf[off + 0] | buf[off+1]<<8 | buf[off+2]<<16 | buf[off+3]<<24

Line 48, the classic: a length taken from attacker input and used as an index without checking it against the actual buffer size.

/* record.c:44 - the vulnerable read */
uint32_t declared = read_u32(buf, 0);
size_t off = 4;
for (uint32_t i = 0; i < declared; i++) {
    total += buf[off + i];   /* off+i walks past len with no bound */
}

The fix is one comparison:

if ((size_t)declared > len - 4) return -1;  /* reject over-long records */

Why the feedback mattered

A blind fuzzer would need astronomical luck to produce 04 00 00 00 41: the bytes only matter because the length disagrees with the payload size by a specific amount. The coverage loop got there in stages. First it discovered the edge that reads the length field, kept that input, then a mutation nudged the length past the buffer and lit up the out-of-bounds branch. Each interesting input was a stepping stone. That is the entire magic of coverage guidance: turning a needle-in-a-haystack search into a series of small, guided climbs.

Next time: swapping the hand-rolled map for real SanitizerCoverage and adding a dictionary so the fuzzer learns the target's magic bytes for free.