Coverage-guided fuzzing and generation-based fuzzing are two powerful approaches to fuzzing. It can be tempting to think that you must either use one approach or the other at a time, and that they can’t be combined. However, this is not the case. In this blog post I’ll describe a method for combining coverage-guided fuzzing with structure-aware generators that I’ve found to be both effective and practical.
What is Generation-Based Fuzzing?
Generation-based fuzzing leverages a generator to create random instances of
the fuzz target’s input type. The
csmith program, which generates
random C source text, is one example generator. Another example is any
implementation of the
Arbitrary trait from the
property-testing framework. The fuzzing engine repeatedly uses the generator to
create new inputs and feeds them into the fuzz target.
The generator can be made structure aware, leveraging knowledge about the fuzz target to generate inputs that are more likely to be interesting. They can generate valid C programs for fuzzing a C compiler. They can make inputs with the correct checksums and length prefixes. They can create instances of typed structures in memory, not just byte buffers or strings. But naïve generation-based fuzzing can’t learn from the fuzz target’s execution to evolve its inputs. The generator starts from square one each time it is invoked.
What is Coverage-Guided Fuzzing?
Rather than throwing purely random inputs at the fuzz target, coverage-guided fuzzers instrument the fuzz target to collect code coverage. The fuzzer then leverages this coverage information as feedback to mutate existing inputs into new ones, and tries to maximize the amount of code covered by the total input corpus. Two popular coverage-guided fuzzers are libFuzzer and AFL.
The coverage-guided approach is great at improving a fuzzer’s efficiency at creating new inputs that poke at new parts of the program, rather than testing the same code paths repeatedly. However, in its naïve form, it is easily tripped up by the presence of things like checksums in the input format: mutating a byte here means that a checksum elsewhere must be updated as well, or else execution will never proceed beyond validating the checksum to reach more interesting parts of the program.
Coverage-based fuzzing lacks a generator’s understanding of which inputs are well-formed, while generation-based fuzzing lacks coverage-guided fuzzing’s ability to mutate inputs strategically. We would like to combine coverage-guided and generation-based fuzzing to get the benefits of both without the weaknesses of either.
So how do we implement a fuzz target?
When writing a fuzz target for use with coverage-guided fuzzers, you’re typically given some byte buffer, and you feed that into your parser or process it in whatever way is relevant.
However, when writing a fuzz target for use with a generation-based fuzzer, instead of getting a byte buffer, you’re given a structure-aware input that was created by your generator.
The signatures for coverage-guided and generation-based fuzz targets have different input types, and it isn’t obvious how we can reuse a single fuzz target with each approach to fuzzing separately, let alone combine both approaches at the same time.
As a running example, let’s imagine we are authoring a crate that converts back and forth between RGB and HSL colors.
Now, let’s start by writing a couple structure-aware test case generators by
quickcheck::Arbitrary for our color types, and then using
quickcheck’s default test runner to get generation-based fuzzing up and
Here are our
Now we need to define what kinds of properties we want to check and what oracles we want to implement to check those properties for us. One of the simplest thigns we can assert is “doing operation X does not panic or crash”, but we might also assert that converting RGB into HSL and back into RGB again is the identity function.
Now we can run
cargo test and
quickcheck will do some generation-based
fuzzing for our RGB and HSL conversion crate — great!
However, so far we have just done plain old generation-based fuzzing. We also want to get the advantages of coverage-guided fuzzing without giving up our nice structure-aware generators.
An easy and practical — yet still effective — way to add coverage-guided fuzzing into the mix, is to treat the raw byte buffer input provided by the coverage-guided fuzzer as a sequence of random values and implement a “random” number generator around it. If our generators only use “random” values from this RNG, never from any other source, then the coverage-guided fuzzer can mutate and evolve its inputs to directly control the structure-aware fuzzer and its generated test cases!
BufRng type from my
bufrng crate is exactly this “random”
number generator implementation:
BufRng will generate “random” values, which are copied from its given
buffer. Once the buffer is exhausted, it will keep yielding zero.
Because there is a blanket implementation of
quickcheck::Gen for all types
rand_core::RngCore, we can use
BufRng with any
Finally, here is a fuzz target definition for a coverage-guided fuzzer that uses
BufRng to reinterpret the input into something that our
implementations can use:
BufRng, going from
quickcheck property tests to combined
structure-aware test case generation and coverage-guided fuzzing only required
We can get the benefits of both structure-aware test case generators and
coverage-guided fuzzing in an easy, practical way by interpreting the fuzzer’s
raw input as a sequence of random values that our generator uses. Because
BufRng can be used with
quickcheck::Arbitrary implementations directly, it
is easy to make the leap from generation-based fuzzing with
property tests to structure-aware, coverage-guided fuzzing with libFuzzer or
AFL. With this setup, the fuzzer can both learn from program execution feedback
to create new inputs that are more effective, and it can avoid checksum-style
If you’d like to learn more, check out these resources:
Structure-Aware Fuzzing with libFuzzer. A great tutorial describing a few different ways to do exactly what it says on the tin.
Write Fuzzable Code by John Regehr. A nice collection of things you can do to make your code easier to fuzz and get the most out of your fuzzing.
cargo fuzz. A tool that makes using libFuzzer with Rust a breeze.
quickcheck. A port of the popular property-testing framework to Rust.
bufrng. A “random” number generator that yields pre-determined values from a buffer (e.g. the raw input generated by libFuzzer or AFL).