Introduction

Fuzzcheck is a crate to easily find bugs in Rust code. Given a test function:

fn test_always_true(x: SomeType) -> bool {
    // ...
}

You can use fuzzcheck to find a value x: SomeType that causes test_always_true(x) to return false or crash 💥.

Technically, it is called an evolutionary, structure-aware fuzzing engine. It is coverage-guided by default, but can also use other observations to guide the evolution of the fuzz test.

Goal 🦄

Fuzzcheck’s goal is to be used as part of your development routine. You can quickly test small or complex function with it. It can find difficult corner-case bugs, minify complex test cases into easy-to-debug ones. It can find stack overflows and inputs that cause excessive computations or allocations.

Over time, by using fuzzcheck, you can automatically build a large corpus of values that trigger most edge cases in your code. This will help ensure that no new bugs are introduced when refactoring.

Requirements 🎟

Currently, it is only possible to use fuzzcheck on Linux and macOS. I'd like to add Windows support to it, and it shouldn't be complicated, but I need some help with it.

You also need a nightly version of the Rust compiler. This requirement is unlikely to change soon.

Design ⚙️

Fuzzcheck works by repeatedly running the test function test_always_true(x) with automatically generated values for x. For each invocation of test_always_true(x), it gathers observations about the code that was run and determines whether new observations were discovered. This enables it to build a list of values that are known to be interesting to test, which we call the “pool of interesting values”.

Then, fuzzcheck repeatedly draws values from that pool, slightly mutates them, and then feeds them to test_always_true again. It continues this process indefinitely, analysing the observations (e.g. code coverage) triggered by each test case in order to discover more and more interesting values to test.

Thus, fuzzcheck is composed of three components working together:

• a Mutator<T>, which can generate arbitrary values of type T, either from scratch or starting from a known interesting value.
• a Sensor, whose role is to gather observations about the execution of a test function. By default, this uses the code coverage information generated by the -C instrument-coverage option of the Rust compiler. But different kinds of observations can be used.
• a Pool, which listens to the observations from the Sensor and determines which values are interesting to test. It internally ranks the different values that were tested and ensures that the most interesting ones are mutated and re-tested more often.

In pseudo-code:

loop {
    let value = pool.get_mut();
    mutator.mutate(value);
    let observations = sensor.record(|| {
        test_function(value);
    });
    if pool.is_interesting(value, observations) {
        pool.add(value, observations);
    }
}

Example 👀

We can illustrate fuzzcheck’s strengths with a simple but unrealistic example. What follows are not instructions to use fuzzcheck (these start from the next section), but rather an example showing how fuzzcheck is different from other testing tools such as quickcheck or proptest. Imagine we have the following function:

fn this_should_always_succeed(xs: &[u8]) -> bool {
    if xs.len() >= 4 && xs[0] == 96 && xs[1] == 1 && xs[2] < 78 && xs[3] == 189 {
        false
    } else {
        true
    }
}

We can find a vector of bytes that makes the function fail by running the following test:

#[cfg(test)]
mod tests {
    #[test]
    fn fuzz_test() {
        let result = fuzzcheck::fuzz_test(super::this_should_always_succeed)
            .default_options()
            .stop_after_first_test_failure(true)
            .launch();
        assert!(!result.found_test_failure);
    }
}

We run:

cargo fuzzcheck tests::fuzz_test

which launches the fuzz test on the library target. Fuzzcheck progressively finds values which satisfy each condition inside fn this_should_always_succeed until, after about 2000 iterations, it prints:

Failing test case found. 
Saving at "fuzz/artifacts/tests::fuzz_test/642e66bf463956ed.json"

It found the bug and serialized the failing test case to the file 42e66bf463956ed.json, which contains:

[96,1,24,189]

The time to find this bug, on my machine, was 12 milliseconds.

While this was a simplistic example, the same process can be used for large functions that take very complex input types as arguments. However, note that the test function should run fairly fast, ideally in less than a tenth of a millisecond.

Getting Started

Prerequisites

First, remember that you need to run either Linux or macOS, as Windows is not yet supported.

Fuzzcheck comes with a helper tool that helps you pass the right flags to compile fuzz targets. It is recommended to use it. To install it, run:

cargo install cargo-fuzzcheck

It is also necessary to use Rust nightly. You can install it using rustup:

rustup install nightly

What type of function can I fuzz-test?

1) Pure, fast functions

It is best if the tested function is “pure”, meaning that it behaves in exactly the same way every time it is called with the same input. It is also best if the tested function runs very fast, ideally in less than a tenth of a millisecond. This is because fuzzcheck often needs hundreds of thousands of iterations to build a corpus of interesting test cases.

Functions that perform file or network operations may have unpredictable behaviour or take too long to run and are thus not a great fit for fuzz-testing.

Note also that the tested function takes an immutable reference as argument. It is important that it does not mutate its argument through types such as Cell, RefCell, or UnsafeCell.

2) No dependence on information that is lost when cloning

Furthermore, be aware that some types lose information when serialised or cloned. This is the case for Vec<T> and its capacity property. If the tested function changes its behaviour based on these kinds of properties, fuzzcheck will be less useful. For a concrete example, imagine that the tested function is:

#![allow(unused)]
fn main() {
fn test_vector_capacity(v: &Vec<T>) -> bool {
	v.capacity < 10
}
}

Then an empty vector with a capacity of 12 would fail the test. But fuzzcheck will save this failing test case as:

[]

And when the test case is deserialised, the resulting vector may have a capacity of 0, and thus will not fail the test anymore.

Problems also arise when the tested function makes internal decisions based on capacity:

#![allow(unused)]
fn main() {
fn test_vector(v: &Vec<T>) -> bool {
	if v.capacity < 10 {
		// do something
	} else {
		// do something else
	}
}
}

Now the problem is more subtle. Imagine that test_vector is called on an empty vector with capacity 12. Then the second branch will be taken and fuzzcheck may judge that the test case is interesting because it explored a previously uncovered code region. The test case is thus saved to the internal pool by cloning. But cloning does not preserve the capacity property. The vector that is saved in fuzzcheck’s pool is an “impostor” in some sense. This may stall the fuzzer’s progress.

Getting Started

To learn how to use fuzzcheck, go to the quick start section or follow one of the tutorials:

• Tutorial 1 sets up a differential property test between a binary search tree and std::collections::BTreeSet. Through it, you can learn about the different parts of the fuzzer and learn to interpret the files generated by it. No bug is directly found in this tutorial, but we guess a potential stack overflow by looking at the content of the generated corpus.
• Tutorial 2 fuzz-test the pulldown-cmark crate using a grammar-based mutator. We find test cases that trigger a panic at multiple different locations.

Quick Start

Setup

• You can only use fuzzcheck on Linux or macOS (Windows support is possible but I need help with it)

• Install cargo-fuzzcheck

  cargo install cargo-fuzzcheck
  

• Make sure you are using Rust nightly

• Add the following to Cargo.toml:

[target.'cfg(fuzzing)'.dev-dependencies]
fuzzcheck = "0.12"

• Add serde = { version = "1.0", features = ["derive"] } to your dependencies as well

  • note: fuzzcheck has a serde dependency only when the serde_json_serializer feature is enabled. This feature is enabled by default, but you can write the following in your Cargo.toml to disable it:

  fuzzcheck = { version = "0.12", default-features = false }
  

• Add #![cfg_attr(fuzzing, feature(no_coverage))] at the top of the root module (e.g. src/lib.rs for a library target)

  • fuzzcheck’s procedural macros use the no_coverage attribute

• In your library, integration test, or executable, create a test module, gated by #[cfg(all(fuzzing, test))] and add a #[test] function inside it

  #[cfg(all(fuzzing, test))]
  mod tests {
      #[test]
      fn my_fuzz_test() {
          // ...
      }
  }
  

  We will write its body later on.

• Create a test function of type Fn(&T) or Fn(&T) -> bool and put the code you want to test inside it. You want this function to always succeed if the code is correct.

  // for example
  fn should_always_succeed(x: &SomeType) -> bool {
      // ...
  }
  

Mutator

The Mutator is responsible for generating values to feed to the test function.

The easiest way to get a mutator for a type is to use the #[derive(fuzzcheck::DefaultMutator)] attribute. Many std types also implement DefaultMutator.

// example
use fuzzcheck::DefaultMutator;
#[derive(Clone, DefaultMutator)]
pub struct SomeType<A, B: SomeTrait> {
    x: Option<A>,
    y: bool,
    z: Vec<Option<SomeOtherType<B>>>
}
#[derive(Clone, DefaultMutator)]
pub enum SomeOtherType<T> where T: SomeTrait {
    A,
    B { x: bool, y: Box<T> }
}

• If the test case is a String, you have two options:

  • Use the default mutator for String, which is essentially a wrapper around a Vec<u8> mutator and thus doesn't often generate useful strings
  • Use a grammar-based mutator (see tutorial 2 or the fuzzcheck::mutators::grammar module documentation)

• If the argument is a recursive type, you will need to use the make_mutator! macro (see the fuzzcheck::mutators::recursive module documentation)

• otherwise, you may need to write the mutator yourself

  • or ask me to do it on GitHub, if it's a type from std

Serializer

You need a way to save the generated test cases to the file system. This is most easily done with the fuzzcheck::SerdeSerializer type if the test case implements Serialize and Deserialize:

use serde::{Serialize, Deserialize};
#[derive(/*..*/, Serialize, Deserialize)]
struct Foo { /* .. */}

But there are other choices:

• ByteSerializer if the test case is Vec<u8> and we simply want to copy the bytes from/to the files
• StringSerializer if the test case is something that implements FromStr and ToString
• your own serializer

Sensor and Pool

TODO (but you probably don't need to worry about it to get started)

In the meantime, you can look at the CodeCoverageSensorAndPoolBuilder documentation, and the fuzzcheck::sensors_and_pools module documentation.

Building the fuzz test

We go back to the #[test] fuzz function that we defined earlier and write its body.

If you used:

1. the DefaultMutator derive attribute, or any other type that has a default mutator
2. serde to serialize the test cases

Then you can write:

    #[cfg(all(fuzzing, test))]
    mod tests {
        #[test]
        fn my_fuzz_test() {
            let result = fuzzcheck::fuzz_test(should_always_succeed) // the name of the function to test
                .default_options()
                .launch();
            assert!(!result.found_test_failure);
        }
    }

Otherwise, you can specify each component separately. Check the fuzzcheck::builder module documentation to learn about the different options available.

    #[cfg(all(fuzzing, test))]
    mod tests {
        #[test]
        fn my_fuzz_test() {
            let mutator = /* ... */;
            let serializer = /* ... */;
            let (sensor, pool) = /* .. */;
            let _ = fuzzcheck::fuzz_test(should_always_succeed) // the name of the function to test
                .mutator(my_mutator) // or .default_mutator() for the default one
                .serializer(my_serializer) // or .serde_serializer() for the default one
                .sensor_and_pool(sensor, pool) // or .default_sensor_and_pool() for the default ones
                .arguments_from_cargo_fuzzcheck() // take the other arguments from the `cargo fuzzcheck` invocation
                .launch();
        }
    }

Launching the fuzz test

On the command line, with the current directory at the root of your crate, run cargo fuzzcheck <args..> to launch the fuzz test. The mandatory arguments are:

• the target to compile, i.e. where is the #[test] function located?

  • the package’s library → add --lib or nothing
  • an integration test → add --test <NAME>
  • an executable → add --bin <NAME>

• the exact path to the test function

  # example
  cargo fuzzcheck tests::my_fuzz_test
  

That's it for the essential arguments. You can run cargo fuzzcheck --help for a list of all possible arguments.

Once you run the command, the crate will be compiled and the fuzz test will start.

Terminal output

When the fuzz test is running, a line is printed after every notable event. It looks like this:

<time> <iter nbr> <pool_name>(<pool_stats>)... failures(..) iter/s <N>

where:

• time is the time elapsed since the start
• iter nbr is the number of iterations performed so far
• pool_name(pool_stats) are statistics about the pool
• failures(..) is the number of test failures found
• iter/s is the number of iterations performed every second

File System Output

The fuzzer creates files under the fuzz/<fuzz_test> folder. Each pool used by the fuzzer maintains a copy of its content under fuzz/<fuzz_test>/corpus/<pool_name>. In particular, failing test cases can be found at fuzz/<fuzz_test>/corpus/test_failures.

There is also a folder called stats, which saves information about each fuzzing run and can be read by other tools for analysis.

Tutorial 1: a binary search tree

In this tutorial, we write a simple data structure and test its API with fuzzcheck. The goal is to learn the basics, that is:

• the requirements for a type or function to be fuzz-testable
• how to create a default Mutator for a custom type through fuzzcheck’s procedural macros
• how to use serde to serialize interesting values and artifacts to the type system
• how to use the cargo-fuzzcheck command line tool
• how to interpret the files generated by fuzzcheck

The data structure we choose to implement is a binary search tree. We create a new tree with Tree::empty(), insert a value into the tree with tree.insert(x), and search for a value in the tree with tree.contains(&x).

We will create a fuzz target that tests whether the tree

1. behaves like a proper set
2. does not crash

And we will see how, even when fuzzcheck does not find any failures, we can analyze its output to gain insight into our code.

Setup

First, create a new empty crate using a library template:

cargo new --lib example_1
cd example_1

And set the default version of the rust compiler for this crate to nightly;

rustup override set nightly

In Cargo.toml, add the following dependencies:

[dependencies]
serde = { version = "1.0", features = ["derive"] }

[dev-dependencies]
fuzzcheck = "0.12"

At the top of src/lib.rs add the following line:

#![cfg_attr(fuzzing, feature(no_coverage))]

This is a rust-nightly feature that fuzzcheck’s procedural macros use.

Now let's write some code to test. In src/lib.rs, we will add a simple implementation of a binary search tree.

pub struct Node<T: Ord> {
    key: T,
    left: Box<Tree<T>>,
    right: Box<Tree<T>>,
}
pub enum Tree<T: Ord> {
    Node(Node<T>),
    Empty,
}

And we implement the methods empty, insert, and contains.

use std::cmp::{self, Ordering};

impl<T: Ord> Tree<T> {
    /// Creates a new empty tree
    pub fn empty() -> Box<Self> {
        Box::new(Tree::Empty)
    }
    /// Returns true iff the tree contains the given value.
    pub fn contains(&self, k: &T) -> bool {
        match self {
            Tree::Node(Node { key, left, right }) => match k.cmp(key) {
                Ordering::Less => left.contains(k),
                Ordering::Equal => true,
                Ordering::Greater => right.contains(k),
            },
            Tree::Empty => false,
        }
    }
    /**
        Adds a value to the set.

        If the set did not have this value present, true is returned.
        If the set did have this value present, false is returned, and the tree is left unmodified.
    */
    pub fn insert(self: &mut Box<Self>, new_key: T) -> bool {
        match self.as_mut() {
            Tree::Node(Node {
                key,
                left,
                right,
            }) => match new_key.cmp(key) {
                Ordering::Less => {
                    left.insert(new_key)
                }
                Ordering::Equal => false,
                Ordering::Greater => {
                    right.insert(new_key)
                }
            },
            Tree::Empty => {
                **self = Tree::Node(Node {
                    key: new_key,
                    left: Self::empty(),
                    right: Self::empty(),
                });
                true
            }
        }
    }
}

We already have enough to start fuzz-testing our tree. To do so, we first add a tests module within the same src/lib.rs file, which we conditionally enable only for test builds with #[cfg(test)].

#[cfg(test)]
mod tests {
    use super::*;
    // Note that fuzzcheck is accessible here because it is a dev-dependency.
}

Test Function

Currently, a test function can be of two different types:

• fn foo(input: &T) always succeeds unless it crashes
• fn foo(input: &T) -> bool fails if it return false

For this example, we will write a function of the first kind.

Since our tree acts like a set, we want to compare its behaviour to a correct set implementation, such as BTreeSet. The idea is to start with two empty sets of type Tree and BTreeSet, apply some operations to them, and check that the result of each operation is the same for both of them. Our tree API consists of two methods, which we can model as:

#[cfg(all(fuzzing, test))]
mod tests {
    use super::*;

    enum Operation<T: Ord> {
        Insert(T),
        Contains(T),
    }
}

The test function takes as input an arbitrary list of operations and applies them to both structures.

#[cfg(all(fuzzing, test))]
mod tests {
    use super::*;
    use std::collections::BTreeSet;

    enum Operation<T: Ord> {
        Insert(T),
        Contains(T),
    }
    fn compare_with_btree_set<T: Ord + Clone>(operations: &[Operation<T>]) {
        let mut tree = Tree::empty();
        let mut set = BTreeSet::new();
        for op in operations {
            match op {
                Operation::Insert(x) => {
                    let a = tree.insert(x.clone());
                    let b = set.insert(x.clone());
                    assert_eq!(a, b);
                }
                Operation::Contains(x) => {
                    let a = tree.contains(x);
                    let b = set.contains(x);
                    assert_eq!(a, b);
                }
            }
        }
    }
}

If compare_with_btree_set never crashes, no matter the list of operations that is passed to it, then we can gain some confidence that our implementation is correct.

The next few sections will explain the different components that fuzzcheck needs in order to fuzz test compare_with_btree_set.

Mutator

A mutator is a value whose type implements the Mutator<T> trait, where T is any type that is Clone + 'static.

While it is possible to hand-write mutators, the easiest way to get one is to use the DefaultMutator trait and procedural macro.

use fuzzcheck::DefaultMutator;
#[derive(Clone, DefaultMutator)]
enum Operation<T: Ord> {
    Insert(T),
    Contains(T),
}

Now, we can get a mutator of Operation<T> by writing, for example:

fn example() {
    let mutator = Operation::<bool>::default_mutator(); // impl Mutator<Operation<bool>>
    // or for a mutator of `Vec<Operation<bool>>`
    let mutator = Vec::<Operation<bool>>::default_mutator(); // impl Mutator<Vec<Operation<bool>>>
    // ...
}

If we have a Mutator<Vec<bool>>, then we can use it for any function whose input type can be obtained by borrowing Vec<bool>. So it is valid for:

• fn test(xs: &Vec<bool>)
• but also fn test(xs: &[bool]) because Vec<bool> can be borrowed as [bool]

Serializer

We also need to know how to save the generated test cases, of type Vec<Operation<T>>, to the file system.

The easiest way to do that is to use serde and its derive macros Serialize and Deserialize.

use serde::{Serialize, Deserialize};

#[derive(Clone, DefaultMutator, Serialize, Deserialize)]
enum Operation<T: Ord> {
    Insert(T),
    Contains(T),
}

Then, we will provide a fuzzcheck::SerdeSerializer to our fuzz test so that each interesting Vec<Operation<T>> is saved as a JSON file.

There are other ways to serialize test cases. For example, for values of type Vec<u8>, you can use a fuzzcheck::ByteSerializer, which will simply copy the content of the vector to the file system. For values of type String, one can use a fuzzcheck::StringSerializer.

Writing the Fuzz Target

To create the fuzz test, create a new #[test] function in the tests module and call fuzzcheck::fuzz_test(compare_with_btree_set::<u16>) inside it. Note that only concrete functions can be tested, not generic ones, which is why we needed to specify a type parameter using ::<u16>.

#[test]
fn fuzz_test_tree() {
    fuzzcheck::fuzz_test(compare_with_btree_set::<u16>)
        // ... we now have a FuzzerBuilder1<..>
        // we still need to pass more arguments to it
        // before calling .launch()
}

We have specified which function to fuzz test, but not which mutator, serializer, sensor, or pool to use. We can add all these parameters as follows:

fn fuzz_test_tree() {
    fuzzcheck::fuzz_test(compare_with_btree_set::<u16>) // : FuzzerBuilder1<..>
        .default_mutator() // : FuzzerBuilder2<..>
        .serde_serializer() // : FuzzerBuilder3<..>
        .default_sensor_and_pool() // : FuzzerBuilder4<..>
}

And finally, we need to give fuzzcheck other arguments such as:

• does it run a regular fuzz-test or try to minize a failing test case?
• how complex can the generated values be?
• does it stop after the first test failure, or try to find more afterwards?
• should it maintain a copy of the pool on the file system? if so, where?
• etc.

The easiest way to do that is to let cargo-fuzzcheck pass these arguments for you. So we simply call .arguments_from_cargo_fuzzcheck(). Once that is done, we can finally call .launch(), which returns a FuzzingResult. The result contains two fields: found_test_failure and reason_for_stopping.

#[test]
fn fuzz_test_tree() {
    let result = fuzzcheck::fuzz_test(compare_with_btree_set::<u16>) // : FuzzerBuilder1<..>
        .default_mutator() // : FuzzerBuilder2<..>
        .serde_serializer() // : FuzzerBuilder3<..>
        .default_sensor_and_pool() // : FuzzerBuilder4<..>
        .arguments_from_cargo_fuzzcheck() // : FuzzerBuilder5<..>
        .launch(); // FuzzingResult
    assert!(!result.found_test_failure);
}

Since all those options are very common, there is a shortcut for them, called .default_options(). The code above is equal to the one below:

#[test]
fn fuzz_test_tree() {
    let result = fuzzcheck::fuzz_test(compare_with_btree_set::<u16>) // : FuzzerBuilder1<..>
        .default_options() // FuzzerBuilder5<..>
        .launch(); // FuzzingResult
    assert!(!result.found_test_failure);
}

#![cfg_attr(fuzzing, feature(no_coverage))]
use std::cmp::{self, Ordering};
pub struct Node<T: Ord> {
    key: T,
    left: Box<Tree<T>>,
    right: Box<Tree<T>>,
}
pub enum Tree<T: Ord> {
    Node(Node<T>),
    Empty,
}
impl<T: Ord> Tree<T> {
    /// Creates a new empty tree
    pub fn empty() -> Box<Self> {
        Box::new(Tree::Empty)
    }
    /// Returns true iff the tree contains the given value.
    pub fn contains(&self, k: &T) -> bool {
        match self {
            Tree::Node(Node { key, left, right }) => match k.cmp(key) {
                Ordering::Less => left.contains(k),
                Ordering::Equal => true,
                Ordering::Greater => right.contains(k),
            },
            Tree::Empty => false,
        }
    }
    /**
        Adds a value to the set.

        If the set did not have this value present, true is returned.
        If the set did have this value present, false is returned, and the tree is left unmodified.
    */
    pub fn insert(self: &mut Box<Self>, new_key: T) -> bool {
        match self.as_mut() {
            Tree::Node(Node {
                key,
                left,
                right,
            }) => match new_key.cmp(key) {
                Ordering::Less => {
                    left.insert(new_key)
                }
                Ordering::Equal => false,
                Ordering::Greater => {
                    right.insert(new_key)
                }
            },
            Tree::Empty => {
                **self = Tree::Node(Node {
                    key: new_key,
                    left: Self::empty(),
                    right: Self::empty(),
                });
                true
            }
        }
    }
}
#[cfg(all(fuzzing, test))]
mod tests {
    use super::*;
    use std::collections::BTreeSet;
    use fuzzcheck::DefaultMutator;
    use serde::{Serialize, Deserialize};

    /// The API of our tree, represented as an enum
    #[derive(Clone, DefaultMutator, Serialize, Deserialize)]
    enum Operation<T: Ord> {
        Insert(T),
        Contains(T),
    }
    /// A test function 
    fn compare_with_btree_set<T: Ord + Clone>(operations: &[Operation<T>]) {
        let mut tree = Tree::empty();
        let mut set = BTreeSet::new();
        for op in operations {
            match op {
                Operation::Insert(x) => {
                    let a = tree.insert(x.clone());
                    let b = set.insert(x.clone());
                    assert_eq!(a, b);
                }
                Operation::Contains(x) => {
                    let a = tree.contains(x);
                    let b = set.contains(x);
                    assert_eq!(a, b);
                }
            }
        }
    }

    // the actual fuzz target, which launches the fuzzer
    #[test]
    fn fuzz_test_tree() {
        let result = fuzzcheck::fuzz_test(compare_with_btree_set::<u16>)
            .default_options()
            .launch();
        assert!(!result.found_test_failure);
    }
}

The next section discusses how to run fuzz_test_tree using cargo fuzzcheck.

Using cargo-fuzzcheck

cargo-fuzzcheck is a convenience tool to

1. compile the fuzz tests correctly (e.g. by enabling -C instrument-coverage)
2. pass the correct command line arguments to the fuzzcheck driver (e.g. the path to the test case corpus in the file system)

Basic Invocation

To use it, you must know the exact path to the #[test] function that calls fuzzcheck. In the previous sections, that function’s path was tests::fuzz_test_tree.

We launch the fuzz test by running the following command:

cargo fuzzcheck tests::fuzz_test_tree

which by default limits the complexity of the test cases to 4096. But we can also limit it to something smaller using --max-cplx:

cargo fuzzcheck tests::fuzz_test_tree --max-cplx 1024

(Note: did it fail to compile for you? I would love to know. Could you please send me an email at loic.lecrenier@me.com and tell me about your computer/OS/rust version, and maybe share the source code? Thank you ❤️)

Terminal Output

cargo fuzzcheck will compile everything, launch the fuzzer, and print updates to the terminal. For example:

20ms 7923 simplest_cov(8 cov: 19/36 cplx: 25.00) diverse_cov_20(19) diverse_cov_1(19) max_each_cov_hits(9 sum: 241) max_total_cov_hits(136) failures(0) iter/s 458294 

After a few seconds, hit Ctrl+C to stop the fuzzer. We will look at the generated corpus in the file system.

Corpora

Each pool used by the fuzzer maintains a copy of its content under fuzz/<path_to_test>/corpus/<pool_name>. It can be useful to look at some of these files. We will look at two in particular: diverse_cov_1 and max_total_cov_hits.

Finding a single test case that covers most code

fuzz/tests::fuzz_test_tree/corpus/diverse_cov_1/ is generated by the pool that tries to find a single input covering most code regions. For me, it contained one file with the following content:

[{"Insert":20069},{"Insert":4746},{"Insert":22343},{"Contains":22343},{"Insert":20069},{"Contains":15415}]

This single value covers the following cases, which are all handed by different regions of code:

• inserting a value into an empty tree
• inserting a value smaller/larger than the key of a node
• inserting a value that is already present in the tree
• searching for a value that is smaller/larger than the key of a node
• searching for a value not present in the set
• searching for a value present in the set

So even though it is quite a small test case, it is an ideal candidate to write unit tests for our data structure.

Finding a test case that reveals performance problems

fuzz/tests::fuzz_test_tree/corpus/max_total_cov_hits is generated by the pool that tries to maximize the combined number of times that any region of code was reached. This is used as an (imprecise) proxy for the time complexity of the tested function. It contains a single value, which in my case is:

[{"Insert":1181},{"Insert":1531},{"Insert":6450},{"Insert":8617},{"Insert":9456},{"Insert":10031},{"Insert":10250},{"Insert":10800},{"Insert":11043},{"Insert":11206},{"Insert":11503},{"Insert":14791},{"Insert":15288},{"Insert":16511},{"Insert":57735},{"Insert":16548},{"Insert":16999},{"Insert":17127},{"Insert":17218},{"Insert":17336},{"Insert":17434},{"Insert":18465},{"Insert":18972},{"Insert":20107},{"Insert":21084},{"Insert":21648},{"Insert":22208},{"Insert":22734},{"Insert":23622},{"Insert":24108},{"Insert":24189},{"Insert":24280},{"Insert":24428},{"Insert":24809},{"Insert":24962},{"Insert":25084},{"Insert":25285},{"Insert":25308},{"Insert":52896},{"Insert":25462},{"Insert":26013},{"Insert":26038},{"Insert":51539},{"Insert":26283},{"Insert":50455},{"Insert":43899},{"Insert":42178},{"Insert":29572},{"Insert":30993},{"Insert":31654},{"Insert":32174},{"Insert":32964},{"Insert":42038},{"Insert":33351},{"Insert":35659},{"Insert":39606},{"Insert":36854},{"Insert":39113},{"Insert":39021},{"Insert":38526},{"Insert":38453},{"Insert":37403},{"Insert":38128}]

This is quite large! To understand why this particular test case was saved, we create a new test function that runs the operations and then print the resulting tree.

#[test]
fn test_highest_aggregate_cov_hits() {
    let input = r#"<content of the .json file shown above>"#;

    let serializer = SerdeSerializer::<Vec<Operation<u16>>>::default();
    let input = serializer.from_data(input.as_bytes()).unwrap();
    let mut tree = Tree::empty();
    for op in input {
        match op {
            Operation::Insert(x) => {
                tree.insert(x);
            }
            Operation::Contains(_) => {}
        }
    }
    tree.print_graphviz_dot();
}

where tree.print_graphviz_dot() prints the .dot file that can be used to visualise the tree:

impl<T> Tree<T>
where
    T: Ord + Display,
{
    fn print_graphviz_dot(&self) {
        match self {
            Tree::Node(Node { key, left, right, .. }) => {
                println!("{}", key);
                match left.deref() {
                    Tree::Node(Node { key: left_key, .. }) => {
                        println!("{} -> {}", key, left_key);
                    }
                    Tree::Empty => {}
                }
                match right.deref() {
                    Tree::Node(Node { key: right_key, .. }) => {
                        println!("{} -> {}", key, right_key);
                    }
                    Tree::Empty => {}
                }
                left.print_graphviz_dot();
                right.print_graphviz_dot();
            }
            Tree::Empty => {}
        }
    }
}

The result is:

Click here to reveal a (large) image of the generated tree

We now see that the problem is that the tree is completely unbalanced! Therefore, inserting a value has a worst-case O(n) time complexity where n is the number of elements in the tree. While this didn't cause any grave problem in our fuzz test, it does illustrate a problem that can eventually lead to a stack overflow. Now we know that we have to balance the tree after insertion.

It is generally a good idea to check the content of max_total_cov_hits to find test cases that cause an excessive amount of computation.

Arguments to cargo fuzzcheck

To find an overview of the arguments that can be passed to cargo fuzzcheck, run:

cargo fuzzcheck --help

Tutorial 2: pulldown-cmark

In this tutorial, we clone the popular pulldown-cmark crate and find real bugs in it.

We will start by creating a grammar-based mutator. From the generated syntax trees, we generate strings and then ask pulldown-cmark to parse those strings.

To get started, go to a new folder and clone the pulldown-cmark repository:

git clone https://github.com/raphlinus/pulldown-cmark.git 

and then checkout the repository to its state from 18 September 2021:

cd pulldown-cmark
git checkout -b fuzz 5088b21d09ef94b424c4d852db7648c9c94fb630

Note that grammar-based mutators are only available when the grammar_mutator feature is enabled. Creating grammars from regular expressions is only possible when the regex_grammar feature is enabled. Both of these featuress are enabled by default.

Test Function

The main function declared by pulldown-cmark is called push_html. It takes a markdown string as input and generates an HTML string from it. Our test function will only verify that push_html never crashes. We write it inside src/lib.rs.

#[cfg(all(fuzzing, test))]
mod tests {
    use crate::{html, Parser};
    fn push_html_does_not_crash(md_string: &str) {
        let parser = Parser::new(md_string);
        let mut html_output = String::new();
        html::push_html(&mut html_output, parser);
    }
}

The most important step afterwards is to create a good mutator for generating markdown strings. This is discussed in the next section.

Creating a grammar-based mutator

String Mutators

First, I should note that fuzzcheck does not yet have a general-purpose Mutator<String>. However, we can still use two approaches to generate strings. The first approach is to use a Vec<u8> and then obtain a string from the slice of bytes using String::from_utf8_lossy(..). The second is to use grammar-based mutators to generate syntax trees and their associated strings. The shape of the generated trees are described by a grammar.

For example, we can write:

use fuzzcheck::mutators::grammar;

let rule1 = grammar::regex("[a-z](0|ad)[!?]{1,10}")

which is a grammar that matches/generates the following strings:

gad!
b0???!
w0?

but not the following:

yad     (missing the last rule: a repetition of ! and ?)
Gad!    (G is not in 'a' ..= 'z')
b0ad?!  (what follows the first letter can be either 0 or ad , but not both)

We can also write recursive grammars as follows:

use fuzzcheck::mutators::grammar::{regex, literal, alternation, concatenation, recursive, recurse};

let grammar = recursive(|g| {
    alternation([
        regex("[a-zA-Z]"),
        concatenation([
            literal('('),
            recurse(g),
            literal(')')
        ])
    ])
);

which matches the following strings:

F
s
(a)
((((H))))
((((((((((((((((((((((((((((((((((((((((n))))))))))))))))))))))))))))))))))))))))

but not those:

(a        (mismatched parentheses)
((()))    (no letter inside the parentheses)

It can be useful to build a grammar piece by piece instead of within a single declaration.

use fuzzcheck::mutators::grammar::{regex, literal, alternation, concatenation, repetition, recursive, recurse};
use fuzzcheck::mutators::grammar::Grammar;
use std::rc::Rc;
use std::rc::Weak;

fn whitespace() -> Rc<Grammar> {
    regex("[ \t]+")
}
fn simple_short_ascii_word() -> Rc<Grammar> {
    regex("[a-zA-Z]{1,10}")
}
fn reference() -> Rc<Grammar> {
    concatenation([
        literal('['),
        simple_short_ascii_word(),
        literal(']')
    ])
}
fn recursing_rule(whole: &Weak<Grammar>) -> Rc<Grammar> {
    concatenation([
        literal('<'),
        recurse!(whole),
        literal('>')
    ])
}
fn final_grammar() -> Rc<Grammar> {
    recursive!(|whole_grammar| {
        alternation([
            simple_short_ascii_word(),
            reference(),
            recursing_rule(whole_grammar)
        ])
    })
}

The above grammar matches the following strings:

hello
[world]
<planto>
<<<[bing]>>>

Creating a String mutator from a grammar

Once you have a grammar, of type Rc<Grammar>, you can obtain a mutator that generates syntax trees matching the grammar as well as the associated string:

use fuzzcheck::mutators::grammar::grammar_based_ast_mutator;
let grammar = regex(/* .. */);
let mutator = grammar_based_ast_mutator(grammar) // : impl Mutator<AST>
    .with_string(); // : impl Mutator<(AST, String)>

Unfortunately, the argument of the test function will need to be &(AST, String) instead of &str. (A previous version of fuzzcheck also had a grammar-based string mutator, which implemented Mutator<String>. However, I have removed it from the latest version while I fix some bugs with it).

The test function given to fuzzcheck will then need to have the following signature:

fn test((_, x): &(AST, String)) { 
    // ...
}
// instead of
fn test(x: &str) { }

In the next section, we build a grammar such that it generates interesting markdown strings.

A markdown grammar

In this section we write a grammar with the goal of producing interesting markdown strings.

Note that this is different from formalizing the markdown syntax. We don't need to make it unambiguous, or to have one rule per syntactic construct. The goal is merely to produce “interesting” strings.

In fact, when testing the parser of a language, it is a good idea to make the grammar used for fuzz-testing different than the actual grammar of the language. The goal of fuzzing, after all, is to verify one’s assumption about the kinds of inputs that our code might handle. If we over-specify our mutators such that the only values they produce are the ones that we anticipated, then we won't discover many bugs. With that being said, let's write a markdown grammar.

Scope

Since this is just a tutorial, we will limit the scope of what we fuzz test. In particular, we won't test any extension to the markdown syntax, such as strikethroughs and tables.

Basic text

The most basic markdown document is just a series of letters with no special meaning:

Hi! My name is Loïc and I am running out of creativity to write good examples in this tutorial.

The grammar for this will just be a repetition of characters, which can also express using a regular expression.

fn text() -> Rc<Grammar> {
    regex(".+")
}

But note that when using such a general pattern as .+, we will almost always produce characters with no meaning. It is better to split the rule into two parts: ascii characters, and the other ones. The mutator will then treat both cases with equal importance.

fn text() -> Rc<Grammar> {
    regex("([\u{0}-\u{7f}]|.)+")
}

Whitespace

Whenever we need whitespace, we will use the following:

fn whitespace() -> Rc<Grammar> {
    regex("[ \t\n\r]+")
}

Header

To generate strings of the form:

# Header
#### Header ######

We can use the following:

fn header() -> Rc<Grammar> {
    concatenation([
        regex("#+"),
        text(),
        regex("#*")
    ])
}

However, we can do better. We don't want to assume that the parser will treat the inside of the header as just text. What if a specific markdown string inside a header causes a bug? It is almost always better to be more general. So instead, we replace the text() part of the grammar with a recursion to the whole markdown grammar.

fn header(md: &Weak<Grammar>) -> Rc<Grammar> {
    concatenation([
        regex("#+"),
        recurse(md),
        regex("#*")
    ])
}

Others

It is not the most useful thing to dwell on the details of every rule. Instead, I will summarize here the markdown features for which I wrote a grammar rule:

• headers: ## header
• emphases: **hello** and _world_
• quotes: > md
• lists: 1. md or - md or ..
• references: [hello](world), ![ref], [ref]: definition
• autolinks: <https://google.come>
• thematic breaks: ---, *****
• setext header (indirectly): ----, ===

For a comprehensive markdown grammar, there should be many more rules, but we will stop here. The full code is available at the bottom of the page.

Putting it all together

We can now write the whole markdown grammar as a repetition of the subgrammars.

fn markdown() -> Rc<Grammar> {
    recursive(|md| {
        repetition(
            alternation([
                text(),
                header(md),
                emphasis(md),
                quote(),
                list(),
                reference(md),
                reference_definition(md),
                autolink(md),
                thematic_break_or_setext()
            ]),
            0..
        )
    })
}

Full Code

#[cfg(all(fuzzing, test))]
mod tests {
    use crate::{html, Parser};
    use fuzzcheck::mutators::grammar::*;
    use std::rc::{Rc, Weak};

    fn text() -> Rc<Grammar> {
        regex("([\u{0}-\u{7f}]|.)+")
    }

    fn whitespace() -> Rc<Grammar> {
        regex("[ \t\n\r]+")
    }

    fn header(md: &Weak<Grammar>) -> Rc<Grammar> {
        concatenation([regex("#+"), recurse(md), regex("#*")])
    }

    pub fn quote() -> Rc<Grammar> {
        regex(">+")
    }

    pub fn list() -> Rc<Grammar> {
        regex("[-*+]+|[0-9]+[.)]?")
    }

    pub fn emphasis(md: &Weak<Grammar>) -> Rc<Grammar> {
        concatenation([regex("[*_~`]+"), recurse(md), regex("[*_~`]+")])
    }

    pub fn autolink(md: &Weak<Grammar>) -> Rc<Grammar> {
        concatenation([literal('<'), alternation([recurse(md), text()]), literal('>')])
    }

    pub fn reference(md: &Weak<Grammar>) -> Rc<Grammar> {
        concatenation([
            regex("!?\\["),
            recurse(md),
            literal(']'),
            repetition(concatenation([literal('('), recurse(md), literal(')')]), 0..=1),
        ])
    }

    pub fn reference_definition(md: &Weak<Grammar>) -> Rc<Grammar> {
        concatenation([
            literal('['),
            recurse(md),
            literal(']'),
            repetition(whitespace(), 0..=1),
            literal(':'),
        ])
    }

    pub fn thematic_break_or_setext_or_fence() -> Rc<Grammar> {
        alternation([
            regex("[* \t]{3,}"),
            regex("[- \t]{3,}"),
            regex("[= \t]{3,}"),
            regex("[~ \t]{3,}"),
            regex("[` \t]{3,}"),
        ])
    }
    fn markdown() -> Rc<Grammar> {
        recursive(|md| {
            repetition(
                alternation([
                    text(),
                    header(md),
                    emphasis(md),
                    quote(),
                    list(),
                    reference(md),
                    reference_definition(md),
                    autolink(md),
                    thematic_break_or_setext()
                ]),
                0..
            )
        })
    } 
    fn push_html_does_not_crash(md_string: &str) {
        let parser = Parser::new(md_string);
        let mut html_output = String::new();
        html::push_html(&mut html_output, parser);
    }
}

Fuzzing

We know have everything needed to fuzz-test pulldown-cmark.

Inside the tests module in src/lib.rs, add the following #[test] function:

use fuzzcheck::mutators::grammar;

#[test]
fn fuzz() {
    let mutator = grammar::grammar_based_ast_mutator(markdown()).with_string();
    let result = fuzzcheck::fuzz_test(|(_, string): &(AST, String)| {
            push_html_does_not_crash(string)
        })
        .mutator(mutator)
        .serde_serializer()
        .default_sensor_and_pool()
        .arguments_from_cargo_fuzzcheck()
        .launch();
    assert!(!result.found_test_failure);
}

We launch the fuzz test using:

cargo fuzzcheck tests::fuzz

Updates about the fuzzing progress will be printed, such as:

7s + 68782 simplest_cov(292 cov: 1937/2617 cplx: 31.75) diverse_cov_20(1904) diverse_cov_1(1514) max_each_cov_hits(501 sum: 8601361) max_total_cov_hits(5799778) failures(3) iter/s 10071

After about a minute, fuzzcheck should have found at least two distinct test failures:

They are stored in the fuzz/<fuzz_test>/corpus/test_failures/ folder with the following structure:

- tests::fuzz/corpus/test_failures
    # each folder here corresponds to a distinct test failure (e.g. different panic locations)
    - 5460776198281478584
        # each folder here corresponds to a test case complexity
        - 26.0000
            # this is an actual failing test case, of complexity 26.0
            - 3d3294fac0c0e5e4.json
            - c780161f12e87030.json
        - 54.0000
            - etc.

The .json file contain both the serialized syntax trees and the markdown string. For example, 3d3294fac0c0e5e4.json is:

[
    ">\t<g\tO\n",
    { /* serialized AST */ }
]

We can debug this string by making a new test function:

#[test]
fn reproduce_crash() {
    let s = ">\t<g\tO\n";
    push_html_does_not_crash(s);
}

Running the test gives us a panic message:

thread 'tests::reproduce_crash' panicked at 'range start index 7 out of range for slice of length 5', src/scanners.rs:871:17