逆向与漏洞挖掘实验室，点击蓝字关注

浅谈并行化模糊测试技术

      模糊测试是漏洞挖掘领域中一种有效的动态检测方法。AFL将基于边缘覆盖率引导的遗传算法与模糊测试相结合，使模糊测试的检测效率提高到了一个新的高度。自从模糊测试技术诞生开始，研究者们对模糊测试技术进行改进的脚步就从来没有停止过，结合符号执行改进种子的生成技术，结合污点分析改进模糊测试的变异机制，识别低频路径等等。但是，当前关于利用并行化的方法提高模糊测试效率的公开研究目前还比较少，在实际的产业应用中，模糊测试常常以并行化的方式工作。并行模糊测试架构常常可以解决单一模式下所无法解决的问题，并行模糊测试架构的最大的一个特点是可以提供实现多种机制共同作用的解决方案，例如多种引导机制的并行、不同模块的拆解与并行、多种变异策略的并行和不同种子优先级排序机制的并行等等。所以，对于模糊测试并行化的研究还是很有意义的。

      以并行模式运行模糊测试是测试实际程序的常见方式，许多广泛使用的模糊测试工具支持并行模式，如 AFL[1]、libFuzzer[2]、honggfuzz[3]等，通过共享种子来协调不同并行节点之间的测试过程。这些工具中，最出名的是谷歌公司的OSS-Fuzz[4]模糊测试平台，据了解谷歌公司为该平台专门建立发电厂，支持2万多个甚至更多的分布式节点的并行化运行，该平台在5个月内用数千台虚拟机发现了1000多个bug，从这方面也可以看出谷歌公司也较为看重并行模糊测试。ClusterFuzz[5] 是OSS-Fuzz背后的分布式模糊测试基础设施，可自动大规模执行由 libFuzzer 驱动的模糊测试并行节点。ClusterFuzz 最初是为对 Chrome 进行大规模模糊测试而构建的，它集成了多个分布式 libFuzzer 进程，并通过语料库同步有效执行。ClusterFuzz 主要在分布式系统上为一个目标应用程序运行多个相同的 libFuzzer 实例，这些模糊测试实例之间没有差异。微软也建立了自己的的并行化模糊测试平台Project Springfield[6]，通过云的方式进行部署。

      接下来，我们主要介绍几项在该领域比较典型的研究成果，重点介绍（1）AFL的并行模式；（2）2018年的CCF A类会议文章PAFL: Extend Fuzzing Optimizations of Single Mode to Industrial Parallel Mode；（3）19年的顶会文章EnFuzz: Ensemble Fuzzing with Seed Synchronization among Diverse Fuzzers.

AFL并行模式

      AFL的并行模式和我们理解的传统意义的并行有很大区别，传统的并行是将一份任务进行划分，不同的并行节点执行不同的任务部分，将处理任务的时间并行从而缩短完成一项任务的时间，而AFL的并行模式只是简单的将并行节点之间的种子进行共享，并没有其他多余的工作，虽然简单但是却很有效，图1即为AFL并行模式的结构框图：

图1 AFL并行模式的结构框图

      AFL并行模式之所以有效是因为对于AFL来说非确定性变异策略要比确定性变异策略更有效果，所有在真实的产业应用中甚至抛弃了确定性变异策略只执行AFL的非确定性变异策略。对于AFL的非确定性变异策略来说，由于其随机性较大，即使变异同一个种子，每次执行都会产生不同的测试用例，所以不同的并行节点变异相同的种子队列会大大增加生成的测试用例的多样性，这也是AFL并行模式的精妙之处。

      AFL并行模式的另一个巧妙的地方就是在并行节点之间共享种子的同时就会将不同节点的位图信息进行同步。基于此，各个节点之间就相当于基于同一张位图执行当前任务，不会因为共享到了其他节点的种子而该种子的路径信息得不到同步而导致该节点的种子队列出现了冗余的种子。之所以说这种思路比较巧妙，是因为如果利用其它手段进行位图同步则会带来更多的资源开销。

      AFL的并行模式提供了一种非常精妙的通过共享种子驱动状态信息同步的机制，是该领域的研究者们继续前行的基石。

PAFL

      PAFL并不是对AFL并行模式的改进，该文的作者抓住了AFLFast[7]和FairFuzz[8]这两种重点变异低频路径种子的模糊器存在的并行后效率降低的特点，完成了一项并行化低频路径种子模糊器的工作。其做法是通过共享内存的方式将统计路径频率的信息实现了并行节点间的同步，成功地将重点变异低频路径的思想融入到了并行化的模糊测试框架中。

      该文的另一个贡献是通过划分位图实现了同一测试任务的划分，实现的方法是先将位图划分为与并行节点数相同的几部分，然后记录每个种子击中次数最少的边，最后根据该边在位图中的位置决定该种子该由哪个并行节点执行变异。划分任务的做法减少了各个并行节点之间的重复任务。图2为PAFL的系统框图。

图2 PAFL系统框图

      PAFL本身也存在的一些问题，首先由于其使用共享内存技术实现信息共享，所以难以实现大规模集群化部署。其次，PAFL根据集中到的最稀有的边在位图中的位置进行任务划分，会存在各个节点之间负载不均衡的问题。PAFL提供了一种在不同的并行实例之间共享细粒度信息的方法，使重点关注低频路径的模糊测试工具可以实现并行化，推动了并行模糊测试技术前进了一大步，多机模式下细粒度信息的共享机制还需要后来者贡献自己的智慧。

EnFuzz

      EnFuzz给自己的定位并不是并行模糊测试，而是集成模糊测试，EnFuzz也是集成模糊测试的首作。就其核心思想来看，是比较简单的，就是将不同机制的各种模糊器集成在一起。虽然想法简单，但是要实现多种模糊器的集成，工作量是很大的。

      EnFuzz的出发点是考虑到不同的模糊器对于不同的应用程序表现不一样，并且也通过实验证明了这一点，将不同机制的模糊器并行在一起，或者说集成在一起，就可以弥补单个模糊器的不足。

      EnFuzz重点关注模糊测试的三方面多样性，分别是覆盖信息粒度的多样性、输入生成策略的多样性以及种子变异和选择策略的多样性。并且使用基于全局异步和本地同步（GALS）的种子同步机制实现了一个集成架构，以有效地集成多种基础模糊器。为了加强不同基础模糊器之间的合作，该机制定期将有趣的种子（即覆盖新路径或触发新崩溃的测试用例）同步到在同一目标应用程序上运行的所有模糊器中。在EnFuzz的实验中，集成了包含AFL、AFLFast、FairFuzz、QSYM、libFuzzer 和 Radamsa等在内的一系列工具。图3为EnFuzz的架构设计：

图3 EnFuzz的架构设计

      基于EnFuzz，研究者们又产出了两项不错的研究成果，分别是Cupid[9]和CollabFuzz[10]。Cupid通过收集和应用来自单个独立模糊器运行的经验数据，以自动识别一组在协作执行时相互补充的模糊器，允许自动、数据驱动地选择多个互补模糊器以进行并行和分布式模糊测试。CollabFuzz 的工作是控制将哪些测试用例分发给哪个 fuzzer，并允许跨网络编排不同的 模糊器。此外，它允许集中分析由其控制的各种模糊器生成的测试用例，根据分析的结果实施调度策略。

      EnFuzz并行了多种模糊测试工具，实质上是并行了不同种类的模糊测试机制，它的成功在于迈出了并行多种机制的第一步。

总结

      在本文中，我们简单介绍了并行模糊测试的研究现状，并重点分析了几个典型的并行模糊测试研究成果，希望对读者能有些许启发。在未来的工作中，我们也会重点研究并行模糊测试的理论与实际应用，推动软件动态测试与漏洞挖掘技术进一步的发展。我们认为，开发有效的同步机制来同步并行节点之间的状态信息，研究模糊测试中各种机制的多样性，应用更先进的并行算法改进并行架构，实现更加合理的资源分配机制，是未来工作中几个值得投入时间与精力的研究方向。

参考文献

[1] ZALEWSKI, M. American fuzzy lop. https://github. com/mcarpenter/afl, 2015.

[2]libfuzzer. https://llvm.org/docs/LibFuzzer. html, 2017. [Online; accessed 10-April-2018].

[3] 2016. Google. Honggfuzz. http://honggfuzz.com/. (2016).

[4] 2017. OSS-Fuzz: Five months later, and rewarding projects. https://security. googleblog.com/2017/05/oss-fuzz-five-months-later-and.html. (2017). [Online; accessed 16-May-2018].

[5] Clusterfuzz document. https://github. com/google/oss-fuzz/blob/master/docs/ clusterfuzz.md, 2018. [Online; accessed 2- November-2018].

[6] 2015. Microsoft Security Risk Detection ("Project Springfield"). https://www. microsoft.com/en-us/research/project/project-springfield/. (2015). [Online; accessed 26-January-2018].

[7] Marcel Böhme, Van-Thuan Pham, and Abhik Roychoudhury. 2016. Coveragebased greybox fuzzing as markov chain. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. ACM, 1032–1043.

[8] Caroline Lemieux and Koushik Sen. 2017. FairFuzz: Targeting Rare Branches to Rapidly Increase Greybox Fuzz Testing Coverage. arXiv preprint arXiv:1709.07101 (2017).

[9]Emre Güler, Philipp Görz, Elia Geretto, Andrea Jemmett, Sebastian Österlund, Herbert Bos, Cristiano Giuffrida, and Thorsten Holz. 2020. Cupid : Automatic Fuzzer Selection for Collaborative Fuzzing. In Annual Computer Security Applications Conference (ACSAC '20). 

[10]Emre Güler, Philipp Görz, Elia Geretto, Andrea Jemmett, Sebastian Österlund, Herbert Bos, Cristiano Giuffrida, and Thorsten Holz. 2020. Cupid : Automatic Fuzzer Selection for Collaborative Fuzzing. In Annual Computer Security Applications Conference (ACSAC '20). 

扫码关注我们

每天有最新消息