It was a dark and stormy night. Bart Miller – you'll find an interview with him at the end of our feature – was working at home, connected by 1200-baud modem to the University of Wisconsin's mainframe computer. But every thunderclap meant that something went wrong: the lightning strikes disrupted data transmission over the phone line and garbled individual characters, forcing Miller to start over time and time again.

Each time he restarted, he noticed how many programs couldn't cope with disrupted data – they crashed, hung up, or otherwise stopped working in some uncontrollable way. Shouldn't programs do much better with invalid or glitched input? Miller decided to have his students systematically investigate this problem and gave them a programming assignment.

That night in the fall of 1988 is considered the birth of fuzz testing, by far the most important method today for testing programs for robustness and checking for security vulnerabilities. Professional programmers routinely use fuzzing to check for problems that could occur in the wild and might not be easy to anticipate. However, fuzzing is still a mystery to many part-time programmers and advanced users who program informally (including many in the Linux community). This month we take a close look at fuzzing and why it is so important.

What Is Fuzzing?

The nature of fuzzing is revealed directly from Bart Miller's programming assignment: "The goal of this project is to evaluate the robustness of various Unix utility programs given an unpredictable input stream. This project has two parts. First, you will build a fuzz generator. This is a program that will output a random character stream. Second, you will take the fuzz generator and use it to attack as many Unix utilities as possible, with the goal of trying to break them."

This programming task summarizes the basic idea of fuzzing: You automatically generate random input, check to see if the programs fed with it then do unpredictable things, and repeat these two steps very often and very quickly.

In the process, fuzzers use various techniques to find errors. Purely random input is easy to generate; it finds errors in input processing, such as buffer overflows. Model-based fuzzers use grammars and other language models to generate valid and targeted input. Evolution-based fuzzers mutate test input to find variants that cover as much code as possible. Constraint-based fuzzers can solve complex constraints in program code, but they take a long time to do so.

Fuzzing with purely random input is very simple to do: A few lines of program code are all that is needed to generate the necessary input. For example, the fuzzer() function from Listing 1 generates strings of random characters that look something like this:

import random
def fuzzer(max_length=100, char_start=32, char_range=32):
  """Generate a string of up to `max_length` characters
   in the range [`char_start`, `char_start` + `char_range` - 1]"""
  string_length = random.randrange(0, max_length + 1)
  out = ""
  for i in range(0, string_length):
    out += chr(random.randrange(char_start, char_start + char_range))
  return out

!7#%"*#0=)$;%6*;>638:*>80"=</>(/*
:-(2<4 !:5*6856&?""11<7+%<%7,4.8+

Bart Miller referred to this kind of input as fuzz, meaning unstructured, random data. What can fuzz do? Let's imagine that you feed this string to a program that expects a five-digit postal code. If it has a buffer of five characters for the input, but the actual input exceeds its capacity (the fuzz above is more than 60 characters), a buffer overflow can occur. Memory areas beyond the five-character buffer are overwritten by the input in a more-or-less random manner, which, in turn, causes the program to behave more-or-less randomly. It could crash or enter an infinite loop when trying to read the five digits.

If the program receives its input via a web page, attackers could, for example, enter a string like the one above into a form and thus attempt to disrupt the program or render it unusable. Because you can generate millions of fuzz input items like this every minute, the attackers would also have many attempts to inject fuzz. All they would have to do is sit back and let the fuzz generator do its work; after hours or days, a crash might occur.

It doesn't have to stop at the crash, however. Since buffer overflows can also overwrite critical data such as passwords or even program code, it may be possible to design the input in such a way that the attacker gains control of the program or even the computer. This part of the work is not yet as automated as fuzz testing; but, if successful, huge rewards beckon for the discovered vulnerability.

Today's programs are protected against such attacks. As a general rule, you should not trust any data that is under the control of a third party (i.e., that comes from users, other computers, or other programs). A web application that expects a five-digit postal code should therefore make sure that the input actually consists of five digits by already checking the input form to see whether the input is correct. The server needs to check the transmitted data for correctness, and all programs that process it downstream should do the same. Last but not least, programs on the network should only allow a limited number of failed attempts before blocking access.

In 1988, such mechanisms were uncommon, and what Miller's students found was alarming: They could crash more than a third of all Unix utilities within seconds by hitting them with random input. Imagine what would happen today if a third of all Web applications were vulnerable in such a trivial way – the Internet as we know it would be taken over in seconds.

In 1988, however, the Internet was still in its infancy, and every administrator knew the users on their machines personally. In fact, Miller initially had trouble getting his findings published. The typical response was, "So what? Why should I care what happens to invalid data? My users send me valid data!" The open source developers of the time saw it differently and quickly adapted their programs to identify invalid input and reject it in a controlled manner. In this way, most GNU programs and the Linux kernel quickly developed resistance to fuzz input, and the standard thus slowly established itself in the rest of the programming world.

Automatic Testing

Once you have hardened a program against random Miller-style strings, it is very hard for a fuzz generator to find errors. This is because most randomly generated input is invalid. For example, suppose our program processing a postal code shows an error for the postal code 00000, perhaps because that number stands for a particular address. What is the chance of getting this input by chance? If the (simplified) fuzz generator generates input between one and 100 characters, then the chance that it will be five characters is 1:100. Let's also assume that the generator generates 10 different (printable) characters, including 10 digits. Then the chance that five digits will come out is 1:105 (that is one in 100,000). The chance for five zeros is even only 1:1005 (that is one in 10 billion). Multiplied by the chance that we get any input of length five at all, that's one in one trillion. Modern web applications work fast, but even if we assume one millisecond per interaction, in the worst case we would need 31 years of continuous computing to discover the error. There's more to be gained from mining bitcoins.

However, if you know how the input is constructed, you can drastically increase the chance by making that knowledge available to the fuzz generator. This is where a more powerful class of generators comes into play, whose operating principle dates back to 1972. Model-based fuzzers use a specification of the input format to generate valid inputs a priori, bypassing the numerous failed attempts with purely random strings.

One well-known and well-understood method for specifying input formats is grammars that define the structure of the input. For example, the grammar from the box "Structure of a Postal Code" describes the structure of a postal code. Such a grammar consists of rules that specify the structure of a single input element: A <postcode> consists of five directly consecutive digits; a digit is one of ten alternatives separated by |.

<postcode> := <digit><digit><digit><digit><digit>
<digit> := 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

A model-based fuzzer now uses this grammar to generate input. To do this, it starts with an input element on the left (such as <postcode>) and replaces it with the text on the right (<digit><digit><digit><digit>). It repeats the whole thing until all symbolic input elements are replaced. If there are several alternatives to choose from on the right-hand side, it picks one of them at random. Thus, the fuzzer replaces each <digit> input element with one of the digits   to 9, so that it generates, say, the random sequence 43672. It could also be 34829 or 12456 – the important thing is that it is five digits.

Using this grammar, the chance of finding the problematic zip code 00000 can be reduced to 1:100,000. This still sounds like a lot of testing, but even model-based fuzzers generate millions of inputs within minutes. And unlike purely random input, their input is always valid, so they can go deeper into the program and thus find logical errors beyond input processing.

Where Fuzzers Find Errors

Although input processing generally rejects purely random input, model- and evolution-based fuzzers can more easily dig down into the program logic. Constraint-based fuzzers take this up a notch (Figure 1). In fact, model-based fuzzers easily can be used to generate even complex input. The grammar from the box "Grammar for Addresses," for example, generates address data.

<address> := <first_name> <name>, <street> <house_number>, <postcode> <city>
<first_name> := Anton | Berta | ... | <random_name>
<name> := Mueller | Schmidt | ... | <random_name>
<city> := Berlin | Munich | <random_name>
<street> := Main Street | Putzbrunner Street | <random_name> Street
<house_number> := <digit> | <house_number><digit>
<random_name> := <letter> | <random_name><letter>
<letter> := A | B | C | ... | Z

Figure 1: Different fuzzer types are able to dig down to different depths in the software.

A record like Berta Mueller, Main Street 10, 43679 Munich is generated from the <address>. The rules for <house_number> and <random_name> generate a sequence of digits and letters, respectively, resulting in more unusual records like Anton GJK, EIUYLHK Street 00, 23165 Berlin.

Since the user can create and extend grammars, they allow the fuzzer to be more targeted. For example, a security tester could add SQL injection to the preceding grammar, that is, an attack that injects database commands into an input (see box entitled "SQL Injection Via a Grammar").

<city> := Berlin | Munich | <random_name> | <SQL_injection>
<SQL_injection> := '); DROP TABLE addresses;

This injection adds SQL commands to the addresses, which can lead to the deletion of data if the inputs are not checked properly. At this point, at the least, it becomes clear that fuzzing experiments should only be carried out in a controlled environment on your own computer. In some jurisdictions, if you try to fuzz a third party, you risk being prosecuted for data manipulation.

Grammar-based testing is widespread in practice, but it is primarily used to test your own programs – not least because the grammar can always be adapted to concrete test goals. Mozilla and Google, for example, have found and fixed thousands of problems in JavaScript interpreters using the grammar-based Langfuzz [1], which generates JavaScript programs. Csmith [2], a program for generating valid C programs, is used extensively in compiler tests. Model-based FormatFuzzer [3] specializes in binary input such as image files or archives.

If you switch to a browser after reading this, you can rely on its security – thanks in no small part to model-based fuzzing.