The ArtScience and Engineering of Fuzzing: A Survey

Posted on | In | 阅读数 次

20200713 15:01 结

  • 关键词：自动化软件测试，模糊化，软件安全
  • 目的：作为一个survey，围绕模糊化，给它下定义，总结对软件测试提出的模糊化方面的改进，发掘有哪些创新点
  • 领域： 软件测试，模糊化

基础知识

定义

  • 模糊化是什么？
    • 使用生成的输入（输入存在语义和语法错误）重复运行一个项目。
  • 目前模糊化有哪些问题？
    • 一些fuzzer工具的源代码和手册实际达不到描述的那样
    • 不同fuzzer工具使用的术语各大相同
  • Fuzzing定义
    • 从fuzz输入空间生成样例测试Program，并突出PUT(Program Under Test)期望的输入空间
  • Fuzz Testing定义
    • 使用fuzzing技术去测试看是否PUT违背安全政策
    • 目的：找出program中影响安全的bugs
  • Fuzzer定义
    • 在一个PUT上执行fuzzing testing的Program
  • Fuzz Campaign
    • 针对一条特定安全政策，一个fuzzer在PUT上的一个特定的执行，相当于专门针对哪个安全，制作出一些sample去用fuzzer执行。
  • Bug Oracle
    • 作为fuzzer的一部分Program，检测给定的PUT执行是否违反特定安全政策
  • Fuzz Configuration
    • Fuzz算法的参数配置，依赖于特定的fuzz algorithm
  • 设计测试工具的时候，一定先熟悉源代码和PUT的相关知识！！！

Fuzz Testing 算法

  • 有两个部分：对配置进行预处理；迭代（包括Schedule,InputGen,InputEval,ConfUpdate,Continue）
    • PREPROCESS：执行大量操作，比如插入一些功能性代码到PUTs中，或是检测种子文件（产生测试样例）的执行速度
    • 第二部分的迭代的流程：先选择一个fuzz配置；根据配置中的参数生成测试样例；用测试样例和oracle bug检测是否违背安全政策（这个应该可以自己规定），这时可以得到execinfos，这大概是为了变动配置，为了之后能选取到更具有代表性的配置去生成测试样例；根据execinfos,改变fuzz配置；最后判断fuzz配置是否进行下一轮的迭代。

Fuzzer的分类

  • 根据在每次fuzz run的时候fuzzer观察到的东西多少，以下只是安全专家的一致认同，在实际使用的时候，三者的区别不太明显。

  • 黑盒fuzzer

    • 只能看到PUT输入和输出的表现，有一些还考虑输入的结构信息
  • 白盒fuzzer
    • 可以观察到PUT的内部信息以及执行过程中的收集到的信息
  • 灰盒fuzzer
    • 可以观察到一部分PUT的内部信息和它的执行，但是不能得到PUT完成的语义，且只能对PUT执行轻量级的分析和对执行收集动态信息。即收集一些近似信息

PREPROCESS

  • 预处理包括对PUT做一些性能监控（灰盒、白盒都能去PUT中获取一些反馈信息）[对PUT进行插桩]，去除冗余的配置（像种子选择），修剪种子，生成驱动应用。

Instrumentation

  • 白盒、灰盒中用来收集最有价值反馈的一种方法，代码插桩（在被测程序中插入完成相应工作的代码，即代码插桩技术，来获取程序中可执行语句被执行（即被覆盖）的情况）
  • 分为static instrumentation和dynamic instrumentation，前者一般在源代码的编译阶段执行，后者一般在运行阶段执行。

Execution Feedback

  • 灰盒fuzzers将执行反馈作为输入去优化测试样例，AFL等文章计算分支覆盖率作为反馈内容，但容易发生分支冲突，对此CollAFL提出相应解决方法。

In-Memory Fuzzing

  • 为了最小化执行开销，每次fuzz迭代只fuzz一部分的PUT,program会保留PUT的快照，下次fuzz新的测试样例时需要恢复memory快照。这种快照可以避免执行不必要的启动代码。
  • in-memiry API fuzzing通过一个函数而不是每次迭代恢复PUT的状态，这种方式尽管有效，但是找到的bugs却不完整，因为可能调用不到这种函数（我猜是函数名生成有问题？？）

Thread Scheduling

  • 随机调度线程对找到race condition bugs很有效。

Seed Selection

  • 希望选取最小的种子集合最大化覆盖率（如节点覆盖率）
  • 覆盖率评价指标：
    • branch coverage（计算分支的执行次数），当测试样例在分支执行次数上的数量级不同时才认为它们是不同的
    • the number of executed instructions,executed branches,and unique basic block。希望将最长的执行路径的测试样例增加到minset中。

Seed Trimming

  • 在preprocess中执行，或作为CONFUPDATE的一部分

  • 在AFL中只要修改过的seed能够达到和原先种子一样的覆盖率，就修剪掉原先种子。

  • [177]发现size小的种子没啥用

Preparing a Driver Application

  • 给fuzzer一开始的时候准备一个驱动器（这里不太理解）

SCHEDULING

  • 选择一个fuzz 配置为下轮fuzz迭代，不同的fuzzer类型具有不同的配置。这里主要的研究点是提出创新性的scheduling算法。

The Fuzz Cofiguration Scheduling (FCS) Problem

  • 挑选一个可能产生最好结果的配置（评判可能依据 find the most number of unique bugs[unique bugs不知道咋翻译], maximize the coverage]。在挑选的时候考虑explore（关于每个配置获取更为准确的信息）和exploit（获取好的结果），做这两者的trade-off。

Black-box FCS Algorithms

  • 黑盒用到的反馈信息：crashes和bug的数量毕竟执行时间
  • [225]提炼数学模型，WCCP/UW，由于反馈信息会随着配置结果变差，因此选择一些配置不会导致反馈decay。为了将crashes或bugs / time来修改反馈信息，目的是为了能更快速地进行配置（感觉是把time因素考虑进去）。

Grey-box FCS Algorithms

  • 灰盒用到的反馈信息：黑盒能用到的，达到的覆盖率等等
  • AFL认为执行最快，input最少的是fit

  • AFLFast在AFL基础上做了三点改进

    • 增加两条重要准则：
      • AFLFast喜欢被选中最少的配置
      • AFLFast喜欢最少选择的路径
    • AFLFast在AFL增加了优先级，替代AFL中的圆形选择
    • AFLFast每个配置被选中次数是动态改变的

  • AFLGo修改了AFLFast优先级的特征，目的是为了找到特定的程序位置。

INPUT GENERATION

  • 分为generation-based和mutation-based，前者是基于model的，后者是通过mutate seed。

Model-based (Generation-based) Fuzzers

  • 预定义或用户提供的模型
  • 推断模型可能发生在PREPROCESS阶段也可能在CONFUPDATE阶段
    • 在PREPROCESS阶段，在PUT中搜找可用的数据（如文字），去预测合适的输出
    • 在CONFUPDATE阶段，每次迭代更新model
  • 编译器模型（不太能理解这个模型）
    • 解析特定的文件格式

Model-less (Mutation-based) Fuzzers

  • 需要seed-based输入生成和白盒输入生成。
  • Bit-flipping：翻转固定/不固定数量bit位，用mutation ratio决定翻转多少数量的bit位。因此，找到一个合适的mutation ratio数值至关重要。
  • Arithmetic Mutation：将选择的字节序列视为一个整数，对整数进行处理（不太能理解）
  • Block-based Mutation：以block为单位，进行mutation
  • Dictionary-based Mutation：对具体的字符（数值）进行mutation（不太能理解）

White-box Fuzzers

  • 先使用白盒程序分析找到PUT的信息，用这信息去进行黑盒or灰盒fuzzing。

  • Dynamic symbolic execution：比灰盒和黑盒慢很多，因为它需要对PUT的每条指令进行插桩和分析，这方面的研究都聚集在如何减少它的代价方面。

  • Guided Fuzzing：先对PUT进行分析（静态or动态分析）来获取有用的信息；再利用这个信息去生成test case。这上面的研究一方面需要减少分析产生的代价。

  • PUT Mutation：不重要。。

INPUT EVALUATION

Bug Oracles

  • 有三个方面的侦测：内存安全问题（是否访问到不安全的内存、控制流的完整性[啥意思]）、访问到未被定义的行为（如编译器不同，程序猿只考虑了某些编译器情况下可行，但有些不可行却忽略了）、输入的合法性（比如SQL访问可能对数据库引擎存在一些破坏）

Execution Optimizations

  • 由于迭代需要每次都初始化PUT进程，需要耗费大量的时间，对此，AFL提供了一个fork-server去让迭代去从进行初始化好的进行进程中fork一下。

Triage

  • 分析和报告导致违反政策（感觉就是不安全的）的进程，分为三步：去重复、优先级、测试样例最小化。

Deduplication

  • 去重复：若该test case返回的Bug已经被以前的test case找到了，这个test case就不要了。能得到test case集合，该集合中每个test case都能触发唯一的bug。去重复有三种主要的实现方式：
    • stack backtrace hashing
      • 记录了crash时的stack backtrace(如：main → d → c → b → a → foo )，当其他crash时的stack backtrace的后五个也是这个时候，认为他们重复, 这是major hash。而minor hash还考虑到line number（感觉是数量）。但这样做事基于一种假设，即相似的crash是由相似的bugs引起的，但这假设未被验证，且能举出反例。
    • coverage-based deduplication
      • 在PUT中插桩记录PUT每次执行的edge覆盖率，根据这个信息选取seeds，AFL认为当crash覆盖到之前未见到的edge或者未覆盖到之前在所有其他crashes中都覆盖到的edge时，认为该crash是唯一的。
    • semantics-aware deduplication
      • 从每个crash处反向分析，找到那个function，根据function来对crashes进行分类。(怎么那么奇怪)

###

Prioritization and Exploitability

  • 根据一个crash的可利用性来划分优先级。Microsoft’s !exploitable的优先级划分： EXPLOITABLE > PROBABLY_EXPLOITABLE > UNKNOWN >

    NOT_LIKELY_EXPLOITABLE,

Test case minimization

  • 利用bug oracle进行test case 最小化。许多fuzzers都针对自己特定的情况选用test case最小化算法。

CONFIGURATION UPDATING

  • 可用来区别是白盒fuzzer、黑盒fuzzer、灰盒fuzzer。由于黑盒只能用到Oracle bug(不能得到PUT的内部信息)大部分Conf都不被修改。

Evolutionary Seed Pool Update

  • 灰盒fuzzer大多基于遗传算法进行展开，EA-based fuzzers大多数使用node或者Branch覆盖度作为fitness function.[后面举例没仔细看]

Maintaining a Minset

  • 赋予favorable fuzzing conf以高的被选择进行fuzzing的权重。思想是：需要少的test case最大化coverage评价指标。

​

Links:

0%