Fuzzing

[Jared DeMott <demottja () msu edu>]

"We developed fuzz testing, the sending of unstructured random input to 
an application program." -- B.P. Miller

"A highly automated testing technique that covers numerous boundary 
cases using invalid data (from files, network protocols, API calls, and 
other targets) as application input to better ensure the absence of 
exploitable vulnerabilities. The name comes from modem applications’ 
tendency to fail due to random input caused by line noise on “fuzzy” 
telephone lines.
...
A complete fuzzer iteration, starting from generation: The fuzzer begins 
by getting semivalid data via one of the two main methods for use in 
testing: generation or mutation. The fuzzer then submits the data and 
tracks whether the erroneous input causes the application to crash (in 
which case, it saves the data for later analysis). If not, the fuzzer 
automatically proceeds to the next iteration" -- Peter Oehlert

"Fuzzer: A fuzzer is a program that attempts to discover security 
vulnerabilities by sending random input to an application. If the 
program contains a vulnerability that can leads to an exception, crash 
or server error (in the case of web apps), it can be determined that a 
vulnerability has been discovered. Fuzzers are often termed Fault 
Injectors for this reason, they generate faults and send them to an 
application. Generally fuzzers are good at finding buffer overflow, DoS, 
SQL Injection, XSS, and Format String bugs. They do a poor job at 
finding vulnerabilities related to information disclosure, encryption 
flaws and any other vulnerability that does not cause the program to 
crash." -- Jack Koziol

"Fuzzing” is an automated software testing technique that generates and 
submits random or sequential data to various areas of an application in 
an attempt to uncover security vulnerabilities. For example, when 
searching for buffer overflows, a tester can simply generate data of 
various sizes and send it to one of the application entry points to 
observe how the application handles it." -- Sacha Faust

"For those who hid themselves successfully so far from the hype, the 
term fuzzing is, well, not defined. Everyone talks about it, but it 
means different things to different people. In general, it means 
throwing semi-valid data against a system to automate security testing. 
Many of today's issues in input parsers can be uncovered by constantly 
throwing data at them and watching them crash at some point in time. 
Supposedly, many people find their 0day bugs that way. The result is 
that more and more fuzzing tools appear, talks are held on conferences 
and people start to think that they can secure their products if they 
just sit long enough in the line-of-fire of a fuzzer before being 
shipped." -- FX

"Fault injection or fuzzing is not completely independent technique. 
Fault injection is normally combined with automated running analysis 
tools in order to simulate the use of targeted programs software. The 
word fuzzing comes from fuzz[3], the first fault injection tool 
dedicated to uncover buffer overflows. This naive but efficient approach 
for finding buffer overflows is simply to supply long arguments or 
inputs to a program and see what happens. Fuzzers like Spike[2] and 
Peach[8] are both available for this task. Other tools like PROTOS[20] 
or Security Bug Catcher[22], much closer to fault injection than fuzzing 
are more complex. Using a complete description of a protocol and an 
automated finite state machine of the program, they are able to detect 
if sensible states like authentication can be avoided. Thus, if an 
authenticated procedure is avoided due to buffer overflow or design 
error, this kind of tool can detect it. Unfortunately, these tools must 
have a complete description of protocols and states of audited programs 
software which represents a hard and long manual work.
...
Black box testing with fault injection and stress testing i.e. fuzzing 
is an approach whereby an auditor uses sets of scripts designed to feed 
a program various inputs, different in size and structure. It is usually 
possible to specify how this input should be constructed and maybe how 
the tool should change it according to the program’s behavior.
...
The cardinality of the potential space of inputs defines the complexity 
of fault injectors: fuzzers basically substitute variables for smaller, 
bigger and malformed strings or values. By using a random character 
string generator, Fuzz owns an infinite potential space of inputs. ... 
Substituting variables with random values is *irrelevant*. By using a 
library of finite substituted strings or values drastically reduces the 
size of the potential space of inputs." -- Martin Vaugnoux

"Fuzzing in the security context is often used to find buffer overflows, 
format string bugs, and integer overflows. These sorts of application 
errors can typically be detected by monitoring application crashes." -- 
Dave Aitel

"Fuzz testing or fuzzing is a software testing technique. The basic idea 
is to attach the inputs of a program to a source of random data 
("fuzz"). If the program fails (for example, by crashing, or by failing 
built-in code assertions), then there are defects to correct." -- Wikipedia

---------------------------------------------------------
Both Miller and Jack mention randomness. But Jack mentions security. 
Peter also mentions security, but not randomness, he says invalid data. 
Some use the word fault injection or stress testing. Does the way we 
make data invalid HAVE to include randomness? Vaugnoux prefers a list of 
attacks rather than random data.

Hmm....so what is the definition of fuzzing? (This is important for 
deeper academic study. Is it also important in practice?) All 
definitions point to a search for bugs -- and all are essentially 
performing black box testing. The unstructured, ad hoc, random nature of 
this testing (relatively cheap) makes it different....sometimes. But 
than Peter & Mike come along, have access to src, design a more 
structured/targeted fuzzer, and make fuzzing part of the Microsoft 
development process (not ad hoc and not as cheap), and they still call 
this fuzzing. It's clear that pure randomness is only good "one level 
deep". We need to add some structure (protocol knowledge) to advance 
multiple layers into any non-trivial protocol. I think this is how B.P. 
Miller never had to face this issue: he was always fuzzing cmd line args 
or mouse/key events. Thus there was never a notion of multiple layers.

Fuzzing is a testing technique (usually software) used to find bugs. 
That's about the only consensus currently. So my question is to all you 
fuzzers and software testers: what is the difference between fuzzing and 
software testing? (If someone knows of a good software testing list, 
please forward this on.) In theory, they seem very similar. In practice, 
the second party, security focus of fuzzing has made it effective in 
finding exploitable bugs. But more academically, what is the difference 
between the two (or the definition of each).

The flip side of fuzzing (and testing) is determining when a fault has 
occurred. This seems to receive less attention than how input data is 
malformed. Here's an important question when defining fuzzing: What are 
the different (current and future) methods/trends for detecting when a 
failure/fault/bug has been found?
------------------------------------------------------------

"As in previous studies, our measure of reliability is simple and crude: 
the absence of a crash or hang. The command line tests run from scripts 
and check for the presence of a core file (crash) or non-responsiveness 
based on a time-out (hang). Of course, if the program completes without 
a crash or hang, but prints nonsensical results, we do not classify that 
as a failure. *Other types of testing* are better equipped for such 
failures.
For GUI applications, the technique is similar. We run the applications 
under fuzz-aqua, checking for a system-generated crash log or timing-out 
if the program hangs." - B.P. Miller

"...the Windows operating system uses exception handling to signal 
failure cases to an application and to other parts of the OS. A debugger 
can see these exceptions, so building one in to a fuzzer allows it to 
determine when an application crashes. Other ways to check application 
correctness during fuzzing include
looking for spikes in the program’s memory usage or CPU utilization ... 
From these simple failure models, we can envision more complex and 
complete failure and success models that actually examine the system to 
ensure that it is working correctly after parsing malformed data. I 
recommend using an extensible pattern in the fuzzer to implement checks 
for the success or failure of applications parsing the malformed data. 
This is true particularly because what constitutes success and failure 
will change over the fuzzer’s lifetime." -- Peter Oehlert

Jared