模糊测试（Fuzz Testing）

最近一直在看模糊测试方面的东西，因为实验室之前没有做过这个方向，基本都是在自己瞎看。实践方面也只是粗略地看了看老版AFL的代码、在一个处理JSON的开源C库上试了试。总之就是把乱七八糟可能没什么干货的收获总结一下吧。

入门资料

先列一些我认为对建立模糊测试概念比较有用的入门资料。

• 综述文章
  • 一篇比较通俗的阐述原理的文章：Fuzzing: Hack, art, and science
  • 更多技术细节的综述：The art, science, and engineering of fuzzing: A survey
• 工程实践
  • 实际用的比较多的fuzzer是AFL和LibFuzzer
  • AFL
  • 原版AFL，仍然在维护的版本AFLplusplus
  • 一篇入门实践的博客一个完整Fuzz过程——对ok-file-formats的模糊测试
  • 更多可以实践的例子https://github.com/mykter/afl-training，https://github.com/antonio-morales/Fuzzing101
  • LibFuzzer
  • 集成在LLVM项目里，官网https://www.llvm.org/docs/LibFuzzer.html
  • 谷歌的入门实践教程https://github.com/google/fuzzing/blob/master/tutorial/libFuzzerTutorial.md

定义和分类

一个可行的定义是：对于一个被测程序（PUT），从它的一个期望输入空间中采样（生成）输入，通过检查是否存在违反PUT正确性的输入，来对PUT进行测试。

按照对PUT内部信息掌握和利用的程度，模糊测试可以分类为：

• 黑盒模糊测试
  • 测试器将被测程序视为“黑盒”，不监测其执行状态，只监测输入、输出
  • 早期模糊测试器多采用黑盒测试，通过随机生成大量输入以找到引起程序崩溃的漏洞
  • 一些现代模糊测试器（如Peach），在考虑输入的字段结构进行黑盒测试
• 白盒模糊测试
  • 通过分析程序内部信息生成输入，在广义上属于模糊测试
  • 最主流的技术是动态符号执行（Concolic Execution），如KLEE、S2E等测试器
  • 面临的主要问题是开销过大
• 灰盒模糊测试
  • 使用类似黑盒测试的输入生成方式，但通过收集部分被测程序运行状态信息优化生成过程
  • 实际测试效率高，是目前的主流研究方向，代表工作有AFL（及基于AFL的一系列变种）和LibFuzzer

模糊一词最初表示随机性，因此狭义上的模糊测试只包含黑盒与灰盒测试，大部分研究者将白盒测试也纳入广义的模糊测试定义。考虑目前的热门研究方向和工程流行程度，如无特殊说明，下文中提到的模糊测试指灰盒模糊测试，白盒模糊测试用动态符号执行指代。

典型流程

• 被测程序插桩
  • 对于白盒和灰盒测试，为了获取被测程序执行信息，一般需要对被测程序进行“插桩”，即修改二进制程序文件以将运行信息发送给测试器
  • 早期AFL直接在汇编代码中插桩，现代AFL和LibFuzzer更多地从LLVM中间代码层面进行插桩
  • 除了修改二进制文件，也有在测试器虚拟环境中执行被测程序的方式
• 种子输入和修剪
  • 为了提高测试效率，灰盒测试模糊器一般以一组“良好”（如对被测程序代码覆盖率高）的种子输入作为输入生成的基础
  • 测试器一般还会根据种子输入的重叠程度、执行开销等进行筛选，以减小测试开销
• 种子调度
  • 通过调整种子的运行优先级和次数，可以更有效率地提高对被测程序的覆盖率
  • 对调度方式（尤其是灰盒测试中）的改进是当前的热门研究方向
  • 例如AFLFast将对程序路径的覆盖建模为马尔科夫链，使到达稀有路径的种子获得更高的调度优先级，以更快覆盖难以到达的路径
• 输入生成
  • 模糊测试获得高被测程序覆盖率的关键是快速生成高质量的输入
  • 基于生成
  • Peach等模糊测试器根据用户定义的输入字段格式生成随机输入
  • Skyfire、IMF等模糊测试器在大量合法输入中自动推断输入字段格式，从而减少人工指定
  • 基于变异
  • AFL、LibFuzzer等主流测试器通过变异种子输入获得新输入
  • 常用变异策略：比特反转、算术运算、基于块变异、基于用户字典变异
  • 结合白盒技术
  • Driller使用动态符号执行辅助灰盒测试器生成覆盖难以到达路径的输入
  • VUzzer、Angora使用污点分析辅助灰盒测试器生成能够通过魔数检查的输入
  • T-Fuzz通过静态分析和符号执行修改被测程序以绕过校验和检查
• 效果评估
  • 漏洞检查（Bug Oracle）：模糊测试器无法确定程序如何运行才是“正确的”，需要在触发漏洞时使程序崩溃以通知模糊测试器
  • sanitize：现代编译器能够加入sanitize选项进行严格检查，使程序在遇到内存越界、未定义行为等漏洞时崩溃，而不是进入不可预测状态继续执行
  • 交叉验证：与相同功能程序进行交叉断言检查，能够使程序在正常结束但给出错误结果时崩溃
  • 输入分类
  • 模糊测试器会保存所有触发了程序崩溃的输入，对于触发同一个漏洞的输入需要进行合并，常用合并策略：依据路径、调用栈散列
  • 输入修剪
  • 覆盖率评估
  • 测试能够显示漏洞的存在，但不能证明漏洞不存在
  • 如果测试对程序达到了较高的“覆盖率”且未发现漏洞，能够为程序安全性提供一部分可信度
  • 朴素的评估方式：代码行覆盖百分比
    • 对于循环、递归等复杂结构表达能力不足
    • 会受到代码中不可到达路径的影响
  • AFL等采用的评估方式：以基本块转移为单位，按次数分组
    • 能够在一定程度上表达复杂结构
    • 无法给出一个覆盖百分比

模糊测试取得的成果

• 得益于极高的效率，AFL和LibFuzzer在开源软件中被大量使用，成功发现了流行开源软件中的许多漏洞：如OpenSSL、LLVM、Ffmpeg等

模糊测试存在的问题

• 不能提供对软件安全性的理论保证
  • 灰盒模糊测试已经被用于发现大量开源软件中的漏洞，但由于输入的随机性，并不能保证通过模糊测试的软件就一定不存在漏洞
  • 覆盖率评估能够为软件安全性提供参考，但：
  • 如前所述，评估方式存在局限性
  • 路径覆盖率也并不能为安全性提供理论保证，一些漏洞在指定路径的触发还需要满足指定条件
• 难以处理严格检查、嵌套条件等深层路径
  • 魔数检查问题：如对32位整数x的条件分支 x == N，在N不是一个特殊值的情况下，灰盒模糊测试的随机变异只有$2^{-32}$概率能够满足条件，即只有极少数的测试用例能够覆盖到条件为真的路径，使得模糊测试难以处理结构化数据
  • 程序中普遍存在的深层条件嵌套加剧了这一问题
  • 从而模糊测试擅长发现浅层漏洞，难以发现深层漏洞
• 变异、调度策略有较大改进空间：经典的AFL变异策略基于效率考虑和工程经验，存在诸多不足，如：
  • 朴素的调度策略下高频路径被过度测试，低频路径难以到达
  • 以是否覆盖新路径作为新加入种子的依据，会丢失变异的中间状态
• 无法处理外部环境
  • 外部函数：程序的正确性可能依赖调用的外部函数的返回结果，而外部函数常常不存在插桩条件，或在常规测试情况下行为不完全（如缺少malloc失败的情况）
  • 外部环境交互：模糊测试目前只应用于纯文件输入的命令行程序，无法处理读取外部环境（如系统环境变量）、其他IO交互（UI、网络）等情况

热门研究方向

• 模糊测试调度策略改进：快速到达高权重路径
  • AFLFast：基本块建模为马尔科夫链
  • AFLGo：以距离目标基本块距离赋权
  • VUzzer：降低错误处理部分路径权重
• 模糊测试变异策略改进：解决严格检查、嵌套条件问题
  • Driller：引入动态符号执行求解难满足的条件
  • VUzzer、T-Fuzz：引入动态污点分析，将比较指令常数值加入测试器字典
  • LibFuzz：使用protobuf定义结构化数据
• 动态符号执行效率改进
  • KLEE：地址空间共享、外部环境模拟
  • angr、S2E……