AFL: American Fuzzy Lop

Fuzzing is essentially feeding random/weird/mutated inputs and finding out where these inputs crash the program (which usually means a bug or vulnerability in the program).

So… What’s the problem?

Feeding purely random inputs (to any program) get rejected most of the time (it’s called blind fuzzing). Because random inputs never understand what is inside the program, so they (most of the time) never crash the program and get rejected at the first branch/condition.

Imagine a following C program that parses a file format starting with a 4-byte magic header GIF8.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char *argv[]) {
    FILE *f = fopen(argv[1], "rb");

    unsigned char buffer[100];
    size_t bytes_read = fread(buffer, 1, sizeof(buffer), f);
    fclose(f);

    if (bytes_read < 4 || memcmp(buffer, "GIF8", 4) != 0) {
        // Purely random inputs exit right here.
        return 0;
    }

    return 0;
}

The blind fuzzer will almost never make it past this condition. Why? Because a blind fuzzer will throw a file with a bunch of random bytes at the program. Files containing {'AAAA', 'BBBB', 'CCCC', 'DDDD', 'EEEE', 'FFFF', 'GGGG', ...} and wait if the program crashes or not. American Fuzzy Lop solves this issue.

What does the AFL try to solve?

AFL looks for the crashes too. But it also looks at the feedback. It checks whether this particular input explored some new code in the program. If so, keep it (and call it a valuable input), otherwise discard it.

In the above example we see an input GGGG. It will get discarded in the blind fuzzing as it cannot crash the program but AFL knows that it passes first index comparison G->G (that’s the feedback). But how does AFL know that? Here comes instrumentation.

In instrumentation, every branch (i.e., if/else condition, loop, and switch case) of the code gets assigned a unique identifier at compile time (coverage guided). And as the program execution starts, it saves branches covered by inputs (called hit records) into a shared memory of 64KB.

AFL doesn’t track whether this branch was hit or not, instead it looks for edges. It XORs current and previous branches to find out a unique edge. Now, if an input finds out a new edge then it’s valuable input, else it will be discarded.

Most of the time a program may contain loops and if a loop runs for n times, it means there is a possibility of n edges, right? But AFL cannot keep all those n values as valuable inputs. As most of those inputs might be covering a subset of edges the 1 input valuable input covers and also the input queue will unnecessarily be large. So AFL optimized on this technique and called hit count of an edge, a bucket.

There are a total of 8 buckets.

AFL calls an input valuable only if there is a transition of a bucket. Lets say at the first input an edge is only gets triggered 1 time (or in simple terms if loop runs for 1 time), it falls in bucket A (valuable input), and if loop runs for 2 times it falls in bucket B (again valuable input because bucket changed on this input).

From the input queue, AFL takes 1 input, mutates it by bit flip, arithmetic or splicing technique and then re-run the program on that mutated input. If it finds a new edge/bucket transition it adds that mutated input in the input queue, else discards that input and takes the next input from the queue and repeats the whole process again.

With time input queue grows large enough. And maybe some entries in the input queue are redundant, meaning the coverage of one input is a subset of another input. So to speedup things it re-evaluates input queue periodically and takes out favoured subset of inputs (this is called culling). How? It goes through all the tuples list (edges) and finds out entry that reaches at the tuple most efficiently; fast and small, marks it as favoured and repeat this process for whole entries.

There are two mutation approaches that AFL uses. In the first part it uses a deterministic approach. Means for each input queue entry it flips bis, does arithmetic operations and inserts hardcoded values at every offset i.e., 0, -1, INT_MIN, INT_MAX. Also, if a deterministic approach lets say bit flip is not working at some area of the code then for later deterministic passes on that same file it will completely skip that part of the code. In the second part AFL becomes crazy and uses a non-deterministic/havoc approach combining operations like bit flips, arithmetic, and deleting chunks of inputs in one go. Or can bring two different files from the input queue and see what happens (splicing).

Big input files make the program slower and mutations on those files might not be as effective. Hence, AFL has a built in trimmer that tries to delete chunks of the input files. If it shows zero changes the execution trace. AFL keeps the file smaller.

When fuzzing a program it can generate a ton of crashes and chances are those crashes might be getting triggered by the same underlying bug. AFL considers a crash unique iff:

1. it contains a tuple (edge) never seen in any previous crash. or
2. It’s missing a tuple (edge) that was present in previous crashes.

Rather than testing every test case separately like running the same program, loading and linking libraries and run time initialization and then test an input. It’s a lot of manual and repeated work. If we have millions of inputs. AFL fixes it by running the program far enough to reach the very first instrument and then waits. From there AFL creates a copy fork() of that initialized and paused program. Hence no execve. Other than basic fork server AFL provides deferred fork server where we can skip initial manual setup and pause the program wherever we want. And it also provides persistent mode where we can reuse a single process/program across all inputs.

If we are given source code we just use afl-gcc compiler and we get a binary in which branches get IDs assigned (coverage guided). But if we don’t have source code then afl uses QEMU USER MODE EMULATION¹ help. Rather than running a program on our CPU it runs on QEMU Emulator. When QEMU takes in binary and translates² the program for our CPU. During that translation process AFL assigns IDs to the branches.

Rather than running a single instance we can run multiple AFL instances (each instance for each core). So that every instance checks every other instances’ input queue and if there is something interesting in the queue of any instance others can copy that. Also we can give them completely different input format dictionaries and later they can sync in their input queues (this is called synergistic coverage).

Thanks to Muhammad Danish for reading drafts of this.

References

1. M. Zalewski, “american fuzzy lop (2.53b),” https://lcamtuf.coredump.cx/afl/
2. M. Zalewski, “Technical ‘whitepaper’ for afl-fuzz,” https://lcamtuf.coredump.cx/afl/technical_details.txt, 2016.
3. Google, “AFL - american fuzzy lop,” https://github.com/google/afl, 2016.