MC2 : 严格而高效的定向灰盒模糊法

abstract

背景：most existing directed greybox fuzzers do not provied any theoretical analysis of their performence or optimality.大多数现有的有向灰盒模糊器都没有对其性能或最优性提供任何理论分析。

方法：

  • 引入了一个复杂性理论框架，将灰盒模糊作为先知引导的搜索问题，通过查询oracle来接收关于输入空间的反馈。使用模糊算法寻找目标达到输入所需的oracle查询数量作为性能指标。
  • 基于框架，设计了一个随机有向灰盒模糊算法

成果：在具有挑战性的基准测试(Magma和Fuzzer测试套件)中比最先进的定向灰盒模糊器的性能平均高出两个数量级(即134×)。MC2还发现了15个以前未被发现的bug，这是其他最先进的定向灰盒模糊器无法发现的

introduction

背景：有向灰盒模糊是一种流行的具有针对性的软件测试技术，当给定程序中的一组目标站点，定向灰盒模糊器自动搜索程序的输入空间，以寻找到达目标的输入。但由于现实世界程序的输入空间非常大，大多数现有的有向灰盒模糊器使用进化算法，将其搜索集中在通过工具化程序执行使用反馈信息确定的有希望的输入区域。（比如模糊器经常收集关于控制流图距离或与目标的分支约束距离的反馈信息，并优先处理接近目标的变异输入）

问题：现有的有向模糊器没有提供任何关于其性能的理论分析。没有严格的理论理解，就很难理解模糊器设计的关键指导原则。（作者提出了几个示例问题：什么是最好的（即最优的）定向模糊器？模糊算法随着输入空间大小的变化而变化的程度如何？什么样的反馈信息对模糊处理最有用？一个算法如何才能最好地利用反馈？在使用这种反馈信息方面，能否比进化算法做得更好？）

工作：

  • 复杂理论框架：将关于仪器和模糊算法类型的具体细节抽象到一个统一的框架中。我们将有向灰盒模糊处理的任务建模为一个甲骨文引导的搜索问题：找到到达目标的输入，给定查询访问执行程序的甲骨文，并向模糊处理算法揭示一些关于搜索空间的信息（即有希望的输入区域的身份）。
  • 执行的复杂性：引入了执行复杂度的概念，这是一个渐近度量框架中任何模糊算法的性能的指标。其值是根据模糊器在找到到达目标站点的输入之前进行的oracle查询的数量。
  • 一个最佳的模糊算法：引入了一种特殊类型的甲骨文，称为噪声计数甲骨文。基于噪声计数甲骨文和分析框架设计了一个模糊算法
  • 用蒙特卡洛进行近似计数：我们开发了一种蒙特卡洛算法，用于实现我们的随机定向灰盒模糊算法，但是作者指出这样容易把到达目标数估计成零，因为在实践中，大多数模糊目标点只能由满足一个或多个分支约束的少量输入到达。所以为了克服这个问题，作者认为即使没有找到达到目标的少数输入，我们仍然可以以高置信度计算出一个计数的上界。（不太懂）
  • 浓度范围。可以使用浓度界来推导满足分支约束的可能性的上界
  • 沿着多个分支进行计数。对于任何给定的到达目标的路径，我们近似地计算满足上述路径中每个分支的输入数量，并将它们结合起来，得到到达目标的输入数量的估计值。

讲实话，读完引言感觉这篇有点抽象啊。

methodology

  • 本节作者提出一个通用复杂理论框架用于在oracle引导搜索问题中推论最好的定向灰盒模糊器。
  • 然后用这个框架搞一个噪声计数oracle，用这个oracle建立一个优化的定向灰盒模糊器。

2.1 terminology and notation

  • 目标程序为P
  • 在模糊处理过程中要探索的大而有限的输入空间表示为I
  • input region：是输入空间I的子集。
  • pai：表示CFG中的一条有穷路径
  • P(i)：输入为i的程序P的执行结果

2.2 A framework for directed greybox fuzzing

在这一节中，我们引入了一个复杂性理论框架来推理最佳模糊器在目标程序执行数量方面的性能下限

  • 该框架允许模糊器通过查询一个甲骨文来学习关于任何有界输入区域I的信息。
  • 假设每个Oracle查询最多可以提供一个给定输入区域的c个比特的信息
  • 该框架不做假设，没有任何关于程序的先验知识

problem definition

  • 将有向灰盒模糊器处理的任务定义为一个Oracle引导的搜索问题：在给定访问程序，控制流图，输入空间，目标边和Oracle询问，模糊算法必须能找到一个输入能够让该输入对应的路径达到目标边。

execution complexity

这个是为了衡量模糊器的性能，定义的一个指标值。在找到达到目标的输入之前需要的甲骨文查询数量。（甲骨文查询的数量直接映射到程序的执行数量，这句话是不是可以理解未查询数就是程序的执行数）

这里也指出了本文框架的目的，计算测试fuzzer的execution complexity，试图找到execution complexity的下界（最小值），即f找到达到目标的输入之前需要的最小甲骨文查询数量，用这个指标衡量fuzzer性能。

这一小节给出了模糊算法的下限定理（定理2.1）：给定在每次查询中只揭示一个恒定的c比特信息的任意Oracle，任何模糊算法都需要Ω(log(N))的执行复杂度来寻找在N大小的输入空间中达到目标的输入。

Greybox vs Blackbox Oracle

作者强调，这个下限是无法用黑盒甲骨文实现的，因为在黑盒甲骨文中无法提供c比特的反馈。

2.3 使用噪声技术的oracle的最佳定向fuzz

  • 噪声计数oracle：选择两个任意的input region，近似地计算可以到达targets并且属于这两个region的inputs的个数，返回c=1比特的信息。给出了计数oracle的公式，大概就是比较两个input region的数量大小，返回1或0。 $$ O ( I _ { L } , I _ { R } ) = \left{ \begin{matrix} { 1 } & { \mathrm { i f ~ } C ( I _ { L } ) \geq C ( I _ { R } ) } \ { 0 } & { \mathrm { o t h e r w i s e } } \ \end{matrix} \right. $$

    • 这里提到了一个错误概率p，作者假设噪声甲骨文以p<1/2的概率返回错误的答案。

  • 最佳确定性模糊器：迭代地将一个输入区域分成两半，并查询计数甲骨文以挑选计数较高的那一半，最终找到达到目标的输入。

    • 这个算法的前提是错误概率为0，也就是没有噪声（noiseless）

  • 最佳的随机化模糊器：指出上面的算法不够实际（p不可能为0），提出了一种新的随机模糊算法

    • 作者指出：随机算法的期望值考虑了所有的潜在行为，没有对输入分布进行假设，使得适用于任何程序；具有一定成功概率的随机模糊算法都可以被多次重新运行，因此其失败的概率随着试验的增加而呈指数级下降，达到一个可以忽略不计的小值。
    • 算法的执行复杂度（定理2.2）：给定一个噪声计数Oracle，该Oracle返回1bit信息并且查询失败概率p小于1/2，随机模糊算法有O((1−𝛿)∗ log(N)/(1/2−p)^2)的预期执行复杂度，以找到成功概率至少为1−𝛿的可以到达target的输入。
    • 算法的最优性（定理2.3）：给定任何每次查询返回一个常数c比特的信息，失败概率p<1/2的Oracle，任何以至少1−𝛿的概率成功的模糊算法都有Ω((1−𝛿)∗ log(N) ( 1 2−p)2)的预期执行复杂性。
    • 作者指出该算法通过自适应地选择基于每个甲骨文查询的分割点来降低预期的执行复杂度，因此总共有较少的查询。
    • 算法概述 ：从相信任何输入区域都同样可能包含到达目标的输入开始，我们的模糊算法根据每个甲骨文查询迭代地增加有希望区域的权重，并优先考虑在这些有希望的输入区域内的点上进行分割

2.3 通过蒙特卡洛计数的噪声计数Oracle

  • 因为input region的大小往往远远大于可以达到target的输入的个数，所以直接应用蒙特卡洛近似的话，很多input region的达到target计数会近似为0，这样会导致模糊器更难识别哪个input region更有可能含有可以到达target的inputs
  • 利用CFG结构进行计数

疑问

二进制搜索（binary search）是个啥玩意儿，翻翻参考文献