Fuzzing Part 02, AFL++
So in our previous post we discussed AFL. But its old and has some limitations. So to overcome those limitations every research group created their own fork (copy) of AFL and tweaked it for their personal use. But there was no actively maintained solution that combined all (or i should say most of) those AFL gaps. And that’s where AFL++ comes in.
Note: Main purpose of this post is to understand AFL++ w.r.t AFL. Essentially whats improved after AFL. The idea behind AFL++ was to (1) combine incremental research in one tool (2) add a new custom mutator (plug-in-play) thing (3) provide more configuration and control over fuzzing.
Just to understand AFL++ we will divide its components in 4 major parts.
Scheduling
AFL used to have a fixed approach on how much energy1 to give the current seed2 and which mutation operators3 to apply. Instead of using this fixed approach, why not spend more energy on what’s working by giving energy inversely proportional to how often its path has already been hit and increase a seed’s energy gradually only if it pays out.
Note that this way we find things efficiently (it finds the same bugs as AFL but just a little faster).
In AFL++ -p is the power schedule.
What makes one seed more valuable than the other? Bohme in his paper tells that its information gain. Bohme and his team developed Entropic, an entropy-based power schedule for greybox fuzzing which assigns more energy to seeds that maximize information about program’s behaviour.
Note: Entropic is not implemented in AFL++ but AFL++ docs suggest running a LibFuzzer with Entropic alongside AFL++ and sharing corpus helps in finding program behaviour.
AFL’s undeterministic (or havoc) stage picks mutation operators like bitflip, splicing uniformly at random. Means it doesn’t matter which program we have, AFL will apply bit flips. And it’s a fixed approach for every program. And might not work for all programs.
To solve this approach MOPT paper introduced this Particle Swarm Optimization approach. In this approach it continuously re-weights each mutation operator based on how many interesting inputs it has produced and groups the best.
In AFL++ we can opt this approach using the -L flag.
Comparisons
AFL had issues with magic bytes4 and checksum5. Conditions like if (input == 0xdeadbeef) would require AFL to guess it all or none. And there was no credit if AFL guessed half right.
To solve this magic bytes issue LAF-Intel introduced this new approach in which we rewrite the code at compile time. So one hard 4-byte comparison becomes 4 easy 1-byte comparisons. So if fuzzer gets correct predictions of an edge it gets credit. LAF-Intel uses LLVM and compiler pass to achieve this. But it only helps for constants that are known at compile time (works for magic bytes only). So it doesn’t work for checksums.
To solve checksums a new paper RedQueen / CmpLog introduced this new technique in which we don’t solve comparisons instead we just watch the value program checks for and for the next input we just overwrite the value program wanted. To do this in AFL++ we build a second copy of the target with AFL_LLVM_CMPLOG=1, then point AFL++ at it with -c.
Coverage and Instrumentation
Remember AFL had hash collisions in its coverage map meaning two different edges get assigned the same slot in 64KB. So chances are that a valuable input gets thrown away. To fix this issue AFL++ assigns IDs to the edges at the link time via its LTO and PCGUARD instrumentation modes.
And for detailing purposes AFL++ has two techniques. The first one is context-sensitive (ctx): in this technique AFL++ counts the same edge depending upon which function calls it. Another technique is n-gram to remember n number of edge (a middle ground between a single edge and a full path)
In AFL++ we can trigger those techniques by using AFL_LLVM_INSTRUMENT=CTX and NGRAM-2..16.
If A block dominates B block and every execution path must pass A to reach B. So writing only both in the coverage map is useless and time consuming. We can trigger this using AFL_LLVM_INSTRIM=1.
Directed, structure-aware & custom mutators
AFL used to explore the whole program. But directed fuzzing aims for one specific location. This helps when you want to trigger some specific bug or you want to verify whether your applied patch is working or not.
Now intuitively we know that blind mutation is not useful as it shreds structured inputs i.e., JSON, network packets before they even get past the format check. That’s why AFL++ introduced custom mutator. You write a small file that understands how to a edit particular format and then load it in AFL++ with AFL_CUSTOM_MUTATOR_LIBRARY=./mut.so or AFL_PYTHON_MODULE=….
It also builds dictionaries automatically.
So, in conslusion, AFL++ is a great utility and provides very good control over fuzzing binaries. But what if we want to fuzz targets that are non standard? like, fuzzing WebAssembly runtime. This is where comes LibAFL. We will be discussing it in the next post.
Stay tunned.