Fuzzing a survey

1.Background

• 静态分析（Static analysis)：静态分析针对代码中的词汇、语义等漏洞，但缺乏正确率，即分析静态分析软件给出的信息，也需要话很多时间（高误报率）；
• 动态分析（Dynamic analysis)：动态分析针对运行中的程序，但效率低下，需要很大程度的人类参与，且对分析员要求很高；
• 符号执行（Symbolic execution)：符号执行对于大规模项目十分效率低下；
• Fuzzing：可应对大规模程序，缺点是低效率与低代码覆盖率。

2.Fuzzing

• 输入文件越破碎越好，这样运行的程序更可能被打败；
• 输入可以是多种形式的：网络数据，各种格式的文件，可执行二进制数据等；

Fuzzing的执行
Fuzzing过程中，会对发生的，感兴趣的exception，crashes，violations进行记录。随后可用各种二进制分析软件进行对crashes的分析，如 IDA Pro,GDB等等。

• 两种Fuzzer
  • 基于生成的fuzzer：更熟悉文件格式，能精准生成代码，更容易突破文件验证，测试更深层次的代码，当文件不友好时，分析文件格式很困难。
  • 基于异变的fuzzer： 更简单地开始测试，需要一串有效的初始输入。

• 基于依赖源码等级分类

  • white box:需要源码，文件内的信息进行fuzz；
  • gray box:无需源码，通过运行分析程序获取部分内部信息；
  • black box:无需源码，不需要任何程序内部信息。

• dumb fuzzer 和 smart fuzzer：

  • 前者更注重速度，不回收信息；
  • 后者会回收信息，优化异变策略，优化输入 。

Fuzzing目前遇到的挑战：

• The challenge of how to mutate seed inputs.

  • 如何变异/生成样例使其能涵盖更多路径、更容易触发bug；
  • 何处变异，如何变异是重点；
  • 即盲目异变是浪费时间，精准的变异策略才是解决问题的关键。

• The challenge of low code coverage.

  • 更高的覆盖率意味着更高的发现bug概率；
  • 利用程序分析，达到更高的覆盖率。

• The challenge of passing the validation.

  • 许多程序都有输入检测，不符合规范则不予执行；
  • 灰盒与黑盒程序对内部认证方式不清楚，很难绕过检测，于是效率低下。

3.Coverage-based Fuzzing

Code coverage counting

• 最先进的方法把基本块（basic blocks）作为粒度

  • 基本块是程序执行时最小的相关单元；
  • 测量函数或者指令会导致信息缺失或冗余；
  • BB可以用首地址辨认，且BB的信息可以轻松通过代码检测提取。

• 两种测量选择：

  • 仅计算运行的 BB 数量；
  • 以及计算 BB 间转换次数；

• 前者测量顶点（vertices），后者测量边（edge）；

以AFL为例，介绍边（edge）测量

• 有源码时：在编译生成二进制文件时，插入桩，为检测做准备；
• 无源码时：将基本块转换为 TCG 块时插桩。

列举一段插桩代码

cur_location = <COMPILE_TIME_RANDOM>;
shared_mem [ cur_location ^ prec_location]++;
prev_location = cur_location >> 1;

cur_location 是随机生成的 ID ，而 shared_mem 是一块 64KB 的共享内存，每一个字节都标识着一个独特的边。
当一个 BB 间跳转发生时，会计算一个哈希值，然后当前哈希值对应的 bitmap 中的数据会被更新。如下图

Working process of coverage-based fuzzing
主循环内，程序挑选 interesting 种子进行变异、程序生成。目标程序执行这些生成的 testcases，发生 crash 的目标程序会被收集下来，其他感兴趣的样例会被放入种子池。
在 覆盖率引导 的 fuzzing 内，触发了新路径的程序，会被认为是 interesting

Fuzzing 过程中，我们主要关注 覆盖率 和 程序违规 。
前者可由之前插桩代码来统计；
后者可在 sanitizer 的帮助下，进行分析。

什么是Sanitizer？
Sanitizer是由 Google 研发团队提出的用于检测 C/C++ 程序常见内存错误的工具集
其中包含：
AddressSanitizer (asan) :检测内存访问错误，即发现程序访问了不该访问的内存，就会记录错误；
LeakageSanitizer (lsan) :内存泄露检测；
MemorySanitizer (msan) :检查读取未初始化的内存错误；
ThreadSanitizer (tsan) :检测数据竞争与死锁；
UndefinedBehaviorSanitizer (ubsan) :检测未定义的操作。

Key questions

• How to get initial inputs ?
  • 提供格式良好的 inputs ；
  • 良好的 inputs 可以适应许多格式复杂的文件 ；
  • 能探入更深层次路径的 inputs ；
  • 可复用
• How to generate testcases ?
• How to select seed from the pool ?
  • covering more code and be more likely to trigger vulnerabilities;
  • reduce the waste of repeatedly execution of paths and save computing resource
• How to efficiently test applications?
  • forkserver

4.Techniques integrated in fuzzing

• 污点分析;
• 利用AI生成、检测好的seed，使之符合格式;
• Intel PT;

5.Fuzzing towards different applications

• File format fuzzing;
  • Peach;
  • on web browsers;
• Kernel fuzzing;
• Fuzzing of protocols;

6.New trends of fuzzing

• Smart fuzzing;
• New techniques;
  • machine learning;
• new system features and hardware features;

7.Conclusion

Fuzzing是目前最为有效且效率高的漏洞发掘方式，本文对比了Fuzzing与其他技术的差别，总结了Fuzzing中综合的技术，最后展望了能让Fuzzing更为高效的未来技术。