How Does Coverage-Guided Fuzzing Find Memory Corruption Bugs?

Coverage-guided fuzz testing automatically discovers memory corruption bugs by generating mutated inputs, executing the target program, and tracking which code paths each input reaches. When an input triggers new code coverage, the fuzzer saves it to a corpus and uses it as a seed for further mutations. By repeating this feedback loop thousands of times per second, the fuzzer systematically explores deep, hard-to-reach execution paths where buffer overflows, use-after-free errors, and other memory safety flaws often hide.

The Core Feedback Loop

Traditional black-box fuzzers send random or malformed data to a program without knowing how the program processes it. Because most random inputs fail early at basic syntax or header checks, black-box fuzzing rarely reaches deeper application logic.

Coverage-guided fuzzing (also called grey-box fuzzing) solves this by instrumenting the target program at compile time or through binary translation. Instrumentation inserts lightweight tracking code at every basic block or branch edge. As the fuzzer feeds an input to the program, it records a coverage map—often a compact bitmap where each byte represents a specific control-flow edge.

The feedback loop follows four main steps:

  1. Seed Selection: The fuzzer picks an existing input from its corpus (initially provided by the user or a minimal valid file).
  2. Mutation: The fuzzer applies random or structured changes to the seed, such as flipping bits, inserting bytes, deleting chunks, or splicing two seeds together.
  3. Execution and Tracking: The instrumented program runs with the mutated input while the fuzzer monitors both the coverage bitmap and any crash signals.
  4. Corpus Update: If the input executes a previously unseen branch or increases the hit count of an edge into a new bucket, the fuzzer adds it to the corpus as a new seed.

Over time, this evolutionary process naturally steers execution toward complex state machines, nested conditionals, and rare error-handling routines.

Detecting Memory Corruption with Sanitizers

A memory corruption bug does not always cause an immediate crash. For example, a small out-of-bounds write might silently overwrite an adjacent variable without triggering a segmentation fault. To catch these subtle bugs, coverage-guided fuzzers are typically paired with runtime sanitizers.

  • AddressSanitizer (ASan): Places "redzones" (poisoned memory) around stack, heap, and global buffers, and tracks freed heap memory. Any out-of-bounds access or use-after-free immediately aborts the program with a detailed report.
  • UndefinedBehaviorSanitizer (UBSan): Detects signed integer overflows, null pointer dereferences, and misaligned memory accesses that often precede memory corruption.
  • MemorySanitizer (MSan): Tracks uninitialized memory reads, which can lead to unpredictable behavior or information leaks.

When a sanitizer or the operating system raises a fatal signal (such as SIGSEGV or SIGABRT), the fuzzer saves the exact triggering input to a dedicated crashes directory for developer triage.

Overcoming Hard-to-Reach Branches

Even with coverage feedback, certain conditions can stall a fuzzer. A common example is a multi-byte magic value check, such as if (header == 0xDEADBEEF). The probability of guessing a 32-bit value through random bit flips is \(2^{-32}\), which is practically zero without assistance.

Modern fuzzers use several techniques to bypass these roadblocks:

  • Comparison Splitting: Instrumentation breaks multi-byte comparisons into single-byte checks, allowing the fuzzer to see partial progress and solve the value one byte at a time.
  • Dictionaries: Developers can supply a list of known keywords, magic bytes, or protocol tokens that the fuzzer injects directly during mutation.
  • Structure-Aware Mutation: Custom mutators understand the grammar or format of the input (such as JSON, XML, or a binary protocol), ensuring mutations remain syntactically valid enough to pass initial parsers.
  • Taint Analysis and Symbolic Execution: Hybrid fuzzers use lightweight taint tracking or constraint solvers (like SMT solvers) to mathematically solve complex branch conditions when random mutations get stuck.

Why It Excels at Finding Edge Cases

Memory corruption bugs frequently arise from unexpected combinations of state, length fields, and boundary conditions—such as an integer overflow in a size calculation followed by a heap allocation. Human-written unit tests tend to focus on expected behavior and known edge cases, leaving obscure interactions untested.

Because coverage-guided fuzzers treat every newly discovered branch as a stepping stone, they excel at chaining together unlikely sequences of inputs. Once an input unlocks a new parsing state, subsequent mutations explore variations within that state, steadily uncovering the exact edge cases that violate memory safety.