基本信息
原文名称 UltraFuzz: Towards Resource-saving in Distributed Fuzzing
原文作者 Xu Zhou；Pengfei Wang；Chenyifan Liu等
原文链接 https://ieeexplore.ieee.org/abstract/
document/9939114
发表期刊 IEEE Transactions on Software Engineering (Volume: 49, Issue: 4, 01 April 2023)
一、 引言
模糊测试是目前最为有效的漏洞挖掘技术之一，它通过生成大量的随机测试用例来运行目标程序，监控运行时crash以报告漏洞。目前提高模糊测试效率主要有两种方法，一是设计新颖的算法优化模糊测试核心机制（种子生成、变异策略、种子调度等），二是利用并行计算资源并发地处理模糊测试。在理想情况下，并行模糊测试提升效率远大于修改模糊测试机制，但大多数研究只关注提升效率以节省时间，忽略了不断增加的测试资源成本。现实世界中的并行模糊测试不仅仅是计算资源的堆积，大规模分布式环境中的并行模糊测试也会放大资源消耗问题。本文分析出了分布式模糊测试导致资源浪费的三个原因：
（1）工作节点之间缺乏全局调度和fuzz状态及时更新，不同模糊测试实例可能会使同一种子发生变异，产生执行同一路径的冗余测试用例，导致任务冲突、资源浪费。这是资源浪费的根本原因。
（2）为了减少任务冲突，需要对不同模糊测试实例生成的新种子进行评估和冗余删除。在模糊测试和种子评估之间不适当的计算能力分配也会限制模糊测试过程、造成资源浪费。
（3）当每个计算core的计算能力不一致或计算core数量动态变化时，不灵活的任务调度会导致工作负载不平衡，从而导致资源浪费
本文首次研究了分布式模糊测试中的资源节约问题。总结了分布式模糊测试可能导致资源浪费的三种情况，并提出一套基于动态集中任务调度的解决方案，实现即时模糊状态同步、全局能量调度、弹性计算资源分配，避免任务冲突、工作负载不平衡、种子评估瓶颈等问题，减少资源浪费。依据论文设计实现UltraFuzz，并在大规模实验中进行评估。
二、 并行模糊测试
并行模糊测试首先由一种朴素的方法，即AFL的并行模式(AFL-p)演变而来，简单地同时运行具有相同目标的多个fuzzer实例。AFL的每个实例绑定一个核心，并定期重新扫描顶级同步目录，查找在其他实例中发现的任何测试用例。这个阶段的并行效率受到机器内部的性能限制。分布式并行模糊测试将机器内并行扩展到通过网络连接的多台机器，允许使用更多的计算资源。在这种模式下，程序开始在fuzz实例之间调度任务，以缓解任务冲突。为了优化并行模糊测试以节省资源，需要面临以下技术挑战：
（1）任务冲突。并行模糊测试中，由于实例之间缺乏全局调度和fuzz信息及时更新，不同fuzz实例可能会变异相同种子或生成执行同一路径的冗余测试用例，从而导致任务冲突，严重浪费测试资源。虽然P-fuzz和PAFL试图在模糊实例之间同步模糊信息，但仍然需要一个集中的调度方案来从全局角度优化并行模糊测试。
（2）同步开销。并行模糊测试中，可以在fuzz实例间共享各种信息(种子、覆盖率、hang、crash)以提高性能。然而同步开销不可避免地会降低性能，随着实例增加问题会更加严重。因此，共享什么信息以及如何共享信息是至关重要的。
（3）算力分配。将fuzz任务分配到不同的实例时，计算能力的分配是另一挑战。AFL-P和PAFL为主机内多核并行fuzz，假设所有core的算力相等，为每个core分配相同的工作负载。然而对于分布式模糊测试环境，每个core算力可能不同，其数量可能动态变化，静态策略可能会加剧工作负载不平衡。
本文提出一种集中式动态调度方案来解决任务冲突问题，采用基于模糊测试信息特征的分层方案提高了同步效率，使用动态按需调度方式调度模糊任务以解决计算能力动态变化导致的工作负载不平衡。最后，针对种子评估请求的急剧增加，采用了弹性计算能力分配方案，自适应协调两组实例，实现资源分配全局优化。具体的设计下文会详细阐述。
三、 设计
01 集中式动态调度
本文从种子选择、能量调度、fuzz状态同步、任务调度等方面，提出了集中式动态调度的全局优化方案。如图1所示，模糊测试框架由调度器、数据库、fuzz实例、评估实例四个组件组成。组成分布式系统的计算节点中，选择一个为主节点，其余为工作节点，进行fuzzing或种子评估。
图 1 集中式动态调度概述
在主节点，设计调度器，用于调度种子评估、对队列中种子进行优先级排序、处理来自fuzz实例的请求、调度fuzz任务。fuzz任务包含两种信息：种子的索引(hash值)和种子变异次数(能量)。同时，部署数据库，用于存储和共享fuzz数据(种子、fuzz状态、覆盖率等)。每个fuzz实例连接到数据库以同步fuzz信息和种子，同步方案使用后文所述的即时分级同步机制。
对于工作节点，它既可以作为fuzz实例，也可以作为评估实例。fuzz实例用于运行测试用例、变异种子。它从数据库下载调度器分配的任务种子，将新种子上传到数据库。评估实例用于过滤掉重复的种子、使fuzz实例下载唯一的种子。两者都连接到调度器和数据库，调度器将相应任务分配给对应实例。考虑到新种子的数量可能发生巨大变化，评估实例和fuzz实例的角色可以根据评估任务的需求动态切换，从而减轻种子评估潜在的过度负担，实现最佳性能。
从调度器的角度来看，每当fuzz实例发现一个新种子，将其存储在数据库并由评估实例进行评估。调度器根据发现的时间对种子队列中的种子进行排序，根据其fuzz状态(种子重要性和fuzz次数)分派fuzz任务。种子选择和能量调度方案仍然按照AFL原始策略进行。
02 按需任务调度
模糊测试通过动态按需模式进行分配。每个fuzz实例在空闲时会向调度器请求一个fuzz任务。调度器根据请求时间将请求存储在队列，选择最高优先级种子，使用任务规范响应请求队列前端的fuzz请求。只有fuzz任务被请求时，才会选择种子，并由调度器计算和分配能量。当前任务即将结束(当前种子最后一次执行开始)时，fuzz实例将请求一个新任务。一旦分配新任务，fuzz实例将继续完成当前任务，随后切换到新任务(节省等待时间)。在该方案下，工作量自动平衡，重要的任务优先完成。这种动态任务调度较为灵活，能够适应测试环境的变化。例如，如果增加或减少测试主机，按需任务调度方案可以自动适应新主机，并根据新主机数量调度任务。
图 2 按需任务调度程序
任务调度由主节点中的调度器处理。如图2所示，整个过程以调度器从数据库下载种子并在种子队列中对它们进行优先级排序开始。空闲的fuzz实例向调度器请求fuzz任务，调度器用任务规范响应排序后的请求。通过种子索引，fuzz实例从数据库中下载种子并进行模糊测试。当接收一个新的种子时，fuzz实例将它上传到数据库。同时，调度器根据待评估的种子数量安排评估实例。评估实例从数据库中下载种子，以过滤掉重复项并从数据库中删除它们。
03 即时分级同步
并行模糊测试中不同fuzz实例之间的状态同步是一大难题。UltraFuzz使用数据库代替文件系统同步fuzz信息，这是因为基于文件的同步在主机间模式较难拓展。主要同步三类信息：种子、fuzz状态(种子重要性和fuzz次数)、覆盖率。根据每种信息类型的特点，文章提出一种分层fuzz状态同步方案。
（1）Fuzz状态直接同步
Fuzz状态主要由种子被fuzz的次数来评估，包括depth—从初始种子到该种子的遗传代数；handicap—队列已经执行的fuzz循环数；bitmap_size—用于变异的种子的位数。Fuzz状态和种子一起存储在数据库，但有很大不同：
种子大小一般是几KB或更多，而fuzz状态要小很多。
种子由fuzz实例使用，可以增量地更新；而fuzz状态只有调度器使用。
当种子被写入数据库时，它们是不变的；但每次种子被fuzz时，fuzz状态会更新，其更加频繁。
因此，对于这种轻量级且经常使用的数据，直接通过数据库共享是可行的。调度器基于fuzz状态而不是种子分派任务，只维护一个轻量级队列对种子进行优先级排序。这将大大减少调度器在调度fuzz任务时的网络压力。
（2）种子缓存
由于种子是相对较大的常量，UltraFuzz使用本地缓存减少种子同步开销：
生成一个hash值，并将其作为识别数据库中的种子的索引。
在每个fuzz实例的内存中维护一个本地种子缓存。
每个fuzz实例都有一个分配给它的种子，在调度任务中，只从数据库中检索本地缓存没有的种子，缓存中存在的种子避免了重复种子。具体来说，修改了AFL中读取和写入种子的函数来重定向种子的访问：
引入本地映射，仅当种子在本地映射中不存在时才从数据库中下载。
种子编写器把种子上传到数据库，同时在本地映射中进行复制。
放弃每个fuzz实例中的本地种子的种子队列，将调度方案移动到调度器。
（3）覆盖率广播
在AFL中，覆盖率信息通过压缩为高密度原始数据bitmap来表现，其变化迅速且频繁。例如，AFL可能在每次执行测试用例时改变bitmap。UltraFuzz不会在所有fuzz实例之间直接更新覆盖率信息，这是因为当多个实例同时更新覆盖率信息时，很容易引起冲突。反之，采用集中的方式同步覆盖率信息：
在主节点维护一个全局bitmap，以接收来自本地fuzz实例的覆盖率更改，并将新的覆盖率信息广播回给它们。
每次本地fuzz实例发生bitmap更改，只会通知全局bitmap，而不是与所有实例同步。
在全局bitmap更新之后，将此更新广播到所有本地实例。实例将全局bitmap复制到本地以完成更新。
当多个实例并发地更新全局bitmap时，更新是在字节级的。这种方式可以显著降低bitmap更新冲突的可能性，过程快速高效。
（4）即时同步
UltraFuzz采用即时同步：每当一个新的种子和它的fuzz状态被发现并上传到数据库，所有fuzz实例都可以立即访问它们；每次全局bitmap覆盖率更新时，一旦fuzz任务完成，fuzz实例中的本地bitmap会相应同步。
04 弹性种子评估计算能力分配
分布式模糊测试环境中，不同fuzz实例可能同时生成重复种子，包括相同的种子和执行相同路径的种子。因此，每次产生新种子时，需要评估新种子以过滤重复种子。然而，当大量种子需要评估时，集中的任务调度可能成为一个瓶颈，且新种子数量分布不均匀。
UltraFuzz设计了单独的评估实例模块，根据要评估的种子数量进行弹性调整。
当fuzz实例向数据库上传新种子，调度器收到更新信号，启动一个评估线程删除重复的种子，当没有新种子时，终止这个线程。同时，若有大量新种子涌入调度器，调度器会移动一些fuzz实例临时评估这些新种子以减轻负担。
图 3 弹性种子评估计算能力分配
调度器每隔一段时间检查未评估的种子数量，并调整评估实例数量。
以下是上图算法中的一些参数定义：
eval_instance_num取值为seeds_to_evaluate除以evaluate_speed，是一个动态统计值，基于每秒评估的种子平均数。
unique_rate作为先前重复数据删除性能的估计，以预测将删除多少重复种子，帮助调整评估实例数量。unique_rate也被用作启发式阈值以限制评估实例的数量。为了有效使用资源，eval_instance_num不能大于unique_rate/2，否则评估实例会过剩。
如果在seed_to_evaluate中接收到的新种子超过threshold，实例会重新分配。threshold初始值为1000，即每1000次更新(接收1000个新种子)重新分配实例。当需要评估的种子过多，会将频率缩短为shreshold/2；反之加倍。
评估实例会删除重复的种子。对于相同的种子，依据种子的hash值删除；对于执行路径相同的不同种子，依据执行路径checksum删除；对于执行路径相同且校验和不同的种子，使用bitmap比较覆盖率范围，删除不提高覆盖率的种子，保留其余种子。
四、 实验设计及结果
（一）实验目标
实验阶段主要通过针对以下两个问题来验证UltraFuzz的性能：
（1）RQ1：UltraFuzz采用的技术是否有效地节省资源？
（2）RQ2：分布式模糊测试能从资源节约中得到什么好处？
（二）实验设置
使用16个被广泛使用的现实世界程序进行测试，选择AFL、PAFL、EnFuzz和UltraFuzz进行对比测试。对于不支持主机间模式的工具，通过延长测试时间扩大实际试验规模。计算资源是计算机核心、测试时间、主机数的综合值，一单位的计算核心定义为1核乘以一个小时乘以一台主机。
图 4 被测目标配置和计算资源分配
具体实验使用UltraFuzz、PAFL、EnFuzz和AFL-P分别对8、16、32、64、128个计算资源单位的每个程序进行模糊测试。每个实验重复10次减少随机性。实验在8台32核Intel(R) Xeon(R) CPU E5-2620 v4 @ 2.10GHz机器上进行，运行64位CentOS Linux release 7.7.1908 (Core)系统。
（三）具体实验
01 资源节约的有效性
本实验使用两个标准评估资源节约有效性，除了经典的覆盖率度量外，定义了路径成本(path cost)作为度量。
（1）覆盖率
下图绘制了不同工具在使用不同计算资源的10次运行中发现的平均分支覆盖率。
图 5 使用相同计算资源的不同工具到达的分支覆盖率比较
可以发现，UltraFuzz在大多数程序中达到最高覆盖率。虽然基于相同的计算资源比较，但由于主机内的限制，PAFL和EnFuzz比UltraFuzz运行的内核更少，但时间更长，这减轻了大规模并行的开销。从这个结果，推断出UltraFuzz优于其他工具的原因在于并行架构的优化。
（2）Path Cost
将路径成本定义为生成的测试用例数量除以fuzz过程中发现路径的数量。其代表找到每条路径时消耗的测试用例平均数量。路径成本可以反映测试用例的质量和Fuzzer的资源效率。
图 6 不同工具的平均路径成本比较
可以发现，每个工具的路径成本随着计算资源的增加而增加，相比较而言UltraFuzz具有最低的路径成本。
基于以上两个实验，可以得出结论，与其他工具相比，采用资源节约技术的UltraFuzz具有更好的资源效率，并且平均消耗更少的测试用例来寻找新的路径。
02 暴露漏洞
所有工具共检测到24个漏洞，其中UltraFuzz发现了20个，比其它5个工具都多。实验说明，UltraFuzz在发现漏洞方面的能量优于其他工具。
图 7 不同模糊器发现的漏洞
03 种子缓存有效性
为了证明UltraFuzz种子缓存机制的有效性，如下表所示，记录了缓存命中率和启用/禁用种子缓存时下载种子所花费的时间。种子下载时间增量在1.59~46.42倍之间，平均值为14.56倍，表明了种子缓存的有效性。实验表明，种子缓存机制在缩短种子下载时间方面是有效的，但性能受到种子特性（如种子大小）的因素影响。
图 8 种子缓存的有效性
04 弹性机制有效性
为了证明UltraFuzz评估实例的弹性机制有效性，使用已完成的模糊测试任务和实验时间作为度量。通过启动和禁用弹性机制，可以通过这两个度量显示弹性机制有效性。如下表所示，当弹性机制被禁用，大部分模糊测试任务完成数减少，实验时间增加。实验表明弹性机制在大多数情况下都有助于提高UltraFuzz的效率。
图 9 弹性机制的有效性
五、 总结
本文针对分布式模糊测试的资源节约问题，叙述了UltraFuzz的设计和实现。UltraFuzz对种子选择、能量调度、主机间状态同步、任务调度等各方面进行全局优化，可以克服任务冲突、负载不均衡、同步开销、计算核动态变化等挑战。
UltraFuzz只针对并行方案来提高模糊测试的性能，种子调度、变异方法等方面依旧采取AFL原始策略，可以针对这些方面进行优化以改进UltraFuzz。
参考文献
1.
Zhou X, Wang P, Liu C, et al. UltraFuzz: Towards Resource-saving in Distributed Fuzzing[J]. arXiv preprint arXiv:2009.06124, 2020.
2.
Michal Zalewski. American Fuzzy Lop (2.52b). http://lcamtuf.coredump.cx/afl, 2019.
3.
Liang J, Jiang Y, Chen Y, et al. Pafl: extend fuzzing optimizations of single mode to industrial parallel mode[C]//Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering. 2018: 809-814.
4.
Chen Y, Jiang Y, Ma F, et al. EnFuzz: Ensemble Fuzzing with Seed Synchronization among Diverse Fuzzers[C]//USENIX Security Symposium. 2019: 1967-1983.
5.
Österlund S, Geretto E, Jemmett A, et al. Collabfuzz: A framework for collaborative fuzzing[C]//Proceedings of the 14th European Workshop on Systems Security. 2021: 1-7.
如有侵权请联系:admin#unsafe.sh