Structure-aware fuzzing can better exercise the system under test (SUT) by
crafting inputs in the format expected by the SUT, rather than throwing
pseudorandom bytes against it. That is, it avoids “shallow” inputs that the SUT
will reject early (for example, syntactically invalid source text when fuzzing a
programming language’s compiler) and only produces inputs that go “deep” into
the SUT (e.g. programs that type-check and exercise the mid-end optimizer and
backend code generator). The Rust fuzzing ecosystem is largely built around
crate, which provides two methods for
structure-aware fuzzing:
Generating structured inputs from scratch with the hook
While the two methods are not technically mutually exclusive, combining the two
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
mutation of guaranteed-valid To evaluate their effectiveness, I
used
Structure-Aware Fuzzing
Structure-unaware fuzzing will generate pseudorandom byte sequences and pass
them directly to the SUT. If the SUT expects some sort of structured input,
e.g. the source text for a programming language, it is likely that these byte
sequences are invalid and will be rejected early by the SUT’s frontend. For
example, when fuzzing a compiler, the input is rejected as syntactically invalid
by the parser or rejected as semantically invalid by the type checker. This can
be useful when hardening a tokenizer, parser, or type checker, but is less
useful when hunting for misoptimization in the mid-end or bad instruction
encoding in the backend because the inputs are unlikely to make it that far
through the compiler’s pipeline.
Structure-aware fuzzing will produce inputs that match the SUT’s expected
input format. Returning to the compiler-fuzzing example, structure-aware fuzzing
lets us generate valid programs for the compiler, so we can exercise more of the
mid-end and backend, rather than just the frontend.
Structure-aware fuzzing is often generation-based: for example using
and
implements a structure-aware mutator for zlib-compressed strings, where the raw
input is decompressed, the decompressed data is mutated, and then the mutated
data is recompressed to provide the new raw input. The mutator is aware of the
SUT’s zlib-compressed input structure.
More resources:
- crate helps Rust developers write custom structure-aware
generators for fuzzing. It provides building blocks and abstractions for
translating a raw byte sequence (usually from a fuzzing engine) into a
structured type, effectively interpreting the raw bytes as a “DNA string” or set
of predetermined choices for its decision tree. The library also provides a
derive(Arbitrary)macro to automatically implement its functionality for a
given type.
Because
arbitraryis effectively implemented by combining decision trees, it
is extremely easy to create imbalanced trees and unintentionally crate is, at a high-level, performing the same role for
authoring structure-aware mutators thatarbitraryplays for generators. That
is, it provides Rust developers with abstractions and combinators for creating
custom structure-aware mutators. It also provides aderive(Mutate)macro to
automatically implement its functionality for a given type.
mutatisis designed to resist bias via a two-phase design: first, it
enumerates all of the candidate mutations that could be applied to a test case,
and only afterwards chooses a particular random mutation from the candidate set
to actually apply.
WebAssembly
crate. The mutator
is built on top of the uses. After
generating instructions this way, it then makes sure that the final types on the
stack match the function signature’s results, similar to the end offixup.
CODEimpl Module {
pub fn bottom_up(u: &mut Unstructured<'_>) -> Result<Self> {
// ...
let max_insts = u.int_in_range(1..=MAX_INSTS)?;
let mut instructions = Vec::new();
let mut stack: Vec<ValType> = Vec::new();
for _ in 0..max_insts {
if stack == result_types && u.ratio(3, 4)? {
break;
}
// Choose a random instruction whose operand
// types match those currently on the stack.
let inst = choose_inst_bottom_up(
u,
&stack,
¶m_types,
&globals,
num_memories,
)?;
// Apply this instruction's effects to the
// stack.
apply_inst(
&inst,
&mut stack,
¶m_types,
&globals,
);
instructions.push(inst);
}
// ...
Ok(Module {
param_types,
result_types,
globals,
num_memories,
instructions,
})
}
}
fn choose_inst_bottom_up(
u: &mut Unstructured<'_>,
stack: &[ValType],
param_types: &[ValType],
globals: &[Global],
num_memories: u32,
) -> Result<Inst> {
// Build up all the valid candidate instructions.
let mut candidates: Vec<Inst> = Vec::new();
// Producers are always okay: [] -> [t]
candidates.push(Inst::I32Const(0));
candidates.push(Inst::I64Const(0));
candidates.push(Inst::F32Const(0.0));
candidates.push(Inst::F64Const(0.0));
candidates.push(Inst::V128Const(0));
if !param_types.is_empty() {
candidates.push(Inst::LocalGet(0));
}
// ...
let top = stack.last().copied();
let second = stack.get(stack.len() - 2).copied();
// Drop needs 1 operand of any type: [t] -> []
if top.is_some() {
candidates.push(Inst::Drop);
}
// i32 unary: [i32] -> [...]
if top == Some(I32) {
candidates.push(Inst::I32Clz);
candidates.push(Inst::I32Ctz);
candidates.push(Inst::I32Popcnt);
// ...
}
// i64 unary: [i64] -> [...]
if top == Some(I64) {
candidates.push(Inst::I64Clz);
candidates.push(Inst::I64Ctz);
candidates.push(Inst::I64Popcnt);
// ...
}
// ...
// i32 binary: [i32 i32] -> [...]
if top == Some(I32) && second == Some(I32) {
candidates.push(Inst::I32Add);
candidates.push(Inst::I32Sub);
candidates.push(Inst::I32Mul);
// ...
}
// i64 binary: [i64 i64] -> [...]
if top == Some(I64) && second == Some(I64) {
candidates.push(Inst::I64Add);
candidates.push(Inst::I64Sub);
candidates.push(Inst::I64Mul);
// ...
}
// ...
// Choose a random instruction from the
// candidates.
let mut inst = *u.choose(&candidates)?;
// If the instruction has immediates, generate
// them here, as they were hard-coded during
// candidate selection.
match &mut inst {
Inst::I32Const(v) => *v = u.arbitrary()?,
Inst::I64Const(v) => *v = u.arbitrary()?,
// ...
Inst::GlobalGet(g) => {
*g = u.int_in_range(0..=(globals.len() as u32 - 1))?;
}
// ...
Inst::I32Load(m)
| Inst::I64Load(m)
| Inst::F32Load(m)
| Inst::F64Load(m)
| Inst::V128Load(m)
| Inst::I32Store(m)
| Inst::I64Store(m)
| Inst::F32Store(m)
| Inst::F64Store(m)
| Inst::V128Store(m)
| Inst::MemorySize(m)
| Inst::MemoryGrow(m) => {
*m = u.int_in_range(0..=(num_memories - 1))?;
}
_ => {}
}
Ok(inst)
}
After constructing a
Moduleviabottom_up, we don’t need to callfixup
because the module is already valid by construction, so all that’s left is
invokingModule::to_wasm_binaryto get the encoded Wasm program.
top_down
The
top_downgenerator is very similar tobottom_up, but instead of
generating instructions forwards, from operands to operators, it generates them
backwards, from operators to operands. Instead of maintaining a stack of the
types of values generated thus far by the instruction sequence prefix, it
maintains a stack of the types of values expected by the instruction sequence
suffix. This is the approach that
CODEimpl Module {
pub fn top_down(
u: &mut Unstructured<'_>,
) -> Result<Self> {
// ...
let max_insts = u.int_in_range(1..=MAX_INSTS)?;
let mut instructions = Vec::new();
let mut needed = result_types.clone();
for _ in 0..max_insts {
if needed.is_empty() && u.ratio(3, 4)? {
break;
}
// Choose a random instruction in a
// top-down manner.
let inst = choose_inst_top_down(
u,
needed.last().copied(),
¶m_types,
&globals,
num_memories,
)?;
// Pop the result type from `needed`, if
// any, as it's been satisfied.
let ty = inst.result_type(
¶m_types,
&globals,
);
if ty == needed.last().copied() {
needed.pop();
}
// Add operand type demands.
match &inst {
Inst::Drop => {
// `drop` is polymorphic; choose
// a random type.
needed.push(u.arbitrary()?);
}
Inst::GlobalSet(g) => {
needed.push(globals[*g as usize].ty);
}
_ => {
needed.extend_from_slice(
inst.operand_types(&globals),
);
}
}
instructions.push(inst);
}
// Fill remaining needed types with
// constants.
for ty in needed.iter().rev() {
instructions.push(
ty.make_const(u.arbitrary()?),
);
}
// Instructions were generated backwards, so
// reverse.
instructions.reverse();
Ok(Module {
param_types,
result_types,
globals,
num_memories,
instructions: prefix,
})
}
}
fn choose_inst_top_down(
u: &mut Unstructured<'_>,
target_ty: Option<ValType>,
param_types: &[ValType],
globals: &[Global],
num_memories: u32,
) -> Result<Inst> {
let mut candidates: Vec<Inst> = Vec::new();
match target_ty {
Some(I32) => {
candidates.push(Inst::I32Const(0));
candidates.push(Inst::I32Add);
candidates.push(Inst::I32Sub);
candidates.push(Inst::I32Mul);
// ...
}
Some(I64) => {
candidates.push(Inst::I64Const(0));
candidates.push(Inst::I64Add);
candidates.push(Inst::I64Sub);
candidates.push(Inst::I64Mul);
// ...
}
Some(F32) => {
candidates.push(Inst::F32Const(0.0));
candidates.push(Inst::F32Add);
candidates.push(Inst::F32Sub);
candidates.push(Inst::F32Mul);
// ...
}
// ...
None => {
// Nothing needed. `drop`, `global.set`, and
// stores add demand.
candidates.push(Inst::Drop);
if globals.iter().any(|g| g.mutable) {
candidates.push(Inst::GlobalSet(0));
}
if num_memories > 0 {
candidates.push(Inst::I32Store(0));
// ...
}
}
}
let mut inst = *u.choose(&candidates)?;
// If the instruction has immediates, generate
// them here, as they were hard-coded during
// candidate selection. Same as `bottom_up`.
match &mut inst {
// ...
}
Ok(inst)
}
Similar to
bottom_up, after we’ve constructed aModuleviatop_down, we
don’t need to callfixupbecause the module is already valid by construction.
All that’s left is invokingModule::to_wasm_binaryto get the encoded Wasm
program.
mutate
mutateis, as the name implies, a mutator rather than a generator. It is the
direct equivalent of thearbgenerator, but for mutation: it uses
derive(mutatis::Mutate)onModuleandInstto automatically generate
custom mutators for these types, rather than authoring them by hand. After
producing a newModuleby mutating an oldModule, that newModuleprobably
represents an invalid Wasm program, in the same way that
derive(arbitrary::Arbitrary)producesModules that are probably invalid. And
mutatealso uses the same approach thatarbdoes to resolve this problem:
thefixupmethod.
But first, a mutator-specific wrinkle is that
fuzz_mutator!gives us a mutable
byte slice to mutate, not aModule. We address this gap by deriving the
crate here, but could just as easily use
and feed the
resulting test cases into , can be extrapolated from the 24-hour results. The 5-minute results
show the expected behavior of short-term fuzzing, e.g. when using
.
Discussion of short-term fuzzing is somewhat rare, so I feel its motivation
deserves explanation. I find short-term fuzzing useful in the following
scenarios, for example:
- Running a quick fuzzing session locally, to catch bugs that avoid detection in
the traditional unit- and integration-test suites, before opening a pull
request. - Running some quick fuzzing in CI before allowing a pull request to merge, for
similar reasons.
That is, short-term fuzzing is useful for the same reasons and in the same
scenarios as property-based testing. by Klees, Ruef, Cooper,
Wei, and Hicks and adopted in . The harness performs 20 trials per fuzzer, the same
number of trials as Fuzz Bench.
Results
24 Hours of Fuzzing
arbhas 1.00 ± 0.00 times more coverage thanbottom_up(p = 0.01)
mutatehas 1.01 ± 0.00 times more coverage thanarb(p = 0.00)
top_downhas 1.00 ± 0.00 times more coverage thanarb(p = 0.00)
mutatehas 1.02 ± 0.00 times more coverage thanbottom_up(p = 0.00)
top_downhas 1.01 ± 0.00 times more coverage thanbottom_up(p = 0.00)
mutatehas 1.01 ± 0.00 times more coverage thantop_down(p = 0.00)
Conclusion
The
mutatefuzzer performs best. It vastly outperforms all the others at 5
minutes of fuzzing (36-49% more coverage), and while the rest narrow that gap
after 24 hours of fuzzing,mutatemaintains its lead (1-2% more coverage).
The comparison between
arbandmutateis as apples-to-apples of a comparison
as it gets between idiomatic test-case generation and mutation in Rust:
derive(Arbitrary)andderive(Mutate). They use the samefixupmethod to
ensure that the resulting Wasm instructions are valid. The fuzzer built with
mutatisand test-case mutation provides better coverage over time than the
fuzzer built witharbitraryand test-case generation. When writing
structure-aware fuzzers, I used to reach for instead.
The
top_downfuzzer performs second-best, and is best of the generation-based
fuzzers. This aligns with results from the intermediate
representation, and erase the operand stack early in their compilation
pipelines. Therefore, from these compilers’ point of view, the following two
WebAssembly snippets are identical:
CODE;; `x = a + (b * c)` in a "stack-y" encoding and
;; without temporary locals.
local.get $a
local.get $b
local.get $c
i32.mul
i32.add
local.set $x
;; `x = a + (b * c)` in a "non-stack-y" encoding
;; that uses temporary locals for every operation.
;;
;; Equivalent of
;;
;; temp0 = b * c
;; temp1 = a + temp0
;; x = temp1
local.get $b
local.get $c
i32.mul
local.set $temp0
local.get $a
local.get $temp0
i32.add
local.set $temp1
local.get $temp1
local.set $x
Producing code that uses many temporaries in this manner might be easier than
code that doesn’t, but, more importantly, it may enable better reuse of
already-computed subexpressions, emit less dead code, and ultimately produce
more interesting data-flow graphs that better exercise the deep innards of the
compiler.
A final vein of interesting follow-up work to mine would be comparing
arbitrary-based generators andmutatis-based mutators for structured inputs
that are not programming languages and when the SUT we are fuzzing is not a
compiler. Do we see these same results when, for example, producing PNG images
to fuzz an image-transformation library?
- Running a quick fuzzing session locally, to catch bugs that avoid detection in
Ignoring its rule-guided bit, which is orthogonal and could be
applied tobottom_upas well. :
convergent evolution from different communities. ↩
SOCIAL SHARE CARD GENERATOR