WindRanger: A Directed Greybox Fuzzer driven by Deviation Basic Blocks
论文基本信息
发表年份：2022
发表会议或期刊（简称，CCF级别）：CCF A类会议 ICSE
论文标题（论文简称）：WindRanger: A Directed Greybox Fuzzer driven by Deviation Basic Blocks
论文一句话概述：提出了deviation basic block的概念，并利用它构造定向模糊测试。
工具开源于：https://sites.google.com/view/windranger-directed-fuzzing/
实验用的数据是unibench，开源于：
论文概述
定向模糊测试是一种安全测试技术，致力于探索程序中的特定的位置。为了获取定向性，DGF优先选择那些执行路径离目标位置更近的种子。因此，评估种子执行路径到目标位置的距离对于定向模糊测试来说很重要。第一个定向灰盒测试器，AFLGo使用静态分析来计算基本块距离，并且在执行的过程中累积执行过基本块的距离来计算种子离目标的距离。顺延AFLGo，后续的定向模糊测试都使用所有的基本块计算距离，并且只考虑了控制流信息。然而，不是所有的基本块都是同等重要的，就有一些基本块（deviation basic block）的执行路径已经开始偏离目标位置。
文章提出了一种名为WindRanger的技术，利用了deviation basic block来构造定向灰盒测试。为了识别deviation basic block，WindRanger不仅应用了静态可达性分析，也使用了动态过滤。为了构建定向模糊测试，WindRanger使用deviation basic block和他们相关的数据流信息来用于种子的距离计算，变异，种子选择，explore和exploit的切换。在3个数据集上使用了29个程序进行评估，实验结果表明WindRanger由于AFLGO，AFL和FairFuzz。而且还发现了1个在ffmpeg的0day漏洞。
研究背景
问题是什么？现有的定向模糊测试计算距离的时候考虑了执行路径上的所有基本块，而且只考虑了控制流信息。然而，不是所有的基本块都是相同重要的，因为有一些开始偏离目标位置的基本块要另作考虑。
意义是什么？能够更快到达目标，并泄露漏洞。
相关工作
相关工作分为三类：定向符号执行，定向灰盒测试，覆盖率导向灰盒测试。
定向符号执行使用协同程序信息来获取定向性，相比通用符号执行，能够有效地测试程序指定位置。然而，定向符号执行在真实程序中效果不好，主要是由于符号执行有严重的路径爆炸问题。
定向灰盒测试，AFLGo是第一个。计算种子的trace到目标的距离，然后应用到能量调度模块，对离的近的种子赋予更大的能量（变异更多次）。Hawkeye在AFLGo的基础上进行改进，主要改了三个部分，距离增强的能量调度，种子选择，选择性的变异。AFLGo和Hawkeye把所有的基本块都考虑进来来计算距离。WindRanger侧重于那些阻止输入到达目标位置的基本块，来提高定向模糊测试的效率。另外，FuzzGuard利用深度学习来过滤不能到达目标的输入。
此外，还有一些工作应用定向模糊测试到不同类型的目标点。Leopard使用程序指标来识别程序中的漏洞代码，并把他们设定为目标位置。Parmsan通过sanitizer插桩的位置来作为目标位置。Parmasan基于动态构造的CFG来计算距离。CAFL利用目标位置的顺序信息和数据条件来加强发现目标崩溃的能力。
覆盖率引导的灰盒模糊测试（CGF）致力于让模糊测试覆盖更多的代码。AFL是经典的CGF，使用覆盖率来引导种子进化。为了提高CGF的覆盖率，一个研究方向是帮助CGF求解程序中的条件约束。混合测试（Hybrid fuzzing）结合CGF和符号执行去加强CGF里的约束求解能力。几个其他的工作采用轻量化的方法来帮助约束求解。Steelix使用轻量的静态分析和二进制插桩来获取比较过程的信息，能够帮助CGF探索那些被魔法字节比较的路径。Angora使用梯度下降的输入搜索来求解约束。Greyone使用污点分析和数据流特征来指导fuzzing的进化。FairFuzz识别并标记那些影响输入覆盖稀有分支的字节。除了这些针对分支的研究，也有一些工作优化种子调度，检查特定类型的漏洞，或者自动生成fuzz的harness。虽然，这些工作和windranger的目标不一致，但windranger也会从这些技术中受益（比如约束求解技术）
原理
先看一个motivation example来了解deviation basic block（DBB）的基本原理。DBB实际上就是开始偏离目标点的那个基本块。比如对于种子A来说，21：1这个点就是DBB。因为他的子节点是不可达的。同理，种子B的DBB就是20：2，种子C的是15：1。
整体框架图如下所示，标有数字的是修改的地方。可以看到改了很多地方。
DBB识别
对于WindRanger来说，DBB是很重要的概念。首先，用静态分析找到潜在的DBB。然后，在fuzzing的过程中，WindRanger在执行路径中定位DBB，以及他们和潜在DBB的关系。
潜在DBB的定义如下，简单来说就是满足两个条件：
- 自身到目标存在可达路径
- 子节点到目标不可达
种子的DBB的定义如下，也是满足两个条件：
- 即在种子路径上，又在潜在DBB集合中的
- 所有可达的后继节点没有被种子执行
基于估算的污点分析
使用污点分析的目的是收集数据流信息，可以知道哪些字节会影响给定分支。然后数据流信息就存储在hashmap中，key是分支约束的基本块地址，值是影响分支约束的字节索引。下面的算法，展示了构造这样一个hashmap的过程。
对于一个种子和它的执行路径，首先提取分支约束相关的变量。然后对这些变量进行字节级的变异。有了这些变异后的输入后，windranger检查每个提取的变量是否在变异后发生了变化。如果变量的值变化了，windranger就会更新哈希表，告诉它，这个变异位置的种子会影响变量。
种子距离计算
种子计算距离公式如下，简单说就是只计算DBB到目标的距离。
然而，这还不够，再加上数据流信息，距离的计算公式如下：新增的变量是用来判断通过该约束的难易度。
难易度公式：有多少字节可以影响约束变量。越多就说明fuzzer需要满足的条件越多，也就越难。
数据流敏感变异
如果在exploitation阶段，会将和DBB约束变量相关的输入字节当作是高优先级的字节。
对于一个约束变量和它相关的输入字节，如果输入字节是连续的。Windranger就会检查变量和输入字节是否共享一个值。如果是的话，很有可能输入字节没有经过数据变换。这种情况下，就直接用比较指令的另外一个操作数来替代输入的相关字节。
种子选择
在exploitation阶段，windranger保留一个高优先级的队列。对于每个DBB，windranger会找到覆盖这个DBB的种子们。然后，windranger基于距离升序将种子排序。并将这些种子放在favored队列，把剩下的种子放在less favored 队列。当要选择下一个种子进行变异的时候，有很高的概率选择favored队列里的。
在exploration阶段，就和普通的CGF一样。选择那些能增加覆盖率的种子。
至于能量调度，就和AFLGO一样，使用的是模拟退火算法，只不过种子距离不一样。
动态切换exploration和exploitation
虽然DGF的目的是尽可能地快地到达目标，但是DGF仍然需要足够的覆盖率探索去避免陷入局部最优。AFLGO在这方面采取的策略是手动设定时间来区分exploration和exploitation阶段。这种方法需要对不同的程序有着很深的理解。为了解决这个问题，windranger采用动态切换的方式。
具体来说，windranger保留所有的DBB，放在一个全局的集合中。在利用阶段，当集合中的所有DBB都利用的足够了，windranger切换到探索阶段。决定DBB是否利用足够了的指标是DBB被执行了多少次。具体的公式如下，T是fuzzing过程的基本块集合。DDB被执行的次数大于某个常数v乘以基本块里的最小执行次数就够了。
至于探索阶段切换到利用阶段的话，如果windranger发现了新的DBB，就会切换到利用阶段。
需要注意切换过程只在windranger完成变异后发生。
具体实现
主要包含两部分。静态分析器和动态的fuzzer。静态分析器部使用SVF构造过程间控制流图。主要写了900行的C/C++代码。动态的fuzzer基于AFL，主要有1000行C代码。
实验结果及分析
实验方面主要针对以下四个问题：
- 到达目标点的能力有多强？
- 在复现目标漏洞方面的性能怎么样？
- 每个组件对总体性能的影响如何？
- 能否发现真实的漏洞？
数据集
使用以下三个benchmark：
- unibench：包含20个真实程序。从数据集中每个程序选4个目标，来评估不同技术到达目标的时间。
- AFLGo Test Suite是AFLGo挖到的0-day漏洞。这个数据集被用在很多工作里。
- Fuzzer Test Suite是Google提出的数据集。包含几个真实程序和漏洞信息，也广泛用在fuzzing的研究。
对比的技术：
- AFLGo：目前最先进的定向模糊测试技术。其他的hawkeye，fuzzguard没开源。
- AFL：经典的覆盖率导向的模糊测试
- FairFuzz：选择这个是因为FairFuzz也使用了估计技术来收集污点信息构造fuzzing。
评估指标：
- Time-To-Target：到达目标的时间。这个指标用来评估没有已知漏洞的benchmark上。
- Time-To-Exposure：触发目标漏洞的时间。用来评估有漏洞的benchmark。
RQ1：到达目标点的能力
现在暂时没有标准的数据集用来评估DGG到达目标的能力。为此，作者用unibench来构建评估TTT的数据集。
- 对于每个程序，先用AFL跑24h，重复10次，在每次跑的时候，记录每个基本块第一次到达的时间。
- 统计每个基本块的平均第一次到达时间。
- 基于平均值，使用四个时间指标来选择基本块。
RQ2 漏洞复现能力
作者发现在测试binutils的时候，冒出了很多其他的漏洞，但只有7个漏洞是用在实验里的。因此，作者用的是binutils 2.28，然后把对应的cve 反patch回去。就避免人工审计这些crash。这个思路其实被用在很多benchmark的构造上，比如magma，fixreverter。
RQ3 不同模块的影响
作者把每个改的地方都关掉了，然后测试了下性能。发现各个模块都提高了10%左右的性能。
论文总结
文章的核心思想是deviation basic block，然后围绕其在fuzz上做了一系列的优化。
自己的感受
读完论文后，自己的想法
time-to-target的benchmark的设计挺好的。没有数据集就自己造。
论文结构也很清晰明了，非常标准，感觉下次写论文的时候可以参考这篇论文写。
修改模糊测试的模块部分，也值得借鉴学习。
感谢作者开源了自己的工具，感觉能从代码中学习到不少东西。
论文有哪些优点和亮点
论文还有哪些问题没有解决
测试的大型程序还不是很多，可以看看大型程序上的效果如何。
有哪些启发，可以继续探索
- exploitation和exploration的切换在代码中是怎么实现的
- 种子选择是怎么实现的
- 执行路径分析