Understanding and Improving Coverage Tracking with AFL++ (Registered Report)
Vasil Sarafov, David Markvica, Felix Berlakovich, Matthias Bernad, Stefan Brunthaler · 2024
Coverage-based fuzzers track which program parts they visit when executing a specific input as a proxy measure to (1) guide the fuzzing process, and (2) explore the PUT's state space. One way to record coverage progress is to enumerate basic block pairs (e.g., edges in the control-flow graph) and use them to index into a hash table that holds counters. The counter is incremented every time a fuzzer's input exercises the corresponding edge. Traditionally the coverage map has been a compact bitmap that fits the L2 CPU cache to reduce runtime overhead and boost fuzzing throughput. In such a design where space is traded for speed, two sources of imprecision can arise: (1) collisions, and (2) arithmetic inaccuracies.