Dr. Memory |

Dr. Fuzz: Dynamic Fuzz Testing Extension

The Dr. Fuzz DynamoRIO Extension provides fuzz testing features. Dr. Fuzz is part of the Dr. Memory Framework. Dr. Fuzz is used to implement the Dr. Memory Fuzz Testing Mode . The documentation is divided into the following sections:

- Setup
- Dr. Fuzz API
- Dr. Fuzz Mutators Mutators

# Setup

To use `Dr`. Fuzz with your client, first locate the Dr. Memory Framework. Then use the standard method of using an Extension with the name `drfuzz`. The two steps will look like this in your client's `CMakeLists.txt` file:

find_package(DrMemoryFramework)
use_DynamoRIO_extension(clientname drfuzz)

To point CMake at the framework, set the DrMemoryFramework_DIR variable to point at the `drmf` subdirectory of the Dr. Memory package that you are using. For example:

cmake -G"Ninja" -DDynamoRIO_DIR=c:/path/to/DynamoRIO-Windows-4.1.0-8/cmake -DDrMemoryFramework_DIR=c:/path/to/DrMemory-Windows-1.6.0-2/drmf ../mysrcs/

That will automatically set up the include path and library dependence.

Your client must call `drfuzz_init()` prior to accessing any API routines in `drfuzz`, and should call `drfuzz_exit()` at process exit time.

# Dr. Fuzz API

`Dr`. Fuzz provides the following key features:

1. Repeat execution of the test target function with fuzzed arguments.
2. Mutate argument values using bit flipping, random number algorithms, or custom user-provided mutators.
3. Schedule fuzz iterations for a target function and set of arguments.
4. Report state information on a crash caused by fuzz inputs.

The client can use the provided Dr. Fuzz APIs to fuzz test the target application. The most flexible approach is to use Dr. Fuzz directly to control the fuzzing cycle using registered callbacks. This approach also requires the most effort, so users who wish to get going quickly may prefer to use Dr. Memory's fuzzing features, which leverage Dr. Fuzz.

# Dr. Fuzz Mutators

To support custom mutators, mutation is performed by a libary separate from the main `Dr`. Fuzz control library. `Dr`. Fuzz provides a default mutator library which contains several different mutator implementations.

## Default Mutator Options

The default mutator built-in to `Dr`. Fuzz supports several mutation variations, controlled by the following options (which are passed to drfuzz_mutator_start()):

- -alg <algorithm_name>
  Specifies the algorithm for generating a new value. The choices are:
  - "random": Randomly search the domain of possible permutations. This is the default for -unit token.
  - "ordered": Exhaustively search all possible permutations in an ordered manner. This is the default for -unit bits and -unit num.
- -unit <unit_name>
  Specifies the unit of transformation for applying the mutation algorithm. The choices are:
  - "bits": Bitwise application of the mutation algorithm. This is the default.
  - "num": Numeric application of the mutation algorithm.
  - "token": Insertion of tokens from a dictionary. The dictionary must be specified via -dictionary.
- -flags <int>
  Flags for the mutator. Some flags are specific to a particular algorithm and/or mutation unit. The choices are:
  - 0x1: Reset the buffer contents to the input_seed after every bit-flip mutation. Not valid for -unit num. On by default.
  - 0x2: Seed the mutator's random number generator with the current clock time.
- -sparsity <int>
  The degree of sparseness in the random coverage of the "random" algorithm with unit "bits" (invalid for other configurations). Sparsity of n will yield on average 1/n total values relative to the "ordered" algorithm in the same configuration. If the sparsity is set to 0, the default value of 1 will be used instead.
- -max_value <uint64>
  For buffers of size 8 bytes or smaller, specifies the maximum mutation value. Use value 0 to disable the maximum value (i.e., limit only by the buffer capacity).
- -random_seed <uint64>
  Set the randomization seed for algorithm "random". The default random seed is 0x5a8390e9a31dc65fULL, which was selected to have an equal number of 0 and 1 bits.
- -dictionary <path>
  Specifies a dictionary file containing tokens for -unit token. The file format is compatible with AFL (http://lcamtuf.coredump.cx/afl/). It is a text file with one token, in double quotes, per line, with an optional preceding name followed by an equals sign. Non-printable characters must use \x hex escapes, and double quotes and backslashes must be escaped by a preceding backslash. Comment lines starting with '#' can be included. An example:
  "token42"
  "different_token"
  unprint="\xCD\xEF"
  mytokA="internal\"quotes\""

The default options are for ordered, seed-centric bit-flipping.

The algorithms are further described below.

## Mutator Algorithms and Units

The default mutator provides two algorithms for mutating the fuzzed argument, ordered and random, and each algorithm can operate in terms of bit-flips or integers. The latter option is referred to as the "unit" of mutation. The behavior of these two mutator options can be easily seen in the following example, where the app's original argument value is all zero (at left), and each successive value reflects one mutation:

    Ordered bit-flip: 0x00000000 => 0x00000001 => 0x00000100 => 0x00010000 => 0x01000000
    Random bit-flip:  0x00000000 => 0x00200000 => 0x00008000 => 0x00000004 => 0x00002000
    Ordered numeric:  0x00000000 => 0x00000001 => 0x00000002 => 0x00000003 => 0x00000004
    Random numeric:   0x00000000 => 0x7abcbb5e => 0xc6f15f41 => 0xaebd59a2 => 0xc375f0ae

Notice that the bit-flip unit does not flip bits in a lexical sequence, even when the ordered algorithm is selected. Instead, it distributes the flips across the bytes first, and secondarily across the bits of each byte. The goal is to improve mutator coverage for very large input buffers, especially when the sparsity option is used (see below). The following sequence illustrates how ordered bit-flip distributes all permutations of a single flip across a 2-byte buffer:

    0x0000 => 0x0001 => 0x0100 => 0x0002 => 0x0200 => 0x0004 => 0x0400 => 0x0008 => 0x0800
           => 0x0010 => 0x1000 => 0x0020 => 0x0200 => 0x0040 => 0x4000 => 0x0080 => 0x8000

After completing all flips of a single bit, the mutator will proceed to flip two bits:

    0x0000 => 0x0101 => 0x0003 => 0x0201 => 0x0005 => 0x0401 => 0x0009 => 0x0801 => 0x0011
           => 0x1001 => 0x0021 => 0x2001 => 0x0041 => 0x4001 => 0x0081 => 0x8001 => 0x0006

## Mutator Random Number Generator

The mutator uses a stateless xorshift algorithm for all of its randomized decisions (see xorshift64star on https://en.wikipedia.org/wiki/Xorshift). For randomized bit-flip, the mutator selects which bits to flip using the Fisher-Yates shuffle (https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle).

To repeat a fuzz test using the exact same sequence of values for the fuzz target function, specify the same random seed as the original fuzz test using the mutator descriptor's optional last field; for example:

    -fuzz_mutator "r|b|r|1|0x17a3cd8648a6ab1f"

To avoid repeating the exact same fuzz test when using the random algorithm, and pass flag `'t'` in the mutator descriptor (field 3 in option `-fuzz_mutator`) to seed the random algorithm with the system clock time. The seed will be reported in the log and in the console output (when enabled) for future reference, e.g., to repeat that fuzz test.

## Mutator "Proximity" via Reset Option

Although the fuzzer executes the target function as rapidly as possible on the given hardware (by redirecting execution directly from the function return back into the function entry point), the number of possible values for the fuzzed argument usually makes it impossible to try all permutations. In many scenarios, the most interesting app functionality can be reached using argument values that are very similar to a "correct" or "typical" input value. For this reason, the fuzzer takes the original argument value passed by the application as a starting point for mutation. To explore input values that are most similar to the app's original input value, use flag `'r'` in the mutator descriptor (field 3 in option `-fuzz_mutator`) to reset the argument to the app's original value before each mutation. Omitting this flag will cause the successive mutations to accumulate. For example, a bit-flipping mutator using the reset option might generate the following sequence on a 4-byte buffer, where the first value is the app's original argument value, and each successive value reflects one mutation (marked with overstrike):

                          __          __          __          __
    0x01020304 => 0x01020305 => 0x01020204 => 0x01030304 => 0x00020304

But the same mutator without the reset option would generate this sequence:

                          __          ____        ______      ________
    0x01020304 => 0x01020305 => 0x01020205 => 0x01030205 => 0x00030205

As you can see, the mutated value remains very similar to the original input when using the reset option, but quickly diverges without it.

## Mutator Sparsity

For many target functions, the reset option generates inputs that are too similar, causing the majority of inputs to be redundant–yet completely random input may also be ineffective. To generate a moderately diverse range of input values, the sparsity can be specified in the mutator descriptor (field 4 in option `-fuzz_mutator`). The term "sparsity" refers to the coverage of the space of possible input values, where a sparsity of 1 indicates to first cover all values reachable by a single bit-flip of the app's original argument value, then cover all values reachable by 2 bit-flips, and so on. By increasing the sparsity, the mutator will reduce the number of permutations it generates at each degree of bit flipping. The following table provides an example of sparsity one, given a 4-byte input buffer:

    Bit-Flip Degree   Total Mutator Values
                  1                     32
                  2                    992
                  3                  29760

By increasing the sparsity to just 4, the number of mutator values at each degree of bit flipping is greatly reduced:

    Bit-Flip Degree   Total Mutator Values
                  1                      8
                  2                    248
                  3                   7440

This second approach balances the diversity of input values with the proximity of each generated input to the app's original argument value.