Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

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

deno fmt:

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

ClickHouse:

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

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. This includes all rustc warnings, 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)]
}

Linting and formatting

We employ a variety of linting and formatting tools. They can be run manually or with Ninja.

Ninja script

To run all the linters:

./scripts/lint/lint.py

To run all the formatters:

./scripts/lint/lint.py --format

As a pre-commit hook:

cat <<'EOF' > .git/hooks/pre-commit
#!/usr/bin/env bash
./scripts/lint/lint.py
EOF
chmod +x .git/hooks/pre-commit

Clippy

We lint Rust code with Clippy.

You can install Clippy with rustup like so:

rustup component add clippy

and run it like this:

cargo clippy --all-targets -- --deny warnings

Generic scripts

We have a few Python scripts in scripts/lint/ that perform one-off checks. They generally take some number of paths as arguments. Use their --help options to learn more.

mdlynx

We run mdlynx on our Markdown files to check for broken links.

git ls-files -z --exclude-standard '*.md' | xargs -0 mdlynx

Mypy

We lint Python code with mypy in --strict mode.

git ls-files -z --exclude-standard '*.py' | xargs -0 mypy --strict

Ruff

We lint and format Python code with Ruff.

git ls-files -z --exclude-standard '*.py' | xargs -0 ruff format
git ls-files -z --exclude-standard '*.py' | xargs -0 ruff check

rustfmt

We format Rust code with [rustfmt].

You can install rustfmt with rustup like so:

rustup component add rustfmt

and then run it like this:

cargo fmt --all

ShellCheck

We lint shell scripts with ShellCheck.

git ls-files -z --exclude-standard '*.sh' | xargs -0 shellcheck

taplo

We format TOML files with taplo.

git ls-files -z --exclude-standard '*.toml' | xargs -0 taplo format

typos

We run typos on Markdown files.

git ls-files -z --exclude-standard '*.md' | xargs -0 typos

zizmor

We lint our GitHub Actions files with zizmor.

zizmor .github