General Theory of Fuzzing

Weaknesses in Fuzzers

You may be thinking that fuzzers are the best thing since sliced bread, but there are some limitations. Let's take a look at a few of them. One property of fuzzers is that they can't find every bug you can find under static analysis. Imagine the following code in a program:

 if (!strcmp(userinput1,"<some static string>")) { strcpy(buffer2,userinput2); } 

For this bug to be reached, userinput1 must be set to a string (known to the authors of the protocol, but not to our fuzzer), and userinput2 must be a very long string. You can divide this bug into two factors:

1. Userinput1 must be a particular string.

2. Userinput2 must be a long string.

For example, assume the program is a SMTP server, which supports HELO , EHLO , and HELL as Hello commands. Perhaps some bugs are triggered only when the server sees HELL , which is an undocumented feature used only by this SMTP server.

Even assuming the fuzzer has a list of special strings, as you get above a few factors you quickly notice that the process becomes exponentially more expensive. A good fuzzer has a list of strings it will try. That means that for each variable you are fuzzing, you must try N strings. And if you want to match that against another variable, that's N*M strings, and so on. (For the fuzzer, an integer is just a short binary string.)

These are the main two weaknesses in fuzzers. Generally, people compensate for these weaknesses by also using static analysis or by doing runtime binary analysis against the target program. These techniques can increase code coverage and hopefully find bugs hidden by traditional fuzzing.

As you come to use fuzzers of various sorts, you'll discover that different fuzzers also have other weaknesses. Perhaps this is due to their underlying infrastructure ”SPIKE, for example, is built heavily on C and is not object oriented. Or you'll find that some target programs are ill-suited to fuzzing. Perhaps they are very slow, or perhaps they crash with nearly any bad input, making it difficult to find an exploitable bug among all the crashes (iMail and rpc.ttdbserverd come to mind). Or perhaps you'll find that the protocol is just too complex to decipher from network traces. Luckily, however, these are not common cases.