Skip to main content
Be Bitwise

Coverage-Guided Fuzzing Deep Dive

Advanced Fuzzing Techniques · VR Analysis & Discovery track

8 min read

In this module

Inside the Coverage-Guided Fuzzer

You've encountered fuzzing before as a technique for finding crashes. This lesson goes deep into how modern coverage-guided fuzzers actually work — the algorithms, data structures, and engineering decisions that make AFL++ and libFuzzer so effective at finding vulnerabilities without a human in the loop.

The AFL++ Architecture

AFL++ (American Fuzzy Lop plus plus) is the most widely-used coverage-guided fuzzer. Its architecture has several key components:

The fork server - instead of launching a new process for each test case (expensive: fork + exec + library loading), AFL++ starts the target once and then forks from a persistent "fork server" process. The child inherits the parent's fully-initialised state, skipping all startup overhead. This is the single biggest performance optimisation in AFL.

text
AFL++ main loop:
1. Select an input from the corpus
2. Mutate the input
3. Send it to the fork server
4. Fork server: fork() -> child runs with mutated input
5. Child executes, coverage bitmap is updated via shared memory
6. Parent collects exit status and reads coverage bitmap
7. If new coverage found: save input to corpus
8. Repeat

The shared memory bitmap - AFL++ uses a 64KB shared memory region as a coverage map. Each byte in the bitmap corresponds to a specific edge (transition from one basic block to another). When the instrumented program executes an edge, it increments the corresponding byte:

c
// AFL++ instrumentation (inserted by the compiler)
// cur_location is a compile-time random ID for each basic block
cur_location = RANDOM_COMPILE_TIME_ID;
shared_mem[cur_location ^ prev_location]++;
prev_location = cur_location >> 1;

The XOR of current and previous location IDs creates a unique identifier for each edge (A->B produces a different hash than B->A, and A->A). The right-shift on prev_location ensures that A->B->A produces different coverage than A->A.

Here's the arithmetic on a path A -> B -> C, with block IDs made up for the example (A = 0x1A2B, B = 0x3C4D, C = 0x0F0E) and prev_location starting at 0. Check one XOR by hand, then look at the last box: a different edge, E -> F, lands on the same bitmap byte as A -> B. That's a collision, and the fuzzer can't tell the two edges apart.

Edge coverage vs. basic block coverage - AFL++ tracks edges (transitions between blocks), not just which blocks execute. This is important because a function might contain a security check that always passes with normal inputs. Edge coverage detects when an input causes the check to fail (a new edge from the check block to the error handler), even though both blocks have been seen before individually.

Why 64KB?

The bitmap is 64KB because this provides a good tradeoff between collision rate and cache performance. With ~65000 possible edge IDs, a program with a few thousand edges will have occasional collisions (two different edges mapping to the same byte), causing the fuzzer to occasionally miss new coverage. Larger bitmaps reduce collisions but hurt cache performance. In practice, 64KB works well for most targets.

Mutation Strategies

AFL++ generates new test cases by mutating existing corpus entries. It employs several mutation strategies, applied in sequence:

Deterministic mutations (applied once to each new corpus entry):

  • Bit flips - flip 1, 2, 4 bits at every position
  • Byte flips - flip 1, 2, 4 bytes at every position
  • Arithmetic - add/subtract small integers to each byte, word, and dword
  • Known interesting values - insert values like 0, 1, -1, 255, 256, 0x7FFFFFFF, 0x80000000 at each position
  • Dictionary tokens - insert user-provided or auto-detected tokens

Havoc mode (random stacking of multiple mutations):

  • Random bit/byte flips
  • Random arithmetic on random positions
  • Random block deletion, insertion, or overwrite
  • Splicing: combine parts of two different corpus entries

Splicing - take two corpus entries and create a new input by combining the first part of one with the second part of another. This is especially effective for structured inputs where different parts independently influence different code paths.

Compile-Time vs. Binary Instrumentation

AFL++ can instrument targets in two ways:

Compile-time instrumentation - by compiling the target with afl-cc (AFL++'s compiler wrapper), instrumentation is inserted during compilation. This produces the fastest instrumented binary:

bash
# Compile with AFL++ instrumentation
CC=afl-cc CXX=afl-c++ ./configure
make -j$(nproc)
# Or directly:
afl-cc -o target target.c

Binary instrumentation - for closed-source targets where source is unavailable, AFL++ supports several binary instrumentation modes:

  • QEMU mode (-Q): uses QEMU user-mode emulation to instrument at runtime. 2-5x slower than compile-time.
  • Unicorn mode (-U): emulates specific code sections using Unicorn engine
  • Frida mode (-O): uses Frida for dynamic instrumentation. Good for complex binaries.
bash
# Fuzz a closed-source binary with QEMU mode
afl-fuzz -Q -i corpus/ -o output/ -- ./closed_source_target @@

Persistent Mode

Persistent mode eliminates the fork overhead entirely by calling the target function in a loop within the same process:

c
// Persistent mode harness
#include <unistd.h>
__AFL_FUZZ_INIT();
int main(int argc, char *argv[]) {
__AFL_INIT();
unsigned char *buf = __AFL_FUZZ_TESTCASE_BUF;
while (__AFL_LOOP(10000)) {
int len = __AFL_FUZZ_TESTCASE_LEN;
// Call target function directly
parse_input(buf, len);
}
return 0;
}

The __AFL_LOOP macro creates a loop that receives new test cases from AFL++ via shared memory, avoiding both fork and file I/O overhead. This can increase throughput from thousands to hundreds of thousands of executions per second.

The requirement is that the target function must not have persistent state that affects subsequent calls - or you must manually reset that state in the loop.

Dictionaries and Power Schedules

Dictionaries provide the fuzzer with format-specific tokens:

text
# pdf.dict - dictionary for fuzzing PDF parsers
"PDF-"
"%%EOF"
"/Type"
"/Page"
"stream"
"endstream"
"endobj"
"xref"
"trailer"

With a dictionary, AFL++ inserts these tokens during mutation, dramatically improving its ability to generate syntactically meaningful inputs for the target format.

Power schedules determine how much fuzzing time is spent on each corpus entry. AFL++'s default schedules prioritise inputs that:

  • Execute faster (more executions per second = more mutations explored)
  • Were discovered more recently (newer entries may be exploring new territory)
  • Have produced more new coverage when mutated (productive entries deserve more attention)

The rare schedule goes further and pours energy into inputs that hit rarely-seen edges, which often correspond to error handling or edge cases where vulnerabilities lurk. exploit, by contrast, is the original AFL behaviour, which keeps hammering the entries it already likes.

bash
# Use the 'rare' power schedule
afl-fuzz -p rare -i corpus/ -o output/ -- ./target @@
# Run a parallel campaign: one main (-M), named secondaries (-S), one shared -o
afl-fuzz -M main -p explore -i corpus/ -o output/ -- ./target @@ &
afl-fuzz -S s1 -p fast -i corpus/ -o output/ -- ./target @@ &
afl-fuzz -S s2 -p rare -i corpus/ -o output/ -- ./target @@ &

Running multiple AFL++ instances with different power schedules creates a campaign where each instance explores a different slice of the input space. Because they all write under the same -o directory, each instance periodically imports the others' queue entries, so a find in one becomes a starting point for all of them. The instances make each other better.

CmpLog deals with a problem neither dictionaries nor schedules fix: a check like if (magic == 0x7f454c46) that random mutation will essentially never satisfy. You build a second copy of the target with AFL_LLVM_CMPLOG=1 and hand it to afl-fuzz with -c. That binary logs the operands of comparisons as they run, and AFL++ splices the values it sees back into the input at the spot they came from (the input-to-state idea from the REDQUEEN paper). Magic numbers and tags compared against constants stop being walls.

bash
# Build a CmpLog copy alongside the normal one
AFL_LLVM_CMPLOG=1 afl-cc -o target.cmplog target.c
afl-fuzz -c ./target.cmplog -i corpus/ -o output/ -- ./target @@