Intro
fzero is a grammar-based fuzzer that generates a Rust application inspired
by the paper "Building Fast Fuzzers" by Rahul Gopinath and Andreas Zeller.
https://arxiv.org/pdf/1911.07707.pdf
You can find the F1 fuzzer here:
Usage
Currently this only generates an application that does benchmarking, but with some quick hacks you could easily get the input out and feed it to an application.
Example usage
D:\dev\fzero_fuzz>cargo run --release html.json test.rs test.exe 8
Finished release [optimized] target(s) in 0.02s
Running `target\release\fzero.exe html.json test.rs test.exe 8`
Loaded grammar json
Converted grammar to binary format
Optimized grammar
Generated Rust source file
Created Rust binary!
D:\dev\fzero_fuzz>test.exe
MiB/sec: 1773.3719
MiB/sec: 1763.8357
MiB/sec: 1756.8917
MiB/sec: 1757.1934
MiB/sec: 1758.9417
MiB/sec: 1758.9122
MiB/sec: 1758.7352
Concept
This program takes in an input grammar specified by a JSON file. This JSON
grammar representation is converted to a binary-style grammar that is intended
for interpretation and optimization. A Rust application (source file) is
produced by the shape of the input grammar. This then is compiled using rustc
to an application for the local machine.
This doesn't have any constraints on the random number generation as it uses an infinite supply of random numbers. There is no limitation on the output size and the buffer will dynamically grow as the input is created.
Benchmarks
All tests on a single core of a Intel(R) Core(TM) i7-8700 CPU @ 3.20GHz with a turbo clock rate of 4.3 GHz
All numbers in MiB/second.
| Benchmark | fzero fuzzer | F1 fuzzer | Speedup |
|---|---|---|---|
| html.json depth=4 | 5330 | 1295 | 4.11x |
| html.json depth=8 | 1760 | 348 | 5.05x |
| html.json depth=16 | 338 | 195 | 1.73x |
| html.json depth=32 | 218 | 175 | 1.25x |
| html.json depth=64 | 201 | 175 | 1.14x |
| json.json depth=4 | 97 | 97 | 1.00x |
| json.json depth=8 | 79 | 93 | 0.84x |
| json.json depth=16 | 83 | 89 | 0.93x |
| json.json depth=32 | 85 | 88 | 0.97x |
| json.json depth=64 | 85 | 90 | 0.94x |
Unsafe code
This project uses a small amount of unsafe code to provide the same semantics
of extend_from_slice but in a much faster way (over 4x faster). Not quite
sure why it's much faster, but if you are uncomfortable with unsafe code,
feel free to set SAFE_ONLY to true at the top of src/lib.rs. This will
restrict this fuzzer to only generate safe code. I don't think this is
necessary but who knows :)
Performance
The performance of this tool is separated into multiple categories. One is the code generation side, how long it takes for the JSON to be compiled into a Rust application. The other is the code execution speeds, which is how fast the produced application can generate inputs.
Code Generation
Code generation vastly outperforms the "Building Fast Fuzzers" paper. For
example when generating the code based on the html.json grammar, the F1
fuzzer took over 25 minutes to produce the code. This fuzzer is capable of
producing a Rust application in under 10 seconds.
Code execution
This project is on some performance metrics about 20-30% slower than the F1 fuzzer, but these scenarios are rare. However, in most situations we've been about to out-perform F1 by about 30-50%, and in extreme cases (html.json depth=8) we've observed over a 4x speedup.
Differences from the F1 fuzzer
The F1 fuzzer mentions a technique that will resolve to the nearest terminal tokens when stack depth is exceeded. We haven't implemented this technique but I don't think it's a huge impact on the generated inputs. This is something I will look into in the future.
Due to not using globals this can easily be scaled out to multiple threads as all random state and input generation are done in a structure.
There is no use of assembly in this project, and thus it can produce highly-performant fuzzers for any architecture or environment that Rust can compile against (pretty much identical to LLVM's target list).