AFL: American Fuzzy Lop

Fuzzing is essentially feeding random/weird/mutated inputs and finding out where these inputs crash the program (which usually mean 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 program that parses a file format starting with a 4-byte magic header GIF8.

if (memcmp(buffer, "GIF8", 4) != 0) {
  return 0;
}

The blind fuzzer will almost never make out of this if condition. Why? Because blind fuzzer will try a list/file of random inputs. Like {'AAAA', 'BBBB', 'CCCC', 'DDDD', 'EEEE', 'FFFF', 'GGGG', ...} and wait if the program crashes or not. AFL solves this issue.

What AFL tries to solve?

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

In 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 comparison G->G (thats the feedback). But how does AFL knows 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 the compile time. And when program execution ends it saves branches covered by inputs (called hit records) in a shared memory of 64KB.

AFL doesnt only track branches it also looks for edges. How? It XOR out current and previous branches to find out a unqiue edge. Now, if an input finds out either a new branch or a new edge its valuable, esle it will be discarded.

Most of the time a program contains loops and if a loop runs for 100 times, it means 100 edges. We cannot keep all those n values as valueable inputs for two reasons 1. because our input queue will grow large, 2. most of those inputs might be the subset of 1 input. So AFL optimized on it and called hit count of an edge a bucket.

for (int i = 1; i <= n; i++) {
  printf("%d ", i);
}

There are total 8 buckets

So if an edge is only triggered 5 times, it falls in bucket D, but if it gets triggered 128 time or 1 million times it will fall in bucket H. So if a valuable input was found earlier which triggered bucket H by running an edge 128 times.

From the input queue, AFL takes 1 input, mutates it by bit flip, arithmetic or splicing technique and then re-run program on that mutated input. If it finds new edge/bucket transition it adds that mutated input in the queue, else discards that input. and takes the next input from the queue and repeats the whole process again. Note that it does not use greedy approach mean doesnt keep only single best input and mutates over it. Instead it keeps all inouts that are interesting.

With time input queue grows large enough. And maybe some entries in the input queue are redundunt means their coverage is subset of another input. So to speedup things it re-evaluates input queue periodically and takes out favoured subset of inputs. 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.

In the first part it uses deterministic approach. Means for every queue entry it flips bis, does arithmetic operations and insert hardcoded values at the every offset i.e., 0, -1, INT_MIN, INT_MAX. Also, if deterministic approach lets say bit flip is not working at some area of the code then for the next queue entry it will completely skip that part of the code. In the second part AFL becomes crazy and uses 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 slowers and mutations on those files might not be as effective. Hence, AFL has 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 underlysing bug. AFL considers a crash unique iff 1. it contains a tuple (edge) never seen in any previous crash. or 2. its missing a tuple (edge) that was present in previous crashes.

Rather than testing every test case separately Like running a same program, loading and linking libraries and run time initialization and then test an input. Its alot of manual and repeated work. If we have millions of inputs. AFL fixes it by running the program for enough to reach the very first instrument and then waits. From there AFL creates a copy (fork()) of that initialized and paused progam. Hence no execve. It provides two advantages: 1 is defferred fork server: means skipping initial manual setup 2 is persistent mode: reusing a single process/program across all test cases (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 dont have source code then afl uses QEMU USER EMULATION help. Rather than running a program on our CPU it runs on QEMU Emulator. When QEMU takes in binary and translate the program for our CPU. During that tranlation process AFL assign IDs to the branches. The main advantage here is with the help of QEMU we can run cross-architecture binaries (like running ARM binaries on x86 machine).

Rather than running a single instance we can run multiple AFL instances (each instance for each core). It has two advantages: First one is every instance checks every other instances’ queue so if there is something interesting in the queue of 1 instance others can copy that. Another advantage is we can give them completely different input format dictionaries and later they can sync in their input queues (this is called synergitic coverage).

And… What’s the problem with AFL?

[to be continued…]