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

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

More examples are listed at the end of the README.

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:

• C
• CSS
• JavaScript
• Regex
• Rust
• SQL
• TypeScript

Additionally, the following fuzzers can be built from source or installed via crates.io:

• HTML
• Ruby

Languages are very easy to add, so file an issue or a PR if you want a new one!

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.

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

From a release

Statically-linked Linux binaries are available on the releases page.

From crates.io

You can build a released version from crates.io. You'll need the Rust compiler and the Cargo build tool. rustup makes it very easy to obtain these. Then, to install the fuzzer for the language <LANG>, run:

cargo install tree-crasher-<LANG>

This will install binaries in ~/.cargo/bin by default.

Build

To build from source, you'll need the Rust compiler and the Cargo build tool. rustup makes it very easy to obtain these. 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.

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

deno fmt:

tree-crasher-javascript corpus/ -- deno fmt @@.js

ClickHouse:

tree-crasher-sql corpus/ -- clickhouse local