#定向fuzzing

ABSTRACT

  • 背景（问题）：现有灰盒fuzzer不能进行有效的定向fuzz
  • 方法：基于模拟退火的power schedule，可以将更多的能量分配给更接近目标位置的种子，同时减少分配给距离目标距离更远的种子的能量。
  • 成果：优于基于符号执行的定向白盒测试和非定向的灰盒测试；可以和谷歌持续模糊测试平台OSS-Fuzz进行整合；可以在几个模糊不清的安全关键项目（如LibXML2）中发现39个bug

INTRODUCTION

定向fuzz的应用：补丁测试；崩溃重现；信息流检测

基于符号执行的白盒定向模糊测试的问题：耗时长

DFG：在本文中，我们介绍了定向灰盒模糊(DGF)，它专注于到达程序中给定的目标位置集。在高层次上，我们将可达性作为一个优化问题，并使用特定的元启发式来最小化生成的种子到目标的距离。为了计算种子距离，我们首先计算并测量每个基本块到目标的距离。虽然种子距离是过程间的，但我们的新度量只需要对调用图进行一次分析，对每个过程内CFG进行一次分析。在运行时，fuzzer聚合每个练习的基本块的距离值，以计算种子距离作为它们的平均值。DGF用于最小化种子距离的元启发式方法被称为模拟退火[19]，并被实现为功率调度。能量表控制所有种子[6]的能量。种子的能量是指种子发毛所花费的时间。像所有的灰盒模糊技术一样，通过将分析转移到编译时，我们可以最小化运行时的开销。

与基于符号执行的白盒定向模糊测试的区别：DGF将目标位置的可达性作为优化问题，而现有的定向（白盒）模糊方法将可达性作为迭代约束满足问题。

主要工作：灰盒模糊和模拟退火的整合；可以考虑多个目标、在检测时预先计算、可以运行时导出的，适用于程序间的一种正式的距离度量方法；AFLGO的实现整合和实验

MOTIVATING EXAMPLE

以心脏滴血漏洞为例子，简单来说该漏洞原理就是没有做边界检测而导致的数据溢出。

2.1 heartbleed and patch testing

简单的说，服务器端得到数据包，数据包长度为plen_real，而数据包中包含一个字节表明有效负载数据长度plen_fake，数据包剩下的部分是有效负载数据，长度为plen_real-1。整个数据包存储在一个char型数组之中。而服务器端构造新数据包时，先分配一段plen_fake+1的内存空间，前两个字节存放plen_fake，之后使用memcpy从收到的数据包有效负载数据起始位置向新数据包拷贝plen_fake字节数据。正常情况下plen_fake = plen_real-1，当用户有意设置plen_fake大于实际有效负载长度plen_real-1时，服务器就会发送plen_fake长度的数据，其中包括plen_fake - plen_real-1长度的数据，这些数据可能是一些用户密码或者密钥。

作者将AFLGO和KATCH比较，KATCH是最先进的基于符号执行的自动补丁测试工具。

2.2Fuzzing the Heartbleed-Introducing Source Code Commit

  • 简述KATCH的工作原理：首先识别最接近目标t的基本块bi，然后构建可以到达该基本块的路径约束，接着识别决定从bi到达t的字节是哪个，最后把完整的路径约束放到SMT中求解。
  • 基于符号执行的定向白盒模糊测试缺陷：耗时久，每探索一条路径都要重新计算距离；搜索可能不完整，解释器和求解器可能不支持语言特性或字节码；贪婪搜索可能陷入局部最优
  • AFLGO优势：AFLGo每秒生成并执行数千个输入，并在不到20分钟的时间内暴露Heartbleed；在运行时几乎不需要程序分析，只需要在编译/插装时进行轻量级程序分析；实现了基于模拟退火的全局搜索；实现了并行搜索，同时搜索多个目标
  • AFLGO测试心脏滴血流程
    • 首先对OPENSSL插桩。对于插桩后的二进制程序，AFL负责检测代码覆盖率，AFLGO负责检测种子到目标的距离
    • 然后使用模拟退火对OPENSSL模糊测试。
      • AFLGo进入探索阶段，并像AFL一样工作。在探索阶段，AFLGo随机变异提供的种子，以产生许多新的输入。如果一个新的输入增加了代码覆盖率，它将被添加到要模糊化的种子集;否则，将被丢弃。提供的和生成的种子在一个连续的循环中被模糊化。
      • 在开发阶段，AFLGo从离目标更近的种子中产生更多的新输入，基本上不会浪费宝贵的时间去模糊太远的种子。AFLGo根据作为功率调度实现的退火函数，慢慢地从探索阶段过渡到开发阶段。

3 TRCHNIQUE

3.2Measure of Distance between a Seed Input and Multiple Target Locations

为函数调用图和基本块级的CFG中的每个节点分配一个值。

将距离为f (n,n’)的函数定义为调用图CG中函数n和n’之间沿最短路径的边数。我们将函数n与目标函数Tf之间的函数级目标距离df(n,Tf)定义为n与任何可达目标函数tf∈Tf之间的函数距离的调和平均值

  • m是基本块，n是函数

  • R（n,Tf）是所有可以从n到达的目标函数集合

  • db(m1,m2)是基本块m1和m2之间沿着最短路径的边数。

  • N(m)是基本块m调用的函数集合

  • T是图Gi中的基本块的集合

  • Gi是控制流图

  • 基于上面的定义，基本块m到目标基本块Tb的距离为这个

image-20221214175433885

  • 种子s到目标基本块Tb的距离（normalized seed distance）为这个（种子的路径包含的基本块到目标基本块的和除以种子路径包含基本块的数量） $$d(s,T_{b})=\frac{\sum_{m\in\xi(s)}d_{b}(m,T_{b})}{|\xi(s)|} $$

  • 作者还定义了normalized seed distance $$\tilde{d} (s,T_b)$$，这是种子s到目标基本块Tb的距离和种子序列中与目标基本块Tb的最小距离的差值比上最大距离和最小距离的差值 $$ \tilde { d } ( s , T _ { b } ) = \frac { d ( s , T _ { b } ) - \mathrm { m i n D } } { \mathrm { m a x } \mathrm { D - m i nD } } $$

  • 注意：函数级和基本块级的距离计算是在插桩的时候，也就是fuzz开始之前预先计算好的。而上文中的mormalized seed distance是在fuzz中基于预先算好的函数间或基本块间的距离进行计算，因为有预计算的存在，所以运行中计算并不会太耗时

3.3 Annealing-based Power Schedules

作者给出了基于模拟退火算法的种子s到目标基本块Tb的能量分配公式 $$ p ( s , T _ { b } ) = ( 1 - \tilde { d } ( s , T _ { b } ) ) \cdot ( 1 - T _ { \mathrm { e x p } } ) + 0 . 5 T _ { \mathrm { e x p } } $$

作者将模拟退火算法的能量分配和AFL原有的能量分配结合在一起： $$ \hat { p } ( s , T _ { b } ) = p _ { \mathrm { a f f } } ( s ) \cdot 2 ^ { 1 0 \cdot p ( s , T _ { b } ) - 5 } $$

3.4 Scalability of Directed Greybox Fuzzing

作者在这里解释了AFLGO在计算节点间的目标距离的时候是如何提高效率的。AFLGO不去计算程序间控制流图，它计算两部分内容：调用图中的函数级目标距离和同一程序内控制流图中的调用点的基本块级别目标距离。计算最小距离的算法使用的是Djikstra算法，复杂度是$$O(V^2)$$，V是节点数。假如这里有n个程序内控制流图，平均每个图有m个结点，AFLGO先算n个图之间的目标距离，复杂度$$O(n^2)$$，然后算图内的每个结点目标距离，复杂度$$O(m^2)$$，整体复杂度$$O(n^2+m^2)$$。

然后说了一下AFLGO和AFL具有同样的可拓展性，因为主要的程序分析是放在编译中，运行中其实没有太大区别。

4 EVALUATION SETUP

image-20221216173338038

给出了AFLGO的架构，但是看这意思还是需要源代码啊，不是灰盒吗。

4.1 Implementation

  • AFLGo图提取器(GE)生成调用图(CG)和相关的控制流图(CFGs)。CG节点由函数签名标识，CFG节点由源文件和对应基本块的第一个语句行标识。GE实现为AFL LLVM通道的扩展，由编译器AFL -clang-fast激活。编译器环境变量CC被设置为afl-clang-fast，然后构建项目。
  • AFLGo距离计算器(DC)采用调用图和每个过程内控制流来计算每个基本块(BB)的过程间距离，如3.2节所述。DC被实现为一个Python脚本，它使用networkx包来解析图，并根据Djikstra的算法进行最短距离计算。DC生成BB-distance文件，其中包含每个BB的基本块级目标距离。
  • AFLGo instrumentor获取BB-distance文件，并在目标二进制文件中测量每个BB。具体来说，对于每个BB，确定各自的BB级目标距离，并注入扩展trampoline。trampoline是一段汇编代码，在每个跳跃指令之后执行，以跟踪覆盖的控制流边缘。一条边由64kb共享内存中的一个字节标识。在64位架构上，我们的扩展使用16个额外字节的共享内存:8个字节累积距离值，8个字节记录执行的bb的数量。对于每个BB, aflgo instrumentor添加汇编代码i)加载当前积累的距离并添加当前BB的目标距离，ii)加载并增加执行BB的数量，以及iii)将两个值存储到共享内存中。该检测实现为AFL LLVM通道的扩展。编译器被设置为afl-clang-fast，编译器标志引用BB-distance文件，项目是用ASAN构建的。
  • AFLGo Fuzzer实现到AFL版本2.40b(已经集成了AFLFast的探索计划[6])。它根据我们基于退火的功率调度(见3.3节)模糊检测二进制。共享内存中额外的16个字节通知fuzzer当前的种子距离。当前种子距离的计算方法是用累计bb距离除以执行的bb数。

5 APPLICATION 1: PATCH TESTING

  • 相对于KATCH，新覆盖的基本块提高了13%，作者认为没有覆盖到的BB是因为特定的操作系统、寄存器间接调用等不作为边出现在CFG中等原因。
  • 同时，KATCH和AFLGO各自都有彼此没有发现的基本块。作者认为可以将有向白盒和有向灰盒整合

6 APPLICATION 2: CONTINUOUS FUZZING

新玩意儿

  • directed symbolic-execution-based whitebox fuzzing 基于符号执行的定向白盒测试
  • SMT是啥子
  • Driller[38]是一个（无定向）模糊器的例子，它集成了AFL灰盒模糊器和Klee白盒模糊器。