• code （进行了一定的注释）

Yanghjsz/Igor

Igor

https://gitee.com/yanghjsz/Igor

Content

• Igor架构

Summary

• 首先是预处理阶段，利用函数调用Hash对大量的PoC进行抽样，减少后序分析的代价，然后用afl-min尽量减小PoC输入大小（虽然可能无法直接修剪与bug无关的路径，但是肯定是对这个目标有利的）。

• 然后修剪与错误无关的路径。并使用一种新颖的覆盖减少模糊测试方法计算最短的错误触发路径（覆盖率最小化导向的Fuzz—IgorFuzz）。

• 然后根据最小化执行轨迹的 CFG 之间的拓扑相似性对崩溃进行聚类（Graph Analyzer、Cluster Builder）。

Method

Data Preprocessing

• 采样
• 在堆栈hash中，很少有两个不同根因的case的函数调用重叠。也就是说一种bug可能有很多种栈哈希结果，但是一种栈hash只对应一种bug。
• 根据函数调用栈来先聚类，从每一个类中采样50个crash，如果一种stack hash有大量的crash，那就找50个最不同的POC。

• 最小化
• 输入大小的减小导致目标更快地解析和处理，从而产生更高的模糊测试吞吐量。
• 通过从输入中删除无关的字节，模糊器的突变更有可能修改对程序行为至关重要的字节。
• Igor利用alf-tmin来进行此过程
• 虽然afl-tmin目标是减少输入的长度，但是间接实现了我们的目标（删除与bug无关的执行trace），从而提高IgorFuzz后续处理的效率。
• afl-tmin也许会侵入引入其他的错误，但是实验表明这种错误可以忽略不急，因为IgorFuzz的seed选择机制会舍弃这些错误的PoC。

IgorFuzz:Minimum-Coverage Fuzzing

• IgorFuzz algorithm

• 覆盖率最小化为目标的Fuzz，IgorFuzz。原则就是用最少的执行trace触发某一bug，然后输出边bitmap最小的PoC。

• 目前比较先进的fuzzer是最大化覆盖率，有三个策略：种子保留、选择、调度，本文根据这三个策略，并修改了一个通用的反馈引导的灰盒模糊器，改为覆盖率最小化算法
• seed 保留原则。
• 两条规则：1. 种子不执行公共边（即，至少有一个边不再执行，尽管整体覆盖率可能会增加） ； 2. 种子以较少的命中计数运行一些边（即，至少一条边执行的次数较少，而没有边执行的次数较多）
• 保留满足上面两条规则中任何一个的seed。
• seed selection principle
• IgorFuzz 试图通过支持修剪分离边集的种子来最小化覆盖范围。修剪边缘组的新种子更有可能在进一步突变时从执行跟踪中修剪这些边缘。出于这个原因，将此类种子标记为更适合的并赋予它们更高的权重。
• seed 权重分配
• 更高权重的种子被突变和执行的次数越多（前面seed selection中使用赋权重），使用贪婪的启发式方法将更多的能量分配给执行长度更短的种子（根据动态覆盖率情况）。
• 位图大小最小的 PoC 来选择最简单的 PoC

Test Case Similarity Measurement

• 目前的测试用例相似度计算主要利用crash时的调用堆栈、指令指针、寄存器内容。

• 要比较程序执行trace的相似度，但是一些循环可能造成同一bug的相似度较低，所以这里用到了图的思想，将执行轨迹折叠到图形上意味着控制流相似性不再受不同循环迭代次数的影响。因此，我们的方法使用图形拓扑来计算轨迹之间的相似性。

• CFG
• 粒度选择：如果进行细粒度的指令级跟踪，则会引入冗余，另外进行粗粒度的函数级的trace，虽然更容易获取，但是因为较粗可能忽略一些关键信息。基础的块级粒度在准确性和可扩展性上相对平衡，这里使用块级粒度构建控制流图。
• 对执行trace要过滤一下噪声
• 在外部共享库中的执行trace
• 崩溃之后再执行的也算噪声

• 图相似度计算
• 用于图相似度估计的核方法包括两种类型：图嵌入和图核。前者利用基于输入图降维的传统向量核算法，导致结构信息丢失。后者直接在高维希尔伯特空间中进行核算法，使得图的结构信息保持完整。
• 本文使用了WeisfeilerLehman 子树核算法，可以更好的区分不同根因的PoC，同时将高相似度的PoC归因到一种bug。Weisfeiler-Lehman 子树内核算法需要标记图的节点。我们使用基本块地址（来自执行跟踪）作为节点标签。

Bug Clustering

• fuzzer不知道在模糊测试中发现多少bug种类，比如100个crash，bug类别就在1-100之间。针对无法确定bug的数量：通过多次运行聚类过程来确定聚类的数量，根据启发式改进假设的错误数量。

• 这里用silhouette score来评估聚类结构的质量。比如下图中b就比a有更高的silhouette score，因为b更利于聚类，边界清晰，重合少。

• 聚类算法
• 谱聚类 [74] 算法解决了存储在 Weisfeiler-Lehman 子树核相似矩阵中的高维信息带来的参数调整挑战。谱聚类只需要一个参数：簇数。给定聚类的数量和相似度矩阵，Spectral Clustering 在相似度矩阵的基础上构建图 Laplacian。计算拉普拉斯图的特征向量，实现降维。然后，该算法会自动将样本分组到较低维空间中指定数量的簇中。
• 聚类的真实数量是未知的，我们需要一个度量来评估聚类结果。为此，我们再次使用剪影分数。在一些研究中表名可以通过最大化剪影分数来确定。这里枚举集群的数量来运行聚类过程，并计算结果的轮廓分数，然后选取分数最高的聚类数量。

• 由于只有一类bug的话没有剪影分数，所以不适用于上述的情景。如果只有一个，则在枚举过程中人为增加簇数以找到更高的silhouette score。但是实践中没发现这种情况。

Experiment

• Benchmark
• Magma benchmark and MoonLight datase
• 14个目标程序中的52个cves。
• 针对一个程序多个bug、多个patch的情况，这里从没补丁的版本开始，一次只打一个patch，然后处理整个PoC语料库，然后标记crash变化，根据这给bug类别打标签。

• Result（上图）
• 输出的是基于基本块trace的聚类结果，但是也评估了基于函数调用和指令级的聚类结果。
• 从表一可以看出，Igor的效果好于之前的方法。

• Test Cases Reduction评估Reduction冗余path的能力

• 具体请阅读论文