基于遗传算法的软件业务流程测试路径的研究

夏良 商伟 王兆星

摘  要： 近些年随着软件行业的迅速兴起，软件产品已经渗透到日常生活中的各个角落。作为软件生命周期中重要阶段的软件测试，对软件行业的发展有着十分重要的意义。对于软件测试来讲，测试质量是核心，测试效率是保证，一个好的测试过程就是要在保证软件质量的基础上尽可能提高软件测试的效率。本文重点针对软件系统级测试，基于遗传算法对选取个体适应因素进行调整，达到保留必须存在的测试路径，减少重复冗余测试路径的目的，进而实现对测试路径的自动选择。

关键词： 计算机软件;业务流程测试;测试路径选取;遗传算法

中图分类号： TP311.5    文献标识码： A    DOI：10.3969/j.issn.1003-6970.2019.04.029

本文著录格式：夏良，商伟，王兆星. 基于遗传算法的软件业务流程测试路径的研究[J]. 软件，2019，40（4）：133139

【Abstract】： Nowadays， as the software industry promptly developing， the software products have penetrated every area in our daily life. Software testing which is a significant period in the software life cycle， has a very important effect on the software industry. From the point of software testing， the testing quality is the core， and the testing efficiency is the guarantee. A good testing process is to improve the testing efficiency as much as possible on the basis of ensuring the testing quality.

This paper focus on the system software testing， adjust the selection of the individual fitness function based on genetic algorithm， to reserve the testing path which is imperative， and to reduce the redundancy of it， and eventually to realize the testing path automatically generation.

【Key words】： Computer software; Business Process Testing; Testing path selection; Genetic algorithm

0  引言

随着信息科学技术的发展，计算机技术及其产物“软件产品”已在各行各业中得到广泛应用，软件产品已成为人们日常工作和生活的必须品，而保证软件质量已成为近年来软件领域的一个重要话题。软件中的一些缺陷将极有可能直接导致软件失效，尤其在一些用户量大或者安全系数高的关键领域（比如军队安防、核电控制、证券金融和银行交易等），甚至可能造成灾难[1]。

软件测试就是保证软件产品质量的有效活动之一。软件测试会选取一些具有代表性的操作或数据，并将其组成测试用例，通过在被测程序上使用这些操作和数据，得到被测程序的实际反馈信息，再使用其与期望结果进行比较，最终得到被测程序是否满足期望的结论。软件测试有很多重要环节，其中测试数据的使用就是其中之一。一个有效的测试数据选择方法可以实现对测试数据的精简，减少大量重复或者无效的测试工作，这样就可以在有限的条件下明确测试目标、扩大覆盖规模，最终达到提高效率、节约成本的目的。研究表明，测试数据的选取直接影响了测试工作的效果，在一定程度上关乎整个软件研发工作的进程[2]。

本文结合笔者实际测试工作，给出了一种个体适应度的计算方法，并依此给出了一种基于遗传算法的测试路径优选算法，该算法可以优化测试路径的选取，减少冗余的测试用例，进而提高了测试效率，同时也对与流程测试路径选取相关的研究提供了参考[3-10]。

1  业务流程测试

1.1  实验材料

业务流程测试是指，针对用户实际的使用场景，将系统中各相关的功能模块或者配置项串联起来，通过连贯的操作驱动系统中的数据进行一系列的变化，比对中间数据结果和最终数据结果来验证被测系统是否满足用户需求的过程。业务流程测试是系统级测试中重要的测试环节，通过业务流程测试，可以有效降低软件系统在交付后出现问题的几率，减少后期维护成本，提高系统运行的稳定性[11-15]。

1.2  使用基本流图表示业务流程路径

在进行业务流程测试时，为了清晰的展现所有可能存在的业务流程路径，通常需要根据实際的使用场景绘制流程图，再将流程图中的每个操作使用唯一的编号进行标识，进而绘制出便于识别每一条流程路径的基本流图。流程图和基本流图的示例如图1所示。

1.3  独立路径的识别

对于一般的业务流程来讲，仅需对每个判断、每个分支以及任意两节点之间的有向线段进行覆盖，即可达到测试的目的。这种覆盖方式就是“独立路径覆盖”，而识别独立路径最简单的方式就是在已覆盖所有有向线段的基础上，增加一条尚未覆盖的新有向线段。假设某软件系统中存在一系列的操作流程，对其进行分析形成的基本流图如图2所示。

这里可以明显看出每天独立路径都是在其他已知路径的基础上，增加了一条未被识别的新有向线段。通过使用对独立路径覆盖的方法，可以较为快速的找出所有需要覆盖的测试路径，在测试时间有限的情况下，尽可能的保证测试到更多的路径。

2  遗传算法

2.1  基本概念

遗传算法的思想来源于达尔文生物进化理论，以“物竞天择”的概念模拟了自然界中生物的进化过程，对搜索空间进行自动优化，对搜索方向进行自动调整。

遗传算法是一种全局搜索算法，重点强调种群中个体的适应度，通过适者生存的概念，自动完成对问题的求解。它仅从适应度这一个方面对种群中的个体进行评估，不受其他条件和因素的制约，这使得其在当今各领域中得到了十分广泛的应用，尤其在信号处理、自动控制选择等专业领域发挥了不小的作用[16-20]。

2.2  遗传算法一般过程

遗传操作在遗传算法中是非常关键的，其目标就是根据个体对环境的适应度而施加一定的影响，从而实现对优良个体的保留和传递，通过这样不断的迭代和优化，最终达到进化的目的。

适应度函数又称评价函数，它表示种群中的某个体对环境的适应能力，通过适应度函数可以直接评价某个体的优劣，以及其是否可以繁衍下一代。因为遗传算法在整个搜索过程中仅使用适应度函数来评价个体的优劣程度，所以对于适应函数的设计就显得非常重要，必须要在对问题进行充分分析和了解的基础上，才能设计出适合的适应度函数。遗传算法一般过程如图3所示[21-25]。

3  基于遗传算法的测试路径选择算法

3.1  使用基本流图表示测试路径

在基本流图中，通过分支直接形成了不同的独立路径，分支越多则最终形成的独立路径就会越多。这里使用P（Path）表示路径，n（node）表示节点，ns表示起始节点，ne表示终节点，L（line）表示相邻两节点之间的有向线段，通过节点的形式可表现为ni-nt。

下面用上文提到过的一个示例图2进行详细说明。为了不改变原图中各节点编号，直接将1作为起始节点s，11作为终结点e，变化后的基本流图如图4所示。

3.2  路径重复度计算

基于遗传算法测试路径选择的技术难点在于确定每条路径的适应度。对于测试路径的选取来讲，个体适应度的高低主要体现在“重复度”上。测试路径的重复度越高，则说明这条路径越接近已经被探索过的路径;反之重复度越低，则说明这是一条新的、未被发现的路径。那么选择一个合理的重复度的计算方法对于本次研究来讲就是一个比较重要的事情了。本文借鉴了前人的研究成果，采用了分段比较的方法，来确定测试路径的重复度。

对于其中一条路径Pt={ns-n1-n2……-nt-ne}，可以从第一个节点开始，依次向下取出长度为定值m的每条子路径，第一条子路径从ns开始直到nm结束，第二条子路径从n1开始直到nm+1结束……这样以此类推，每条子路径都是在前一条的基础上移出第一个节点再引入一个新的后续节点。这样就有了路径集合：

通过上面的方法就可以比较容易找出重复度较低的测试路径。基于遗传算法的测试路径选择中，可以使用对比已有路径和新路径的重复度的方法确定个体的适应度。两条路径上经过的相同节点越多，则说明这两条路径越接近，反之则说明两条路径之间的差别越大。在对个体适应度进行判断时，个体重复度越高，则说明其与已有路径越接近，个体适应度就越低，应该被淘汰;而重复度越低的，适应度就会越高，应该被保留[26-31]。

3.3  子路径权值

在对测试路径进行覆盖时，通常会使用深度优先和广度优先两种方法。一般情况下，分支出现的越早，之后的两条路径差距越大，所以从某个方面来讲，在测试时间有限的情况下，广度优先的方法更优于深度优先的方法，它更容易选出多条差距较大的测试路径。

可以借助为子路径设置权值的思想来实现广度优先，在子路径集中，越靠前的子路径其优先级就应该设定得越高，越靠后的则越低。这里使用前文中重复度计算的例子进行说明。

使用等比权值得到的结果与使用等差权值得到结果差距不大，且都与基本流图的直观感受基本一致，所以这两种方法都可以使用，而且最终的结果差距不大，都可以满足实际使用时的需要。

等差权值的优点在于计算精确，当出现重复的路径时可以保证重复度刚好为1，其缺点在于对不同路径的子路径权值不同，每次进行比较的时候需要先确定权值才能进行比较;而等比权值对于所有路径均是一样的，使用起来比较方便，但如果路径很短时，重复度结果就与1偏离较大。所以对于存在多分支的复杂流程来说，推荐使用等比权值，而简单的流程推荐使用等差权值。

3.4  个体适应度计算

基于遗传算法的测试路径选取算法的核心在于如何确定个体适应度，确定一个合适的计算函数对个体适应度的计算以及搜索算法的效果都有着直接的影响。对于测试路径的覆盖问题来说，测试人员最不希望的进行的工作就是对同一条路径进行反复的测试，但对于比较复杂的流程来讲，通过人工选取的方式很难做到避免的冗余，所以本文中采用了计算测试路径重复度的方法来辅助计算个体适应度。

在对个体重復度的计算方法和计算结果进行分析后，可以很容易的发现，重复度函数是一条值域在[0，1]之间的单调递增的函数，这样在计算个体适应度时，就可以通过最简单的线性函数y=1f（x）来完成个体测试路径适应度的计算。

前文中得出的mP1与mP2的重复度为：0.9（等差数列形式计算），所以mP2的适应度就应该为：10.9=0.1。类似的mP3的适应度为10.5=0.5。很明显0.5>0.1，说明mP3的适应度要高于mP2的适应度，在选取时应该保留mP3淘汰mP2。将重复度计算函数带入y=1f（x）中得出个体测试路径的适应度公式。

子路徑权值成等差数列时，个体测试路径的适应度

其中nPi是两条路径中各子路径的重复程度，m为子路径数量（如果相比较的两条路径的子路径条数不一样，则取较短的一条的子路径个数），i是自然数[1， n]。

子路径权值成等比数列时，个体测试路径的适应度

其中nPi是两条路径中各子路径的重复程度，m为子路径数量（如果相比较的两条路径的子路径条数不一样，则取较短的一条的子路径个数），i是自然数[1， n]。

从公式上看，当子路径权值成等比数列时，公式更为简单，对于比较复杂的测试路径选取更加合适，这也再一次印证了上文中所说的对于存在多分支的复杂流程来说，推荐使用等比权值，而简单的流程推荐使用等差权值。因为两种方法计算出的适应度结果差距不大。

3.5  基于遗传算法的测试路径选择

在选择一条新的测试路径时，需要分别对备选新路径与每条已有路径的适应度进行计算，并Min（SPi）的方式得出每条备选新路径对已有多条路径的多路径适应度。

3.6  基于遗传算法的测试路径选取步骤

不管是通过人工方式还是基于某种算法测试路径进行选取时，都必须认真分析现有业务需求和逻辑操作流程。在正确绘制业务流程图、基本流图之后才可以进行测试路径的选取。基于遗传算法的测试路径选取步骤如下：

（1）首先要找到基本流图中包含的所有的有向线段集合LS。

（2）再要确定第一条分支路径，将该路径直接加入测试路径解集中，并将该路径中包含的所有向线段在有向线段集合LS中删除。确定该路径的方法很简单，仅需要识别出基本流图中一条最短的路径即可。如果发现存在多条最短路径，则将其全部纳入解集中。

（3）选取其他新的测试路径并进行筛选，如果路径中未包含当前有向线段集合LS中的元素时，则直接将其删除;如果路径中包含了有向线段集合LS中的元素时，则保留这些测试路径并使用这些测试路径与已有路径解集中的测试路径逐一进行重复度比较，得出单路径的多个适应度值，并使用最值的方式得到每条新测试路径的适应度。

（4）从所有适应度中选取适应度最高的一条测试路径作为本次选择的最优解并纳入到解集中，同时删除LS中对应的元素。如果出现适应度相同的多条路径，则取路径长度较短的一条，如果路径长度也相同则取第一条。

（5）重复执行3-4两个步骤，直到LS中没有元素为止，此时所有的测试路径已经全部被覆盖，这样就在测试路径的解集中得到了全部的测试路径。

4  结论

如今的测试技术和测试方法较之前相比已经有了很大的进步，单纯的功能测试已经远远不能满足当今软件测试行业的发展需要，越来越多的时间和资源将被用于系统级的测试中。而且人们对于测试技术的追求也不断提高，降低测试设计的复杂度已经成为了目前迫切需要解决的问题。目前对于路径测试方面的测试技术和研究成果还比较有限，本文在现有研究成果的基础上进行了深入的学习和研究，给出了一种新的更加适合实际测试工作需要的基于遗传算法的软件业务流程测试用例选取算法。对于流程测试路径选取提供了参考，对于自动化测试在系统业务流程测试用的应用起到了指导作用。

参考文献

[1] 颜乐鸣. 基于工作流的软件测试过程模型研究[J]. 软件， 2018， 39（5）： 160-165

[2] 翁秀木. 一个通用的软件质量评估指标体系[J]. 软件， 2015， 36（3）： 59-63

[3] 杨勋姮， 段明璐. 软件缺陷分析技术的研究[J]. 软件， 2018， 39（2）： 93-101

[4] 叶常春， 尹良泽. 面向小规模程序的轻型测试方法[J].软件， 2015， 36（10）： 90-93

[5] 杨子健， 赵逢禹. 基于数据流约简的测试用例生成策略研究[J]. 软件， 2018， 39（4）： 191-195

[6] Huang C Y， Software reliability modeling and cost estimation incorporating testing-effort and efficiency[J]. Software Reliability Engineering， 1999， 22（4）： 62-72

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

[8] Nirmal Kumar Gupta， Dr.Mukesh Kumar Rohil. Using Genetic Algorithm for Unit Testing of Object Oriented Software[C] ICETET 08， NewYorK， 2008： 308-313

[9] Glen.Myers著， 王峰， 陈杰译. 软件测试的艺术[M]. 北京： 机械工业出版社， 2006.

[10] Susan Khor， Peter Grogono. Using a Genetic Algorithm and Formal Concept Analysis to Generate Branch Coverage Test Data Automactically[J]. Proceeding of the 19th IEEE international conference on Automated software engineering： 346-349.

[11] Dr. Velur Rajappa， Arun Biradar， Satanik Panda. Efficient Software Test Case Generation Using Genetic Algorithms Based Graph Theory[J]. First International Conference on Emerging Trends in Engineering and Technology， ICETET 08， 2008： 298-303.

[12] 董敏， 毕盛， 齐德昱. 基于正则表达式的测试数据自动生成技术[J]. 计算机工程， 2009， 35（16）： 29-31.

[13] 付博. 基于模拟退火遗传算法的软件测试数据自动生成. 计算机工程与应用. 2005， 12： 82-84.

[14] 王溪波， 马春， 杜晓舟. 面向路径的测定数据自动生成工具设计与实现[J]. 沈阳航空工业学院学报， 2009， 26（3）： 54-59.

[15] 夏芸， 刘峰. 基于免疫遗传算法的路径测试数据生成的研究[J]. 计算机应用， 2008， 28（3）： 723-725.

[16] 周泽岩， 张喜. 基于改进遗传算法的TSP问题求解的研究. 物流技术， 2012（17）： 220-223.

[17] 张海藩. 软件工程导论[M]. 第三版. 北京： 清华大学出版社， 2000.139-143.

[18] 巩敦卫， 张岩. 一种新的多路径覆盖测试数据进化生成方法[J]. 电子学报， 2010（6）： 1300-1301.

[19] 张岩， 巩敦卫. 基于搜索空间自动缩减的路径覆盖测试数据进化生成[J]. 电子学报， 2012， 40（5）： 1011-1016.

[20] 魏锐， 王海荣. 软件测试数据自动生成方法研究. 电子设计工程， 2013（21）： 5-7.

[21] 曹洋， 胡春华， 陈少波， 李路明. 一种路径测试数据自动生成方法. 计算机工程， 2011（9）： 25-28.

[22] 崔丽婷， 雷斌. 改进的遗传算法及其在测试数据自动生成中的应用. 信息技术与信息化， 2013（4）： 110-115.

[23] 于远诚， 潘洪军， 李春秋. 遗传算法在软件测试中的应用. 浙江海洋学院学报， 2013（2）： 149-154.

[24] 史娇娇， 姜淑娟. 基于遗传算法的动态可变参数的测试数据自动生成工具. 计算机科学， 2012（5）： 124-127.

[25] 夏輝， 宋昕， 王理. 基于Z路径覆盖的测试用例自动生成技术研究[J]. 现代电子技术， 2006（6）： 92-94.

[26] Willem Visser， Corina S. Pasareanu， Sarfraz Khurshid. Test Input Generation with Java Path Finder. ISSTA， 2004： 97-107.

[27] J.Wegener， A.Baresel， H.Sthamer. Evolutionary test environment for automatic structural testing[J]. Information and Software Technology， 2001， 43（4）： 841-854.

[28] 熊伟清， 魏平. 二进制蚁群进化算法[J]. 自动化学报. 2007， 33（3）： 259-264.

[29] 王柳毅， 熊伟清. 并行二级制蚁群算法的多峰函数优化[J].计算机工程与应用. 2006， 22（3）： 42-45.

[30] Yucheng Kao， Kevin Cheng. An ACO-Based Clustering Algorithm. 5th International Workshop， ANT， 2006， 340- 347.

[31] Michael Eley. Some Experiments with Ant Colony Algorithms for the Exam Timetabling Problem . 5th International Workshop， ANT， 2006， 492-499.