Igor: Crash Deduplication Through Root-Cause Clustering

admin 2022年5月5日11:05:31评论145 views字数 4052阅读13分30秒阅读模式

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

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


一、背景与动机

Fuzzing是当前很有效的一项bug检测技术,对于所有检测到的“独特”crashfuzzing会输出相应的PoC。随后,开发人员会分析这些导致程序crashPoC。这个分析过程主要是手动完成的,因此会占用开发者大量的时间,加重了开发人员的工作负担。尽管目前存在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,因此该方法可能导致同一个bugcrash被归为几类。同时,该方法也有可能导致几个不同的bug由于crash点相同而被归为一类。

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

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

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

 

三、核心思路

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

 

                                            
四、设计与实现

Igor: Crash Deduplication Through Root-Cause Clustering

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

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

Coverage-minimizingfuzzing:文章采用以减少边覆盖率为导向的fuzzingcrash执行路径进行最小化精简,并输出与初始crash点相同且edge bitmapsize最小的PoC。文章将该PoC的执行路径作为待聚类crash的最短执行路径(代表bug触发的核心行为)。本质上来看,文章的fuzzing策略和afl相反,即文章的fuzzing策略是以减少fuzzer探索新边的概率为导向的,目的是尽可能去除与触发crash无关的执行边。以文章fuzzingseed保留策略为例,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 embeddinggraph kernel。前者是利用传统的基于输入图降维的向量核算法,会导致结构信息丢失,而后者直接在高维hilbert空间执行核算法,从而图的结构信息会保持得相对完整。作者在调研了不同的graph kernel算法后,发现WL算法在该任务上表现更好,所以采用了WL算法。在获得图相似度之后,文章基于谱聚类和轮廓系数进行聚类。具体的,文章在每次迭代时指定不同的类簇数量,并选择轮廓系数最高那一次迭代结果作为最终的crash聚类结果。

 

五、实验评估

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

Igor: Crash Deduplication Through Root-Cause Clustering


六、局限

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

 

七、Q&A

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

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

 

Qigorfuzz保留seed的规则是什么,分别的作用是什么?

Aigorfuzzseed retention策略与afl相反。具体的有以下两个规则:有至少一个边不被执行,或者存在边的执行次数变少(同时没有其它边执行次数增多)。

 

Q:文章如何进行图聚类?

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

 

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

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

 

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

AAfl-tminraw data划分为n等分,尝试去掉每一份重新将rawdata进行组合来精简POCafl-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


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

  • 左青龙
  • 微信扫一扫
  • weinxin
  • 右白虎
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2022年5月5日11:05:31
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                   Igor: Crash Deduplication Through Root-Cause Clusteringhttp://cn-sec.com/archives/952859.html

发表评论

匿名网友 填写信息