Coverage-Guided Fuzzing Internals: How AFL++ and libFuzzer Actually Work

Coverage-guided fuzzing finds more bugs than random fuzzing because it learns from execution. Each input that exercises new code paths is kept; inputs that don't are discarded. Over time, the fuzzer builds a corpus that covers increasingly deep program states.

Understanding how this works internally — instrumentation, coverage maps, the genetic algorithm — makes you a better fuzzer operator and helps you design more effective fuzz targets.

The Core Loop

All coverage-guided fuzzers implement the same fundamental loop:

1. Start with a seed corpus (initial inputs)
2. Pick an input from the corpus
3. Mutate it
4. Run the target with the mutated input
5. Check if the mutation exercised new code coverage
6. If yes: add the mutated input to the corpus
7. If the target crashed: save as a finding
8. Go to step 2

The key step is 5. Without coverage feedback, step 5 is always "no" and the fuzzer makes no progress beyond random mutation. With coverage feedback, the corpus grows to represent the program's reachable state space.

Instrumentation: How Coverage Is Measured

Coverage-guided fuzzers require instrumented binaries — binaries compiled with code that records which branches are executed.

Edge coverage (AFL-style)

AFL introduced a coverage model based on edges — transitions between basic blocks. For a branch like:

if (x > 0) {
    do_something();
} else {
    do_other();
}

AFL instruments the edges:

• Entry → true branch
• Entry → false branch
• True branch → continuation
• False branch → continuation

Each edge gets an ID. AFL maintains a 64KB coverage bitmap where each byte represents an edge. When an edge is taken, bitmap[edge_id]++.

The edge coverage model is important because it distinguishes which branches are taken, not just which lines are reached. A function that takes 10 different conditional paths generates 10 different edge tuples — each worth adding to the corpus.

Hit count bucketing

AFL doesn't just track whether an edge was taken — it tracks how many times. But it doesn't track exact counts. It uses bucketing:

• 1 hit
• 2 hits
• 3–4 hits
• 5–8 hits
• 9–16 hits
• 17–32 hits
• 33–128 hits
• 129+ hits

An input that takes an edge 2 times is considered "new coverage" compared to one that takes it 1 time, but an input that takes it 5 times vs. 4 times is not.

This bucketing finds bugs caused by repetition (buffer accumulation, counter overflows) without exploding the corpus with every input that changes hit counts.

SanitizerCoverage (libFuzzer-style)

libFuzzer uses LLVM's SanitizerCoverage (SanCov), which instruments at compile time:

clang -fsanitize=fuzzer,address target.c -o target_fuzz

The -fsanitize=fuzzer flag inserts callbacks at every edge. The fuzzer runtime collects these during execution and compares against the previous coverage set.

SanCov supports multiple coverage granularities:

• edge: per-edge coverage (most information)
• bb: basic block coverage (coarser)
• func: per-function coverage (coarsest, fast but misses branch selection)
• indirect-calls: tracks virtual call targets

For most targets, edge coverage provides the best signal-to-noise ratio.

Comparison coverage

Modern fuzzers add comparison coverage — tracking the values compared in equality and relational operators:

if (magic == 0xDEADBEEF)  // comparison coverage records: compared X vs 0xDEADBEEF

Without comparison coverage, the fuzzer must randomly mutate to hit magic numbers. With it, the fuzzer learns which magic bytes to try and can efficiently generate inputs that pass specific checks.

AFL++ implements this via cmplog mode. libFuzzer implements it natively. Both dramatically improve performance on targets with checksum validations, magic bytes, or complex input format parsers.

The Corpus: Inputs That Found New Coverage

The corpus is the fuzzer's memory. Each entry represents a unique coverage state discovered.

Corpus growth

A new input is added to the corpus when it produces a unique coverage tuple — a combination of (edge, hit_count_bucket) not seen before.

This creates a ratchet: coverage only grows. Once an edge is covered at a given hit count bucket, only inputs that cover new edges or new hit count buckets add to the corpus.

Corpus bloat

Naively managed corpora grow without bound. Every mutation that touches a new edge adds to the corpus. After millions of iterations, the corpus can contain hundreds of thousands of inputs.

Corpus bloat slows fuzzing because:

• Each cycle selects and mutates a corpus entry
• Larger corpora mean more entries to cycle through
• Many corpus entries are redundant (cover the same edges as simpler entries)

Corpus minimization

Minimize the corpus by finding the smallest set of inputs that covers all unique edges:

# AFL++ corpus minimization
afl-cmin -i corpus/ -o corpus_minimized/ -- ./target @@

# libFuzzer corpus minimization
./target_fuzz -merge=1 corpus_minimized/ corpus/

Minimization dramatically reduces corpus size without losing coverage. Run it periodically (weekly, or before sharing a corpus).

Corpus distillation

Beyond minimization, distillation reduces individual corpus entries to their minimal form — the smallest input that still triggers the same coverage:

# AFL++ input minimization (one file at a time)
afl-tmin -i seed.bin -o seed_min.bin -- ./target @@

# libFuzzer minimization
./target_fuzz -minimize_crash=1 -runs=100000 crash_input

Minimized inputs are easier to analyze, reproduce, and understand root causes.

The Genetic Algorithm: Mutation Strategies

Coverage-guided fuzzers use mutation-based input generation, not random generation. The mutations are chosen to maximize the probability of finding new coverage.

Havoc mode (AFL)

AFL's primary mutation strategy: havoc mode applies random combinations of mutations:

• Flip random bits
• Increment/decrement small integers
• Set bytes to interesting values (0x00, 0xFF, 0x7F, 0x80, integer boundaries)
• Insert/delete/replace blocks of bytes
• Splice two corpus inputs together

Havoc is powerful because of the combinatorial explosion. The mutations are individually simple but combined they navigate complex input spaces.

Deterministic mutations

AFL begins with deterministic mutations on high-priority corpus entries:

• Single-bit flips (every bit, sequentially)
• Byte flips
• Arithmetic increments/decrements
• Interesting value substitutions (known crash-causing integers)

Deterministic mutations are slower but systematic. They ensure obvious vulnerabilities (single off-by-one, single boundary value) are found early.

Structure-aware mutation (custom mutators)

For structured input formats (JSON, protobuf, HTTP), generic bit-flipping produces mostly syntactically invalid inputs that are rejected before reaching interesting code.

Custom mutators generate valid structure while fuzzing the semantics:

// AFL++ custom mutator
size_t afl_custom_fuzz(void *data, uint8_t **buf, size_t buf_size,
                       uint8_t **add_buf, size_t add_buf_size, size_t max_size) {
    // Parse current input as JSON
    // Mutate while preserving JSON syntax
    // Return mutated input
}

Custom mutators dramatically improve fuzzer effectiveness for targets with complex input formats. Without them, most mutations are discarded at the parser, never reaching the interesting logic.

Power Scheduling: Which Corpus Entry Gets Fuzzed Next?

Not all corpus entries are equal. Power scheduling determines how much fuzzing time each entry gets.

AFL's power schedule

AFL assigns a "fuzz score" to each corpus entry based on:

• Execution time: faster entries get more attempts (faster to iterate)
• File size: smaller inputs are preferred (likely more focused)
• Number of edges covered: inputs covering more edges are preferred
• Discovery time: recently discovered inputs get extra attention

Entries are selected proportional to their fuzz score. A fast, small, highly-covering entry gets 10x more fuzzing attempts than a slow, large, low-coverage entry.

AFL++ improvements

AFL++ added multiple power schedule variants, selectable with -p:

• fast (default): prioritizes less-fuzzed entries
• explore: balances new coverage vs. exploitation
• exploit: focuses on entries near found crashes
• coe (cut-off exponential): cuts off entries with diminishing returns
• rare: prioritizes entries in rarely-hit coverage buckets

No single schedule is universally best. fast works well for most targets. explore is better for targets where coverage is hard to find.

Why Coverage Guidance Finds Deep Bugs

The value proposition becomes clear at scale. Consider a function that parses a binary format:

Layer 1: Magic bytes check (4 bytes)
Layer 2: Version field (1 byte)
Layer 3: Length field (4 bytes)
Layer 4: Payload parser (variable)
Layer 5: CRC verification (4 bytes)

Random fuzzing probability of reaching Layer 4: (1/256)^5 ≈ 10^-12. Essentially never.

Coverage-guided fuzzing:

1. A random input accidentally gets magic bytes right → corpus entry
2. Mutation of that entry gets version right → corpus entry
3. Mutation gets length right → corpus entry
4. Mutants explore payload parser → coverage grows
5. Deep bugs in payload logic are found

Each "lucky" input that passes a check is preserved and mutated further. The corpus accumulates the successful partial solutions that naive random mutation would throw away.

AFL++ vs. libFuzzer: Internal Differences

Both are coverage-guided, but with architectural differences:

Fork-based (AFL++): Each test input runs in a new process. Crash isolation is automatic. State from one input can't contaminate the next. Slower due to fork overhead. Required for targets that maintain global state or aren't reentrant.

In-process (libFuzzer): The fuzz target function is called in a loop within the same process. Extremely fast. Required: the target must be stateless (or reset state between calls). A crash crashes the fuzzer process. Combined with AddressSanitizer, which aborts on memory errors, this is the standard pattern.

Measuring Fuzzer Effectiveness

Coverage over time

Track edge coverage over time. A healthy fuzzer shows coverage increasing rapidly at first, then leveling off. Plateau = you've covered the reachable code.

# AFL++ coverage stats
afl-showmap -o coverage.map -i corpus/ -- ./target @@
wc -l coverage.map  # number of covered edges

Code coverage reports

For deeper analysis, generate an LLVM coverage report:

llvm-profdata merge -sparse *.profraw -o coverage.profdata
llvm-cov show ./target -instr-profile=coverage.profdata

This shows which source lines are covered — useful for identifying what the fuzzer is missing.

Fuzzer bottlenecks

Low executions/second → usually: sanitizer overhead, I/O in the target, or fork overhead. Consider persistent mode for AFL++ or reducing sanitizer scope.

Coverage plateau with known uncovered code → usually: input format constraint (custom mutator needed), or coverage sink (target rejects inputs before reaching interesting code).

Corpus explosion → run afl-cmin or libFuzzer -merge=1. Bloated corpus slows cycling.

Summary

Coverage-guided fuzzing works because edge instrumentation + corpus management creates a directed search over the program's input space. The genetic algorithm (mutation + selection based on new coverage) navigates complex input spaces that random testing can't reach.

Understanding instrumentation models helps you choose the right coverage granularity. Understanding the corpus lifecycle helps you manage corpus quality. Understanding power scheduling helps you tune for your target.

The internals aren't just theoretical — they determine how effective your fuzzing campaign is and which knobs to turn when it stalls.