Fuzzing: Common Tools and Techniques

June 04, 2019, Andy Bowden, Consultant, Coalfire Labs

What Is It?

Fuzzing is a software testing methodology that can be used from either a black or white box perspective and predominantly consists of providing deliberately malformed inputs to an application to identify errors such as unhandled exceptions, memory spikes, thread hangs, read access violations or buffer overruns that could lead to further compromise of a system.

Fuzzing relies on the assumptions that all software has bugs just waiting to be found. Hence, given enough time, a methodical approach should find these previously unknown bugs. Fuzzing can provide an additional avenue for bug identification alongside common testing techniques due to its mechanical approach and the limited amount of effort needed to carry it out.

Terminology

Before we get started, below are some common terms we will be using throughout this article:

Term Definition
Dumb Fuzzing Input of malformed data with zero knowledge of the underlying data structure.
Smart Fuzzing Input of malformed data with knowledge of the underlying data structure.
Black Box Fuzzing Input of malformed data without monitoring which code paths the data is passed through.
White Box Fuzzing Input of malformed packets with full knowledge of which code paths are hit.
Generation The creation of completely random data for inputting into the fuzz target.
Mutation Corruption of valid data according to a pattern.
Mutation Template Template used to define the pattern for corrupting valid data.
Code Coverage Represents the amount of code paths covered during testing.
 

Which Targets Are Suitable for Fuzzing?

Fuzzing has historically been used against software developed in either C or C++, which leave memory management to the programmer. However, it can be useful for any software that processes input received across a trust boundary. Some common trust boundaries include:

  • Files received from an untrusted source
  • XML blobs
  • User-supplied input
  • Network sockets
  • Shared memory
  • Pipes
  • RPC interfaces
  • Driver IOCTLs
  • ActiveX objects

The Advantages and Disadvantages

Fuzzing is a testing technique like any other; it is not perfect and should be used as part of a robust testing strategy. As such, a list of some of the advantages and disadvantages of fuzzing are listed here:

Advantages:

  • Very simple to design
  • Can find problems not easily visible through other testing techniques
  • Usually very inexpensive to implement

Disadvantages:

  • Often takes an extremely long time to run
  • Crashes can often be difficult to analyze, especially when using black box fuzzing
  • Mutation templates for applications with complex inputs can often be time consuming to produce

The Process of Fuzzing

Once you have selected your fuzzing target, you will then have to decide how you would like to generate your data to use. You can either generate a selection of random data (dumb fuzzing) for use against the target or you can use a mutation of a set of valid inputs (smart fuzzing).

Should you decide to utilize smart fuzzing, the next step will be to create a set of inputs to be used against the target. This can be broken down into two phases:

  • Generation of a valid mutation template
  • Mutation of the template to produce fuzzed data

The valid inputs can be gained through a number of methods, such as monitoring the software during normal usage or through reviewing the source code of the software.

Generation or Mutation

For complex inputs, full code coverage is almost impossible in any sort of sensible time frame using only random input generation. This is due to the fact that it takes the fuzzer excessive time to generate inputs that are both sufficiently complex to avoid being caught by the target’s input filtering while still exposing potential security vulnerabilities.

However, should the target software be simple enough that fuzzing with randomly generated data is achievable in the allotted time frame, then this is the simpler method requiring less time to implement.

Should your target require complex input, a far more efficient method for creating well-formed fuzzing data is to use known good data and a mutation template.

Imagine we had a web server that required four special HTTP headers (in this case, we will call them header1, header2, etc.), and if we were to omit header3 but include all the others, the program would crash.

To find such a flaw, an HTTP request that contains all three headers – header1, header2, and header4, and without header3 – should be attempted.

If our fuzzing engine is able to add or delete random headers from the request, it will take a long time (if it is at all possible) to generate an HTTP request that has exactly those four headers present. However, if we provide a template buffer with all possible HTTP headers present, the fuzzer will very quickly create the bogus request with all the headers, but without header3 present.

Types of Fuzzer

Fuzzers generally fall into one of the following categories: generation, mutation, or evolution, based on how they create the data with which to fuzz the target piece of software. In the following section we will briefly go over each of these categories.

Generation

Generation fuzzers can be anything from completely random data to slightly designed data. Imagine fuzzing an HTTP server (such as described above) but completely fuzzing the whole packet. Most of what would be fuzzed would be the TCP/IP data, and the packet would never reach its destination.

Generation fuzzers usually take a valid input, break it into pieces, and then fuzz each of the selected pieces randomly. The idea is to keep the overall structure of the data but to fuzz selected parts of it.

Mutation

Mutation-based fuzzers take a set of valid inputs and perform mutations on them in order to elicit errors from the software missed in other types of testing. Techniques such as least significant bit flipping fall into mutation fuzzing. Another example includes when fuzzing an HTTP request – if directed to do so, a mutation fuzzer could append random values to each of the HTTP header values in search of a vulnerability. For many targets, this can be a surprisingly effective strategy due to the fact that inputs are often similar enough to the original valid inputs to achieve a good amount of code coverage. 

A mutation-based fuzzer can be further improved by using templates to ensure the structure of the data supplied to the target meets the format of the target’s expectations. Things like ensuring file inputs are in the correct format or that HTTP requests contain the correct headers could be added to the parsing of inputs from the mutation fuzzer to reduce time spent fuzzing.

As previously stated, a mutation-based fuzzer leverages a selection of known good inputs to generate a set of modified inputs to be used when fuzzing. For example, when fuzzing an mp3 processing library, the user would provide a selection of valid mp3 files, and then the fuzzer would modify these files to produce semi-valid variants of each file.

Evolution

Evolutionary fuzzing is based on the use of genetic programming, which aims to converge toward the discovery of vulnerabilities. Genetic algorithms are used to create continuous sets of test cases. Test case generation is based on both the fuzzing framework designed by the user and the responses received from the fuzzing target. The first set of test cases will be generated in a similar way to a generational fuzzer (described previously), and all further test cases will be generated through the steps described below:

  1. Score: Each member of the current set of test cases is given a score, which is a combination of multiple metrics defined by the user and monitored through the fuzzing test
  2. Removal of weak cases: Lowest scoring test cases are discarded
  3. Mutation: Minor changes are applied to each remaining test case, similar to those described in the mutation fuzzing section
  4. Combination: Involves combining test cases with high scores to generate test cases that find other optimums. This process is also used to replenish the test cases that were discarded in step 2

Fuzzing Engine

There are many prebuilt fuzzing packages available that can be leveraged against a target, some of which are quite simple and require minimal setup time, while others offer a range of features and require quite complex setup. It is also possible to design a custom fuzzing engine for a specific project.

A good fuzzing engine should implement the following features:

  • Parse the mutation template and input data, then assemble it into a data structure
  • Randomly select one of the attributes and modify it in line with the mutation template specification
  • Submit the fuzzed input back to the target

It is possible to use some of the below features to assist with finding bugs while fuzzing.

Using Heap Canaries to Assist with Memory Corruption

Often, fuzzing will cause slight memory error. For example, an IndexOutOfBounds exception that for the most part will not cause an application to crash can in some cases lead to things like remote code execution.

On the Windows operating system, it is possible to use features such as heap canaries or similar utilities to assist with detecting memory corruption.

Generating Test Cases

When generating test cases, something will need to be transformed in one form or another regardless of whether the fuzzing is generation, mutation, or evolution based. It is worth noting that edge cases are often where interesting things happen, and as such, it is advised to consider including:

  • Exceedingly long strings
  • String format characters
  • Negative values
  • Null characters
  • New lines
  • EOL characters
  • Maximum and minimum integer values

Reproducing a Crash

When carrying out fuzzing, the demanding nature of the task can itself cause errors in a target. As such, all bugs should be reproduced for verification purposes. It is advisable to attach a debugger to the process or set up a Just-In-Time (JIT) debugger so that a dump of the crash can be analyzed and allow identification of how the target failed and what caused the failure.

A second method that will work reliably for crashes that are caused by fuzzing a single request at a time is to log either the manipulated data in a database or similar product so that it can be referred to at a later date.

Common Fuzzers

Conclusion

While finding bugs in a timely manner can require a large time investment to correctly set up a suitable fuzzing framework for the task, integrating fuzzing into the software testing suite can help avoid costly vulnerabilities being discovered by malicious actors in the future. Fuzzing is a useful software testing technique that can be leveraged with (depending on framework complexity) little time invested, across multiple types of software, and can be very effective at finding vulnerabilities missed by techniques like code reviews.

Andy Bowden

Author

Andy Bowden — Consultant, Coalfire Labs

Recent Posts

Post Topics

Archives

Top