Guided Fuzzing with Driller


Guided Fuzzing with Driller

At GRIMM, we are always trying out new tools to build our capabilities in vulnerability research. We frequently use fuzzing to search for bugs in applications, but there are some bugs a fuzzer alone would not be able to find. So, we were excited to try out Driller, a tool written by Shellphish. Driller uses symbolic execution to find new parts of the code to fuzz, helping the fuzzer to find bugs that it might not have reached otherwise. We found it a little tricky to get up and running, but it did succeed in helping a stuck fuzzer to make progress, so it seems like a potentially valuable tool. In this post, we’ll show how we installed AFL and Driller on Linux, and discuss our experiences using and troubleshooting it.

How Does Driller Work?

Fuzzing is an extremely useful technique for discovering software bugs that can cause crashes, which often lead to vulnerabilities. A fuzzer provides randomly-generated inputs to a target program, attempting to find inputs that cause the program to crash. Instrumentation can be added to the target program to find when an input causes it to take a new execution path, allowing the fuzzer to focus on inputs that are similar to these promising ones. This technique of instrumentation-guided fuzzing is exemplified by the American Fuzzy Lop fuzzer (AFL), and has been used to find many real bugs.
However, fuzzing has some limitations as well. Some programs have branch points that are only taken in very specific circumstances. For example, the program might require a specific input format like JSON, or check part of the input against a magic number. Inputs that don’t match these requirements would always be processed by the program’s error handling, not testing the main logic of the program at all. The fuzzer, which just generates inputs randomly, needs some help to arrive at the correct format.
We can give it help in the form of concolic execution (i.e. symbolic execution along a concrete path). Driller performs concolic execution on a run of the program, analyzing it as though each instruction were an algebraic function, where the inputs, memory, and registers of the program are the variables and the CPU instructions are the operators (add, subtract, mod, etc.). Given the final algebraic expression, a constraint solving tool can be used to solve for the input that would produce that result. Because real programs have so many instructions and potential paths, it is infeasible to analyze them from beginning to end. Instead, Driller looks at the inputs that AFL has deemed interesting, and steps along the execution paths those inputs cause the program to take. At each branch point in the execution path, it checks whether AFL has already seen both sides of the branch. If not, this is a potential new path! It applies the constraint solver to try and find an input that takes the program in the new direction. If it finds an input, it feeds it back into AFL.
Using this feedback loop, Driller should be able to help AFL get unstuck. AFL can pick up the input suggested to it by Driller, and use it as a starting point to which it randomly applies various types of mutations. If we are lucky, there is some vulnerable code behind that new branch, and AFL now has a chance to exercise it.

Tool Setup

Let’s get all of our tools set up. Though Shellphish provides git repositories1 that incorporate AFL, Driller, and tools to link them together, instead we’re going to install AFL and Driller separately so that it’s easier to see what’s going on.

AFL

Download and build AFL from the developer’s website http://lcamtuf.coredump.cx/afl/
$ sudo apt install build-essential libtool-bin automake bison flex python libglib2.0-dev
$ mkdir ~/driller
$ cd ~/driller
$ wget http://lcamtuf.coredump.cx/afl/releases/afl-2.52b.tgz
$ tar xf afl-2.52b.tgz
$ cd afl-2.52b
$ make
To build “QEMU mode,” which we need so that AFL and Driller can execute programs the same way, we must download a patch for QEMU and modify the build script to apply it:
$ cd qemu_mode
$ wget -O patches/memfd.diff https://salsa.debian.org/qemu-team/qemu/raw/ubuntu-bionic-2.11/debian/patches/ubuntu/lp1753826-memfd-fix-configure-test.patch
$ sed -i '/syscall.diff/a patch -p1 <../patches/memfd.diff || exit 1' build_qemu_support.sh
$ ./build_qemu_support.sh

Driller

Install some needed tools:
$ sudo apt install python3 virtualenv git python3-dev
Set up the virtual environment:
$ cd ~/driller
$ virtualenv -ppython3 venv
$ source venv/bin/activate
Install Python dependencies (these are needed as of the latest update to this post, but may no longer be needed depending on how the Driller repo has evolved):
$ pip install git+https://github.com/angr/archinfo
$ pip install git+https://github.com/angr/cle
$ pip install git+https://github.com/angr/claripy
$ pip install git+https://github.com/angr/angr
$ pip install git+https://github.com/angr/tracer
Install Driller itself:
$ pip install git+https://github.com/shellphish/driller

Target Setup

To show the basic functionality of Driller, we are going to try fuzzing a toy program named buggy. This program simply reads 6 bytes of input, checks them one by one against a sequence of characters, and crashes if all 6 of them match. The source code for the program (~/driller/buggy.c) follows:
#include <stdio.h>
#include <unistd.h>

int main(int argc, char *argv[]) {
  char buffer[6] = {0};
  int i;
  int *null = 0;

  read(0, buffer, 6);
  if (buffer[0] == '7' && buffer[1] == '/' && buffer[2] == '4'
      && buffer[3] == '2' && buffer[4] == 'a' && buffer[5] == '8') {
    i = *null;
  }

  puts("No problem");
}
We compile the program:
$ cd ~/driller
$ gcc -o buggy buggy.c
And test that it works as expected:
$ echo 123456 | ./buggy
No problem
$ echo 7/42a8 | ./buggy
Segmentation fault (core dumped)

Basic Fuzzing with AFL

Set up a working directory:
$ cd ~/driller
$ mkdir -p workdir/input
Begin with a seed file, or several. These should be valid inputs for the program, and should exercise as many different features as possible. For our toy program, we’ll be lazy:
$ echo 'init' > workdir/input/seed1
Now run the fuzzer:
$ # AFL will complain if the default core pattern is used
$ echo core | sudo tee /proc/sys/kernel/core_pattern
$ afl-2.52b/afl-fuzz -M fuzzer-master -i workdir/input/ -o workdir/output/ -Q ./buggy
Let’s go through those flags one by one:
  • -M fuzzer-master - this puts AFL in parallel fuzzing mode, and sets its ID to “fuzzer-master.” Parallel fuzzing mode will cause it to watch for interesting inputs in the directories alongside its own, which is how Driller will tell it about inputs it has found.
  • -i workdir/input/ - this sets the input directory for AFL. It performs a one-time read of the files in this directory and adds them to the queue of inputs to be tested and mutated.
  • -o workdir/output/ - this sets the output directory for AFL. This directory contains all of AFL’s state and results.
  • -Q - this makes AFL use QEMU mode for fuzzing. This means that the program is run in an instrumented QEMU emulator rather than on the bare metal, allowing AFL to be used on programs with no source code available.
After this runs for a while, the screen will look something like this:


As you can see, it has found no crashes so far, but it has found 5 different paths through the binary. These correspond to matching 0, 1, 2, 3, and 4 characters of the magic string, as we can see by looking at the inputs that have been generated:
$ cat "workdir/output/fuzzer-master/queue/id:000000,orig:seed1"
init
$ cat "workdir/output/fuzzer-master/queue/id:000001,src:000000,op:havoc,rep:2,+cov"
77it
$ cat "workdir/output/fuzzer-master/queue/id:000002,src:000001,op:flip2,pos:1,+cov"
7/it
$ cat "workdir/output/fuzzer-master/queue/id:000003,src:000002,op:havoc,rep:2,+cov"
7/4i
$ cat "workdir/output/fuzzer-master/queue/id:000004,src:000003,op:havoc,rep:2,+cov"
7/42
However, it doesn’t seem to be making any more progress. AFL’s havoc algorithm will try lots of random mutations, so it may eventually hit upon more characters of the string, but let’s see if we can use Driller to take a more targeted approach.

Getting Unstuck with Driller

We have written a custom script to run Driller. Its basic operation is to iterate through all the files in workdir/output/fuzzer-master/queue (the files that AFL has found interesting) and pass them to Driller as seeds. Any new interesting outputs that Driller finds will be placed in workdir/output/driller/queue, where AFL will discover them via the parallel fuzzing interface. If AFL also finds the inputs interesting, it may be able to use them to make more progress. However, Driller doesn’t appear ever to increase the length of the input, so none of these inputs will lead to Driller finding the crash. So, our script also modifies the existing inputs with some extra bytes, giving the solver room to find the new paths. Here is the ~/driller/run_driller.py script:
#!/usr/bin/env python

import errno
import os
import os.path
import sys
import time

from driller import Driller


def save_input(content, dest_dir, count):
    """Saves a new input to a file where AFL can find it.

    File will be named id:XXXXXX,driller (where XXXXXX is the current value of
    count) and placed in dest_dir.
    """
    name = 'id:%06d,driller' % count
    with open(os.path.join(dest_dir, name), 'wb') as destfile:
        destfile.write(content)


def main():
    if len(sys.argv) != 3:
        print('Usage: %s <binary> <fuzzer_output_dir>' % sys.argv[0])
        sys.exit(1)

    _, binary, fuzzer_dir = sys.argv

    # Figure out directories and inputs
    with open(os.path.join(fuzzer_dir, 'fuzz_bitmap'), 'rb') as bitmap_file:
        fuzzer_bitmap = bitmap_file.read()
    source_dir = os.path.join(fuzzer_dir, 'queue')
    dest_dir = os.path.join(fuzzer_dir, '..', 'driller', 'queue')

    # Make sure destination exists
    try:
        os.makedirs(dest_dir)
    except os.error as e:
        if e.errno != errno.EEXIST:
            raise

    seen = set()  # Keeps track of source files already drilled
    count = len(os.listdir(dest_dir))  # Helps us name outputs correctly

    # Repeat forever in case AFL finds something new
    while True:
        # Go through all of the files AFL has generated, but only once each
        for source_name in os.listdir(source_dir):
            if source_name in seen or not source_name.startswith('id:'):
                continue
            seen.add(source_name)
            with open(os.path.join(source_dir, source_name), 'rb') as seedfile:
                seed = seedfile.read()

            print('Drilling input: %s' % seed)
            for _, new_input in Driller(binary, seed, fuzzer_bitmap).drill_generator():
                save_input(new_input, dest_dir, count)
                count += 1

            # Try a larger input too because Driller won't do it for you
            seed = seed + b'0000'
            print('Drilling input: %s' % seed)
            for _, new_input in Driller(binary, seed, fuzzer_bitmap).drill_generator():
                save_input(new_input, dest_dir, count)
                count += 1
        time.sleep(10)

if __name__ == '__main__':
    main()
In another terminal, we run this script for a while:
$ cd ~/driller
$ source venv/bin/activate
$ python run_driller.py ./buggy workdir/output/fuzzer-master
And eventually AFL discovers a crash!


Since AFL names its findings according to how it got them, we can see that it imported one output from Driller into its queue:
$ cat "workdir/output/fuzzer-master/queue/id:000005,sync:driller,src:000016,+cov"
7/42a
And that the crashing input also came directly from Driller:
$ cat "workdir/output/fuzzer-master/crashes/id:000000,sig:11,sync:driller,src:000034"
7/42a8
This shows the effectiveness of Driller at finding specific inputs that lead to new paths, but if we observe the process carefully we can also see a limitation of the AFL/Driller combination. Driller produced the string “7/42a”, but because it only explores one branch away from the path its seed takes, in order to find the final crash, “7/42a8”, it must receive “7/42a” as input. Thus the crashing output is not produced until AFL imports “7/42a” into its queue, and Driller is run on that new input. It works, but it takes a long time for findings to propagate back and forth.

All-in-One Fuzzing with Shellphuzz

For simplified usage, this repository contains a script, shellphuzz, that combines the AFL and Driller runs into a single command. We have contributed a feature to this tool that tries extending the length of the input passed to Driller, which allows it to find the crash in our test program. After installing according to the instructions in the README of the fuzzer repo, the following command should find the bug:
$ shellphuzz -d 1 -c 1 -w workdir/shellphuzz/ -C --length-extension 4 ./buggy
However, in this post we chose to use our own script to better show the interaction between Driller and AFL. Additionally, the repo containing shellphuzz is currently in archive mode, so it is uncertain whether it will receive any further features or bugfixes.

Working with Real Programs

Most programs worth fuzzing are not very much like our toy program. Even the simplest real program has more complex logic than this one, and most use features like data structures, parsing, shared libraries, network and file I/O, and threads as well. If Driller is to be useful for real-world vulnerability research, it must be able to handle some of these complexities.
Using AFL as the fuzzer brings with it certain limitations. For example, AFL expects its targets to take all their input from standard input or from a file specified in the command line, and to exit after processing one input. Many larger programs don’t follow this pattern, such as long-lived network servers or applications with a Graphical User Interface (GUI). There are ways to work around this though. If the target’s source code is available, a driver can be written that reads input from stdin and calls functions to test in the target. Alternatively, Preeny can be used to turn network I/O into local I/O, and binaries can be patched to exit after input processing instead of serving indefinitely. One can even use an entirely different fuzzer, as long as it tracks coverage in a compatible format to AFL’s fuzz_bitmap. Some other fuzzers that use this format include AFLFastFairFuzz, and GRIMM’s own Killerbeez fuzzer. With a little coding, Driller could also be modified to understand a different format, if the features of a specific fuzzer are needed.
Of course, for all these awesome features, there are also some issues. It can sometimes be a challenge to get Driller to load a binary at all. Angr (the symbolic analysis engine behind Driller) contains a custom component, CLE, to load binaries into memory rather than using the standard Linux loader. This is for performance reasons; it means that Angr does not have to symbolically emulate each instruction of the Linux loader for every binary it wants to run, which would take a lot of redundant processing. However, it means that the loading is not guaranteed to be exactly the same as what the real loader would do. This led to some problems, including false positives when analyzing code that calls into shared libraries, because the library addresses used by the symbolic execution did not match up with the ones seen by AFL.
The loader differences also caused some difficulties when working with binaries that link against libpthread. After digging deep into the code of glibc, we learned that a function pointer that was supposed to be set up upon loading libpthread was not being set when loaded by CLE. We submitted https://github.com/angr/angr/pull/558 to fix this specific issue, but the fact remains that this type of problem can occur with concolic execution, and to debug it requires much deeper knowledge of Linux system internals than a typical fuzzer issue.
Driller also suffers from a problem common to many tools that use symbolic execution: performance. Even on our tiny binary, Driller takes about 3 minutes to run on each input, and for a more complex binary with more branches to investigate it takes even longer. Multiple Driller processes can be run in parallel to process multiple seed inputs, but it’s a tradeoff; the user must decide how many cores should run the fuzzer and how many should run Driller.

Conclusion

Driller is a very cool vulnerability discovery tool that brings together two powerful techniques into a feedback loop, using concolic execution to find new code for the fuzzer to fuzz, and taking interesting fuzzing results as the starting point for concolic exploration. It is not trivial to use, though. It is installed from several repositories that are not always in sync with one another, and when problems arise they tend to be subtle issues with the way the concolic execution loads or emulates a binary, which can be very time-consuming to debug. So, expect that you may need to spend some time improving the tool to support the features used by your particular binary. Once that’s done, though, Driller seems to be a powerful tool with the potential to find bugs that other automated tools would not.

Document History

  • 2018-05-16 Original release
  • 2019-07-01 Updated to work with Ubuntu 18.04 and Python 3, and to mention current status of shellphuzz

Popular posts from this blog

New Old Bugs in the Linux Kernel

Automated Struct Identification with Ghidra

SOHO Device Exploitation