Fuzz testing

"Fuzzing" redirects here. For other uses, see Fuzz (disambiguation).

Fuzz testing or fuzzing is a software testing technique, often automated or semi-automated, that involves providing invalid, unexpected, or random data to the inputs of a computer program. The program is then monitored for exceptions such as crashes, or failing built-in code assertions or for finding potential memory leaks. Fuzzing is commonly used to test for security problems in software or computer systems. It is a form of random testing which has been used for testing hardware or software.

The field of fuzzing originated with Barton Miller at the University of Wisconsin in 1988. This early work includes not only the use of random unstructured testing, but also a systematic set of tools to evaluate a wide variety of software utilities on a variety of platforms, along with a systematic analysis of the kinds of errors that were exposed by this kind of testing. In addition, they provided public access to their tool source code, test procedures and raw result data.

There are two forms of fuzzing program, mutation-based and generation-based, which can be employed as white-, grey-, or black-box testing. File formats and network protocols are the most common targets of testing, but any type of program input can be fuzzed. Interesting inputs include environment variables, keyboard and mouse events, and sequences of API calls. Even items not normally considered "input" can be fuzzed, such as the contents of databases, shared memory, or the precise interleaving of threads.

For the purpose of security, input that crosses a trust boundary is often the most interesting. For example, it is more important to fuzz code that handles the upload of a file by any user than it is to fuzz the code that parses a configuration file that is accessible only to a privileged user.

History

The term "fuzz" or "fuzzing" originates from a 1988 class project, taught by Barton Miller at the University of Wisconsin. The project developed a basic command-line fuzzer to test the reliability of Unix programs by bombarding them with random data until they crashed. The test was repeated in 1995, expanded to include testing of GUI-based tools (such as the X Window System), network protocols, and system library APIs. Follow-on work included testing command- and GUI-based applications on both Windows and Mac OS X.

One of the earliest examples of fuzzing dates from before 1983. "The Monkey" was a Macintosh application developed by Steve Capps prior to 1983. It used journaling hooks to feed random events into Mac programs, and was used to test for bugs in MacPaint.

Another early fuzz testing tool was crashme, first released in 1991, which was intended to test the robustness of Unix and Unix-like operating systems by executing random machine instructions.

Uses

Fuzz testing is often employed as a black-box testing methodology in large software projects where a budget exists to develop test tools. Fuzz testing offers a cost benefit for many programs.

The technique can only provide a random sample of the system's behavior, and in many cases passing a fuzz test may only demonstrate that a piece of software can handle exceptions without crashing, rather than behaving correctly. This means fuzz testing is an assurance of overall quality, rather than a bug-finding tool, and not a substitute for exhaustive testing or formal methods.

As a gross measurement of reliability, fuzzing can suggest which parts of a program should get special attention, in the form of a code audit, application of static code analysis, or partial rewrites.

Types of bugs

As well as testing for outright crashes, fuzz testing is used to find bugs such as assertion failures and memory leaks (when coupled with a memory debugger). The methodology is useful against large applications, where any bug affecting memory safety is likely to be a severe vulnerability.

Since fuzzing often generates invalid input it is used for testing error-handling routines, which are important for software that does not control its input. Simple fuzzing can be thought of as a way to automate negative testing.

Fuzzing can also find some types of "correctness" bugs. For example, it can be used to find incorrect-serialization bugs by complaining whenever a program's serializer emits something that the same program's parser rejects. It can also find unintentional differences between two versions of a program or between two implementations of the same specification.

Techniques

Fuzzing programs fall into two different categories. Mutation-based fuzzers mutate existing data samples to create test data while generation-based fuzzers define new test data based on models of the input.

The simplest form of fuzzing technique is sending a stream of random bits to software, either as command line options, randomly mutated protocol packets, or as events. This technique of random inputs continues to be a powerful tool to find bugs in command-line applications, network protocols, and GUI-based applications and services. Another common technique that is easy to implement is mutating existing input (e.g. files from a test suite) by flipping bits at random or moving blocks of the file around. However, the most successful fuzzers have detailed understanding of the format or protocol being tested.

The understanding can be based on a specification. A specification-based fuzzer involves writing the entire array of specifications into the tool, and then using model-based test generation techniques in walking through the specifications and adding anomalies in the data contents, structures, messages, and sequences. This "smart fuzzing" technique is also known as robustness testing, syntax testing, grammar testing, and (input) fault injection. The protocol awareness can also be created heuristically from examples using a tool such as Sequitur. These fuzzers can generate test cases from scratch, or they can mutate examples from test suites or real life. They can concentrate on valid or invalid input, with mostly-valid input tending to trigger the "deepest" error cases.

There are two limitations of protocol-based fuzzing based on protocol implementations of published specifications: 1) Testing cannot proceed until the specification is relatively mature, since a specification is a prerequisite for writing such a fuzzer; and 2) Many useful protocols are proprietary, or involve proprietary extensions to published protocols. If fuzzing is based only on published specifications, test coverage for new or proprietary protocols will be limited or nonexistent.

Fuzz testing can be combined with other testing techniques. White-box fuzzing uses symbolic execution and constraint solving. Evolutionary fuzzing leverages feedback from an heuristic (E.g., code coverage in grey-box harnessing, or a modeled attacker behavior in black-box) effectively automating the approach of exploratory testing.

Reproduction and isolation

Test case reduction is the process of extracting minimal test cases from an initial test case. Test case reduction may be done manually, or using software tools, and usually involves a divide-and-conquer algorithm, wherein parts of the test are removed one by one until only the essential core of the test case remains.

So as to be able to reproduce errors, fuzzing software will often record the input data it produces, usually before applying it to the software. If the computer crashes outright, the test data is preserved. If the fuzz stream is pseudo-random number-generated, the seed value can be stored to reproduce the fuzz attempt. Once a bug is found, some fuzzing software will help to build a test case, which is used for debugging, using test case reduction tools such as Delta or Lithium.

Advantages and disadvantages

The main problem with fuzzing to find program faults is that it generally only finds very simple faults. The computational complexity of the software testing problem is of exponential order ($O(c^n)$, $c>1$) and every fuzzer takes shortcuts to find something interesting in a timeframe that a human cares about. A primitive fuzzer may have poor code coverage; for example, if the input includes a checksum which is not properly updated to match other random changes, only the checksum validation code will be verified. Code coverage tools are often used to estimate how "well" a fuzzer works, but these are only guidelines to fuzzer quality. Every fuzzer can be expected to find a different set of bugs.

On the other hand, bugs found using fuzz testing are sometimes severe, exploitable bugs that could be used by a real attacker. Discoveries have become more common as fuzz testing has become more widely known, as the same techniques and tools are now used by attackers to exploit deployed software. This is a major advantage over binary or source auditing, or even fuzzing's close cousin, fault injection, which often relies on artificial fault conditions that are difficult or impossible to exploit.

The randomness of inputs used in fuzzing is often seen as a disadvantage, as catching a boundary value condition with random inputs is highly unlikely but today most of the fuzzers solve this problem by using deterministic algorithms based on user inputs.

Fuzz testing enhances software security and software safety because it often finds odd oversights and defects which human testers would fail to find, and even careful human test designers would fail to create tests for.

See also

• Boundary value analysis

Further reading

• Ari Takanen, Jared D. DeMott, Charles Miller, Fuzzing for Software Security Testing and Quality Assurance, 2008, ISBN 978-1-59693-214-2
• Michael Sutton, Adam Greene, and Pedram Amini. Fuzzing: Brute Force Vulnerability Discovery, 2007, ISBN 0-32-144611-9.
• H. Pohl, Cost-Effective Identification of Zero-Day Vulnerabilities with the Aid of Threat Modeling and Fuzzing, 2011
• Fabien Duchene, Detection of Web Vulnerabilities via Model Inference assisted Evolutionary Fuzzing, 2014, PhD Thesis
• Bratus, S., Darley, T., Locasto, M., Patterson, M.L., Shapiro, R.B., Shubina, A., Beyond Planted Bugs in "Trusting Trust": The Input-Processing Frontier, IEEE Security & Privacy Vol 12, Issue 1, (Jan-Feb 2014), pp. 83-87 -- Basically highlights why fuzzing works so well: because the input is the controlling program of the interpreter.

External links

• University of Wisconsin Fuzz Testing (the original fuzz project) Source of papers and fuzz software.
• Look out! It's the Fuzz! (IATAC IAnewsletter 10-1)
• Designing Inputs That Make Software Fail, conference video including fuzzy testing
• Link to the Oulu (Finland) University Secure Programming Group
• Building 'Protocol Aware' Fuzzing Frameworks
• Video training series about Fuzzing, Fuzz testing, and unknown vulnerability management