1 2 3 4 next »

This article originally appeared in c't 18/2006, p. 210

Christiane Rütten

Data salad

Fuzzing, aka fuzz testing, has revolutionized the automated search for programming flaws. Nowadays, you simply use corrupt data to crash programs and detect flaws even without access to the source code. Indeed, the process is almost over before it starts if you have the right strategy and choose your input data cleverly.

In the past few years, the number of discovered vulnerabilities has been continuously rising, mainly as a result of the development of automated methods for the detection of programming flaws in software. One of the most exciting methods used is one developed relatively recently that can do without both the source code and binary of the program: fuzzing. Using this technique, a program is flooded with arbitrary data until it crashes - an obvious indication of programming flaws.

A crash itself usually suffices to constitute a security vulnerability. After all, attackers can take down specific programs or internet services in denial-of-service attacks if they know what input data can cause a crash. But further analysis of the cause of the crash provides indications of whether and how the flaw might be exploited to inject malicious code.

In 2005, Michael Zalewski's discovery of the extremely critical IFRAME hole in Internet Explorer marked a real breakthrough in media attention for fuzzing. In July of 2006, security expert H.D. Moore then published a new vulnerability each day in a major Internet browser - Mozilla, Safari, Opera, or Internet Explorer - in his "Month of Browser Bugs". Impressively, he managed to find 25 security-related programming flaws in Microsoft's browser alone even though he, like Zalewski, did not have access to the source code.

Nobody's perfect

There is a general consensus that a program probably contains a flaw if it has a certain level of complexity. Those with any significant programming experience certainly believe so. In the inevitable search for programming flaws, a distinction is made between three different cases: you have access to the source code; you only have access to the binary program; you don't have access to either, such as with Internet servers.

Access to the source code facilitates the search for flaws tremendously. At the same time, manually sifting through the source code - the classic approach in flaw detection - has severe limitations. Even midsize programming projects can contain an enormous amount of source code: for instance, the GPG encryption program has some 100,000 lines in C. Likewise, version 2.6.16 of the Linux kernel consists of nearly 5 million lines of source if we include the hundreds of hardware drivers available.

Fortunately, a number of tools can sift through the source code in all common programming languages on the lookout for potential flaws [1]. But even they only provide starting points for further manual checks and generally only catch a fraction of the programming flaws.

If all you have is the executable binary file, which is the case for many commercial products, you can still use disassemblers and debuggers to inspect the program, though the process is then much more time-consuming. Furthermore this process is no longer possible for a number of services on internet servers that only send replies to input data sent via a network connection.

In contrast, fuzzing works in all three cases. Nonetheless, access to the source code or the binary program makes preparations and execution easier.

Sinking ships

The first tool that gave this method the name fuzz [2] was developed in 1990 to test UNIX commands. It merely generated arbitrary strings up to a certain user-defined length; a second program then passed on the strings to the test application. Using this simple procedure, researchers Barton P. Miller, Lars Fredriksen and Bryan So managed to take down a third of the utilities tested, including vi, emacs and telnet.

But there's a catch to bombardment with arbitrary data: most programs expect input data to have a specified format or protocol. For instance, a JPEG image always begins with the bytes "FF D8", and network packets contain indications of links and checksums at specified positions. Generally, programs simply stop processing input if the data do not have the expected structure or if they contain obvious flaws.

Often, formats and protocols are interwoven, such as with DivX and MP3 data inside an AVI container or HTTP data in TCP packets. Flawed headers in lower format or protocol layers also prevent actual usable data from getting to the handling routines. For instance, to test a video player's MP3 decoder, the input data used must contain a correct AVI header because the program would otherwise stop the procedure by outputting an error message.

Therefore if you simply use completely arbitrary data, you waste a lot of time inputting data that stops the test before it really gets started. You can then only have a look at a fraction of the functions available and only a few internal programming statuses.

Furthermore, the large number of possible input data cannot be tested randomly within a reasonable timeframe. You might as well blindly try to sink a ship in the Pacific by randomly dropping bombs all over the ocean. For instance, if we assume an average processing time of 1 ms per data packet, it would take us a thousand years to have covered most of the combinations with lengths up to six bytes.

1 2 3 4 next »