|
No edit summary
|
Making History more coherent.
Tag: references removed
|
||
| Line 7: | Line 7: | ||
==History== |
==History== |
||
|
The random generation of program inputs dates back to the 1950's when data was still stored on [[Computer_programming_in_the_punched_card_era|punched cards]].<ref name="weinberg" /> Programmers would use punched cards pulled from the trash or card decks of random numbers as input to computer programs. Random input generation is sometimes described as Monkey Testing originating from a tool called "The Monkey" that was developed in 1983 to test Mac programs, such as [[MacPaint]].<ref name="AutoDO-3" /> The figurative "monkey" refers to the [[infinite monkey theorem]] which states that a monkey hitting keys at random on a typewriter keyboard for an infinite amount of time will eventually type out the entire works of [[William Shakespeare|Shakespeare]]. In the case of testing, the monkey would write the particular sequence of inputs that will trigger a crash. |
||
The term "fuzz" or "fuzzing" originates from a 1988 class project, taught by Barton Miller at the University of Wisconsin.<ref name="AutoDO-1" /><ref name="AutoDO-2" /> The project developed a basic command-line fuzzer to test the reliability of [[Unix]] programs by bombarding them with random data until they crashed. 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. |
The term "fuzz" or "fuzzing" originates from a 1988 class project, taught by Barton Miller at the University of Wisconsin.<ref name="AutoDO-1" /><ref name="AutoDO-2" /> The project developed a basic command-line fuzzer to test the reliability of [[Unix]] programs by bombarding them with random data until they crashed. 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. |
||
| ⚫ | In 1991, the crashme tool was released, which was intended to test the robustness of Unix and [[Unix-like]] operating systems by executing random machine instructions.<ref name="AutoDO-4" /> |
||
As is often the case, similar techniques existed long before the name was applied. Jerry Weinberg reports using card decks of random numbers, or cards pulled out of the trash, as input to programs in the 1950s.<ref name="weinberg" /> |
|||
In 1995, a fuzzer was used to test GUI-based tools (such as the [[X Window System]]), network protocols, and system library APIs.<ref name="sutton" />. Later the tested tools included testing command- and GUI-based applications on both Windows and Mac OS X. |
|||
Since 2014, C compilers allow to inject memory-based assertions using [[AddressSanitizer|sanitizers]] which would crash the program upon buffer overflow, use-after-free, or other memory-based errors. |
|||
|
Fuzzing has gone well beyond these early works, and is now an integral part of the security and testing communities, with a myriad of open source and commercial tools, and related research efforts. All tools and results were made public, creating a transparent process that is now common and familiar to the open source community. |
||
| ⚫ |
|
||
Fuzzing has gone well beyond these early works, and is now an integral part of the security and testing communities, with a myriad of open source and commercial tools, and related research efforts. |
|||
==Uses== |
==Uses== |
||
 |
It has been suggested that Monkey testingbemerged into this article. (Discuss) Proposed since January 2016.
|
Fuzzingorfuzz testing 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 a form of random testing commonly used to test for security problems in software or computer systems.
For the purpose of security, input that crosses a trust boundary is often the most interesting.[1] 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.
The random generation of program inputs dates back to the 1950's when data was still stored on punched cards.[2] Programmers would use punched cards pulled from the trash or card decks of random numbers as input to computer programs. Random input generation is sometimes described as Monkey Testing originating from a tool called "The Monkey" that was developed in 1983 to test Mac programs, such as MacPaint.[3] The figurative "monkey" refers to the infinite monkey theorem which states that a monkey hitting keys at random on a typewriter keyboard for an infinite amount of time will eventually type out the entire works of Shakespeare. In the case of testing, the monkey would write the particular sequence of inputs that will trigger a crash.
The term "fuzz" or "fuzzing" originates from a 1988 class project, taught by Barton Miller at the University of Wisconsin.[4][5] The project developed a basic command-line fuzzer to test the reliability of Unix programs by bombarding them with random data until they crashed. 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.
In 1991, the crashme tool was released, which was intended to test the robustness of Unix and Unix-like operating systems by executing random machine instructions.[6] In 1995, a fuzzer was used to test GUI-based tools (such as the X Window System), network protocols, and system library APIs.[7]. Later the tested tools included testing command- and GUI-based applications on both Windows and Mac OS X. Since 2014, C compilers allow to inject memory-based assertions using sanitizers which would crash the program upon buffer overflow, use-after-free, or other memory-based errors.
Fuzzing has gone well beyond these early works, and is now an integral part of the security and testing communities, with a myriad of open source and commercial tools, and related research efforts. All tools and results were made public, creating a transparent process that is now common and familiar to the open source community.
Fuzz testing is often employed as a black-box testing methodology. 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.[8] 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.
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.[9] It can also find unintentional differences between two versions of a program[10] or between two implementations of the same specification.[11]
Any type of program input can be fuzzed. Interesting inputs include: file formats, network protocols, environment variables, sequences of API calls, keyboard and mouse events. Even items not normally considered "input" can be fuzzed, such as the contents of databases, shared memory, or the precise interleaving of threads.
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.[7] These can be employed as white-, grey-, or black-box testing.[7]
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.
Other fuzzers have a detailed understanding of the format or protocol being tested. This 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.[12][13][14] The protocol awareness can also be created heuristically from examples using a tool such as Sequitur.[15] These fuzzers can generate test cases from scratch, or they can mutate examples from test suites or real life. They can concentrate on validorinvalid 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.[16] Evolutionary fuzzing leverages feedback from an heuristic (E.g., code coverage in grey-box harnessing,[17] or a modeled attacker behavior in black-box) effectively automating the approach of exploratory testing.
Test case reduction is the process of extracting minimal test cases from an initial test case.[18][19] 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.
The main problem with fuzzing to find program faults is that it generally only finds very simple faults.[citation needed] The computational complexity of the software testing problem is of exponential order (
On the other hand, bugs found using fuzz testing are sometimes severe, exploitable bugs that could be used by a real attacker.[citation needed] 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.[citation needed]
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.
