Igor: Crash Deduplication Through Root-Cause Clustering

本文发表于CCS 2021，第一作者是来自国防科大的Zhiyuan Jiang。

论文链接：https://dl.acm.org/doi/10.1145/3460120.3485364

一、背景与动机

Fuzzing是当前很有效的一项bug检测技术，对于所有检测到的“独特”crash，fuzzing会输出相应的PoC。随后，开发人员会分析这些导致程序crash的PoC。这个分析过程主要是手动完成的，因此会占用开发者大量的时间，加重了开发人员的工作负担。尽管目前存在crash去重技术，但是它们主要是依赖覆盖率和栈哈希完成的，实际并不能很好地对crash进行聚类去重。因此，这篇文章旨在针对crash/PoC进行聚类，以减少开发人员在修复bug时的人工代价。

二、现有方法

现有的crash聚类方法主要有4种：（1）基于Crash Sites的聚类方法；（2）基于Coverage Profiles的聚类方法；（3）基于Stack Hashes的聚类方法；（4）分析出bug成因后，根据root cause进行crash聚类。但是，它们在准确性或实用性方面都存在问题。

基于Crash Sites的聚类方法根据crash点进行聚类，粒度很粗。相同的bug可能会在不同的地址crash，因此该方法可能导致同一个bug的crash被归为几类。同时，该方法也有可能导致几个不同的bug由于crash点相同而被归为一类。

基于Coverage Profiles的聚类方法将程序执行覆盖了相同CFG边的crash归为同一类，但是相同bug的多次crash执行可能覆盖不同的路径，因此该方法很有可能导致同一bug的crash被归为几类。

基于Stack Hashes的聚类方法根据函数粒度的调用栈哈希进行crash聚类。由于相同bug在多次crash时的执行路径不一定完全相同，因此该方法可能导致相同bug的crash被归为多个类别。同时，不同bug触发crash的函数执行栈有可能是相同的，该方法也有可能导致几个不同的bug被归为同一类。

另外，近年来有相关工作基于污点分析，程序切片，trace分析和符号执行技术对crash做root cause成因分析。虽然我们可以根据root cause的分析结果对crash进行聚类，但是这些程序分析技术的内存开销或时间开销普遍较大，在现实场景中进行crash聚类任务并不实用。

三、核心思路

文章认为，相同root-cause的bug，它们的executiontrace中有相同的核心行为。基于上述认识，作者认为可以选取合适粒度的核心行为来进行crash聚类。作者发现executiontrace中有足够表征crash触发行为的控制流信息，但是需要移除trace中与触发bug无关的执行。所以，作者基于coverage-minimizingfuzzing对executiontrace进行无关执行去除。精简后的最短的execution trace代表了PoC使程序崩溃的核心行为。最后，作者再基于图聚类的方法对精简（去除无关执行）后的程序执行CFG进行聚类，CFG聚类结果即为对应crash的聚类结果。

                                            
四、设计与实现

文章的igor设计流程如图所示，主要分为三部分：数据预处理，精简执行路径和图聚类。输入是待分析的crash PoC，输出是crash的聚类结果。

DataPreprocessing：文章首先基于stackhash对PoC进行去重，将stack hash相同且PoC相似的PoC进行预处理去重（对于相同stackhash的PoC，只保留50个）。作者认为，尽管基于stack hash的方法不能很好地完成对crash的聚类任务，但是这主要是因为相同bug的多个crash有可能stack hash不同，而不同root cause的bug栈哈希相同的情况是很少的。文章基于stack hash对PoC进行预处理去重降低了后续的运行开销。另外，作者还基于afl-tmin对PoC进行minimize，以增加后续fuzzing阶段的吞吐量，提升fuzzing效率。

Coverage-minimizingfuzzing：文章采用以减少边覆盖率为导向的fuzzing对crash执行路径进行最小化精简，并输出与初始crash点相同且edge bitmapsize最小的PoC。文章将该PoC的执行路径作为待聚类crash的最短执行路径（代表bug触发的核心行为）。本质上来看，文章的fuzzing策略和afl相反，即文章的fuzzing策略是以减少fuzzer探索新边的概率为导向的，目的是尽可能去除与触发crash无关的执行边。以文章fuzzing的seed保留策略为例，igor保留符合下列两种条件之一的seed：有至少一条边不被执行，或者存在边的执行次数变少（同时没有其它边执行次数增多）。值得注意的是，文章在收集最小化trace时，注意到了两种噪声：（1）外部动态共享库中执行的代码，例如glibc；（2）程序crash后执行的多余代码，例如sanitizer中的crash处理代码。文章在trace收集时过滤掉了这两类代码执行。

PoCsimilarity and bug clustering：文章记录basicblock级别的execution trace，并根据记录的trace构建CFG。作者选用Weisfeiler-Lehman (WL) SubtreeKernel算法进行CFG之间的相似度计算。目前，计算图相似度的方法主要包括两类：graph embedding和graph kernel。前者是利用传统的基于输入图降维的向量核算法，会导致结构信息丢失，而后者直接在高维hilbert空间执行核算法，从而图的结构信息会保持得相对完整。作者在调研了不同的graph kernel算法后，发现WL算法在该任务上表现更好，所以采用了WL算法。在获得图相似度之后，文章基于谱聚类和轮廓系数进行聚类。具体的，文章在每次迭代时指定不同的类簇数量，并选择轮廓系数最高那一次迭代结果作为最终的crash聚类结果。

五、实验评估

文章在254,000个PoC（属于39个unique bug，10个应用程序）上进行实验评估，结果如图所示。图中的结果显示文章提出的Igor方法可以将crash划分为48个bug类簇，crash聚类的表现比现有方法好很多。

六、局限

文章在聚类时，cluster数量最终是由轮廓系数（Silhouette Score）确定的，但是这种做法的准确性不能得到保证。另外，如果待聚类crash只属于一类bug，igor的聚类方法会出现问题，难以独立解决（最终会依赖于afl-collect方法的结果）。

七、Q&A

Q：数据预处理部分的crash最小化的作用是什么，和igor fuzzing部分中的最小化有什么不同？

A：数据预处理部分的crash最小化能够缩减输入PoC的大小，移除掉输入中与crash无关的byte，加快后续fuzzing的处理速度，增加变异到关键byte的可能性。预处理部分的最小化并不能很有效地缩减与crash无关的执行路径，而fuzzing部分的最小化才是有效减少无关执行路径的方式。

Q：igorfuzz保留seed的规则是什么，分别的作用是什么？

A：igorfuzz的seed retention策略与afl相反。具体的有以下两个规则：有至少一个边不被执行，或者存在边的执行次数变少（同时没有其它边执行次数增多）。

Q：文章如何进行图聚类？

A：基于谱聚类算法和轮廓系数。谱聚类(Spectral Clustering)是基于图论的聚类方法，它将带权无向图划分为两个或两个以上的最优子图，使子图内部尽量相似，而子图间距离尽量距离较远，以达到常见的聚类的目的。但是，谱聚类需要事先指定有几个cluster，由于缺乏先验知识，所以做迭代，每次迭代中指定不同的cluster数量，然后最后选出silhouette score最高的结果作为最终的聚类结果。

Q：聚类的时候如果只有一类bug怎么处理？

A：在这种情况下，Igor将聚类结果与基于调用栈的方法（例如afl-collect）进行了比较。如果Igor报告的聚类数超过afl-collect，会在报告指出应该参考afl-collect结果。

Q：Igor在预处理数据的时候，使用了afl-tmin来缩减POC长度，结合afl-tmin的原理说明为什么afl-tmin会引入可能存在的FN？

A：Afl-tmin将raw data划分为n等分，尝试去掉每一份重新将rawdata进行组合来精简POC，afl-tmin有两种模式，分别要求复现crash和相同的coverage，但是没有严格要求复现crash的类型，可能会导致minimize后发生了一个不同于精简之前的新POC。

Q：在分析POC执行流的时候，可能引入的噪声以及解决办法是什么？

A：在外部共享库执行时候引入的执行流以及crash之后的多余代码（例如ASan）。对于第一种情况，排除目标代码地址以外的地址；对于第二种情况，过滤掉crash之后的执行流。以上两者均通过Intel Pin来实现。

Q：文章Cluster Builder的缺点是什么？

A：谱聚类需要事先指定有几个cluster，由于缺乏先验知识，所以需要不断的迭代。每次迭代指定不同的cluster数量，最后通过轮廓系数来决定cluster数量。这种做法不一定准确，需要人工确认，对于同一个cluster里面仍然有gap的情况，需要进一步做分类。

复旦白泽战队

一个有情怀的安全团队

原文始发于微信公众号（复旦白泽战队）：Igor: Crash Deduplication Through Root-Cause Clustering