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