Fuzzing and the quest for safer software
The Buzz on Fuzz

Fuzzing is an important method for finding bugs and security vulnerabilities in software. Read on to find out what fuzzing is and which methods are commonly used today.
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:
Listing 1
Simple Fuzzer in Python
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 |
.
Structure of a Postal Code
<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.
Grammar for Addresses
<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
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").
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.
Buy this article as PDF
(incl. VAT)
Buy Linux Magazine
Direct Download
Read full article as PDF:
Price $2.95
Subscribe to our Linux Newsletters
Find Linux and Open Source Jobs
Subscribe to our ADMIN Newsletters
Find SysAdmin Jobs
News
-
Kubuntu Focus Announces XE Gen 2 Linux Laptop
Another Kubuntu-based laptop has arrived to be your next ultra-portable powerhouse with a Linux heart.
-
MNT Seeks Financial Backing for New Seven-Inch Linux Laptop
MNT Pocket Reform is a tiny laptop that is modular, upgradable, recyclable, reusable, and ships with Debian Linux.
-
Ubuntu Flatpak Remix Adds Flatpak Support Preinstalled
If you're looking for a version of Ubuntu that includes Flatpak support out of the box, there's one clear option.
-
Gnome 44 Release Candidate Now Available
The Gnome 44 release candidate has officially arrived and adds a few changes into the mix.
-
Flathub Vying to Become the Standard Linux App Store
If the Flathub team has any say in the matter, their product will become the default tool for installing Linux apps in 2023.
-
Debian 12 to Ship with KDE Plasma 5.27
The Debian development team has shifted to the latest version of KDE for their testing branch.
-
Planet Computers Launches ARM-based Linux Desktop PCs
The firm that originally released a line of mobile keyboards has taken a different direction and has developed a new line of out-of-the-box mini Linux desktop computers.
-
Ubuntu No Longer Shipping with Flatpak
In a move that probably won’t come as a shock to many, Ubuntu and all of its official spins will no longer ship with Flatpak installed.
-
openSUSE Leap 15.5 Beta Now Available
The final version of the Leap 15 series of openSUSE is available for beta testing and offers only new software versions.
-
Linux Kernel 6.2 Released with New Hardware Support
Find out what's new in the most recent release from Linus Torvalds and the Linux kernel team.