GSoC 2018 Reports: Integrate libFuzzer with the Basesystem, Part 2

Prepared by Yang Zheng (tomsun.0.7 AT Gmail DOT com) as part of GSoC 2018

This is the second part of the project of integrating libFuzzer for the userland applications, you can learn about the first part of this project in this post.

After the preparation of the first part, I started to fuzz the userland programs with the libFuzzer. The programs we chose are five:

1. expr(1)
2. sed(1)
3. sh(1)
4. file(1)
5. ping(8)

After we fuzzed them with libFuzzer, we also tried other fuzzers, i.e.: American Fuzzy Lop (AFL), honggfuzz and Radamsa.

Fuzz Userland Programs with libFuzzer

In this section, I'll introduce how to fuzz the five programs with libFuzzer. The libFuzzer is an in-process, coverage-guided fuzzing engine. It can provide some interfaces to be implemented by the users:

• LLVMFuzzerTestOneInput: fuzzing target
• LLVMFuzzerInitialize: initialization function to access argc and argv
• LLVMFuzzerCustomMutator: user-provided custom mutator
• LLVMFuzzerCustomCrossOver: user-provided custom cross-over function

In the above functions, only the LLVMFuzzerTestOneInput is necessary to be implemented for any fuzzing programs. This function takes a buffer and the buffer length as input, it is the target to be fuzzed again and again. When the users want to finish some initialization job with argc and argv parameters, they also need to implement LLVMFuzzerInitialize. With LLVMFuzzerCustomMutator and LLVMFuzzerCustomCrossOver, the users can also change the behaviors of producing input buffer with one or two old input buffers. For more details, you can refer to this document.

Fuzz Userland Programs with Sanitizers

libFuzzer can be used with different sanitizers. It is quite simple to use sanitizers together with libFuzzer, you just need to add sanitizer names to the option like -fsanitize=fuzzer,address,undefined. However, memory sanitizer seems to be an exception. When we tried to use it together with libFuzzer, we got some runtime errors. The official document has mentioned that "using MemorySanitizer (MSAN) with libFuzzer is possible too, but tricky", but it doesn't mention how to use it properly.

In the following part of this article, you can assume that we have used the address and undefined sanitizers together with fuzzers if there is no explicit description.

Fuzz expr(1) with libFuzzer

The expr(1) takes some parameters from the command line as input and then treat the command line as a whole expression to be calculated. A example usage of the expr(1) would be like this:

    $ expr 1 + 1
    2
  

This program is relatively easy to fuzz, what we only to do is transform the original main function to the form of LLVMFuzzerTestOneInput. Since the implementation of the parser in expr(1) takes the argc and argv parameters as input, we need to transform the buffer provided by the LLVMFuzzerTestOneInput to the format needed by the parser. In the implementation, I assume the buffer is composed of several strings separated by the space characters (i.e.: ' ', '\t' and '\n'). Then, we can split the buffer into different strings and organize them into the form of argc and argv parameters.

However, there comes the first problem when I start to fuzz expr(1) with this modification. Since the libFuzzer will treat every exit as an error while fuzzing, there will be a lot of false positives. Fortunately, the implementation of expr(1) is simple, so we only need to replace the exit(3) with the return statement. In the fuzzing process of other programs, I'll introduce how to handle the exit(3) and other error handling interfaces elegantly.

You can also pass the fuzzing dictionary file (to provide keywords) and initial input cases to the libFuzzer, so that it can produce test cases more smartly. For expr(1), the dictionary file will be like this:

    min="-9223372036854775808"
    max="9223372036854775807"
    zero="0"
    one="1"
    negone="-1"
    div="/"
    mod="%"
    add="+"
    sub="-"
    or="|"
    add="&"
  

And there is only one initial test case:

    1 / 2
  

With this setting, we can quickly reproduce an existing bug which has been fixed by Kamil Rytarowski in this patch, that is, when you try to feed one of -9223372036854775808 / -1 or -9223372036854775808 % -1 expressions to expr(1), you will get a SIGFPE. After adopting the fix of this bug, it also detected a bug of integer overflow by feeding expr(1) with 9223372036854775807 * -3. This bug is detected with the help of undefined sanitizer (UBSan). This has been fixed in this commit. The fuzzing of expr(1) can be reproduced with this script.

Fuzz sed(1) with libFuzzer

The sed(1) reads from files or standard input (stdin) and modifying the input as specified by a list of commands. It is more complicated than the expr(1) to be fuzzed as it can receive input from several sources including command line parameters (commands), standard input (text to be operated on) and files (both commands and text). After reading the source code of sed(1), I have two findings:

1. The commands are added by the add_compunit function
2. The input files (including standard input) are organized by the s_flist structure and the mf_fgets function

With these observations, we can manually parse the libFuzzer buffer with the interfaces above. So I organized the buffer as below:

    command #1
    command #2
    ...
    command #N
        // an empty line
    text strings
  

The first several lines are the commands, one line for one command. Then there will be an empty line to identify the end of command lists. At last, the remaining part of this buffer is the text to be operated on. After parsing the buffer like this, we can add the commands one by one with the add_compunit interface. For the text, since we can directly get the whole text buffer as the format of a buffer, I re-implement the mf_fgets interface to get the input directly from the buffer provided by the libFuzzer.

As mentioned before in the fuzzing of expr(1), exit(3) will result in false positives with libFuzzer. Replacing the exit(3) with return statement can solve this problem in expr(1), but it will not work in sed(1) due to the deeper function call stack. The exit(3) interface is usually used to handle the unexpected cases in the programs. So, it will be a good idea to replace it with exceptions. Unfortunately, the programs we fuzzed are all implemented in C language instead of C++. Finally, I choose to use setjmp/longjmp interfaces to handle it: use the setjmp interface to define an exit point in the LLVMFuzzerTestOneInput function, and use longjmp to jmp to this point whenever the original implementation wants to call exit(3).

The dictionary file for it is like this:

    newline="\x0A"
    "a\\\"
    "b"
    "c\\\"
    "d"
    "D"
    "g"
    "G"
    "h"
    "H"
    "i\\\"
    "l"
    "n"
    "N"
    "p"
    "P"
    "q"
    "t"
    "x"
    "y"
    "!"
    ":"
    "="
    "#"
    "/"
  

And here is an initial test case:

    s/hello/hi/g

    hello, world!
  

which means replacing the "hello" into "hi" in the text of "hello, world!". The fuzzing script of sed(1) can be found here.

Fuzz sh(1) with libFuzzer

sh(1) is the standard command interpreter for the system. I choose the evalstring function as the fuzzing entry for sh(1). This function takes a string as the commands to be executed, so we can directly pass the libFuzzer input buffer to this function to start fuzzing. The dictionary file we used is like this:

    "echo"
    "ls"
    "cat"
    "hostname"
    "test"
    "["
    "]"
  

We can also add some other commands and shell script syntax to this file to reproduce other conditions. And also an initial test case is provided:

    echo "hello, world!"
  

You can also reproduce the fuzzing of sh(1) by this script.

Fuzz file(1) with libFuzzer

The fuzzing of file has been done by Christos Zoulas in this project. The difference between this program and other programs from the list is that the main functionality is provided by the libmagic library. As a result, we can directly fuzz the important functions (e.g.: magic_buffer) from this library.

Fuzz ping(8) with libFuzzer

The ping(8) is quite different from all of the programs mentioned above, the main input source is from the network instead of the command line, standard input or files. This challenges us a lot because we usually use the socket interface to receive network data and thus more complex to transform a single buffer into the socket model.

Fortunately, the ping(8) organizes all the network interfaces as the form of hooks to be registered in a structure. So I re-implement all these necessary interfaces (including socket(2), recvfrom(2), sendto(2), poll(2) and etc.) for ping(8).These re-implemented interfaces will take the data from the libFuzzer buffer and transform it into the data to be accessed by the network interfaces. After that, then we can use libFuzzer to fuzz the network data for ping(8). The script to reproduce can be found here.

Fuzz Userland Programs with Other Fuzzers

To compare libFuzzer with other fuzzers from different aspects, including the effort to modify, performance and functionalities, we also fuzzed these five programs with AFL, honggfuzz and radamsa.

Fuzz Programs with AFL and honggfuzz

The AFL and honggfuzz can fuzz the input from standard input and file. They both provide specific compilers (such as afl-cc, afl-clang, hfuzz-cc, hfuzz-clang and etc.) to fuzz programs with coverage information. So, the basic process to fuzz programs with them is to:

1. Use the specific compilers to compile programs with necessary sanitizers
2. Run the fuzzed programs with proper command line parameters

For detailed parameters, you can refer to the scripts for expr(1), sed(1), sh(1), file(1) and ping(8).

There is no need to do any modification to fuzz sed(1), sh(1) and file(1) with AFL and honggfuzz, because these programs mainly get input from standard input or files. But this doesn't mean that they can achieve the same functionalities as libFuzzer. For example, to fuzz the sed(1), you may also need to pass the commands in the command line parameters. This means that you need to manually specify the commands in the command line and you cannot fuzz them with AFL and honggfuzz, because they can only fuzz input from standard input and files. There is an option of reusing the modifications from the fuzzing process with libFuzzer, but we need to further add a main function for the fuzzed program.

For expr(1) and ping(8), we even need more modifications than the libFuzzer solution, because expr(1) mainly gets input from command line parameters and ping(8) mainly gets input from the network.

During this period, I have also prepared a package to install honggfuzz for the pkgsrc-wip repository. To make it compatible with NetBSD, we have also contributed to improving the code in the official repository, for more details, you can refer to this pull request.

Fuzz Programs with Radamsa

Radamsa is a test case generator, it works by reading sample files and generating different interesting outputs. Radamsa is not dependant on the fuzzed programs, it is only dependant on the input sample, which means it will not record the coverage information.

With Radamsa, we can use scripts to fuzz different programs with different input sources. For the expr(1), we can generate the mutated string and store it to a variable in the shell script and then feed it to the expr(1) in command line parameters. For the sed(1), we can generate both command strings and text by Radamsa and then feed them by command line parameters and file separately. For both sh(1) and file(1), we can generate the needed input file by Radamsa in the shell scripts.

It seems that the shell script and Radamsa combination can fuzz any kinds of programs, but it encounters some problems with ping(8). Although Radamsa supports generating input cases as a network server or client, it doesn't support the ICMP protocol. This means that we can not fuzz ping(8) with modifications or help from other applications.

Comparison Among Different Fuzzers

In this project, we have tried four different fuzzers: libFuzzer, AFL, honggfuzz and Radamsa. In this section, I will introduce a comparison from different aspects.

Modification of Fuzzing

For the programs we mentioned above, here I list the lines of code we need to modify as a factor of porting difficulties:

	expr(1)	sed(1)	sh(1)	file(1)	ping(8)
libFuzzer	128	96	60	48	582
AFL/honggfuzz	142	0	0	0	590
Radamsa	0	0	0	0	N/A

As mentioned before, the libFuzzer needs to modify more lines for programs who mainly get input from standard input and files. However, for other programs (i.e.: expr(1) and ping(8)), the AFL and honggfuzz need to add more lines of code to get input from these sources. As for Radamsa, since it only needs the sample input data to generate outputs, it can fuzz all programs without modifications except ping(8).

Binary Sizes

The binary sizes for these fuzzers should also be considered if we want to ship them with NetBSD. The following binary sizes are based on the NetBSD-current with the nearly newest LLVM (compiled from source) as an external toolchain:

	Dependency	Compilers	Fuzzer	Tools	Total
libFuzzer	0	56MB	N/A	0	56MB
AFL	0	24KB	292KB	152KB	468KB
honggfuzz	36KB	840KB	124KB	0	1000KB
Radamsa	588KB	0	608KB	0	1196KB

The above table shows the space needed to install different fuzzers. The "Dependency" column shows the size of dependant library; the "Compilers" column shows the size of compilers used for re-compiling fuzzed programs; the "Fruzzer" column shows the size of fuzzer itself and the "Tools" column shows the size of analysis tools.

For the libFuzzer, if the system has already included the LLVM together with compiler-rt as the toolchain, we don't need extra space to import it. The fuzzer of libFuzzer is compiled together with the user's program, so the size is not counted. The compiler size shown above in this table is the size of statically compiled compiler clang. If we compile it dynamically, then there will be a plenty of dependant libraries should be considered. For the AFL, there is no dependant library except libc, so the size is zero. It will also introduce some tools like afl-analyze, afl-cmin and etc. The honggfuzz is dependant on the libBlocksRuntime library whose size is 36KB. This library is also included in the compiler-rt of LLVM. So, if you have already installed it, this size can be ignored. As for the Radamsa, it needs the Owl Lisp during the building process. So the size of the dependency is the size of Owl Lisp interpreter.

Compiler Compatibility

All these fuzzers except libFuzzer are compatible with both GCC and clang. The AFL and honggfuzz provide a wrapper for the native compiler, and the Radamsa does not care about the compilers. As for the libFuzzer, it is implemented in the compiler-rt of LLVM, so it cannot support the GCC compiler.

Support for Sanitizers

All these fuzzers can work together with sanitizers, but only the libFuzzer can provide a relatively strong guarantee that it can provide them. The AFL and honggfuzz, as I mentioned above, provide some wrappers for the underlying compiler. This means that it is dependant on the native compiler to decide whether they can fuzz the programs with the support of sanitizers. The Radamsa can only fuzz the binary directly, so the programs should be compiled with the sanitizers first. However, since the sanitizers are in the compiler-rt together with libFuzzer, you can directly add some flags of sanitizers while compiling the fuzzed programs.

Performance

At last, you may wonder how fast are those fuzzers to find an existing bug. For the above programs we have fuzzed in NetBSD, only libFuzzer can find two bugs for the expr(1). However, we cannot assert that the libFuzzer performs well than others. To further evaluate the performance of different fuzzers we have used, I choose some simple functions with bugs to measure how fast they can find them out. Here is a table to show the time for them to find the first bug:

	libFuzzer	AFL	honggfuzz	Radamsa
DivTest+S	<1s	7s	1s	7s
DivTest	>10min	>10min	2s	>10min
SimpleTest+S	<1s	>10min	1s	>10min
SimpleTest	<1s	>10min	1s	>10min
CxxStringEqTest+S	<1s	>10min	2s	>10min
CxxStringEqTest	>10min	>10min	2s	>10min
CounterTest+S	1s	5min	1s	7min
CounterTest	1s	4min	1s	7min
SimpleHashTest+S	<1s	3s	1s	2s

The "+S" symbol means the version with sanitizers (in this evaluation, I used address and undefined sanitizers). In this table, we can observe that libFuzzer and honggfuzz perform better than others in most cases. And another point is that fuzzers can work better with sanitizers. For example, in the case of DivTest, the primary goal of this test is to trigger a "divide-by-zero" error, however, when working with the undefined sanitizer, all these fuzzers will trigger the "integer overflow" error more quickly. I only present a part of the interesting results of this evaluation here. You can refer to this script to reproduce some results or do more evaluation by yourself.

Summary

In the past one month, I mainly contributed to:

1. Porting the libFuzzer to NetBSD
2. Preparing a pkgsrc-wip package for honggfuzz
3. Fuzzing some userland programs with libFuzzer and other three different fuzzers
4. Evaluating different fuzzers from different aspects

Regarding the third contribution, I tried to use different methods to handle them according to their features. During this period, I have fortunately found two bugs for the expr(1).

I'd like to thank my mentor Kamil Rytarowski and Christos Zoulas for their suggestions and proposals. I also want to thank Kamil Frankowicz for his advice on fuzzing and playing with AFL. At last, thanks to Google and the NetBSD community for giving me a good opportunity to work on this project.

[0 comments]