Grammar Mutator (Gramatron)

Relevant source files

The following files were used as context for generating this wiki page:

• custom_mutators/gramatron/README.md
• custom_mutators/gramatron/gramfuzz.c
• custom_mutators/gramatron/preprocess/construct_automata.py
• custom_mutators/gramatron/build_gramatron_mutator.sh
• custom_mutators/gramatron/gramfuzz.h
• src/afl-fuzz.c

Gramatron is a coverage-guided, grammar-aware custom mutator for AFL++. It utilizes a pre-processed "grammar automaton" to generate and mutate inputs that conform to a specified grammar, making it effective for fuzzing targets with structured inputs. Unlike other mutators that operate on a byte-level, Gramatron operates on the abstract structure of the input, as defined by its grammar.

This approach allows for more intelligent and syntactically valid mutations, which can be more effective at exploring deeper states in the target application. Gramatron is provided as one of the "production-ready" custom mutators within the AFL++ repository.

Sources: custom_mutators/gramatron/README.md, custom_mutators/README.md

Setup and Compilation

Gramatron must be compiled before it can be used with afl-fuzz. The compilation process involves building its dependency, json-c, and then compiling the mutator itself into a shared library (gramatron.so).

Build Process

A shell script, build_gramatron_mutator.sh, automates the entire process.

1. Sanity Checks: The script first verifies that necessary tools like git, make, and a C compiler are present. It also ensures it's not being compiled with an afl- compiler wrapper.
2. Dependency Fetching: It checks out and builds the json-c library, which is a dependency for parsing the automaton files.
3. Compilation: Finally, it compiles gramfuzz.c and its helper files into gramatron.so, linking against the json-c library and AFL++'s internal objects.

The following diagram illustrates the build flow:

To compile, execute the following command from the custom_mutators/gramatron/ directory:

./build_gramatron_mutator.sh

Sources: custom_mutators/gramatron/build_gramatron_mutator.sh

Usage

To use Gramatron, you must configure afl-fuzz with several environment variables.

Variable	Description	Example
AFL_CUSTOM_MUTATOR_LIBRARY	Path to the compiled gramatron.so shared library.	AFL_CUSTOM_MUTATOR_LIBRARY=./gramatron.so
GRAMATRON_AUTOMATION	Path to the generated grammar automaton JSON file.	GRAMATRON_AUTOMATION=grammars/ruby/source_automata.json
AFL_CUSTOM_MUTATOR_ONLY	(Recommended) If set to 1, AFL++ will only use the Gramatron mutator, disabling its built-in mutation strategies.	AFL_CUSTOM_MUTATOR_ONLY=1
AFL_DISABLE_TRIM	(Recommended) If set to 1, this disables AFL++'s input trimming, which can corrupt grammar-valid inputs.	AFL_DISABLE_TRIM=1

Example Command

export AFL_DISABLE_TRIM=1
export AFL_CUSTOM_MUTATOR_ONLY=1
export AFL_CUSTOM_MUTATOR_LIBRARY=./gramatron.so
export GRAMATRON_AUTOMATION=grammars/ruby/source_automata.json
afl-fuzz -i in -o out -- ./target

Sources: custom_mutators/gramatron/README.md

Grammar and Automaton Generation

Gramatron requires a grammar to be pre-processed into a Pushdown Automaton (PDA) stored in a JSON file. This process is handled by a Python script.

1. Grammar Specification

First, the context-free grammar (CFG) must be defined in a JSON format. The file should contain the rules of the grammar and specify the start symbol.

Example source.json structure:

{
  "Start": ["<PROGRAM>"],
  "<PROGRAM>": ["'function' <NAME> '(' ')' '{' <BODY> '}'"],
  "<NAME>": ["'foo'"],
  "<BODY>": ["'return' '0' ';'"]
}

Note: This is a simplified example. The actual format is visible in custom_mutators/gramatron/grammars/js/source.json.

Sources: custom_mutators/gramatron/README.md, custom_mutators/gramatron/preprocess/construct_automata.py

2. Automaton Construction

The construct_automata.py script converts the grammar JSON into a PDA representation that Gramatron can use. A wrapper script, prep_automaton.sh, is provided for convenience.

Command:

./preprocess/prep_automaton.sh <grammar_file> <start_symbol> [stack_limit]

• <grammar_file>: Path to the source.json grammar file.
• <start_symbol>: The starting non-terminal of the grammar (e.g., PROGRAM).
• [stack_limit]: An optional integer. If the grammar contains self-embedding (recursive) rules, this parameter limits the recursion depth to prevent infinitely large inputs. A recommended starting value is 5.

This script generates an _automata.json file in the same directory as the source grammar.

Sources: custom_mutators/gramatron/README.md, custom_mutators/gramatron/preprocess/construct_automata.py

3. Sanity Checking

After generation, you can use the provided test binary to ensure the automaton generates valid inputs.

./test SanityCheck <automaton_file>

Sources: custom_mutators/gramatron/README.md

Generation Workflow

The following diagram shows the process of converting a grammar file into a usable automaton.

Sources: custom_mutators/gramatron/preprocess/construct_automata.py, custom_mutators/gramatron/README.md

Architecture and Core Components

Gramatron integrates with AFL++ through the custom mutator API. Its core logic is implemented in C and relies on several key data structures and functions.

Data Structures

The primary data structures define the automaton and the mutator's state.

• my_mutator_t: The main state struct for the mutator. It holds pointers to the AFL++ state, buffers, and the original and mutated automaton walks.
• Array: A dynamic array representing an input as a sequence of terminals (an "automaton walk").
• terminal: A single token or symbol in the generated input, associated with a state and trigger from the PDA.
• state: A state in the Pushdown Automaton (PDA).
• trigger: A transition rule from a state, containing a terminal symbol and a destination state.

Sources: custom_mutators/gramatron/gramfuzz.h, custom_mutators/gramatron/gramfuzz.c

Initialization and Fuzzing Loop

The interaction with AFL++ is managed through standard custom mutator API functions.

Sources: custom_mutators/gramatron/gramfuzz.c, src/afl-fuzz.c

Core Functions

• afl_custom_init: Called once at startup. It allocates the my_mutator_t struct, reads the GRAMATRON_AUTOMATION environment variable, and calls create_pda to parse the automaton JSON and build the in-memory PDA.
• create_pda: Reads the automaton JSON file and constructs the graph of state and trigger structs in memory.
• afl_custom_fuzz: The main mutation engine. It is called by AFL++ to generate a new test case. It cycles through several mutation strategies.
• afl_custom_queue_get: Called when AFL++ selects an input from the queue. Gramatron reads the corresponding .aut file (which stores the input's automaton walk), builds a statemap (a map of states to their occurrences in the walk), and identifies recursive features to prepare for mutation.
• afl_custom_queue_new_entry: Called when a mutated input finds new coverage. Gramatron saves the mutated_walk to a new .aut file, ensuring the grammar-aware representation is persisted for future mutation rounds.
• unparse_walk: Converts an Array (automaton walk) back into a flat byte buffer that can be fed to the target application.

Sources: custom_mutators/gramatron/gramfuzz.c:113-393

Mutation Strategies

afl_custom_fuzz cycles through four primary mutation strategies to generate new inputs.

Strategy	Function	Description
Random Mutation	performRandomMutation	Performs a random mutation on the automaton walk.
Recursive Mutation	doMult	Exploits recursive structures identified in the grammar to expand or duplicate sections of the input. This is only active if recursive features are found (data->recurlen > 0).
Splice Mutation	performSpliceOne	Splices a part of the current input with a part from another randomly chosen input from the AFL++ queue.
Generation	gen_input	Generates a completely new input from scratch based on the grammar automaton.

The mutator index data->mut_idx is used to cycle through these strategies.

Sources: custom_mutators/gramatron/gramfuzz.c:191-240