一种覆盖测试中路径集的自动生成方法

詹泽梅

摘要： 覆盖测试是软件测试中的重要方法，路径覆盖测试中路径集的自动生成能提高测试效率。该文提出了一种描述程序分支情况的分支关系图，给出了基于分支关系图的路径集自动生成算法，实验证明了该方法的正确性，能有效地求出程序路径集。

关键词：路径集；分支关系图；软件测试

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）25-5898-04

An Method of Automatic Generation for Paths Set in Software Coverage Testing

ZHAN Ze-mei

（Computer Science College， Yangtze University， Jingzhou 434023，China）

Abstract： Coverage testing is a important method for software testing. Automatic generation for paths set can enhance testing efficiency. A graph of branch relation is proposed for depicting branches in the program. The paper gives an algorithm for finding out paths set， which can work efficiently. The correctness of the algorithm is verified on a example.

Key words： paths set；the graph of branch relation； software testing

软件测试是软件工程理论中非常重要的一个方面，是提高软件产品质量和可靠性的关键。软件测试可以分为功能测试和结构测试两大类。其中结构测试又称为白盒测试，是基于程序结构特征，以实现某种测试覆盖为目的一种测试方法。路径覆盖就是一种针对结构测试的常用充分性准则[1]，该方法可以有效地检测程序中的错误。基于路径覆盖的测试[2]是设计足够的测试数据，覆盖程序中所有可能的路径。目前设计测试用例基本上是预先确定路径，针对路径设计对应的测试用例，所以路径集的确定对于路径覆盖测试非常重要。如果完全靠人工确定路径集会花费很大精力，因此应该借助于自动化的方法。

路径集就是指程序中所有可能的路径的集合。路径集中没有两条完全相同的路径。由于程序中存在分支语句、循环语句，程序中的路径的数目会非常大，因此，在有限的测试资源下进行路径覆盖测试，我们只考虑循环的两种可能：循环体未执行和循环体至少执行一次。

目前已有的路径集生成方法有：采用遗传算法进行路径生成的方法[3]和A. Bertolino 利用简化的控制流图来确定程序路径。这些方法为生成程序的路径提供了帮助，但不能保证生成的完整的路径集。该文提出一种基于分支关系图的路径集生成方法，生成完整的路径集。

1 程序路径的表示

本质上，程序的执行表现为一系列判定条件取值的组合。例如程序1判断三角形形状的代码如下。

1 main（ ）

2 {int a，b，c；

3 scanf（“%d%d%d”，&a，&b，&c）；

4 if （（a+b>c）&&（b+c>a）&&（a+c>b））

5 {if（（a！=b）&&（b！=c）&&（c！=a））

6 printf（"这是一个普通三角形"）；

7 else

8 if（（（a==b）&&（b！=c））||（（b==c）&&（c！=a））||（（c==a）&&（a！=b）））

9 printf（"这是一个等腰三角形"）；

10 else

11 printf（"这是一个等边三角形"）； } }

12 else

13 printf（"这不是一个三角形"）；}

该程序总共有四条可执行路径，路径1：1 2 3 4 12 13，路经2：1 2 3 4 5 6，路经3：1 2 3 4 5 7 8 9，路经4：1 2 3 4 5 7 8 10 11。程序中的判定条件有3个，判定条件1：（a+b>c）&&（b+c>a）&&（a+c>b），判定条件2：（a！=b）&&（b！=c）&&（c！=a），判定条件3：（（a==b）&&（b！=c））||（（b==c）&&（c！=a））||（（c==a）&&（a！=b）） 。四条执行路经可用判定条件组合值来表示。由于判定条件可能被执行到，也可能未被执行到，例如路径1中判定条件1执行到了，而判定条件2和3就未执行到。假设未被执行到的判定条件其值用[φ]表示，执行到的判定条件就用它的具体值表示，被执行到的判定条件取值可为1或0或者其他整型值（switch语句中的条件值）。例1中程序的四条路径可用判定条件组合值表示，路径1：0[φ][φ]，路径2：1 1[φ]，路经3：1 0 1，路经4：1 0 0。

本文中采用字符串表示路径，可将路径的组合值转换为字符串形式，在分支序号前加字母c，在取值前加字母v，对未被执行到的分支可省略，例如路径1可表示为c1v0，路径4表示为c1v1c2v0c3v0。

2 分支关系图

2.1 分支结点

分支关系图表示程序中分支情况，由于对于循环语句只考虑其循环体被执行和未被执行两种情况，所以分支关系图也描述了循环语句产生的分支。分支关系图中一个结点代表一个条件分支，结点中记录了该分支的判定条件序号和取值等信息，结点类型struct node定义如下：

struct node{

int number；

int value；

struct node * left；

struct node * right；

struct node * parallel；

}

number属性表示判定条件序号，value属性表示判定条件取值，left属性指向内层语句中的分支结点。内层语句包括if子句、else子句、case后语句、循环体语句。right指向同一判定条件的其他分支，同属于一个判定条件的分支取值互不相同。parallel指向同层次的其他判定条件的分支结点。

2.2 分支关系图的创建

在遍历抽象语法树的过程中建立程序分支关系图。在遍历的过程中，遇到不同的节点进行不同的处理，直到扫描结束。

当被扫描结点为赋值语句或表达式语句或输入输出语句时，直接跳过，不进行任何操作。

当被扫描结点为if语句，则为该if语句的判定条件建立值为1的分支节点，和值为0的分支结点，再扫描if子句和扫描else子句。

当被扫描结点为循环语句时，则为该循环条件建立值为1和值为0的分支结点，再扫描循环体。若被扫描结点为switch语句则为每个case和default建立一个分支结点，再扫描每个case分支语句。

程序1对应的分支关系图如图1。

图1 程序1的分支关系图

3 路径集生成算法

3.1 算法

建立分支关系图后，通过遍历该图生成路径集。在遍历过程中记录结点的分支序号和取值，在分支序号前加字母c，在取值前加字母v，将记录的分支组合值字符串与该结点三个指针所指分支的组合值字符串进行某种形式的连接。结点与其left所指分支属于外层和内层关系，应进行组合值字符串的直接连接；结点与其right所指分支结点为同一判定条件的不同取值结点，分属于不同的路径，是并列关系，应用逗号连接组合值字符串；结点与parallel所指分支属于同一层次，两组合值字符串应进行路经个体的矢量相乘。详细算法如下。

算法1：Point（ ）//描述结点与其left所指分支之间的组合值字符串直接连接

参数：str1字符串1首地址，str2字符串2首地址

返回值：结果字符串地址

{ char t[60]，*p2=0，*q；

if （*str2=='c'）// c1v0·c2v1形式

{q为str1字符串和str2字符串直接相连}

if（*str2=='{'） // c1v0·{c2v1，c2v0}形式

{ 计算str2中条件组合值的个数i

计算结果字符串的大致长度n

q= （char *）malloc（n）；

q[0]='＼0'；

p2=str2+1；

将str2中条件组合值逐个与str1中值直接连接，并加入q中 }

return q；

}

算法2：VectorMulti（ ）//描述结点与其parallel所指分支之间的组合值字符串矢量乘

参数：str1字符串1首地址，str2字符串2首地址

返回值：结果字符串地址

{char *s；

计算str1中条件组合值的个数i1和str2中条件组合值的个数i2；

计算结果字符串的大致长度n；

s=（char *）malloc（n）；

s[0]={ ‘； s[1]=＼0；

while（str1中每一个条件组合值t1）

While（str2中每一个条件组合值t2）

{ 将t1与t2直接相连，并复制到s末尾

向s中加入逗号分隔符“，”； }

strcat（s，” }”）；

return s；

}

算法3：Comma（ ）//描述结点与其right所指分支之间的组合值字符串逗号连接

参数：str1字符串1首地址，str2字符串2首地址

返回值：结果字符串地址

{char * p；

p=（char）malloc（strlen（str1）+strlen（str2））；

将”{”复制到p中；

将str1中的分支条件值字符串复制到p末尾；

将逗号加入p字符串末尾；

将str2中的分支条件值字符串加入p字符串末尾；

将”}”复制到p末尾；

return p；

}

算法4：TravelGraph（）//遍历分支关系图，求路径集字符串。

参数：分支关系图根指针root

返回值：字符串地址

{计算该节点字符串p=“c”+number+”v”+value；

if（（root->left==0）&&（root->right==0）&&（root->parallel==0））

{ return p；}

else if （（root->left==0）&&（root->parallel==0））

{ q=Comma（p， TravelGraph （root->right ））； return q；}

else if（（root->right==0）&&（root->parallel==0））

{q=Point（p， TravelGraph （root->left））； return q；}

else if （root->left==0）

{q=Comma（p， TravelGraph （root->right ））； w=VectorMulti（q，TravelGraph（root->parallel））； return w；}

else if （root->parallel==0）

{q=Point（p， TravelGraph （root->left））； w=Comma（q， TravelGraph （root->right ））； return w；}

else if

（（root->left！=0）&&（root->right！=0）&&（root->parallel！=0））

{q=Point（p，TravelGraph（root->left））；w=Comma（q， TravelGraph （root->right））； s=VectorMulti（w，TravelGraph（root->parallel））； return s；}

else {printf（“错误，结点异常”）；}

}

3.2 实例分析

利用本算法对程序1进行扫描分析，最终求得的路径集结果为：c1v1c2v1， c1v1c2v0c3v1， c1v1c2v0c3v0，c1v0。该结果字符串清楚地表示了程序1的所有路径及每条路径的判定条件组合值，实验证明了本算法能有效地自动生成路径集。

4 结束语

面向路径覆盖的测试用例自动生成必须首先确定路径集，该文提出了一种路径集的自动生成方法，首先在扫描抽象语法树的过程中建立分支关系图，然后遍历分支关系图求出程序的路径集。实验证明该方法能有效的求出程序的路径集。但是，本方法仍然存在缺陷，在某些情况下求得的路径集中会存在不可达的路径，如何排除路径集中全部不可达路径是下一步要研究的问题。

参考文献：

[1] Bertolino A，Marré M.How Many Paths Are Needed for Branch Testing？[J].The Journal of Systems and Software，1996，35（2）：95-106.

[2] Jin-Cherng Lin，Pu-Lin Yeh.Automatic Test Data Generation for Path Testing Using GAs[J].An International Journal，2001，131：47-64.

[3] Bint J R，Site R.Optimizing Testing Efficiency with Error Prone Path Identification and Genetic Algorithms[C] //Proc.of Australian Software Engineering Conference，2004：106-115.