Structure-Aware Fuzzing
Advanced Fuzzing Techniques · VR Analysis & Discovery track
8 min read
In this module
Fuzzing Beyond Random Bytes
Coverage-guided fuzzers like AFL++ chew through flat binary formats happily enough. Throw a structured input at them and they choke. If the target wants a valid PDF, a properly framed protocol message, or syntactically correct source code, random byte flips almost never make it past the front gate. Structure-aware fuzzing sidesteps the problem by generating inputs that respect the target's format, then mutating inside that structure.
The Problem with Dumb Mutation
Take a JSON parser. The input {"key": "value"} is 16 bytes. A random byte flip might produce {"key": "vblue"} (still valid JSON, fine) or {"key"< "value"} (rejected at the syntax check). Most random mutations land in that second bucket. They get bounced in the first few lines of the parser and never touch the deeper logic where interesting bugs sit.
Structure-aware fuzzing generates inputs like {"key": "value", "nested": {"a": [1, null, true, "very long string..."]}} — syntactically valid, but loaded with deep nesting, type mixing, and edge-case numbers that dumb mutation would take geological time to stumble onto.
Grammar-Based Fuzzing
Grammar-based fuzzers use a formal grammar to generate inputs. The grammar defines the valid structure of the input format, and the fuzzer produces random valid derivations:
// Simplified JSON grammarjson := object | arrayobject := '{' members? '}'members := pair (',' pair)*pair := string ':' valuearray := '[' elements? ']'elements := value (',' value)*value := string | number | object | array | 'true' | 'false' | 'null'string := '"' characters '"'number := '-'? digits ('.' digits)?The fuzzer walks the grammar, rolling dice at each production rule. Bias the choices towards deep nesting, long arrays, edge-case numbers (0, -0, MAX_INT), and weird character sequences, and you get inputs that exercise the parser's handling of complex-but-valid data.
Tools for grammar-based fuzzing:
Dharma (Mozilla) takes grammar files and emits random outputs. Originally built for browser fuzzing.
Domato (Google Project Zero) is purpose-built for DOM and JavaScript fuzzing. It generates valid HTML/CSS/JS that hammers browser rendering and scripting engines.
Nautilus marries grammar-based generation to coverage-guided feedback, so you get the best of both.
Grammar-only fuzzing generates valid inputs but has no idea which ones reach new code. Coverage-only fuzzing knows what's interesting but flounders trying to produce a syntactically valid input from scratch. Tools like Nautilus, and AFL++ with custom mutators, fuse the two: the grammar produces and mutates valid inputs, and coverage feedback decides which mutations are worth keeping around.
Protocol Buffer Mutators
For targets that use Protocol Buffers (protobuf) for serialisation, libprotobuf-mutator provides structure-aware mutation:
// Fuzz harness using libprotobuf-mutator#include "src/libfuzzer/libfuzzer_macro.h"#include "my_protocol.pb.h"
DEFINE_PROTO_FUZZER(const MyMessage& msg) { // msg is a valid protobuf message, randomly mutated // but always structurally valid std::string serialized = msg.SerializeAsString(); process_message(serialized.data(), serialized.size());}The mutator knows protobuf's type system. Mutations stay schema-valid: adding or dropping fields, swapping values inside their type constraints, nesting submessages legally.
The same trick works for any schema-driven format. Thrift, FlatBuffers, Cap'n Proto, ASN.1 — all benefit from schema-aware mutation.
Custom Mutators for Complex Formats
For formats without an existing mutator, you can write custom mutators for AFL++ or libFuzzer:
// AFL++ custom mutator for a simple TLV (Type-Length-Value) protocol#include "afl-fuzz.h"#include <stdlib.h>#include <string.h>
typedef struct { uint8_t *out; // our own output buffer: AFL++'s buf is not ours to write size_t out_cap;} tlv_state;
void *afl_custom_init(afl_state_t *afl, unsigned int seed) { (void)afl; srand(seed); return calloc(1, sizeof(tlv_state));}
// Little-endian 16-bit fields via memcpy: no unaligned pointer castsstatic uint16_t get16(const uint8_t *p) { uint16_t v; memcpy(&v, p, 2); return v; }static void put16(uint8_t *p, uint16_t v) { memcpy(p, &v, 2); }
// Called by AFL++ to mutate an inputsize_t afl_custom_fuzz(void *data, uint8_t *buf, size_t buf_size, uint8_t **out_buf, uint8_t *add_buf, size_t add_buf_size, size_t max_size) { (void)add_buf; (void)add_buf_size; tlv_state *st = data; size_t n = buf_size < max_size ? buf_size : max_size;
if (n > st->out_cap) { // grow our buffer if needed uint8_t *p = realloc(st->out, n); if (!p) { *out_buf = buf; return 0; } // 0 = skip this mutation st->out = p; st->out_cap = n; } uint8_t *out = st->out; memcpy(out, buf, n); // mutate the copy, never buf
// Walk the TLV messages and mutate some of them size_t offset = 0; while (offset + 4 <= n) { uint16_t length = get16(out + offset + 2);
switch (rand() % 4) { case 0: // Mutate the type field put16(out + offset, (uint16_t)(rand() % 256)); break; case 1: // Mutate the length field (might cause overflow!) put16(out + offset + 2, (uint16_t)(rand() % 65536)); break; case 2: // Mutate payload bytes if (length > 0 && offset + 4 + length <= n) out[offset + 4 + (rand() % length)] = (uint8_t)(rand() % 256); break; case 3: // Keep unchanged break; } offset += 4 + (size_t)length; // walk by the original length }
*out_buf = out; return n;}
void afl_custom_deinit(void *data) { tlv_state *st = data; free(st->out); free(st);}This mutator knows the input is a series of TLV messages and mutates within that frame. It will happily emit invalid lengths to probe error handling, while keeping the surrounding TLV scaffolding intact. Note where it writes: AFL++ hands you buf as the current test case, and the mutated result goes into a buffer the mutator owns and returns through out_buf. The 16-bit fields are read and written with memcpy, because casting buf + offset to uint16_t * is an unaligned access the C standard doesn't allow and some CPUs fault on.
Real formats often add one more wall: a checksum or CRC over the message. Every random byte flip breaks it, so the parser rejects the input before any TLV is looked at. The runner fuzzes a toy TLV format with a CRC32 trailer twice with the same single-byte mutations: once plainly, once with a mutator that recomputes the CRC afterwards. The bug needs a type-7 record whose first payload byte is 0xff. Predict how often each fuzzer gets past the checksum.
libFuzzer's Custom Mutator API
libFuzzer (LLVM's built-in fuzzer) provides a clean API for custom mutators:
// Custom mutator for libFuzzerextern "C" size_t LLVMFuzzerCustomMutator( uint8_t *data, size_t size, size_t max_size, unsigned int seed) {
// Parse the input as your format MyFormat parsed; if (!parsed.parse(data, size)) { // If input is invalid, generate a valid one from scratch return generate_valid_input(data, max_size, seed); }
// Mutate the parsed structure std::mt19937 rng(seed); mutate_structure(&parsed, rng);
// Serialize back return parsed.serialize(data, max_size);}
// The actual fuzz targetextern "C" int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { process_input(data, size); return 0;}Domato for DOM Fuzzing
Domato earns its own section because it's been responsible for hundreds of browser vulnerabilities. It generates random-but-valid HTML, CSS, and JavaScript that exercises rendering and DOM manipulation:
# Domato generates complex, valid HTML like:# <html># <body># <svg><animate attributeName="d" values="M0,0 L100,100"/># <foreignObject># <div style="columns: 3; column-fill: auto"># <span style="float: left">text</span># </div># </foreignObject># </svg># </body># </html>That snippet is valid HTML, but it touches SVG animation, foreign object embedding, multi-column CSS layout, and floats all in one place. The combination stresses the layout engine in ways no real-world page ever would. Bugs in those interactions have historically been turned into remote code execution.
Choosing the Right Fuzzing Approach
The choice between dumb mutation and structure-aware fuzzing depends on the target:
Use dumb mutation (AFL++ default) when:
- The input is flat binary data without strong structural requirements
- The target accepts a wide range of inputs (image decoders, compression algorithms)
- You have a good seed corpus that already passes validation
Use structure-aware fuzzing when:
- The target rejects most random inputs immediately (protocol parsers, language interpreters)
- The input format has mandatory structure (headers, checksums, framing)
- You want to test deep parsing logic that random mutation cannot reach
Combine both when:
- The format has both structured and unstructured components
- You want to hit both the format-validation paths and the payload-processing paths
- You have the engineering resources to write a custom mutator
Writing a custom mutator burns engineer-days. Before you invest, gauge how much of the target is reachable with dumb mutation. If AFL++ with a good dictionary and corpus already hits 60%+ of the parsing code, a custom mutator probably won't pay back. If coverage flatlines at 10% because every input gets bounced for format violations, structure-aware fuzzing will smash through that ceiling.