论文阅读笔记——PathAFL：Path-Coverage Assisted Fuzzing

---

前言

  此博客为PathAFL：Path-Coverage Assisted Fuzzing论文的阅读笔记，本篇论文提出了一种新的跟踪执行路径的方法、路径过滤算法和追踪执行路径的方法，以提高Fuzz的准确性以及Fuzz性能。本文将会从解决的问题和目标、技术路线、达到的效果和结论四个角度来分析本篇论文。以下就是本文的全部内容。

---

PathAFL：Path-Coverage Assisted Fuzzing

1、解决的问题和目标

  现有的覆盖引导fuzzer通常使用所探索的基本块或边的数量来测量代码覆盖，路径覆盖可以提供比基本块和边缘覆盖更准确的覆盖信息。然而，路径的数量随着程序大小的增加而呈指数级增长，几乎不可能追踪真实世界应用程序的所有路径，这也是本文亟待解决的问题。针对此问题，本文完成了以下几个目标：

1. 作者提出了一种新的跟踪执行路径的方法，并在跟踪路径覆盖粒度和fuzzing性能之间进行了权衡。研究发现，作者可以用很少的开销来追踪重要的路径
2. 作者设计了一种路径过滤算法，它对新的路径做出了快速的判断。只有那些满足特定条件并具有高权重的路径才会添加到种子队列中
3. 作者提出了一种追踪执行路径的新方法，并在追踪路径覆盖的细粒度和模糊性能之间进行了权衡。研究发现，作者可以在几乎没有额外开销的情况下追踪重要路径
4. 作者开发了PathAFL的开源实现，并将其作为AFL的分支发布在Github上

2、技术路线

  关于PathAFL的工作过程如下图所示（紫色的组件显示了作者对原始AFL的改进）：

由上图可知，PathAFL是在AFL的基础上进行改进的，而AFL的整个工作流程如下所示：

1. 对目标应用插桩
2. 向种子队列提供初始输入
3. 选择种子。AFL根据种子选择算法从种子队列中选择一个种子，该算法更喜欢更快、更小的种子。种子选择算法采用贪婪算法实现，如下图所示：
   
4. 变异种子。该步骤使用多种变异算法对种子文件进行变异，并在循环中生成大量测试用例
5. 测试和跟踪。此步骤以测试用例为输入，执行并跟踪插桩指令的目标应用程序
6. 报告崩溃。如果发现崩溃，则可能触发了潜在的漏洞
7. 识别种子。如果发现新的边缘覆盖状态，则将测试用例添加到下一个循环的种子队列中
8. 如果该种子的fuzzing结束，则转到步骤(3)，否则转到步骤(4)

  需要注意的是，整个fuzzing处理过程是一个无限循环，只有在手动终止时才会结束循环。此外，因为AFL使用哈希计算来存储边缘覆盖信息（需要通过在每个BBL中插入一个BID随机数来进行哈希计算），不过这样会存在哈希冲突的问题（哈希冲突率通常在30%~70%范围内浮动）。为了解决这个问题，AFL又发展为了CollAFL，CollAFL使用新的哈希计算来存储边缘覆盖信息，这样可以让哈希冲突降低到接近0%（不过CollAFL只使用了边缘覆盖）。此外，CollAFL还遵循以下三个新的种子选择策略：

9. 具有更多未受影响的相邻分支的种子将优先进行fuzzing处理
10. 更喜欢有更多未受影响的邻居后代的种子
11. 更喜欢具有更多内存访问操作的种子

  现在我们对AFL和CollAFL已经有了较深的理解，不过上面提到的这两种技术的覆盖率信息又是什么东西呢？覆盖率信息可以看作是评判fuzzer的能力的一项指标，覆盖率越高，说明fuzzer探索到的路径越多，故越有可能发现漏洞；反之则说明覆盖率越低，说明fuzzer探索到的路径越少，故越没有可能发现漏洞。目前测量代码覆盖率的方法主要有三种：

12. $BBL$覆盖率（基本块覆盖率）：$BBL$是一个有一个入口和一个出口点的代码片段，BBL中的指令将按顺序执行，并且只执行一次。$BBL$是程序执行的最小相干单元，可以通过第一条指令的地址来识别。通过代码插入和静态分析可以很容易地提取BBL信息。由于这些优点，$BBL$覆盖信息被fuzzer广泛使用。而典型的基于$BBL$的覆盖引导fuzzer只跟踪每个块是否被击中，而不跟踪fuzzing过程中哪些块被击中的顺序，因此详细信息会丢失。如下图所示，在fuzzing过程中，如果首先执行程序路径$1（A，B，C，D）$，则与程序路径$2（A，B，D）$相关联的测试用例将永远不会添加到种子队列中，因为路径$2$没有命中新的$BBL$，因此边缘$BD$的信息将丢失。
    
13. 边缘覆盖率：为了解决$BBL$覆盖的缺点，边缘覆盖跟踪每条边缘是否被击中。在上图的例子中，如果首先执行程序路径$1（A，B，C，D）$，fuzzer将记录边缘$AB$、$BC$和$CD$，当执行路径$2（A、B、D）$时将记录新的边缘$BD$，因此与路径$2$相关的测试用例现在将添加到种子队列中。然而，边缘覆盖并不能追踪边缘被命中的顺序，因此一些详细信息可能会丢失。我们使用下图中的简单程序和其控制流图来说明这个问题，该程序以$8$个字符作为输入。当输入为abcd**‼$或**cdef!!时，程序将崩溃。
    
14. 路径覆盖率：基于路径覆盖的方法跟踪整个执行路径，包括命中的顺序边缘，从而记录最丰富的信息。几乎不可能为真实世界的应用程序实现路径覆盖，因为程序中有太多的循环和条件，路径的数量会激增。海量路径将带来较大的运行时开销，并可能降低模糊处理的效率。为了克服这个问题，作者将新探索的路径分为两类：
    • 对于之前未触及的边，作者将其表示为$e-path$。$“e-”$表示路径有新的边
    • 所有边都已接触的路径，作者将其表示为$h-path$。$“h-”$表示路径有一个新的哈希
      关键问题是如何处理大量的$h-path$，作者的解决方案是，不将所有的$h-path$添加到种子队列，而只将那些高权重的$h-path$增加到种子队列。这是一种效率和追踪粒度之间的权衡。

  根据上文分析可以发现，目前主要的挑战是路径的数量随着程序大小的增加而呈指数级增长。因此，建议只向种子队列添加重要路径。根据这一思想，作者总结了路径覆盖辅助fuzzer的三个关键问题：

1. 如何识别$h-path$？
2. 如何减少$h-path$的数量?
3. 哪些$h-path$将被添加到种子队列？

2.1、如何识别$h-path$？

  静态插桩。AFL在编译时对目标程序进行插桩。插桩代码计算边缘哈希并更新边缘覆盖记录到共享内存中。PathAFL维护一个类似AFL的全局哈希表。表索引表示路径哈希，值表示路径是否被覆盖。PathAFL以类似的方式对目标程序进行插桩。它只在AFL原始插桩代码中插入了一小段代码来计算路径哈希。此外，PathAFL扩展了原始共享内存，以存储路径哈希值的4个字节。在程序执行期间，执行路径的哈希值会实时计算并追加到共享内存中。当程序运行完成时，执行路径哈希可用于确定是否已探索新路径。与AFL相比，PathAFL只在插入代码中添加了哈希计算函数，导致开销增加很少。

2.2、如何减少$h-path$的数量？

  PathAFL采用两种方法来降低执行路径的跟踪粒度，以便模糊器可以限制新$h-path$的数量：

1. 选择性插桩：AFL默认情况下对目标程序中的所有边缘进行检测，使我们能够跟踪几乎所有的执行路径。为了减少路径，PathAFL必须降低跟踪粒度，只检测部分$BBL$并跟踪到达新BBL或触发新错误的概率更高的路径。为了实现这个目的，PathAFL仅对一些函数进行执行路径的插桩。提出以下四个策略来选择关键函数（根据以下策略，可以有效地减少新发现的$h-path$的数量）：

   • 插桩较大的函数，默认为最大的$20$。因此，可以找到许多通过这些函数的$h-path$
   • 插桩具有内存操作的函数，例如函数名包含alloc/free的函数
   • 忽略太小的函数。类似于第一个策略，函数越小，代码越少
   • 对其他函数的$10$进行插桩

2. 哈希算法：作者采用了一个非常简单的方案，直接使用全加运算作为路径哈希算法，并以粗粒度的方式区分执行路径。哈希算法如下：
   
   $p$表示执行路径。$BS$表示所有插桩的基本块的执行序列。只需在现有的插桩代码中插入一个add汇编指令，对测试程序的运行效率几乎没有影响。哈希表的大小与AFL中的位图相同。请注意，此方法仅用于计算路径哈希，不影响 AFL 的原始边缘哈希计算。

2.3、哪些h-path将被添加到种子队列？

  为了进一步减少添加到种子队列的$h-path$的数量，设计了一种策略来确定是否向种子队列添加$h-path$：

1. 效率是一个关键因素
2. $e-path$比$h-path$更重要
3. 应该选择变异后更有可能接触到新边缘的$h-path$

  正如以下算法所示，作者设计了一种快速过滤算法来满足这些要求。

2.4、种子选择算法

  在AFL的原始种子选择算法中存在一个小问题。它虽然确保$F$（受青睐的种子集）覆盖所有探测到的边，但它并不能确保在一个fuzzing测试循环中测试的受青睐的种子涵盖所有已发现的边，此问题正如下面的算法所示。

  针对此问题，作者提出了一个新的种子选择算法，如下图所示。它修复了上述提到的缺陷，确保在一个模糊测试周期中测试的受青睐的种子将覆盖所有已发现的边。

2.5、资源调度

  PathAFL根据路径的权重实现新的资源调度，并将更多的资源分配给更高权重的路径。具体来说，它将所有路径按权重划分为六部分，每一部分都分配了不同的资源。

3、达到的效果

  作者使用IDA进行静态分析。编写IDAPython脚本来自动分析程序结构，获得边缘信息，并为目标程序生成数据文件。该文件记录所有边缘信息，作为PathAFL的输入，以计算路径权重。下表展现了关于静态分析的时间开销。

3.1、一个简单例子的结果（RQ1）

  此部分的实验用于回答RQ1，即“跟踪执行路径对于fuzzing是否可行？”。作者以第1.3节中讨论的例子作为测试用例，对其所有边进行了插装，以在使用PathAFL进行测试时计算路径哈希。结果显示在下表中。AFL和CollAFL-x在7天内未能触发崩溃，而PathAFL和PathAFL-np仅用了一个小时就触发了。此外，PathAFL和PathAFL-np分别在一天内触发了6次和8次崩溃。

  这个实验表明，PathAFL能够有效地识别$h-path$，并且使用$h-path$引导模糊测试是可行的。

3.2、代码覆盖率和崩溃测量（RQ2）

  此部分的实验用于回答RQ1，即“PathAFL的代码覆盖率有多好？”。在本次实验中，作者选择了如下几个流行的应用程序进行测试。

  下表显示了四个模糊测试工具探索的路径和边的数量。

  以上实验表明，PathAFL和PathAFL-np探索的路径数量几乎相同，但PathAFL探索的边的数量比PathAFL-np多。故认为PathAFL更好，可能触及更多的新代码分支。
  下图显示了10个实验中不同fuzzer随时间的增长的代码覆盖率的增长。

  这再次表明作者的解决方案是有效的。
  下表统计了触发的唯一崩溃的平均数量。

  此结果表明PathAFL在找到程序中存在的不同崩溃方面表现出色。
  总之，PathAFL在路径和边缘发现方面优于AFL和CollAFL-x。而且最好使用资源调度。这些实验证明，所提出的解决方案可以帮助提高路径和边缘覆盖率，并引发更多的崩溃。

3.3、LAVA-M数据集（RQ3）的结果

  此部分的实验用于回答RQ1，即“PathAFL的错误检测能力有多好？”。作者在LAVA-M数据集上对AFL和PathAFL进行了为期7天的评估。且对每个实验都进行了五次，并对所有发现的bug进行了计数。评估结果如下表所示。

  结果表明，与AFL相比，PathAFL发现了更多的错误。具体来说，PathAFL发现了AFL发现的所有错误。此外，PathAFL发现了base64中注入的所有漏洞，甚至发现了LAVA-M的作者没有列出的四个新漏洞。

3.4、发现现实世界中的漏洞（RQ3）

  作者选择了binutils、libav和libtiff进行实验，并使用PathAFL发现了许多严重的漏洞和几个bug（如下表所示）。

  所有的错误和漏洞以前都没有报告，可能会带来一些安全风险。作者联系了这些工具的开发人员，并提交了错误详细信息。

4、结论

  在本文中，作者辅助fuzzer进行路径覆盖，讨论了其中的一些挑战，并最终实现了一个名为PathAFL的新fuzzing系统。它采用了粗粒度的路径跟踪和快速过滤算法，可以有效地选择更高权重的$h-path$，大大增加了路径覆盖的数量。此外，作者还设计了一种基于路径权重的种子选择算法和资源调度。作者在几个不同的实验中对其进行了评估，结果证明 PathAFL 在改善边缘覆盖和发现更多唯一崩溃方面比AFL和CollAFL更为有效。在经过充分测试的程序中，PathAFL 发现了8个新的安全漏洞，分配了6个CVE编号。

---

总结

  以上就是本篇论文阅读笔记的全部内容了，读完这篇论文后，相信各位读者朋友也会认为本篇论文写的相当不错，当然，有些地方笔者可能也理解不深，欢迎各位读者朋友与我积极讨论。后面如果有时间，我会分享阅读本篇论文的心得体会！