This blogpost sheds some light on how fuzzers handle crash deduplication and what a unique crash is for a fuzzer. For this, we take a look at two contrived examples and compare the unique crashes identified by AFL++ and honggfuzz.
Both examples are similar. They read from STDIN, check if the first character of the read data is a digit, then call a vulnerable function. The main difference in test1.c is that the program crashes directly in the vuln function due to a null pointer dereference. In test2.c, a previously allocated buffer is freed; this buffer is again freed at the end of main, resulting in libc identifying the double free and raising a sigabort.
In test1.c the crash happens in line 6 when 42 is written to the null pointer. Test2.c is very similar to test1.c, however, we allocate a buffer with malloc and pass a pointer to this buffer to vuln where the buffer is freed the first time. After the comparisons and right before the return statement in line 39 we free this buffer once more. This will cause libc to raise an error as a double-free is detected. We could also have compiled the program with ASan, which would result in the same behavior.
As a first step, let’s compile the programs with instrumentation for the respective fuzzers. I used the brand-new AFL++ version 3.00a and honggfuzz 2.3.1. I always used the default options without anything fancier as the idea is to showcase the difference in crash identification and not the difference in instrumentation.
For AFL++ I had to “cheat” a little. Clang-11 optimized the comparisons and double-free simply out as the buffer was never used. You can find the used c source code here.
$ <afl++_root_dir>/afl-clang-fast test1.c -o test1_afl $ <afl++_root_dir>/afl-clang-fast test2.c -o test2_afl $ <honggfuzz_root_dir>/hfuzz_cc/hfuzz-cc test1.c -o test1_hongg $ <honggfuzz_root_dir>/hfuzz_cc/hfuzz-cc test2.c -o test2_hongg
As I did not want to wait for crashes, I created a dictionary for the fuzzers. Both AFL++ and honggfuzz use the same dictionary style, so I could use the same one for both fuzzers.
$ cat dict.txt "0" "1"
I provided an initial seed
$ cat in/1 in/2 a a1
Now all we have to do is start the fuzzers. In case of honggfuzz we need to specify that the input is read from stdin, and not from a file.
And soon the crashes came in:
$ <honggfuzz_root_dir>/honggfuzz -i in -o out -s -w dict.txt – test1_hongg ---------------------[ 0 days 00 hrs 00 mins 08 secs ]------------------- Iterations : 4,252 [4.25k] Mode [3/3] : Feedback Driven Mode Target : test1_hongg Threads : 2, CPUs: 4, CPU%: 228% [57%/CPU] Speed : 514/sec [avg: 531] Crashes : 707 [unique: 10, blacklist: 0, verified: 0] Timeouts : 0 [1 sec] Corpus Size : 86, max: 8,192 bytes, init: 2 files Cov Update : 0 days 00 hrs 00 mins 00 secs ago Coverage : edge: 22/23 [95%] pc: 0 cmp: 460
Honggfuzz writes out the crash files with some information, like which signal was raised by the software under test, the address of the current instruction, the AT&T disassembly of the instruction, and a call stack hash (more on this later). In this case, all values but the hash are the same.
'SIGSEGV.PC.55555557f9c0.STACK.18b0f71716.CODE.1.ADDR.0.INSTR.movl___$0x2a,(%rax).fuzz' 'SIGSEGV.PC.55555557f9c0.STACK.18b52f40d9.CODE.1.ADDR.0.INSTR.movl___$0x2a,(%rax).fuzz' 'SIGSEGV.PC.55555557f9c0.STACK.1933d5236e.CODE.1.ADDR.0.INSTR.movl___$0x2a,(%rax).fuzz' 'SIGSEGV.PC.55555557f9c0.STACK.1933f3f9f3.CODE.1.ADDR.0.INSTR.movl___$0x2a,(%rax).fuzz' 'SIGSEGV.PC.55555557f9c0.STACK.193e0eff27.CODE.1.ADDR.0.INSTR.movl___$0x2a,(%rax).fuzz' 'SIGSEGV.PC.55555557f9c0.STACK.1974293e64.CODE.1.ADDR.0.INSTR.movl___$0x2a,(%rax).fuzz' 'SIGSEGV.PC.55555557f9c0.STACK.1974db196b.CODE.1.ADDR.0.INSTR.movl___$0x2a,(%rax).fuzz' 'SIGSEGV.PC.55555557f9c0.STACK.197f31f9ce.CODE.1.ADDR.0.INSTR.movl___$0x2a,(%rax).fuzz' 'SIGSEGV.PC.55555557f9c0.STACK.19f2f296ab.CODE.1.ADDR.0.INSTR.movl___$0x2a,(%rax).fuzz' 'SIGSEGV.PC.55555557f9c0.STACK.19fd0c0c89.CODE.1.ADDR.0.INSTR.movl___$0x2a,(%rax).fuzz'
We run the same examle, but this time with AFL++.
$ <afl++_root_dir>/afl-fuzz -i in -o out -x dict.txt -- ./test1_afl
american fuzzy lop ++3.00a (default) [explore] {0}
┌─ process timing ────────────────────────────────┬─ overall results ────┐
│ run time : 0 days, 0 hrs, 0 min, 17 sec │ cycles done : 38 │
│ last new path : none yet (odd, check syntax!) │ total paths : 2 │
│ last uniq crash : 0 days, 0 hrs, 0 min, 17 sec │ uniq crashes : 10 │
│ last uniq hang : none seen yet │ uniq hangs : 0 │
├─ cycle progress ───────────────┬─ map coverage ─┴──────────────────────┤
│ now processing : 0.116 (0.0%) │ map density : 6.25% / 6.25% │
│ paths timed out : 0 (0.00%) │ count coverage : 1.00 bits/tuple │
├─ stage progress ───────────────┼─ findings in depth ───────────────────┤
│ now trying : MOpt-havoc │ favored paths : 1 (50.00%) │
│ stage execs : 0/256 (0.00%) │ new edges on : 1 (50.00%) │
│ total execs : 48.1k │ total crashes : 5158 (10 unique) │
│ exec speed : 2550/sec │ total tmouts : 0 (0 unique) │
├─ fuzzing strategy yields ──────┴───────────────┬─ path geometry ───────┤
│ bit flips : n/a, n/a, n/a │ levels : 1 │
│ byte flips : n/a, n/a, n/a │ pending : 0 │
│ arithmetics : n/a, n/a, n/a │ pend fav : 0 │
│ known ints : n/a, n/a, n/a │ own finds : 0 │
│ dictionary : n/a, n/a, n/a │ imported : 0 │
│havoc/splice : 10/48.1k, 0/0 │ stability : 100.00% │
│ py/custom : 0/0, 0/0 ├───────────────────────┘
│ trim : n/a, n/a │ [cpu000:100%]
└────────────────────────────────────────────────┘
+++ Testing aborted by user +++
[+] We're done here. Have a nice day!
AFL++ writes the crashes to the output directory. It also states the signal, in our case SIGILL. This is due to some optimizations done by clang.
$ ls out/default/crashes/ id:000000,sig:04,src:000000,time:3,op:havoc,rep:8 id:000001,sig:04,src:000000,time:15,op:havoc,rep:16 id:000002,sig:04,src:000000,time:29,op:havoc,rep:8 id:000003,sig:04,src:000000,time:33,op:havoc,rep:16 id:000004,sig:04,src:000000,time:53,op:havoc,rep:4 id:000005,sig:04,src:000000,time:58,op:havoc,rep:8 id:000006,sig:04,src:000000,time:80,op:havoc,rep:4 id:000007,sig:04,src:000000,time:123,op:havoc,rep:16 id:000008,sig:04,src:000000,time:171,op:havoc,rep:16 id:000009,sig:04,src:000000,time:293,op:havoc,rep:16
We run AFL++ against the second target:
$ <afl++_root_dir>/afl-fuzz -i in -o out2 -x dict.txt -- ./test1_afl2
american fuzzy lop ++3.00a (default) [explore] {0}
┌─ process timing ────────────────────────────────┬─ overall results ────┐
│ run time : 0 days, 0 hrs, 0 min, 19 sec │ cycles done : 15 │
│ last new path : none yet (odd, check syntax!) │ total paths : 2 │
│ last uniq crash : 0 days, 0 hrs, 0 min, 18 sec │ uniq crashes : 10 │
│ last uniq hang : none seen yet │ uniq hangs : 0 │
├─ cycle progress ───────────────┬─ map coverage ─┴──────────────────────┤
│ now processing : 0*131 (0.0%) │ map density : 8.33% / 8.33% │
│ paths timed out : 0 (0.00%) │ count coverage : 1.00 bits/tuple │
├─ stage progress ───────────────┼─ findings in depth ───────────────────┤
│ now trying : havoc │ favored paths : 1 (50.00%) │
│ stage execs : 227/256 (88.67%) │ new edges on : 1 (50.00%) │
│ total execs : 53.2k │ total crashes : 5571 (10 unique) │
│ exec speed : 2450/sec │ total tmouts : 0 (0 unique) │
├─ fuzzing strategy yields ──────┴───────────────┬─ path geometry ───────┤
│ bit flips : n/a, n/a, n/a │ levels : 1 │
│ byte flips : n/a, n/a, n/a │ pending : 0 │
│ arithmetics : n/a, n/a, n/a │ pend fav : 1 │
│ known ints : n/a, n/a, n/a │ own finds : 0 │
│ dictionary : n/a, n/a, n/a │ imported : 0 │
│havoc/splice : 10/53.0k, 0/0 │ stability : 100.00% │
│ py/custom : 0/0, 0/0 ├───────────────────────┘
│ trim : n/a, n/a │ [cpu000:125%]
└────────────────────────────────────────────────┘
+++ Testing aborted by user +++
[+] We're done here. Have a nice day!
And again the crashing input are written into the out folder. We can see that this time the signal is SIGABRT.
$ ls out/default/crashes/ id:000002,sig:06,src:000000,time:54,op:havoc,rep:8 id:000005,sig:06,src:000000,time:132,op:havoc,rep:16 id:000008,sig:06,src:000000,time:679,op:havoc,rep:16 id:000000,sig:06,src:000000,time:6,op:havoc,rep:16 id:000003,sig:06,src:000000,time:116,op:havoc,rep:16 id:000006,sig:06,src:000000,time:182,op:havoc,rep:16 id:000009,sig:06,src:000000,time:815,op:havoc,rep:16 id:000001,sig:06,src:000000,time:28,op:havoc,rep:8 id:000004,sig:06,src:000000,time:117,op:havoc,rep:8 id:000007,sig:06,src:000000,time:239,op:havoc,rep:8
And now we run honggfuzz on the second example:
$ <honggfuzz_root_dir>/honggfuzz -i in -o out -s -w dict.txt – test2_hongg ---------------------[ 0 days 00 hrs 00 mins 27 secs ]------------------- Iterations : 13,652 [13.65k] Mode [3/3] : Feedback Driven Mode Target : test2_hongg Threads : 2, CPUs: 4, CPU%: 237% [59%/CPU] Speed : 528/sec [avg: 505] Crashes : 2454 [unique: 1, blacklist: 0, verified: 0] Timeouts : 0 [1 sec] Corpus Size : 99, max: 8,192 bytes, init: 2 files Cov Update : 0 days 00 hrs 00 mins 05 secs ago Coverage : edge: 22/23 [95%] pc: 0 cmp: 474
We see that only one unique crash was identified. However, the same amount of edges has been covered.
Also, only one file gets written stating a SIGABRT happened.
'SIGABRT.PC.7ffff7c76615.STACK.e44f0733f.CODE.-6.ADDR.0.INSTR.mov____0x108(%rsp),%rax.fuzz'
The signal is consistent with AFL++, but why was only one crash reported and not ten like before? AFL and its derivates determine a crash’s uniqueness by checking if the same edges have been executed and resulted in a crash. If the same edges have been executed, it is the same crash. However, if other edges have been executed, it is a new crash. Honggfuzz chooses a different approach. When the crash happens, the stack frames are analyzed. Then a hash of the call stack is calculated. This hash, along with the other reported information, is used to determine the crash’s uniqueness.
Depending on our input, the call stack at the time of the crash in test1.c will be different. The caller is always in main, however, at a different line/address.
Here an example for test1.c at the time of the crash if a 0 was inputted. In the first section, we see that the current instruction is where the null pointer is dereferenced (rax is 0). In the next section, we see the expected signal, SIGSEGV. And then the backtrace with the “vuln” and “main” function. After that, we see the disassembly from the saved return address. In this case, the next if statement. Depending on the inputted number, this location will vary.
──────────────────────────────────────────────────────────── code:x86:64 ──── 0x55555555515a <vuln+1> mov rbp, rsp 0x55555555515d <vuln+4> mov QWORD PTR [rbp-0x8], 0x0 0x555555555165 <vuln+12> mov rax, QWORD PTR [rbp-0x8] → 0x555555555169 <vuln+16> mov DWORD PTR [rax], 0x2a 0x55555555516f <vuln+22> nop 0x555555555170 <vuln+23> pop rbp 0x555555555171 <vuln+24> ret 0x555555555172 <main+0> push rbp 0x555555555173 <main+1> mov rbp, rsp ──────────────────────────────────────────────────────────────── threads ──── [#0] Id 1, Name: "test1", stopped 0x555555555169 in vuln (), reason: SIGSEGV ────────────────────────────────────────────────────────────────── trace ──── [#0] 0x555555555169 → vuln() [#1] 0x5555555551ca → main() ───────────────────────────────────────────────────────────────────────────── gef➤ x/8i 0x5555555551dc 0x5555555551dc <main+106>: movzx eax,BYTE PTR [rbp-0x70] 0x5555555551e0 <main+110>: cmp al,0x32 0x5555555551e2 <main+112>: jne 0x5555555551ee <main+124> 0x5555555551e4 <main+114>: mov eax,0x0 0x5555555551e9 <main+119>: call 0x555555555159 <vuln> 0x5555555551ee <main+124>: movzx eax,BYTE PTR [rbp-0x70] 0x5555555551f2 <main+128>: cmp al,0x33 0x5555555551f4 <main+130>: jne 0x555555555200 <main+142>
The next snippet shows the same but for example2.c
──────────────────────────────────────────────────────────── code:x86:64 ──── 0x7ffff7e09609 <raise+313> mov edi, 0x2 0x7ffff7e0960e <raise+318> mov eax, 0xe 0x7ffff7e09613 <raise+323> syscall → 0x7ffff7e09615 <raise+325> mov rax, QWORD PTR [rsp+0x108] 0x7ffff7e0961d <raise+333> sub rax, QWORD PTR fs:0x28 0x7ffff7e09626 <raise+342> jne 0x7ffff7e0964c <raise+380> 0x7ffff7e09628 <raise+344> mov eax, r8d 0x7ffff7e0962b <raise+347> add rsp, 0x118 0x7ffff7e09632 <raise+354> ret ──────────────────────────────────────────────────────────────── threads ──── [#0] Id 1, Name: "test2", stopped 0x7ffff7e09615 in raise (), reason: SIGABRT ────────────────────────────────────────────────────────────────── trace ──── [#0] 0x7ffff7e09615 → raise() [#1] 0x7ffff7df2862 → abort() [#2] 0x7ffff7e4b5e8 → __libc_message() [#3] 0x7ffff7e5327a → malloc_printerr() [#4] 0x7ffff7e54d4c → _int_free() [#5] 0x5555555552a0 → main() ───────────────────────────────────────────────────────────────────────────── gef➤ x/8i 0x5555555552a0 - 5 0x55555555529b <main+279>: call 0x555555555030 <free@plt> 0x5555555552a0 <main+284>: mov eax,0x0 0x5555555552a5 <main+289>: mov rcx,QWORD PTR [rbp-0x8] 0x5555555552a9 <main+293>: sub rcx,QWORD PTR fs:0x28 0x5555555552b2 <main+302>: je 0x5555555552b9 <main+309> 0x5555555552b4 <main+304>: call 0x555555555040 <__stack_chk_fail@plt> 0x5555555552b9 <main+309>: leave 0x5555555552ba <main+310>: ret
The interesting part is the backtrace. We see that the execution currently is not in our program but in libc. This happened because a double-free was detected, and the abort signal was sent. All inputs that result in a crash will result in the same stack hash as the caller is always at the same location in test2.c.
It should be noted that in this case, the examples were contrived such that the vulnerabilities were simple to detect. This blogpost should not serve as a reference to which approach is better but show the differences. The key takeaway is that it is crucial to understand how the tool you’re using defines a unique crash and what that means for you and your workflow. For example, using AFL++’s numbers of unique crashes as a performance metric is not a good idea! Test1.c shows this problem. The actual bug is independent of the input data; the input does not affect the vulnerability itself. It is either reached or not reached, depending on the input. Some more in-depth thoughts can be found in the paper “Evaluating Fuzz Testing” in section 7.
The approach of using a stack hash to bucket crashes is also used by the GDB exploitable plugin. Bucketing a large number of crashes by hand with exploitable is still very tedious. Crashwalk can be used to automate the process.
Example exploitable report for a crashing input from test1.c.
gef➤ exploitable Description: Access violation near NULL on destination operand Short description: DestAvNearNull (15/22) Hash: 192eeaee244138417ff835e27c990c6b.192eeaee244138417ff835e27c990c6b Exploitability Classification: PROBABLY_EXPLOITABLE Explanation: The target crashed on an access violation at an address matching the destination operand of the instruction. This likely indicates a write access violation, which means the attacker may control write address and/or value. However, it there is a chance it could be a NULL dereference. Other tags: AccessViolation (21/22)
Example exploitable report for a crashing input from test2.c
gef➤ exploitable Description: Heap error Short description: HeapError (10/22) Hash: b8bcf58d80d4661d053ccce18fc289df.0621a1ede1a407427f691584eab16c9f Exploitability Classification: EXPLOITABLE Explanation: The target's backtrace indicates that libc has detected a heap error or that the target was executing a heap function when it stopped. This could be due to heap corruption, passing a bad pointer to a heap function such as free(), etc. Since heap errors might include buffer overflows, use-after-free situations, etc. they are generally considered exploitable. Other tags: AbortSignal (20/22)
Let’s take a quick look at crashwalk. Crashwalk internally uses the GDB exploitable plugin, but it enriches it with further information like registers. It saves the observed crashes into a database (crashwalk.db)
The next section shows crashwalk against the crashes found by AFL++ in test1.c
$ go run <crashwalk_root>/cmd/cwtriage/main_unix.go -root out/default/crashes -- ./test1 [...] --------- ---CRASH SUMMARY--- Filename: […]/out/default/crashes/id:000000,sig:04,src:000000,time:3,op:havoc,rep:8 SHA1: 17ba0791499db908433b80f37c5fbc89b870084b Classification: PROBABLY_EXPLOITABLE Hash: 192eeaee244138417ff835e27c990c6b.192eeaee244138417ff835e27c990c6b Command: ./test1 -in Faulting Frame: vuln @ 0x0000555555555169: in […]/test1 Disassembly: Stack Head (2 entries): vuln @ 0x0000555555555169: in /[…]/test1 main @ 0x00005555555551dc: in /[…] /test1 Registers: rax=0x0000000000000000 rbx=0x0000000000000000 rcx=0x0000000000001000 rdx=0x0000000000000000 rsi=0x00007fffffffe000 rdi=0x00007ffff7f914f0 rbp=0x00007fffffffdfe0 rsp=0x00007fffffffdfe0 r8=0x0000000000000003 r9=0x00007ffff7f8ea60 r10=0x0000000000000070 r11=0x0000000000000000 r12=0x0000555555555060 r13=0x0000000000000000 r14=0x0000000000000000 r15=0x0000000000000000 rip=0x0000555555555169 efl=0x0000000000010246 cs=0x0000000000000033 ss=0x000000000000002b ds=0x0000000000000000 es=0x0000000000000000 fs=0x0000000000000000 gs=0x0000000000000000 Extra Data: Description: Access violation near NULL on destination operand Short description: DestAvNearNull (15/22) Explanation: The target crashed on an access violation at an address matching the destination operand of the instruction. This likely indicates a write access violation, which means the attacker may control write address and/or value. However, it there is a chance it could be a NULL dereference. ---END SUMMARY--- [...]
After triaging the crashes in the out folder for test2.c, let’s compare the two databases.
$ go run <crashwalk_root>/cmd/cwdump/main.go crashwalk1.db (1 of 1) - Hash: 981a4f6be138dbeb754554b6a8e3f7e1.981a4f6be138dbeb754554b6a8e3f7e1 ---CRASH SUMMARY--- [...] ---END SUMMARY--- (1 of 1) - Hash: f0b15920caafa302edf704ff722aeb8e.f0b15920caafa302edf704ff722aeb8e ---CRASH SUMMARY--- [...]
$ go run <crashwalk_root>/cmd/cwdump/main.go crashwalk2.db (1 of 10) - Hash: b8bcf58d80d4661d053ccce18fc289df.0621a1ede1a407427f691584eab16c9f
In the case of test1.c Crashwalk identified ten different crashes that need further inspection, in the case of test2.c it identified ten occurrences of the same crash.
Once the crashes have been categorized and bucketed, the unique crashes can be analyzed in more detail. Further information about the vulnerabilities in test2.c can, for example, be obtained with Adress Sanitizer (ASan), or in the case of black-box binaries Valgrind, dr memory, or custom tools.
To illustrate this, we compile the binary with ASan.
$ clang -fsanitize=address test2.c -o test2_asan
Now we execute the binary and provide a crashing input:
$ ./test2_asan 1 ================================================================= ==64246==ERROR: AddressSanitizer: attempting double-free on 0x60c000000040 in thread T0: #0 0x555b5672c059 in free (/[...]/test2_asan+0xc5059) #1 0x555b567625fa in main (/[...]//test2_asan+0xfb5fa) #2 0x7f10b12a8151 in __libc_start_main (/usr/lib/libc.so.6+0x28151) #3 0x555b5668619d in _start (/[...]/test2_asan+0x1f19d) 0x60c000000040 is located 0 bytes inside of 128-byte region [0x60c000000040,0x60c0000000c0) freed by thread T0 here: #0 0x555b5672c059 in free (/[...]/test2_asan+0xc5059) #1 0x555b56762134 in vuln (/[...]/test2_asan+0xfb134) #2 0x555b56762369 in main (/[...]/test2_asan+0xfb369) #3 0x7f10b12a8151 in __libc_start_main (/usr/lib/libc.so.6+0x28151) previously allocated by thread T0 here: #0 0x555b5672c389 in malloc (/[...]/test2_asan+0xc5389) #1 0x555b567622c3 in main (/[...]/test2_asan+0xfb2c3) #2 0x7f10b12a8151 in __libc_start_main (/usr/lib/libc.so.6+0x28151) SUMMARY: AddressSanitizer: double-free (/[...]/test2_asan+0xc5059) in free ==64246==ABORTING
ASan reports the double free and provides information about the call to free that caused the double-free; however, we also get information about the first call to free. This enables us to work faster on a fix.
Similar information can be obtained with Valgrind. However, Valgrind does not require source access.
$ valgrind --tool=memcheck ./test2 ==64286== Memcheck, a memory error detector ==64286== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al. ==64286== Using Valgrind-3.16.1 and LibVEX; rerun with -h for copyright info ==64286== Command: ./test2 ==64286== 1 ==64286== Invalid free() / delete / delete[] / realloc() ==64286== at 0x483B9AB: free (vg_replace_malloc.c:538) ==64286== by 0x10929F: main (in /[...]/test2) ==64286== Address 0x4a47040 is 0 bytes inside a block of size 128 free'd ==64286== at 0x483B9AB: free (vg_replace_malloc.c:538) ==64286== by 0x109180: vuln (in /[...]/test2) ==64286== by 0x1091F3: main (in /[...]/test2) ==64286== Block was alloc'd at ==64286== at 0x483A77F: malloc (vg_replace_malloc.c:307) ==64286== by 0x1091C7: main (in /[...]/test2) ==64286== ==64286== ==64286== HEAP SUMMARY: ==64286== in use at exit: 0 bytes in 0 blocks ==64286== total heap usage: 1 allocs, 2 frees, 128 bytes allocated ==64286== ==64286== All heap blocks were freed -- no leaks are possible ==64286== ==64286== For lists of detected and suppressed errors, rerun with: -s ==64286== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
If you are interested in reading more about a workflow from initial attack surface identification to fuzzing and triaging a target. I recommend a writeup (source code) from @niklasb where he found exploitable bugs in CS:GO for RealWorldCTF 2018. For bucketing, he used a GDB script that determines the uniqueness of crashes with a call stack hash. He then used Valgrind to distinguish between invalid reads and writes.
In an upcoming blogpost, we will take a look at root-causing crashes in a real world target with GDB and rr.