Fuzzing

Fuzzing is an anomaly-triggering attempt on an application by providing it with random, often invalid data. The idea is to force the application to crash through unexpected inputs in order to detect potential memory leaks and other hard-to-find bugs in the application. Fuzzing is tangential to traditional software functional testing in that it deliberately focuses on the failing cases of the software, the root-cause analysis of which greatly enhances the robustness of the software. In this post, let’s pickle-taste the principles and general concepts of fuzzing before we can chew the deeper aspects of it in the coming weeks.

What to Fuzz? — The Inputs

fuzzing-inputs-of-a-program

The fuzzing vectors of a program are nothing but its input vectors. The input to a program can be from,

  1. Console: User interacting with the program through a terminal window
  2. File: Program reading the file containing arguments, settings and other inputs
  3. Network: Program making use of a well-defined network protocol
  4. API: Several ready-made libraries utilized by the program
  5. Devices: Data coming from I/O and sensors

All these possible data input paths to an application can be fuzzed independently or in combination to stress-test the application’s input validating, bounds checking, and self-defending capability.

Types of Fuzzers

A fuzzer can be categorized as follows:

  1. A fuzzer can be generation-based or mutation-based depending on whether inputs are generated from scratch or by modifying existing inputs,
  2. A fuzzer can be dumb or smart depending on whether it is aware of input structure, and
  3. A fuzzer can be white, grey, or blackbox depending on whether it is aware of program structure.

Reuse of existing input seeds

A mutation-based fuzzer leverages an existing corpus of seed inputs during fuzzing. It generates inputs by modifying (or rather mutating) the provided seeds. For example, when fuzzing the image library libpng, the user would provide a set of valid PNG image files as seeds while a mutation-based fuzzer would modify these seeds to produce semi-valid variants of each seed. The corpus of seed files may contain thousands of potentially similar inputs. Automated seed selection (or test suite reduction) allows to pick the best seeds in order to maximize the total number of bugs found during a fuzz campaign.

A generation-based fuzzer generates inputs from scratch. For instance, a smart generation-based fuzzer takes the input model that was provided by the user to generate new inputs. Unlike mutation-based fuzzers, a generation-based fuzzer does not depend on the existence or quality of a corpus of seed inputs.

Some fuzzers have the capability to do both, to generate inputs from scratch and to generate inputs by mutation of existing seeds.

Aware of input structure

Typically, fuzzers are used to generate inputs for programs that take structured inputs, such as a file, a sequence of keyboard or mouse events, or a sequence of messages. This structure distinguishes valid input that is accepted and processed by the program from invalid input that is quickly rejected by the program. What constitutes a valid input may be explicitly specified in an input model. Examples of input models are formal grammars, file formats, GUI-models, and network protocols. Even items not normally considered as input can be fuzzed, such as the contents of databases, shared memory, environment variables or the precise interleaving of threads. An effective fuzzer generates semi-valid inputs that are “valid enough” so that they are not directly rejected from the parser and “invalid enough” so that they might stress corner cases and exercise interesting program behaviours.

A smart (model-based, grammar-based, or protocol-based) fuzzer leverages the input model to generate a greater proportion of valid inputs. For instance, if the input can be modelled as abstract syntax tree, then a smart mutation-based fuzzer would employ random transformations to move complete subtrees from one node to another. If the input can be modelled by a formal grammar, a smart generation-based fuzzer would instantiate the production rules to generate inputs that are valid w.r.t. the grammar. However, generally the input model must be explicitly provided which is difficult when it is proprietary, unknown, or very complex. If a large corpus of valid and invalid inputs are available, a grammar induction technique, such as Angluin‘s L* algorithm would be able to generate an input model.

A dumb fuzzer does not require the input model and can thus be employed to fuzz a wider variety of programs. For instance, AFL is a dumb mutation-based fuzzer that modifies a seed file by flipping random bits, by substituting random bytes with “interesting” values, and by moving or deleting blocks of data. However, a dumb fuzzer might generate a lower proportion of valid inputs and stress the parser code rather than the main components of a program. The disadvantage of dumb fuzzers can be illustrated by means of the construction of a valid checksum for a cyclic redundancy check (CRC). A CRC is an is an error-detecting code that ensures that the integrity of the data contained in the input file is preserved during transmission. A checksum is computed over the input data and recorded in the file. When the program processes the received file and the recorded checksum does not match the re-computed checksum, then the file is rejected as invalid. Now, a fuzzer that is unaware of the CRC is unlikely to generate the correct checksum. However, there are attempts to identify and re-compute a potential checksum in the mutated input, once a dumb mutation-based fuzzer has modified the protected data.

Aware of program structure

Typically, a fuzzer is considered more effective if it achieves a higher degree of code coverage. The rationale is, if a fuzzer does not exercise certain structural elements in the program, then it is also not able to reveal bugs that are hiding in these elements. Some program elements are considered more critical than others. For instance, a division operator might cause a division by zero error, or a system call may crash the program.

A blackbox fuzzer treats the program as a black box and is unaware of internal program structure. For instance, a random testing tool that generates inputs at random is considered a blackbox fuzzer. Hence, a blackbox fuzzer can execute several hundred inputs per second, can be easily parallelized, and can scale to programs of arbitrary size. However, blackbox fuzzers may only scratch the surface and expose “shallow” bugs. Hence, there are attempts to develop blackbox fuzzers that can incrementally learn about the internal structure (and behavior) of a program during fuzzing by observing the program’s output given an input. For instance, LearnLib employs active learning to generate an automaton that represents the behavior of a web application.

A whitebox fuzzer leverages program analysis to systematically increase code coverage or to reach certain critical program locations. For instance, SAGE leverages symbolic execution to systematically explore different paths in the program. If the program’s specification is available, a whitebox fuzzer might leverage techniques from model-based testing to generate inputs and check the program outputs against the program specification. A whitebox fuzzer can be very effective at exposing bugs that hide deep in the program. However, the time used for analysis (of the program or its specification) can become prohibitive. If the whitebox fuzzer takes relatively too long to generate an input, a blackbox fuzzer will be more efficient. Hence, there are attempts to combine the efficiency of blackbox fuzzers and the effectiveness of whitebox fuzzers.

A greybox fuzzer leverages instrumentation rather than program analysis to glean information about the program. For instance, AFL and libFuzzer utilize lightweight instrumentation to trace basic block transitions exercised by an input. This leads to a reasonable performance overhead but informs the fuzzer about the increase in code coverage during fuzzing, which makes greybox fuzzers extremely efficient vulnerability detection tools.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s