0x01 Why
Popular fuzzers such as AFL use simple coverage information. Its inaccuracy and incompleteness cause path collisions, hiding paths that may trigger new crashes and distorting optimal fuzzing decisions. Most academic work focuses on coverage-guided fuzzing rather than coverage itself, which is the gap CollAFL addresses.
0x02 What
Improves AFL's coverage accuracy and seed-selection strategy; the resulting tool is CollAFL.
0x03 How
The paper makes two improvements. First, AFL stores coverage in a 64 KB bitmap. During fuzzing, different edges can receive identical hashes, causing collisions. A colliding input may reach a new path without being retained as a seed. CollAFL introduces a new algorithm to reduce path-hash collisions. Second, seed selection prioritizes seeds that contribute to coverage.
CollAFL works as follows.
For hash collisions:
For an AFL edge A→B, the hash is:
prev and cur are the keys for basic blocks A and B. Because keys are random, distinct edges can share a hash. CollAFL improves this. Given blocks A and B with prev and cur keys:
Its hash algorithm is:
<x, y, z> are edge-specific parameters. AFL is the special case <x=0, y=1, z=0> for every edge/block. Fmul has the same process and overhead as AFL.
However, the algorithm cannot guarantee a solution for a given application: there are too many basic blocks to enumerate every parameter combination. Even exhaustive search would not ensure a solution because block keys are assigned randomly.
CollAFL therefore improves the proposed hash calculation further:
- Hash Algorithm for Blocks with a Single Predecessor
If a block has only one predecessor:
An edge ending at an unsolvable block can receive a hash directly in the ending block:
prev and cur are the keys assigned to blocks A and B; c is a unique constant to determine.
- Hash Algorithm for Blocks with Multiple Predecessors
If block B has multiple predecessors:
If B has multiple incoming edges, its hash must be calculated dynamically:
prev and cur are the keys for A and B. CollAFL builds an offline table of unique edge hashes, including edges ending at unsolvable blocks. At runtime it looks up hashes using start and end blocks as keys. This lookup is substantially slower than Fmul and Fsingle.
- Overall mitigation
Provided the bitmap exceeds the number of edges, Fmul, Fsingle, and Fhash are used for different block types:
For seed selection, CollAFL provides three strategies.
- CollAFL-br
Seeds with more untouched adjacent branches are prioritized. The number of untouched neighbors is the weight for test case t:
This formula applies only when edge <bb, bb_i> has not been covered by any previous test case; otherwise it is 0.
This formula weights seed selection, prioritizing seeds with larger weights. The set of previously executed test cases changes as testing proceeds, so function results and test-case weights are dynamic.
- CollAFL-desc
Seeds with more untouched nearby descendants are prioritized. Their count is used as the weight for test case t:
IsUntouched is the same function used in CollAFL-br; NumDesc returns the number of descendant paths beginning at the given basic block. Formally:
This weight is not deterministic because IsUntouched is dynamic, although each basic block's number of descendant paths is fixed.
- CollAFL-mem
Seeds with more memory-access operations are prioritized. The number of memory accesses is the weight for test case t:
NumMemInstr returns the number of memory-access operations in a basic block and can be computed statically. Unlike the first two strategies, this weight is deterministic.
In the first strategy, each seed follows a path containing branches, some already exercised by other seeds and some untouched. CollAFL counts the untouched branches. If one seed has one untouched branch and another has N, it chooses the latter because mutation is more likely to reach an untested branch.
The second strategy improves on the first. It treats branches from strategy one as initial values, then adds their descendant paths according to path count rather than counting only the initial branch.
The third strategy considers memory access. CollAFL counts basic-block accesses on the seed's path and gives higher priority to paths with more accesses.
0x04 Result
- The authors found 157 new security vulnerabilities across 24 real applications, 95 of which received CVEs. Unfortunately, CollAFL was not open-sourced.
0x05 Question
Why must the bitmap be larger than the number of edges?
Answer: AFL's hash result is bounded by cur or prev, whose values are at most 64K. Treat the bitmap as an array: an edge hash of 100 sets bitmap[100] nonzero to mark the edge as visited. The bitmap must therefore have enough slots for the edges.
In many real projects, testers have only a binary. AFL supports binary fuzzing through QEMU, but it is slow. How might this be improved?
Answer: AFL's QEMU, LLVM, and afl-gcc modes all instrument edges. LLVM and afl-gcc operate on source; QEMU targets binaries. QEMU acts as a virtual machine because instrumenting binaries is difficult, deriving fuzzing coverage from execution state. Improving QEMU speed therefore means finding better binary instrumentation or a better virtual machine.
Thanks to a senior colleague for answering the two questions above.