Fuzzing的原理与实现机制-1

关于模糊测试的原理与实现机制等的探究。

背景知识

基本块

所谓基本块（basic block），就是一段线性程序码，只能从这段程序码的开始处进入这段程序，并且没有其它程序码会jump进这段程序，同时只能从这段程序码的最后一行离开这段程序，并且中间无其它程序码会jump出这段程序。说白点，以高级语言举例的话，就是一段顺序语句，中间没有if、else、while这样的分支或循环，这一段线性的程序码就是基本块。在IDA的反汇编CFG中那些一个个方框中的就是基本块。基本块有单一入口点、单一结束点的特征。

边

边（edge）是计算机图论里的一个概念，是连接两个顶点的线，表示顶点间的关系。在程序执行流中，边实际上就是程序的分支。在CFG中就是每个基本块中连接的箭头，因此，程序执行流中的边实际上描述的是基本块之间的关系。

路径

所谓程序运行的路径（path），就是程序执行遍历基本块的链表。一个非线性的程序里必然存在不同的路径，例如存在一个用户输入的分支选择的时候，程序就会根据用户的输入结果来选择不同的程序运行路径。

程序执行流

程序执行流（execution flow）就是指程序码从头到尾执行的顺序，遵循顺序、选择、循环三结构等基本的控制流程，根据代码逻辑和条件判断来决定下一步该执行哪个基本块。这种流程控制通过条件判断、循环语句和函数调用等控制结构实现，其定义了程序运行的路径和行为。

软件测试

软件测试（software testing）是一种用来鉴定软件的正确性、完整性、安全性和质量等的过程。按照可计算理论一个简单的数学证明推断出以下结果：不可能完全解决所谓“死机”，指任意计算机程序是否会进入死循环，或者罢工并产生输出问题。也就是说，软件测试是一种实际输出和预期输出间的审核或比较过程。

测试的进程常见的有alpha、beta、closed beta（封测）、open beta（公测）等（喜欢玩游戏的话应该都听说过这些测试）。

软件测试的方法一般分为黑盒测试、白盒测试以及灰盒测试。

黑盒测试

所谓黑盒测试就是指不关注程序的内部结构或者运作方式，而测试程序的功能。这种情况下测试者不需要具备相关代码等专业知识也可以进行，测试者只需要关注这个系统应该做的事，即当键入一个特定输入可以得到一定的输出。测试这选择有效输入和无效输入来验证产生的输出是否是正确的。

白盒测试

白盒测试需要关注测试程序内部的结构和运作方式，不太关注程序的功能（也就是黑盒测试的关注点）。这种测试是从编程语言的视角来设计测试用例的，测试者通过构建输入数据验证数据在程序中的流动路径，并以此确定适当的输出。

灰盒测试

是一种结合白盒和黑盒测试的方法。

代码覆盖率

代码覆盖（code coverage）是软件测试中的一种度量，描述程序中源代码被测试的比例和程度，所得的比例就是代码覆盖率。

基本的覆盖率准则有以下这些：

• 函数覆盖率（function coverage）
• 语句覆盖率（statement coverage）
• 边覆盖率（edge coverage）
  • 分支覆盖率（branch covergae）
• 条件覆盖率（condition coverage）

我们考虑以下C/C++函数：

int foo(int x, int y) {
  int z = 0;
  if ((x > 0) && (y > 0)) {
    z = x;
  }
  return z;
}

我们假设foo函数是一个大型程序的一部分。且某次测试用例执行到了这个函数，那么对于的各覆盖率准则如下：

• 函数覆盖率：只要foo执行过了一次，即满足函数覆盖率100%的条件。
• 语句覆盖率：若调用过foo(1, 1)，函数中每一行（包括z=x;）都执行一次，则满足语句覆盖率100%的条件。
• 分支覆盖率：若调用过foo(1, 1)和foo(0, 1)，由于前者进入if分支，因此z = x;就会执行，而后者不会进入if分支，因此满足分支覆盖率100%的条件。
• 条件覆盖率：若调用过foo(1, 1)、 foo(1, 0)、foo(0,0)，前两个会使(x > 0)的条件成立，而第三个则会使得其不成立；同时第一个会使(y > 0)的条件成立，而后两个则不会；所有条件都有出现成立或者不成立的情形，因此满足条件覆盖率100%的条件。

自动化测试

在软件测试中，自动化测试是使用独立于待测软件的其它软件来自动执行测试、比较实际结果和预期并产生测试报告的过程。自动化测试的优点是可以自动执行一些重复繁琐但是必要的测试工作，这可以极大程度上提高软件测试的效率。自动化测试也被称为测试驱动开发（TDD），测试用例可以在代码编写完成之前就设计好，并作为功能的一种定义形式存在，随着新的代码不断完成编写，测试也随之进行，缺陷被不断找出，因而代码也不断得到改进。但是其也有一定的局限性，即测试结果分析、测试脚本维护和编写仍需要人力投入。

插桩

插桩（instrumentation）是通过修改软件以便对其进行分析的行为。插桩一般分为对源码的插桩和对二进制文件的插桩两类。插桩的一个用途是进行性能分析，即测量测试运行期间的动态行为，这对于无法以足够精度进行静态分析的程序很有效。

但是插桩也具有一定的局限性：例如插桩会受到代码覆盖率达限制，比如程序从未到达过某个特定的执行点，那么在该点进行插桩就不会收集到任何数据。插桩也会增加程序的执行时间因此只能在测试环境中使用，其实际开销因所使用的插桩技术而异。

模糊测试

模糊测试（fuzz testing或fuzzing）是软件测试的一种技术，其核心思想是将自动或半自动生成的随机数据输入到一个程序中，并监视程序异常（如崩溃、断言失败等），以发现可能的程序错误或漏洞。其常常用于检测软件或计算机系统的安全漏洞。

Fuzzing在白盒、黑盒、灰盒测试中均有运用。

Fuzzing工具可用的基本假设

• 代码覆盖率能有效反馈
• 程序崩溃可以被检测
• 每秒可以执行多次Fuzzing（效率高）
• 符号执行可约束求解

通用的Fuzzing策略

• 追踪基本块
• 追踪边（分支）和路径
• 覆盖率比较

Fuzzing方法的不同类别Fuzzer

盲式Fuzzer

这是一种最古老的Fuzzing类别（blind fuzzers），这类Fuzzer必须要克服随机输入无法执行到软件中需要关注的代码的问题。通常采用变异模糊测试（mutational fuzzing）和生成式模糊测试（generational fuzzing）两种方法。

• 变异模糊测试：引入随机的变异，但是只能检测程序是否崩溃，并且无法有效发现新代码。
• 生成式模糊测试：通过形式化规范定义输入输出的格式，fuzzer无需学习如何生成格式正确的输入文件，但创建定义仍需要手动操作

这类Fuzzer唯一能观察到的就是输入是否会导致程序崩溃。

覆盖率引导Fuzzer

覆盖率引导的Fuzzer是为了提高变异模糊测试的性能而提出的一种测量程序代码覆盖率反馈的有效方法。这类的核心思想就是提供了评判输入的标准：哪些（新）代码区域被访问过以及访问的频率如何。横向对比盲式Fuzzer只会对输入进行随机变异能有效提升效率并提高测试的代码覆盖率。获取代码覆盖率反馈的方法有这些：

• 静态插桩：也就是源码插桩，获取代码覆盖率最快的方法之一就是静态编译时覆盖率（这种方法被AFL等工具广泛使用）。在这种情况下，编译器会在每个基本块头部添加存储代码覆盖率信息的特殊代码。
• 动态二进制插桩（DBI）：在程序运行时动态注入相关的代码实现（例如PIN插桩框架，以及支持多分支的AFL等工具）。
• 由硬件支持的追踪：一些现代CPU会支持多种形式的硬件追踪。以Intel的CPU为例，会使用两种技术：
  • 最后分支记录（last branch record）
  • Intel-PT

混合Fuzzer

覆盖引导的Fuzzer本身能够带来不错的结果，但一些程序中可能仍存在难以触及的代码区域，这种情况通常发生在仅少数输入能够满足某些条件时。这时候就需要结合程序的分析技术来辅助Fuzzing过程，例如结合符号执行或者污点分析技术。