AFL Overview

TOC

1. 1. Introduction
2. 2. Model
3. 3. fuzzing-binaries-without-execve
4. 4. write_to_testcase
5. 5. fuzz_one
6. 6. Document
7. 7. Mutations
8. 8. Related Work

GitHub: https://github.com/google/AFL

Introduction

technical whitepaper

AFL is a mutational, coverage guided fuzzer. It mutates a set of test cases (seed) to reach previously unexplored points in the program. When this happens, the test case triggering a new coverage is saved as part of the test case queue.

the overall algorithm can be summed up as:

1. Load user-supplied initial test cases into the queue,
2. Take next input file from the queue,
3. Attempt to trim the test case to the smallest size that doesn’t alter the measured behavior of the program,
4. Repeatedly mutate the file using a balanced and well-researched variety of traditional fuzzing strategies,
5. If any of the generated mutations resulted in a new state transition recorded by the instrumentation, add mutated output as a new entry in the queue.
6. Go to 2.

afl-cmin & afl-tmin: They 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.

Model

• Main

  

• Map

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

  This form of coverage provides considerably more insight into the execution path of the program than simple block coverage.

  The reason for the shift operation in the last line of the pseudocode shown earlier in this section is to preserve the directionality of tuples (without this, A^B would be indistinguishable from B^A) and to retain the identity of tight loops (otherwise, A^A would be obviously equal to B^B).

• Two-Layer Depth: The order of hitting counts is stored in a power of two to avoid path explosion.

  COVERAGE_ONLY in config.h, which is uncommented default.

  Pseudo-code:

  // Start for(int i = 0; i < 2; i++) { if(choice) { // Block 1 } else { // Block 2 } } // End

  Blocks are seen as recorded points.

  With COVERAGE_ONLY, it only has two paths, which are block 1 and block 2.

  Without COVERAGE_ONLY, it has four paths, which are block 1-block 1, block 1-block 2, block 2-block 1 and block 2-block 2. Not only recording the hit situations, but also the hit sequences. Which extends a great deal of paths.

  

  There are two status, which are __afl_prev_loc and present, instead of all status.

  Example: It trivially distinguishes between the following execution traces.

  • A -> B -> C -> D -> E (tuples: AB, BC, CD, DE)
  • A -> B -> D -> C -> E (tuples: AB, BD, DC, CE)

• Interesting: An input is consideration interesting (i.e. saved to the queue) if it explores a new hitting map (trace_bits). The size of this map is limited, so collisions are possible.

• Seed score preference

  1. Coverage
  2. Execution time
  3. Discovery time

• AFL defects

  1. Lack of adaptivity
  2. Constantly
  3. Inefficient search strategy

fuzzing-binaries-without-execve

fuzzing-binaries-without-execve

It is an embedding fork server with less overhead.

write_to_testcase

Write modified data to file for testing. If out_file is set, the old file is unlinked and a new one is created. Otherwise, out_fd is rewound and truncated.

fuzz_one

abandon_entry: exception happens.

break 7 if buf[0] == 'h'  -- afl-fuzz.c:6

Document

Github:

Interpreting output:

• queue/ - test cases for every distinctive execution path, plus all the starting files given by the user. This is the synthesized corpus mentioned in section 2. Before using this corpus for any other purposes, you can shrink it to a smaller size using the afl-cmin tool. The tool will find a smaller subset of files offering equivalent edge coverage. (seed)
• crashes/ - unique test cases that cause the tested program to receive a fatal signal (e.g., SIGSEGV, SIGILL, SIGABRT). The entries are grouped by the received signal.
• hangs/ - unique test cases that cause the tested program to time out. The default time limit before something is classified as a hang is the larger of 1 second and the value of the -t parameter. The value can be fine-tuned by setting AFL_HANG_TMOUT, but this is rarely necessary.

Fuzzer dictionaries:

By default, afl-fuzz mutation engine is optimized for compact data formats - say, images, multimedia, compressed data, regular expression syntax, or shell scripts. It is somewhat less suited for languages with particularly verbose and redundant verbiage - notably including HTML, SQL, or JavaScript.

It needs relevant input data to keep high performance.

Other:

There are some unfortunate trade-offs with ASAN and 64-bit binaries.

Mutations

The mutations of AFL are divided into two categories: deterministic and havoc (indeterministic).

• Deterministic: Deterministic stages include single deterministic mutations on contents of the test cases, like bit flips, additions, substitution with integers from a set of common interesting values (e.g. -1, INT_MAX, …) and others.
• Havoc: In havoc, mutations are randomly stacked and include also changes to the size of the test case (e.g. adds or deletes portions of the input).

Related Work

• AFL: Baseline

• AFLFast: It was published in 2016.

  Phenomenon: most tests exercise the same few “high-frequency” paths.

  Method: Introduce a Markov chain model.

• FairFuzz: It was published in 2018.

  1. Identify AFL-produced inputs (exercised rare branches)
  2. A novel mutation algorithm (biased towards rare branches)

• MOPT-AFL: It was published in 2019.

  Find the optimal selection probability distribution of mutation operators.