体现分支覆盖情况的基本路径集自动生成算法

徐烂　陈磊

摘要：在软件测试中，各种基本路径自动生成算法已经在单元测试中得到充分运用，使得单元测试的效率得到了极大提高。但是这些基本路径自动生成算法生成的基本路径并不能直观反应它们对程序的覆盖情况。该文提出一种算法，它采用最短路径复用及分支结点逐个覆盖法，使得生成的基本路径最短，重要的是每条基本路径能显示它是为了覆盖哪个分支结点而存在。它能够减少测试者根据基本路经集设计测试用例的时间，从而提高单元及其回归测试效率。实践表明，此算法具有很好的应用效果，特别适用于自动化生成的测试用例不能满足覆盖率要求需要人工生成测试用例的复杂单元。

关键词：单元测试；回归测试；基本路径

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

An Automatic Generation Algorithm of Basic Path Set— Reflect the Situation of Branch Coverage

XU Lan， CHEN Lei

（College of Computer， University of South China， Hengyang 421001， China）

Abstract： As all kinds of algorithms about the generation of basic path set have given plenty of exercise in the software testing， so that it improves the efficiency of unit testing greatly. But each basic path generated by those algorithms cant reflect which portions of the code have been covered intuitively. This article comes up with a new algorithm which can generate the shortest basic path for it adopts methods of reusing shortest path and covering branch node one by one. Whats more， the basic path generated by this algorithm can reflect which branch node it has cover. This algorithm will help us narrow the time when we design the test case based on basic paths， and improve the efficiency of unit and regression testing. The practice shows that my algorithm has a good effect especially on complex units that need generate test cases artificially for the automatic generation of test cases cannot meet the coverage requirements.

Key words： unit testing； regression testing； basic path

目前单元测试中自动化生成测试用例的算法及测试工具已有多种，但是它们自动生成的测试用例不尽如人意。自动生成测试用例的算法中，遗传性算法较为复杂且收敛性差、基于蚁群及粒子群的算法容易产生早熟现象、随机算法因呈现出较大的盲目性导致覆盖率低[1]。覆盖率是单元测试重要的衡量标准，包括语句覆盖、分支覆盖、条件覆盖、判定-条件覆盖、路径覆盖等等。像工具C++test，它能够为函数自动生成测试用例并执行，但是很难达到覆盖率要求，所以很多情况下还是得根据基本路径人工生成测试用例的数据来进行单元测试。

人工生成测试用例最重要的环节是基本路径集的寻找，寻找完基本路径集后根据每条基本路径设计对应测试用例。进行单元回归测试时，若代码做了修改，基本路径集就得做调整，或是增加测试用例来覆盖某个分支达到测试覆盖率，或是删除某个多余的用例。当设计某条测试用例的时候，可以在其他测试用例的基础上做修改，因为它们可能有共同的必经分支结点，那么这两条路径有共同的参数及前置条件，可以复用这些数据来减少设计测试用例的时间。那么如何寻找这条被参考的用例呢？基本路径与测试用例相对应，如果能从基本路径集中看出覆盖必经分支结点的是哪条路径，那么就能找到参考用例，节省了寻找参考测试用例的时间。不过，这对基本路径的生成有要求，即生成的路径能反应分支结点的覆盖情况。

在提出基本路径测试法的同时McCabe就提出了两种方法来实现：一是通过控制流图求解基本路径集；第二种是直接遍历程序求得基本路径集。这两种方法被认为是动态白盒测试技术中严谨而有效的测试方法。针对这两种方法，人们提出了各种基本路径集的求解算法[1-10]，如：路径字符串组合算法[2]、基于图深度优先搜索算法等[5]，基于状态图的测试路径自动生成算法[7]等。但这些算法均未体现对代码的覆盖情况，当测试单元比较复杂、路径比较多而测试用例由人工来根据基本路径来生成时，这些算法生成的路径就不能快速地帮测试员定位参考用例。 本文提出的基本路径集生成算法，它将覆盖同一分支的基本路径排列到一起，并且基本路径集中的路径按分支编号从小到大排列，方便定位参考用例。下面将介绍此算法：endprint

1 算法介绍

1.1 基本概念

1） 结点的出度。从结点A有N条边出来，A的出度就是N；

2）分支结点。流程图中，出度>=2的结点；

3）独立路径。在程序中至少引进一条新的语句或是一个新的条件的路径。采用控制流图的术语来表示，即路径P至少包含一条在其他路径中从未有过的边；

P=< N0， N1 … Nf >

（N为控制流图中的节点，N0代表程序入口，Nf代表程序出口）

4）程序环路复杂性或是圈复杂度。又称McCabe复杂性度量，从圈复杂度可以导出基本路径中的独立路径数。E为控制流图的边数，N为图的节点数。

计算公式为：V（G） = E-N+2.

5）程序基本路径集。基本路径集中的每条独立路径称为基本路径。这些路径具有如下特点：

①每一条路径都是独立路径；

②程序中所有的边都被访问；

③程序中所有的、不属于该基本路径集的路径都可以由这个基本路径集中的路径经过线性运算得到。

1.2 算法对流程图的编号要求

1）先编开始结点，为0；

2）其次编分支结点（结点出度数>=2），从1往后编；

3）再编执行语句结点；

4）最后编结束结点；

示例流程图如图1。

图1 被测程序流程图

1.3 路径生成算法思路

1）为了体现基本路径对分支结点的覆盖情况，采用搜索分支结点的方式来生成基本路径集。按照分支编号由小到大的方式搜索，对于搜索到的每一个分支结点，查看是否有未曾访问的边连接到其他结点，若有则以此为一条新边添加到路径，然后沿此新边分别向上扩展寻找到开始结点的通路，和向下扩展寻找到结束结点的通路。这样从开始结点到结束结点形成一条完整的通路，此通路上的结点连接起来就为一条基本路径。在寻找路径的时候有如下要求：若搜索到的分支结点存在多条未访问边连接到其它结点，且所有边连接的结点中有未访问结点，则优先以此分支结点和未访问结点（存在多个的话，优先选择编号较大者）之间的边分别向上和向下扩展寻找通路，其次是已访问结点；

2）寻找通路过程中，对于遇到的结点若被访问过，则复用它已经走过的路径；

3）在向下寻找通路的过程中，若遇到的分支结点存在多条未访问边连接到其它结点，且所有边连接的结点中有未访问结点，也是优先将未访问结点（存在多个的话，优先选择编号较大者）添加到路径，其次是已访问结点。

按照此算法，对于图1寻找出来的基本路径集应该如下：

1.3 算法实现需要的数据结构

1）BasePathCounts 基本路径数目

2）NodeOuts 结点出度数（一维数组）

3）FCM流程图矩阵（二维数组，0为无边，1为有边，全程不变）

4）LeftNum_Conditions_Node分支结点剩下的未访问边的数目（一维数组）

5）EVF边访问标识（二维数组，2为访问过，1为未访问过）

6）NVF结点访问标识（一维数组，1为访问过，0为未访问过）

7）PrePath_Node结点前置最短复用路径（二维数组）

8）PostPath_Node结点后置最短复用路径（二维数组）

9）L_PrePath_Node结点前置复用路径长度（一维数组）

10）L_PostPath_Node结点后置复用路径长度（一维数组）

11）BasePathSet基本路经集合（二维数组）

程序先根据FCM算出每个节点的NodeOuts，初始化LeftNum_Conditions_Node为NodeOuts，然后由NodeOuts算出BasePathCounts。以BasePathCounts为循环次数，每次循环找出分支未访问完且编号最小的分支节点，将NVF设为1（若不为1），LeftNum_Conditions_Node减1，然后以此节点及未访问的一条边为中心分别向上和向下寻找通路，设置此边的EVF为2。在寻找通路的过程中，对于遇到的未访问边将EVF设为2，遇到的未访问节点将NVF设为1，对于遇到的节点若存在复用路径则复用此路径。一条路径寻找完毕，设置此条路径上节点的复用路径（包括设置PrePath_Node及PostPath_Node，当节点的L_PrePath_Node或L_PostPath_Node较当前路径的可复用路径长才重新设置）。

1.5 算法实现流程图

2 算法实验结果

利用本文介绍的算法，将流程图转换为矩阵存储作为本算法程序的输入，运行程序得到的基本路径集如图4所示。

程序运行的结果与预期一致，验证了算法的正确性。

3 结束语

路径自动生成算法很多，在生成基本路径集的基础上能够帮助测试者在单元及回归测试中减少测试用例的设计时间，才能极大地提高测试效率。实际经验表明，此算法具有可操作性。路径前的辅助提示信息，如（1-1）代表此路径覆盖了分支结点1的一条边。这样，测试者在设计测试用例的时候，能够清楚的知道此路径是为覆盖哪个分支而存在，减少了用例设计时间，提高了测试效率。

参考文献：

[1] 聂鹏，耿技，秦志光.软件测试用例自动生成算法综述[J].计算机用研究，2012（2）： 401-405.

[2] 王敏，陈亚光.用于基本路径测试的路径字符串组合算法[J].计算机工程与科学，2013（12）：134-140.

[3] 解圣霞.基于基本路径测试的程序图自动生成的应用研究[J].通化师范学院院报，2009（12）：38-41.

[4]毛澄映，卢炎生.分支测试中测试路径用例的简化生成方法[J].计算机研究与发展，2006（2）：175-178.

[5] 吴取劲，阳小华，鹿江春，等.一种基于图深度优先搜索的基本路径集自动生成优算法[J]. 南华大学学报：自然科学版，2012（12）：87-90.

[6] 韩寒，姜淑娟.路径测试中基本路径集自动生成方法的研究[J].微电子学与计算机，2013（1）：104-109.

[7] 李鹏，彭祥伟，周喜，等.基于状态图的测试路径自动生成[J].计算机工程，2011（1）：25-29.

[8] 杜庆峰，李娜.白盒测试基路径算法[J].计算机工程，2009（1）：100-102，123.

[9] 孙晓东，黄松.用于软件测试的路径测试方法[J].指挥信息系统与技术，2011（8）：79-82.

[10] 张广梅，李晓维，韩丛英.路径测试中基本路径集的自动生成[J].计算机工程，2012（6）：80-83.

[11] 朱少民.软件测试方法和技术[M].北京：清华大学出版社，2005.

[12] Na Zhang， Xiaoan Bao，Zuohua Ding.Unit Testing：Static Analysis and Dynamic Analysis[J].Computer Sciences and Convergence Information Technology，2009.

1 算法介绍

1.1 基本概念

1） 结点的出度。从结点A有N条边出来，A的出度就是N；

2）分支结点。流程图中，出度>=2的结点；

3）独立路径。在程序中至少引进一条新的语句或是一个新的条件的路径。采用控制流图的术语来表示，即路径P至少包含一条在其他路径中从未有过的边；

P=< N0， N1 … Nf >

（N为控制流图中的节点，N0代表程序入口，Nf代表程序出口）

4）程序环路复杂性或是圈复杂度。又称McCabe复杂性度量，从圈复杂度可以导出基本路径中的独立路径数。E为控制流图的边数，N为图的节点数。

计算公式为：V（G） = E-N+2.

5）程序基本路径集。基本路径集中的每条独立路径称为基本路径。这些路径具有如下特点：

①每一条路径都是独立路径；

②程序中所有的边都被访问；

③程序中所有的、不属于该基本路径集的路径都可以由这个基本路径集中的路径经过线性运算得到。

1.2 算法对流程图的编号要求

1）先编开始结点，为0；

2）其次编分支结点（结点出度数>=2），从1往后编；

3）再编执行语句结点；

4）最后编结束结点；

示例流程图如图1。

图1 被测程序流程图

1.3 路径生成算法思路

1）为了体现基本路径对分支结点的覆盖情况，采用搜索分支结点的方式来生成基本路径集。按照分支编号由小到大的方式搜索，对于搜索到的每一个分支结点，查看是否有未曾访问的边连接到其他结点，若有则以此为一条新边添加到路径，然后沿此新边分别向上扩展寻找到开始结点的通路，和向下扩展寻找到结束结点的通路。这样从开始结点到结束结点形成一条完整的通路，此通路上的结点连接起来就为一条基本路径。在寻找路径的时候有如下要求：若搜索到的分支结点存在多条未访问边连接到其它结点，且所有边连接的结点中有未访问结点，则优先以此分支结点和未访问结点（存在多个的话，优先选择编号较大者）之间的边分别向上和向下扩展寻找通路，其次是已访问结点；

2）寻找通路过程中，对于遇到的结点若被访问过，则复用它已经走过的路径；

3）在向下寻找通路的过程中，若遇到的分支结点存在多条未访问边连接到其它结点，且所有边连接的结点中有未访问结点，也是优先将未访问结点（存在多个的话，优先选择编号较大者）添加到路径，其次是已访问结点。

按照此算法，对于图1寻找出来的基本路径集应该如下：

1.3 算法实现需要的数据结构

1）BasePathCounts 基本路径数目

2）NodeOuts 结点出度数（一维数组）

3）FCM流程图矩阵（二维数组，0为无边，1为有边，全程不变）

4）LeftNum_Conditions_Node分支结点剩下的未访问边的数目（一维数组）

5）EVF边访问标识（二维数组，2为访问过，1为未访问过）

6）NVF结点访问标识（一维数组，1为访问过，0为未访问过）

7）PrePath_Node结点前置最短复用路径（二维数组）

8）PostPath_Node结点后置最短复用路径（二维数组）

9）L_PrePath_Node结点前置复用路径长度（一维数组）

10）L_PostPath_Node结点后置复用路径长度（一维数组）

11）BasePathSet基本路经集合（二维数组）

程序先根据FCM算出每个节点的NodeOuts，初始化LeftNum_Conditions_Node为NodeOuts，然后由NodeOuts算出BasePathCounts。以BasePathCounts为循环次数，每次循环找出分支未访问完且编号最小的分支节点，将NVF设为1（若不为1），LeftNum_Conditions_Node减1，然后以此节点及未访问的一条边为中心分别向上和向下寻找通路，设置此边的EVF为2。在寻找通路的过程中，对于遇到的未访问边将EVF设为2，遇到的未访问节点将NVF设为1，对于遇到的节点若存在复用路径则复用此路径。一条路径寻找完毕，设置此条路径上节点的复用路径（包括设置PrePath_Node及PostPath_Node，当节点的L_PrePath_Node或L_PostPath_Node较当前路径的可复用路径长才重新设置）。

1.5 算法实现流程图

2 算法实验结果

利用本文介绍的算法，将流程图转换为矩阵存储作为本算法程序的输入，运行程序得到的基本路径集如图4所示。

程序运行的结果与预期一致，验证了算法的正确性。

3 结束语

路径自动生成算法很多，在生成基本路径集的基础上能够帮助测试者在单元及回归测试中减少测试用例的设计时间，才能极大地提高测试效率。实际经验表明，此算法具有可操作性。路径前的辅助提示信息，如（1-1）代表此路径覆盖了分支结点1的一条边。这样，测试者在设计测试用例的时候，能够清楚的知道此路径是为覆盖哪个分支而存在，减少了用例设计时间，提高了测试效率。

参考文献：

[1] 聂鹏，耿技，秦志光.软件测试用例自动生成算法综述[J].计算机用研究，2012（2）： 401-405.

[2] 王敏，陈亚光.用于基本路径测试的路径字符串组合算法[J].计算机工程与科学，2013（12）：134-140.

[3] 解圣霞.基于基本路径测试的程序图自动生成的应用研究[J].通化师范学院院报，2009（12）：38-41.

[4]毛澄映，卢炎生.分支测试中测试路径用例的简化生成方法[J].计算机研究与发展，2006（2）：175-178.

[5] 吴取劲，阳小华，鹿江春，等.一种基于图深度优先搜索的基本路径集自动生成优算法[J]. 南华大学学报：自然科学版，2012（12）：87-90.

[6] 韩寒，姜淑娟.路径测试中基本路径集自动生成方法的研究[J].微电子学与计算机，2013（1）：104-109.

[7] 李鹏，彭祥伟，周喜，等.基于状态图的测试路径自动生成[J].计算机工程，2011（1）：25-29.

[8] 杜庆峰，李娜.白盒测试基路径算法[J].计算机工程，2009（1）：100-102，123.

[9] 孙晓东，黄松.用于软件测试的路径测试方法[J].指挥信息系统与技术，2011（8）：79-82.

[10] 张广梅，李晓维，韩丛英.路径测试中基本路径集的自动生成[J].计算机工程，2012（6）：80-83.

[11] 朱少民.软件测试方法和技术[M].北京：清华大学出版社，2005.

[12] Na Zhang， Xiaoan Bao，Zuohua Ding.Unit Testing：Static Analysis and Dynamic Analysis[J].Computer Sciences and Convergence Information Technology，2009.

1 算法介绍

1.1 基本概念

1） 结点的出度。从结点A有N条边出来，A的出度就是N；

2）分支结点。流程图中，出度>=2的结点；

3）独立路径。在程序中至少引进一条新的语句或是一个新的条件的路径。采用控制流图的术语来表示，即路径P至少包含一条在其他路径中从未有过的边；

P=< N0， N1 … Nf >

（N为控制流图中的节点，N0代表程序入口，Nf代表程序出口）

4）程序环路复杂性或是圈复杂度。又称McCabe复杂性度量，从圈复杂度可以导出基本路径中的独立路径数。E为控制流图的边数，N为图的节点数。

计算公式为：V（G） = E-N+2.

5）程序基本路径集。基本路径集中的每条独立路径称为基本路径。这些路径具有如下特点：

①每一条路径都是独立路径；

②程序中所有的边都被访问；

③程序中所有的、不属于该基本路径集的路径都可以由这个基本路径集中的路径经过线性运算得到。

1.2 算法对流程图的编号要求

1）先编开始结点，为0；

2）其次编分支结点（结点出度数>=2），从1往后编；

3）再编执行语句结点；

4）最后编结束结点；

示例流程图如图1。

图1 被测程序流程图

1.3 路径生成算法思路

1）为了体现基本路径对分支结点的覆盖情况，采用搜索分支结点的方式来生成基本路径集。按照分支编号由小到大的方式搜索，对于搜索到的每一个分支结点，查看是否有未曾访问的边连接到其他结点，若有则以此为一条新边添加到路径，然后沿此新边分别向上扩展寻找到开始结点的通路，和向下扩展寻找到结束结点的通路。这样从开始结点到结束结点形成一条完整的通路，此通路上的结点连接起来就为一条基本路径。在寻找路径的时候有如下要求：若搜索到的分支结点存在多条未访问边连接到其它结点，且所有边连接的结点中有未访问结点，则优先以此分支结点和未访问结点（存在多个的话，优先选择编号较大者）之间的边分别向上和向下扩展寻找通路，其次是已访问结点；

2）寻找通路过程中，对于遇到的结点若被访问过，则复用它已经走过的路径；

3）在向下寻找通路的过程中，若遇到的分支结点存在多条未访问边连接到其它结点，且所有边连接的结点中有未访问结点，也是优先将未访问结点（存在多个的话，优先选择编号较大者）添加到路径，其次是已访问结点。

按照此算法，对于图1寻找出来的基本路径集应该如下：

1.3 算法实现需要的数据结构

1）BasePathCounts 基本路径数目

2）NodeOuts 结点出度数（一维数组）

3）FCM流程图矩阵（二维数组，0为无边，1为有边，全程不变）

4）LeftNum_Conditions_Node分支结点剩下的未访问边的数目（一维数组）

5）EVF边访问标识（二维数组，2为访问过，1为未访问过）

6）NVF结点访问标识（一维数组，1为访问过，0为未访问过）

7）PrePath_Node结点前置最短复用路径（二维数组）

8）PostPath_Node结点后置最短复用路径（二维数组）

9）L_PrePath_Node结点前置复用路径长度（一维数组）

10）L_PostPath_Node结点后置复用路径长度（一维数组）

11）BasePathSet基本路经集合（二维数组）

程序先根据FCM算出每个节点的NodeOuts，初始化LeftNum_Conditions_Node为NodeOuts，然后由NodeOuts算出BasePathCounts。以BasePathCounts为循环次数，每次循环找出分支未访问完且编号最小的分支节点，将NVF设为1（若不为1），LeftNum_Conditions_Node减1，然后以此节点及未访问的一条边为中心分别向上和向下寻找通路，设置此边的EVF为2。在寻找通路的过程中，对于遇到的未访问边将EVF设为2，遇到的未访问节点将NVF设为1，对于遇到的节点若存在复用路径则复用此路径。一条路径寻找完毕，设置此条路径上节点的复用路径（包括设置PrePath_Node及PostPath_Node，当节点的L_PrePath_Node或L_PostPath_Node较当前路径的可复用路径长才重新设置）。

1.5 算法实现流程图

2 算法实验结果

利用本文介绍的算法，将流程图转换为矩阵存储作为本算法程序的输入，运行程序得到的基本路径集如图4所示。

程序运行的结果与预期一致，验证了算法的正确性。

3 结束语

路径自动生成算法很多，在生成基本路径集的基础上能够帮助测试者在单元及回归测试中减少测试用例的设计时间，才能极大地提高测试效率。实际经验表明，此算法具有可操作性。路径前的辅助提示信息，如（1-1）代表此路径覆盖了分支结点1的一条边。这样，测试者在设计测试用例的时候，能够清楚的知道此路径是为覆盖哪个分支而存在，减少了用例设计时间，提高了测试效率。

参考文献：

[1] 聂鹏，耿技，秦志光.软件测试用例自动生成算法综述[J].计算机用研究，2012（2）： 401-405.

[2] 王敏，陈亚光.用于基本路径测试的路径字符串组合算法[J].计算机工程与科学，2013（12）：134-140.

[3] 解圣霞.基于基本路径测试的程序图自动生成的应用研究[J].通化师范学院院报，2009（12）：38-41.

[4]毛澄映，卢炎生.分支测试中测试路径用例的简化生成方法[J].计算机研究与发展，2006（2）：175-178.

[5] 吴取劲，阳小华，鹿江春，等.一种基于图深度优先搜索的基本路径集自动生成优算法[J]. 南华大学学报：自然科学版，2012（12）：87-90.

[6] 韩寒，姜淑娟.路径测试中基本路径集自动生成方法的研究[J].微电子学与计算机，2013（1）：104-109.

[7] 李鹏，彭祥伟，周喜，等.基于状态图的测试路径自动生成[J].计算机工程，2011（1）：25-29.

[8] 杜庆峰，李娜.白盒测试基路径算法[J].计算机工程，2009（1）：100-102，123.

[9] 孙晓东，黄松.用于软件测试的路径测试方法[J].指挥信息系统与技术，2011（8）：79-82.

[10] 张广梅，李晓维，韩丛英.路径测试中基本路径集的自动生成[J].计算机工程，2012（6）：80-83.

[11] 朱少民.软件测试方法和技术[M].北京：清华大学出版社，2005.

[12] Na Zhang， Xiaoan Bao，Zuohua Ding.Unit Testing：Static Analysis and Dynamic Analysis[J].Computer Sciences and Convergence Information Technology，2009.