# Nautilus

Nautilus is the grammar-based fuzzer published by Aschermann, Schumilo, Blazytko, Gawlik, and Holz at NDSS 2019 (TU Berlin / Ruhr-Uni Bochum). It pairs a context-free grammar with coverage feedback: inputs are stored as derivation *trees* rather than byte strings, mutations rewrite subtrees, and the corpus is scheduled by coverage like AFL.

The structural choice is what makes it work — a grammar fuzzer that stores inputs as strings ends up byte-mutating them and degrading to AFL with extra steps. Storing the tree means a single mutation is "replace this Number subtree with another Number subtree," which keeps the input structurally valid by construction.

## Where it shows up

- Embedded as the grammar engine inside other fuzzers (Honggfuzz extensions, AFL++ via custom mutators, [[gosentry-go-fuzzing-fork|gosentry]]'s grammar mode)
- The grammar-format conventions Nautilus introduced — JSON arrays of `[non-terminal, production]` rules — have been picked up by several downstream tools, including gosentry's `--grammar` mode

## Grammar format

The standard form is a JSON array of two-element arrays, where the first element is the non-terminal name and the second is the production (with `{Name}` referring to other non-terminals). See [[grammar-based-fuzzing]] for the worked example.