The day I fell in love with fuzzing

https://nullprogram.com/blog/2019/01/25/
  • Transfer
In 2007, I wrote a couple of modding tools for the Freelancer space simulator . Game resources are stored in “binary INI” or “BINI” format. Probably, the binary format was chosen for the sake of performance: such files are faster to download and read than arbitrary text in the INI format.

Most of the game content can be edited directly from these files, changing the names, prices of goods, statistics of space ships, or even adding new ships. Binary files are difficult to modify directly, so the natural approach is to convert them to text INI, make changes in a text editor, then convert back to BINI format and replace the files in the game directory.

I did not analyze the BINI format, and I am not the first to learn how to edit them. But I did not like the existing tools, and I had my own vision of how they should work. I prefer the Unix-style interface, although the game itself runs under Windows.

At that time, I was just introduced to the yacc (actually Bison ) and lex (actually flex ) tools , as well as Autoconf, so I used them. It was interesting to try out these utilities in action, although I slavishly imitated other open source projects, not understanding why everything was done in such a way. Due to the use of yacc / lex and the creation of configuration scripts, a full-fledged Unix-like system was required. This is all seen inoriginal version of the programs .

The project turned out to be quite successful: I myself successfully used these tools, and they appeared in different collections for Freelancer modding.

Refactoring


In mid-2018, I returned to this project. Have you ever looked at your old code with the thought: what did you even think about? My INI format turned out to be much tougher and more rigorous than necessary, the recording of the binaries was dubious, and the build did not even work properly.

Thanks to ten years of extra experience, I knew for sure that now I will write these tools much better. And I did it in a few days, rewriting them from scratch. In the master branch on Github now lies this new code.

I like to do everything as easy as possible , so I got rid of autoconf in favor of a simpler and portable Makefile. There is no longer any yacc or lex, and the parser is written by hand. Only the appropriate, portable C is used. The result is so simple that I put together a project with one short command from Visual Studio , so the Makefile is not so necessary. If replaced stdint.h with typedef, you can even build and run binitools under DOS .

The new version is faster, more compact, cleaner and simpler. It is much more flexible in terms of INI input, so it is easier to use. But is it more correct?

Fuzzing


I have been interested in fuzzing for many years , especially afl (american fuzzy lop). But he did not master it, although he tested some tools that I regularly use. But fuzzing didn't find anything remarkable, at least before I gave up. I tested my JSON library and for some reason also did not find anything. It's clear that my JSON parser could not be so reliable, right? But fuzzing showed nothing. (As it turned out, my JSON library is still quite reliable, thanks in large part to the efforts of the community!)

But now I have a relatively new INI parser. Although he can successfully analyze and correctly assemble the initial set of BINI files in the game, his functionality is trulynot tested. Surely here fuzzing will find something. In addition, to run afl on this code, you do not need to write a single line. The default tools work with standard input, which is ideal.

Assuming you have the necessary tools installed (make, gcc, afl), here’s how easy the fuzzing binitools run:

$ make CC=afl-gcc
$ mkdir in out
$ echo '[x]' > in/empty
$ afl-fuzz -i in -o out -- ./bini

The utility biniaccepts INI input and issues a BINI, so it is much more interesting to check it than the reverse procedure unbini. Since it unbinianalyzes relatively simple binary data, (probably) the fuzzer has nothing to look for. However, I just checked anyway.



In this example, I changed the default compiler to the GCC shell for afl ( CC=afl-gcc). Here, afl calls GCC in the background, but adds its own toolkit to the binary. When fuzzing afl-fuzz, it uses this tool to monitor the program execution path. The afl documentation explains the technical details.

I also created input and output directories, putting a minimum working example in the input directory that gives afl a starting point. At startup, it mutates the input queue and monitors changes during program execution. The output directory contains the results and, more importantly, the corpus of input data that cause unique execution paths. In other words, a lot of inputs are processed at the output of a fuzzer, testing many different border scenarios.

The most interesting and terrible result - a complete failure of the program. When I first launched a fuzzer for binitools, I binifound a lot of such failures. Within a few minutes, afl discovered a number of subtle and interesting bugs in my program, which was incredibly useful. Fuzzer found even the unlikelyoutdated pointer bug by checking the different order of different memory allocations. This particular bug was a turning point that made me realize the value of fuzzing.

Not all errors found led to crashes. I also examined the issue and looked at which inputs yielded a successful result, and which did not, and watched as the program handled various extreme cases. She rejected some input that I thought she would handle. Conversely, she processed some data that I considered to be incorrect, and interpreted some data in an unexpected way. So even after fixing bugs with program crashes, I still changed the parser settings to fix each of these unpleasant incidents.

Creating a test suite


As soon as I corrected all the errors detected by the fuzzer and set up the work of the parser in all border situations, I made a set of tests from the fuzzer data case - although not directly.

First, I ran a fuzzer in parallel — this process is explained in the afl documentation — so I got a lot of redundant input data. By redundancy, I mean that the input data is different, but have the same execution path. Fortunately, afl has a tool to deal with this:, the afl-cminbody minimization tool. It eliminates the extra inputs.

Secondly, many of these inputs were longer than necessary to call their unique execution path. It helped afl-tmin, the minimizer of test cases, which reduced the test case.

I separated valid and invalid input - and checked it in the repository. Take a look at all these stupid entrances invented by the fuzzer , based on a single minimum entry:


In fact, here the parser is frozen in one state, and the test suite ensures that a particular build behaves in a very specific way. This is especially useful for ensuring that builds made by other compilers on other platforms really behave the same to their output. My test suite even revealed an error in the dietlibc library because binitools did not pass the tests after binding to it. If it were necessary to make non-trivial changes to the parser, then in fact, we would have to abandon the current test suite and start all over again, so that afl generates an entire new package for the new parser.

Of course, fuzzing has proven itself as a powerful technique. He found a number of errors that I could never discover on my own. Since then, I have become more competent to use it for testing other programs - not just my own - and have found many new bugs. Now, fuzzer has taken a permanent place among the tools in my developer kit.

Also popular now: