Evaluating Fuzz Testing

发表于 | 更新于 | 分类于

Evaluating Fuzz Testing

1 介绍

信息量太大回头再写。。

# 一天后更新

不想写了差不多就下面这些内容吧。。

2 背景

2.1 fuzzing流程

fuzzing algorithm.png

fuzzing的核心算法

initSeedCorpus：初始化新的输入

isDone：决定fuzzing是否停止

choose：从队列中选择至少一个种子输入进行变异

mutate：从至少一个种子输入和观察到的现象中产生新的候选种子

eval：评价程序的种子产生观察现象

isInteresting：根据观察到的现象决定种子是否保留

fuzzer的最终目标是生成输入使程序crash。其他类型的观察现象也是需要的，比如用例运行的时间，可以用来指示算法复杂度漏洞的存在。

2.2 近年来fuzzing的进展

本文研究对象是2012至2018这7年顶会上32篇相关论文。其中25篇是2016年以来的成果。

summary.png

这里总结了32篇论文评价时的相关信息。

这里通过文章的主题将这些文章分类：

initSeedCorpus:

  • Skyfire和Orthrus改进初始化种子选择
  • QuickFuzz通过输入结构的语法生成种子输入
  • DIFUZE进行前期的静态分析来识别输入的结构（？）

mutate:

  • SYMFUZZ使用符号执行决定变异的种子输入的位数
  • 有些fuzzer使用预定义的变异策略（如位翻转或随机代替）
  • MutaGen通过代码切片使用测试程序的代码段来转换或操作输入
  • SDF使用种子自身的性质指导变异
  • Chizpurfle的变异器使用java语言构建器的知识辅助安卓系统服务的过程中fuzz

eval:

  • Driller和MAYHEM发现某些guard条件通过暴力猜很难满足，因此使用符号执行在eval阶段绕过他们
  • S2F也在eval阶段使用符号执行
  • 其他工作目标加快eval阶段的速度通过修改操作系统或低层级的原语来观测执行影响
  • T-Fuzz移除对于输入的检查（这些检查阻止程序达到新代码）
  • MEDS进行更细粒度的运行时分析来检测error

isInteresting:

有意思的行为如：长运行时间，有差异的行为等

  • Steelix和Angora进行插桩获取更细粒度的信息
  • Dowser和VUzzer使用静态分析在不同程序点赋值不同的rewards来达到CFG中更深的点

choose:

  • 部分工作基于输入是否到达某些区域来选择下一个候选输入
  • 另一部分提出算法选择候选种子

3 综述和实验设置

评价模糊测试算法的步骤

  1. 选择一个baseline算法
  2. 选择一个有表达能力的目标程序（benchmark）
  3. 选择比较的度量，最理想的是找到的bug数
  4. 算法的参数选择，比如种子文件如何选择
  5. 在A和B上多次运行，进行性能上的差异显著性检验

实验设置：

fuzzers. AFL 2.43b作为baseline B，AFLFast作为advanced算法。同时使用AFL的-n选项（关闭了覆盖率跟踪），称为AFLNaive。

benchmark. nm, objdump, cxxfilt, gif2png, FFmpeg。这些程序都在最近的成果评价时用来评价工具性能。

Performance measure. unique crashes，uniqueness由AFL能覆盖的路径数决定。

platform and configuration. 每次测试跑24小时，每种测试至少跑30次。同时也尝试了多样的种子输入文件：空文件，随机选择正确类型，人工写得文件。

4 统计上的鲁棒性比较

大部分已有研究（18/32）没有提及测试的次数。这些论文可能认为随机性是均匀的，即如果测试跑了足够长时间，不同的随机会收敛，所有fuzzer会发现相同数量的crash。对于gif2png进行30次24小时的实验，AFLFast找到51个crash（中位数），AFL找到39个crash（中位数），使用Mann Whitney U-test进行显著性检验发现p-value>0.05。

讨论：最好的检验方法

两个可行的方法：

  1. permutation test
  2. bootstrap-based tests

这两个方法与Mann Whitney相比是否合适不得而知，所以本文采取Arcuri和Briand的方法。从实验结果可知方法A比B好，但是好多少不知道，所以通过比较中位数的绝对差异来隐含地回答这个问题。

5 种子选择

大多数工作（27/32）改进fuzzing loop。30/32使用非空的种子集合。

一个普遍的观点就是种子输入应该well-formed（valid）而且small。

可能初始语料库的细节并不重要，也就是说，不论种子如何初始，都能从算法的改进上体现出来。

本文使用不同种子输入测试FFmpeg，包括已有video files和randomly-generated videos。

总结来说，fuzzers在同个程序上针对不同输入的性能表现各不同。本文建议应该更谨慎地考虑，应该使用各类输入评价fuzzer的算法。论文应该写明种子输入如何收集，且最好给出实验用到的种子输入。而且empty seed应该考虑到，因为这是最简单的输入，可以被任意系统使用。

6 超时

比较常用的是24小时（10/32），和5或6小时（7/32）。6/32超过一天。

QQ截图20181026134651.png

而且不同超时设置会影响实验的结果，如上图。timeout=6h时，AFL没找到crash但是AFLFast找到4个，差异是显著的；然而若timeout=24h，AFL找到14个crash而AFLFast只找到8个，这个差异也是显著的。

较短的timeout更符合实际场景。

讨论：也可以计算AUC作为报告找bug能力的度量。但是如果一个fuzzer A一开始就发现5个crash，另一个fuzzer B在最后才发现了10个crash，直觉来说B的找bug能力大于A，但是AUC较小，所以AUC度量不适用于基于时间绘图。

7 表现/性能度量

7.1 Ground Truth: Bugs Found

能找到bug是检验fuzzers性能的第一标准！

7.2 AFL覆盖率简况

7.3 Stack hashes

7.4 代码覆盖

一句话，代码覆盖率作为第二度量是讲得通的，但是最主要的评价指标还是找到的bug数（distinct bugs）。

8 目标程序

这里涉及benchmark选择的问题。

主要分为两类：

  1. 真实程序和人工程序（或bug）
  2. 手动选择的程序，人工注入bug

8.1 真实程序

使用真实程序作为benchmark的问题：

  1. 只使用了很少的目标程序，没有明确说明代表性。很难泛化到其他程序，7个真实项目太少了
  2. 在这些文章中很少有论文用到相同的目标程序（版本也相同）

Google Fuzzer Suite比较好地解决了这个问题：

  1. 使用了25个程序，包括已有bug
  2. 设计用作一类回归测试

8.2 人工程序

有时不关心特定的程序集合，而是程序中反模式的有代表性的集合。

有两个著名的suite：CGC和LAVA-M

8.3 面向一个Fuzzing Benchmark Suite

  1. suite包含的程序应该能够说明bug在什么是否发现的？是合成引入的还是就版本已有bug？
  2. suite应该足够大，能够很好表达目标程序群体的特征
  3. 需要构建测试方法防止overfitting（为了找更多bug而强行硬编码规则之类的？）

9 结论和未来工作

已有工作：

  • 没有多次执行，没有进行性能提升的显著性检验
  • 很有工作没有通过统计distinct bugs评价fuzzer的性能，而是和AFL一样使用unique crashes
  • 很多工作只有很短的timeout，缺少合理的理由
  • 许多工作没有认真考虑种子输入的影响
  • 这些工作选择了不同的目标程序，很难比较不同工具或算法间的性能

本文建议，模糊测试效果评价应该包含以下元素：

  • 多次试验，进行统计测试
  • 大量包含已知bug的目标程序
  • 从已知bug的方面度量性能，而不是基于AFL的启发式度量
  • 全面考虑各类种子输入，包括空输入
  • timeout≥24h

未来工作的三条线：

  1. benchmark
  2. 在实际fuzzign结果的基础上考虑crash去重方法
  3. 探索改进新的基于observation的fuzzing算法