This is a personal blog. My other stuff: book | home page | Twitter | prepping | CNC robotics | electronics

August 08, 2014

Binary fuzzing strategies: what works, what doesn't

Successful fuzzers live and die by their fuzzing strategies. If the changes made to the input file are too conservative, the fuzzer will achieve very limited coverage. If the tweaks are too aggressive, they will cause most inputs to fail parsing at a very early stage, wasting CPU cycles and spewing out messy test cases that are difficult to investigate and troubleshoot.

Designing the mutation engine for a new fuzzer has more to do with art than science. But one of the interesting side effects of the design of american fuzzy lop is that it provides a rare feedback loop: you can carefully measure what types of changes to the input file actually result in the discovery of new branches in the code, and which ones just waste your time or money.

This data is particularly easy to read because the fuzzer also approaches every new input file by going through a series of progressively more complex, but exhaustive and deterministic fuzzing strategies - say, sequential bit flips and simple arithmetics - before diving into purely random behaviors. The reason for this is the desire to generate the simplest and most elegant test cases first; but the design also provides a very good way to quantify how much value each new strategy brings in to the table - and whether we need it at all.

The measurements of afl fuzzing efficiency for reasonably-sized test cases are remarkably consistent across a variety of real-world binary formats - anything ranging from image files (JPEG, PNG, GIF, WebP) to archives (gzip, xz, tar) - and because of this, I figured that sharing the data more broadly will be useful to folks who are working on fuzzers of their own. So, let's dive in:
  • Walking bit flips: the first and most rudimentary strategy employed by afl involves performing sequential, ordered bit flips. The stepover is always one bit; the number of bits flipped in a row varies from one to four. Across a large and diverse corpus of input files, the observed yields are:

    • Flipping a single bit: ~70 new paths per one million generated inputs,
    • Flipping two bits in a row: ~20 additional paths per million generated inputs,
    • Flipping four bits in a row: ~10 additional paths per million inputs.

    (Note that the counts for every subsequent pass include only the paths that could not have been discovered by the preceding strategy.)

    Of course, the strategy is relatively expensive, with each pass requiring eight execve() per every byte of the input file. With the returns are diminishing rapidly, afl stops after these three passes - and switches to a second, less expensive strategy past that point.

  • Walking byte flips: a natural extension of walking bit flip approach, this method relies on 8-, 16-, or 32-bit wide bitflips with a constant stepover of one byte. This strategy discovers around ~30 additional paths per million inputs, on top of what could have been triggered with shorter bit flips.

    It should be fairly obvious that each pass takes approximately one execve() call per one byte of the input file, making it surprisingly cheap, but also limiting its potential yields in absolute terms.

  • Simple arithmetics: to trigger more complex conditions in a deterministic fashion, the third stage employed by afl attempts to subtly increment or decrement existing integer values in the input file; this is done with a stepover of one byte. The experimentally chosen range for the operation is -35 to +35; past these bounds, fuzzing yields drop dramatically. In particular, the popular option of sequentially trying every single value for each byte (equivalent to arithmetics in the range of -128 to +127) helps very little and is skipped by afl.

    When it comes to the implementation, the stage consists of three separate operations. First, the fuzzer attempts to perform subtraction and addition on individual bytes. With this out of the way, the second pass involves looking at 16-bit values, using both endians - but incrementing or decrementing them only if the operation would have also affected the most significant byte (otherwise, the operation would simply duplicate the results of the 8-bit pass). The final stage follows the same logic, but for 32-bit integers.

    The yields for this method vary depending on the format - ranging from ~2 additional paths per million in JPEG to ~8 per million in xz. The cost is relatively high, averaging around 20 execve() calls per one byte of the input file - but can be significantly improved with only a modest impact on path coverage by sticking to +/- 16.

  • Known integers: the last deterministic approach employed by afl relies on a hardcoded set of integers chosen for their demonstrably elevated likelihood of triggering edge conditions in typical code (e.g., -1, 256, 1024, MAX_INT-1, MAX_INT). The fuzzer uses a stepover of one byte to sequentially overwrite existing data in the input file with one of the approximately two dozen "interesting" values, using both endians (the writes are 8-, 16-, and 32-bit wide).

    The yields for this stage are between 2 and 5 additional paths per one million tries; the average cost is roughly 30 execve() calls per one byte of input file.

  • Stacked tweaks: with deterministic strategies exhausted for a particular input file, the fuzzer continues with a never-ending loop of randomized operations that consist of a stacked sequence of:

    • Single-bit flips,
    • Attempts to set "interesting" bytes, words, or dwords (both endians),
    • Addition or subtraction of small integers to bytes, words, or dwords (both endians),
    • Completely random single-byte sets,
    • Block deletion,
    • Block duplication via overwrite or insertion,
    • Block memset.

    Based on a fair amount of testing, the optimal execution path yields appear to be achieved when the probability of each operation is roughly the same; the number of stacked operations is chosen as a power-of-two between 1 and 64; and the block size for block operations is capped at around 1 kB.

    The absolute yield for this stage is typically comparable or higher than the total number of execution paths discovered by all deterministic stages earlier on.

  • Test case splicing: this is a last-resort strategy that involves taking two distinct input files from the queue that differ in at least two locations; and splicing them at a random location in the middle before sending this transient input file through a short run of the "stacked tweaks" algorithm. This strategy usually discovers around 20% additional execution paths that are unlikely to trigger using the previous operation alone.

    (Of course, this method requires a good, varied corpus of input files to begin with; afl generates one automatically, but for other tools, you may have to construct it manually.)

As you can see, deterministic block operations (duplication, splicing) are not attempted in an exhaustive fashion; this is because they generally require quadratic time (or worse) - so while their yields may be good for very short inputs, they degrade very quickly.

Well, that's it! If you ever decide to try out afl, you can watch these and other cool stats on your screen in real time.

August 04, 2014

A bit more about american fuzzy lop

Fuzzing is one of the most powerful strategies for identifying security issues in real-world software. Unfortunately, it also offers fairly shallow coverage: it is impractical to exhaustively cycle through all possible inputs, so even something as simple as setting three separate bytes to a specific value to reach a chunk of unsafe code can be an insurmountable obstacle to a typical fuzzer.

There have been numerous attempts to solve this problem by augmenting the process with additional information about the behavior of the tested code. These techniques can be divided into three broad groups:
  • Simple coverage maximization. This approach boils down to trying to isolate initial test cases that offer diverse code coverage in the targeted application - and them fuzzing them using conventional techniques.

  • Control flow analysis. A more sophisticated technique that leverages instrumented binaries to focus the fuzzing efforts on mutations that generate distinctive sequences of conditional branches within the instrumented binary.

  • Static analysis. An approach that attempts to reason about potentially interesting states within the tested program and then make educated guesses about the input values that could possibly trigger them.
The first technique is surprisingly powerful when used to pre-select initial test cases from a massive corpus of valid data - say, the result of a large-scale web crawl. Unfortunately, coverage measurements provide only a very simplistic view of the internal state of the program, making them less suited for creatively guiding the fuzzing process later on.

The latter two techniques are extremely promising in experimental settings. That said, in real-world applications, they are not only very slow, but frequently lead to irreducible complexity: most of the high-value targets will have a vast number of internal states and possible execution paths, and deciding which ones are interesting and substantially different from the rest is an extremely difficult challenge that, if not solved, usually causes the "smart" fuzzer to perform no better than a traditional one.

American fuzzy lop tries to find a reasonable middle ground between sophistication and practical utility. In essence, it's a fuzzer that relies on a form of edge coverage measurements to detect subtle, local-scale changes to program control flow without having to perform complex global-scale comparisons between series of long and winding execution traces - a common failure point for similar tools.

In almost-plain English, the fuzzer does this by instrumenting every effective line of C or C++ code (or any other GCC-supported language) to record a tuple in the following format:

[ID of current code location], [ID of previously-executed code location]

The ordering information for tuples is discarded; the primary signal used by the fuzzer is the appearance of a previously-unseen tuple in the output dataset; this is also coupled with coarse magnitude count for tuple hit rate. This method combines the self-limiting nature of simple coverage measurements with the sensitivity of control flow analysis. It detects both explicit conditional branches, and indirect variations in the behavior of the tested app.

The output from this instrumentation is used as a part of a simple, vaguely "genetic" algorithm:
  1. Load user-supplied initial test cases into the queue,

  2. Take input file from the queue,

  3. Repeatedly mutate the file using a balanced variety of traditional fuzzing strategies (see later),

  4. If any of the generated mutations resulted in a new tuple being recorded by the instrumentation, add mutated output as a new entry in the queue.

  5. Go to 2.
The discovered test cases are also periodically culled to eliminate ones that have been made obsolete by more inclusive finds discovered later in the fuzzing process. Because of this, the fuzzer is useful not only for identifying crashes, but is exceptionally effective at turning a single valid input file into a reasonably-sized corpus of interesting test cases that can be manually investigated for non-crashing problems, handed over to valgrind, or used to stress-test applications that are harder to instrument or too slow to fuzz efficiently. In particular, it can be extremely useful for generating small test sets that may be programatically or manually examined for anomalies in a browser environment.

(For a quick partial demo, click here.)

Of course, there are countless "smart" fuzzer designs that look good on paper, but fail in real-world applications. I tried to make sure that this is not the case here: for example, afl can easily tackle security-relevant and tough targets such as gzip, xz, lzo, libjpeg, libpng, giflib, libtiff, or webp - all with absolutely no fine-tuning and while running at blazing speeds. The control flow information is also extremely useful for accurately de-duping crashes, so the tool does that for you.

In fact, I spent some time running it on a single machine against libjpeg, giflib, and libpng - some of the most robust best-tested image parsing libraries out there. So far, the tool found:
  • CVE-2013-6629: JPEG SOS component uninitialized memory disclosure in jpeg6b and libjpeg-turbo,

  • CVE-2013-6630: JPEG DHT uninitialized memory disclosure in libjpeg-turbo,

  • MSRC 0380191: A separate JPEG DHT uninitialized memory disclosure in Internet Explorer,

  • CVE-2014-1564: Uninitialized memory disclosure via GIF images in Firefox,

  • CVE-2014-1580: Uninitialized memory disclosure via <canvas> in Firefox,

  • Chromium bug #398235, Mozilla bug #1050342: Probable library-related JPEG security issues in Chrome and Firefox (pending),

  • PNG zlib API misuse bug in MSIE (DoS-only),

  • Several browser-crashing images in WebKit browsers (DoS-only).
More is probably to come. In other words, you should probably try it out. The most significant limitation today is that the current fuzzing strategies are optimized for binary files; the fuzzer does:
  • Walking bitflips - 1, 2, and 4 bits,

  • Walking byte flips - 1, 2, and 4 bytes,

  • Walking addition and subtraction of small integers - byte, word, dword (both endians),

  • Walking insertion of interesting integers (-1, MAX_INT, etc) - byte, word, dword (both endians),

  • Random stacked flips, arithmetics, block cloning, insertion, deletion, etc,

  • Random splicing of synthetized test cases - pretty unique!
All these strategies have been specifically selected for an optimal balance between fuzzing cost and yields measured in terms of the number of discovered execution paths with binary formats; for highly-redundant text-based formats such as HTML or XML, syntax-aware strategies (template- or ABNF-based) will obviously yield better results. Plugging them into AFL would not be hard, but requires work.