这是一篇来自于IEEE TDSC的文章分享，文章名为《Path Sensitive Fuzzing for Native Applications》。其关注点是模糊测试中代码覆盖这一环节的精确度，由此进一步去提高模糊测试的准确性。
浅谈背景信息
模糊测试经过长时间的发展，逐渐形成了适合不同领域的模糊策略，其中最为普适且有着较好测试效果的当属基于覆盖引导的模糊测试，其根据代码覆盖率对种子调度进行指导，切合实际测试效果给出指导，在很多领域均取得极佳的漏洞挖掘效果。但是基于覆盖引导的模糊测试受制于仪器开销等物理因素、执行路径爆炸等理论因素，得到的多为粗略覆盖信息。此处仅以最常见的AFL为例，AFL采用一张存有边命中数量的紧凑位图，通过静态分析获取覆盖率信息，但是随机生成的哈希算法却有可能时两条不同的边具有相同的哈希值，这就会知道在位图中二则的记录相同，如此统计出来的覆盖率精度必然有所损失。
考虑到AFL技术作为最基础的模糊测试技术，对各种现实程序有着较好的适应效果。本文在AFL技术的基础上对其在哈希冲突方面的问题进行优化，并由此引申出三种全新的模糊策略，这些在精度提高的覆盖信息上有着很好的效果。本文的贡献有以下几点：
01 证实了哈希冲突对于边覆盖信息的精确度有着极大的影响。
02 设计出解决哈希冲突的算法，同时保持低开销，高精度。
03 在提高了覆盖信息的精确度后，提出了新的模糊测试策略。
04 在本文的方法上衍生出两个变体，用于测试无源码的测试程序。
分析如今代码覆盖准确率低的源头何在
覆盖引导的模糊器其漏洞挖掘效果很大程度上受到覆盖信息准确度的影响。由于在现实程序中跟踪所有路径覆盖时不可行的，主流方法主要考虑跟踪基本块覆盖率及边覆盖率。但是由边覆盖可以推导出块覆盖，反之则不然。
如图所示，两个程序P1和P2,他们共享大部分边，但是其在函数foo中的子路径不同，他们的块覆盖完全相同，但是其边覆盖不同，比如其中的B1→C1仅存在于路径P1中。
因此本文的主要思想还是建立在考虑边覆盖来标识覆盖信息上，而主流的使用边覆盖的方法AFL，却面临着哈希冲突带来的覆盖信息误差大的问题。
哈希冲突问题的根源在于AFL在使用位图来跟踪应用程序边覆盖的时候，边使用随机的哈希值来标识，但是由于算法的随机性，两条不同的边可能具有相同的哈希值，这使得模糊器无法区分这样的两条边，最终导致覆盖信息不准确。
一直以来，AFL技术的显著漏洞挖掘效果，掩盖了其中覆盖信息精度极低的问题，甚至由部分程序，边碰撞率高达70%以上，提高覆盖信息精度给漏洞挖掘工作带来的收益是极大的。
为解决哈希冲突问题而具体情况具体分析
现实程序中的基本块一般可分为三类，根据其前置块（precedent）的数量先分为由多个前置块和单个前置块两种，再对多个前置块进行接下来的分析做进一步区分。之所以根据前置块数量区分，是由于从哈希算法给边分配哈希值的角度触发，对于多前置块，即多条如边的块，其处理方式与单前置块，单入边的块处理方式不同。
公式中的关键在于x,y,z三个参数的选取，其中y值同一程序取值相同，而x，z的值则通过遍历的方法，其判断条件为所有多前置块的基本块其参数选取均不同，在此基础之上，可以保证所有边的散列值不同，从而缓解哈希冲突问题。其伪代码如下。
如代码中显示，在选取参数时采用贪婪算法实现，但是其中会存在不可解析块，对此，在为其设计有针对性的哈希值分配方法。
这里需要注意的是，不可解析的块的参数分配是在可解析块结束后，构建一个哈希表，表中会筛选掉可解析快已经使用的哈希值，转而从未使用的哈希中选取唯一的哈希值给以不可解析快结尾的边，这一步操作均可在离线状态下完成，降低实验的时间开销。其思想如下图。
至此，所有多前置块都已被处理殆尽，还剩下的单前置块，这里根据前置操作中构造的Freehashes表获取此时位图中还剩下的哈希值，赋给剩下的但前置块，这一步也可以通过离线操作完成。
三类基本块的处理方法中，由多前置块的基本块解析操作，遍历寻求参数均需要较大的开销，最终三者的时间开销方面。
cost(Fhash) > cost(Fmul) > cost(Fsingle) ≈ 0
但是在现实程序中，三者的数量却区别极大，其中绝大多数为但前置块的Fsingle算法，一部分多前置块，可解析的Fmul算法，而剩下的Fhash算法对应的不可解析多前置块的情况只有极少数，几乎可以忽略不计，这也使得其带来的高昂计算成本在现实程序中的影响不大。
高精度覆盖信息所带来的全新模糊策略
在拥有了准确的代码覆盖信息后，本文提出以下三个全新的模糊测试策略：
1.对于一条路径，倘若有多个未被探索的分支，那么对该路径的突变可能会探索那些分支。
2.对于一条路径，倘若其未被探索的分支有多个后代，那么对该路径突变有可能会探索那些后代。
3.考虑到最终目标是提高漏洞挖掘效率，那如果一个路径有多次内存访问操作，对其突变可能触发潜在的内存相关崩溃，漏洞。
基于这样的三个思想，从以下三个角度提出全新的模糊策略。
（一）其执行路径有着多个未覆盖分支的种子
这里会给予那些未覆盖分支以权重，通过加权的方式来衡量这些种子提高代码覆盖，探索未覆盖领域的能力。此方法记为CollAFL-br。
图中IsUntouched()的值将根据边是否被覆盖表示为0（未覆盖）或1（已覆盖）。
（二）对于未覆盖分支的后代对提高代码覆盖的影响。
这里需先统计种子执行路径下的未覆盖分支，随后根据这些分支计算其后代的数量。
这个方法标识未CollAFL-Desc，其计算的权重Weight_Desc()是一个动态结果，其具体值随着模糊测试过程中，未覆盖边IsUntouched()值的变化而变化，但是考虑到每个未覆盖块的后代数量是确定的，这一步计算为静态值，即
该计算可以在离线情况下完成。
（三）关于高内存访问在漏洞挖掘中的影响。
这里从种子执行路径中，内存访问次数为加权目标，计算其是否有希望发现内存漏洞，之所以这里着重强调内存相关漏洞，是由于在历史研究中表明，内存相关漏洞在总的漏洞中占比较高。
具体实验来论证文章观点
实验选择了24个开源Linux应用程序的最新版本，包括主流工具，图像处理库，音频视频处理工具，文档处理工具等，主要参考要素是其在社区中受欢迎程度，发展活跃度。此外还对带有4个设置好漏洞的LAVA-M数据集进行评估。
实验中对CollAFL和其三种不同模糊策略-br，-desc，-mem都进行了评估。实验中设置的虚拟机使用2 GHz Intel CPU和1GB RAM，Ubuntu版本为15.10.
哈希冲突对覆盖信息准确率的影响有多少
AFL在计算边命中信息时，采用的位图默认为64KB大小，对于哈希冲突问题，传统想法有扩大位图从而减小边碰撞概率，事实上，扩大位图确实在一定程度上缓解了碰撞问题。
如图，在位图扩大到1MB以后，边碰撞比已经是一个较低的状态。但是需要注意的是，模糊器在获取到覆盖信息后，准备进行下一步指导种子调度等操作时，需要去查询位图获取边命中情况，这里就需要对位图进行遍历，倘若贸然地扩大位图，这给模糊器每次访问带来的时间开销将会是几何级增长。
显然，在位图扩大的过程中，所有程序的执行速度均大幅度下降，对比降低边碰撞比的收益和其带来的巨额时间开销，简单扩大位图的操作，是一种低收益的操作。哈希冲突对于代码覆盖精度的影响不能简单通过扩大位图去改善。
本文提出的CollAFL技术在代码覆盖方面的表现
如图所示，200个小时内，不同模糊器在11个应用程序上的探索路径总数上，CollAFL平均多找到了9.9%的路径，其中尤其是考虑未覆盖分支的模糊策略-br，其平均多发现了20.78%的路径。而和相对比AFL-fast，即优先考虑低访问次数的路径，CollAFL表现出更优的路径覆盖率，平均多找到8.45%的路径。
CollAFL在发现独特崩溃方面的能力
除了代码覆盖率，漏洞挖掘的效果很大程度上也要取决于特殊崩溃的发现，进而联系到发现的漏洞数量，二者大体是正相关的。
从图中发现，以所有模糊器发现崩溃数的平均值为基线，CollAFL对比AFL和AFL-fast均有更优表现。其中最突出的两条，表明CollAFL衍生出的新模糊策略在一些具体的程序上有着特别优秀的表现。
最终该方法确定了157个漏洞，这些漏洞在提交给开发者后均证实为程序存在的问题。
面对现实程序的随机性表现如何
在衡量测试随机性时，选择对同一程序进行20次漏洞挖掘，分析其中多少次发现了漏洞，耗时多久，由此判断测试方法应对现实程序的测试随机性如何。
在测试程序中，Exiv2的随机性最大，在其上的测试中CollAFL仍优于AFL技术，除了意外，多数程序上，CollAFL技术均能实现20此实验全部或基本上都挖掘到漏洞，且用时也较短。
结论
本文研究了覆盖引导模糊器中覆盖误差的负面影响。我们提出了一种覆盖敏感模糊解决方案CollAFL，它解决了最先进的fuzzer AFL中的散列冲突问题，在保持低仪器开销的同时实现更准确的边缘覆盖信息。本文还提出三种模糊策略，经实验证明效果更优。
