基于遗传算法与XML的测试用例自动生成执行系统研究与实现

刘慰+应新洋

摘 要： 自动化软件测试技术因为其效率高，成本低的优点，成为近年来软件测试技术的重要研究方向和发展趋势。文章提出并实现了一个测试用例自动生成与执行系统，能够利用以遗传算法为核心的测试数据生成方法，自动生成测试数据及XML测试用例文件，自动执行测试用例并以XML的格式记录测试结果。

关键词： 自动化测试； 遗传算法； XML； 自动生成； 自动执行

中图分类号：TP311.5 文献标志码：A 文章编号：1006-8228（2018）02-67-04

Abstract： Because of its high efficiency and low cost， automated software testing technology has become an important research direction and development trend of software testing technology in recent years. This paper presents and implements a test case automatic generation and execution system， by using the genetic algorithm as the core test data generation method， it can automatically generate test data and the XML styled test case file， and automatically executes the test case and records the test results with XML format.

Key words： automatic testing； genetic algorithm； XML； automatic generation； automatic execution

0 引言

軟件测试是保证软件质量的重要手段。传统的人工测试存在着成本高，效率低的缺点，所以自动化测试技术就成为近年来软件测试技术的重要研究方向与发展趋势。自动化测试技术能够有效提高测试的质量与效率，降低测试成本。

目前，自动化测试技术的研究方向主要包括测试数据的自动生成与测试用例自动执行两个方面，但将这两者结合的研究还较少。

本文提出并实现了一个测试用例自动生成与执行系统，能够利用以遗传算法为核心的测试数据生成方法自动生成测试数据，然后生成基于XML（Extensible Markup Language）的测试用例文件，之后自动执行测试用例并以XML的格式记录测试结果。

1 系统总体设计

本系统使用C#语言实现，采用XML描述与存储测试过程中所需的各种数据，如测试配置、测试用例与测试结果。系统分为程序主界面、测试配置处理、测试数据自动生成，测试用例处理，测试用例自动执行这五个模块，系统数据流如图1所示。

2 自动生成测试数据

测试数据自动生成模块是系统的核心模块，能自动搜索并获取一组测试数据，实现对被测函数的路径覆盖测试与边界值测试。使用随机法[1]自动生成测试数据时间成本很低，但效率低下，很难搜索到特殊的测试数据，如三角形分类函数测试中三条边相等，或日期计算函数测试中输入日期为2000年2月29日的情况。近年来，不少研究者将遗传算法引入了测试数据生成领域，并取得了良好的效果，如Jones B.F.[2]的实验表明，针对三角形分类函数，遗传算法生成的测试数据数，要比随机法小1～2个数量级。史亮[3]在博士论文中也对使用遗传算法的测试数据自动生成技术进行了研究。基于遗传算法收敛速度快、易于操作的优点，本系统将其作为测试数据自动生成方法的核心算法，并在此基础上利用边界值法生成一组测试数据作为补充。

2.1 使用遗传算法生成实现路径覆盖的测试数据

遗传算法（Genetic Algorithm）通过借鉴生物界中的自然选择和自然遗传机制，把可能的解编码为一个向量（即染色体），并将若干个染色组成一个种群，模拟种群通过选择、交叉及变异等机制进行进化的过程。该种群在每次迭代中都保留一组适应度高的候选个体，通过若干代进化之后，理想情况下其适应度达到近似最优的状态。

2.1.1 选择操作

选择操作模拟了生物界优胜劣汰的自然选择现象，作用是从种群中选择出一些染色体作为父本进行遗传操作，从而决定种群中哪些染色体的基因将被遗传给子代。选择的方法有轮盘赌法、精英法、混合法等。本系统同时提供了这3种方法，具体算法如下：

⑴ 轮盘赌法：其基本思想就是染色体被选中的概率与其适应度的大小成正比，具体步骤为：①计算每个染色体的适应度；②计算所有染色体适应度之和；③计算每个染色体的选择概率（即当前染色体适应度/所有染色体适应度之和）；④计算所有染色体的累积选择概率（即第一个染色体到当前染色体的选择概率之和）；⑤随机生成一个[0，1]之间的数r，若r在染色体Ci的累积选择概率区间内，则将该染色体加入优胜染色体集合中；⑥重复步骤；⑤M次（M为种群中的染色体个数）。

⑵ 精英法：其基本思想就是选取适应度最高的一批染色体，具体步骤为：①将所有染色体按适应度从高到低排列；②将前N个染色体加入优胜染色体集合中。选取个数N=种群染色体总数×预设的存活率。

⑶ 混合法：结合了轮盘赌法与精英法思想。具体步骤为：①按照精英法，选取N个染色体；②剩余染色体按照轮盘赌法进行选择。

2.1.2 交叉操作

交叉操作模拟了生物界中的基因重组。交叉操作分为单点交叉法与多点交叉法。本系统采用单点交叉法，步骤如下：endprint

⑴ 在种群中随机选择两个染色体，作为新一代染色体的父母；

⑵ 随机生成一个范围在[1，L-1]之间的整数，作为交叉位置，其中L为染色体长度；

⑶ 父染色体与母染色体从交叉位置起，互换基因，得到新的子代染色体；

⑷ 重复步骤⑴M次，M为需要产生的子代染色体个数。

2.1.3 变异操作

变异操作以一定的概率改变染色体中的某些基因，并产生新的染色体，以提供逃脱局部最小值的手段。本系统中，种群中染色体的变异概率可以由用户设置（默认为30%），若该染色体发生变异，则随机抽取某位基因，并将该基因上的等位基因取反，即：从0变为1，或从1变为0。

2.1.4 使用遺传算法生成实现路径覆盖的测试数据的具体步骤

系统利用遗传算法生成实现路径覆盖测试的测试数据的具体步骤如下：

⑴ 对被测函数进行插桩操作，即在保持原有逻辑结构的基础上在被测程序中加入检查语句，使其能够在测试时输出程序执行路径；

⑵ 从用户事先输入的期望路径集中选取本次搜索要覆盖的期望路径；

⑶ 根据预设的种群数量、染色体长度、选择策略、变异率、存活率、随机选择率等参数，随机生成初始种群；

⑷ 选取当前种群中适应度最高的染色体，根据二进制编码[4]方式进行解码，解码公式为，并将解码后的值作为被测函数的输入数据，得到程序执行路径。系统提供了路径匹配法与节点匹配法这两种适应度计算方法，由用户根据被测函数具体情况进行选择。其中路径匹配法得到的适应度为程序执行路径与期望路径的最长子串长度，节点匹配法得到的适应度为程序执行路径与期望路径中相同的节点个数；

⑸ 若程序执行路径与期望路径一致，则将测试数据加入测试数据集，停止进化，回到步骤⑵；否则对种群进行选择、交叉与变异操作，并回到步骤⑷。其中的选择操作可以是轮盘赌法、精英法或是混合法，由用户根据数据搜索效率进行选择。

2.2 利用边界值法生成实现边界值测试的测试数据集

路径覆盖法只能对程序的逻辑结构进行测试，而不能有效地测试程序对于数据边界的处理是否正确，所以本系统使用边界值法生成一组测试数据对其进行补充，其基本思想是选取来自等价类的边界的值，通常选取略小于最小值、最小值、略高于最小值、正常值、略低于最大值、最大值、略大于最大值这7个值。若输入数据取值范围为，则测试数据集（数据类型为整型，则μ=1，否则μ=0.1。若存在多个输入数据，则在一个测试用例中只有一个输入数据能取边界值，其余输入数据都必须取正常值，以便在程序未通过测试时分析导致错误的原因。系统通过遍历所有被测函数参数的上下界，并取得全部边界值与正常值的组合，作为测试数据加入测试数据集中。

3 生成基于XML的测试用例文件

在得到测试数据集后，需要将测试数据转换为计算机能够自动执行的测试用例。传统的测试用例存储方式，如Word或Excel文档等，存在描述不规范，文件较大，不便于计算机自动处理等缺点。芮素娟[5]对基于XML的测试用例复用技术进行了研究，表明XML具有层次化、扩展性好、轻量，能够进行数据有效性验证、便于计算机处理等优点。本系统采用XML来存储测试用例与测试结果。

测试用例处理模块利用.NET Framework中提供的XDocument类，将内存中的测试套件对象（TestSuite）序列化为XML文件，每个测试套件元素中都包含测试套件名称、被测函数名称与一组测试用例子元素（TestCase）；每个测试用例元素又包含一组测试断言（Assertion）子元素；每个测试断言元素中又包含一组输入数据、期望结果、实际结果与测试结果。使用XSD（XML Schema Definition）表示的测试用例文件结构如图2所示。

4 执行测试用例并记录测试结果

测试用例处理模块生成测试用例文件后，需要用户编辑该文件并在每个测试断言的ExpectedOutput标签之间输入该条测试数据对应的期望结果。在用户指定要执行的测试用例文件后，测试用例自动执行模块会将其反序列化为一个TestSuite对象，然后遍历其中的所有的测试断言，获取测试数据，并调用被测函数得到实际输出结果，并与断言中的期望结果作比较，若一致，则将测试结果记为“Passed”，否则记为“Failed”。所有测试完成后，统计测试用例总数、通过数与未通过数，并记录到测试用例文件中。测试用例文件结构如图3所示。

5 结束语

本系统能够通过遗传算法高效地获取实现路径覆盖的测试数据，尤其是在输入数据取值范围很大的情况下，能够搜索到使用随机法很难搜索到的测试数据，且搜索速度有较大提高。在此基础上，还能通过边界值法生成一组补充测试数据，进一步提高测试的质量。除此之外，系统利用XML描述并存储测试用例与测试结果，提高了程序的扩展性，且便于计算机自动处理。今后系统可以从两个方面改进：①引入控制流分析功能，实现被测函数插桩操作自动化；②采用自适应遗传算法，动态地改变各种参数，进一步提高测试数据查找效率。

参考文献（References）：

[1] Bird D. L.， C. U. Munoz. Automatic Generation of andom Self-Checking Test Cases[J].IBM Systems Journal，1983.22（3）：229-245

[2] Jones B. F.， Eyres D. E.， Sthamer H. H.A Strategy for sing Genetic Algorithms to Automate Branch and Fault-Based Testing[J]. The Computer Journal，1998.41（2）：98-107

[3] 史亮.测试数据自动生成技术研究[D].东南大学博士学位论文，2006.

[4] 吉根林.遗传算法研究综述[J].计算机应用与软件，2004.2：69-73

[5] 芮素娟.基于XML的测试用例复用研究[D].西南大学硕士学位论文，2006.endprint