基于重要语句的分支覆盖测试数据生成方法

摘要

本发明公布了一种基于重要语句的分支覆盖测试数据生成方法，旨在可以高效地生成覆盖目标分支的测试数据。具体步骤如下：(1)利用弱变异测试转化方法对原程序进行转化；(2)根据语句重要度指标体系对原程序语句进行排序；(3)基于以重要度排序后的原程序语句序列，确定相应的变异分支优先级；(4)建立以分支覆盖为准则的测试数据生成问题的数学模型；(5)设计适应度函数，以优先级最高的变异分支为目标；(6)设置相关遗传操作，采用遗传算法生成覆盖目标分支的测试数据。

说明书

技术领域

本专利属于软件变异测试领域，具体涉及一种基于重要语句的分支覆盖测试数据生成方法，可用于软件测试中生成覆盖目标分支的测试数据。

背景技术

软件测试旨在揭示软件中存在的漏洞或者风险，保证所开发软件的安全性和可靠性。而生成有效的测试数据，是软件测试的核心工作。随着手机等移动设备的普及，各行业对软件的开发力度都在逐步加大，与人们生活相关的订餐软件、网上购物等方方面面，都需要较高的软件可靠性支持。为了确保软件质量得到较高的保障，软件开发人员需要在软件开发的各个阶段对软件反复检测，以揭露软件可能存在的漏洞。软件测试过程，主要有软件需求分析、设计测试数据、执行测试数据以及测试报告的撰写等，测试过程繁琐，而且容易导致新的缺陷产生，所以，研究有效的测试方法，简化软件测试过程，对提高测试效率，是极为必要的。

研究表明，传统的覆盖测试，例如：语句覆盖和分支覆盖等，与缺陷的检测能力没有很强的联系；变异测试的目标对象是程序缺陷，采用适当的方法，添加新的代码到原语句之中，以仿造程序漏洞。其中，每一个新生成的漏洞，称为一个变异体；相应的缺陷产生规则，称为变异算子。因此，基于变异测试，能够生成具有更强缺陷检测能力的测试数据集。变异测试产生了众多的变异体，为了杀死每一变异体，需要生成相应的测试数据，并通过执行原程序和某一变异体，判定该变异体能否被杀死。

作为一种测试技术，变异分析能够真实的反映真实软件的各种缺陷。但是，实际软件通常包含规模庞大的代码行、复杂的语句，以及各种变量，显著增加了可变异的位置和可实施的变异算子类型，从而产生为数众多的变异体。为了杀死这些变异体，必须采用充分的测试数据，反复执行原程序和变异体，明显降低了变异测试的效率，从而限制了变异测试的应用范围。

然而，已有的变异体约简方法应用范围小，约简程度低。主要表现在：变异体的抽样和选择，会随着所选变异体数目的减少降低变异测试充分度；变异体聚类需要基于一定的准则，而不同的准则得到的变异体聚类结果不同，从而选择用于实施变异测试的变异体也不同；高阶变异体能够有效减少需要杀死的变异体数量，但是，如何高效生成杀死这些高阶变异体的测试数据，目前尚缺少有效的方法。测试数据生成方面，目前已有诸多的研究工作，而设计合适的生成策略，并使用先进的算法进行求解，将会进一步降低变异执行代价。Papadakis和Malevris基于弱变异测试准则，将变异体进行变换，然后插桩到原语句之前，覆盖变异分支真分支即为杀死变异体，提高了弱变异测试的效率。基于此，设计高效的分支覆盖策略，并利用遗传算法生成测试数据，变异测试的执行效率将大大提高。因此，针对变异测试，研究有效的分支覆盖测试数据生成方法，是非常有必要的。

发明内容

本发明利用弱变异测试转化方法，生成变异分支并插桩到原程序中，设计分支覆盖优先策略；基于分支覆盖准则，建立基于该策略的测试数据生成问题的数学模型；使用遗传算法求解，生成覆盖目标分支的测试数据。

本发明所要解决的技术问题：针对转化后的变异分支，提供一种覆盖优先策略，用以提高测试数据生成效率，降低测试代价。

本发明的技术方案：提出了一种分支覆盖测试数据生成方法。

其特征在于步骤如下：

步骤1：分支覆盖优先策略

利用弱变异测试转化方法，生成变异分支并插桩到原程序P中，形成新的被测程序P'，原程序转化后的变异分支为集合B＝{b₁,b₂,…,b_i,…,b_m}。根据原程序中各语句重要度，设计分支覆盖顺序。

步骤2：数学模型的建立

针对转化后的新程序P'，记执行测试数据t，被覆盖的变异分支集合为f(t)。因而，测试数据覆盖变异分支问题，可以表示为：在P'的输入域D中，搜索能够覆盖B中的全部变异真分支的测试数据集T＝{t₁,t₂,…,t_i,…t_n}，其中t_i,i＝1,2,…,n，是P'的一个测试输入，n是包含的元素个数。记T中所有的测试数据，覆盖的变异分支集合为F(T)，F(T)＝f(t₁)∪f(t₂)∪…∪f(t_i)∪…∪f(t_n)。因此，未被覆盖的变异分支，可以表示为B-F(T)。如此一来，转化后的问题，可以表示为如下最小化问题：

min{B-F(T)}

s.t.T∈D₁×D₂×…D_i×…×D_n

式中，D表示P'的输入域，n为包含的测试数据个数。因而，当B中的全部变异分支均被覆盖时，B-F(T)为空。

步骤3：变异测试数据的进化生成

利用遗传算法，求解步骤2建立的数学模型，生成覆盖目标分支的测试数据。具体方法如下：

[1]:根据分支覆盖优先策略，确定被测试程序变异分支优先级，对遗传算法所需的控制参数赋值；

[2]:种群初始化，在输入域内随机产生测试数据；

[3]:利用种群中的新个体，以B中优先级最高的分支作为覆盖目标，执行转化后的新程序；

[4]:若B中的变异分支被覆盖，则删除相关分支，同时保留新个体；

[5]:根据执行信息，判断算法是否结束，如果是，转步骤7；

[6]:实施遗传操作，得到子代种群，转步骤3；

[7]:算法结束，输出结果。

本发明的主要贡献在于：(1)提出变异分支覆盖优先策略，依此建立以分支覆盖为准则的测试数据生成问题的数学模型；(2)使用遗传算法，对所建模型求解，自动生成覆盖变异分支的测试数据；(3)将所提方法应用于多个基准与工业程序的测试，并验证本发明所提方法的有效性。

附图说明

图1是本发明的总流程图；

图2是变异分支构建过程图；

图3是转化后的新程序；

图4是遗传算法基本流程图。

具体实施方式

本发明根据原程序中变异测试对象的重要程度，提出基于重要语句的分支覆盖测试数据生成方法。该方法根据对原程序各语句依据重要度进行降序排列，并依此确定变异分支的覆盖优先策略，建立以分支覆盖为准则的测试数据生成问题的数学模型。针对该模型，利用遗传算法求解，生成覆盖目标分支的测试数据。

该部分结合具体附图，对本发明的实施方式做详细说明。所提出方法的流程图如图1所示，具体实施步骤亦根据该图拟定，下面对本发明的技术方案做进一步详细描述。

步骤1：分支覆盖优先策略

步骤101：记被测程序为P，其变异体集合为M，为了杀死变异体，生成的测试数据集为T。根据Papadakis和Malevirs提出的弱变异测试转化方法，利用MuClipse生成变异体,手工检测并确定等价变异体；从日志文件“mutation_log”中自动获取操作之后的语句，并与原语句进行组合，形成变异分支，如图2所示。插桩到原语句之前，得到的新程序记为P'，如图3所示。植入后的新语句，不影响原程序的执行。若共有个m变异体，对于新程序，可以记这些转化后的变异分支真分支分别表示为b₁,b₂,…,b_i,…,b_m，其中1≤i≤m。那么，原程序转化后的变异分支为集合B＝{b₁,b₂,…,b_i,…,b_m}。

步骤102：针对插桩后的新程序，利用变异测试对象重要度评价方法，分析原程序，统计变异测试对象所在语句的类型、包含关键变量的个数，以及其所含变量被依赖的变量个数，根据评价语句重要度的指标体系，计算各程序语句的重要度；接着，根据重要度大小，对程序原语句进行降序排列；最后，按照上述排序，设计变异分支的覆盖顺序，优先覆盖优先级最高的变异分支。

步骤2：数学模型的建立

步骤201：在生成变异测试数据之前，集合B＝{b₁,b₂,…,b_i,…,b_m}中包含所有的变异分支，且其中的变异分支都是未被覆盖的。此时，测试数据集T为空集，即覆盖变异分支的过程为：首先，以优先级最高的变异分支b₁为目标分支，在各输入分量的定义域内随机生成测试数据t；然后，执行转化后的程序P'，如果目标分支b₁或其他分支被覆盖，那么，将被覆盖分支从B中删除，并把t加入到T中。多次执行，直到全部分支都被覆盖，或达到算法设置的最大运行次数为止。当T中的元素覆盖所有的变异分支时，B变成空集，T即为生成的分支覆盖变异测试数据。变异分支覆盖算法的步骤如下：

[1]：根据变异测试对象重要度评价方法，计算原程序各语句重要度，并对原程序语句进行降序排列；

[2]：依据原程序语句重要度排列次序，确定变异分支的覆盖顺序；

[3]：选择优先级最高的变异分支为目标分支，并生成覆盖其的测试数据t；

[4]：若覆盖B中的变异分支，删除被杀死的变异分支，同时将t加入T中；

[5]：判断算法是否结束？如果是，输出T；否则，转[3]。

步骤202：针对转化后的新程序P'，记执行测试数据t，被覆盖的变异分支集合为f(t)。因而，测试数据覆盖变异分支问题，可以表示为：在P'的输入域D中，搜索能够覆盖B中的全部变异真分支的测试数据集T＝{t₁,t₂,…,t_i,…t_n}，其中t_i,i＝1,2,…,n，是P'的一个测试输入，n是包含的元素个数。记T中所有的测试数据，覆盖的变异分支集合为F(T)，F(T)＝f(t₁)∪f(t₂)∪…∪f(t_i)∪…∪f(t_n)。因此，未被覆盖的变异分支，可以表示为B-F(T)。基于弱变异测试转化方法，对原程序进行分析处理，将变异语句与原语句组合，并插桩到原语句之前。因而，求解目标变成覆盖所有的变异真分支。如此一来，转化后的问题，可以表示为如下最小化问题：

min{B-F(T)}

s.t.T∈D₁×D₂×…D_i×…×D_n

式中，D表示P'的输入域，n为包含的测试数据个数。因而，当B中的全部变异分支均被覆盖时，B-F(T)为空。

步骤3：变异测试数据的进化生成

步骤301：设计适应度函数

利用遗传算法，求解步骤2建立的模型，主要包括适应度函数设计和相关参数的设置。基于遗传算法的测试数据生成，适应度函数由分支距离和层接近度构成，即

fitness(t)＝Appr(t)+dist(t)

层接近度，与测试数据执行的代码，偏离目标语句所在分支的程度有关，用Appr(t)表示。偏离的越远，该值越大。分支距离和目标分支的覆盖与否有关，记为dist(t)。如果目标被覆盖，则为0。反之，根据相应的准则，计算分支距离。具体的方法如表1所示，根据复杂程度，有两种不同的计算方法。最后，由于程序规模较大，分支零散的原因，还根据公式Normal(dist)＝1-1.001^-dist，对其进行标准化处理。因此，测试数据的适应度函数最终可以表示为fitness(t)＝Appr(t)+Normal(dist(t))。

表1分支距离计算公式

步骤302：测试数据生成方法

首先，依据步骤201提出的变异分支覆盖优先策略，从B中选择优先级最高的分支b₁作为目标分支；接着，初始化种群，在定义域内随机生成测试数据t，计算并评价个体适应值；若t执行了目标分支或B中的其它分支，则保留t，并删除相关分支；然后，实施遗传操作，得到新的测试数据，并依据变异分支的覆盖顺序，选择B中优先级最高的分支作为新的目标分支；往复执行该过程，直到B为空集，或达到算法终止条件，求解过程结束。

步骤303：测试数据的生成具体步骤

步骤如下：

[1]：根据分支覆盖优先策略，确定被测试程序变异分支优先级，对遗传算法所需的控制参数赋值；

[2]：种群初始化，在输入域内随机产生测试数据；

[3]：利用种群中的新个体，以B中优先级最高的分支作为覆盖目标，执行转化后的新程序；

[4]：若B中的变异分支被覆盖，则删除相关分支，同时保留新个体；

[5]：根据执行信息，判断算法是否结束，如果是，转步[7]；

[6]：实施遗传操作，得到子代种群，转[3]；

[7]：算法结束，输出结果。

步骤304：遗传算法具体步骤

遗传算法的基本步骤如图4所示，描述如下：

[1]对算法所需的控制参数赋值，编码被测程序的语句，确定目标路径，插装被测程序；

[2]初始化种群；

[3]解码进化个体，执行插桩后的被测程序，计算进化个体适应值；

[4]判断是否满足算法终止条件，若满足，转[6]；

[5]实施选择、交叉和变异等遗传操作，生成子代种群，转[3]；

[6]终止算法运行，输出测试数据。

步骤4：实例分析

步骤401：测试程序

选取8个基准和工业程序作为被测程序，进一步验证本章方法的有效性，8个被测程序都是开源工业类。这些程序均采用Java语言编写，基本信息如表2所列。

表2被测程序基本信息

步骤402：遗传操作设置

遗传算法通过不断进化种群中的个体，得到满足需求的优秀个体，对于种群的进化，遗传操作必不可少。基本的操作包括选择、交叉、变异，其中，选择操作使得种群中的优秀个体，能够有更高的概率保留到下一代种群，本章采用轮盘赌选择；交叉操作则是通过重组两个个体，产生两个新个体，本章采用单点交叉；变异操作则是对个体编码的某些位置，进行随机改变，并得到一个新的个体，本章采用基本位变异。

步骤403：实验结果及分析

(1)生成测试数据的代价

对于变异分支排序前后的测试程序，均采用遗传算法生成测试数据，通过实验得到的迭代次数和时间，评价生成测试数据的代价。结果如表3所列，表中，未对变异分支进行排序的方法，称为传统方法。

由表3可知，(1)对于不同的被测程序，采用相同的方法生成测试数据，迭代次数和时间明显不同。对于本章方法，在8个被测程序中，迭代次数最高的是程序J7，为2433次，时间花费最多的是程序J4，为28234.91ms；迭代次数最低的是程序J8，为42次，时间花费最少的是程序J2，为27.17ms；对于传统方法，也是如此；(2)对于同一被测程序，本章方法的迭代次数和时间明显少于传统方法。比如，对于程序J1，传统方法的迭代次数和时间为411次97.50ms，而本章方法的迭代次数和时间为253次53.39ms，两者的迭代次数比和时间比分别为1.6和1.83；(3)对于所有程序，本章方法所需的迭代次数和时间为5360次40806.22ms，远低于传统方法的9730次85724.62ms。这说明，采用本章方法生成的变异测试数据，能够有效地降低变异测试代价。

表3生成测试数据需要的迭代次数和时间

(2)生成测试数据的有效性

对于变异分支排序前后的被测程序，采用遗传算法生成的测试数据，分别对程序执行弱变异和强变异测试，考察变异分支覆盖情况以及取得的变异得分，结果如表4和表5所列。

表4测试数据对变异分支的覆盖情况

由表4可知，(1)对于8个被测程序，共有变异分支2843个，其中，包含201个不可覆盖分支；(2)采用传统方法生成的测试数据，覆盖的变异分支个数为2627个，分支覆盖率为99.43％；(3)采用本章方法生成的测试数据，覆盖的变异分支个数为2628个，分支覆盖率99.47％。这说明，基于弱变异准则，通过本章方法对变异体排序之后生成的测试数据，其有效性不弱于排序之前。

表5测试数据对强变异测试的有效性

由表5可知，(1)对于8个被测程序，共有变异体2662个，其中，包含404个等价变异体；(2)采用传统方法生成的测试数据，杀死的变异体个数为2192个，取得的变异得分为97.08％；(3)采用本章方法生成的测试数据，杀死的变异体个数为2195个，取得的变异得分为97.21％。由此可见，基于强变异准则，通过本章方法对变异体排序之后生成的测试数据，其有效性不弱于排序之前。

通过上述实验结果与分析，可以得出如下结论：采用本章方法生成的测试数据，能够大幅度减少算法迭代次数，缩短程序运行时间；同时，基于此生成的测试数据，能够维持很高的变异测试充分度。因此，本章方法在确保变异测试有效性的同时，能够降低执行成本。