基于控制流图遍历和切片前向遍历相结合的软件测试方法

摘要

本发明提供的是一种基于控制流图遍历和切片前向遍历相结合的软件测试方法。是对基于控制流图遍历的选择性回归测试方法的遍历策略进行改进，对于代码中变量定义的改变，引用切片前向遍历算法，识别所有直接或间接被影响的变量定义使用对vdefine～vuse，并只选择遍历到这些变量定义使用对的测试用例，避免了选择所有通过某节点的测试用例而造成的测试时间和效力的消耗。由于策略改进和算法引入只是针对变量定义的修改，不考虑代码的删除，所以本发明公开的方法不会对安全性产生不利的影响，并且在一定范围内提高了测试用例选择的精确度。

说明书

技术领域

本发明涉及的是一种软件测试方法。特别涉及回归测试技术领域的一种基于控制流图遍历和切片前向遍历算法结合的选择性回归测试方法。

背景技术

软件测试是伴随着软件的产生而产生的，早期的软件开发过程中，测试的含义比较狭窄，将测试等同于“调试”。直到1957年，软件测试才开始与调试区别开来，成为一种发现软件缺陷的活动。目前国内外软件测试的研究热点在：软件测试过程模型、单元测试充分性标准、回归测试、嵌入式软件测试、面向对象软件测试、软件质量和复杂度度量、自动化测试数据生成等。其中，回归测试是软件测试领域中的一个重要研究方向。

在回归测试中，经常面临数量巨大的单元测试用例和复杂度很高的成员函数，如何从已存在的测试用例集中选择测试用例或者设计新的测试用例，从而既保证回归测试的质量，又提高回归测试效率，一直是回归测试面临的主要问题。

目前，已经存在几种选择性回归测试方法，在这一领域中，测试方法的优劣主要是通过安全性和精确度来衡量的，安全性和精确度的定义如下：

1.安全性

假设M是一个选择性回归测试方法，安全性是衡量M从测试用例集T中选择修改揭露测试用例的范围。我们定义安全性是根据一个特定的程序P、修改的程序P′和测试用例集T，具体如下：

定义：假设T包含了n个测试用例对于程序P和P′是修改揭露的，假设选择这些测试用例中的m个，则M关于P、P′和T的安全性如下：

$M_{\mathrm{safety}}=\left(\begin{array}{cc}m/n& n\ne 0\\ 100\%& n=0\end{array}\right)$

如果M确定地选择了所有的修改揭露测试用例，那么我们说M技术是安全的。如果M选择了一个已知的修改揭露的超集，则M也是安全的。例如，如果M选择了所有的修改遍历的测试用例对于控制性回归测试，那么M是安全。

如果M是安全的，则M选择了在T中每一个错误揭露测试用例，而如果M是不安全的，则它可能忽略一些暴露错误的测试用例，此外，我们假设M₁和M₂是两个选择性回归测试方法，若M₁比M₂有更大的安全性，则M₁相对M₂有更大的揭露错误的能力。

2.精确度

假设M是一个选择性回归测试方法，精确度衡量M忽略非修改揭露测试用例的程度，定义精确度根据一个特定的程序P、被修改的程序P′和测试用例集T，具体如下：

定义：假设测试用例集T中包含了n个测试用例是非修改揭露的，假设M忽略了其中的m个测试用例，则M关于P、P′和T的精确度如下：

$M_{\mathrm{precision}}=\left(\begin{array}{cc}m/n& n\ne 0\\ 100\%& n=0\end{array}\right)$

与安全性相似，对于任意的M、P、P′和T，还没有一个算法能够决定M关于P、P′和T的精确度，但是关于精确度，我们仍然能够得到一些有用的结论。首先，我们能够根据精确度来比较选择性回归测试方法M₁和M₂的优劣；其次，我们能够证明M是不是精确的，如果M选择一个非修改揭露的测试用例，则M是不精确的。

精确度是很有实用价值的，因为它衡量了一个选择性回归测试方法M避免选择一些测试用例的能力，而这些测试用例在P和P′上不能产生不同输出结果。一般来说，根据精确度比较选择性回归测试方法，能够识别哪一个方法执行更少的没必要的测试。

与本发明相关的文献包括：

[1]R.Gupta，M.J.Harrold，M.L.Soffa.An Approach to Regression Testing UsingSlicing；

[2]H.Agrawal，J.Horgan，E.Krauser，S.London.Incremental Regression Testing；

[3]Gregg Rothermel，Mary Jean Harrold.A Safe，Efficient Regression Test SelectionTechnique。

接下来分析三个典型的选择性回归测试方法，使用上述的框架来评估和分析它们，为了更加清晰地阐述安全性和精确度，这里用图1来描述，在椭圆内的所有测试用例都是修改遍历的，其余的测试用例则不是，在图1中，T′_{modification-revealing}阴影部分是修改揭露的测试用例集，因为修改遍历的测试用例集中一部分测试用例是修改揭露的，而另一部分却不是修改揭露的。

文献[1]提出了基于数据流的选择性回归测试方法。

安全性：

仅仅考虑了与变量定义使用对(define-use)有关的修改，因此它可能忽略一些修改揭露的测试用例，例如函数调用代码的删除不涉及变量的定义使用，该方法不能选择任何测试用例；相似地，如果一个测试用例执行一个新的或修改的输出语句，但是该语句中并没有包含变量的使用，该方法就不可能选择对应的测试用例，即使该语句对于P和P′是修改揭露的，因此数据流技术是不全的。

精确度：

1)仅仅选择执行那些新增加的、被修改的或被删除的变量定义使用对的测试用例，所以，数据流选择性回归测试技术典型地忽略了非修改遍历的测试用例；

2)数据流测试技术选择遍历新增加的、修改的或删除的定义使用对的测试用例，数据流技术就可能忽略一些测试用例，该测试用例达到了一个被修改的变量定义，但是却没有达到该变量的使用，这些测试用例是修改遍历的，但是非修改揭露的。

3)数据流技术可能忽略掉修改揭露的测试用例，例如，当代码的删除不涉及到变量定义使用时。

文献[2]定义了采用程序切片技术来实现选择性回归测试的方法。包括执行切片、动态切片、相关切片和近似相关切片四种切片类型。

安全性：

1)当程序P中包含了修改的断言语句时，动态切片技术可能忽略一些修改揭露的测试用例，所以该技术是不安全的，；当代码的修改没有改变程序P的控制流图或增加新的变量定义，其它的切片技术是安全的。

2)在程序P中增加断言语句或赋值语句将会对切片技术的安全性产生不利影响，例如在P中增加一个新的赋值语句s，因为程序切片技术获得的切片仅仅是包含在程序修改之前出现在程序P中的语句，任何测试用例的切片都不会包含语句s。但是，在测试程序P′时，在T中任何能够执行到s语句的测试用例都是修改揭露的，但是切片技术并没有选择这些测试用例，所以切片技术是不安全的。

精确度：

当代码修改是非结构化的，并且没有新代码的增加，切片技术仅仅选择修改遍历的测试用例。通过限制性地选择影响程序输出的测试用例，动态切片技术和相关切片技术在不同程度上排除了一些是修改遍历而不是修改揭露的测试用例。但是当程序P′中包含结构化的改变，该技术就可能选择非修改遍历的测试用例。

文献[3]提出了一个基于控制流图遍历技术的选择性回归测试方法。

安全性：

控制流图遍历技术选择了所有的修改遍历的测试用例，对于控制性回归测试，该技术是安全的。

精确度：

控制流图遍历技术并不是100％的精确的。控制流图具有一个多次被访问的节点(multiply-visited-node)特性，同时当程序P和P′中不含有该特性时，该技术精确地选择了修改遍历的测试用例；当程序P和P′中含有该特性时，该技术将可能选择了一些非修改遍历的测试用例。

发明内容

本发明的目的在于提供一种同时保证回归测试用例选择的安全性和精确度的基于控制流图遍历和切片前向遍历相结合的软件测试方法。

本发明的目的是通过如下步骤实现的：

A.分别创建原有程序及修改后的程序控制流图G和G′，对回归测试之前的测试用例集T中每一个测试用例，建立其与执行路径的对应关系；

B.对G和G′同步进行深度优先搜索遍历，比较每一个遍历能够到达的语句节点；对于代码中变量定义的改变，使用前向遍历算法只识别所有直接或间接被影响的变量定义使用对v_define～v_use，在T中选择遍历到变量定义使用对的测试用例；对于比较过程中其他的节点N和N′的语句词法不一致的情况，在T中选择所有能够达到该节点的测试用例；

C.列出从T中选出的所有适合修改后程序的测试用例。

上述技术方案中，所述步骤B进一步包括：

B1.根据步骤B中遍历得到的定义改变的变量，初始化其变量定义使用对集合，并记录该语句所在的节点位置；

B2.继续向前遍历：

1)若发现在一个语句中使用步骤B中遍历到的变量的值，将其放入定义使用对集合中；

2)若发现在一个语句中使用的变量控制依赖于步骤B中遍历到的变量的值，将其放入定义使用对集合中；

3)若发现在一个语句中，步骤B遍历得到的变量有一个新的定义，停止在该路径上的遍历；

B3.返回步骤B1记录的节点位置继续执行步骤B。

本发明在基于控制流图遍历的选择性回归测试方法的基础上，结合切片前向遍历算法，提出了一种改进的选择性回归测试方法，使其在保持基于控制流图遍历的选择性回归测试方法的完全安全的优点同时，进一步改提高回归测试用例选择的精确度。

本发明的方法区别于现有方法的显著特征在于：对于代码中存在的变量定义的改变，只需识别所有直接或间接被影响的变量定义使用对v_define～v_use即可，而不需选择所有通过该变量值定义的测试用例。直接被影响的变量定义使用对是指主要由于变量定义值的直接改变，例如定义语句x＝2被直接改为x＝3，代码改变并没有引入新的定义使用对，但是必须重新测试所有依赖变量x值的定义使用对；间接被影响的变量定义使用对是指某变量定义使用对的变量定义值依赖于被改变的变量值，或者是某变量定义使用对控制依赖于被改变的变量。选择遍历这些变量定义使用对的测试用例，即选择了所有的修改遍历的测试用例，因而也保证了其安全性。

本发明的方法的有益效果主要体现在：本发明中，对基于控制流图遍历的选择性回归测试方法的遍历策略进行改进，对于代码中变量定义的改变，引用切片前向遍历算法，识别所有直接或间接被影响的变量定义使用对v_define～v_use，并只选择遍历到这些变量定义使用对的测试用例，避免了选择所有通过某节点的测试用例而造成的测试时间和效力的消耗。由于改进只是针对变量定义的修改，不考虑代码的删除等，所以本发明公开的方法不会对安全性产生不利的影响，并且在一定范围内提高了测试用例选择的精确度。

附图说明

图1为测试用例集关系图；

图2为本发明公开的选择性回归测试方法的具体实施流程图；

图3为本发明公开的选择性回归测试方法选择的回归测试用例集图。

具体实施方式

下面结合附图举例对本发明做更详细地描述：

结合图2，主要包含以下几个步骤：

步骤1：分别创建原有程序及修改后的程序控制流图G和G′，对回归测试之前的测试用例集T中每一个测试用例，建立其与执行路径的对应关系。

步骤2：对G和G′同步深度优先搜索进行遍历，比较每一个遍历能够到达的语句节点。对于改变变量定义的节点，跳至步骤3；对于比较过程中节点N和N′的语句词法不一致的情况，在T中选择所有能够达到该节点的测试用例。

步骤3：首先对前向遍历算法ForwardWalk(Pairs)中的使用的变量和过程量进行说明：

算法ForwardWalk(Pairs)

输入Pairs：(s_i，v_i)受影响的变量定义的集合，其中s_i为变量v_i定义的语句，v_i为变量。

输出ValueUseTriples：{(s，u，v)}

声明In[i]，Out[i]，kill，NewIn：变量的集合

    Worklist，Cd[i]，OldCd，Affected Preds：语句的集合

    s：语句集

    v：原始变量集

    u：被改变的变量集

    k，n：语句

    i，x：节点

    DefsOfV[i]：(s，v)定义的集合

    Pred(i)，Succ(i)：程序控制流图中节点i的前驱、后继节点

    Def(i)：语句i定义的变量

具体如下：

对于改变变量定义的节点，初始化变量定义使用对集合ValueUseTriples：{(s，u，v)}，令得到受影响的变量定义的集合Pairs中每一个(s，v)中s的直接后继节点的深度优先搜索工作列表Worklist＝n_depth-first+Worklist。将控制流图中所有不在Pairs中的节点n_i的In[n_i]和Out[n_i]初始化为在Pairs中的节点s的In[s]初始化为Out[s]初始化为{(s，v)}。对于每一个语句节点n∈G，In和Out集合包含了定义值被修改或影响的变量，采用一个二元值用(d，p)表示，d为变量的位置，p为被改变或影响的变量，并且这些变量的使用将在后续遍历过程中被发现，集合In[n]表示在节点n之前变量的使用已经被发现，Out[n]表示在节点n之后变量的使用将会被发现。

步骤4：循环处理Worklist中的每个节点，如果则算法停止，否则从Worklist中取出第一个语句节点n，定义如果NewIn≠In[n]，则In[n]＝NewIn、

1)如果则所有k∈(OldCd-Cd(n))∩Affected Preds的语句，式(1)、(2)、(3)成立，如下：

In[n]＝In[n]-{(k，v_i)}                        (1)

AffectedPreds＝AffectedPreds-{k}              (2)

ValueUseTriples＝ValueUseTriples-{(k，u，v)}  (3)

对于所有(d，v)∈DefsOfV[k]的定义对，式(4)成立，如下：

ValueUseTriples＝ValueUseTriples∪{(d，u，v)} (4)

2)如果语句n计算使用了(d，v)∈In[n]的变量v，式(5)成立，如下：

ValueUseTriples＝ValueUseTriples∪{(d，n，v)} (5)

如果在该路径上发现了变量v的新定义，则停止(d，v)在该路径上的搜索，并且定义kill＝{(x，Def(n))：(x，Def(n))∈In[n]}，式(6)成立，如下：

Out[n]＝(In[n]-kill)∪{n，Def(n)}             (6)

3)如果语句n断言使用了(d，v)∈In[n]的变量v，式(7)成立，如下：

ValueUseTriples＝ValueUseTriples∪{(d，n，v)} (7)

再计算出达到该断言语句却不在In[n]中的定义集合，式(8)、(9)、(10)、(11)成立，如下：

DefsOfV[n]＝BackwardWalk(n，{v})-In[n]        (8)

In[n]＝In[n]∪{(n，v_i)：(d，v_i)∈DefOfV[n]}   (9)

Out[n]＝In[n]                            (10)

Affected Preds＝Affected Preds∪{n}      (11)

4)如果语句n定义了一个变量p，并且则Out[n]＝Out[n]∪{(n，Def(n))}；

5)否则Out[n]＝In[n]；

6)如果将n的所有后继节点x∈Succ(n)的深度优先搜索加入工作列表Worklist＝x_depth-first+Worklist；

7)如果则算法停止，返回ValueUseTriples，否则回到1)。

步骤5：在T中选择遍历ValueUseTriples集合中所有变量定义使用对的测试用例；

步骤6：返回至步骤2中变量定义改变的节点位置，继续基于控制流图的深度优先搜索遍历；

步骤7：遍历结束，列出从T中选出的所有适合修改后程序的测试用例。

以下通过实验来比较研究本发明公开的方法与以文献[3]方法的精确度和安全性，证明了本发明公开的方法在保证测试用例选择安全性的情况下，提高了精确度，比较结果详见表1。

表1  文献[3]方法和本发明公开的方法测试用例选择对照表

实验结果分析总结：

1)当被测试函数的复杂度越大——圈复杂度和节点数，如calcup、draw_ft、draw_feature和draw_sounding等函数，它们的复杂度都非常高。当仅仅在函数入口改变变量值时，本发明公开的方法能够较大幅度的提高基于控制流图遍历技术的精确度。

2)当被测试函数的复杂度较小时，函数内部的嵌套语句较少，或者被修改得定义值存在断言使用时，如getdeg、kp_sub、putspace和get_text_cmds等函数，本发明公开的方法与控制流图遍历技术的精确度基本一致。

3)当被测试函数内的全局变量值被修改，而在函数内不存在引用时，如getcmds和get_chinese_cmds函数，本发明公开的方法不会选择任何测试用例，而基于控制流图遍历算法会选择所有的测试用例。

综上所述，本发明公开的方法能够在一定范围内提高基于控制流图遍历的算法的精确度，如图3所示，由于本发明公开的方法只是针对变量定义的修改，不考虑代码的删除等，所以不会对安全性产生不利的影响。