-
-
[翻译]fuzzer开发4:快照、代码覆盖率与模糊测试
-
发表于: 2024-9-8 14:14 7017
-
背景
这是关于一个快照模糊测试器开发过程的系列博文的下一篇,旨在利用 Bochs 作为目标执行引擎。你可以在 Lucid 仓库中找到模糊测试器及其代码。
介绍
在之前的文章中,我们实现了足够的 Linux 仿真逻辑,使得 Lucid 能够运行一个 -static-pie
的 Bochs 直到其启动菜单。自那之后的几个月里,我们取得了很多进展。我们现在已经实现了快照、代码覆盖反馈以及更多的 Linux 仿真逻辑,现在我们实际上可以开始模糊测试了!因此,在这篇文章中,我们将回顾一些代码库中新添加的主要功能,并提供一些关于如何设置模糊测试器进行模糊测试的示例。
快照
这个模糊测试器设计的一个关键优势(感谢 Brandon Falk)是,被模拟或目标系统的整个状态完全由 Bochs 封装。其吸引力在于,如果我们能够可靠地记录和重置 Bochs 的状态,我们就可以默认获得目标快照。未来,当我们的目标程序影响设备状态时(例如模糊测试一个网络服务),这将对我们有很大帮助。那么现在的问题是,在 Linux 上,我们如何完美地记录和重置进程的状态?
我想到的解决方案,我认为非常美观。我们需要重置 Bochs 中的以下状态:
- Bochs 映像本身的任何可写的 PT_LOAD 内存段
- Bochs 的文件表
- Bochs 的动态内存,如堆分配
- Bochs 的扩展 CPU 状态:AVX 寄存器、浮点单元等
- Bochs 的寄存器
首先,动态内存应该比较容易记录,因为我们在模糊测试器的系统调用仿真代码中自己处理了所有对 mmap
的调用。因此,我们可以很容易地通过这种方式对 MMU 状态进行快照。这也适用于文件表,因为我们以相同的方式控制所有文件 I/O。不过目前,我还没有实现文件表快照,因为在我用于开发的模糊测试工具中,Bochs 不会触及任何文件。当前,我的解决办法是将文件标记为“脏”,如果我们在模糊测试时访问了这些文件,我会在那时让系统崩溃。以后,我们应该能够像处理 MMU 一样处理文件快照。
扩展的 CPU 状态可以通过机器指令保存。
然而,我一直在思考的问题是如何记录和重置 PT_LOAD 段。我们无法很好地跟踪这些页面在 Linux 用户空间中的修改,因为它们是在本机发生的。不过,在模糊测试领域,如果你想差异性地恢复这些页面,有一些常见的解决方法:
- 将这些页面标记为不可写,并处理每个页面的写访问故障。这样做可以让你知道 Bochs 是否使用了可写页面。一旦处理了故障,你可以永久地将页面标记为可写,然后在每次模糊测试迭代中懒惰地重置它。
- 使用
/proc
中为类似 Checkpoint Restore 提供的工具,如 d0c s4vage 讨论的那样。
不过,最终为了简化起见,我决定每次都重置所有的可写段。
真正的问题是,Bochs 的动态内存分配可能非常庞大,因为它会分配堆内存来保存被模拟的来宾内存(即你的目标系统)。因此,如果你配置了一个具有 2GB 内存的来宾虚拟机,Bochs 将尝试进行一个 2GB 的堆分配。这使得捕获和恢复快照变得非常昂贵,因为每次模糊测试迭代都要进行 2GB 的 memcpy
操作,这将非常耗费成本。因此,我需要找到一种避免这种情况的方法。Bochs 确实有内存访问钩子,因此我可以通过这种方式跟踪来宾中的脏内存。如果我们发现当前的实现成为性能瓶颈,这可能是未来的一个实现方向。
根据我目前对 Lucid 项目的设计哲学,即我们可以为了更好的内省或架构/实现的简单性而牺牲性能,我决定有一个不错的解决方案可以利用,因为我们是将 Bochs 映射到内存中的,而不是由内核处理。只要 ELF 映像的可加载段是按顺序加载的,并且可写段最后加载,这意味着我们开始了一个需要重置的内存块。此时,你可以将内存中的映射视为这样的结构:
1
2
3
4
5
|
| - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - |
| Non - Writable ELF Segments |
| - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - | < - - Start of memory that we need to record and restore
| Writable ELF Segments | | - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - |
|
这对我们来说很有利,因为我们现在实际上有了一块需要在每次模糊测试迭代时恢复的连续的可写内存块。Bochs 会影响的其他我们关心的可变内存可以任意映射,让我们来思考一下:
-
Bochs 的扩展状态保存区:是的,我们控制这个区域的映射位置,我们可以通过
mmap
和MAP_FIXED
将其直接映射到最后一个可写的 ELF 段旁边。现在我们的连续内存块也包含了扩展状态。 - MMU 动态内存(Brk, Mmap):是的,我们也控制这一块,因为我们预先分配了动态内存,然后使用这些系统调用作为基本的“递增分配器”API,所以这也成了我们连续内存块的一部分。
因此,现在我们可以将需要快照的整个内存块概念化为:
1
2
3
4
5
6
7
8
9
|
| - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - |
| Non - Writable ELF Segments |
| - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - | < - - Start of memory that we need to record and restore
| Writable ELF Segments | | - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - |
| Bochs Extended CPU State | | - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - |
| Bochs MMU / Brk Pool |
| - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - | < - - End of memory that we need to record and restore
|
为什么我们关心可写内存是这样紧凑和连续的?我们仍然面临一个问题,即 MMU/Brk 内存池太大,无法在每次模糊测试迭代时进行一次巨大的 memcpy
。我们的解决方案要么使用差异性重置(即只重置脏页),要么找到一种新的方法进行整体恢复,因为 memcpy
并不足够。
为了保持简单,我决定使用一种有效的方法,利用连续内存的概念来重置整个内存块,而不依赖于 memcpy
。我们可以使用 Linux 的共享内存对象来缓存模糊测试期间的快照内容,这些对象是通过 libc::shm_open
分配的。这基本上就像打开了一个由共享内存支持的文件,因此在每次快照恢复时,我们实际上不会触发任何磁盘读取或昂贵的文件 I/O。
接下来,当我们需要恢复时,我们可以简单地将这个“文件”通过 mmap
覆盖在脏的连续内存块上。它们大小相同,对吧?而且我们控制连续内存块的位置,所以这使得重置脏内存变得非常容易!代码基本上就是这样:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
// This function will take the saved data in the shm object and just mmap it // overtop of the writable memory block to restore the memory contents #[inline] fn restore_memory_block(base: usize, length: usize, fd: i32) -> Result<(), LucidErr> {
// mmap the saved memory contents overtop of the dirty contents
let result = unsafe {
libc::mmap(
base as *mut libc::c_void,
length,
libc::PROT_READ | libc::PROT_WRITE,
libc::MAP_PRIVATE | libc::MAP_FIXED,
fd,
0
)
};
if result == libc::MAP_FAILED || result != base as *mut libc::c_void {
return Err(LucidErr::from( "Failed to mmap restore snapshot" ));
}
Ok(())
} |
你只需要共享内存对象的文件描述符,就可以执行内存内容的恢复。在我的相对较旧的 CPU 和 VMWare 虚拟机中,我大约每秒能够重置这个内存块 18,000 次,这对于像 Lucid 这样的模糊测试器来说绝对够快了,因为瓶颈几乎肯定会出现在目标仿真代码上。不过,这并不意味着我们将来不会遇到问题。使用这种方法时,内核在销毁那些 mmap
覆盖了但不再需要的页面时会花费大量时间,如果我们未来扩大模糊测试规模,这可能会成为瓶颈。时间会证明一切。目前,我非常喜欢这种方法的简单和易用性。特别感谢 Dominik Maier 和模糊测试 Discord 社区的其他人帮助我完善了这个想法。
除此之外,这种方法的第二个重要优势就是性能相对稳定,无论内存块大小如何。我们利用了 Linux 内核的多种高效内存管理优化,不再因为 2GB 的 memcpy
操作而减慢速度。以我当前的设置(分配了 64MB 的来宾内存)来看,这种共享内存加 mmap
的方法比单纯的巨型 memcpy
快了大约 10 倍。我们从在快照恢复代码中花费 13% 的 CPU 时间提升到使用 memcpy
时的 96%。因此,当前对我们来说效果很好。
关于快照恢复的其他一些小细节,我们可以“克隆”一个现有的 MMU,比如我们在记录快照时保存的那个,通过类似这样简单的操作将其复制到当前(脏)的 MMU:
1
2
3
4
5
6
7
8
9
10
11
12
|
// Copy the contents of an existing MMU, used for snapshot restore pub fn restore(&mut self, mmu: &Mmu) {
self.map_base = mmu.map_base;
self.map_length = mmu.map_length;
self.brk_base = mmu.brk_base;
self.brk_size = mmu.brk_size;
self.curr_brk = mmu.curr_brk;
self.mmap_base = mmu.mmap_base;
self.mmap_size = mmu.mmap_size;
self.curr_mmap = mmu.curr_mmap;
self.next_mmap = mmu.next_mmap;
}
|
我们还需要处理 Bochs 的通用寄存器(GPRs),幸运的是,当 Bochs 切换上下文到 Lucid 以进行快照时,这些寄存器已经被保存了。
触发快照操作
接下来我们需要做的是确定如何从来宾运行的 harness 中调用快照逻辑。我决定借用 Bochs 的方法,利用特定类型的 NOP 指令序列,这些序列在目标程序中不太可能出现(碰撞的可能性很低)。Bochs 使用这些类型的 NOP 作为使用 Bochs 调试模式编译时的魔法断点。它们如下:
1
2
3
4
5
6
7
|
66:87C9 | xchg cx,cx | 1000011111 001 001 -> 1 66:87D2 | xchg dx,dx | 1000011111 010 010 -> 2 66:87DB | xchg bx,bx | 1000011111 011 011 -> 3 66:87E4 | xchg sp,sp | 1000011111 100 100 -> 4 66:87ED | xchg bp,bp | 1000011111 101 101 -> 5 66:87F6 | xchg si,si | 1000011111 110 110 -> 6 66:87FF | xchg di,di | 1000011111 111 111 -> 7 |
这段代码位于 bochs/cpu/data_xfer16.cc
文件中。bxInstruction_c
结构体有处理这类操作的字段,跟踪源寄存器和目标寄存器。如果它们相同,它会根据指令编码中的二进制表示进行检查。例如,xchg dx, dx
表示 i->src()
和 i->dst()
都等于 2。
因此,在这个指令处理程序中,我们已经有了一个示例,说明如何实现逻辑,让 Bochs 识别来宾中的指令并执行某些操作。
我们实际上有两种快照。一种是使用带有图形用户界面的普通版本的 Bochs 时,我们的目标是将 Bochs 的状态“快照”到磁盘上,以便从那里开始模糊测试。这与模糊测试器构思的快照不同。例如,如果你像我一样构建了一个 harness,你可能会希望使用带有 GUI 的 Bochs 启动系统,获取一个 shell,然后运行你的 harness。你的 harness 可以触发这些魔法断点之一,让 Bochs 将其状态保存到磁盘上,这就是我所做的。
Bochs 具有在用户使用“暂停”功能时将其状态保存到磁盘的能力,就像暂停一个虚拟机一样。然后 Bochs 可以在将来恢复该暂停的虚拟机,这显然是一个很棒的功能。我们可以利用这一点,将这段代码从 GUI 模拟接口代码中复制粘贴到指令处理程序中。我所做的只是为 data_xfer16.cc
添加了一个额外的 include,然后像下面这样加入我的逻辑:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#if BX_SNAPSHOT // Check for take snapshot instruction `xchg dx, dx`
if ((i->src() == i->dst()) && (i->src() == 2)) {
BX_COMMIT_INSTRUCTION(i);
if (BX_CPU_THIS_PTR async_event)
return ;
++i;
char save_dir[] = "/tmp/lucid_snapshot" ;
mkdir(save_dir, 0777);
printf ( "Saving Lucid snapshot to '%s'...\n" , save_dir);
if (SIM->save_state(save_dir)) {
printf ( "Successfully saved snapshot\n" );
sleep(2);
exit (0);
}
else {
printf ( "Failed to save snapshot\n" );
}
BX_EXECUTE_INSTRUCTION(i);
}
#endif |
因此,如果我们构建一个带 GUI 的普通 Bochs,并在构建过程中定义了 BX_SNAPSHOT
,当 Bochs 遇到 xchg dx, dx
指令时,它应该能够将其状态保存到磁盘上,就像终端用户在我们的 harness 中完美时刻按下了暂停按钮一样。
在模糊测试器中
我们将告诉 Bochs 恢复之前保存到磁盘的状态,并在它即将仿真 CPU 循环中的第一条指令时,返回到模糊测试器,并进行我们在上一节中讨论的快照。这是通过在 cpu/cpu.cc
中加入一些代码实现的,如下所示:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
jmp_buf BX_CPU_C::jmp_buf_env;
void BX_CPU_C::cpu_loop( void )
{ #if BX_SUPPORT_HANDLERS_CHAINING_SPEEDUPS volatile Bit8u stack_anchor = 0;
BX_CPU_THIS_PTR cpuloop_stack_anchor = &stack_anchor;
#endif #if BX_DEBUGGER BX_CPU_THIS_PTR break_point = 0;
BX_CPU_THIS_PTR magic_break = 0;
BX_CPU_THIS_PTR stop_reason = STOP_NO_REASON;
#endif // Place the Lucid snapshot taking code here above potential long jump returns #if BX_LUCID lucid_take_snapshot();
#endif if ( setjmp (BX_CPU_THIS_PTR jmp_buf_env)) {
// can get here only from exception function or VMEXIT
BX_CPU_THIS_PTR icount++;
BX_SYNC_TIME_IF_SINGLE_PROCESSOR(0);
#if BX_DEBUGGER || BX_GDBSTUB if (dbg_instruction_epilog()) return ;
#endif #if BX_GDBSTUB if (bx_dbg.gdbstub_enabled) return ;
#endif }
|
可以看到,如果我们为模糊测试器构建 Bochs(定义了 BX_LUCID
),我们将在开始仿真指令之前或通过 longjmp
或类似逻辑返回异常之前调用 take_snapshot
函数。take_snapshot
代码的逻辑非常简单,我们只需在全局执行上下文中设置一些变量,让 Lucid 知道我们为什么退出虚拟机以及应该对此做些什么:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
// Call into Lucid to take snapshot of current Bochs state __attribute__((optimize(0))) void lucid_take_snapshot( void ) {
if (!g_lucid_ctx)
return ;
// Set execution mode to Bochs
g_lucid_ctx->mode = BOCHS;
// Set the exit reason
g_lucid_ctx->exit_reason = TAKE_SNAPSHOT;
// Inline assembly to switch context back to fuzzer
__asm__ (
"push %%r15\n\t" // Save r15 register
"mov %0, %%r15\n\t" // Move context pointer into r15
"call *(%%r15)\n\t" // Call context_switch
"pop %%r15" // Restore r15 register
: // No output
: "r" (g_lucid_ctx) // Input
: "memory" // Clobber
);
return ;
} |
现在 Lucid 可以将此状态保存为快照,并在每次模糊测试迭代后重置到此状态。所有这些仅仅是通过在你的模糊测试 harness 中包含一个简单的 xchg dx, dx
指令,非常酷!在一个 fuzzcase 结束时,当我们重置快照状态并希望从快照状态重新开始执行 Bochs 时,我们只需通过上下文切换调用此函数,以一个简单的 ret
指令结束。这将表现得就像 Bochs 正常从调用 lucid_take_snapshot
函数返回一样:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
// Restore Bochs' state from the snapshot fn restore_bochs_execution(contextp: *mut LucidContext) { // Set the mode to Bochs
let context = LucidContext::from_ptr_mut(contextp);
context.mode = ExecMode::Bochs;
// Get the pointer to the snapshot regs
let snap_regsp = context.snapshot_regs_ptr();
// Restore the extended state
context.restore_xstate();
// Move that pointer into R14 and restore our GPRs
unsafe {
asm!(
"mov r14, {0}" ,
"mov rax, [r14 + 0x0]" ,
"mov rbx, [r14 + 0x8]" ,
"mov rcx, [r14 + 0x10]" ,
"mov rdx, [r14 + 0x18]" ,
"mov rsi, [r14 + 0x20]" ,
"mov rdi, [r14 + 0x28]" ,
"mov rbp, [r14 + 0x30]" ,
"mov rsp, [r14 + 0x38]" ,
"mov r8, [r14 + 0x40]" ,
"mov r9, [r14 + 0x48]" ,
"mov r10, [r14 + 0x50]" ,
"mov r11, [r14 + 0x58]" ,
"mov r12, [r14 + 0x60]" ,
"mov r13, [r14 + 0x68]" ,
"mov r15, [r14 + 0x78]" ,
"mov r14, [r14 + 0x70]" ,
"sub rsp, 0x8" , // Recover saved CPU flags
"popfq" ,
"ret" ,
in(reg) snap_regsp,
);
}
} |
我觉得快照的部分基本上就是这样了,挺好奇它们未来的表现,不过现在它们已经起作用了。
代码覆盖反馈
在快照功能完成后,我开始实现代码覆盖反馈功能。起初,由于通过 Bochs 能访问所有内容,选项繁多让我有些不知所措。我们知道在每次模糊测试迭代中执行的每一个程序计数器(PC),所以理论上我们可以做任何想做的事情。最终,我实现了一个与老式 AFL 类似的方案,跟踪两级代码覆盖率:
-
边缘对(Edge pairs):这些是发生分支的地址。例如,如果地址为
0x1337
的指令是jmp 0x13371337
,那么我们将跟踪一个由0x1337
和0x13371337
组成的边缘对。基本上,我们跟踪当前的 PC 和跳转到的 PC。这同样适用于未采取分支的情况,因为我们会跳过分支指令并转到新指令,这本质上也是一种分支。 - 边缘对频率:我们还想知道在一次模糊测试迭代中这些边缘对被访问的频率。因此,不仅仅是“边缘对是否被看到”的二元信息,我们还想区分在一次模糊测试迭代中某个输入命中某个边缘对 100 次与命中 100000 次的差异。这种额外的细化信息应该能为我们提供比简单的边缘命中与否更有价值的反馈。
在考虑了这两级内省之后,我们需要选择实现方式。幸运的是,我们可以通过 instrument/stubs/instrument.cc
暴露的存根编译 Bochs 进行插桩。一些存根对我们特别有用,因为它们为分支指令插桩。因此,如果你在编译 Bochs 时定义了 BX_INSTRUMENTATION
,这些存根将被编译到来宾的分支指令处理程序中。它们的原型记录了当前的 PC 和目标 PC。我不得不对条件分支未采取的插桩存根的签名做了一些修改,因为它没有跟踪可能被采取的 PC,而我们需要该信息来形成边缘对。以下是修改前后的存根逻辑:
1
2
|
void bx_instr_cnear_branch_taken(unsigned cpu, bx_address branch_eip, bx_address new_eip) {}
void bx_instr_cnear_branch_not_taken(unsigned cpu, bx_address branch_eip) {}
|
然后我将它们改为:
1
2
|
void bx_instr_cnear_branch_taken(unsigned cpu, bx_address branch_eip, bx_address new_eip) {}
void bx_instr_cnear_branch_not_taken(unsigned cpu, bx_address branch_eip, bx_address new_eip) {}
|
因此,我不得不遍历并更改指令处理程序中的所有宏调用,以便为 bx_instr_cnear_branch_not_taken
计算一个新的 taken
PC,这虽然有点麻烦,但对于在别人的项目上做修改来说,还是很简单的。以下是 Bochs 补丁文件中我在调用点所做的更改的示例,你可以看到我必须计算一个新的变量 bx_address taken
来获取一个对:
1
2
3
|
- BX_INSTR_CNEAR_BRANCH_NOT_TAKEN(BX_CPU_ID, PREV_RIP); + bx_address taken = PREV_RIP + i->ilen(); + BX_INSTR_CNEAR_BRANCH_NOT_TAKEN(BX_CPU_ID, PREV_RIP, taken); |