ISSTA 2023 Rare Path Guided Fuzzing 论文阅读

Rare Path Guided Fuzzing

Abstract

从随机的初始种子开始，模糊器搜索触发bug或漏洞的输入。然而，模糊器经常无法生成由限制性分支条件保护的程序路径的输入。在本文中，我们表明，通过首先识别程序中的稀有路径（具有不太可能被随机输入生成满足的路径约束的程序路径），然后生成触发稀有路径的输入/种子，可以提高模糊工具的覆盖率。特别是，我们提出的技术1）识别稀有的路径使用符号分析，和2）生成输入，可以探索这些稀有的路径，使用路径引导的concolic执行。我们提供这些输入作为初始种子集，在三个最先进的模糊器进行实验。我们的实验评估的一组程序表明，稀有路径为基础的种子集相比随机初始种子，实现更好的覆盖率。

Introduction

提出了一个轻量级的白盒分析，以确定在程序中的稀有路径，然后引导符号执行，以产生输入。

我们提出了一个启发式识别稀有的路径，我们使用控制流分析，依赖性分析和模型计数分支约束，转换控制流图为概率控制流图。然后，估计路径概率并遍历概率控制流图，并确定稀有的（低概率）路径。我们使用稀有的路径指导concolic执行，以生成触发罕见行为的输入。作为方法的最后一步，提供分析所产生的输入集作为初始种子集的模糊。这使得模糊器能够立即探索稀有路径，从而与随机生成的初始种子集相比，获得更好的覆盖率。我们的方法只依赖于初始种子，可以与所有现有的模糊器进行整合。

本文中的贡献如下：·一种方法，用于估计路径概率，以识别程序中的稀有路径，使用轻量级定量符号分析。·一种新型的控制流路径（II路径），以提高稀有路径分析的效率和有效性。·用稀有路径引导的concolic执行的算法。·稀有路径引导的模糊化方法，其中给定模糊器的初始种子集是利用稀有路径分析生成的。·在现有模糊器AFL++、FairFuzz和DigFuzz上对所提出的技术进行实验评估，证明了通过所提出的稀有路径引导的模糊方法实现了覆盖率改进，甚至不修改模糊器。

考虑图中的运行示例。它是libxml2中代码结构的缩短版本。程序的主过程读取字符串作为参数。它检查字符串的前3个字符是否是DOC。如果字符串的前3个字符是DOC，则从第4个字符开始解析字符串。首先，它进入parse_cmt过程，检查第四个字符是否是< or >，如果是则跳过。然后，程序返回到main过程并进入parse_att过程。在parse_att过程中，程序查找字符序列ATT。如果它找到了这个序列，它会更深入地进入程序并执行更多的功能。总而言之，程序试图找到两个特定的字符序列：首先是DOC，然后是ATT，如果它能找到这两个序列，它就能执行更多的功能。
1.Path

表1中的路径1至5对应于main函数CFG的所有内部路径，表1中的路径20至43是基于图1所示的控制流图的整个程序的IP-CFG的所有过程间路径。

让我们考虑图1所示的EIP-CFG的路径（在表1中列出）。正如前面提到的，表1中的路径1到5是过程main的所有内部路径，表1中的路径20到43是程序的所有过程间路径。注意，基于II-路径定义，这些路径也是II-路径。此外，使用II路径定义，除了从1到5和从20到43的II路径之外，我们现在有从6到19的附加II路径，其中从6到13的路径忽略parse_cmt内部的控制流，但考虑过程parse_att内部的控制流，从14到19的路径忽略parse_cmt内部的控制流。但是考虑过程parse_cmt内部的控制流。

2.识别稀有路径

顶点2与分支条件CUR[0] = D相关联。认为输入是均匀分布的，字符串中的每个字符的域有256个值。顶点2处的分支条件的分支选择性S为1/256 = 0.004。因此，边2 → 3的概率为0.004，边2 → 10的概率为1 - 0.004 = 0.996。

3.生成输入

算法2中的第1-5行生成具有随机输入的初始路径tc，并且使用函数Overlap计算tc和tr之间的初始重叠。第6-19行中的while循环迭代tc中的节点。它在tc中查找与tr中相应分支节点不同的分支节点。函数Differ在两个条件下返回真：1）在tr中存在对应于tc（index）的相补的分支（即，tr和tc对于相同的分支语句采取不同的分支），或者2）在tr中没有对应于分支tc（index）的分支（TC中的该分支节点对应于在TR中未探索的过程中的分支）。在这两种情况下，我们否定tc（index）处的分支条件，看看是否可以改善tc和tr之间的重叠，如果重叠可以改善，则更新input和tc。注意，如果不能改善重叠，则输入恢复到行17-18中的先前输入。算法2中对分支进行单次传递而不进行回溯，因此不能保证找到最大化重叠的输入。寻找最大重叠需要搜索所有执行路径，从而导致路径爆炸，这是为了可伸缩性，必须避免的。

实验

使用concolic执行工具CREST和底层程序转换工具CIL提取程序的分支条件和控制流图。为了从程序中收集分支条件，我们修改了CIL中的OCaml代码。我们将分支条件转换为SMT-LIB格式的约束。为了识别依赖于输入的分支，使用CodeQL执行依赖分析，CodeQL是一个代码分析引擎。为了收集边覆盖(edge coverage)，使用afl-showmap。

1.可以使用从稀有路径分析中生成的种子集来提高基于突变的模糊效果吗？

2.与基于采样的混合模糊器相比，稀有路径引导模糊能实现更好的覆盖率吗？（ps：作者自己用afl++和qsym实现Digfuzz）

3.使用II-路径可以提高稀有路径分析的有效性？

结论

在本文中，提供了技术来识别稀有的程序路径，为了识别罕见的路径，使用轻量级的静态分析。我们使用所识别的稀有路径来引导concolic执行工具生成可以执行这些稀有路径的输入。最后，提供这些输入作为初始种子集到模糊器。在3个不同的基准集上进行实验评估，我们的方法可以得到模糊器不能通过突变产生的输入。相比初始的随机种子，分析产生的输入指导现有的模糊器，实现了更好的覆盖率。

成可以执行这些稀有路径的输入。最后，提供这些输入作为初始种子集到模糊器。在3个不同的基准集上进行实验评估，我们的方法可以得到模糊器不能通过突变产生的输入。相比初始的随机种子，分析产生的输入指导现有的模糊器，实现了更好的覆盖率。