基路径覆盖测试用例自动生成方法研究

宋 想，宋晓秋（中国航天科工集团第二研究院706所，北京100854）

0 引 言

软件的单元测试中控制流测试中诸如语句覆盖、分支覆盖、条件覆盖、判定－条件覆盖、路径覆盖等问题和数据流测试中的全定值覆盖、全引用覆盖等问题都可以归结为面向路径的测试用例生成问题［1］。本文主要研究的是基于程序直接执行的路径覆盖问题。

路径覆盖是一种非常苛刻的覆盖准则，即使一小段代码包含的路径数也可能是非常庞大的。

如下面一段代码：

其程序结构图如图1所示。

图1 程序结构

这段程序可能的路径数为220。要做到百分之百路径覆盖，测试人员的工作量是非常巨大的。测试人员往往只能根据一定的准则对全路径集合的某个有限子集进行测试。

在上世纪八十年代，Thomas McCabe提出了基路径的概念，他认为可以将程序中所有可达的路径集合看成一个向量空间，对应向量空间中基的概念，存在着一组基路径，对基路径的线性组合可以覆盖整个路径集合，因此McCabe认为找出路径空间中的一组基路径进行测试，如果这组基路径没有问题，则可以期待能够用这组基路径表示的一切路径组合都没有问题［2］。

目前，基路径覆盖测试用例的生成都是先根据程序得到流程图，然后求出程序的圈复杂度，再根据流程图找出一组基路径，最后分别求出每条基路径对应的测试用例。但由于机械地将源代码表达为有向图和程序路径，掩盖了代码中的逻辑信息，通过程序图得到的基路径在程序实际运行中由于存在相互矛盾的语义依赖关系有些是不可达的，也就无法得到相应的测试用例。为此，本文通过执行一个用例得到一个路径向量，执行若干用例得到一个路径向量矩阵，利用进化的思想不断逼近程序真实的逻辑圈复杂度，最终求得满足基路径覆盖百分之百的测试用例。

1 圈复杂度

McCabe在1976年提出了圈复杂度的概念，他认为在一个强连通图G中，圈数等于最大的线性无关的环数［3］。在所有的路径集合中，存在若干条基路径，其他的所有路径都可以由这几条路径来线性表示，基路径的条数就是圈复杂度［3］。

圈复杂度目前可以通过如下方法求得［4］：

（1）控制流图：V （G）＝E－N＋2p，p＝1；

（2）强流通图：V （G）＝E－N＋p，p为强流通区域的个数；

（3）V （G）＝R，R表示控制流图将将平面划分的区域的数量；

（4）V （G）＝p＋1，其中p表示判定节点的数量，若判定为复合条件，则应将复合条件分解。每个case语句以及每个if，if else，语句都应算一个判定。

以上圈复杂度的求法都是一种静态的求法，都没有动态运行程序。由于代码前后会存在语义依赖关系，这种静态求法得的圈复杂度会比程序实际逻辑上的圈复杂度大。

2 传统基路径覆盖测试用例生成方法及存在的问题

传统基路径覆盖测试用例的的生成方法一般有以下4个步骤：

（1）根据程序生成程序对应的结构图；

（2）根据程序的结构图求出程序的圈复杂度；

（3）根据结构图求出一组基路径；

（4）针对基路径组中的每条路径求出相应的测试用例。

传统基路径覆盖测试用例的生成方法不仅繁琐，而且机械地将程序转换为结构图，没有实际运行被测程序，完全是一种静态的方法。这种静态方法完全忽视了程序语义之间的相互依赖关系，导致得到的某些独立路径在逻辑上其实是不可达的，也就无法生成对应的测试用例。不可达路径的存在导致测试数据生成阶段大量人力，财力的浪费，增加了软件测试的成本。

针对存在的路径不可达问题，有人对传统算法提出了改进的方法。在得到基路径集后，求每条独立路径之前，对每条独立路径进行可达性检测。针对不可达路径的检测问题解决方法，总体上可以划分为两类：一类是静态分析技术；第二类是动态分析技术［5］。

对于静态分析技术，其本质是检测各条件语句之间的相关性，即通过分析条件语句之间的分支冲突来判断目标路径是否可达，这类技术主要包括路径条件可满足性方法以及探测分支相关性方法［6］。路径条件可满足性的方法由于关联到程序中所有的路径条件信息，缺乏相对性，对于规模较大的软件来说，耗费的代价太大，因此往往很难在实际工程中应用；R.Gupta以及Bodik.R两位学者都提出了探测分支相关性的方法，但他们提出的方法只能针对极少的条件谓词种类，这样使得分支的覆盖率太低，另外探测分支相关语句的方法由于缺乏针对性，使得搜索到的信息很多都是无用的，这导致判断分支相关性的代价增加了［7］。

动态分析技术的基本思想是在一个程序的运行过程中，通过动态测试数据的生成算法来检测路径的可达性［8］。但是，测试数据的产生往往依靠符号执行，因此动态分析技术与符号执行方法几乎需要花费同样昂贵的代价。另外动态方法由于其试探性使得测试用例的生成和探测性执行产生大量的耗费，还有可能排除掉测试域比较窄的可达路径，直接影响到测试的充分性［9］。

下面以常用的三角形程序为例说明传统基路径覆盖测试用例生成的过程以及存在的问题：

以上代码的结构如图2所示。

图2 三角形程序结构

根据V （G）＝E－N＋2p，p＝1求其圈复杂度，将E＝14，N＝11代人得V （G）＝5.

下面根据McCabe的基线方法来确定基路径集合：首先挑出一个包含尽可能多判断节点的路径，不妨选择1－2－4－6－8－9－结束。接下来回溯基线路径，依次翻转每个判断节点，翻转判断节点8得到路径1－2－4－6－8－10－结束，翻转判断节点6，得到路径1－2－4－6－7－结束，翻转判断节点4得到路径集合1－2－4－5－结束，翻转判断节点1得到路径1－3－4－6－8－9－结束。由此得到下列基路径集合：

传统基路径测试用例生成的下一步就是针对基路径组中的每条路径分别生成对应的测试用例。

由于存在相互矛盾的语义依赖关系，3－4－6在程序实际运行过程中是不可达的路径，所以上述基路径集合中1－3－4－6－8－9－结束是不可达的，也就无法生成对应的测试用例。

3 本文提出的基路径覆盖测试用例生成算法

算法基于以下基路径覆盖的充分性判别方法［10］：

设待测程序有n行，根据其程序结构图得出其圈复杂度为V。

（1）执行一个测试用例时，若经过某一行，记为1，未经过某行记为0，执行完一个测试用例后便得到一个n位的0、1向量；

（2）执行完m个测试用例后便得到一个m行n列的向量矩阵。求出矩阵的秩为R；

（3）若R＜V，说明测试不够充分，没有测试到一组完整的基路径；若R＝V，说明基路径覆盖率为百分之百；

（4）当用例不断增加时，得到的秩随用例数变化的曲线应该渐渐趋向平滑。

若直接应用上述充分性判别方法生成测试用例，存在4个问题：

（1）仍需要先生成程序的结构图，然后根据结构图得出圈复杂度；

（2）忽视了程序的语义依赖关系，根据结构图得出的圈复杂度可能比程序实际运行时的圈复杂度要大；

（3）当用例数逐渐增加时，得到的向量矩阵也越来越大，求矩阵的秩计算代价也增加了；

（4）用例的增加带有盲目性，不利于生成测试用例集的效率，而且用例数越多越背离基路径测试基的思想。

为解决以上问题本文基于一种进化的思想，动态运行程序，逐渐接近程序的实际圈复杂度，不断进化找到一个向量矩阵使得圈复杂度具有最大值，该向量矩阵对应的测试用例集合即为满足基路径覆盖测试的用例集合。

以遗传算法为寻优搜索算法来说明：设被测程序的输入为M个，M个数据称为一组，被测程序的圈复杂度为V，V的初始值为2。设T＝V，以T组数据的组合作为种群的一个个体，以该T组数据执行被测程序得到的向量矩阵的秩为R，以值P＝R作为个体的适应度。当找到P＝V的个体后，V＝V＋1，继续进化；当没有找到P＝V的个体时，P＝V－1的个体对应的V－1组数据作为满足基路径覆盖测试的测试用例，程序圈复杂度为V＝V－1。个体结构图如图3所示。

图3 个体结构

当没有找到P＝V的个体时，进化算法并不能绝对的保证程序的圈复杂度达不到V，存在没有找到P＝V的个体，但程序圈复杂度为V的可能性。为了减小这种可能性，并考虑到以下事实：若存在某个判定的分支从没有被走过，那么程序中至少有一条路径没有被走过，当没有找到P＝V的个体，并且存在没有被走过的分支时，进行进化寻找P＝V的个体。因此，需要标记某个分支是否没有被走到过。

是否找到目标圈复杂度、是否存在未经过的分支的各个组合情况的处理对策见表1。

表1 处理对策表

为了得到用例执行后经过的路径向量以及判断是否存在未经过的分支，需要对源程序进行预处理，预处理方式如下：通过插装的方法来判断是否经过了某一行。考虑到每行都插装工作量过大、得到的矩阵向量会过长，在每个分支的第一个语句后进行插装。通过判定节点统计程序中的分支数n，向量以数组C［n］来表示，通过数组B［n］来标记是否经过某个分支，两数组元素初始值都为零。将C［m］＝1，B［m］＝1插装在第m＋1个分支中第一个语句后。执行完一个用例后就可以得到该用例对应的路径向量。执行完所有用例后就知道是否存在未经过的分支。

综上所述，本文提出的基路径覆盖测试用例自动生成算法过程如下：

（1）对源程序进行预处理；

（2）V＝2；

（3）T＝V，以T组数据的组合作为种群的一个个体，以该T组数据执行被测程序得到的向量矩阵的秩为R，以值P＝R作为个体的适应度；

（4）当找到P＝V的个体后，V＝V＋1，继续进化，转到步骤 （6）；当没有找到P＝V的个体时，执行步骤 （5）；

（5）若存在未经过的分支，转到步骤 （6），若不存在未经过的分支，执行步骤 （7）；

（6）对种群进行选择、交叉、变异操作，转到步骤（3）；

（7）V＝ V－1，程序圈复杂度为V－1，以P＝V－1的个体对应的数据作为测试用例，算法结束。

以遗传算法作为寻优搜索算法，则以上过程模型如图4所示。

个体包含数据组数的变化：目标圈复杂度为V时，个体包含的数据组数为T＝V，当目标圈复杂度为V＋1时，个体包含的数据组数变为T＝V＋1。个体组数变化有两个途径：①保留个体原来的V组数据，在步骤 （6）的交叉操作中，被选中进行交叉的两个个体，彼此添加对方的一组数据；②执行完步骤 （6）中的选择、交叉、变异操作后为每个个体再随机生成一组数据。

以常用的三角形程序为例说明本文基路径覆盖测试用例自动生成的动态方法。

图4 算法模型

为了得到用例执行后经过的路径向量以及判断是否存在未经过的分支，需要对源程序进行插装。考虑到每行都插装工作量过大、得到的矩阵向量会过长，在每个分支的第一个语句后进行插装。通过判定节点统计程序中的分支数n，向量以数组C［n］来表示，通过数组B［n］来标记是否经过某个分支，两数组元素初始值都为零。将C［m］＝1，B［m］＝1插装在第m＋1个分支中第一个语句后。执行完一个用例后就可以得到该用例对应的路径向量。执行完所有用例后就知道是否存在未经过的分支。插装后的源程序如下：

通过对参数的分析，确定参数为a，b，c，数据类型为int型。不妨设int型为8位，每个参数用8位的二进制编码表示，则一组数据可以用24位的二进制编码表示。设进化过程中目标圈复杂度大小为V，则一个个体可以用V个24位的二进制编码表示。

图5 三角形问题个体组成

以遗传算法作为寻优搜索算法，种群大小设定为500，最大进化代数为100，以每个个体得到的矩阵向量的秩作为个体的适应度。选择运算中保留适应度最高的个体，并用最优个体替换最差个体，交叉运算中交叉率设为0.8，变异运算中变异率设为0.02。每个个体包含的数据组数增加时通过执行完步骤 （6）中的选择、交叉、变异操作后为每个个体再随机生成一组数据。

算法代码实现后统计运行50次的结果，发现有47运行能得到三角形程序的真实逻辑圈复杂度4，三次运行得到的圈复杂度为3，得到满足基路径覆盖百分之百的测试用例的概率为94%，所需要的进化代数最少为17次，最大为82次，平均为32.6次。试验结果表明本文提出算法能够有效地生成满足基路径覆盖百分之百的测试用例。

4 结束语

传统算法先生成程序的结构图，然后通过结构图静态的分析出程序的圈复杂度，这种的静态的分析忽视了程序的语言间的相互依赖关系，求出的圈复杂度可能比实际的程序圈复杂度大，本文算法，不需要生成程序的结构图，动态运行程序，通过进化的方法逐渐逼近程序的实际圈复杂度；

传统算法需要针对基路径组的每条路径，逐条求出覆盖每条路径的测试用例，本文算法在求出程序的实际圈复杂度的同时，得到了覆盖整个基路径组的测试用例；

传统算法因为忽视了语义间的相互依赖关系，可能存在路径不可达问题，也就无法生成不可达路径的测试用例，本文算法动态运行程序，不存在路径不可达问题。

［1］CHEN Jifeng.Framework of automatic test data generation for software structure ［J］.Computer Engineering，2007，33 （8）：3425－3428（in Chinese）.［陈继锋 .一种结构测试数据自动生成的框架 ［J］.计算机工程，2007，33 （8）：3425－3428.］

［2］LI Yonghua.Research of methods of getting the basic paths dynamically without unreachable paths （in Chinese）.［李勇华.消除不可达路径的基路径自动获取方法研究 ［J］.武汉理工大学学报，2009，23 （3）：23－29.］

［3］XIAO Liqiong.The core of software testing ［M］.Beijing：Electronic Industry Press，2011 （in Chinese）. ［肖利琼.软侧之魂 ［M］.北京：电子工业出版社，2011.］

［4］RONG Zhiwen，LI Jia，CAI Lizhi.Software testing method researching of cyclomatic complexity ［J］.Software Industry and Engineering，2012，6 （1）：28－34 （in Chinese）.［荣志文，李嘉，蔡立志.基于圈复杂度的软件测试方法研究 ［J］.软件产业与工程，2012，6 （1）：28－34.］

［5］JIA Songtao，ZHANG Hongwei.Framework and application of testing data generation based on paths ［J］.Micro Computer Information （Management），2010，26 （2－3）：45－54 （in Chinese）. ［贾松涛，张红卫.面向路径的测试数据生成框架及应用 ［J］.微计算机信息 （管控一体化），2010，26 （2－3）：45－54.］

［6］Kostas Sturgeon.Representation and reasoning with non－binary constraints［D］.The Univ of Strathclyde，2010.

［7］Ngo M N，Tan H B K.Heuristics－based infeasible path detection for dynamic test data generation ［J］.Information and Software Technology，2008，50 （7／8）：641－655.

［8］Brahman P，Marian S，Hussein H，et al.Automated analysis of Reo circuits using symbolic execution ［J］.Electronic Notes in Theoretical Computer Science，2009 （255）：137－158.

［9］LI Junyi.Research on testing case generate automatically ［D］.Changsha：Hunan University，2007 （in Chinese）.［李军义.软件测试用例自动生成技术研究 ［D］.长沙：湖南大学，2007.］

［10］CAO Fengyan.An application research of creating test cases automatically based on basie path test ［D］.Dalian：Dalian Marring Univesity，2007 （in Chinese）. ［曹烽燕.基于基本路径测试的测试用例自动生成应用研究 ［D］.大连：大连海事大学，2007.］