Programming Assignment #1
Weakening Strong Constraints for AFL
Software Security (CS52700) Fall-16, Purdue University
- Due date: 11:59pm, Sep 16, 2016
Introduction
Fuzz testing or fuzzing is a software testing technique popularly used to discover software vulnerabilities. It provides a massive number of random input data to a target program in hopes that the program crashes sometime. This crash event may have a strong potential to be a vulnerability, as the crash itself manifests some unexpected behaviors of a target program. In practice, most fuzzers are targeted to discover memory corruption vulnerabilities.
In this programming assignment, we will try to improve one of the most well known fuzzer, AFL. While AFL provides many interesting features, one of the most outstanding feature is its design in using genetic algorithms to better trigger new program states in a target binary --- maintaining an internal state matrix and updating the matrix according to something similar to n-grams of basic blocks (so you can say AFL is using a simple, yet effective, machine learning technique). Before you get started on this assignment, I strongly recommend you fully read through README documentation of AFL and run it for some programs (tutorial).
Motivation - Strong constraints are not fuzzer friendly
Consider the following code snippet.
if (x == 0x12345678) {
// then-block
// Assume there's some vulnerable code here.
}
Assuming x
is the input variable of a target program, randomly
mutating x
would highly unlikely hit the then-block condition, as
the chance of satisfying the given predicate is around 1/(2**32)
. As
such, fuzzers, which generally employs a random mutation, cannot
trigger the above condition, and thus fail to discover a vulnerability
in then-block. Note, symbolic execution techniques, including
KLEE or
angr, do not suffer from this issue in general, and
we will cover these techniques in the class later).
Now let's consider semantically the same, but a bit tweaked code.
if ((x>>24 && 0xff) == 0x12) {
// match1-block
if ((x>>16 && 0xff) == 0x34) {
// match2-block
if ((x>>8 && 0xff) == 0x56) {
// match3-block
if ((x>>0 && 0xff) == 0x78) {
// then-block
}
}
}
}
As you can see, while it checks the condition for four times, the code
basically performs the same logic --- execute then-block
only if the
variable x
is 0x12345678
. While this simple transformation may
seem pointless, it may dramatically improve AFL in exploring the
then-block
. The secret lies in the fact how AFL mutates the input.
Once AFL hits match1-block
, it will keep the corresponding input and
mutate it again until it hits match2-block1
. This process will be
repeated until it hits then-block
. Therefore, a single event drawn
from 2**32
space is transformed into four dependent events drawn
from 2**8
space following the additional rule in probabilistic,
resulting in a significant search space reduction.
Some other researchers have posted this idea in the blog as well, and please check it out for more details. Also note that the blog posting mentions LLVM-based transformation, but we will do QEMU-based transformation.
Assignment - Weakening Strong Constraints in QEMU
Now we begin to describe how we automatically transform the target program to benefit AFL from this idea, which is the goal of this programming assignment. Specifically, we will take binary-based transformation, which doesn't require us to access the source code of a target program. In fact, AFL already implements this binary-based transformation using QEMU. Instead of natively run the target program, AFL's QEMU-mode emulates the program execution with the help of QEMU and instruments all necessary code on-the-fly through QEMU. In order to understand how this works, refer following links:
- QEMU internals
- The list of changes that AFL made to enable this instrumentation.
We will make similar changes as AFL's QEMU-mode did, but in a slightly different way --- instead of instrumenting at the basic block level, we will do the instrumentation at the instruction-by-instruction level. This is largely because our weakening idea needs to instrument and convert a branch instruction, which is difficult to be done at the basic block level. This instruction-by-instruction level instrumentation can be done with Tiny Code Generator (TCG).
Particularly for this project, you may want to focus on the function,
tcg_gen_brcond_i64()
. This function is invoked when QEMU translates
a conditional branch instruction, and you can run your additional
logic by invoking a runtime helper function. For example, the
reference implementation does the following:
- Modified
tcg_gen_brcond_i64()
inqemu_mode/qemu-2.3.0/tcg/tcg-op.c
to invoke a new runtime helper function. - Created a new runtime helper function in
qemu_mode/qemu-2.3.0/tcg-runtime.c
. According to the branch condition, this function updates the status of AFL by writing to theafl_area_ptr
matrix.
For your reference, the following shows a list of changed files (diff stats) to implement this assignment.
afl-1.86b/qemu_mode/patches/afl-qemu-cpu-inl.h | 2 +-
afl-1.86b/qemu_mode/qemu-2.3.0/tcg-runtime.c | 35 +++++++++++++++++++++++++++++++++++
afl-1.86b/qemu_mode/qemu-2.3.0/tcg/tcg-op.c | 24 ++++++++++++++++++++++++
afl-1.86b/qemu_mode/qemu-2.3.0/tcg/tcg-runtime.h | 2 ++
4 files changed, 62 insertions(+), 1 deletion(-)
Note, it is fine if your transformation only supports the specific architecture (i.e., x86 or x86-64), or takes place in the front-end (rather than in the backend). Moreover, the reference implementation is just one possible way to implement this functionality, and feel free to take some other approaches if you think it is more general and efficient.
How to Setup/Customize/Testing AFL
Descriptions below assume you have an access to the Linux-based machine with root privilege. If you do not have one, please read this.
We provide a basic setup script as well as testing scripts in our github repo for this course - https://github.com/lifeasageek/cs52700-public. You can follow the steps described below to setup the AFL with qemu_mode.
# Clone CS52700 setup/testing code
$ git clone https://github.com/lifeasageek/cs52700-public
# Download AFL and builds AFL (with qemu_mode)
$ (cd cs52700-public/prog-assign-1 && ./setup.sh)
Once the build is successful, now your system must be ready to run AFL
with QEMU. Our testing code (i.e., a sample vulnerable program to be
fuzzed) is located in cs52700-public/prog-assign-1/test/test.c
.
// test.c
#include <stdio.h>
#include <string.h>
#define MSG_HELO "> Started.\n"
#define MSG_VULN "> Vulnerability triggered.\n"
#define MSG_EXIT "> Exiting.\n"
#define BUFLEN 4
void crash() {
// Intentionally trigger the crash to simulate a vulnerability.
printf(MSG_VULN);
int *y = 0;
*y = 0x1234;
}
int main(int argc, char *argv[]) {
char c;
FILE *file;
char buf[BUFLEN];
if (argc <= 1) {
fprintf(stderr, "[-] ERROR: Not valid arguments\n");
return -1;
}
printf(MSG_HELO);
file = fopen(argv[1], "r");
if (!file) {
fprintf(stderr, "[-] ERROR: Failed to open a file [%s]\n", argv[1]);
return -1;
}
for (int i=0; i<BUFLEN; i++) {
c = getc(file);
if (c == EOF)
break;
buf[i] = c;
}
fclose(file);
#ifdef COND_WEAK
if (buf[0] == 0x54) {
// Weak condition. Original AFL can easily solve.
crash();
}
#else
unsigned int *x = (unsigned int*)buf;
if (*x == 0x54534554) { // x == "TEST"
// Strong condition. Original AFL cannot easily solve.
crash();
}
#endif
printf(MSG_EXIT);
return 0;
}
You can build this testing program with make
command, which
generates two executables, bin-weak and bin-strong, depending
on whether the definition (COND_WEAK) is given or not,
respectively.
As the branch condition is already weak enough (as it is only matching a one-byte), the original AFL can easily solve bin-weak (i.e., AFL can find a crashing input) in a very short time. For example, if you run AFL with the following command, you will see AFL immediately discovers crashing inputs.
$ cd cs52700-public/prog-assign-1/test
# Build testing code
$ make
# Run AFL on the binary, bin-weak.
$ make runafl-weak
The image below shows the running result of AFL using the command
make runafl-weak
. As you can see, AFL found total 140 crashes (with
2 unique crashes --- refer AFL's README for more details on unique
crashes) in 20 seconds.
However, in the case of bin-strong, as the branch condition is strictly restricted, the original AFL cannot solve it in a reasonable time. From our testing, no crashes were observed in an hour.
# Run AFL on the binary, bin-strong.
$ make runafl-strong
Now, your job is to modify AFL/QEMU so that AFL can solve
bin-strong way more efficiently. Note, the performance of fuzzers
are highly depending on the initial inputs (so called seeding inputs),
and you should NOT change the given initial input
(test/input/input.txt
) for fair testing.