Fuzzing: Let Machines Find Crashes for You

This article has three layers:

1. Layer 1: The Intuition: Letting ten thousand monkeys press keys randomly, but only rewarding the monkeys that find new rooms.
2. Layer 2: Real-World Use: AFL, OSS-Fuzz, Heartbleed, smart contract invariant testing, AI assistance.
3. Layer 3: Principles and Engineering details.

Layer 1: The Intuition

1.1 Ten thousand monkeys, only rewarding those who find new rooms

Imagine a labyrinthine building where some rooms contain bombs (bugs). You send ten thousand monkeys inside to run around randomly:

• Pure Random: Most monkeys wander around the entrance and rarely reach the depths;
• Coverage-guided: Whenever a monkey enters a room that has never been visited before, its route is recorded; subsequent monkeys start from these routes and take a few more random steps.

In this way, the scope of exploration goes deeper and deeper, eventually reaching corners that human testers could never imagine.

1.2 What it excels at finding

It is particularly good at testing code that parses untrusted input: file formats, network protocols, compression, image decoding, regex engines.

Layer 2: Real-World Use

• AFL (2013): American Fuzzy Lop, released by Michał Zalewski, pioneered practical coverage-guided fuzzing and discovered vulnerabilities in many well-known software packages. This was followed by libFuzzer, AFL++, honggfuzz, and others.
• Heartbleed (2014): This critical OpenSSL vulnerability was discovered independently by two groups, one of which (Codenomicon) was using its own fuzzing tools while testing an SSL implementation.
• OSS-Fuzz (since 2016): A free continuous fuzzing service provided by Google for critical open-source projects. As of 2023, it has helped discover and fix over ten thousand security vulnerabilities and tens of thousands of other bugs in over a thousand projects.
• Smart Contracts: Tools like Foundry and Echidna perform "invariant fuzzing" on contracts: generating random sequences of calls to check if properties like "assets $\ge$ liabilities" always hold true (see Contract Auditing and Formal Verification).
• AI Assistance: In recent years, Large Language Models have begun to be used to automatically write fuzzing entry points, analyze crashes, and even directly search for vulnerabilities. In 2024, Google reported that its AI agent discovered a previously unknown exploitable vulnerability in SQLite.

Layer 3: Principles and Engineering

3.1 The coverage-guided loop

Lightweight "probes" are inserted during compilation to record which branches the program traverses. An input is considered "interesting" and added to the corpus if it triggers a new combination of branches.

3.2 Writing a test entry point

Fuzzing requires an "entry function": it receives an arbitrary byte sequence and feeds it to the code under test. Taking the libFuzzer style as an example:

int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) {
    parse_my_format(data, size);   // Function under test: must not crash and must not violate assertions
    return 0;
}

A good entry point should be:

• Fast: Able to run thousands of times per second;
• Deterministic: The same input always produces the same result;
• Focused: Only tests a single parser or a single module.

One can also add property checks, such as "parsing and then re-serializing should yield the same content" (round-trip testing), or "the output of two implementations must be identical" (differential testing, see Multi-source Cross-validation).

3.3 Sanitizers

Many memory errors do not cause immediate crashes but instead silently corrupt data. Enabling sanitizers during compilation allows these issues to be caught the moment they occur:

3.4 Seed Corpus

Starting from some valid sample inputs (such as a few normal image files or a few normal protocol messages) is much more efficient than starting from nothing. The corpus should be continuously preserved as part of regression testing.

3.5 Relationship with other testing methods

Fuzzing is best suited for continuous execution: integrated into CI to run for a period during every code change, or running 24/7 like OSS-Fuzz.

Summary