简介

传统模糊测试能快速探索输入空间, 但无法很好地进入深层空间, 而混合执行则擅长深层空间的状态但难以解决复杂的约束. 混合模糊测试则是将两者结合在一起, 而作者认为混合执行引擎的性能瓶颈时制约混合模糊测试的主要因素, 而论文的解决性能瓶颈的方法就是将符号执行的部分通过动态二进制翻译(DBT)的方案转变成本地执行, 同时相对现有的混合执行引擎而言, 也能实现更细粒度的指令级别执行. 此外也降低了健壮性的一些要求使其性能更高, 能应用于大规模测试.

动机: 性能瓶颈

P1. 符号执行开销

论文探讨了符号执行低效的原因: 首先符号执行对IR的依赖降低了性能, 其次针对IR的优化器没有充分地进行优化(限制了优化空间), 特别是将程序翻译成基本块级别IR这部分. 最后是没法跳过不涉及符号执行的那部分指令.

IR能够降低原型实现的复杂度, 但同时也带来了额外的开销. 比如amd64架构指令是CISC, 而IR是RISC, 在转换过程中一条机器指令就会被转化成多条IR, 从实验结果来看, Angr使用的VEX IR则平均膨胀了4.69倍.

IR优化器有自己的一些优化策略, 比如不涉及符号变量的基本块就不进行符号执行, 这确实能提高性能但不充分, 因为对于含有符号变量的基本块, 从真实软件测试来看, 只有约30%的指令需要符号执行. 也就意味着指令级别的符号执行能减少不必要的符号执行开销. 但现有的混合执行引擎因为IR缓存策略, 常常以基本块为单位转换成IR以降低缓存的成本, 因此没有从基本块级别上做优化.

论文则是以此出发, 移除了IR转换, 增加实现复杂性, 和尽可能最小化符号执行的使用.

P2. 低效的快照

传统混合执行引擎使用快照来减少重新执行目标程序的开销, 但对于一些混合执行引擎来说快照机制是必要的, 例如Driller. 传统符号执行需要快照来保存分支的探索状态, 而对于混合模糊测试中的混合符号执行引擎, 则是从从Fuzzer处拿测试样例, 而这些样例的路径很可能是不同的, 因此也就没有必要使用快照来保存分支状态.

同时快照机制需要频繁地与外部环境比如文件系统和内存管理系统交互, 但当进程通过fork族的系统调用创建子进程时, 内核不再维护其状态, 因此混合执行引擎需要自行维护状态.

快照机制还会有其他的问题, 论文中则对重复的混合执行进行优化, 移除了快照机制, 取而代之使用具体执行.

P3. 低效不灵活的健壮性分析

混合执行会试图收集完整的约束来保证健壮性, 确保满足约束的输入能引导到预期路径. 然而计算完整约束的代价可能非常昂贵. 比如一些密码学或解压的函数, 强求完整约束会使得其没法探索其他有趣的代码. 此外过度约束也会带来计算开销.

论文里则是收集不完整的部分约束, 并针对过度约束情况仅求解其部分约束.

设计

QSYM的设计架构如下图所示:

优化混合执行引擎

使用了四种技术来对混合执行引擎进行优化.

  1. 指令级别的符号执行: 使用DBT在单个进程允许本地和符号执行, 使得其模式的切换开销非常小
  2. 只求解相关约束: 只求解跟目标分支相关的约束并产生新的测试样例. 传统符号执行引擎例如S2E和Driller会逐步求解约束, 并关注于通过前段执行解决当前执行中约束的最新部分, 而这对于没有初始输入可供探索的符号执行器而言是非常有效的. 但并不适用于混合执行. QSYM相比Driller在输出测试样例能够仅修改跟分支相关的约束. 但这里对QSYM的输出没有很好的解释.
  3. 更多使用重新执行而非快照: 重新执行程序到达特定路径状态的开销可能比快照恢复要高的多, 但当QSYM的混合执行引擎变快, 快照恢复的开销会高于重新执行.
  4. 具体的外部环境: 不再对外部环境进行建模而是与具体的外部环境进行交互, 将外部环境视为黑盒给予具体值运行, 这是处理那些无法模拟的函数的常用手段, 但很难适用于给予fork的符号执行, 因为这会打破进程边界. QSYM做了折衷的方案, 损失一定的健壮性, 通过Fuzzer来快速检查及丢弃测试用例来停止进一步的分析.

优化求解器

混合执行容易遇到过度求解的问题. QSYM通过求解最后一条路径约束来达到提速的目的, 这样有两点考虑, 一是乐观地认为最后一条约束通常具有比较简单的形式, 能很高效地进行约束求解(作者也有考虑过求unsat_core的补集, 但其也是计算高昂), 二是求解最后一条约束, 能保证后续的约束求解结果也一定满足这最后一条到底该分支的约束.

修剪基本块

重复代码生成的约束对于实际测试中查找新的代码覆盖率没有帮助, 并且有的时候会因为复杂的基本块带来的约束限制了进一步的探索.

QSYM会在运行时测量每一个基本块执行的频率, 并选择重复的基本块进行修剪. 如果基本块执行的过于频繁, 则会放弃从该基本块生成进一步的约束. 当然除开那些不引入任何新符号表达式的常量指令组成的基本块, 例如x86的mov指令以及使用常量对指令进行移位/屏蔽.

QSYM利用2的指数来计算基本块的频率, 这可以快速地制止过于频繁的基本块, 但同时也带来了过度修剪的问题, QSYM采用了两种方式来解决过度修剪: 基本块组合和上下文敏感性.

基本块组合是将多个基本块视为一个组合, 比如8个基本块视为一个组合, 那么当这个组合执行了8次之后, 其频率才加一, 也就是一种缓和的策略.

上下文敏感则是为了对在不同上下文运行的同一基本块做区分. 比如两个strcmp(), 其上下文是不同的, 故这两次调用需要视为不同的基本块进行频率计数. QSYM会维护当前执行的调用堆栈, 并计算其哈希来区分不同的上下文.