tree-crasher
tree-crasher is an easy-to-use grammar-based black-box fuzzer. It parses a number of input files using tree-sitter grammars, and produces new files formed by splicing together their ASTs.
tree-crasher aims to occupy a different niche from more advanced grammar-based fuzzers like Gramatron, Nautilus, and Grammarinator. Rather than achieve maximal coverage and bug-finding through complete, hand-written grammars and complex techniques like coverage-based feedback, tree-crasher aims to achieve maximal ease-of-use by using off-the-shelf tree-sitter grammars and not requiring any instrumentation (nor even source code) for the target. In short, tree-crasher wants to be the Radamsa of grammar-based fuzzing.
tree-sitter grammars are resistant to syntax errors. Therefore, tree-crasher can even mutate syntactically-invalid inputs! You can also use tree-crasher with an incomplete grammar.
tree-crasher uses treereduce to automatically minimize generated test-cases.
Examples
See the usage docs.
Bugs found
tree-crasher uses tree-splicer to generate test cases, see the list of bugs found in that project's README.
If you find a bug with tree-crasher, please let me know! One great way to do so would be to submit a PR to tree-splicer to add it to the README.
Supported languages
tree-crasher currently ships pre-built executables for the following languages:
Additionally, the following fuzzers can be built from source or installed via crates.io:
Languages are very easy to add, so file an issue or a PR if you want a new one!
How it works
tree-crasher is mostly a thin wrapper around tree-splicer that runs it in parallel. When "interesting" test cases are found, they're handed off to treereduce.
Installation
Pre-compiled binaries
Pre-compiled binaries are available on the releases page.
Fetching binaries with cURL
You can download binaries with curl
like so (replace X.Y.Z
with a real
version number, LANG
with a supported language, and TARGET
with your OS):
curl -sSL https://github.com/langston-barrett/tree-crasher/releases/download/vX.Y.Z/tree-crasher-LANG_TARGET -o tree-crasher-LANG
Build from source
To install from source, you'll need to install Rust and Cargo. Follow the instructions on the Rust installation page.
From a release on crates.io
You can build a released version from crates.io. To install the latest
release of tree-crasher for the language <LANG>
, run:
cargo install tree-crasher-<LANG>
This will automatically download the source from crates.io, build it, and
install it in Cargo's global binary directory (~/.cargo/bin/
by default).
From the latest unreleased version on Github
To build and install the very latest unreleased version, run:
cargo install --git https://github.com/langston-barrett/tree-crasher.git tree-crasher-LANG
From a local checkout
See the developer's guide.
Uninstalling
To uninstall, run cargo uninstall tree-crasher-<LANG>
.
Usage
The inputs to tree-crasher are a corpus of files and a command to run. By
default, tree-crasher passes inputs to the command on stdin, but will replace
the special symbol @@
with a filename as seen in the examples above.
tree-crasher saves inputs that match a set of conditions. By default the only
condition is that the target receives an unhandled signal (e.g., a segfault).
Extra conditions may be added with the --interesting*
flags, see --help
.
tree-crasher does not exit gracefully at the moment; just send SIGINT (ctrl-c) when you're done fuzzing.
Examples
When reading these examples, keep in mind that fuzzing can cause unpredictable behaviors. Always fuzz in a VM or Docker container with a memory limit, no network access, and no important files.
JavaScript interpreters
Obtain a collection of JavaScript files and put them in corpus/
(for example,
using this script). Then here's how to fuzz
JerryScript and Boa:
tree-crasher-javascript corpus/ jerry
tree-crasher-javascript corpus/ boa
(By default, tree-crasher passes input to the target on stdin.)
Python's regex engine
Write rx.py
like so:
import re
import sys
try:
s = sys.stdin.read()
r = re.compile(s)
print(r.match(s))
except:
pass
Put some sample regular expressions in corpus/
. Then:
tree-crasher-regex corpus/ -- python3 $PWD/rx.py
rustc
tree-crasher has found many bugs in rustc. Here's how it was done! The special
@@
symbol on the command line gets replaced by the file generated by
tree-crasher.
tree-crasher-rust \
--interesting-stderr "(?m)^error: internal compiler error:" \
corpus \
-- \
rustc +nightly --crate-type=lib --emit=mir -Zmir-opt-level=4 @@.rs
(The regex syntax is that of the regex crate.)
Here's how to limit the amount of memory taken by tree-crasher and rustc using
systemd-run
, and drop network access using unshare
:
systemd-run --scope -p MemoryMax=16G -p MemorySwapMax=0B --user \
unshare -Umn \
tree-crasher-rust \
--interesting-stderr "(?m)^error: internal compiler error:" \
corpus \
-- \
rustc +nightly --crate-type=lib --emit=mir -Zmir-opt-level=4 @@.rs
SQL databases
Obtain a collection of SQL files (for example, using this script). Then here's how to fuzz DuckDB:
tree-crasher-sql --interesting-stderr "INTERNAL Error" corpus/ -- duckdb
Sometimes, you keep running into the same bug and would like to stop reporting
it. For that, you can use --uninteresting-stderr
:
tree-crasher-sql \
--interesting-stderr "INTERNAL Error" \
--uninteresting-stderr "INTERNAL Error.+HyperLogLog::ComputeHashes" \
corpus \
-- \
duckdb
Even more examples
Clang (frontend) (see also this script):
tree-crasher-c corpus/ --interesting-stderr "(?m)^PLEASE " -- clang -c -O0 -o /dev/null -emit-llvm -Xclang -disable-llvm-passes @@.c
tree-crasher-javascript corpus/ -- deno fmt @@.js
tree-crasher-sql corpus/ -- clickhouse local
Contributing
Thank you for your interest in tree-crasher! We welcome and appreciate all kinds of contributions. Please feel free to file and issue or open a pull request.
You may want to take a look at:
If you have questions, please ask them on the discussions page!
Developer's guide
Build
To install from source, you'll need to install Rust and Cargo. Follow the instructions on the Rust installation page. Then, get the source:
git clone https://github.com/langston-barrett/tree-crasher
cd tree-crasher
Finally, build everything:
cargo build --release
You can find binaries in target/release
. Run tests with cargo test
.
Docs
HTML documentation can be built with mdBook:
cd doc
mdbook build
Format
All code should be formatted with rustfmt. You can install rustfmt with rustup like so:
rustup component add rustfmt
and then run it like this:
cargo fmt --all
Lint
All code should pass Clippy. You can install Clippy with rustup like so:
rustup component add clippy
and then run it like this:
cargo clippy --workspace -- --deny warnings
Release
-
Create branch with a name starting with
release
-
Update
CHANGELOG.md
-
Update the version numbers in
./crates/**/Cargo.toml
find crates/ -type f -name "*.toml" -print0 | \ xargs -0 sed -E -i 's/^version = "U.V.W"$/version = "X.Y.Z"/'
-
Run
cargo build --release
-
Commit all changes and push the release branch
-
Check that CI was successful on the release branch
-
Merge the release branch to
main
-
git checkout main && git pull origin && git tag -a vX.Y.Z -m vX.Y.Z && git push --tags
-
Verify that the release artifacts work as intended
-
Release the pre-release created by CI
-
Check that the crates were properly uploaded to crates.io
Warnings
Certain warnings are disallowed in the CI build. You can reproduce the behavior
of the CI build by running cargo check
, cargo build
, or cargo test
like
so:
env RUSTFLAGS="@$PWD/rustc-flags" cargo check
Using a flag file for this purpose achieves several objectives:
- It frictionlessly allows code with warnings during local development
- It makes it easy to reproduce the CI build process locally
- It makes it easy to maintain the list of warnings
- It maintains forward-compatibility with future rustc warnings
- It ensures the flags are consistent across all crates in the project
This flag file rejects all rustc
warnings by default, as well as a subset of
allowed-by-default lints. The goal is to balance
high-quality, maintainable code with not annoying developers.
To allow a lint in one spot, use:
#![allow(unused)] fn main() { #[allow(name_of_lint)] }
To enable these warnings on a semi-permanent basis, create a [Cargo configuration file][cargo-conf]:
mkdir .cargo
printf "[build]\nrustflags = [\"@${PWD}/rustc-flags\"]\n" > .cargo/config.toml