American fuzzy lop (fuzzer)

To generate new inputs, AFL applies various mutations to existing inputs.[22] These mutations are mostly agnostic to the input format of the target program; they generally treat the input as simple blob of binary data.

At first, AFL applies a deterministic sequence of mutations to each input. These are applied at various offsets in the input. They include:[23][24]

• Flipping (i.e., negating or inverting) 1-32 bits
• Incrementing and decrementing 8-, 16-, and 32-bit integers, in both little- and big-endian encodings
• Overwriting parts of the input with "approximately two dozen 'interesting' values", including zero and maximum and minimum signed and unsigned integers of various widths, again in both little- and big-endian encodings.
• Replacing parts of the input with data drawn from a "dictionary" of user-specified or auto-detected tokens (e.g., magic bytes, or keywords in a text-based format)[25][22][26]

After applying all available deterministic mutations, AFL moves on to havoc, a stage where between 2 and 128 mutations are applied in a row. These mutations are any of:[22]

• The deterministic mutations described above
• Overwriting bytes with random values
• Operations over multi-byte "blocks":
  • Deleting blocks
  • Duplicating blocks
  • Setting each byte in a block to a single value

If AFL cycles through the entire queue without generating any input that achieves new code coverage, it begins splicing. Splicing takes two inputs from the queue, truncates them at arbitrary positions, concatenates them together, and applies the havoc stage to the result.

AFL pioneered the use of binned hitcounts for measuring code coverage.[27] The author claims that this technique mitigates path explosion.[28][29]

Conceptually, AFL counts the number of times a given execution of the target traverses each edge in the target's control-flow graph; the documentation refers to these edges as tuples and the counts as hitcounts. At the end of the execution, the hitcounts are binned or bucketed into the following eight buckets: 1, 2, 3, 4-7, 8-15, 16-31, 32-127, and 128 and greater. AFL maintains a global set of (tuple, binned count) pairs that have been produced by any execution thus far. An input is considered "interesting" and is added to the queue if it produces a (tuple, binned count) pair that is not yet in the global set.

In practice, the hitcounts are collected and processed using an efficient but lossy scheme. The compile-time instrumentation injects code that is conceptually similar to the following at each branch in the control-flow graph of the target program:[30]

cur_location = <COMPILE_TIME_RANDOM>;
shared_mem[cur_location ^ prev_location]++;
prev_location = cur_location >> 1;

where <COMPILE_TIME_RANDOM> is a random integer and shared_mem is a 64 kilobyte region of memory shared between the fuzzer and the target.

This representation is more fine-grained (distinguishes between more executions) than simple block or statement coverage, but still allows for a linear-time "interestingness" test.

On the assumption that smaller inputs take less time to execute, AFL attempts to minimize or trim the test cases in the queue.[22][31] Trimming works by removing blocks from the input; if the trimmed input still results in the same coverage (see #Measuring coverage), then the original input is discarded and the trimmed input is saved in the queue.

AFL selects a subset of favored inputs from the queue, non-favored inputs are skipped with some probability.[32][27]

One of the challenges American fuzzy lop had to solve involved an efficient spawning of hundreds of processes per second. Apart from the original engine that spawned every process from scratch, American fuzzy lop offers the default engine that relies heavily on the fork system call.[33][27] This can further be sped up by leveraging LLVM deferred fork server mode or the similar persistent mode, but this comes at the cost of having to modify the tested program.[34] Also, American fuzzy lop supports fuzzing the same program over the network.

American fuzzy lop features a colorful command line interface that displays real-time statistics about the fuzzing process. Various settings may be triggered by either command line options or environment variables. Apart from that, programs may read runtime statistics from files in a machine-readable format.

In addition to afl-fuzz and tools that can be used for binary instrumentation, American fuzzy lop features utility programs meant for monitoring of the fuzzing process. Apart from that, there is afl-cmin and afl-tmin, which can be used for test case and test corpus minimization. This can be useful when the test cases generated by afl-fuzz would be used by other fuzzers.

AFL++

Initial release	2.52c / 5 June 2019 (2019-06-05)
Stable release	4.00c / 26 January 2022 (2022-01-26)[41]
Repository	github.com/AFLplusplus/AFLplusplus
Website	aflplus.plus

AFL++ (AFLplusplus)[42] is a community-maintained fork of AFL created due to the relative inactivity of Google's upstream AFL development since September 2017. It includes new features and speedups.[43]

Google's OSS-Fuzz initiative, which provides free fuzzing services to open source software, replaced its AFL option with AFL++ in January 2021.[44][45]

• Fioraldi, Andrea; Mantovani, Alessandro; Maier, Dominik; Balzarotti, Davide (2023-01-20). "Dissecting American Fuzzy Lop – A FuzzBench Evaluation". ACM Transactions on Software Engineering and Methodology. 32 (2): 1–26. doi:10.1145/3580596. ISSN 1049-331X. S2CID 247088398.
• Metzman, Jonathan; Szekeres, László; Simon, Laurent; Sprabery, Read; Arya, Abhishek (2021-08-18). "FuzzBench: An open fuzzer benchmarking platform and service". Proceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering. ESEC/FSE 2021. New York, NY, USA: Association for Computing Machinery. pp. 1393–1403. doi:10.1145/3468264.3473932. ISBN 978-1-4503-8562-6. S2CID 237205274.