Tut10: Fuzzing
In this tutorial, you will learn about fuzzing, an automated software testing technique for bug finding, and play with two of the most commonly-used and effective fuzzing tools, i.e., AFL and libFuzzer. You you learn the workflow of using these fuzzers, and explore their internals and design choices with a few simple examples.
Step 1: Fuzzing with source code
1. The workflow of AFL
We first have to instrument the program, allowing us to extract the coverage map efficiently in every fuzzing invocation.
$ cd tut10-01-fuzzing/tut1
$ afl-gcc ex1.cc
afl-cc 2.52b by <lcamtuf@google.com>
afl-as 2.52b by <lcamtuf@google.com>
[+] Instrumented 9 locations (64-bit, non-hardened mode, ratio 100%).
# meaning 9 basic blocks are instrumented
Instead of using gcc, you can simply invoke afl-gcc,
a wrapper script that enables instrumentation seamlessly without
breaking the building process. In a standard automake-like
building environment, you can easily inject this compiler option via
CC=afl-gcc or CC=afl-clang depending on the copmiler of your choice.
// ex1.cc
int main(int argc, char *argv[]) {
char data[100] = {0};
size_t size = read(0, data, 100);
if (size > 0 && data[0] == 'H')
if (size > 1 && data[1] == 'I')
if (size > 2 && data[2] == '!')
__builtin_trap();
return 0;
}
$ ./a.out
HI!
Illegal instruction (core dumped)
Indeed, ./a.out behaves like a normal program if invoked: instrumented
parts are not activated unless we invoke the program with afl-fuzz, a
fuzzing driver. Let's first check how this binary is instrumented by AFL.
$ nm a.out | grep afl_
0000000000202018 b __afl_area_ptr
0000000000000e8e t __afl_die
0000000000202028 b __afl_fork_pid
...
$ objdump -d a.out | grep afl_maybe_log
7fd: e8 7e 03 00 00 callq b80 <__afl_maybe_log>
871: e8 0a 03 00 00 callq b80 <__afl_maybe_log>
8b5: e8 c6 02 00 00 callq b80 <__afl_maybe_log>
8ed: e8 8e 02 00 00 callq b80 <__afl_maybe_log>
...
You would realize that __afl_maybe_log() is invoked in every basic
blocks, in a total 9 times.
Each basic block is uniquely identified with a random number as below:
7e8: 48 89 14 24 mov %rdx,(%rsp)
7ec: 48 89 4c 24 08 mov %rcx,0x8(%rsp)
7f1: 48 89 44 24 10 mov %rax,0x10(%rsp)
*7f6: 48 c7 c1 33 76 00 00 mov $0x7633,%rcx
7fd: e8 7e 03 00 00 callq b80 <__afl_maybe_log>
The fuzzer's goal is to find one of crashing inputs, "HI!...", that
reaches the __builtin_trap() instruction. Let's see how AFL generates
such an input, quite magically! To do so, we need to provide an
initial input corpus, on which the fuzzer attempts to mutate based.
Let's start the fuzzing with "AAAA" as input, expecting that AFL
successfully converts the input to crash the program.
$ mkdir input output
$ echo AAAA > input/test
$ afl-fuzz -i input -o output ./a.out
(after a few seconds, press Ctrl-c to terminate the fuzzer)
...
american fuzzy lop 2.52b (a.out)
+- process timing -------------------------------------+- overall results -----+
| run time : 0 days, 0 hrs, 0 min, 30 sec | cycles done : 100 |
| last new path : 0 days, 0 hrs, 0 min, 29 sec | total paths : 4 |
| last uniq crash : 0 days, 0 hrs, 0 min, 29 sec | uniq crashes : 1 |
| last uniq hang : none seen yet | uniq hangs : 0 |
+- cycle progress --------------------+- map coverage -+-----------------------+
| now processing : 2 (50.00%) | map density : 0.01% / 0.02% |
| paths timed out : 0 (0.00%) | count coverage : 1.00 bits/tuple |
+- stage progress --------------------+- findings in depth --------------------+
| now trying : havoc | favored paths : 4 (100.00%) |
| stage execs : 237/256 (92.58%) | new edges on : 4 (100.00%) |
| total execs : 121k | total crashes : 6 (1 unique) |
| exec speed : 3985/sec | total tmouts : 0 (0 unique) |
+- fuzzing strategy yields -----------+---------------+- path geometry --------+
| bit flips : 1/104, 1/100, 0/92 | levels : 3 |
| byte flips : 0/13, 0/9, 0/3 | pending : 0 |
| arithmetics : 1/728, 0/0, 0/0 | pend fav : 0 |
| known ints : 0/70, 0/252, 0/132 | own finds : 3 |
| dictionary : 0/0, 0/0, 0/0 | imported : n/a |
| havoc : 1/120k, 0/0 | stability : 100.00% |
| trim : 20.00%/1, 0.00% +------------------------+
+-----------------------------------------------------+ [cpu000: 10%]
There are a few interesting information in AFL's GUI:
- Overall results:
+-----------------------+
| cycles done : 100 |
| total paths : 4 |
| uniq crashes : 1 |
| uniq hangs : 0 |
+-----------------------+
cycles done: the count of queue passes done so far, meaning that the number of times that AFL went over all the interesting test cases.total paths: how many test cases discovered so far.unique crashes/hangs: how many crashes/hangs discovered so far.
- Map coverage
+- map coverage -+-----------------------+
| map density : 0.01% / 0.02% |
| count coverage : 1.00 bits/tuple |
+- findings in depth --------------------+
map density: coverage bitmap density of the current input (left) and all inputs (right)count coverage: the variability in tuple hit counts seen in the binary
- Stage progress
+- stage progress --------------------+
| now trying : havoc |
| stage execs : 237/256 (92.58%) |
| total execs : 121k |
| exec speed : 3985/sec |
+- fuzzing strategy yields -----------+
This describes the progress of the current stage: e.g., which fuzzing strategy is applied and how much this stage is completed.
(from document)
- havoc - a sort-of-fixed-length cycle with stacked random tweaks. The
operations attempted during this stage include bit flips, overwrites with
random and "interesting" integers, block deletion, block duplication, plus
assorted dictionary-related operations (if a dictionary is supplied in the
first place).
- Fuzzing strategy yields
+- fuzzing strategy yields ---------------------------+
| bit flips : 1/104, 1/100, 0/92 |
| byte flips : 0/13, 0/9, 0/3 |
| arithmetics : 1/728, 0/0, 0/0 |
| known ints : 0/70, 0/252, 0/132 |
| dictionary : 0/0, 0/0, 0/0 |
| havoc : 1/120k, 0/0 |
| trim : 20.00%/1, 0.00% |
+-----------------------------------------------------+
It summarizes how each strategies yield a new path: e.g., bit flips, havoc and arithmetics found new paths, helping us to determine which strategies work for our fuzzing target.
2. Finding a security bug!
Using AFL, we can reveal non-trivial security bugs without having a deep understanding of the target program. Today's target is a toy program called "registration" that is carefully implemented to contain a bug for education purpose.
Can you spot any bugs in "registration.c" via code auditing? Indeed, it's not too easy to find one, so let's try to use AFL.
- Instrumentation
$ CC=afl-gcc make
$ ./registration
...
- Generating seed inputs
Let's manually explore this toy program while collecting what we are typing as input.
$ tee input/test1 | ./registration
(your input...)
$ tee input/test2 | ./registration
(your input...)
- Fuzzing time!
$ afl-fuzz -i input -o output ./registration
In fact, the fuzzer fairly quickly finds a few crashing inputs! You can easily analyze them by manually injecting the crashing input to the program or by running it with gdb.
$ ls output/crashes
id:000001,sig:06,src:000001,op:flip2,pos:18
...
Let's pick one of the crashing inputs, and reproduce the crash like this:
$ cat output/crashes/id:000001,sig:06,src:000001,op:flip2,pos:18 | ./registration
...
[*] Unregister course :(
- Give me an index to choose
double free or corruption (fasttop)
Abort (core dumped) ./registration
# need to run docker with
# --cap-add=SYS_PTRACE --security-opt seccomp=unconfined
$ gdb registration
(gdb) run < output/crashes/id:000000,sig:06,src:000000...
...
Program received signal SIGABRT, Aborted.
__GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:51
(gdb) bt
#0 __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:51
#1 0x00007ffff7a24801 in __GI_abort () at abort.c:79
#2 0x00007ffff7a6d897 in __libc_message (action=action@entry=do_abort, fmt=fmt@entry=0x7ffff7b9ab9a "%s\n") at ../sysdeps/posix/libc_fatal.c:181
#3 0x00007ffff7a7490a in malloc_printerr (str=str@entry=0x7ffff7b9c828 "double free or corruption (fasttop)") at malloc.c:5350
#4 0x00007ffff7a7c004 in _int_free (have_lock=0, p=0x55555575a250, av=0x7ffff7dcfc40 <main_arena>) at malloc.c:4230
#5 __GI___libc_free (mem=0x55555575a260) at malloc.c:3124
#6 0x0000555555556d1d in unregister_course () at registration.c:110
#7 0x0000555555554de7 in main () at registration.c:173
(Have you spotted the exploitable security bug?!)
- Better analysis with AddressSanitizer (ASAN)
You can enable ASAN simply by setting AFL_USE_ASAN=1:
$ make clean
$ AFL_USE_ASAN=1 CC=afl-clang make
$ ./registration < output/crashes/id:000000,sig:06,src:000000...
...
=================================================================
==20957==ERROR: AddressSanitizer: heap-use-after-free on address 0x603000000020 at pc 0x562a7aadc3f9 bp 0x7ffee576f8f0 sp 0x7ffee576f8e8
READ of size 8 at 0x603000000020 thread T0
#0 0x562a7aadc3f8 in register_course tut1/registration.c:63:21
#1 0x562a7aade3d8 in main tut1/registration.c:170:17
#2 0x7f1c00605222 in __libc_start_main (/usr/lib/libc.so.6+0x24222)
#3 0x562a7a9cb0ed in _start (tut1/registration+0x1f0ed)
0x603000000020 is located 16 bytes inside of 32-byte region [0x603000000010,0x603000000030)
freed by thread T0 here:
#0 0x562a7aa9de61 in __interceptor_free (tut1/registration+0xf1e61)
#1 0x562a7aadcf28 in unregister_course tut1/registration.c:111:5
#2 0x562a7aade3e2 in main tut1/registration.c:173:17
#3 0x7f1c00605222 in __libc_start_main (/usr/lib/libc.so.6+0x24222)
previously allocated by thread T0 here:
#0 0x562a7aa9e249 in malloc (tut1/registration+0xf2249)
#1 0x562a7aadc0c5 in new_student tut1/registration.c:16:31
#2 0x562a7aadc0c5 in register_course tut1/registration.c:56
#3 0x562a7aade3d8 in main tut1/registration.c:170:17
#4 0x7f1c00605222 in __libc_start_main (/usr/lib/libc.so.6+0x24222)
SUMMARY: AddressSanitizer: heap-use-after-free tut1/registration.c:63:21 in register_course
Shadow bytes around the buggy address:
0x0c067fff7fb0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c067fff7fc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c067fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c067fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c067fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x0c067fff8000: fa fa fd fd[fd]fd fa fa 00 00 00 00 fa fa fa fa
0x0c067fff8010: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c067fff8020: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c067fff8030: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c067fff8040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c067fff8050: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Freed heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
Container overflow: fc
Array cookie: ac
Intra object redzone: bb
ASan internal: fe
Left alloca redzone: ca
Right alloca redzone: cb
Shadow gap: cc
==20957==ABORTING
With ASAN, the program might stop at a different location, i.e.,
register_course(), unlike the previous case as it aborts when free()-ing in
unregister_course(). ASAN really helps in pinpointing the root cause
of the security problem!
3. Understanding the limitations of AFL
- # unique bugs
// ex2.cc
int strncmp(const char *s1, const char *s2, size_t n) {
size_t i;
int diff;
* for (i = 0; i < n; i++) {
* diff = ((unsigned char *) s1)[i] - ((unsigned char *) s2)[i];
* if (diff != 0 || s1[i] == '\0')
* return diff;
}
return 0;
}
$ afl-gcc ex2.cc
$ afl-fuzz -i input -o output ./a.out
...
At this time, AFL quickly reports more than one
unique crashes, although all of them are essentially the same. This is
mainly because AFL considers an input unique if it results
in a different coverage map, while each iteration of the for
loop (*) in strncmp() is likely considered as an unique path.
- Tight conditional constraints
// ex3.cc
int main(int argc, char *argv[]) {
char data[100] = {0};
size_t size = read(0, data, 100);
if (size > 3 && *(unsigned int *)data == 0xdeadbeef)
__builtin_trap();
return 0;
}
$ afl-gcc ex3.cc
$ afl-fuzz -i input -o output ./a.out
...
Even after a few minutes, it's unlikely that AFL can randomly mutate
inputs to become 0xdeadbeef for triggering crashes.
Nevertheless, it indicates the importance of the seeding inputs:
try to provide those that can cover as many branches as possible
so that the fuzzer can focus on discovering crashing inputs.
Step 2: Fuzzing binaries (without source code)
Now we are going to fuzz binary programs. In most cases as attackers,
we cannot assume the availability of source code to find vulnerabilities.
To provide such transparency, we are going to use a system-wide
emulator, called QEMU, to combine with AFL for fuzzing binaries.
- Compile AFL & QEMU
$ cd tut10-01-fuzzing
$ ./build.sh
- Legitimate corpus
$ cd tut2
$ ls -l input
-rw-rw-r-- 1 root root 15631 Oct 25 01:35 sample.gif
Since the fuzzed binary gif2png transforms a gif file into a png file,
we can find legitimate gif images online
and feed them to fuzzer as seeding inputs.
- Run fuzzer
$ ../afl-2.52b/afl-fuzz -Q -i input -o output -- ./gif2png
- Analyze crashes
$ gdb gif2png
(gdb) run < output/crashes/id:000000,sig:06,src:000000...
[Task] Can you find any bugs in the binary?
Step 3: Fuzzing Real-World Application
- Target program: ABC
ABC is a text-based music notation system designed to be comprehensible by both people and computers. Music notated in abc is written using letter, digits and punctuation marks.
Let's generate a Christmas Carol! Save the below text as music.abc:
X:23001
T:We Wish You A Merry Christmas
R:Waltz
C:Trad.
O:England, Sussex
Z:Paul Hardy's Xmas Tunebook 2012 (see www.paulhardy.net). Creative Commons cc by-nc-sa licenced.
M:3/4
L:1/8
Q:1/4=180
K:G
D2|"G" G2 GAGF|"C" E2 C2 E2|"A" A2 ABAG|"D" F2 D2 D2|
"B" B2 BcBA|"Em" G2 E2 DD|"C" E2 A2 "D" F2|"G" G4 D2||
"G" G2 G2 G2|"D" F4 F2|"A" G2 F2 E2|"D" D4 A2|
"B" B2 AA G2|"D" d2 D2 DD|"C" E2 A2 "D" F2|"G" G6|]
W:We wish you a merry Christmas, we wish you a merry Christmas,
W:We wish you a merry Christmas and a happy New Year!
W:Glad tidings we bring, to you and your kin,
W:We wish you a merry Christmas and a happy New Year!
Run the target binary with the saved text, and check the content of the generated file.
$ cd tut3
$ ./abcm2ps.bin music.abc
$ ls -l Out.ps
-rw-r--r-- 1 root root 21494 Oct 25 01:47 Out.ps
- Let's fuzz this program!
$ mkdir input
$ mv music.abc input
$ ../afl-2.52b/afl-fuzz -Q -i input -o output -- ./abcm2ps.bin -
(NOTE. '-' is important, as it makes binary read input from stdin)
[Task] Can you find any bugs in the binary?
Step 4: libFuzzer, Looking for Heartbleed!
Now we will learn about libFuzzer that is yet another
coverage-based, evolutionary fuzzer. Unlike AFL, however,
libFuzzer runs "in-process" (i.e., don't fork). Thus, it can
easily outperform in regard to the cost of testing (i.e., # exec/sec)
compared to AFL.
It has one fundamental caveat: the testing function, or the way you test, should be side-effect free, meaning no changes of global states. It's really up to the developers who run libFuzzer.
- The workflow of libFuzzer
Let's first instrument the code. At this time, it does not require a
special wrapper unlike afl-gcc/afl-clang, as the latest clang is
already well integrated with libFuzzer.
$ cd tut4
$ clang -fsanitize=fuzzer ex1.cc
$ ./a.out
...
// ex1.cc
extern "C" int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) {
if (size > 0 && data[0] == 'H')
if (size > 1 && data[1] == 'I')
if (size > 2 && data[2] == '!')
__builtin_trap();
return 0;
}
ex1.cc is essentially the same code you saw in the previous step, but it is
tweaked a bit to support libFuzzer. In fact, it is designed to be
linked with libFuzzer.a (i.e., the starting main() in the
/usr/lib/llvm-6.0/lib/libFuzzer.a). The fuzzing always starts by
invoking LLVMFuzzerTestOneInput() with two arguments, data (i.e.,
mutated input) and its size. For each fuzzing run, libfuzzer follows
these steps (similar to AFL):
- determine data and size for testing
- run LLVMFuzzerTestOneInput(data, size)
- get the feedback (i.e., coverage) of the past run
- reflect the feedback to determine next inputs
If the compiled program crashes (e.g., raising SEGFAULT) in the middle the cycle,
it stops, reports and reproduces the tested input for further investigation.
Let's understand the output of the fuzzer execution:
$ ./a.out
INFO: Seed: 1669786791
INFO: Loaded 1 modules (8 inline 8-bit counters): 8 [0x67d020, 0x67d028),
INFO: Loaded 1 PC tables (8 PCs): 8 [0x46c630,0x46c6b0),
INFO: -max_len is not provided; libFuzzer will not generate inputs larger than 4096 bytes
INFO: A corpus is not provided, starting from an empty corpus
#2 INITED cov: 2 ft: 2 corp: 1/1b exec/s: 0 rss: 32Mb
#402 NEW cov: 3 ft: 3 corp: 2/5b exec/s: 0 rss: 32Mb L: 4/4 MS: 5 ChangeByte-ChangeByte-ChangeByte-CMP-EraseBytes- DE: "H\x00\x00\x00"-
#415 REDUCE cov: 3 ft: 3 corp: 2/4b exec/s: 0 rss: 32Mb L: 3/3 MS: 3 ChangeBit-ChangeByte-EraseBytes-
#426 REDUCE cov: 3 ft: 3 corp: 2/3b exec/s: 0 rss: 32Mb L: 2/2 MS: 1 EraseBytes-
#437 REDUCE cov: 4 ft: 4 corp: 3/4b exec/s: 0 rss: 32Mb L: 1/2 MS: 1 EraseBytes-
#9460 NEW cov: 5 ft: 5 corp: 4/6b exec/s: 0 rss: 32Mb L: 2/2 MS: 3 CMP-EraseBytes-ChangeBit- DE: "H\x00"-
#9463 NEW cov: 6 ft: 6 corp: 5/9b exec/s: 0 rss: 32Mb L: 3/3 MS: 3 CopyPart-CopyPart-EraseBytes-
==26007== ERROR: libFuzzer: deadly signal
#0 0x460933 in __sanitizer_print_stack_trace (/tut/tut10-01-fuzzing/tut4/a.out+0x460933)
#1 0x4177d6 in fuzzer::Fuzzer::CrashCallback() (/tut/tut10-01-fuzzing/tut4/a.out+0x4177d6)
#2 0x41782f in fuzzer::Fuzzer::StaticCrashSignalCallback() (/tut/tut10-01-fuzzing/tut4/a.out+0x41782f)
#3 0x7f72da89788f (/lib/x86_64-linux-gnu/libpthread.so.0+0x1288f)
#4 0x460d12 in LLVMFuzzerTestOneInput (/tut/tut10-01-fuzzing/tut4/a.out+0x460d12)
#5 0x417f17 in fuzzer::Fuzzer::ExecuteCallback(unsigned char const*, unsigned long) (/tut/tut10-01-fuzzing/tut4/a.out+0x417f17)
#6 0x422784 in fuzzer::Fuzzer::MutateAndTestOne() (/tut/tut10-01-fuzzing/tut4/a.out+0x422784)
#7 0x423def in fuzzer::Fuzzer::Loop(std::vector<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, fuzzer::fuzzer_allocator<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > > > const&) (/tut/tut10-01-fuzzing/tut4/a.out+0x423def)
#8 0x4131ac in fuzzer::FuzzerDriver(int*, char***, int (*)(unsigned char const*, unsigned long)) (/tut/tut10-01-fuzzing/tut4/a.out+0x4131ac)
#9 0x406092 in main (/tut/tut10-01-fuzzing/tut4/a.out+0x406092)
#10 0x7f72d9af3b96 in __libc_start_main /build/glibc-OTsEL5/glibc-2.27/csu/../csu/libc-start.c:310
#11 0x4060e9 in _start (/tut/tut10-01-fuzzing/tut4/a.out+0x4060e9)
NOTE: libFuzzer has rudimentary signal handlers.
Combine libFuzzer with AddressSanitizer or similar for better crash reports.
SUMMARY: libFuzzer: deadly signal
MS: 2 InsertByte-ChangeByte-; base unit: 7b8e94a3093762ac25eef0712450555132537f26
0x48,0x49,0x21,0x49,
HI!I
artifact_prefix='./'; Test unit written to ./crash-df43a18548c7a17b14b308e6c9c401193fb6d4a9
Base64: SEkhSQ==
- Seed
INFO: Seed: 107951530
Have you tried invoking ./a.out multiple times? Have you noticed that its output changes in every invocation? It shows that the randomness aspect of libFuzzer. If you want to deterministically reproduce the result, you can provide the seed via the "-seed" argument like:
$ ./a.out -seed=107951530
- Instrumentation
INFO: Loaded 1 modules (8 inline 8-bit counters): 8 [0x55f89f7cac20, 0x55f89f7cac28),
INFO: Loaded 1 PC tables (8 PCs): 8 [0x55f89f7cac28,0x55f89f7caca8),`
It shows that # PCs are instrumented (8 PCs) and keeps track of 8-bit (i.e., 255 times) per instrumented branch or edge.
- Corpus
INFO: -max_len is not provided; libFuzzer will not generate inputs larger than 4096 bytes
INFO: A corpus is not provided, starting from an empty corpus
-max_len limits the testing input size (upto 4KB by default) and it
runs without any corpus. If you'd like to add initial inputs, just
create a corpus directory and provide it via another argument, similar to AFL.
$ mkdir corpus
$ echo AAAA > corpus/seed1
$ ./a.out corpus
...
- Fuzzing Status
+---> #execution
| +---> status
---+ --+
#426 NEW cov: 6 ft: 6 corp: 5/9b lim: 4 exec/s: 0 rss: 23Mb L: 2/3 MS: 1 EraseBytes-
-----+ ----+ ---------+ -----+ --------+ --------+ -----+ +---------------
| | | | | | | +---> mutation strategies (see more)
| | | | | | +---> input size / max size
| | | | | +---> memory usage
| | | | +---> exec/s (but this run exits too fast)
| | | +---> #size limit in this phase, increasing upto -max_len
| | +---> #corpus in memory (6 inputs), its total size (9 bytes)
| +---> #features (e.g., #edge, counters, etc)
+---> coverage of #code block
The mutation strategies are the most interesting field:
+---> N mutations
|
MS: 1 EraseBytes-
MS: 2 ShuffleBytes-CMP- DE: "I\x00"-
|
+----------------> mutation strategies
There are ~15 different mutation strategies implemented in libFuzzer. Let's take a look on one of them:
size_t MutationDispatcher::Mutate_ShuffleBytes(uint8_t *Data, size_t Size,
size_t MaxSize) {
if (Size > MaxSize || Size == 0) return 0;
size_t ShuffleAmount =
Rand(std::min(Size, (size_t)8)) + 1; // [1,8] and <= Size.
size_t ShuffleStart = Rand(Size - ShuffleAmount);
assert(ShuffleStart + ShuffleAmount <= Size);
std::shuffle(Data + ShuffleStart, Data + ShuffleStart + ShuffleAmount, Rand);
return Size;
}
As the name applies, ShuffleBytes goes over #ShuffleAmount and
randomly shuffles each bytes ranged from ShuffleStart.
Note that the status line is reported whenever the new coverage is
found (see "cov:" increasing on every status line).
- Crash Report
==26007== ERROR: libFuzzer: deadly signal
#0 0x460933 in __sanitizer_print_stack_trace (/tut/tut10-01-fuzzing/tut4/a.out+0x460933)
#1 0x4177d6 in fuzzer::Fuzzer::CrashCallback() (/tut/tut10-01-fuzzing/tut4/a.out+0x4177d6)
#2 0x41782f in fuzzer::Fuzzer::StaticCrashSignalCallback() (/tut/tut10-01-fuzzing/tut4/a.out+0x41782f)
#3 0x7f72da89788f (/lib/x86_64-linux-gnu/libpthread.so.0+0x1288f)
#4 0x460d12 in LLVMFuzzerTestOneInput (/tut/tut10-01-fuzzing/tut4/a.out+0x460d12)
...
SUMMARY: libFuzzer: deadly signal
MS: 2 InsertByte-ChangeByte-; base unit: 7b8e94a3093762ac25eef0712450555132537f26
0x48,0x49,0x21,0x49,
HI!I
artifact_prefix='./'; Test unit written to ./crash-df43a18548c7a17b14b308e6c9c401193fb6d4a9
Base64: SEkhSQ==
Whenever the fuzzer catches a signal (e.g., SEGFAULT), it stops and
reports the crashing status like above---in this case, the fuzzer hits __builtin_trap().
It also persistently stores the crashing input as a file as a result (i.e.,
crash-df43a18548c7a17b14b308e6c9c401193fb6d4a9)
The crashing input can be individually tested by passing it to the instrumented binary.
$ ./a.out ./crash-df43a18548c7a17b14b308e6c9c401193fb6d4a9
...
- libFuzzer internals
Let's explore a few interesting design decisions made by libFuzzer:
- Edge coverage
More realistically, you can check if libFuzzer can find an input for
strncmp(). In fact, this example indicates that having "edge" coverage
really helps in finding bugs compared with a simple code coverage.
$ clang -fsanitize=fuzzer ex2.cc
$ ./a.out
...
// ex2.cc
int strncmp(const char *s1, const char *s2, size_t n) {
size_t i;
int diff;
for (i = 0; i < n; i++) {
diff = ((unsigned char *) s1)[i] - ((unsigned char *) s2)[i];
* if (diff != 0 || s1[i] == '\0')
return diff;
}
return 0;
}
- Instrumentation
The limitation of "bruteforcing" is to find an exact input condition concretely specified in the conditional branch, like below.
// ex3.cc
extern "C" int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) {
if (size > 3 && *(unsigned int *)data == 0xdeadbeef)
__builtin_trap();
return 0;
}
What's the chance of "randomly" picking 0xdeadbeef?
$ clang -fsanitize=fuzzer ex3.cc
$ ./a.out
...
You might find that libFuzzer finds the exact input surprisingly quickly! In fact, during instrumentation, libFuzzer identifies such simple comparison and takes them into consideration when mutating the input corpus.
$ objdump -M intel-mnemonic -d a.out
...
0000000000065ba0 <LLVMFuzzerTestOneInput>:
460b90: 55 push rbp
460b91: 48 89 e5 mov rbp,rsp
...
*460beb: bf ef be ad de mov edi,0xdeadbeef
*460bf0: 48 8b 45 f8 mov rax,QWORD PTR [rbp-0x8]
*460bf4: 8b 08 mov ecx,DWORD PTR [rax]
*460bf6: 89 ce mov esi,ecx
*460bf8: 89 4d e4 mov DWORD PTR [rbp-0x1c],ecx
*460bfb: e8 50 6e fd ff call 437a50 <__sanitizer_cov_trace_const_cmp4>
460c00: 8b 4d e4 mov ecx,DWORD PTR [rbp-0x1c]
460c03: 81 f9 ef be ad de cmp ecx,0xdeadbeef
460c09: 0f 84 15 00 00 00 je 460c24 <LLVMFuzzerTestOneInput+0x94>
...
You can see one helper function, __sanitizer_cov_trace_const_cmp4(),
keeps track of the constant, 0xdeadbeef, associated with the cmp
instruction.
These are just tip of the iceberg. There are non-trivial amount of heuristics implemented in libFuzzer, making it possible to discover new bugs in programs.
- Finding Heartbleed
Let's try to use libFuzzer in finding the Heartbleed bug in OpenSSL!
// https://github.com/google/fuzzer-test-suite
// handshake-fuzz.cc
extern "C" int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) {
static int unused = Init();
SSL *server = SSL_new(sctx);
BIO *sinbio = BIO_new(BIO_s_mem());
BIO *soutbio = BIO_new(BIO_s_mem());
SSL_set_bio(server, sinbio, soutbio);
SSL_set_accept_state(server);
BIO_write(sinbio, Data, Size);
SSL_do_handshake(server);
SSL_free(server);
return 0;
}
To correctly test SSL_do_handshake(), we first have to prepare proper
environments for OpenSSL (e.g., SSL_new), and set up the compatible
interfaces (e.g., BIOs above) that deliver the mutated input to
SSL_do_handshake().
The instrumentation process is pretty trivial:
$ cat build.sh
...
clang++ -g handshake-fuzz.cc -fsanitize=address -Iopenssl-1.0.1f/include \
openssl-1.0.1f/libssl.a openssl-1.0.1f/libcrypto.a \
/usr/lib/llvm-6.0/lib/libFuzzer.a
$ ./build.sh
To run the fuzzer:
$ ./a.out
...
==28911==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x629000009748 at pc 0x0000004dc0a2 bp 0x7ffe1158dc10 sp 0x7ffe1158d3c0
READ of size 65535 at 0x629000009748 thread T0
#0 0x4dc0a1 in __asan_memcpy (/tut/tut10-01-fuzzing/tut4/a.out+0x4dc0a1)
#1 0x525d4e in tls1_process_heartbeat /tut/tut10-01-fuzzing/tut4/openssl-1.0.1f/ssl/t1_lib.c:2586:3
#2 0x58f263 in ssl3_read_bytes /tut/tut10-01-fuzzing/tut4/openssl-1.0.1f/ssl/s3_pkt.c:1092:4
#3 0x59380a in ssl3_get_message /tut/tut10-01-fuzzing/tut4/openssl-1.0.1f/ssl/s3_both.c:457:7
#4 0x56103c in ssl3_get_client_hello /tut/tut10-01-fuzzing/tut4/openssl-1.0.1f/ssl/s3_srvr.c:941:4
...
0x629000009748 is located 0 bytes to the right of 17736-byte region [0x629000005200,0x629000009748)
allocated by thread T0 here:
#0 0x4dd1e0 in __interceptor_malloc (/tut/tut10-01-fuzzing/tut4/a.out+0x4dd1e0)
#1 0x5c1a92 in CRYPTO_malloc /tut/tut10-01-fuzzing/tut4/openssl-1.0.1f/crypto/mem.c:308:8
SUMMARY: AddressSanitizer: heap-buffer-overflow (/tut/tut10-01-fuzzing/tut4/a.out+0x4dc0a1) in __asan_memcpy
Shadow bytes around the buggy address:
0x0c527fff9290: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c527fff92a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c527fff92b0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c527fff92c0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c527fff92d0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x0c527fff92e0: 00 00 00 00 00 00 00 00 00[fa]fa fa fa fa fa fa
0x0c527fff92f0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c527fff9300: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c527fff9310: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c527fff9320: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c527fff9330: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Freed heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
Container overflow: fc
Array cookie: ac
Intra object redzone: bb
ASan internal: fe
Left alloca redzone: ca
Right alloca redzone: cb
==28911==ABORTING
MS: 1 PersAutoDict- DE: "\xff\xff\xff\xff"-; base unit: 96438ff618abab3b00a2e08ae5faa5414f28ec3e
0x18,0x3,0x2,0x0,0x1,0x1,0xff,0xff,0xff,0xff,0x0,0x14,0x3,0x82,0x0,0x28,0x1,0x1,0x8a,
\x18\x03\x02\x00\x01\x01\xff\xff\xff\xff\x00\x14\x03\x82\x00(\x01\x01\x8a
artifact_prefix='./'; Test unit written to ./crash-707d154a59b6e039af702abfa00867937bc3ee16
Base64: GAMCAAEB/////wAUA4IAKAEBig==
You can easily debug the crash by attaching gdb to ./a.out with the crashing input:
$ gdb ./a.out --args
> br tls1_process_heartbeat
> run ./crash-707d154a59b6e039af702abfa00867937bc3ee16
...
[Task] Could you trace down to
memcpy(to, from, nbytes)and map the crashing input to its arguments?
Hope you now understand the potential of using fuzzers, and apply to what you are developing!