Optimizing Mayhem Targets

Fuzzing or fuzz testing is an automated application testing technique that feeds randomized input (called test cases) into a program to try and break the program and identify potential vulnerabilities. Fuzzers, such as the ones in Mayhem's analysis suite, will continually re-run a program with varying test cases to observe unique changes in the behavior of the program and attempt to cover as much of the underlying code as possible.

Therefore, the efficiency of fuzzers are dependent on two main components: both the execution speed of the program as well as the effectiveness to which the fuzzer can quickly cover new pathways within the underlying code.

Fast Execution Speed

Fuzzers can re-run a program thousands of times (if not more) while simultaneously mutating its inputs each time to discover new program behavior and underlying code paths. However, if a program takes too long to execute, this can greatly diminish the time (and overall efficiency) it takes for the fuzzer to test the program and discover new code pathways.

Therefore, in order to increase the execution speed of the underlying program for a fuzz target, the underlying program should be modified to remove any extraneous operations that can cause delays in the execution of the program itself, such as sleep or wait functions or disk/network IO that delay and block subsequent parts of the program from executing until such operations are complete. Even better, test drivers can be created to more directly focus on a particular area of code within a program, thereby minimizing extraneous operations and increasing the execution speed and rate of new code coverage for the fuzz target.

Tip

Check out Diagnosing Low Test Run Rates for more information on increasing execution speed for a fuzz target.

Effective Code Coverage

In order to maximize the effectiveness of code coverage for a fuzz target, programs should not only be quick to execute (as faster programs lead to faster testing and therefore a quicker rate of code coverage), but also utilize seeded test cases as well as small test cases. This is called seeding a test suite and test case minimization, respectively.

Seeding a Test Suite

If possible, it's always beneficial to provide your fuzz target a starting point by creating an initial set of test cases called a seed test suite. If a seed test suite is not provided, the fuzzing engine has to guess inputs from scratch, which can take time depending on the size of the inputs and the complexity of the target. In many cases, providing a seed test suite can substantially increase code coverage by an order of magnitude.

Tip

Check out the tutorial contained within Packaging and Testing a Non-Docker Target for more information on seeding a test suite.

Test Suite Minimization

When seeding a test suite, it's also important to think about how effective initial test cases will be in inducing the largest amount of net code coverage for the target application. For example, for a starting test suite there may be similar test cases that when compared to each other provide minimal net code coverage for the underlying target application.

Therefore, rather than having a large volume of similar test cases, which will require Mayhem to re-run the target for each test case, Mayhem will by default undergo a test suite minimization task to analyze the code coverage for each initial test case and use a "minset" algorithm to determine the test cases that provide the most “bang for our buck”—in other words Mayhem will minimize a starting test suite down to the test cases that provide the largest net code coverage for the target application.

Let's see what this means using a basic technical example:

#include <stdio.h>
#include <string.h>

int testme(char *buf, unsigned len);

int main(int argc, char *argv[])
{
  FILE *f;
  char buf[12];

  if(argc != 2){
    fprintf(stderr, "Must supply a text file\n");
    return -1;
  }
  f = fopen(argv[1], "r");
  if(f == NULL){
    fprintf(stderr, "Could not open %s\n", argv[1]);
    return -1;
  }
  if(fgets(buf, sizeof(buf), f) == NULL){
    fprintf(stderr, "Could not read from %s\n", argv[1]);
    return -1;
  }
  testme(buf, strlen(buf));
  return 0;
}

int testme(char *buf, unsigned len)
{
  unsigned ok;

  if(!ok) // Defect: uninitialized use of ok.
    ok = len;

  if(buf[0] == 'b')
    if(buf[1] == 'u')
      if(buf[2] == 'g') {
        return 1/0;      // Defect: divide-by-zero.
      }
  return 0;
}

You may already be familiar with the above testme application that is used within our tutorials.

To recap, Mayhem will attempt to fuzz the testme target and provide a test case of "bug" to hit the divide-by-zero defect. Now imagine that a starting test suite were supplied for the testme target that had test cases ranging from "a" to "z". Clearly, only test cases starting with "b" would begin to cover the parts of the testme application. Therefore, rather than re-running the testme application for all test cases (of which some of them would provide no additional net code coverage value), it would be wise to limit the test cases used during the Mayhem run to only those starting with the letter "b" to optimize our runs.

Test Case Minimization

As a fuzzer continues to re-run a program and provide mutated test cases as input, test cases tend to grow in both size and complexity. This leads to higher execution times and makes it more difficult to find test cases that result in unique code coverage. For example, attempting to mutate a 4096-byte testcase by a single bit will take longer and result in less of a code coverage change than mutating a 1-byte testcase by a single bit.

In addition, test cases should be kept small when mutating and adding more bytes to an already-giant testcase provides no additional value. For example, a program that parses GET HTTP/1.1 will only ever parse 12 bytes, and therefore generating a 4,000-byte testcase will be treated the same as a 12-byte testcase. As a result, generating such a large testcase would be unnecessary and would ultimately decrease the fuzzing efficiency for the target.

Info

For this reason we've included a max_length feature to put a limit on the size of test cases that Mayhem will generate. Check it out in the Mayhemfile Specification documentation!

Summary

The efficiency of fuzzers are dependent on two main components: both the execution speed of the program as well as the effectiveness to which the fuzzer can quickly cover new pathways within the underlying code.

Understanding how to optimize your fuzz targets in Mayhem will help you save time and increase the amount of code coverage for your underlying program.