模糊测试经过长时间的发展，逐渐形成了适合不同领域的模糊策略，其中最为普适且有着较好测试效果的当属基于覆盖引导的模糊测试，其根据代码覆盖率对种子调度进行指导，切合实际测试效果给出指导，在很多领域均取得极佳的漏洞挖掘效果。但是基于覆盖引导的模糊测试受制于仪器开销等物理因素、执行路径爆炸等理论因素，得到的多为粗略覆盖信息。此处仅以最常见的AFL为例，AFL采用一张存有边命中数量的紧凑位图，通过静态分析获取覆盖率信息，但是随机生成的哈希算法却有可能时两条不同的边具有相同的哈希值，这就会知道在位图中二则的记录相同，如此统计出来的覆盖率精度必然有所损失。

考虑到AFL技术作为最基础的模糊测试技术，对各种现实程序有着较好的适应效果。论文在AFL技术的基础上对其在哈希冲突方面的问题进行优化，并由此引申出三种全新的模糊策略，这些在精度提高的覆盖信息上有着很好的效果。论文的贡献有以下几点：

覆盖引导的模糊器其漏洞挖掘效果很大程度上受到覆盖信息准确度的影响。由于在现实程序中跟踪所有路径覆盖时不可行的，主流方法主要考虑跟踪基本块覆盖率及边覆盖率。但是由边覆盖可以推导出块覆盖，反之则不然。

现实程序中的基本块一般可分为三类，根据其前置块（precedent）的数量先分为由多个前置块和单个前置块两种，再对多个前置块进行接下来的分析做进一步区分。之所以根据前置块数量区分，是由于从哈希算法给边分配哈希值的角度触发，对于多前置块，即多条如边的块，其处理方式与单前置块，单入边的块处理方式不同。

如式（1）所示，在对多前置块的基本快参数选取中由三个未定参数，其中y值同一程序取值相同，而x，z的值则通过遍历的方法，其判断条件为所有多前置块的基本块其参数选取均不同，在此基础之上，可以保证所有边的散列值不同，从而缓解哈希冲突问题。

图(2)在解析这些参数时，使用贪心算法来解析，对于其中不可解析的块，则将其归为不可解析块，按照式(2)再对其分配哈希值，

不可解析的块的参数分配是在可解析块结束后，构建一个哈希表，表中会筛选掉可解析快已经使用的哈希值，转而从未使用的哈希中选取唯一的哈希值给以不可解析快结尾的边，这一步操作均可在离线状态下完成，降低实验的时间开销。其思想如图3所示。

至此，所有多前置块都已被处理殆尽，还剩下的单前置块，这里根据前置操作中构造的FreeHashes表获取此时位图中还剩下的哈希值并按照式(3)赋给剩下的但前置块，这一步也可以通过离线操作完成。

三类基本块的处理方法中，由多前置块的基本块解析操作，遍历寻求参数均需要较大的开销，最终三者的时间开销方面如式(4)所示。

但是在现实程序中，三者的数量却区别极大，其中绝大多数为但前置块的Fsingle算法，一部分多前置块，可解析的Fmul算法，而剩下的Fhash算法对应的不可解析多前置块的情况只有极少数，几乎可以忽略不计，这也使得其带来的高昂计算成本在现实程序中的影响不大。

在拥有了准确的代码覆盖信息后，论文提出以下三个全新的模糊测试策略：

基于这样的三个思想，从以下三个角度提出全新的模糊策略。

（a）其执行路径有着多个未覆盖分支的种子

这里会按照式(5)给予那些未覆盖分支以权重，通过加权的方式来衡量这些种子提高代码覆盖，探索未覆盖领域的能力。此方法记为CollAFL-br。

式中IsUntouched()的值将根据边是否被覆盖表示为0（未覆盖）或1（已覆盖）。

（b）对于未覆盖分支的后代对提高代码覆盖的影响。

这里需先统计种子执行路径下的未覆盖分支，随后根据这些分支计算其后代的数量，对应式(6)为其赋予权重。

这个方法标识未CollAFL-Desc，其计算的权重Weight_Desc()是一个动态结果，其具体值随着模糊测试过程中，未覆盖边IsUntouched()值的变化而变化，但是考虑到每个未覆盖块的后代数量是确定的，这一步计算为静态值，即式(7)中的NumDesc(bb)。

该计算可以在离线情况下完成。

（c）关于高内存访问在漏洞挖掘中的影响。

这里从种子执行路径中的内存访问次数为加权目标按照式(8)计算，计算其是否有希望发现内存漏洞。

AFL在计算边命中信息时，采用的位图默认为64KB大小，对于哈希冲突问题，传统想法有扩大位图从而减小边碰撞概率，事实上，扩大位图确实在一定程度上缓解了碰撞问题。

如图4所示，在位图扩大到1MB以后，边碰撞比已经是一个较低的状态。但是需要注意的是，模糊器在获取到覆盖信息后，准备进行下一步指导种子调度等操作时，需要去查询位图获取边命中情况，这里就需要对位图进行遍历，倘若贸然地扩大位图，这给模糊器每次访问带来的时间开销将会是几何级增长。

图5显示出在位图扩大的过程中，所有程序的执行速度均大幅度下降，对比降低边碰撞比的收益和其带来的巨额时间开销，简单扩大位图的操作，是一种低收益的操作。哈希冲突对于代码覆盖精度的影响不能简单通过扩大位图去改善。

如图6所示，200个小时内，不同模糊器在11个应用程序上的探索路径总数上，CollAFL平均多找到了9.9%的路径，其中尤其是考虑未覆盖分支的模糊策略-br，其平均多发现了20.78%的路径。而和相对比AFL-fast，即优先考虑低访问次数的路径，CollAFL表现出更优的路径覆盖率，平均多找到8.45%的路径。

除了代码覆盖率，漏洞挖掘的效果很大程度上也要取决于特殊崩溃的发现，进而联系到发现的漏洞数量，二者大体是正相关的。

在衡量测试随机性时，选择对同一程序进行20次漏洞挖掘，分析其中多少次发现了漏洞，耗时多久，由此判断测试方法应对现实程序的测试随机性如何。

图8表明，在测试程序中，Exiv2的随机性最大，在其上的测试中CollAFL仍优于AFL技术，除了意外，多数程序上，CollAFL技术均能实现20此实验全部或基本上都挖掘到漏洞，且用时也较短。

论文研究了覆盖引导模糊器中覆盖误差的负面影响。作者提出了一种覆盖敏感模糊解决方案CollAFL，它解决了最先进的fuzzer AFL中的散列冲突问题，在保持低仪器开销的同时实现更准确的边缘覆盖信息。论文还提出三种模糊策略，经实验证明效果更优。