Fuzzing is essentially feeding random (mutatted) inputs and finding out where those inputs crash the program.
Purely random inputs gets rejected most of the time. Hence, Michal Zalewski implementated this new technique in AFL called instrumentation. In this technique we keep inputs that has covered new paths and ignore the rest of the inputs.
We assign if/else branches a unique identifier. When program execution ends, it saves hit records (branches covered by inputs) in a shared memory (shared by AFL and program) of size 64KB. And then it XOR out current and previous branches identifiers to find out unique edges (paths).
If an input finds out new edge it updates the table and queue the input. If an input doesn’t find out a new edge it gets discarded. Edge is just one area if we find a new bucket (counter range) that is also interesting.
A bucket is basically hit count of an edge. If an edge A to B is explored only once. It falls in Bucket A. And if an edge A to B is explored twice, it falls in the Bucket B. And so on. There are total 8 buckets.
AFL takes 1 input from the input queue, mutates it by bit flip or arithmetic and then run program on that input. If it finds a new edge/bucket add that mutatted input in the queue, else discard it. And then take the next input from the queue.
It doesn’t use greedy approach. Hence it keeps all the inputs that are interesting.
With the time input queue grows large enough. Hence to speedup things it re-evaluates input queue periodically and takes out favoured subset of inputs [to be continued…]