Skip to content

About

A grammar-based custom mutator for AFL++

Topics

Resources

Contributing

Stars

278 stars

Watchers

3 watching

Forks

Latest commit

 

History

310 Commits

Folders and files

Repository files navigation

Grammar Mutator - AFL++

Grammar Mutator CI

A grammar-based custom mutator for AFL++ to handle highly-structured inputs.

Overview

We developed a grammar mutator to enhance AFL++ such that AFL++ can handle highly-structured inputs, such as JSON, Ruby, etc. The grammar mutator leverages the idea of F1 fuzzer and Nautilus for test case generation and mutations. In summary, this repository includes:

  • Grammars in a JSON format or in the ANTLR 4 format (.g4), for example from grammars-v4
  • Tree-based mutation: rules mutation, random mutation, random recursive mutation, splicing mutation
  • Tree-based trimming: subtree trimming, recursive trimming
  • An ANTLR4 shim for parsing fuzzing test cases during the runtime
  • Documents about how to build the grammar mutator, specify custom grammars, and use the grammar mutator
  • Comprehensive test cases for unit testing
  • Sample grammar files and a script to convert nautilus's python grammar file

For more details about tree-based mutation, trimming, and grammar-based fuzzing, please refer to Nautilus paper.

A fuzzing writeup on Apache which uses the AFL++ Grammmar Mutator can be found here: https://securitylab.github.com/research/fuzzing-apache-1

Getting Started

Prerequisites

Before getting started, the following tools/packages should be installed:

sudo apt install valgrind uuid-dev default-jre python3
# ANTLR 4.13.2 needs Java 11 or later. In the Grammar-Mutator folder,
# `make antlr-jar` downloads the jar that matches the build. Or download it:
wget https://www.antlr.org/download/antlr-4.13.2-complete.jar
sudo cp -f antlr-4.13.2-complete.jar /usr/local/lib

If you do not leave the JAR file in the Grammar-Mutator directory or do not copy it to /usr/local/lib then you must specify the location via ANTLR_JAR_LOCATION=... in the make command.

Note that the grammar mutator is based on the latest custom mutator APIs in AFL++, so please use the latest dev or stable branch of AFL++.

git clone https://github.com/AFLplusplus/AFLplusplus.git
cd AFLplusplus
make distrib
sudo make install

Building the Grammar Mutator

Next you need to build the grammar mutator. To specify the grammar, you can use the GRAMMAR_FILE environment variable. The grammar can be one of two kinds:

  • A JSON grammar file. There are several in the grammars directory, such as json.json, ruby.json and http.json.
  • An ANTLR 4 grammar (.g4 files). You can use a grammar from grammars-v4 directly. Give all its .g4 files, for example the lexer and the parser grammar. Samples are in grammars/g4. Run make deps once before the first .g4 build: it installs the Python tools for the conversion into .venv.

Please refer to customizing-grammars.md for more details about both kinds, and to its ANTLR 4 section for the current limits of .g4 grammars. Note that pull requests with new grammars are welcome! :-)

# A JSON grammar
make GRAMMAR_FILE=grammars/ruby.json

# An ANTLR 4 grammar: one combined grammar ...
make deps
make GRAMMAR_FILE=grammars/g4/JSON.g4

# ... or a lexer grammar and a parser grammar
make GRAMMAR_FILE="grammars/g4/javascript/JavaScriptLexer.g4 grammars/g4/javascript/JavaScriptParser.g4"

Note that the shared library and grammar generator are named after the grammar file that is specified so you can have multiple grammars generated. The grammar name part is based on the filename with everything cut off after a underline, dash or dot, hency ruby.json will result in ruby and hence grammar_generator-ruby and libgrammarmutator-ruby.so will be created. For .g4 grammars, the name comes from the last file without Lexer or Parser, so the JavaScript example above gives javascript. You can specify your own naming by setting GRAMMAR_FILENAME=yourname as make option.

Now, you should be able to see two symbolic files libgrammarmutator-ruby.so and grammar_generator-ruby under the root directory. These two files actually locate in the src directory.

If you would like to fork the project and fix bugs or contribute to the project, you can take a look at building-grammar-mutator.md for full building instructions.

Instrumenting Fuzzing Targets

You can refer to sample-fuzzing-targets.md to build the example fuzzing targets.

Seeds

Before fuzzing the real program, you need to prepare the input fuzzing seeds. You can either:

  • Generating seeds for a given grammar
  • Using existing seeds

Using Existing Seeds

You can feed your own fuzzing seeds to the fuzzer, which does not need to match with your input grammar file. Assuming that the grammar mutator is built with grammars/ruby.json, which is a simplified Ruby grammar and does not cover all Ruby syntax. In this case, the parsing error will definitely occur. For any parsing errors, the grammar mutator will not terminate but save the error portion as a terminal node in the tree, such that we will not lose too much information on the original test case.

To e.g. use the test cases of the mruby project as input fuzzing seeds just pass the -i mruby/test/t to afl-fuzz when we run the fuzzer (if it has been checked out with git clone https://github.com/mruby/mruby.git in the current directory).

For a .g4 grammar, the mutator does not parse the seeds itself. Run grammar_parser-$GRAMMAR first. It parses the seeds and writes their trees, for example ./grammar_parser-javascript ./seeds ./trees. Then copy the trees folder as shown in Using Generated Seeds. Refer to the ANTLR 4 section for the skip reasons and for G4_SUPPORT_DIR.

Using Generated Seeds

grammar_generator can be used to generate input fuzzing seeds and corresponding tree files, following the grammar file that you specified during the compilation of the grammar mutator (i.e., GRAMMAR_FILE). You can control the number of generated seeds and the maximal size of the corresponding trees. Usually, the larger the tree size is, the more complex the corresponding input seed is. The generator does not write empty seeds or the same seed twice. If 100 tries in a row give no new seed, it stops early and writes fewer than <max_num> seeds.

# Usage
# ./grammar_generator-$GRAMMAR <max_num> <max_size> <seed_output_dir> <tree_output_dir> [<random seed>]
#
# <random seed> is optional
# e.g.:
./grammar_generator-ruby 100 1000 ./seeds ./trees

Afterwards copy the trees folder with that exact name to the output directory that you will use with afl-fuzz (e.g. -o out -S default):

mkdir -p out/default
cp -r trees out/default

Note that if you use multiple fuzzers (-M/-S sync mode) then you have to do this for all fuzzer instances, e.g. when the fuzzer instances are named fuzzer1 to fuzzer8:

for i in 1 2 3 4 5 6 7 8; do
  mkdir -p out/fuzzer$i
  cp -r trees out/fuzzer$i/
done

Fuzzing the Target with the Grammar Mutator!

Let's start running the fuzzer. The following example command is using Ruby grammar (from grammars/ruby.json) where mruby project has been cloned to the root Grammar-Mutator directory.

The default memory limit for child process is 75M in afl-fuzz. This may not be enough for some test cases, so it is recommended to increase it to 128M by adding an option -m 128.

export AFL_CUSTOM_MUTATOR_LIBRARY=./libgrammarmutator-ruby.so
export AFL_CUSTOM_MUTATOR_ONLY=1
afl-fuzz -m 128 -i seeds -o out -- /path/to/target @@

You may notice that the fuzzer will be stuck for a while at the beginning of fuzzing. One reason for the stuck is the large max_size (i.e., 1000) we choose, which results in a large size of test cases that increases the loading time. Another reason is the costly parsing operations in the grammar mutator. Since the input seeds are in string format, the grammar mutator needs to parse them into tree representations at first, which is costly. The large max_size passed into grammar_generator-$GRAMMAR does help us generate deeply nested trees, but it further increases the parsing overhead.

Changing the Default Configurations

Users can set the number of mutations per queue entry with these environment variables:

  • RANDOM_MUTATION_STEPS: the number of random mutations
  • RANDOM_RECURSIVE_MUTATION_STEPS: the number of random recursive mutations
  • SPLICING_MUTATION_STEPS: the number of splicing mutations
  • RULES_MUTATION_STEPS: the maximum number of rules mutations
  • TRIMMING_STEPS: the maximum number of trimming steps

By default, each of the first three mutation types runs 1000 times, and the rules mutation tries every other rule at every nonterminal node of the tree. With RULES_MUTATION_STEPS, the rules mutation tries at most that many of these node and rule pairs, sampled uniformly across the whole tree and tried in tree order. The trimming of a new queue entry tries every nonterminal node and every recursion of its tree, from the root down. With TRIMMING_STEPS, it stops after that many tries and keeps what it has trimmed by then. Change them as follows, if needed. :)

export RANDOM_MUTATION_STEPS=10000
export RANDOM_RECURSIVE_MUTATION_STEPS=10000
export SPLICING_MUTATION_STEPS=10000
export RULES_MUTATION_STEPS=10000
export TRIMMING_STEPS=10000
export AFL_CUSTOM_MUTATOR_LIBRARY=./libgrammarmutator-ruby.so
export AFL_CUSTOM_MUTATOR_ONLY=1
afl-fuzz -m 128 -i seeds -o out -- /path/to/target @@

Contact & Contributions

We welcome any questions and contributions! Feel free to open an issue or submit a pull request! Please read CONTRIBUTING.md before you open a pull request.

Branches and Releases

stable is the only long-lived branch. Send all pull requests to stable.

The dev branch is abandoned. It stays in the repository for history, but it does not get new changes.

Release Please makes the releases from stable. See CHANGELOG.md and the GitHub releases for the changes in each version.

About

A grammar-based custom mutator for AFL++

Topics

Resources

Contributing

Stars

278 stars

Watchers

3 watching

Forks

Releases

Used by

Contributors

Languages