基本路径测试用例设计的改进方法

王 敏 马 敏 张 志

(湖北广播电视大学软件工程学院 湖北 武汉 430074)

0 引 言

研究表明，软件测试是软件质量保证的重要手段。虽然早在20世纪70年代软件测试的基础理论和方法体系就已初步建立，但迄今为止软件测试的很多理论和方法仍然停留在早期的状态，已不能满足实际应用中对测试效率和实用性的需求。寻找新的测试技术以应对软件的测试需求依然是软件工程研究者们需要探索的问题。

软件测试过程中的单元测试可以发现大约80%的软件缺陷，同时，由于软件缺陷的放大效应，单元测试阶段的动态白盒测试对尽早发现软件缺陷、降低项目风险起着重要的作用。McCabe提出基本路径测试法被认为是动态白盒测试技术中严谨而有效的测试方法，其基本思想是在程序控制流图的基础上, 通过分析控制结构的环路复杂度导出基本路径集,以此作为设计测试用例的依据。但是当程序逻辑结构较为复杂时，人工实现变得比较困难，进而对测试用例设计的效率和正确性都有较大的影响。

人们针对基本路径集求解问题提出了各种算法[1-5]，但迄今为止都是拘泥于McCabe的基本思想进行的一系列基本路径集求解算法的改进，仍然不能完满地对应各种程序结构。近期的研究提出了基于路径字符串组合的基本路径集求解算法[6-7]，该算法较好地实现了基本路径的自动生成，但此方法未对应条件拆分的问题。因此，本文拟借助决策表解决基本路径集求解中的条件拆分问题。

1 条件拆分问题的对应思路

研究发现[6-7]：所有程序都是由若干基本程序结构(顺序、分支和循环)构成，提出了基于Z路径覆盖的基本单元图，从而可得到构成基本单元图的基本子路径。程序基本单元通过嵌套(并联)组合或顺序(串联)组合形成各种应用程序的控制流图，由此探索出了基本子路径按照一定方式组合生成基本路径集的算法。但该算法将所有分支结构的判断语句视为一个节点，没考虑判定语句中含多个条件的情况，这将导致程序中含多条件的判断语句时，测试用例的条件覆盖率不够充分。为此借鉴决策表法，将决策表融入基本路径集求解方法中，以解决基本路径测试中的条件覆盖不充分的问题。

文献[8]为实现多条件组合问题的自动化测试用例设计，提出了一种用于表示关系和约束的因果表达式，根据因果表达式可实现决策表的简化，从而按简化后的规则自动生成测试用例。

在以上研究成果的基础上，本文提出基本路径集求解问题中条件拆分的对应方法，基本思路是：采用路径字符串组合法[6]，在基本单元信息提取的同时提取分支节点的判断语句信息，若判断语句为含多个条件的逻辑表达式，则赋予分支节点特殊的标志；然后对含多个条件的判断语句进行分析，形成因果表达式[8]，借助于因果表达式生成并简化决策表；最后将精简后的规则形成规则路径集组合到对应的基本路径集中，从而形成含满足条件覆盖的基本路径集。

2 决策表在基本路径集求解中的应用

按照以上思路，首先用常规方法结合实例对含多条件的判断语句进行人工条件拆分，求得基本路径集；然后将决策表应用于条件拆分问题，寻找基本路径求解方法；最后将人工拆分条件的方法与决策表法进行比较，验证方法的正确性。

2.1 基本路径集求解中的条件拆分

为便于描述，借用文献[6]中的伪代码进行说明，该伪代码中的“条件表达式”默认为仅含一个条件(关系运算)，对该代码进行修改，将条件表达式2替换为含2个条件逻辑与运算的多条件表达式，修改后的伪代码如下：

例1：

1. while (条件表达式1)

//含1个关系运算

2. {

3. 语句1

4. }

5. if (条件表达式21 && 条件表达式22)

//含2个关系运算

6. {

7. if (条件表达式3)

//含1个关系运算

8. {

9. 语句3；

10. }

11. else

12. {

13. 语句4；

14. }

15. }

16. else

17. {

18. 语句5

19. }

若不考虑条件拆分，采用文献[6]中路径字符串组合算法，其基本路径集P1为：

路径1：1→4→5→18→19

路径2：1→4→5→7→9→14→19

路径3：1→3→4→5→7→13→14→19

由于节点5含多个条件，为满足条件覆盖需要进行条件拆分，分析例1的代码可知，条件表达式结果为TRUE进入第7行语句，否则进入第18行语句，对例1进行条件拆分，其代码改写为：

1. while (条件表达式1)

2. {

3. 语句1

4. }

5. if (条件表达式21)

5.1. {

5.2. if(条件表达式22)

6. {

7. if (条件表达式3)

8. {

9. 语句3；

10. }

11. else

12. {

13. 语句4；

14. }

15. }

15.1. else

15.2. {

15.3. 语句5

15.4. }

15.5. }

16. else

17. {

18. 语句5

19. }

按照文献[6]提出的基本单元图，改写代码段对应的控制流图如图1(a)所示，按路径字符串组合算法，其可能的一组基本路径集P2为：

路径1：1→4→5→18→19

路径2：1→4→5→5.2→15.3→15.5→19

路径3：1→3→4→5→5.2→7→9→14→15.5→19

路径4：1→3→4→5→5.2→7→13→14→15.5→19

图1 条件拆分代码的控制流图

由于15.3行语句与18行语句等价，节点15.5可合并为节点19，因此图1(a)等价于图1(b)，假设第5行代码包含的两个条件用C1、C2表示，其组合值(C1,C2)有(0,0)、(0,1)、(1,0)、(1,1)四对取值，图1(b)对应的基本路径集和条件组合如下：

路径1：1→4→5→18→19 对应条件组合(0,1)和(0,0)

路径2：1→4→5→5.2→18→19 对应条件组合(1,0)

路径3：1→3→4→5→5.2→7→9→14→19 对应条件组合(1,1)

路径4：1→3→4→5→5.2→7→13→14→19 对应条件组合(1,1)

以上是通过人工进行条件拆分(代码改写)求得的基本路径集，代码改写过程较为复杂，不便于通过算法自动生成基本路径集。因此需要寻找便于算法实现的方法对应条件拆分的问题。

2.2 决策表的应用

在黑盒测试中，多条件组合问题常常采用决策表法进行测试用例设计，针对多条件组合的测试用例设计已有算法实现测试用例的自动生成[8]，因此，拟尝试引入决策表法应对多条件判断语句的条件拆分问题。

(1) 含决策表节点的基本路径集 若不考虑条件拆分，例1对应的控制流图如图2(a)所示。当考虑条件拆分时，将含多个条件的判断节点转化为一个决策表节点，即将圆形节点5转化为一个方形的决策表节点，如图2(a)的控制流图改造为图2(b)。为与最终产生的基本路径集进行区分，将含决策表节点的基本路径集称为“T基本路径集”，集合中的路径称为“T基本路径”，对应的基本路径集P3记为T基本路径集Pt：

路径1：1→4→T5→18→19

路径2：1→4→T5→7→9→14→19

路径3：1→3→4→T5→7→13→14→19

图2 例1对应的控制流图

(2) 决策表与规则路径 针对例1的决策表T5如表1所示，将T5的动作桩设定为“进入”T5节点后继的分支节点，例1中，决策表节点T5的后继分支节点有节点7和节点18，因此动作桩设为“进入18”(表示程序进入第18行执行)和 “进入7”(表示程序进入第7行代码执行)，如此描述动作桩既直观又便于后续规则路径的生成及与基本路径的组合。

表1 T5对应的决策表

我们将每一条规则转化为一条“规则路径”，定义规则路径的语法格式为：

Tn(C1，C2，…,Cm)-pe

式中：Tn为判定节点；(C1，C2，…,Cm)为条件组合值；pe为Tn的某一后继节点。故可得例1中T5的规则路径集Pr如下：

Pr={T5(0,0)-18，T5(0,1)-18，T5(1,0)-18，T5(1,1)-7}

(3) T基本路径集与规则路径集的组合规则 同样以例1为例，当条件值满足规则1、规则2和规则3时，程序将沿T基本路径1执行，条件值满足规则4时，程序将沿T基本路径2或3执行。若要求基本路径覆盖所有条件(规则)，T基本路径1需与T5(0,0)-18、T5(0,1)-18、T5(1,0)-18三条规则路径组合，规则路径T5(1,1)-7需与T基本路径2和3组合。而T基本路径集Pt与规则路径集Pr如何组合，是需要进一步分析的问题。

将规则路径Tn(C1，C2，…,Cm)-pe中条件组合(C1，C2，…,Cm)用通配符“*”代替，我们将“Tn*-px”相同的规则路径组成集合Rni(针对Tn决策表，含i条规则路径的路径集合)，将T基本路径集中包含相同“Tm-py”子路径的路径组成集合Pnj(针对Tn决策表，含j条T基本路径的路径集合)，若Tn=Tm，且px=py，则规则路径集Rni与T基本路径集Pnj是具有组合关系的一对路径集。下面进一步讨论规则路径集Rni与T基本路径集Pnj的组合规则。

假设规则路径集Rni与路径集Pnj具有组合关系，则二者组合形成的路径数为Max(i，j)。若i≥j，则按一定的顺序将j条规则与j条路径一对一组合，余下的i-j条规则随机与j条路径中任意路径随机组合；若i

按以上组合规则例1将形成5条基本路径，路径组合的结果不唯一，以下路径集P4为可能的组合之一：

路径1：1→4→T5(0，0)→18→19

路径2：1→4→T5(0，1)→18→19

路径3：1→4→T5(1，0)→18→19

路径4：1→4→T5(1,1)→7→9→14→19

路径5：1→3→4→T5(1,1)→7→13→14→19

(4) 测试用例的精简 在组合条件数较少的情况下，覆盖所有条件组合较容易实现，由于条件数n与其组合规则数2n呈指数关系，当条件数较多时，规则数将是一个较大的数值，因此，有必要对决策表进行化简。对决策表1进行化简得决策表2，可得规则路径集Pr如下：

Pr={T5(0,-)-18，T5(1,0)-18，T5(1,1)-7}

式中：“-”代表0和1中的任意值，按规则路径集与T基本路径集的组合规则，得基本路径集P5如下：

路径1：1→4→T5(0，-)→18→19

路径2：1→4→T5(1，0)→18→19

路径3：1→4→T5(1,1)→7→9→14→19

路径4：1→3→4→T5(1,1)→7→13→14→19

表2 决策表T5简化结果

采用决策表法得到基本路径集P5与人工进行代码拆分后形成的基本路径集P2相吻合。实验借助其他经典代码进行了验证，证实采用决策表法形成的基本路径集与通过人工代码拆分形成的基本路径集一致，因此，采用决策表对应条件拆分问题是可行的。

文献[6-7]以及文献[8]分别实现了基本路径集的自动求解和决策表的自动简化及用例生成，因此将二者结合便能通过算法对应基本路径集求解中条件拆分的问题。

3 测试工具设计

对应条件拆分的基本路径集求解工具将在文献[7]工具的基础上进行功能扩展。追加功能主要包含以下几点：

(1) 多条件信息的提取。在进行代码扫描提取程序基本信息时，对判断语句信息进行分析，若判断语句含多个条件，则将判断语句提取出来用于条件拆分处理使用；同时将含多条件判断语句的节点标识为“T+行号”，以便规则路径与T基本路径组合时识别。

(2) 决策表化简。根据提取的判断语句信息，采用文献[8]中的因果表达式描述多条件的逻辑关系，利用文献[8]中“因果表达式法测试用例设计”工具化简决策表，得到精简后的有效规则。

(3) 规则路径生成。根据化简后的决策表，将有效规则生成规则路径。

(4) 规则路径与T基本路径的组合。按规则路径与T基本路径的组合规则进行路径组合，形成达到一定条件覆盖的基本路径集。

3.1 界面设计

工具主界面设计如图3所示，复选框【条件拆分】选中时，将对应多条件拆分的测试用例设计。单击【多条件对应】按钮，将生成含决策表节点的T基本路径集，同时输出含多条件的判断语句。随后启动“因果表达式法测试用设计”界面，界面设计如图4所示。在该界面完成因果表达式输入，生成精简后的有效规则及规则路径，关闭“因果表达式法测试用设计”界面，返回主界面，单击【基本路径生成】将完成规则路径与T基本路径的组合，形成满足条件覆盖的基本路径集。

(a) 初始界面

(b) 执行结果界面图3 工具主界面

图4 因果表达式法测试用例设计界面

3.2 工具实现流程

当【条件拆分】勾选时，【多条件对应】按钮可用，单击该按钮的处理流程与文献[7]基本路径集构造流程图基本一致。如图5所示，本工具的区别在于：① 在基本信息提取处理中，追加了对条件语句是否为多条件的判断，若为多条件语句，则在节点编号前加标志“T”，同时提取出该判断语句的条件信息；② 后续的基本路径生成算法不变，但含多条件的节点在路径中表示为“Tn”(n为节点编号)；③ 输出结果中增加了多条件语句信息，用于编辑因果表达式，生成决策表和对决策表进行化简。

图5 T基本路径集生成流程图

单击主界面的【基本路径生成】，若不勾选【条件拆分】，将按文献[7]进行基本路径集求解，若勾选【条件拆分】，则完成规则路径集与T基本路径集的组合，形成基本路径集。

3.3 工具在智能机器人控制软件中的应用

进行智能机器人控制软件的研发过程中，对软件的维护频率高、测试效率比较低下，将本工具应用于该系统的白盒测试，有效提高了测试效率。

图6为一个机器手臂寻迹处理软件代码文件MainWindow.xaml.cs中的被测代码段截图。代码扫描提取出了多条件信息T34：(obj.Name==″sld1″ || obj.Name==″sldAcc″)，生成的T基本路径集如下：

路径1：34-35-50；

路径2：34-42-T43-49-50；

路径3：34-42-T43-44-49-50。

图6 被测程序代码段

根据多条件信息T34：(obj.Name == ″sld1″ || obj.Name == ″sldAcc″)，可得条件和结果信息如下：

C[1]:obj.Name == ″sld1″；

C[2]:obj.Name == ″sldAcc″;

E[1]:进入44；

E[2]:进入49。

根据关系表达式和约束表达式的语法规则[7]，由于obj.Name不可能同时等于″sld1″和″sldAcc″，因此有约束表达式：

Y[1]:E(C[1]，C[2])；

原因C[1]和C[2]之间为“或”关系，可得关系表达式：

R[1]:OR(C[1]，C[2])=E[1]；

R[2]:AND(NEG(C[1])，NEG(C[2]))=E[2]。

采用因果表达式法测试用例设计工具，输入以上条件、结果、约束和关系表达式，生成测试用例如图7(a)所示，可观察决策表简化信息如图7(b)所示，因Y[1]约束制约，规则4为不存在的规则，规则1-规则3均为有效规则。

(a) 用例生成结果

(b) 简化过程表图7 因果表达式法测试用例设计运行结果

依据决策表可形成规则路径：

规则路径1：T43(0,0)-49；

规则路径2：T43(0,1)-44；

规则路径3：T43(1,0)-44。

返回主界面单击【基本路径生成】，完成规则路径与T基本路径的组合，得基本路径集如下：

路径1：34-35-50；

路径2：34-42-T43(0,0)-49-50；

路径3：34-42-T43(0,1)-44-49-50；

路径4：34-42-T43(1,0)-44-49-50。

对应条件拆分后，基本路径数由原来的3条变成了4条。这与采用人工拆分代码生成的测试用例一致。

3.4 工具算法分析

工具实现借鉴了文献[6-8]中的基本算法，其中追加的规则路径与T基本路径的组合算法与文献[6]中的串联组合一致，因此，工具的算法时间复杂度与文献[6]一致，T(n)=O(n)。

4 结 语

本文提出的基本路径集求解方法，借鉴路径字符串组合算法，在扫描被测代码获取基本路径信息的同时对判断节点的条件信息进行判断，获取含多条件组合的判断语句信息，并生成字符串形式的T基本路径集。采用因果表达式描述多条件间的逻辑关系，依据因果表达式生成并化简决策表，形成字符串形式的有效规则路径集。将T基本路径集与有效规则路径集进行组合即可得到满足条件覆盖的基本路径集。该方法对应了文献[7]基本路径集求解算法中的条件拆分问题。在后续研究中，我们将继续采用适当的算法解决不可达路径问题，以较完满地实现基本路径集的自动求解。