Coverage-Guided Fuzzing

• Describe fuzzing, its oracle (crash, hang, sanitizer report, assertion), and the progression from random to grammar-based to coverage-guided fuzzing.
• Explain the AFL feedback loop: edge-coverage instrumentation, a queue of interesting inputs, and mutation.
• Write a libFuzzer-style harness and explain what makes a harness good.
• Explain the role of sanitizers, the limits of fuzzing (magic values, checksums, deep state), and how fuzzing applies to memory-safe languages such as Java.

software-distributed/security-cryptography showed how memory-safety bugs and injection flaws become exploits, and algorithms-software/software-construction covered testing and debugging that start from inputs a person thought of. Fuzzing starts from the opposite premise: let the machine generate millions of inputs nobody thought of, and watch for failure. In 1990 Miller, Fredriksen, and So fed random bytes to common UNIX utilities and crashed or hung roughly a quarter to a third of them. Plain random input is shallow, though, because most random bytes are rejected by the first validation check and exercise only the error path.

The breakthrough came with coverage-guided fuzzing. AFL (American Fuzzy Lop, Michal Zalewski, 2013) and then libFuzzer, honggfuzz, and AFL++ add one idea: instrument the program, observe which code each input reaches, and keep any input that reaches something new as a seed for further mutation. This turns the search from guessing into hill climbing. Google's OSS-Fuzz runs these tools continuously over hundreds of open-source projects and has reported thousands of bugs, many of them security vulnerabilities in parsers for images, fonts, archives, and network protocols. Zeller et al.'s The Fuzzing Book is a free, runnable introduction.

The structure of a fuzzer

A fuzzer is a loop: produce an input, run the target on it, and check an oracle that says whether the run was a failure. For a generic fuzzer the oracle is "the program did not crash or hang", which sounds weak but becomes strong when combined with sanitizers: compiler instrumentation that turns silent memory corruption into an immediate, reportable crash. AddressSanitizer (ASan) detects out-of-bounds accesses and use after free, UndefinedBehaviorSanitizer (UBSan) detects overflow and invalid shifts, MemorySanitizer detects reads of uninitialized memory, and ThreadSanitizer detects data races. Custom assertions and property checks (for example, "decoding then encoding returns the original") extend the oracle.

Three generations

1. Black-box random: generate random bytes. Easy, but almost every input dies at the first check.
2. Grammar-based or structure-aware: generate or mutate inputs according to a grammar or format specification (the fuzzing of C compilers with Csmith, protocol fuzzers, protobuf-based mutators). The inputs pass the parser and reach deeper code, but someone has to write the grammar.
3. Coverage-guided greybox: use lightweight feedback from the program (greybox, between black-box and the whitebox reasoning of symbolic execution) to evolve a corpus.

The AFL loop

AFL instruments each basic block at compile time. Every block gets a random identifier, and the program updates a shared 64 KB bitmap at each control-flow edge: it increments bitmap[prev ^ cur] and sets prev = cur >> 1 (the shift keeps the edge A to B distinct from B to A). The hit counts are bucketed (1, 2, 3, 4 to 7, 8 to 15, and so on). The main loop is:

1. Take an input from the queue (initially the seed corpus supplied by the user).
2. Mutate it: deterministic stages (flip each bit, flip bytes, add or subtract small integers, insert "interesting" values like 0, -1, 255, 65535), then a random "havoc" stage stacking many mutations and a splice stage combining two inputs.
3. Run the mutant. If it reaches an edge or a hit-count bucket not seen before, add it to the queue. If it crashes, save it.
4. Repeat for hours or days.

A fork server avoids the cost of exec per run, and persistent mode reuses the process for many inputs. Corpus minimization tools (afl-cmin, afl-tmin) shrink the queue and each crash to a small reproducer.

libFuzzer follows the same idea in-process: the fuzzer is linked into the target and repeatedly calls a function you write, using LLVM's SanitizerCoverage for feedback, so each execution costs microseconds.

Writing a good harness

A harness is the function that feeds bytes to the code under test. In libFuzzer it is int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size). A good harness is:

• Deterministic: the same bytes always give the same behavior, with no hidden global state, clock, or randomness; otherwise coverage feedback is noisy and crashes do not reproduce.
• Fast: thousands of executions per second; avoid file system, network, and process creation.
• Narrow: it targets one parser or decoder at the boundary where untrusted data enters, rather than a whole program.
• Accompanied by a seed corpus and a dictionary (-dict=) of format keywords and magic numbers, which accelerates progress through format checks.

Limits

Coverage feedback cannot easily satisfy a condition like crc32(data) == header_crc or a 4-byte magic number checked by a single comparison, because partial progress is invisible: the branch is either taken or not. Mitigations include dictionaries, instrumenting comparisons so that matching bytes are noticed (laf-intel, CmpLog/RedQueen, libFuzzer's value profile), and hybrid tools that call a symbolic executor on stuck branches. Fuzzing also struggles with deep stateful protocols where many valid steps precede the bug, and it can never prove absence of bugs: a long run that finds nothing is evidence, not a guarantee.

Fuzzing memory-safe languages

In Java, Rust, or Go, out-of-bounds access throws an exception or panics rather than corrupting memory, but fuzzing is still valuable: it finds uncaught exceptions, infinite loops, excessive memory use (OutOfMemoryError), stack exhaustion on deeply nested input, and logic bugs surfaced by property checks (round trips, differential comparison of two implementations). Jazzer brings libFuzzer to the JVM, with extra detectors for injection patterns, and JQF combines coverage guidance with property-based testing. Fuzzing also pays off in Rust, in the unsafe parts and in panic-on-malformed-input behavior.

Example 1: why feedback beats guessing

Problem: How many executions does it take to reach the abort() below by pure random input, and by coverage-guided fuzzing?

plaintext
void check(const uint8_t *d, size_t n) {
    if (n >= 4 && d[0] == 'F')
        if (d[1] == 'U')
            if (d[2] == 'Z')
                if (d[3] == 'Z')
                    abort();
}

Solution: Blind random input must produce the four specific bytes at once: probability $2^{-32}$ per try, about 4 billion executions on average. A coverage-guided fuzzer finds F in the first byte after about $256$ tries of single-byte mutations; that input reaches a new edge (the second if), so it is saved. Mutating the saved input finds U in the second byte after about 256 more tries, and so on. Each stage costs on the order of $256$ attempts, so about $4 \times 256 \approx 1000$ executions in total plus mutation overhead, a reduction by a factor of millions. Feedback turns a conjunction of independent conditions from a product into a sum.

Example 2: a harness and a bug found by ASan

Problem: Find the bug in this parser with a fuzzer.

plaintext
// parser.c
#include <stdint.h>
#include <string.h>

int parse_record(const uint8_t *data, size_t size) {
    if (size < 1) return -1;
    uint8_t len = data[0];            // length byte comes from the input
    char buf[16];
    memcpy(buf, data + 1, len);       // trusts len: overflows when len > 16
    return buf[0];
}

// fuzz.c
#include <stdint.h>
#include <stddef.h>
int parse_record(const uint8_t *data, size_t size);

int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) {
    parse_record(data, size);
    return 0;
}

Build and run: clang -g -O1 -fsanitize=fuzzer,address parser.c fuzz.c -o fuzz && ./fuzz corpus/.

Solution: Within seconds the fuzzer finds an input whose first byte exceeds 16 and the following bytes are present. ASan reports a buffer overflow at the memcpy (a stack-buffer-overflow write, or a heap-buffer-overflow read when len also exceeds the input size), writes the input to a file crash-<hash>, and exits. Re-running ./fuzz crash-<hash> reproduces the failure deterministically, and -minimize_crash=1 shrinks it. The fix is if (len > sizeof buf || (size_t)len + 1 > size) return -1;. Without ASan the overflow could silently corrupt the stack and might not crash, which is why sanitizers are part of the setup.

Example 3: fuzzing a Java JSON parser

Problem: Write a Jazzer harness for Json.parse(String) that treats invalid JSON as normal and anything else as a bug.

java
public static void fuzzerTestOneInput(FuzzedDataProvider data) {
    String text = data.consumeRemainingAsString();
    Object value;
    try {
        value = Json.parse(text);
    } catch (JsonParseException expected) {
        return;                              // malformed input is fine
    }
    // property: printing then parsing gives the same value back
    if (!value.equals(Json.parse(Json.print(value)))) {
        throw new AssertionError("round trip changed " + value);
    }
}

Solution: The catch documents the contract: JsonParseException is the parser's declared reaction to bad input. Any other throwable that escapes (NullPointerException, StackOverflowError from deeply nested arrays, OutOfMemoryError from a pathological length, a ClassCastException) is reported with the input that caused it. The round-trip property turns a crash-only oracle into a correctness oracle, and finds bugs such as number formatting that loses precision or Unicode escapes handled inconsistently.

• "Fuzzing is for C and C++ only." Memory corruption is the classic target, but any language benefits for uncaught exceptions, resource exhaustion, and property violations.
• "Higher coverage means a better fuzzing campaign." Coverage is a means. A fuzzer can saturate edge coverage and still miss a bug that depends on a particular value or state; the oracle (sanitizers, assertions, properties) decides what is detectable.
• "A fuzzer that has run for an hour without a crash shows the code is safe." It shows the explored part of the input space is clean. Campaigns should run continuously (OSS-Fuzz, CI fuzzing on every change), starting from a corpus that keeps growing.
• "Fuzzing replaces unit tests." It finds what no one anticipated, but it cannot tell whether a correct-looking output is the right one. Use both: fuzz for robustness, tests and properties for behavior.

A fuzzer generates inputs, runs the target, and checks an oracle, strengthened by sanitizers that turn memory corruption into crashes. Coverage-guided fuzzers such as AFL and libFuzzer instrument edges, keep every input that reaches new code, and mutate from that corpus, which changes the search for a conjunction of conditions from exponential to roughly linear. A good harness is deterministic, fast, and narrow, with a seed corpus and a dictionary. Magic values, checksums, and deep state remain hard, and hybrid approaches with symbolic execution address some of them. In memory-safe languages, fuzzing finds exceptions, resource exhaustion, and violated properties. The next concept looks at the tooling that surrounds all these analyses in daily work: how editors talk to language-aware analysis through language servers, and how that analysis stays fast.