University of Minnesota
Development of Secure Software Systems
index.php

CSci 4271 Lab 6

In this week's lab you'll try out the fuzzing tool AFL, to find interesting crashing inputs of programs. (To be precise we'll be using AFL++, a more recent forked version.)

We'll walk through using AFL on two different example programs, a very contrived example based on a text adventure game, and then the slightly more realistic buggy program from Project 1.

A good starting point for the documentation of AFL++ is discussion and links you can find on the AFL++ Github front page. It's too long to suggest you read through it all during lab, though. (A subset of this information is also available in the directory /usr/share/doc/afl++-doc). Another interesting documentation section is the explanation of what all the console statistics mean. It's also pretty long, but you might skim though it if you're otherwise just watching the statistics screen waiting for something interesting to happen.

CSE-IT has installed a suitable version of AFL++ on the workstations that are running Ubuntu 22.04. Also, because fuzzing can be CPU-intensive, it can be better to do on a non-shared machine. Therefore we recommend using the 1-250 lab workstations, either in person or remotely. If you want to try using Vole, the classic Vole cluster that is running Ubuntu 20.04 is too old: you'd need to try out the VOLEFX3 cluster that is now in testing. (In previous semesters we had also compiled our own newer version of AFL++ to run on Ubuntu 20.04, but while you still may be able to find it, these instructions don't recommend it.)

Because fuzzing involves creating, using, and removing files quickly, it will work noticeably faster if the files are kept on a local filesystem rather than a networked one like the CSE Labs home directories. On whatever machine you're using, we suggest creating yourself a directory under /export/scratch/users and doing your work there. The convention would be to name the subdirectory of users after your username, as in (replace "goldy007" with your username):

mkdir /export/scratch/users/goldy007
cd /export/scratch/users/goldy007
mkdir 4271-afl-lab
cd 4271-afl-lab

There are three programs from AFL++ that you'll need to use. afl-cc is a compiler that adds control flow instrumentation to make a binary suitable for use with AFL/AFL++, and afl-fuzz is the fuzzer itself. afl-tmin is a program to automatically simplify test cases. If you've followed our recommendation of using a CSE Labs Ubuntu 22.04 workstation, suitable versions of these programs should already be in your path. You can check the version of AFL available with this command (shown with the expected output) :

$ afl-fuzz -h 2>&1 | head -1
afl-fuzz++4.00c based on afl by Michal Zalewski and a large online community

Finding the crash in the maze

Our first example is a modeled after a text adventure game, where getting the program to crash is like a game event. You can try compiling the program normally and running it with commands on the standard input. It's simple enough that with a little bit of experimenting and/or reading the source code you should be able to find how to get to the magic potion.

cp /web/classes/Fall-2023/csci4271/labs/06/maze.c .
gcc -Wall -g maze.c -o maze
./maze

Next let's see if AFL can find the potion (crash) as well. First recompile the program using afl-cc:

afl-cc -g maze.c -o maze-for-afl

Though the maze that AFL needs to explore here isn't really that large, changing the input to the game randomly would take a long time to get it to the goal, because there are only a few legal commands. So the thing we can do that is most useful is to give it a dictionary of the legal commands in the game. This is like a simplified form of grammar-based fuzzing, where we just provide some useful tokens rather than a full grammar. We've supplied a sample dictionary you can use:

cp /web/classes/Fall-2023/csci4271/labs/06/maze.dict .

The other thing we have to give to get AFL started is a directory of seed inputs. A bunch of good seeds are potentially another way to give AFL information about what the input format should look like. On the other hand large seeds can cause some parts of AFL to slow down, so you can potentially put a lot of work into optimal seeds. But because we're already helping with the dictionary, choosing good inputs turns out not to be as important. Let's create a minimal set with just one:

mkdir maze-inputs
echo 'go north' >maze-inputs/input1

One other piece of trivia to deal with is that AFL suggests changing a couple of system options to make it run faster, but you won't be allowed to change those options on CSE Labs, so we need to use an environment variable AFL_SKIP_CPUFREQ=1 to tell AFL not to worry. (The performance loss won't be too bad for our purposes.) On some other systems (including out-of-the-box Ubuntu systems), you may also need to set the environment variable AFL_I_DONT_CARE_ABOUT_MISSING_CRASHES=1 if you can't change the way crash reporting works to be compatible with AFL. This is a slightly more serious problem that can cause some crashes to be misclassified as hangs, so if you're running this on your own computer you might consider taking AFL's advice of changing the setting. But in our recent testing the CSE Labs machines don't need this. So putting together all those resources, the command to start AFL looks like:

env AFL_SKIP_CPUFREQ=1 afl-fuzz -i maze-inputs -x maze.dict -o maze-results -- ./maze-for-afl

Once you start AFL running, it will take over its terminal with a bunch of statistics about the execution. While it is running, it will fill the directory specified with -o, maze-results in our example command, with the interesting inputs it finds: inputs that cause new code to be executed, inputs that cause crashes, and inputs that cause execution to take much longer than expected (called hangs). These input files are kept in subdirectories of maze-results, specifically ones named default/queue, default/crashes, and default/hangs. If you're waiting to get good results as shown by the execution statistics, you can open another terminal at the same time and use it to look at the generated files. The files in the queue directory will give you an idea of how AFL is exploring the search space, while the crashes and hangs are the results that it has found so far. The file names in these directories have long names that give some information about what step of the fuzzing process produced them.

The maze example should run pretty quickly. If you're using a scratch drive on a lab machine, you should see it able to execute around 6000 or more tests per second (shown as exec speed) in the statistics, and it should start finding crashes within a minute or faster. (Vole machines can be noticeably slower, especially if other students are using them at the same time.) The fuzzing process is potentially endless, so you'll need to decide when you want AFL to stop, by typing Control-C is its terminal window. In the real world, you would often run a fuzzer for hours or days to find the most interesting results. But because your time in lab and the CSE Labs' computing power are limited, we've tried to pick the examples in this lab so that you can get results fairly quickly. If you aren't seeing the results you're expecting after a few minutes, you should try to debug what's happening.

Because the maze program is tolerant of a lot of junk in its input (unknown commands are just ignored), AFL's default mode will produce long crashing inputs with a mix of legal commands and random data. If you just wanted to confirm that the program had a bug or trigger it under the debugger, this would be enough. But for understanding the program it would be nice to have cleaner-looking crashing inputs. AFL has a companion tool based on the same execution experiment infrastructure that searches for ways to make test inputs smaller, which generally also makes them cleaner-looking. You can run it on one of the crashes you've found using a command like:

afl-tmin -i maze-results/default/crashes/id:000000,* -o crash-reduced.in -- ./maze-for-afl

That particular command will try to minimize the first crash, or you can replace the id:000000,* with the name of a particular test case you're interested in. The output file crash-reduced.in will be a simplified crashing input.

If you're feeling lazy, you might be wondering whether it's possible for AFL to find relevant strings from the program automatically, instead of us having to create a dictionary manually. In fact AFL++ has a couple of features designed for exactly this purpose. They just require the extra step of compiling the program with a special option (an environment variable). To do this example in "cmplog" mode, change the compilation command to:

env AFL_LLVM_CMPLOG=1 afl-cc -g maze.c -o maze-for-afl-cmplog

And then supply this program with the -c option to afl-fuzz (eliminating the need for the dictionary):

env AFL_SKIP_CPUFREQ=1 afl-fuzz -i maze-inputs -c $(pwd)/maze-for-afl-cmplog -o maze-results -- ./maze-for-afl

Crashing c4

You can use the same basic process of fuzzing to find crashes in lots of different programs. As a slightly more realistic example, let's next take a look at "c4", a very smaller interpreter for the core of the C programming language. (The name c4 comes from being implemented using only four functions, though as you might expect all four functions are pretty complicated.) The program is open-source and you can see the original version on its GitHub page.

The original version can be compiled by GCC as well as executed by itself, but it achieves this by being loose with the type system in a way that the Clang compiler used by AFL doesn't like. So we've had to make a small change to make it compile with afl-cc.

cp /web/classes/Fall-2023/csci4271/labs/06/c4-afl.c .
afl-cc -Wno-format -Wno-parentheses -Wno-main-return-type -g c4-afl.c -o c4-afl

You can potentially use a variety of C programs as seeds, but a simple starting place is the two C programs that come in the c4 source code, c4.c itself and a hello-world program hello.c.

git clone https://github.com/rswier/c4.git
mkdir c4-inputs
cp c4/c4.c c4/hello.c c4-inputs

Another thing that needs to be slightly different in the command is how to tell AFL to run the binary: you give it a template that can contain other options, but then has the location where the input filename should go replaced with @@. So for instance the command might look like:

env AFL_SKIP_CPUFREQ=1 afl-fuzz -i c4-inputs -o c4-results -- ./c4-afl @@

Given that c4 implements an unsafe language even when it's working correctly, and the code seems to not have very many bounds checks, the fuzzer should be able to find a crash without too much searching. It's also definitely also possible to make it go into an infinite loop. However you'll see that the two programs hello.c and c4.c are not a great seed set: hello.c is too small to cover much code, while c4.c is large enough that it leads to large crashes that are hard to read. Try creating some other short seed files that are legal according to C4's rules so that AFL can create a wider variety of short crashing or hanging inputs.

Crashing a decompression program

If the previous programs seemed too small or unrealistic, here is one that is more complicated. We've created a simplified decompression utility for the lzip file format; but it still handles the full file format, so it's about 1600 lines of code. Except that whereas the real implementation this is derived from has already been tested and fuzzed and is probably pretty robust, this version contains a memory safety bug that might be triggered in unusual circumstances. The bug isn't very stealthily hidden, so you might also be able to find it just by auditing the code, but 1600 lines of code would take a while just to read. So you could think of this as a race between whether you or AFL can find the problem first. You can copy the program source code with this command:

cp /web/classes/Fall-2023/csci4271/labs/06/mini-lunzip-bug1.c .

You can compile the program in the normal way. It is similar in behavior to the command lzip -dc in that it reads a file compressed in lzip format and prints the decompressed result to the standard output; a single file name should be the only command-line input and no options are supported. So you can run it with @@ similar to c4. We haven't given you any seed inputs, but you can make some with lzip.