一种面向路径覆盖的测试用例进化生成方法

范书平 刘志宇 杨禹军 李明 马宝英 高晨光 朱旭东 王雪艳 李莹 李力力 樊俊杰

摘 要：提出一种测试用例生成方法.针对穿越程序各节点间测试用例数目的不等性，引入测试用例穿越程序后流量均衡性的概念，给出节点间流量均衡因子的定义及计算过程，并根据个体加入前后流量均衡性，设置遗传算法的适应值函数，以快速进化生成覆盖目标路径的测试用例.

关键词：路径覆盖;测试用例生成;遗传算法

[中图分类号]TP301   [文献标志码]A

Abstract：Aiming at the unequal number of test cases that traversing the nodes of program， the concept of flow balance is introduced， and the definition and calculation process of flow equilibrium factor between nodes are given. Finally， according to the flow balance before and after individual joining， the fitness function of Genetic Algorithms is set up. So the test cases covering the target path can be generated by rapid evolution.

Key words：path coverage;test case generation;genetic algorithms

测试是软件开发生命周期中关键而又昂贵的组成部分，软件测试的目标是通过一个潜在的测试数据集尽可能多地揭露缺陷.自动化软件测试可以有效减少测试代价并获得可信的结果[1]，其基本前提是自动生成测试数据.近些年，许多学者应用进化算法[2]来生成满足指定覆盖准则的测试数据.遗传算法是常用的进化算法之一，该算法具有较强的优化能力，当使用遗传算法生成满足特定覆盖标准的测试数据时，首先会执行一些随机产生的测试数据，之后依据适应值函数评价数据的优劣，在搜索机制的作用下，更加接近目标的测试数据将被不断生成，直到满足需求为止.[3-5]

本文提出一种面向路径覆盖的测试用例进化生成方法，通过设置适应值函数，应用遗传算法进化生成测试数据，目的是实现测试的充分性，快速达到路径覆盖率，提高软件测试的效率.研究主要包括两方面：负载均衡以及基于流量均衡的测试用例生成方法.

1 负载均衡和测试用例进化生成方法

负载均衡作为一种策略，能够让多台服务器或多条链路共同承担繁重的计算或大吞吐量工作，从而以较低成本消除网络瓶颈，提高网络的灵活性和可靠性.针对网络通信不畅的问题，负载均衡技术已广泛应用于计算机网络中.[6-8]针对无线传感器网络的负载均衡问题，宋宁博[9]等人在HEED的基础上，通过改进簇问路由协议提出了一种网络负载均衡路由算法.解文斌[10]等人提出一种基于等概率路由模型的传感器网络负载均衡方法.张健[11]等人提出一种基于多目标优化函数的无线传感器网络负载均衡路由协议，协议中将节点可用能量、节点之间的物理距离以及路由跳数等参数引入到路由选择函数中.负载均衡应用在测试用例生成中还没有比较成熟的研究成果.

应用遗传算法生成测试数据方面已有很多成果.张岩[12]提出的测试数据生成方法中，引入了精英学习的概念，加快了遗传算法的求解速度，提高了目标测试数据的生成效率.Gong[13]等人提出的测试数据生成方法中，适应值函数仅考虑个体穿越路径与目标路径从前至后连续相同节点的个数.谢晓园[14]等人提出用相同节点个数表示测试数据穿越路径与目标路径的相似程度，并给出三种相似度的计算方法，这两种方法在本质上给出了表示层接近度的新方法.应用遗传算法进化种群测试用例生成方法的最终目标是生成覆盖目标路径的用例，当找到穿越全部目标路径的测试数据或者达到条件时就终止了遗传算法.实际在测试用例生成时，除了考虑目标路径的覆盖情况，还要考虑所生成测试用例的有效性与测试代价.鉴于此，本文提出在测试用例生成时，考虑流量均衡性，以快速生成覆盖目标路径的测试用例.

2 程序的流量均衡性2.1 控制流图

控制流图是一个有向图，见图1.图1（a）是一个源程序，图1（b）是图1（a）中源程序所对应的控制流图.

2.2 流量均衡的相关定义

定义1 在控制流图中，节点nj称为节点ni的直接后继节点，当且仅当：nj是ni的直接后继模块，nj控制依赖于ni，记为njni .如图1中的节点n2和n3是节点n1的直接后继节点.

定义2 分叉节点.记NUM（i）为节点ni的直接后继节点数目，若NUM（i）>1，则称节点ni为分叉节点.如图1中的节点n1和n5，均为分叉节点.

定义3 节点ni的流量用Tij表示，指种群中个体运行程序后穿越节点ni上的第j个后继节点的测试用例数目.

定义4 流量均衡因子.根据图1所示的程序及控制流图不难看出，对于复杂的计算机程序，容易穿越的节点将有大量的测试用例通过，而难覆盖的节点有很少甚至根本没有测试用例通过，这会导致前一种情况会有大量冗余的测试用例产生.因此，研究节点间流量均衡性，使得生成的测试用例向穿越难以覆盖的节点进化.

（1）节点间流量均衡因子及其计算方法

4 结语

本文提出一种面向路径覆盖的测试用例进化生成方法，方法中考虑了穿越节点间的测试用例均衡性，并定义了流量均衡因子，给出计算过程，通过设置遗传算法的适应值函数，优先保留改善流量均衡性的个体，以更快地生成覆盖目标路径的测试數据.

参考文献

[1]Mansour N，Salame M.Data generation for path testing[J].Softw.Qual.Control，2004，12 （2）：121-136.

[2]张功杰，谢春丽.面向测试用例生成的集合进化算法实现[J].牡丹江师范学院学报：自然科学版，2017（2）：1-5.

[3]周明，孙树栋.遗传算法原理及应用[M].北京：國防工业出版社，2002.1-20.

[4]Sofokleous A A，Andreou A S.Automatic，evolutionary test data generation for dynamic software testing[J].Systems and Software，2008，81（11）：1883-1898.

[5]Kristof Bohmer，Stefanie Rinderle-Ma.A Genetic Algorithm for Automatic Business Process Test Case Selection[J].OTM conferences，2015，166-184.

[6]刘彩霞.集群网络负载均衡技术分析及实现[J].内蒙古大学学报：自然科学版，2005，36（5）：555-559.

[7]秦光.多路径路由网络负载均衡算法研究[J].计算机仿真，2011，28（11）：118-121.

[8]赵东，韩晓艳，赵宏伟，等.基于分类优化的物联网节点负载均衡策略[J].吉林大学学报：工学版，45（3），2015：926-931.

[9]宋宁博，范敏，王玲.基于HEED的无线传感器网络负载均衡路由算法[J].计算机工程与应用.2015，51（11），83-87.

[10]解文斌，鲜明，陈永光.基于等概率路由模型的传感器网络负载均衡研究[J].电子与信息学报：32（5），2010：1205-1211.

[11]张健.基于多目标优化函数的无线传感器网络负载均衡路由协议[J].安庆师范学院学报：自然科学版，2015，21（4）：33-36.

[12]张岩.基于精英学习的多路径覆盖测试数据进化生成[J].牡丹江师范学院学报：自然科学版，2012（4），20-22.

[13]Gong D W，Zhang W Q，Zhang Y. Evolutionary generation of test data for multiple paths coverage[J].Chinese Journal of Electronics，2011，19（2）：233-237.

[14] 谢晓园，徐宝文，史亮，等.面向路径覆盖的演化测试用例生成技术[J].软件学报，2009，20 （12），3117-3136.