A Structure-Aware Fuzzing Experiment

Structure-aware fuzzing can better exercise the system under test (SUT) by<br>crafting inputs in the format expected by the SUT, rather than throwing<br>pseudorandom bytes against it. That is, it avoids “shallow” inputs that the SUT<br>will reject early (for example, syntactically invalid source text when fuzzing a<br>programming language’s compiler) and only produces inputs that go “deep” into<br>the SUT (e.g. programs that type-check and exercise the mid-end optimizer and<br>backend code generator). The Rust fuzzing ecosystem is largely built around<br>cargo-fuzz and the libfuzzer-sys crate, which provides two methods for<br>structure-aware fuzzing:

Generating structured inputs from scratch with the arbitrary crate

Mutating existing inputs from the fuzzer’s corpus in a structure-aware<br>manner, thereby producing new structured inputs, via the<br>fuzz_mutator! hook

While the two methods are not technically mutually exclusive, combining the two<br>can be difficult and engineering resources are finite. So:

If we are only implementing one approach, is generation or mutation better?

To help answer this question, I implemented structure-aware generation and<br>mutation of guaranteed-valid WebAssembly (Wasm) instruction sequences. This<br>task is small enough to be easily understandable but large enough and real<br>enough to (hopefully) be representative and applicable to other domains, or, at<br>the very least, interesting.1 To evaluate their effectiveness, I<br>used Wasmtime as the SUT, libfuzzer-sys as the fuzzing engine driving<br>everything, and then compared code coverage over time when using mutation-based<br>fuzzing versus generation-based fuzzing.

Additionally, there are many ways we can generate pseudorandom WebAssembly<br>instruction sequences. In this experiment, I’ve evaluated three methods:

Unconstrained instruction sequence generation followed by a fixup pass to<br>ensure validity

Generating valid instructions in a forwards, bottom-up<br>manner (from operands to operators)

Generating valid instructions in a backwards, top-down manner (from operators<br>to operands)

In contrast, while there are surely many ways to mutate a given WebAssembly<br>instruction sequence into a new, valid instruction sequence, I’ve only<br>implemented one method: perform an arbitrary instruction insertion, deletion, or<br>replacement, producing a new but probably-invalid instruction sequence, and then<br>run the same fixup pass mentioned previously to ensure validity. This is the<br>direct mutation-based equivalent of the first generation-based method.

Before continuing further, I want to disclose that I am the author of<br>wasm-smith and mutatis, and a maintainer of Wasmtime, arbitrary,<br>libfuzzer-sys, and cargo-fuzz. That is, while I am familiar with Wasm,<br>fuzzing, fuzzing Wasm, and both the arbitrary and mutatis crates, I may also<br>be propagating my own biases into these implementations.

Background

Generation-Based and Mutation-Based Fuzzing

A generation-based fuzzer uses a generator to create a pseudo-random test<br>cases from scratch, feeds these into the system under test, and reports any<br>failures to the user:

fn generation_based_fuzzingT>(<br>// A test-case generator.<br>generator: impl Fn() -> T,<br>// A function to run the system under test with a<br>// generated test case, returning a result that<br>// describes whether the run was successful or<br>// not.<br>run_system_under_test: impl Fn(&T) -> FuzzResult,<br>) {<br>loop {<br>// Generate an input.<br>let input = generator();

// Run the input through the system under test.<br>let result = run_system_under_test(&input);

// If the system crashed, panicked, failed an<br>// assertion, violated an invariant, or etc...<br>// then report that to the user.<br>if let Err(failure) = result {<br>report_to_user(&input, failure);

On the other hand, mutation-based fuzzers are given an initial corpus of inputs<br>and create new inputs by mutating existing corpus members. They run each new<br>input through the SUT, report failures the same as before, and if the new input<br>was “interesting” (for example, exercised new code paths in the SUT that weren’t<br>previously covered in any other input’s execution) then the new input is added<br>into the corpus for use in future test iterations:

fn mutation_based_fuzzingT>(<br>// A corpus of test cases.<br>corpus: &mut CorpusT>,<br>// A function to pseudo-randomly mutate an existing<br>// input into a new input.<br>mutate: impl Fn(&T) -> T,<br>// A function to run an input in the system under<br>// test, returning a result that describes whether<br>// the run was successful or not.<br>run_system_under_test: impl Fn(&T) -> FuzzResult,<br>) {<br>loop {<br>// Choose an old test case from the corpus.<br>let old_input = corpus.choose_one();

// Pseudo-randomly mutate that old test case,<br>// creating a new one.<br>let input = mutate(old_input);

// Run the input through the system under test.<br>let result = run_system_under_test(&input);

// If the system crashed, panicked, failed an<br>// assertion, violated an invariant, or etc...<br>// then report that to the user.<br>if let...