基于函数调用的路径集成测试模型研究

同济大学软件学院 冯国尧

1 引言

软件测试是软件开发工程中的重要阶段，是保证软件质量，提高 软件可靠性的重要保障。路径覆盖测试是白盒测试的一种方法，即使是很小的程序，包含的逻辑路径数量也非常庞大，所以在大型程序中进行完全路径测试几乎是不可能完成的，所以本文提出以组件为单位的集成测试，将路径测试的级别提升到函数组件的级别上，同时找出一组基路径集进行测试，其他路径都可以由这组路径集线性表示。故而减少了测试的复杂度。

2 组件的集成

组件的集成是进行路径测试的第一步，根据函数间的调用关系，结合判断循环将各个组件进行结合。

定义1：函数组件调用图简称为调用图，常用来描述面向对象软件方法间的调用关系。可以提供大量的方法调用和对象类型信息。调用图CG=(V,E,v0, vn)中的节点V表示方法。节点间的有向边E表示方法间的调用关系,v0属于V为起始方法或入口方法。vn代表组件集成中唯一的结束节点。对于入口和出口不唯一的程序，我们可以采取构造虚拟入口，或虚拟出口使得该组件控制流图具有唯一的入口或出口。调用图上从节点vi到vj的边表示方法vi中的某个调用点调用方法vj.

函数组件之间[1]的调用图是根据函数间的条件循环判断分支进行集成的。四种基本的分支结构包括(1)顺序结构；(2)if判断结构；(3)循环分支；(4)swit ch分支。

一个程序函数组件调用图就是四种分支的组合形式。它反映了各个函数之间的调用关系图1就是一个函数组件的调用图。

其中图1中每一个节点代表一个函数组件或者一个判断循环分支，节点与节点之间的路径代表方法间的调用关系。例如：图中main()代表主函数入口，end()代表主函数出口。E(main,add)代表主函数main()调用add()函数。

图1 函数调用图

3 组件基路径集成测试

定义2：函数组件接口路径：两个函数之间存在某种调用关系，假设在函数组件控制流图中ci是cj的前驱节点，cj是ci的后继节点，那么存在一条从ci到cj的路径Pij，称之为组件ci到组件cj的调用接口路径。

定义3：函数组件执行路径：在组件控制流图中存在一条从c0（开始节点）开始到cn（结束节点）结束的路径，中间经过若干接口路径，如P0,n=（c0-＞ci-＞cj-＞cm-＞cn）(i,j,m＜n)，那么称这条路径为函数组件集成的执行路径。由此可见组件执行路径是从源节点开始到汇结点结束，中间经过若干调用接口路径的一条完整路径。

定义4：独立路径[2]：是一条组件执行路径，但是至少包含一条在其他路径中从未包含过的边的路径。

虽然我们把程序系统的代码分析粒度从语句扩展到了函数组件的级别，但是在一个庞大的系统当中，函数之间的调用还是比较复杂，从而进行集成测试也需要设计巨大的测试用例。因此，我们可以把每一条组件的执行路径看成向量空间的一个向量，我们从中找出一组路径，而其他路径可以由这组路径线性表示出来。那么我们称这组路径为函数集成测试的基路径集。

基路径[3]集中的每条路径具有下列特点：

（1）每一条路径都是一条独立路径，即每一条路径中都包含至少一条不包含在其它路径中的边；

（2）程序中所有的边都被该基本路径集的路径访问过；

（3）程序中的所有的，不属于该基路径集的路径都可以由该路径集中的路径通过线性运算得到。基路径集中的每一条路径称为一条组件执行路径。

组件集成的基路径集求解需要根据函数调用图计算出该调用图的环形复杂度(此即为基路径集合中独立路径的个数)。公式如下：

V（G）=E-N+2；

其中E为函数组件的接口路径数；N为节点的个数；

结合次公式可得出图2中的基路径独立路径的个数为8-7+2=3。

然后在根据函数调用图找出一条基础独立路径。其原则上尽量经过度为2的节点，和路径尽可能的达到最长。

4 函数组件基路径无效路径问题

4.1 无效路径的判断

无效路径[4]是指无论在什么样的情况下，没有任何输入能完整的执行这条路径。导致函数调用图中路径无效的一个主要原因是函数条件分支语句的相关性，即函数语句F1的值能直接决定其后续函数F2分支语句的取值结果或函数分支F2的值直接由该分支入口前的函数语句所确定。

我们在选择路径后，需要判定被选定的路径是否是有效的路径。或者在选择的同时就要判断节点会不会导致无效路径的产生。这样才能生成一条可执行的路径来对此设计测试用例。

定义5 函数依赖：在被测试的函数调用图当中，如果存在函数节点Ci与Cj，从节点Ci到节点Cj存在路径Pij，且节点Ci对特定的函数f()或者变量B进行了定义并初始化，则存在以下情况：如果Cj节点引用了变量B或者函数f()或者对变量B和函数重新进行了赋值或计算，并且在此路径上的其他节点没有对变量和函数重新定义或赋值，那么节点Cj函数依赖于节点Ci。

定义6 控制依赖：设Ci、Cj为函数调用图中的两个节点，若下列条件满足，则Ci控制依赖Cj,记为Ci—＞Cj。

(1)从Ci到Cj之间存在一条可执行路径P;

(2)在P上除了Ci,Cj外的每个节点Ck,节点Cj都是它的后必经节点。

设节点a,c为程序分支判断节点，b为函数赋值或执行的对应节点，f()为一个函数，若b节点执行f()或对f()定义赋值，且c节点使用了这个赋值，或者重新进行定义赋值，则b控制依赖于a,则c函数控制依赖于b。

4.2 无效路径的改造

假设有如下问题，只关注函数的调用关系，不关注实际的业务。

(1) if(*)

(2) c=add(a,b);

el se

(3) c=min(a,b);

(4) if(c==add(a,b)){

(5) if(**){

(6) s1();}

el se{

(7) s2(); } }

el se

(8)makeIt();其对应的函数调用图如图2所示。

图2 函数调用图

图3 改进后函数调用图

根据组件函数基路径测试可得出路径集有四条独立路径：{1-＞2-＞4-＞5-＞6-＞End,1-＞3-＞4-＞5-＞6-＞End,1-＞2-＞4-＞8-＞End, 1-＞2-＞4-＞5-＞7-＞End}

由于节点4函数控制依赖于节点2和节点3，存在1-＞3-＞4-＞5＞6-＞End这样的路径是不可达的。如果简单的将不可达路径从路径集中简单的去除，由于基路径的不唯一性，会造成有些可达边没有被包含到基路径集中。仔细分析，可以知道函数节点4的判定与节点2和节点3存在函数依赖关系。所以需要将节点4分割成两个节点为4和4’，4’为4的相反判定即4的el se分支。那么就排除了函数不可达路径。改进后的函数调用图如图3所示。

由此改进后的函数调用图可得出基路径中独立路径的条数为4条，分别是：1-＞2-＞4-＞5-＞6-＞end,1-＞3-＞4’-＞8-＞end,1-＞2-＞4-＞8-＞end,1-＞2-＞5-＞7-＞end.这四条路径全部是可达的路径。不存在无效路径的问题，该方法不仅适用于函数调用图的基路径无效路径的判定，而且适用于单元程序图的基路径判定。

5 总结

我们首先要对函数的控制流分支进行插装分析，对被测的程序进行预处理，生成相应的带有控制逻辑的函数调用图，并获取全部的函数调用路径，然后结合基路径的测试思想生成独立路径集。接着对路径中的节点就行函数依赖和控制依赖分析，找出无效路径。然后用构造无效节点的副节点的方法对无效路径进行改造。最终生成可执行路径，找出可执行路径的路径集合。这样就生成了基于调用图的集成测试模型。

[1]崔霞,高建华.一种新的测试集简化的测试覆盖准则[J].计算机科学,2009,36(1):244-246.

[2]伦立军,孔庆彦,孙鹏飞,宋益波.一种软件体系结构级路径覆盖方法[J].小型微型计算机系统,2010,11(11):2166-2168.

[3]安金霞,王国庆,李树芳,等.基于多维度覆盖率的软件测试动态评价方法[J].软件学报,2010,21(9):2135-2147.

[4]杜庆峰.高级软件测试技术[M].北京:清华大学出版社,2011:108-112.