Map
↑Supply Chain Security

Grammar-Based Fuzzing

Wiki conceptfuzzingsecuritytesting ↳ show in map Markdown
title
Grammar-Based Fuzzing
type
concept
summary
Generate fuzzing inputs from a context-free grammar instead of random bytes, so inputs survive early parsing stages and exercise downstream logic
parent
supply-chain-security
tags
fuzzing, security, testing
created
2026-05-12
updated
2026-05-12

A coverage-guided fuzzer that produces random bytes will spend most of its CPU watching the target reject malformed input at the lexer. For any target with a non-trivial input format — JSON, protobuf, ASN.1, an RPC frame, a tx encoding — the interesting code lives several stages past the bytes. Grammar-based fuzzing fixes this by generating inputs from a context-free grammar so they're structurally valid by construction, and mutating within the grammar (rule rewrites, subtree replacements) instead of at the byte level.

The grammar is typically expressed as a list of production rules. Nautilus, AFL++ in grammar mode, and CSmith all use variants of this idea. A small JSON example from gosentry's docs:

[
  ["Json", "\\{\"postOfficeBox\":{Number}\\}"],
  ["Number", "{Digit}"],
  ["Number", "{Digit}{Number}"],
  ["Digit", "0"], ["Digit", "1"], ...
]

Every input is valid JSON with the expected shape, freeing the fuzzer to mutate the number the wrapping syntax wraps.

Where it pays

  • Compilers, parsers, query engines — anything whose interesting bugs live past the front end
  • Differential testing across multiple implementations of the same spec (see differential-fuzzing) — both implementations need valid input to disagree about
  • Protocol conformance fuzzing — the bytes have to look like the protocol or the receiver disconnects

Where it doesn't help

  • Lexer / parser bugs themselves — random bytes are a better fuzzer for the front end
  • Targets whose input is genuinely unstructured (image pixel data, raw audio)
  • Cases where the grammar is the spec under test and writing it is half the work

Combining strategies

Production fuzzing campaigns usually mix grammar-based generation with byte-level mutation: grammar for the new-corpus seeding pass and the "produce a valid base" step, then byte-level mutations to find tokenizer/parser edge cases. Coverage feedback works across both because the instrumentation is in the target, not in the input generator.

Relation to structure-aware fuzzing

structure-aware-fuzzing is the in-language equivalent: instead of a grammar, the fuzzer is told the Go/Rust/C++ type of the input and constructs an instance directly. Grammar-based fuzzing is the right tool when the input is bytes on the wire (a serialized protocol, source code); structure-aware is the right tool when the input is a value the API takes (a struct, a typed record). gosentry supports both.

Linked from