基于遗传算法的UML活动图测试用例优化研究

李浩　陈锋

摘 要： 测试用例的选择在软件测试中十分重要，良好的测试用例可以减少时间和资源的使用，因此提出了一种基于遗传算法的UML活动图自动生成测试用例的算法。通过建立UML活动图模型，将活动图转换为有向图，然后采用深度优先搜索方法获得测试路径，应用遗传算法优化得到测试路径。该算法可以提供优先需要测试的路径，用于自动生成高质量的测试用例，提高测试任务的工作效率。

关键词： UML； 测试用例； 活动图； 深度优先搜索算法； 遗传算法

中图分类号： TN911?34 文献标识码： A 文章编号： 1004?373X（2015）19?0117?04

Abstract： The selection of test cases in software testing is important， and the better test cases can reduce time and resource usage. An algorithm of automatic generation test cases of UML activity diagram based on genetic algorithm is proposed. The activity diagram is converted into digraph by establishing UML activity diagram model. The testing path is acquired by adopting depth first search （DFS） method， and obtained by using genetic algorithm optimization. This algorithm can provide the path needed to be tested first to generate high quality test cases automatically. The work efficiency of the test task can be improved.

Keywords： UML； test case； activity diagram； depth first search method； genetic algorithm

0 引 言

随着信息技术的发展，软件技术在各行业领域中的应用日益广泛。作为软件质量的保证，软件测试在软件开发中的作用逐渐得到重视。国内外相关学者在基于模型的测试技术以及测试用例自动生成上，开展了大量的研究[1?3]。UML（Unified Modeling Language）作为软件建模的标准，激发了研究者极大的热情，UML模型在设计测试用例方面的重要性得到了充分的验证。UML中包含状态图、活动图和序列图等，文献[4?6]给出了基于UML状态图、序列图和协作图生成测试用例的方法。对于描述系统动态行为，UML活动图（Activity Diagram）被认为是最适合描述软件过程的模型[7]。本质上，活动图是一种流程图，该模型是描述系统业务过程的重要工具，不仅能定义活动中对象的角色、属性和状态的变化，也适用于描述满足用例要求所进行的活动以及活动时间的约束关系，强调对象间的控制流程。Rudram研究了如何使用UML活动图生成测试用例的方法[8]，提出了形式化的活动图。M.S.Chen等人提出一种基于UML活动图的随机测试用例生成方法[9]。对于生成的测试路径，适当的优化能够在满足较高测试覆盖率的基础上，减少测试用例的数量，从而进一步降低测试成本，提高测试效率。本文采用DFS算法寻找UML状态图中的测试路径，将遗传算法用于优化测试路径。

1 UML活动图与测试用例

（4）[dependent（CA）]表示存在与CA有依赖关系的所有对象，[dependent（CA）={o（o，a）∈Fo，a∈CA，o∈O}?][{o（a，o）∈Fo，a∈CA，o∈O}]。设[D=（A，O，T，Fc，Fo，C，S，E）]是一个活动图，[a∈A]是图中的一个结构化活动，描述结构化活动[a]的图记为[Da，][D]是活动图[Da]的父图，[Da]是活动图[D]的子图。

其中，TS表示针对活动图[D]的测试场景，每个测试场景由活动图中一系列相关的活动（包括活动的迁移信息、触发事件等）组成；Data表示测试场景TS所需要的测试数据，是指对应于特定测试场景的输入信息（包括各种类型的数据等）。

2 测试路径生成

2.1 UML活动图的建立规则

活动图是对系统的活动动态建模的行为视图，如图1所示。针对测试对象，为了使UML活动图能较好地生成测试用例，在建模时需要遵循以下的可测试性设计规则[11?12]：

（1） 满足结构化条件，一个活动图有惟一的起始节点，分支节点与汇合节点要求配对出现；

（2） 不存在孤立节点，除了起始节点和结束节点之外，每个节点至少有输入边、输出边各一条，使活动图的每个节点都是可达的；

（3） 业务过程中的各个环节通常会涉及到对象状态的变迁，可以采用对象流描述，同一对象可能多次出现，表明该对象处于对象生存周期的不同时间点，对应着对象的不同状态；

（4） 业务过程中的各个活动也会涉及到参数模型的某些参数，如配置参数、功能参数和环境参数等，为了表示活动图中的这些参数，需要给活动节点加注释，记为：参数1：参数2：参数3：…；

（5） 一般情况下，在活动图中的决策节点拥有若干条件分支，为了识别出优先遍历的条件分支，可以在这个条件分支中使用构造符加以区分；

（6） 如果在循环体内存在Fork?join块或者在Fork?join块内存在嵌套的Fork?join块，可以使用结构化活动替换此Fork?join块，然后再构建该结构化活动的活动子图。

2.2 活动图转换

在活动图上，从起始节点到终止节点任意可能的路径，都能表示为待测软件的一个测试场景，由路径上的动作状态和转换组成的活动执行序列[11]。为了获得活动图中所有的测试路径，首先应当将活动图转化为如图2所示的有向图，根据相应的测试覆盖准则，通过对有向图采用深度优先搜索，获取起始点到终节点的所有活动序列，即得到了测试路径。

深度优先搜索算法（Depth First Search）是一种递归算法，对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。每次在访问完当前顶点后，首先访问当前顶点的一个未被访问过的邻接顶点，然后去访问这个邻接点的一个未被访问过的邻接点[13]。图3为深度优先搜索算法流程图，算法内容如下：

（1） 访问初始顶点[v，]标记顶点[v]已访问；

（2） 查找[v]的第一个邻接顶点[w；]

（3） 若[w]存在，继续执行；否则回溯到[v，]继续寻找[v]的另外一个未访问过的邻接点；

（4） 若[w]尚未被访问，则访问顶点[w]并标记顶点[w]为已访问；

（5） 继续查找顶点[w]的下一个邻接顶点[wi，]将[v]取值[wi，]回到步骤（3），直到图中所有的顶点全部访问完成为止。

测试用例包含测试路径和相应的输入数据，每一条测试路径对应一个相应的测试场景。在得到测试路径之后，通过加入输入、输出参数和决策条件等信息，就能得到完整的测试用例。

3 基于遗传算法的UML活动图生成测试用例

遗传算法（Genetic Algorithm）是一类仿生算法[14]，借鉴生物界适者生存，优胜劣汰遗传机制的进化规律演化而来的随机化搜索方法。通过对生物进化行为的描述，将生物学特性用于实际计算问题中，是计算机科学、人工智能和模式识别等领域中用于解决最优化的一种搜索启发式算法。

3.1 遗传算法介绍

遗传算法的基本运算过程如下：

（1） 抽象待解决问题，进行编码；

（2） 初始化种群，设置最大进化代数为[T，]随机生成[n]个个体作为初始群体[P（0）=p1，p2，…，pn；]

（3） 采用适应度函数，计算现有群体[P（t）]中各个个体的适应度；

（4） 根据群体中个体的适应度，将选择算子作用于群体，把优化的个体遗传到下一代或配对交叉产生新的个体遗传到下一代；

（5） 将交叉算子和变异算子作用于群体，得到新一代群体[P（t+1）；]

（6） 若[t=T，]选取进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算若不满足，则返回步骤（3）。

3.2 UML活动图生成测试用例算法

根据上文的论述，将遗传算法用于UML活动图自动生成优化测试路径，算法步骤如下：

（1）生成测试对象的活动图，将其转换为活动有向图。

（2） 对判断或选择节点编码，随机生成一组测试数据，作为初始化种群。

（3） 对于每一个测试数据：

① 使用DFS算法遍历有向图，按顺序使每个节点入栈，得到栈的容量Smax；

② 对于每个节点，节点基于栈的权值[w]表示为[w=Smax-k，][k]为当前节点上方的节点号，并行的节点指定相同的[w；]

③ 对于每个判断或选择节点，它的分支节点权值[w]相同，插入相邻的分支节点并且更新顶点，忽略分支节点和先前插入的判断或选择节点。

（4） 计算每个个体的适应度[F，][F=i=1n（wei+wsi）=][i=1n[Edge（i）+Stack（i）]]，其中Edge（i）表示每个节点的流入边个数与流出边个数之积，表示为[Edge（i）=In（i）*Out（i），]Stack（i）为节点基于栈的权值。

（5） 选择初始化的种群个体数据，分别求出相应的适应度。

（6） 随机生成0～1区间的实数[R，]如果[R<0.8，]执行交叉；[R>0.8，]执行变异。

（7） 对适应度较高的个体根据[R]的值执行交叉、变异操作，得到新的个体。

（8） 将新个体代入下一代种群，随机加入若干个体，维持种群规模，形成新的种群。

（9） 重复上述遗传算法步骤，直至所有路径被覆盖或者设置的种群数达到最大化。

（10） 选择适应度最大的个体，其所对应的即是最佳路径，结束。

3.3 实验分析

如图2所示，选取判断或选择节点4，8和14，进行三位二进制编码，0表示“否”，1表示“是”，对于节点14，0表示“Transfer”，1表示“Withdraw”。例如，000就能表示路径1→2→3→4→6→9→10→13→18。如表1所示，列举了图2中各个节点基于栈的权值，表2所示为各节点权值之和。

4 结 语

本文提出了一种基于遗传算法优化测试路径的自动生成方法。详细地描述了UML活动图模型的属性，UML活动图转化为有向图的规则，采用DFS算法获得测试路径和使用遗传算法优化测试路径的步骤。该方法可以寻找最优化的测试路径，用于优先测试，能在一定程度上提高测试效率。如何设计实现相应的自动化工具，将成为未来的研究方向。

参考文献

[1] OFFUTT A J， XIONG Y， LIU S. Criteria for generating specification?based tests [C]// Proceedings of 1999 the 4th IEEE International Conference on Engineering of Complex Computer Systems. Las Vegas： IEEE， 1999： 119?129.endprint

[2] RIEBISCH M， PHILIPPOW I， GOTZE M. UML?based statistical test case generation [J]. Lecture Notes in Computer Science， 2003， 8（19）： 394?411.

[3] 王林章，李宣东，郑国梁.一个基于UML协作图的集成测试用例生成方法[J].电子学报，2004，32（8）：1290?1296.

[4] FRAIKIN F， LEONHARDT T. SeDiTeC?testing based on sequence diagrams [C]// Proceedings of 2002 the 17th IEEE International Conference on Automated Software Engineering. [S.l.]： IEEE， 2002： 261?266.

[5] OFFUTT A J， ABDURAZIK A. Using UML collaboration diagrams for static checking and test generation [C]// Proceedings of 2000 the 3rd Advancing International Conference. New York： Springer Berlin Heidelberg， 2000： 383?386.

[6] BRIAND L， LABICHE Y. A UML?based approach to system testing [J]. Journal of Software and Systems Modeling， Springer Verlag， 2002， 1： 10?42.

[7] MCLEOD G， HALPIN T， KANGASSALO H， et al. Unified modeling language （UML）： a critical evaluation and suggested future [C]// Proceedings of 2001 the 34th Annual Hawaii International Conference on System Science. Hawaii ： 2001， 3： 112?114.

[8] RUDRAM C. Generating test cases from UML [D]. Sheffield ： University of Sheffield， 2000.

[9] CHEN Mingsong， QIU Xiaokang， LI Xuandong. Automatic test case generation for UML activity diagrams [C]// Proceedings of 2006 International Workshop on Automation of Software Test. Shanghai， China： ACM， 2006： 1?8.

[10] 袁洁松，王林章，李宣东，等.UMLTGF：一个基于灰盒方法从UML活动图生成测试用例的工具[J].计算机研究与发展，2006，43（1）：46?53.

[11] 苏翠翠.一种基于UML活动图生成测试用例的方法[D].南京：南京邮电大学，2011.

[12] 解楠.基于UML活动图模型的测试用例自动生成方法研究[D].西安：西安电子科技大学，2011.

[13] WEISS M A. Data structures and problem solving using Java [M]. Boston： Addison Wesley， 2005.

[14] 王小平，蓸立明.遗传算法理论、应用与软件实现[M].西安：西安交通大学出版社，2002.endprint