关于模糊测试(Fuzz Testing)的一些总结

发布于 2022-10-20  442 次阅读


模糊测试(Fuzz Testing)

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

入门资料

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

定义和分类

一个可行的定义是:对于一个被测程序(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……

长安城里的一切已经结束,一切都在无可挽回地走向庸俗。