Lesson 12.6 — Grammar-based and coverage-guided fuzzing, and metamorphic testing (EMI)

Techniques: grammar-based fuzzing (random derivations from a grammar, from Hanford's syntax machine to Zeller's GrammarFuzzer); coverage-guided fuzzing with libFuzzer (feedback from code coverage, mutation, corpus); equivalence modulo inputs (EMI), a metamorphic oracle for compilers (Le, Afshari and Su 2014) · Pebble implements: ★ E4 (stretch) fuzzes your Chapter 4 parser with libFuzzer; Chapter 24 fuzzes pebblec with a Pebble program generator; this lesson's real-world boxes fuzz a toy parser and prune a C program · Drill: none (see §9) · Prerequisites: Lesson 12.5, grammars from Ch 2 · Time: 4–5 hours

Lesson 12.5's generators know the whole language. Two cheaper ideas get surprisingly far. A grammar alone already produces syntactically valid inputs — enough to exercise a parser. And a fuzzer that watches which code an input reached can evolve random bytes into inputs that pass deep checks, with no knowledge of the format at all; libFuzzer finds the buffer overflow of this lesson's toy parser in under 8 000 executions. Finally, EMI gives a compiler a test oracle without a second compiler: delete code that did not run, and the program must still produce the same output.

1. Problem and motivation

Grammar-based fuzzing

The front end of a compiler rejects almost every random byte string at the first token, so random bytes test only the lexer. Hanford's syntax machine at IBM (1970) generated random programs from a grammar to test PL/I compilers [Han70]; Purdom showed how to generate a small set of sentences that together use every production (1972) [Pur72]. Modern tools (LangFuzz, Grammarinator, Zeller et al.'s Fuzzing Book GrammarFuzzer [FB-Grammar]) add probabilities and size control so that random derivations terminate and cover the grammar.

Coverage-guided fuzzing

Blind random testing rarely passes a check like if (s[0] == '(' && isdigit(s[1]) && s[2] == ')'): the chance is \(2^{-8} \cdot 10/256 \cdot 2^{-8}\) per input. Coverage-guided fuzzers (AFL, libFuzzer, honggfuzz) instrument the program to record which edges or comparisons an input exercised and keep any input that reached something new; mutations of kept inputs then attack the next check. libFuzzer runs in-process: the user writes LLVMFuzzerTestOneInput(data, size), compiles with clang -fsanitize=fuzzer (SanitizerCoverage instrumentation + the libFuzzer driver), and usually adds AddressSanitizer to turn silent memory errors into crashes [LLVM-LibFuzzer, Ser16]. LLVM fuzzes its own parsers and passes this way (llvm-opt-fuzzer, llvm-isel-fuzzer, clang-fuzzer).

Equivalence modulo inputs (EMI)

Differential testing needs a second compiler and a well-defined program. Le, Afshari and Su's EMI [LAS14] needs neither: run program \(P\) on input \(I\), record which statements executed, and produce variants by deleting (or changing) statements that did not execute. Every variant must behave like \(P\) on \(I\), so a compiler that gives different outputs for \(P\) and a variant is wrong. Their tool, Orion, reported 147 confirmed, unique bugs in GCC and LLVM in eleven months of testing [LAS14]. EMI is a metamorphic relation: a known relation between the outputs of related inputs, instead of known outputs.

2. Definitions and algorithms

Grammar-based fuzzing

Definition 12.6.1 (Probabilistic grammar, random derivation)

A probabilistic grammar is a context-free grammar \(G = (N, T, P, S)\) (house notation, NOTATION.md §5) with, for each \(A \in N\), a probability distribution \(\pi_A\) over the productions \(A \to \alpha\). A random leftmost derivation starts from \(S\) and repeatedly replaces the leftmost nonterminal \(A\) by \(\alpha\) drawn from \(\pi_A\). For a single nonterminal \(A\), let \(\xi\) be the number of occurrences of \(A\) on the right-hand side of the drawn production: the mean offspring is \(m = \mathbb{E}[\xi]\) and the offspring generating function is \(f(s) = \mathbb{E}[s^{\xi}]\).

Algorithm 12.6.2 (Three-phase grammar fuzzer, after GrammarFuzzer)

• Input: grammar \(G\); bounds \(k_{\min} \le k_{\max}\) on the number of open nonterminals; a random source.
• Output: a sentence \(w \in L(G)\).
• Precondition: every nonterminal derives some terminal string (no useless symbols).
• Postcondition: \(w \in L(G)\); the derivation terminates (phase 3 closes every open nonterminal; Theorem 12.6.7 shows why it is needed).
• Invariant: the current derivation tree is a valid partial derivation of \(G\); cost(A) is the size of the smallest terminal tree for \(A\) (precomputed by a fixed point).

function Fuzz(G, kmin, kmax):
    t ← tree with root S (unexpanded)
    while open(t) < kmin:                  # phase 1: grow — pick expansions of maximal cost
        expand a random open node with an expansion of maximal cost
    while open(t) < kmax and open(t) > 0:   # phase 2: random — pick uniformly among expansions
        expand a random open node with a uniformly random expansion
    while open(t) > 0:                      # phase 3: close — pick expansions of minimal cost
        expand a random open node with an expansion of minimal cost
    return the leaves of t, left to right

Coverage-guided fuzzing

Definition 12.6.3 (Features, corpus)

Instrumentation maps every execution of the target on an input \(x\) to a finite set of features \(\Phi(x)\): covered edges, edge hit-count buckets (1, 2, 3, 4–7, 8–15, ...), and comparison operands. The corpus \(\mathcal{C}\) is a set of inputs; \(\Phi(\mathcal{C}) = \bigcup_{x \in \mathcal{C}} \Phi(x)\). An input is interesting if \(\Phi(x) \not\subseteq \Phi(\mathcal{C})\).

Algorithm 12.6.4 (libFuzzer's main loop, simplified from Fuzzer::Loop)

• Input: the target LLVMFuzzerTestOneInput; an initial corpus (possibly empty); a seed; limits.
• Output: a crashing input (saved as crash-<sha1>), or the final corpus when a limit is reached.
• Precondition: the target is deterministic and does not keep state between calls.
• Postcondition: every corpus element added was interesting when added; \(\Phi(\mathcal{C})\) never shrinks.
• Invariant: \(\Phi(\mathcal{C})\) equals the union of the features of all inputs executed so far.

function Fuzz(target, C, seed):
    rng ← Random(seed)
    run target on each x ∈ C (or on the empty input); Φ ← ∪ Φ(x)          # "INITED"
    loop until a limit:
        x ← ChooseFromCorpus(C, rng)                   # entropic schedule: favour inputs with rare features
        y ← x
        repeat r times (r random, up to MutationDepth):
            y ← Mutate(y, rng)   # ShuffleBytes, EraseBytes, InsertByte, ChangeBit, ChangeByte, CopyPart,
                                 # CrossOver with another corpus input, CMP (insert a compared constant),
                                 # PersAutoDict / ManualDict (insert a dictionary word)
        result ← run target(y) with the sanitizers
        if result is a crash or sanitizer report: save y as crash-<sha1(y)>; stop
        if Φ(y) ⊄ Φ: C ← C ∪ {y}; Φ ← Φ ∪ Φ(y)                              # "NEW"
        else if y is shorter than a corpus input with the same unique features: replace it   # "REDUCE"

Equivalence modulo inputs (EMI)

Definition 12.6.5 (Profile, EMI variant)

Let \(P\) be a deterministic program in a structured language with statements \(s \in \mathrm{Stmt}(P)\) and \(I\) an input on which \(P\) terminates and is well defined. The profile \(\mathrm{cov}_I(P) \subseteq \mathrm{Stmt}(P)\) is the set of statements executed at least once on \(I\). A program \(P'\) is an EMI variant of \(P\) for \(I\) if \(P'\) is obtained by replacing some statements \(s \notin \mathrm{cov}_I(P)\) by the empty statement ; (more generally: by any statement, as long as the result is well formed). \(P\) and \(P'\) are equivalent modulo \(I\) if \(\llbracket P \rrbracket(I) = \llbracket P' \rrbracket(I)\).

Algorithm 12.6.6 (EMI testing, after Orion)

• Input: a compiler \(C\); a program \(P\) and an input \(I\) (e.g. a Csmith program, which ignores its input); a pruning probability \(p\); a number of variants \(V\).
• Output: a pair \((P, P')\) on which \(C\)'s executables disagree, or "no difference".
• Precondition: \(P\) is well defined on \(I\) (Definition 12.5.4).
• Postcondition: every reported pair exposes a miscompilation of \(P\) or of \(P'\) (Theorem 12.6.9).
• Invariant: every generated \(P'\) is an EMI variant of \(P\) for \(I\).

function Orion(C, P, I, p, V):
    cov ← statements executed when running P on I (compile with coverage, run, read the profile)
    expected ← run(C(P), I)
    for v ← 1 to V:
        P' ← P
        for s in Stmt(P) \ cov:                        # unexecuted statements only
            with probability p: replace s by ";" in P'
        if run(C(P'), I) ≠ expected: return (P, P')     # then reduce the pair (Lesson 12.7)
    return "no difference"

3. Worked examples

A random derivation. For the one-nonterminal grammar \(E \to E + E \mid \texttt{x}\) with \(\pi_E(E \to E + E) = p\), a derivation is a Galton–Watson branching process: each \(E\) has \(\xi = 2\) children with probability \(p\) and \(\xi = 0\) otherwise, so \(m = 2p\) and \(f(s) = (1-p) + p s^2\). With \(p = 1/3\) (\(m = 2/3\)), draws \(E+E\), x, \(E+E\), x, x give the trace

step	sentential form	open \(E\)s
0	\(E\)	1
1	\(E + E\)	2
2	\(\texttt{x} + E\)	1
3	\(\texttt{x} + E + E\)	2
4	\(\texttt{x} + \texttt{x} + E\)	1
5	\(\texttt{x} + \texttt{x} + \texttt{x}\)	0

and Theorem 12.6.7 says every such derivation ends with probability 1. With \(p = 2/3\) (\(m = 4/3\)) it does not: the extinction probability is the smallest root of \(f(s) = s\), i.e. of \(\tfrac{2}{3}s^2 - s + \tfrac{1}{3} = 0\), which is \(s = 1/2\) — half of the derivations never end, which is why Algorithm 12.6.2 switches to minimal-cost expansions (phase 3).

Coverage feedback on the toy parser (the real-world box in §7). The parser accepts (k) followed by \(k\) items; the bug is an array of 4 items written without checking \(k \le 4\). libFuzzer's log shows the corpus growing one feature at a time:

execution	event	coverage (edges)	corpus (inputs / bytes)
2	INITED	2	1 / 1
9, 234, 246	NEW	3, 4, 5	2 → 4 inputs
277 … 6518	REDUCE	5 → 8	shorter inputs with the same features replace longer ones
6565, 6576, 7747	NEW	11, 12, 13	7 → 9 inputs
after 7747	crash	—	(5) + 5 bytes: the fifth write overflows items[4]

Coverage grows in small steps, each step an input that passes one more check of the parser, and each kept input is the starting point of the next mutations. A blind random tester needs, for the first three bytes alone, \(1/(\tfrac{1}{256} \cdot \tfrac{10}{256} \cdot \tfrac{1}{256}) \approx 1.7\) million tries on average; Theorem 12.6.8 explains the difference.

EMI on a small program (the real-world box in §7). f(10) runs the loop 10 times; the statement g = g * 7 + i; is guarded by i > 100 and never runs on this input:

statement (line)	executions on \(I\)	may be pruned?
int s = 0; (4)	1	no
for (...) (5)	11 (condition)	no
if (i > 100) (6)	10	no
g = g * 7 + i; (7)	0	yes
s += i * i; (8)	10	no

Replacing line 7 by ; gives an EMI variant; both programs must print 285 0 at every optimization level.

4. Invariants and correctness

Theorem 12.6.7 (When random derivations terminate)

For a probabilistic grammar with a single nonterminal (Definition 12.6.1), a random derivation terminates with probability 1 iff \(m \le 1\) (excluding the degenerate case \(\Pr[\xi = 1] = 1\)). If \(m > 1\), it runs forever with probability \(1 - q > 0\), where \(q < 1\) is the smallest fixed point of \(f\) on \([0, 1]\).

Proof (the Galton–Watson extinction theorem)

The numbers of open nonterminals after expanding every nonterminal of generation \(n\) form a Galton–Watson process \(Z_0 = 1\), \(Z_{n+1} = \sum_{j=1}^{Z_n} \xi_{n,j}\) with independent copies of \(\xi\); the derivation terminates iff \(Z_n = 0\) for some \(n\) (the order of expansion does not change which productions are drawn for which nonterminal, only when). The generating function of \(Z_n\) is the \(n\)-fold composition \(f^{n}\), so \(q_n = \Pr[Z_n = 0] = f^{n}(0)\), and \(q_n\) increases to \(q = \lim_n q_n\), which is a fixed point of the continuous \(f\) (take limits in \(q_{n+1} = f(q_n)\)) and the smallest one in \([0,1]\) (if \(f(s) = s\) then \(q_n \le s\) for all \(n\) by induction, since \(f\) is increasing). \(f\) is convex on \([0,1]\) with \(f(1) = 1\) and \(f'(1) = m\). If \(m \le 1\) and \(\xi\) is not constantly 1, \(f\) lies strictly above the diagonal on \([0,1)\) (convexity and \(f'(1) \le 1\)), so the only fixed point is 1 and \(q = 1\). If \(m > 1\), \(f(s) < s\) just below 1 while \(f(0) \ge 0\), so by continuity there is a fixed point \(q < 1\). ∎

Theorem 12.6.8 (Why coverage feedback helps: a model)

Consider a target that checks \(k\) bytes in sequence, if (b[0]==c0) { if (b[1]==c1) { ... } }, where passing check \(j\) adds a new edge, and inputs of length \(k\). (a) A blind fuzzer drawing uniformly random inputs needs \(256^{k}\) executions on average to pass all checks. (b) A feedback fuzzer that mutates a corpus input by setting one uniformly chosen position to a uniformly random byte, and keeps an input iff it covers a new edge, needs at most \(256\,k^2\) executions on average (always mutating the most recent corpus entry).

Proof

(a) One execution passes all \(k\) checks with probability \(256^{-k}\); the waiting time is geometric with mean \(256^{k}\). (b) Suppose the latest corpus input passes checks \(0..j-1\). A mutation passes check \(j\) too if it picks position \(j\) (probability \(1/k\)) and writes \(c_j\) (probability \(1/256\)); it cannot break checks \(0..j-1\) unless it picks one of those positions, and then it is simply not kept. So each execution advances with probability at least \(1/(256 k)\), the waiting time for stage \(j\) has mean at most \(256 k\), and summing \(k\) stages gives \(256 k^2\). (With comparison tracing — libFuzzer's CMP mutations — the constant \(c_j\) is offered directly and the \(1/256\) factor mostly disappears.) ∎

Theorem 12.6.9 (EMI variants are equivalent modulo the input)

If \(P\) is deterministic and well defined on \(I\) and \(P'\) is an EMI variant of \(P\) for \(I\) (Definition 12.6.5), then \(\llbracket P' \rrbracket(I) = \llbracket P \rrbracket(I)\). Consequently, if a compiler's executables for \(P\) and \(P'\) disagree on \(I\), the compiler miscompiled at least one of them.

Proof

Let \(\langle \sigma_0, \sigma_1, \dots, \sigma_n \rangle\) be the execution of \(P\) on \(I\) as a sequence of states, each paired with the statement about to execute. We show by induction on \(t\) that \(P'\) on \(I\) reaches the same \(\sigma_t\) with the corresponding statement. Base: the initial states are equal (same declarations and input; pruning replaces statements, not declarations of variables that executed code uses). Step: the statement \(s_t\) that \(P\) executes at step \(t\) is in \(\mathrm{cov}_I(P)\), hence unchanged in \(P'\); its effect and the next control point depend only on the state and on \(s_t\) itself and its enclosing control structures, which are also executed, hence unchanged. Pruned statements are never reached, so replacing them changes no transition taken. The final states, hence the outputs, are equal. The consequence follows as in Theorem 12.5.10 with the reference result \(\llbracket P \rrbracket(I)\) playing the role of the specification. ∎

Prune statements, not lines

Deleting the text of line 7 of the EMI example changes the if's body to the next statement, s += i * i; — a different program, not an EMI variant. Deleting lines 6 and 7 together removes the if statement, which did execute, so that is not an EMI variant either (it only happens to be equivalent because the condition has no side effects). Replace the unexecuted statement by ;.

5. Complexity

Let \(\lvert w \rvert\) be the size of a generated sentence, \(E\) the number of executions, \(t\) the cost of one execution, \(S\) the number of statements of \(P\) and \(u \le S\) the number of unexecuted ones.

Technique	Time (worst)	Time (typical)	Space	Notes
Grammar-based fuzzing	unbounded for \(m > 1\) without phase 3; \(O(\lvert w \rvert)\) per sentence with it	microseconds per sentence	the derivation tree	Theorem 12.6.7
Coverage-guided fuzzing	\(E \cdot t\); waiting times as in Theorem 12.6.8	\(10^5\)–\(10^6\) executions per second for small in-process targets	corpus + feature table	the §7 run crashes after fewer than 8 000 executions
EMI (Orion)	one coverage run + \(V\) compilations and runs	seconds per variant	\(V\) variants of \(P\)	\(2^{u}\) possible pruning variants per program

Justification. Each derivation step of Algorithm 12.6.2 adds at least one terminal or closes a nonterminal, so the steps are linear in the final tree once phase 3 bounds it. Theorem 12.6.8 gives the waiting times in its model. Pathological family for coverage guidance: a check if (hash(b) == c) on a cryptographic hash offers no intermediate features, so feedback reduces to blind search: \(2^{32}\) expected executions for a 32-bit hash comparison; structure-aware mutators or dictionaries are the remedy. For EMI, a program with \(u\) unexecuted statements has \(2^{u}\) variants; Orion samples them with probability \(p\) per statement.

6. Variants and refinements

Grammar-based fuzzing

• Coverage of productions (Purdom [Pur72]): a minimal set of sentences using every production; a test-suite generator rather than a fuzzer. Trade-off: no randomness.
• Fragment recombination (LangFuzz [HHZ12]: splice code fragments from real test suites into grammar-generated programs). Trade-off: needs a corpus of programs.
• Probabilistic grammars learned from samples (pick \(\pi_A\) from real code) [FB-Grammar].

Coverage-guided fuzzing

• Power schedules (AFLFast [BPR16]; libFuzzer's entropic schedule [BMC20]): choose which corpus input to mutate by how rare its features are. Trade-off: bookkeeping per feature.
• Structure-aware fuzzing (libprotobuf-mutator, custom mutators, -dict=): mutations that keep the input well-formed; llvm-opt-fuzzer mutates IR modules. Trade-off: a mutator per format.
• Crash minimization (-minimize_crash=1): a built-in reducer for byte inputs (Lesson 12.7).

Equivalence modulo inputs (EMI)

• Athena and Hermes (Le et al., 2015 and Sun et al., 2016): also insert code into unexecuted regions and mutate live code in semantics-preserving ways, guided by search [CPS+20]. Trade-off: more complex mutation rules.
• EMI for other languages and for JIT/OpenCL compilers [CPS+20]. Trade-off: coverage tooling per language.

7. In real compilers

Grammar-based fuzzing

The Fuzzing Book's GrammarFuzzer (fuzzingbook/GrammarFuzzer.py, expand_tree with the three strategies expand_node_max_cost, expand_node_randomly, expand_node_min_cost) [FB-Grammar]; Csmith and YARPGen are grammar-based generators with semantic side conditions (Lesson 12.5); Chapter 24's Pebble generator.

Random sentences from an expression grammar

Reproduce (fuzzingbook 1.2.2 via uvx, Python 3.11):

uvx --from fuzzingbook python -c "
import random
from fuzzingbook.GrammarFuzzer import GrammarFuzzer
from fuzzingbook.Grammars import EXPR_GRAMMAR
random.seed(1)
f = GrammarFuzzer(EXPR_GRAMMAR, min_nonterminals=0, max_nonterminals=5)
for _ in range(5): print(f.fuzz())
for k in ['<expr>', '<factor>']: print(k, '::=', ' | '.join(EXPR_GRAMMAR[k]))
" 2>/dev/null

Output:

7 / 1 - 4 * 9 - 5
(4 + 1) / +-1 / 9 * 7
5 / 8 * 3 + 4 + 8
9.1989
8.61 * 7.9
<expr> ::= <term> + <expr> | <term> - <expr> | <term>
<factor> ::= +<factor> | -<factor> | (<expr>) | <integer>.<integer> | <integer>

What to notice: every sentence is syntactically valid (a parser test gets past the lexer), and sizes stay small because phase 3 of Algorithm 12.6.2 closes the tree with minimal-cost expansions once 5 nonterminals are open. Under uniform choice an expansion of <factor> produces on average \((1 + 1 + 1 + 2 + 1)/5 = 1.2\) nonterminals — the cost-aware phases, not the probabilities, guarantee termination here. The expressions are also full of divisions by zero and leading +-: fine for a parser, useless for differential testing of code generation without Lesson 12.5's UB avoidance.

Coverage-guided fuzzing

compiler-rt/lib/fuzzer/FuzzerLoop.cpp — Fuzzer::Loop, Fuzzer::MutateAndTestOne, Fuzzer::RunOne [LLVM-FuzzerLoop]; compiler-rt/lib/fuzzer/FuzzerMutate.cpp (the mutators); SanitizerCoverage in llvm/lib/Transforms/Instrumentation/SanitizerCoverage.cpp; LLVM's own fuzzers in llvm/tools/llvm-opt-fuzzer, llvm/tools/llvm-isel-fuzzer (LLVM 23.1.2).

libFuzzer finds the toy parser's overflow

Reproduce (clang 23.1.2 with the compiler-rt 23.1.2 fuzzer and sanitizer runtimes, which the course's Linux toolchain lacks: Homebrew's llvm ships them — drop -resource-dir="$RD"; on Linux build $RD as in the chapter's tools outside the course toolchain):

cat > parse.c <<'EOF'
#include <stddef.h>
#include <stdint.h>
/* A toy parser for "(k)" lists: a digit count k, then k items separated by ','. */
static int parse(const uint8_t *s, size_t n) {
  if (n < 3 || s[0] != '(') return 0;
  if (s[1] < '0' || s[1] > '9') return 0;
  int k = s[1] - '0';
  if (s[2] != ')') return 0;
  int items[4];
  size_t i = 3;
  for (int j = 0; j < k; j++) {           /* bug: no check that k <= 4 */
    if (i >= n) return 0;
    items[j] = s[i++];
    if (i < n && s[i] == ',') i++;
  }
  return items[0];
}
volatile int sink;
int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) {
  sink = parse(data, size);
  return 0;
}
EOF
clang-23 -resource-dir="$RD" -g -O1 -fsanitize=fuzzer,address parse.c -o parse-fuzz
mkdir -p corpus && ./parse-fuzz -seed=1 corpus 2>&1 \
  | grep -E '^#[0-9]+.*(NEW|REDUCE|INITED)|^SUMMARY' \
  | awk '{ if ($1 == "SUMMARY:") print $1, $2, $3; else print $1, $2, $3, $4, $5, $6, $7, $8 }'
od -c crash-*

Output:

#2 INITED cov: 2 ft: 2 corp: 1/1b
#9 NEW cov: 3 ft: 3 corp: 2/4b
#234 NEW cov: 4 ft: 4 corp: 3/9b
#246 NEW cov: 5 ft: 5 corp: 4/12b
#277 REDUCE cov: 5 ft: 5 corp: 4/11b
#328 REDUCE cov: 5 ft: 5 corp: 4/10b
#1034 REDUCE cov: 6 ft: 6 corp: 5/14b
#1046 REDUCE cov: 6 ft: 6 corp: 5/13b
#6518 REDUCE cov: 8 ft: 8 corp: 6/16b
#6565 NEW cov: 11 ft: 11 corp: 7/21b
#6576 NEW cov: 12 ft: 12 corp: 8/25b
#7747 NEW cov: 13 ft: 13 corp: 9/30b
SUMMARY: AddressSanitizer: stack-buffer-overflow
0000000   (   5   ) 377 377   ) 377 377 377
0000011

What to notice: Algorithm 12.6.4's log: every NEW is an input with a new feature, every REDUCE a shorter input with the same features (corp: is the corpus size in inputs and bytes). After fewer than 8 000 executions the input (5) followed by five bytes () counts as an item) overflows items[4], AddressSanitizer turns the silent stack write into a crash, and the reproducer is saved. The first version of this harness called parse without using its result: -O1 deleted the whole call and libFuzzer reported one coverage point forever — keep the result observable (sink).

Equivalence modulo inputs (EMI)

Orion (Le, Afshari and Su's tool, built on gcov and the Clang/LibTooling rewriter) [LAS14]; coverage in LLVM comes from -fprofile-instr-generate -fcoverage-mapping and llvm-cov (llvm/tools/llvm-cov), in GCC from --coverage and gcov.

An EMI variant from an llvm-cov profile

Reproduce (clang 23.1.2, llvm-profdata and llvm-cov 23.1.2, compiler-rt 23.1.2 in $RD as above):

cat > p.c <<'EOF'
#include <stdio.h>
int g = 0;
int f(int x) {
  int s = 0;
  for (int i = 0; i < x; i++) {
    if (i > 100)
      g = g * 7 + i;
    s += i * i;
  }
  return s;
}
int main(void) {
  printf("%d %d\n", f(10), g);
  return 0;
}
EOF
clang-23 -resource-dir="$RD" -O0 -fprofile-instr-generate -fcoverage-mapping p.c -o p.cov
LLVM_PROFILE_FILE=p.profraw ./p.cov
llvm-profdata merge -o p.profdata p.profraw
llvm-cov show ./p.cov -instr-profile=p.profdata p.c | sed -n '3,11p'
sed '7s/.*/      ;/' p.c > p.emi.c
for f in p.c p.emi.c; do for o in O0 O2; do clang-23 -$o $f -o x && echo "$f -$o: $(./x)"; done; done

Output:

285 0
    3|      1|int f(int x) {
    4|      1|  int s = 0;
    5|     11|  for (int i = 0; i < x; i++) {
    6|     10|    if (i > 100)
    7|      0|      g = g * 7 + i;
    8|     10|    s += i * i;
    9|     10|  }
   10|      1|  return s;
   11|      1|}
p.c -O0: 285 0
p.c -O2: 285 0
p.emi.c -O0: 285 0
p.emi.c -O2: 285 0

What to notice: the profile's execution counts are \(\mathrm{cov}_I(P)\) of Definition 12.6.5 (line 7 ran 0 times); sed replaces that statement by ; (the pitfall above), producing an EMI variant; Theorem 12.6.9 demands equal outputs, and clang delivers them at both levels. A miscompilation — for example an optimizer that reasons wrongly about the now-empty if — would show as a different line.

8. Comparison

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Grammar-based fuzzing	Syntactically valid inputs; no semantic validity; terminates with cost-aware expansion (Thm. 12.6.7)	Microseconds per input	Readable inputs; crash oracle unless combined with differential testing	Low (a grammar + Algorithm 12.6.2)	Parser and front-end robustness
Coverage-guided fuzzing (libFuzzer)	Finds inputs that pass deep checks without knowing the format (Thm. 12.6.8); crash/sanitizer oracle	\(10^5\)–\(10^6\) executions/s in process	A minimal-ish crashing input (-minimize_crash)	Low: one entry point + -fsanitize=fuzzer	Parsers, decoders, LLVM's own *-fuzzer tools
Equivalence modulo inputs	Detects miscompilations with one compiler and no expected output (Thm. 12.6.9)	A coverage run + one compile/run per variant	A pair of programs that differ only in dead code	Medium (coverage + a source rewriter)	Miscompilation hunting in GCC/LLVM (Orion, Athena, Hermes)

Choose grammar-based fuzzing when inputs must parse and you have a grammar; coverage-guided fuzzing when the target is a function of bytes that can crash (a lexer, a parser, a bitcode reader) — pair it with sanitizers; EMI when you hunt miscompilations and have no second compiler, or want variants that stress optimizations around dead code.

9. Assessment

• Quiz: gw-extinction (number), gw-terminate, cov-waiting (number), cov-new-reduce, emi-prune (set), diff-agree, llvm-where-fuzzer-loop.
• Drill: none — the waiting-time and extinction computations are single formulas (quiz cov-waiting, gw-extinction), and pruning is exercised by quiz emi-prune; the lab's difftest and Chapter 24's fuzzer are the hands-on practice.
• Flashcards: tags grammar-fuzzing, coverage-fuzzing, emi.
• Find where LLVM does it: in compiler-rt/lib/fuzzer/FuzzerLoop.cpp, which member function mutates one corpus input and runs it?

References

See the chapter references.