parsarium

Chapter 05

Coverage feedback

How AFL++ decides an input is interesting, how Parsarium gets that signal from eight languages, and how to read the numbers.

6 min read5 quiz questions3 exercises

A coverage-guided fuzzer mutates inputs and keeps the ones that make the program do something new. "Something new" is measured with coverage feedback: which parts of the code an input reached. Without it, a fuzzer is guessing. With it, the fuzzer builds a corpus step by step, each input reaching a little further into the parser.

How AFL++ sees coverage

AFL++ keeps a shared memory map, 64 KiB by default. As the target runs, each transition between code locations, an edge, increments a slot in the map. After every execution AFL++ looks at the map. If an input touched a slot no earlier input touched, or touched one a very different number of times, it is saved to the queue and mutated further.

For C, C++, and Rust, the compiler inserts this instrumentation into the parser. That is the fastest and most precise setup.

Bridges for other languages

Go, Java, JavaScript, Python, and PHP do not compile to native code in the same way, so Parsarium uses a bridge. The harness records which parts of the parser source ran, using the language's own coverage tool, and a small proxy writes those features into the AFL++ map.

LanguageFeatureSource
C, C++Compiled edgesAFL++ compiler instrumentation
RustCompiled edgesafl.rs
GoStatement blocksGo coverage of the parser package
JavaSource linesJaCoCo
JavaScriptSource rangesV8 coverage
PythonSource linesLine tracing
PHPSource linesXdebug

The parser packages stay unchanged, and coverage is limited to the parser's own source, so the signal is about the parser and not about the interpreter or the harness. Bridges are slower than compiled instrumentation, which is worth remembering when you set time budgets.

Parsarium checks that the bridges really respond to the input. For a few targets in each bridged language, it runs two different inputs and records how many parser features each one reached. For the Java PLY reader jply, for example, the two inputs reached 235 and 146 features. That difference is what the fuzzer uses to tell them apart.

Reading the numbers

A coverage count means something only next to another count from the same target. Use it to compare two inputs, two corpora, or the same campaign over time. Do not compare counts across languages: a Java line, a Go block, and a C edge are different units. When you report results across many targets, report the feedback kind of each one. The bench adds it to the report table for you.

Key ideas

  • AFL++ records edges in a shared map and keeps inputs that reach new slots or very different hit counts.
  • C, C++, and Rust targets are instrumented at compile time. Go, Java, JavaScript, Python, and PHP targets use a bridge that reports parser source coverage.
  • Bridge coverage is limited to the parser's own source, so the signal is about the parser.
  • Coverage counts are comparable only within one target. Report the feedback kind of every target.

Check yourself

Answer all five to see your score

Which inputs does AFL++ keep in its queue?

  1. Every input it generates
  2. Inputs that reach a new slot in the map, or hit a slot a very different number of times
  3. Only inputs that crash

New coverage, including a new hit-count bucket for an edge it has seen, is what makes an input worth keeping and mutating further.

A Go target reports 900 features and a C target 600 edges on the same file. Which parser is better covered?

  1. The Go target
  2. The C target
  3. You cannot tell: the units are different.

A Go statement block and a compiled C edge measure different things. Compare counts only within the same target.

Why do bridges measure only the parser's source and not the interpreter?

  1. So the feedback describes the parser, not the runtime or the harness
  2. Because interpreters cannot be measured
  3. To make the map smaller

If the interpreter's own code counted, the fuzzer would chase new paths in the runtime instead of in the parser under test.

The AFL++ map has 64 KiB of slots. What can happen when two different edges hash to the same slot?

  1. The target crashes.
  2. The fuzzer may not notice that one of them is new coverage.
  3. Nothing; collisions are impossible.

Collisions are possible in any fixed-size map. They make the feedback slightly less precise; they do not break the campaign.

You give a bridged target and a compiled target the same one-hour budget. What should your report say?

  1. Nothing extra; time is time.
  2. Only the final coverage
  3. The feedback kind of each target and how many executions each one ran

Bridged targets usually run fewer executions per second. Reporting executions and feedback kind lets readers interpret the comparison.

Exercises

Exercise 5.1Warm-up

Prepare an AFL++ run for a compiled target and a bridged target, and compare their plans.

$ parsarium afl build png c stb
$ parsarium afl prepare png c stb runs/stb-afl
$ parsarium afl build png python pillow
$ parsarium afl prepare png python pillow runs/pillow-afl
$ parsarium afl run runs/pillow-afl --check

Open both plan.json files and find the feedback kind. Then run each for five minutes with --seconds 300 and compare execs_per_sec in afl-out/default/fuzzer_stats.

Hint

fuzzer_stats is a plain text file of key : value lines.

Solution

The Pillow plan names the Python bridge; the stb_image plan uses compiled edges. Expect stb_image to run many more executions per second, often by an order of magnitude or more, because the bridge traces Python lines and passes them through a proxy. This is why budgets for bridged targets need care.

Exercise 5.2Practice

Parsarium checks that bridges respond to the input by running two different inputs and recording the parser features each one reached. Read data/afl-feedback-differential.json and, for each project, compute the difference as a share of the first input's features.

python3 - <<'EOF'
import json, os
for r in json.load(open(os.path.join(os.environ["PARSARIUM"], "data/afl-feedback-differential.json")))["results"]:
    share = r["parser_feature_difference"] / r["first_parser_features"]
    print(f"{r['project']:30} {r['first_parser_features']:4} {r['second_parser_features']:4} {share:6.1%}")
EOF

Which bridge shows the largest relative difference, and which the smallest? What does a small difference mean?

Hint

The difference counts features reached by one input but not the other, in either direction.

Solution

At the time of writing, the PHP SVG reader shows the largest share (40 of 72 features differ) and the JavaScript PDF library pdf-lib the smallest (4 of 656). A small difference does not mean the bridge is broken: these two PDF inputs simply take almost the same path through a large parser. It does mean that a fuzzer will need inputs that differ in more interesting ways to make progress there.

Exercise 5.3Challenge

Run the Pillow campaign twice for ten minutes each and plot how the corpus grows over time in both runs. AFL++ writes a time series to afl-out/default/plot_data.

Hint

The first line of plot_data is a header starting with #. Read the column names from it instead of hard-coding positions.

Solution
python3 - runs/pillow-a runs/pillow-b <<'EOF'
import sys, csv
import matplotlib.pyplot as plt
for run in sys.argv[1:]:
    with open(f"{run}/afl-out/default/plot_data") as f:
        header = [h.strip() for h in f.readline().lstrip("# ").split(",")]
        rows = [dict(zip(header, (v.strip() for v in line))) for line in csv.reader(f)]
    plt.plot([int(r["relative_time"]) for r in rows], [int(r["corpus_count"]) for r in rows], label=run)
plt.xlabel("seconds"); plt.ylabel("corpus size"); plt.legend(); plt.savefig("corpus.png")
EOF

The two curves will not be identical. Most of the growth happens early and then flattens; the runs differ in when the jumps happen. That spread is why the next chapters insist on repetitions.