一种聚类分析驱动种子调度的模糊测试方法

Fuzzing Approach of Clustering Analysis-driven in Seed Scheduling

作为当前被广泛应用的自动化软件测试技术,模糊测试的首要目标是尽可能多地探索被测程序的代码区域以达到更高的覆盖率,从而检测出更多的漏洞或者错误.现有的模糊测试方法大多是根据种子的历史突变数据来调度种子,实现起来比较简单,但忽略了种子所探索程序空间的分布情况,导致测试工作可能会陷入只对程序的某单一区域进行探测,造成测试资源的浪费.提出一种基于聚类分析驱动种子调度的模糊测试方法Cluzz.首先,Cluzz结合种子执行路径覆盖的分布来分析种子在特征空间上的区别,使用聚类分析对种子在程序空间中的执行分布情况进行划分.然后,根据不同种子簇群的路径覆盖模式与聚类分析结果对种子进行优先级评估,探索稀有代码区域并优先调度评估得分较高的种子.其次,通过种子评估得分为种子分配能量,将突变得到的有趣输入保留并进行归类以更新种子簇群信息.Cluzz根据更新后的种子簇群重新评估种子,以确保测试过程中种子的有效性,从而在有限时间内探索更多的未知代码区域,提高被测程序的覆盖率.最后,将Cluzz实现在3个当前主流的模糊器上,并在8个流行的真实程序上进行大量测试工作.结果表明:Cluzz检测独特崩溃的平均数量是普通模糊器的1.7倍,在发现新边缘数量方面,平均优于基准模糊器22.15%.此外,通过与现有种子调度方法进行对比,Cluzz的综合表现要优于其他基准模糊器.

As a widely used automated software testing technique,the primary goal of fuzzy testing is to explore as many code areas of the program under test as possible,thereby achieving higher coverage as well as detecting more bugs or errors.Most of existing fuzzy testing methods schedule the seed based on the historical mutation data of the seed,which is simpler to implement but ignores the distribution of program space explored by the seed,resulting in that the testing may fall into only a single region of the program to be probed,and causing the waste of testing resources.This study proposes the Cluzz,a fuzzing approach of clustering analysis-driven in seed scheduling.Firstly,Cluzz analyzes the difference between seeds in the feature space by combining the distribution of seed execution path coverage,and uses cluster analysis to classify the distribution of seeds execution in the program space.And then,Cluzz prioritizes the seeds according to the path coverage patterns of different seed clusters and the results of cluster analysis,explores the rare code regions and prioritizes the seeds with higher evaluation scores.Secondly,energy is allocated to the seeds by their evaluation scores,and the interesting inputs obtained from mutations are retained and categorized to update the seed cluster information.Cluzz reevaluates the seeds based on the updated seed clusters to ensure the validity of seeds during testing process,thereby exploring more unknown code regions in a limited time and improving the coverage of the program under test.Finally,the Cluzz is implemented on three current mainstream fuzzers and extensive testing work is conducted on eight popular real-world programs.The results show that Cluzz can detect an average of 1.7 times more unique crashes than a regular fuzzer,and it also outperforms a benchmark fuzzer by an average of 22.15%in terms of the number of new edges found.In addition,compared with the existing seed scheduling methods,the comprehensive performance of Cluzz is better than that of other benchmark fuzzers.