LAAF — Language-Aware AST Fuzzing Framework

LAAF parses structured inputs into AST/trees, applies semantically-aware mutations on the tree structure, and dumps valid outputs back — achieving higher coverage than vanilla byte-level fuzzing.

Validation: 3/4 projects show LAAF > Baseline. Improvement scales with harness complexity: +14.3% edges (cmark), +5.4pp lines (expat), +0.5pp lines (libxml2).

---

Multi-Project Validation Results

Project	Code	Type	Baseline	LAAF	Δ	Status
cmark	10K C	Markdown	edges 1,979	2,309	+14.3%	✅ EXP-001
expat	12K C	XML (OT0)	lines 34.5%	40.0%	+5.4pp	✅ EXP-002
libxml2	70K C	XML (OT0)	lines 11.2%	11.7%	+0.5pp	✅ EXP-003
libyaml	5K C	YAML (OT1)	lines 3,688	3,688	±0	⚠️ harness too simple
RE2	3.7K C++	Regex	—	—	0 vulns	✅ 570M+ execs
json-c	1.5K C	JSON	—	—	PoC	✅ validated

Key finding: LAAF advantage monotonically increases with harness complexity (5 API paths → +14.3%, 4 modes → +5.4pp, 1 call → ±0).

---

Projects

Project	Type	Attack Surfaces	Mutators	Execs	Bugs Found
RE2	Regex engine	14	15 AST + 5 Mut4All	570M+	0 (8 tool bugs fixed)
libyaml	YAML parser	12	15 AST + 3 MetaMut + 1 IssueMut + 5 Mut4All	4.2B+	0 (6 fuzzer bugs fixed)
json-c	JSON parser	1	12 AST	—	0

---

Mutation Strategies

Strategy	Description	Mutators
Fuzz4All	26 attack surfaces across 3 projects, pipeline decomposition	—
AST Mutators	Direct tree node manipulation (parse→mutate→dump→validate)	M1-M12
MetaMut	LLM reads source → generates domain-specific mutators	M13-M18
IssueMut	Bug report mining → targeted mutators from CVE history	M19
Mut4All	LLM auto-generates mutators from historical bug reports	M20-M24
Combined	M_a → dump → reparse → M_b (11× burst after single-mutation saturation)	—

---

Quick Start

# RE2
clang++ -stdlib=libc++ -std=c++17 -O2 -g \
    -fsanitize=fuzzer,address,undefined \
    -I/tmp/re2 -I. -I/usr/local/libcxx/include \
    -o build/laaf_fuzzer laaf_fuzzer_full.cc \
    build/laaf_adapter.o build/laaf_mutator.o build/laaf_mutator_ext.o \
    /tmp/re2/obj/libre2.a -lc++ -lc++abi -pthread

# libyaml
cd libyaml
clang++ -std=c++17 -O2 -g -fsanitize=fuzzer,address,undefined \
    -I. -o build/laaf_yaml_fuzzer laaf_yaml_fuzzer.cc \
    build/laaf_yaml_adapter.o -lyaml

---

Directory Structure

laaf/
├── README.md
├── Dockerfile                          # Ubuntu 24.04 fuzzing environment
├── .gitignore
│
├── laaf_adapter.{h,cc}                 # Framework core: RE2 adapter (6 APIs)
├── laaf_mutator.{h,cc}                 # M1-M8 core mutators
├── laaf_mutator_ext.{h,cc}             # M9-M12 extended mutators
├── laaf_mutator_llm.{h,cc}             # M13-M15 MetaMut (LLM-generated)
├── laaf_fuzzer_full.cc                 # Main fuzzer (CustomMutator + CrossOver)
│
├── src/re2/                            # RE2-specific attack surfaces (13 fuzzers)
├── libyaml/                            # libyaml adapter + 12 fuzzers + Mut4All
├── json/                               # json-c adapter + 12 mutators
├── afl/                                # AFL++ harness + custom mutator
│
├── tools/                              # Offline generators + verification
│   ├── generate_mutants_v15.cc         #   RE2 offline 15-mutator generator
│   ├── verify_pipeline.cc              #   12-invariant divide-and-conquer
│   └── coverage_replay.cc              #   Coverage replay
│
├── experiments/                        # A/B validation data
│   ├── FINAL_REPORT.md                 #   Complete results summary
│   └── cmark/                          #   EXP-001: cmark raw data
│
├── docs/                               # Design documents
│   ├── AST_MUTATOR_SURVEY.md           #   50+ mutator designs
│   ├── decompose_for_verification.md   #   Methodology
│   └── spec.md
│
├── scripts/                            # Build & automation
├── seeds/                              # Sample seed corpora
└── vulnerabilities/                    # RE2 bug reports

---

Key Design Decisions

1. Deep clone via dump→reparse — eliminates UAF/corruption from shallow Incref
2. Combined mutations (M_a→M_b) — 11× burst when single mutations saturate
3. Fuzz4All — separate fuzzer per pipeline layer, upstream generates valid inputs for downstream
4. Consistency validation — is_consistent() check before every dump, discard corrupt trees
5. Offline + Online — offline batch mutation generates seed pool, online fuzzer explores neighborhood

---

Contributing

LAAF is designed to be extensible. To add a new target project:

1. Implement the 6 adapter APIs (parse, clone, dump, collect_slots, replace, free)
2. Implement 8-15 mutators on the target's tree structure
3. Write a libFuzzer harness with CustomMutator + CustomCrossOver
4. Run A/B validation against vanilla libFuzzer (see experiments/ for protocol)

License

MIT