一种基于聚类和多种群遗传算法的软件测试数据生成方法

摘要

本发明公布了一种基于聚类和多种群遗传算法的软件测试数据生成方法，目的是将模糊聚类方法和遗传算法应用于软件测试中，提高软件缺陷检测的效率。首先，在弱变异测试准则下，基于统计分析计方法计算变异体之间的相似度和变异体的杀死难度，进而排序变异体；接着基于排序好的变异体序列，选择难杀死的变异体为聚类中心，模糊聚类变异体。然后，针对每个簇，建立基于分支覆盖约束的测试数据生成数学模型；最后，对于多个变异体簇，基于强变异测试准则，采用多种群遗传算法生成测试数据，其中对于每个簇中变异体，优先生成杀死聚类中心的变异体，聚类中心动态调整。

说明书

技术领域

本发明涉及计算机软件测试领域，具体是一种基于聚类和多种群遗传算法的软件测试数据生成方法。

背景技术

软件质量评价是软件工程领域一个重要研究内容，软件的正确性和可靠性，需要通过软件测试进行评估。变异测试是由Hamlet和DeMillo等提出的一种面向缺陷的测试技术，它不仅可以根据程序或语句的特征，模拟真实软件中的各种类型的缺陷，也可以基于程序的复杂情况，针对性的选择缺陷发生位置和注入缺陷的数目。因此，对于软件测试来说，变异测试是一种方便、灵活、个性化的技术。与传统的结构化测试相比，变异测试具备的充分性测试准则，使其具有更强的缺陷检测能力。因此，上述变研究的结果，为本方法研究奠定了坚实的基础。

为了进行变异测试，首先，通过使用变异算子，对程序的某一语句做合乎语法的微小变动，以产生一个新的程序，称该程序为一个变异体。生成缺陷的规则称为变异算子。根据变异测试可达性、必要性和充分性满足的条件不同，变异测试分为强变异和弱变异测试两种。在强变异测试准则下，判断一个变异体能否被杀死，需要满足如下3个条件：(1)可达性，测试数据能够执行到变异体中的变异语句；(2)必要性，测试数据执行变异语句之后，产生与原程序不同的状态；(3)充分性，上述不同的状态，能够导致原程序和变异体的输出不同。在弱变异测试准则下，只需满足可达性和必要性条件。

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

人工智能技术近年来在软件测试中得到广泛的应用，并取得了丰硕的研究成果。本方法借鉴其中的机器学习和进化算法这两种技术，解决众多变异体的测试数据生成的问题。

聚类方法是在无监督情况下，对数据进行分类。如果类与类之间有重叠数据，采用模糊聚类更有效，也更符合现实情况。基于模糊聚类可以将相似度高的变异体分到同一簇中，减少生成测试数据的代价。此外，进化算法受自然界生物进化机制启发而来，具有自组织、自适应、自学习、全局搜索的特性，能够有效地处理传统优化算法难以解决的复杂问题。若将变异测试数据生成问题转化为进化优化问题，那么，可以借助进化算法，提高变异测试数据生成的效率。由此可见，将聚类方法和进化算法融入变异测试，可以丰富变异测试理论和方法，增强变异测试的性能。

遗传算法是一种受自然界生物进化和遗传变异机制启发产生的全局概率搜索方法，该算法特点是，不要求被优化的目标函数是连续的和可微的，且能在允许的时间内，找到复杂优化问题的满意解，因此，该方法比较适用于变异测试数据生成。单种群遗传算法的特点是对单个种群的进化个体实施遗传操作，比如编码、选择、交叉、变异和解码。多种群遗传算法是一种高性能扩展版本的遗传算法，它首先将一个种群划分为几个孤立的子种群，每个子种群可以完成相同的任务，也可以完成不同的子任务。一般情况，在子种群中，个体实施遗传操作与单种群遗传算法相同，在子种群进化过程中，各子种群中的个体具有潜在的并行性，个体也被允许从一个子种群迁移到另一个子种群。因此，多种群遗传算法对于处理复杂的优化问题，具有更强的处理能力和更高的效率。与单种群遗传算法相比，多种群遗传算法更接近于自然界遗传进化的过程。

发明内容

为了解决上述现有技术中变异测试效率低下、测试数据质量低的问题，本发明提供了一种基于聚类和多种群遗传算法的软件测试数据生成方法，深入挖掘变异体形成机理和它们之间内在关联，借鉴“分而治之”思想，基于弱变异测试准则，采用模糊聚类方法，“分”变异体；采用多种群遗传算法，基于强变异测试准则，以并行方式“治”变异体，期望以低测试代价，高效生成高质量测试数据。该方法不仅使变异测试更加智能，而且有利于变异测试在产业界的广泛应用。

本方法采用的技术方案：一种基于聚类和多种群遗传算法的软件测试数据生成方法，其特征在于：该方法包括以下步骤：

S1.1：确定变异体杀死难度；

S1.2：确定变异体纸件的相似度；

S2：聚类变异体；

S3：构建测试数据生成数学模型；

S4：基于多种群遗传算法生成测试数据。

优选的，步骤S1.1中，确定变异体杀死难度的方法为：

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

为了反映X杀死变异体M

为了计算μ

所有变异体杀死难度，记为Dif(M

优选的，步骤S1.2中确定变异体之间的相似度的方法为：

假设变异体M

M

由上式可知，α

优选的，步骤S2中聚类变异体的方法为：

对于所有变异体M

设第i簇为C

聚类变异体步骤如下，

A1：变量i＝1，

A2：从S中选出首元素作为聚类中心

A3：将

A4：考察Λ中

A5：将

A6：i＝i+1；

A7：判断S中是否还有变异体，如果还有变异体，转A2：；

A8：输出所有的簇，记为C

优选的，步骤S3中构建测试数据生成数学模型的方法为：

对于

然而，由上式可知

在杀死

其中Appr(s′,X)是X对于s′的层接近度，dist(s',X)为分支距离；由上式可知，当且仅当时

根据X，

优选的，步骤S4基于多种群遗传算法生成测试数据的方法为：

对于上面的数学模型，基于强变异准则，采用多种群遗传算法生成测试数据；为了引导种群进化，需要计算进化个体的适应值；考虑到数学模型中包括一个目标函数和一个约束函数，适应值函数

其中，

在多种群遗传算法中，一个种群包含m个子种群，分别处理m个簇 C

生成测试数据的步骤：

B1:初始化m个子种群和算法中的各种参数；

B2:设变量count＝1；

B3:判定终止条件是否满足，如果满足，转B13；

B4:设变量i＝1；

B5:

B6:

B7:停止第i个子种群的进化；m＝m-1；保存生成的测试数据；转B13；

B8:

B9:计算所有个体的适应值

B10:实施选择、交叉和变异操作；生成新进化个体，不引起混淆，仍记为

B11:count＝count+1；转B5；

B12:在每一个簇中，从未杀死的变异体中，选择难杀死的变异体为新的聚类中心；转B1；

B13:输出测试数据集。

本发明的有益效果：

(1)基于弱变异准则排序和模糊聚类，大大降低了变异测试的代价，提高了变异测试的实用性，而且模糊聚类更适合变异分支之间的真实的相似情况。

(2)多种群遗传算法，能够通过进化个体信息共享，以并行方式，高效生成测试数据，同时提高杀死变异体的能力；而且，优先生成杀死簇中心变异体的测试数据，有利于提高杀死簇中其它变异体概率。

(3)人工智能技术中的模糊聚类和多种群遗传算法融入变异测试，有利于增强了变异测试的性能。

附图说明

图1为本发明提出的一种基于聚类和多种群遗传算法的软件测试数据生成方法总流程图；

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

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

具体实施方式

(1)模糊聚类变异体

步骤S1.1确定变异体杀死难度

设某一测试程序为G，程序的输入为X，s为G中某一原语句，对其实施变异之后，得到变异语句s'；条件语句“ifs！＝s'”，和它的真分支，基于弱变异测试准则称为变异分支，它对应的变异体记为M

难杀死变异体是指，在给定的测试集中，很少测试数据能够杀死的变异体。显而易见，杀死变异体的测试数据越少，变异体越难杀死。因此，变异体杀死难度可以用杀死它的测试数据衡量。

为了反映X杀死变异体M

为了计算μ

所有变异体杀死难度，记为Dif(M

步骤S1.2确定变异体之间的相似度

假设变异体M

M

由上式可知，α

设第i簇为C

步骤S3聚类变异体如下，

A1：变量i＝1，

A2：从S中选出首元素作为聚类中心

A3：将

A4：考察Λ中

A5：将

A6：i＝i+1；

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

A8：输出所有的簇，记为C

步骤3构建测试数据生成数学模型

对于

然而，由上式可知

在杀死

其中Appr(s′,X)是X对于s′的层接近度，dist(s',X)为分支距离。由上式可知，当且仅当时

根据X，

步骤4基于多种群遗传算法生成测试数据

对于上面的数学模型，基于强变异准则，采用多种群遗传算法生成测试数据。为了引导种群进化，需要计算进化个体的适应值。考虑到数学模型中包括一个目标函数和一个约束函数，适应值函数

其中，

在多种群遗传算法中，一个种群包含m个子种群，分别处理m个簇 C

生成测试数据的步骤：

B1:初始化m个子种群和算法中的各种参数；

B2:设变量count＝1；

B3:

B4:判定终止条件是否满足，如果满足，转B13；

B5:判断

B6:

B7:停止第i个子种群的进化；m＝m-1；保存生成的测试数据；转B4；

B8:

B9:计算所有个体的适应值

B10:实施选择、交叉和变异操作；生成新进化个体，不引起混淆，仍记为

B11:count＝count+1；转B5；

B12:在每一个簇中，从未杀死的变异体中，选择难杀死的变异体为新的聚类中心；转B1；

B13:输出测试数据集。

测试实例分析

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

对于图2(b)中的M

根据式(2)，计算图2(b)中对应30个变异体的杀死难度，并基于变异体的杀死难度降序排列变异体，得到排序后的变异体序列为S＝M

表1本发明变异体的杀死难度和排序。

若有170个测试数据杀死M

下面模糊聚类变异体。由表1可知，首先选最难杀死的变异体M

在S中，M

表2聚类结果和活着的变异体

采用多种群遗传算法生成测试数据时，起初，初始化每个子种群的优化个体，设置各种参数，和最大迭代次数g＝3000。如果某一个测试数据期望杀死簇C

若所有的进化个体都不能杀死M

类似的，运行多种群遗传算法一次后，每一簇中生成的测试数据和活着的变异体都被列在表2第2,3列中。注意到，虽然在某一簇中，某变异体没有被杀死，然而它被其它簇中的测试数据杀死。比如在C

最终的杀死30个变异体的测试数据集为：

T＝{(39,36,15),(15,14,15),(63,62,62),(8,8,7),(29,19,47),(20,10,38)}。

通过上述实例表明，本发明方法采用分而治之的思想，先聚类变异体再采用多种群遗传算法生成测试数据，能高效生成测试数据，提高了软件测试的效率。