一种融入模糊聚类的软件测试方法

摘要

本发明公布了一种融入模糊聚类的软件测试方法，目的是将模糊聚类方法应用于软件测试中，将模拟真实缺陷的变异体基于相似性进行聚类，同类缺陷只需检测一次，提高软件缺陷检测的效率；首先基于弱变异测试准则生成变异体，采用数理统计的方法，计算变异体之间的相似度；然后构建相似矩阵，最后，基于与变异体相似的变异体数目排序变异体，再基于变异体之间的相似性模糊聚类变异体，使得非中心变异体分配到多个簇中，有利于提高生成测试数据的效率；所提模糊聚类方法有助于降低变异测试的代价；对于提高变异测试的有效性和实用性，具有巨大潜力。

说明书

技术领域

本发明涉及计算机软件测试领域，设计了一种融入模糊聚类的软件测试方法。该方法区别于原有方法的特色在于，将模糊聚类方法应用于软件测试中，将模拟真实缺陷的变异体，基于相似性进行聚类，同类缺陷只需检测一次，有利于提高软件缺陷检测的效率。

背景技术

软件测试是一种提高软件产品质量的有效方式。软件质量越来越受到人们的重视与关注，软件测试是保证软件质量的重要手段，通过测试，不但能够检测软件可能存在的缺陷，而且能够提高软件的可靠度。变异测试具有排错能力强、方便灵活，以及自动化程度高等显著优点，广泛用来评估测试数据集的充分性与软件测试技术的有效性

变异测试是指将模拟软件的真实缺陷插入原程序，被插入缺陷的程序称为变异体；改动之后的语句，称为变异语句；采用相同的测试输入，分别执行原程序和变异体，如果某测试数据能够从执行结果上区分原程序和某变异体，那么，称该变异体基于强变异测试准则被杀死，如果两者在变异点执行后，变量状态出现不一致，称该变异体基于弱变异测试准则被杀死。变异得分是指被杀死的变异体占非等价变异体的比，用于评价测试数据集的缺陷检测能力，变异得分越高，测试数据集的实际缺陷检测能力越强。

一个程序往往存在很多变异体，为了杀死这些变异体，也需要大量的测试数据；而且，为了生成有效的测试数据集，最大限度地杀死变异体，必须反复执行原程序和变异体，这增加了变异测试的成本，严重阻碍了其在软件工程中的广泛应用，因此，需要研究合适的方法，提高变异测试的效率。

研究表明，减少运行变异体的次数是提高变异测试的效率的有效方式之一。Offutt等选择代表性变异算子代替所有的变异算子，生成变异体，以减少需要杀死的变异体。Mateo等提出通过构建额外代码框架，研究影响覆盖变异体的因素，减少变异体数目。国内的研究，主要有陈振宇团队通过约简同类变异算子生成的变异体，减少需要杀死的变异体。宫云战团队通过区间运算判断变异体之间冗余关系约简变异体，巩敦卫团队从语句重要度方面，选择重要的变异测试对象，减少变异体生成的数目，以及基于变异体依路径相似性，将变异体分组，进行高效软件测试。

聚类方法是在无监督情况下，将基于数据相似进行分类，其中模糊聚类能够对类与类之间有交叉的数据样本集进行有效聚类，所得的聚类结果明显优于硬聚类方法。将模糊聚类方法应用于变异测试，可以将相似度高的变异体分到同一簇中，有效减少变异体，降低变异测试执行代价。

国内陈翔团队一直致力于研究基于机器学习预测软件缺陷，其中基于聚类方法的研究成果，主要有2014年在《Computer Software and Applications》会议上发表基于聚类分析的特征子集选择框架，在《Software Security and Reliability》会议上发表基于聚类的缺陷预测的两阶段数据集预处理方法；2016年在《中国科学》发表软件缺陷预测中基于聚类分析的特征选择方法，在《软件学报》发表静态软件缺陷预测方法研究等。

Hussain首次采用聚类方法实现变异体的约简，他使用的聚类方法包括K-means聚类算法和凝聚型层次聚类算法。该方法的缺点是，采用K-means聚类算法，事先难以确定簇的数目及初始聚类中心，而且，采用凝聚型层次聚类算法，簇一旦合并就不能修正，这样一来，影响变异体的聚类质量。针对以上问题，黄玉涵提出了基于遗传算法改进变异体的聚类，该方法可以降低变异测试代价，约简率大大提高。然而，上述两种方法中，基于强变异测试准则，需要测试数据执行原程序和变异体，变异测试的计算开销仍然很大，而且基于测试数据之间距离作为变异体相似特征，不够准确，对于有些程序，距离很近的测试数据，不一定能够杀死相似的变异体。

鉴于以上分析，本发明将模糊聚类和弱变异测试技术应用软件测试中，能够增强软件测试缺陷检测能力，降低软件测试的代价，有利于变异测试在产业界的广泛应用。

发明内容

本发明提出一种融入模糊聚类的软件测试方法。该方法，首先基于弱变异测试准则生成变异体，采用数理统计的方法，计算变异体变异体之间的相似度；然后，构建变异体相似矩阵；最后，最后，基于与变异体相似的变异体数目排序变异体，再基于变异体之间的相似性模糊聚类变异体，使得非中心变异体分配到多个簇中。

本发明采用的技术方案：一种融入模糊聚类的软件测试方法，该方法包括以下步骤：

步骤S1:计算变异体之间的相似度

设某一测试程序为G，程序的输入为X，s为G中某一原语句，对其实施变异之后，得到变异语句s'；满足变异测试的必要条件“s！＝s'”，即是满足弱变异测试准则，其中“！＝”为不等于符号，那么条件语句“if s！＝s'”和它的真分支，基于弱变异测试准则称为变异分支，它对应的变异体记为M

为了反映X杀死变异体M

为了计算μ

为了聚类变异体，需要确定变异体之间的相似度。之前的研究发现，杀死某一变异体的测试数据，也可能杀死其它变异体，这表明，变异体之间存在某种联系，因此，可以基于这种联系定义变异体之间的相似性。

假设变异体M

M

由上式可知，α

步骤S2构建变异体相似矩阵

对于所有变异体M

M

步骤S3模糊聚类变异体

设第i簇为C

S31：η

S32：考察Λ中M

S33：基于η

S34：变量i＝1；

S35：从S中选出首元素M′

S36：将

S37：考察Λ中

S38：将

S39：i＝i+1；

S310：判断S是否还有变异体，如果还有变异体，转S34；

S311：输出变异体簇，记为C

本发明的有益效果：

(1)本发明将模糊聚类方法应用于变异测试，进行变异体聚类，可以提高软件测试缺陷检测的效率。进行变异测试时，往往变异体为数众多，一个变异体代表一个缺陷，为了提高检测缺陷的能力，可以将相似的变异体聚到同一类中，这样同一簇中的变异体，可以同时被杀死。

(2)本发明提出计算变异体相似度的方法。一个变异体就是一个程序，程序之间的相似度很难直接衡量。因此，可以通过执行它们的测试数据衡量变异体之间的相似度，即采用数理统计的方法，将杀死一个变异体的测试数据杀死其它变异体的概率作为变异体的相似度。

(3)本发明提出与其它变异体最相似的变异体为聚类中心，有助于同一簇中的变异体同时被杀死。

附图说明

图1为本发明提出的一种融入模糊聚类的软件测试方法总流程图；

图2为本发明实施例中的示例程序；

图3为变异体之间相似矩阵；

具体实施方式

为了进一步说明本发明技术方案的细节及其优点，现结合附图进行说明。

如图1所示，为本发明提出的一种融入模糊聚类的软件测试方法总流程图。该方法包括：

步骤S1:计算变异体之间的相似度

设某一测试程序为G，程序的输入为X，s为G中某一原语句，对其实施变异之后，得到变异语句s'；满足变异测试的必要条件“s！＝s'”，即是满足弱变异测试准则，其中“！＝”为不等于符号，那么条件语句“if s！＝s'”和它的真分支，基于弱变异测试准则称为变异分支，它对应的变异体记为M

为了反映X杀死变异体M

为了计算μ

为了聚类变异体，需要确定变异体之间的相似度。之前的研究发现，杀死某一变异体的测试数据，也可能杀死其它变异体，这表明，变异体之间存在某种联系，因此，可以基于这种联系定义变异体之间的相似性。

假设变异体M

M

由上式可知，α

步骤S2构建变异体相似矩阵

对于所有变异体M

M

步骤S3模糊聚类变异体

设第i簇为C

S31：η

S32：考察Λ中M

S33：基于η

S34：变量i＝1；

S35：从S中选出首元素M′

S36：将

S37：考察Λ中

S38：将

S39：i＝i+1；

S310：判断S是否还有变异体，如果还有变异体，转S34；

S311：输出变异体簇，记为C

测试实例分析：

如图2(a)所示为三角形分类程序的源代码。图2(b)为新程序，插入了30个基于弱变异测试准则生成的变异分支，它们形成的变异体集合为M＝{M

根据式(2)计算变异体之间的相似度。比如，基于弱变异测试准则，若有170个测试用例杀死M

类似的，可以得到所有变异体之间的相似度，并构建似矩阵为Λ，如图3所示。

下面排序变异体。基于Λ，对于每一个变异体，统计它与其它变异体高相关度的数目。设T＝0.5，比如M

表1排序后的变异体

下面模糊聚类变异体。由表1可知，首先相关性最多的变异体M

C

在S中，M

C

C

C

C

C

C

C

C

C

通过上述实例表明，本发明方法能够使相似的变异体精确地聚到一起，从而提高了软件测试的效率。