基于改进遗传算法的测试用例生成研究与仿真

林亚娜

基于改进遗传算法的测试用例生成研究与仿真

林亚娜

（福州理工学院 计算与信息科学学院，福建 福州 350506）

提出一种基于改进遗传算法的测试用例自动生成工具，改进的遗传算法通过路径构建方法构建目标路径矩阵集合以及实际路径矩阵，通过对比目标路径矩阵与实际路径矩阵差异设计适应度函数，通过归一化处理得到适应度值，最后根据适应度值调节遗传算子，得到问题的最优解集合进而得到全部测试数据。工具通过可视化界面操作实现待测程序的自动插桩、自动生成覆盖全部路径的测试用例并代入程序进行测试，最后反馈生成测试结果。改进的算法能够提高算法收敛速度，降低早熟程度，在覆盖率及准确度相同的情况下，工具生成用例可以减少测试数据生成时间，达到节省测试成本、提高测试效率的效果。

遗传算法；自动化测试；适应度函数；遗传算子

软件测试工作是软件质量保证的重要手段[1]。据统计，约80%的软件缺陷是在单元测试阶段发现的[2]。基于路径覆盖的白盒测试方法是单元测试阶段的重要方法之一，通过手工设计测试用例来覆盖程序的全部路径不仅需要花费大量的人力和时间成本，在路径覆盖程度方面也很难达到预期的目标。因此，通过算法自动生成测试用例变得尤为重要，在基于路径覆盖的测试中，生成测试用例可归结为寻找有效路径问题，遗传算法是解决该问题的一个较成熟的方法。标准的遗传算法可能产生早熟现象，可能将局部最优解误认为是全局最优解，难以保证生成测试数据的质量[3]。笔者提出将改进的遗传算法应用于测试用例自动生成，针对白盒测试中的路径覆盖方法，设计自动生成测试用例工具（以下简称工具），改进的遗传算法通过对适应度函数的改进，加快算法的收敛速度，将遗传算子做自适应的改变，降低算法早熟程度，针对待测程序生成覆盖多个目标路径的测试用例，达到一次运行生成覆盖全部目标路径的测试用例的效果。将改进的算法研究转化为实际应用的工具软件，收集实践成果的同时也可以提高单元测试中的路径覆盖测试的工作效率，节省人力、时间等方面的成本。

1 改进的遗传算法

遗传算法（Genetic Algorithm，GA）是一种模拟自然界的进化规律，由Holland[4]在20世纪60年代首次提出，该算法属于进化算法，是一种通过选择、交叉、变异操作生成优化搜索问题解决方法的算法。算法优势在于能够并行搜索且效率较高[5]。

测试数据的自动生成可以看作遗传算法通过不断进化生成符合目标路径的测试数据的过程[6]。遗传算法中最关键的步骤是算法适应度函数的设计，在标准遗传算法中，遗传算子即交叉率、变异率均被设置为固定不变的值，针对待测程序的具体情况不同，固定的遗传算子无法将算法特点发挥到最优状态，因此通过设计自适应的遗传算子可以在遗传算法执行过程中动态调整算子的值，加速获取符合目标路径的测试数据，提高生成有效数据的效率。

1.1 路径构建

改进的遗传算法将生成的测试数据代入被测程序，通过待测程序插桩，获得生成数据对应的实际路径，记为一维数组PA[]，数组中的元素个数表示该条路径经过的节点个数，数组中的每个元素表示节点个数的递减数，每个元素用正、负代表当前分支的走向，元素为正数，表示该元素对应的分支走了为真的方向，而元素为负数，则表示该元素对应的分支走了为假的方向。例如，某条测试数据代入被测函数后，发现经过的路径有3个节点，前两个节点走真分支，最后一个节点走假分支，则该路径记为PA={3,2,-1}。

分析待测程序，利用程序插桩插入的探针，获得被测程序的全部路径集合，用二维数组P[][]表示，其中，表示全部路径数量，[]则对应各条路径，P[][]表示路径集合中第条路径的第个节点的元素值。

1.2 适应度函数设计

适应度函数在遗传算法中体现了优胜劣汰的进化原则，是遗传算法的关键[7]。改进的算法通过比较实际路径PA与目标路径集合中所有路径的相似程度的平均值作为当前测试数据的适应度。

通过1.1的路径构建，对比两条路径的相似程度可以看作对比两个元素个数相同的一维数组的相似程度，从第一个节点开始一一对比，根据路径构建原则，如果两条路径的第一个分支点就是相反的，即实际路径的第一个节点走真分支，目标路径的第一个节点走假分支，则认为两条路径的不匹配程度比较大，也就是说越靠前的节点出现不匹配的情况越能够影响两条路径的相似程度，造成两条路径相似程度越低。因此，设计适应度函数为两条路径对应位置元素带符号做乘法后，将所有元素做乘法后的结果相加，得到的结果为适应度值，为便于比较，将适应度值与目标路径的各个元素的平方和做除法，将数值进行归结到[-1,1]的闭区间处理，得到适应度值，如下式

Fitness = [(3*(-3))+(2*(-2))+(1*1)]/[32+ (-2)2+ 12]=-12/14 = -0.86

按公式(1)计算出的适应度，最差情况，即所有元素全部不匹配的情况，得到适应度为-1，各个元素全部匹配得到的适应度为1。

1.3 遗传算子自适应设计

遗传算子是算法的核心部分之一，算子的设定影响着遗传算法的搜索能力和效率[8]。在标准的遗传算法中，交叉率、变异率等算子均为固定值，针对待测对象情况，固定的遗传算子值将不符合实际情况，而随着算法的进行，将会出现偏离最优解的情况，自适应的调整遗传算子会随着算法的运行，适当增加种群多样性，避免陷入算法早熟收敛，提高获取最优解的效率[9]，对遗传算子的动态改进将对算法的优化能力起到辅助作用。

设定初始的交叉率、变异率，在算法运行过程中，个体的适应度与种群的平均适应度比较，当个体适应度小于种群平均适应度时，说明个体需要提高变异、交叉概率以提高物种多样性，提高交叉率、变异率；当个体适应度大于种群平均适应度时，则相反，降低交叉率、变异率。

为了便于表示交叉率、变异率升高或降低的程度，首先将个体的适应度值做归一化处理，根据公式(1)，计算个体适应度得到的值在[-1,1]闭区间，利用如下公式(2)将适应度做归一化，将新的适应度值控制在[0,1]的闭区间内。

公式(2)中Fitness'表示归一化后的个体适应度值，Min表示原适应度闭区间的最小值，即-1；Max表示原适应度闭区间的最大值，即1。按公式(2)变换后，如上案例中的新的个体适应度值变为：

Fitness’ = [-0.86-(-1)]/[1-(-1)] = 0.14/2 = 0.07

将归一化处理后的适应度值用于如下公式（3）、（4），得到交叉率Pcross和变异率Pmutation的自适应变化后的值。

2 自动生成测试用例工具设计

基于改进遗传算法的自动生成测试用例工具主要针对Java语言开发的程序进行自动化测试用例的生成，工具的开发前台使用JSP、JavaScript、CSS样式等进行绘制页面，后台环境配置如表1所示。

表1 工具后台环境配置

以改进的遗传算法为核心，测试用例自动生成工具针对用户导入的待测程序，可一次性生成所有目标路径对应的测试用例，并将测试用例返回结果反馈给用户，以评价程序是否存在缺陷。工具实现了基于B/S模式的测试用例自动生成功能，目前主要设计三个功能页面，即准备测试、测试数据生成、测试结果反馈。其中核心功能为测试数据生成。整体开发功能流程如图1所示，工具代码结构如图2所示。

图1 基于改进遗传算法的自动生成测试用例工具功能流程图

图2 自动生成测试用例工具代码结构

整体代码分为四个部分，分别用于存放待测程序、改进遗传算法、Servlet以及JSP页面等。首先，testedPro包中为待测程序以及经路径构建后的程序（带_Modify.java）；其次，ga包中为改进遗传算法；第三，recreate、resultfile包中存放Servlet，用于接收工具页面输入，并针对页面输入参数做相关处理，其中ReCreateServlet.java用于接收测试准备页数据，获取到待测原文件，读取原文件内容并通过1.1中路径构建方法进行路径构建，并生成新的待测文件，存放在testedPro包中，GetResult用于获取测试数据自动生成页面中的设定值，调用改进的遗传算法方法（AllOnesGA.java），最终获取测试数据集合并将其传递给测试结果反馈页面；最后，webapp下存放工具的主要功能界面，分别是测试准备页、测试数据自动生成页以及测试结果反馈页。

2.1 测试准备

在测试数据准备阶段，界面预留了需求编号、设计编号、程序编号三个输入框，以便于将生成测试用例快速地与需求阶段的需求规格说明、设计阶段的设计书以及编码阶段的程序一一对应，利用这三个编号自动生成测试用例的标识，也为工具的后期功能扩展预留接口。模拟准备测试页面如图3(a)所示。

图3 工具页面

需求编号、设计编号、程序编号可通过手工输入，需上传待测程序，仅支持上传一个.java文件，以上四个字段带有星号标记，为必须输入字段；点击下一步，工具检测三个编号是否输入以及待测程序是否上传，检查通过后点击下一步，进入测试数据自动生成页面。

在跳转到下一个页面之前，工具后台程序需完成如下两步：

以待测程序为基础，通过1.1的路径构建原则，生成一个新的插桩后的待测程序，新的程序命名在原程序名后加后缀“_Modify”。

读取待测插桩后程序文件内容，找出程序中的所有方法，并确定每个方法的输入变量类型以及输入顺序，传递给下一个测试数据自动生成页面。

2.2 测试数据自动生成

在测试数据自动生成页面，将上一步上传的被测程序名显示出来，通过分析程序，检测出待测程序中的方法并罗列出来，前面加复选框，用户可以选择需要生成用例的方法。选中某方法后，下面会对应出现初始种群数、初始交叉率、初始变异率的设置界面，用户可以根据方法的复杂程度设置需要的参数，交叉率和变异率会随着遗传算法的执行，根据公式（2）、（3）、（4）进行自适应的调整，界面如图3(b)所示。

点击开始生成用例按钮，出现进度条及进度提示信息，后台程序开始根据页面选中的方法逐个生成测试用例，以选中一个方法为例，按如下步骤说明程序执行过程：

步骤一：利用生成的插桩程序获取测试数据自动生成页面选中方法的目标路径集合。

步骤二：利用改进的遗传算法，即1.2适应度函数的设计以及1.3自适应的交叉率、变异率的设计，生成第t代测试数据（t=1，2，3…）。

将情景教学应用在护理带教服务当中,可以有效的提高护理实习生在专业知识方面的掌握程度、实践操作能力以及应急能力等多方面的能力,在制定计划时可以评估患者的综合素质,并将患者所存在的共性、个性问题进行针对性考虑和分析,将改进措施规划在循环计划当中,并实施计划,借助和实习生共同制定的计划进行护理教学,可以显著提升护理教学的价值与意义,同时借助情景教学可以实现护理教学质量的循环性提升作用,达到一个良性循环,从而实现不断提升护理实习生护理能力的目标[4]-[5]。

步骤三：循环当前种群中的个体即测试数据，代入插装后的被测程序，获得测试数据对应的实际路径，进行当前个体即测试数据适应度的计算，具体流程如图4所示。

流程中的过滤目标路径集合中不可能匹配路径即寻找目标路径集合中所包含元素个数与实际路径元素个数不同的路径。路径中元素个数代表了测试数据在被测程序中经过的分支，如果分支数不同则证明路径不可能匹配，因此计算不可能匹配路径的相似程度是没有意义的。

图4 计算个体适应度流程图

步骤四：当如上图4中的目标路径集合中没有目标路径时，表示所有目标路径均找到测试数据，程序结束，将找到的所有测试数据以及代入程序后获得的结果反馈给下一页面即测试结果反馈。

2.3 测试结果反馈

将改进的遗传算法针对每个方法返回的测试数据以及输出结果逐条列出，用户可以在工具的测试结果反馈页面查看数据生成情况，核对预期结果与实际结果是否一致，判断程序是否存在异常，支持将选中的方法对应的测试用例导出到excel表格中。具体页面如图3(c)所示。

页面中的测试用例编号由图3(a)测试准备页输入的需求编号、设计编号、程序编号、测试用例序号组成，为未来自动生成测试用例工具向需求、设计、编码阶段的拓展预留接口，工具将在生成的测试用例上面提示选中方法目标路径条数以及生成的测试用例个数。

3 仿真实验

为了验证基于改进的遗传算法的自动生成测试用例工具的可用性，以基础程序中判断三角形程序为例展开仿真实验，首先针对待测程序进行人工分析，得到目标路径，然后将待测程序导入工具，利用工具按步骤实施，导出测试用例结果，最后对比人工分析与工具生成的结果，验证工具的可用性。

3.1 仿真实验准备

实验环境配置为2.3 GHz四核Inter（R）i5-6300HQ处理器，8 GB内存，Windows10操作系统，Eclipse版本：2019-09 R (4.13.0)，JVM版本1.8.0_121。

改进的遗传算法默认的种群数量为50，变异率为0.9，交叉率为0.3，这三个参数仅作为用户参考数值，具体数值可以通过工具的测试用例生成页面进行调整修改。

3.2 待测程序分析及工具仿真

分析三角形问题源程序，三角形问题的输入值为3个整型变量，表示输入的三条边，分析三边数值判断三角形类别，能够得出的情况有一般三角形、等腰三角形、等边三角形、直角三角形以及不能构成三角形。

人工分析采用McCabe的基本路径测试方法，在白盒测试中基本路径分析法被认为是严谨而有效的测试方法[10]，基本思想是分析程序控制流图中的结构环路复杂度，导出基本路径集合，并以此为依据设计测试用例。控制流图由节点和边构成，通过节点和边计算程序结构复杂程度，又称为圈复杂度，代表程序中的目标路径数。控制流图中表示边的数量，表示节点个数，表示待测程序，其环路复杂度公式可表示为：

()=-+2，

最后得到所有的目标路径。

首先分析源程序，待测程序如下图5所示。

图5 待测程序判断三角形源代码

其次，根据如上源代码绘制程序流程图，如下图6所示。

图6 判断三角形程序流程图

根据流程图绘制控制流图如下图7所示。控制流图节点的数字表示对应图5中源程序的行数。

图7 被测程序-判断三角形程序控制流图

根据控制流图可得边的个数= 14，节点个数= 11，根据圈复杂度计算公式可得

然后根据控制流图找到5条目标路径。根据目标路径，可人工设计测试用例如下表2所示。

表2 人工设计的测试用例表

3.3 工具仿真

通过工具实现自动生成测试用例并将结果导出到excel中。首先将待测程序Angles.java上传到测试准备页，并填写需求编号、设计编号以及程序编号；后台根据路径构建原则进行程序插装并生成新的待测程序Angles_Modify.java，并获取待测程序中的方法名及输入变量个数、类型等信息，在测试数据自动生成页面，针对所选待测方法，设置初始的遗传因子，遗传算法运行过程中，遗传因子会根据公式(3)、(4)随着反馈结果的情况自适应地调整；在反馈结果页面，显示出全部生成的测试用例，并支持导出所有测试用例。

以三角形问题为例，工具生成的测试用例如表3所示。

表3 工具生成的测试用例

表3中的覆盖路径指根据路径构建原则，对应测试数据经过的构建后的路径，因三角形待测程序中存在4个分支点，见图5程序源代码。根据路径构建原则，构建出5种情况下的路径分别与自动生成的数据对应。

通过工具仿真可得，工具可以针对待测程序自动生成覆盖全部路径的测试数据，与人工设计相比在准确性相同的情况下，提高了设计测试用例的效率。

4 结论

通过改进的遗传算法提出了基于路径覆盖的测试用例自动生成方法并将算法应用于自动化生成用例工具中。相比于基本遗传算法，笔者提出对适应度函数进行改进，加速算法收敛，提高数据生成效率；对遗传算子即交叉率、变异率做自适应改进，使得算法更快速地找到适合的数据；基于改进算法开发了一款测试数据自动生成工具，自动地分析待测程序并根据预设参数生成测试用例，预留测试用例与需求阶段、设计阶段、开发阶段对接的接口，以便后期工具的扩展。

改进的遗传算法生成测试用例的输入值仅支持数字类型，对于具有特殊含义的文本类型没有很好的支持，下一阶段将针对文本类型及其他类型的输入变量进行自动化生成的研究。

[1] Kim J, Kim E S, Yoo J, et al. An Integrated Software Testing Framework for FPGA-Based Controllers in Nuclear Power Plants[J]. Nuclear Engineering & Tech- nology, 2016, 48(2): 470-481.

[2] 钱丽,万家华,陈秀明,等.基本路径测试算法的改进与应用[J].长春理工大学学报(自然科学版),2016,39(1):107- 111.

[3] 孙德刚.基于改进遗传算法的软件测试数据自动生成系统研究[J].现代信息科技,2020,4(1):23-24.

[4] Holland J H. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence[M]. Ann Arbor: University of Michigan Press, 1975: 170-173.

[5] 陈宏,宋艳.基于改进遗传算法的城市交通最佳路径选择[J].唐山师范学院学报,2010,32(5):72-74.

[6] 曹珣,方徽星.基于改进型GA的测试数据自动生成研究[J].信息记录材料,2020,21(8):158-159.

[7] 夏春艳,张岩,万里,等.基于否定选择遗传算法的路径覆盖测试数据生成[J].电子学报,2019,47(12):2630-2638.

[8] 赫彦文,刘紫阳,李建义,等.基于遗传算法的测试用例自动生成方法综述[J].廊坊师范学院学报(自然科学版), 2020,20(4):16-20.

[9] 包晓安,熊子健,张唯,等.一种基于改进遗传算法的路径测试用例生成方法[J].计算机科学,2018,45(8):174-178.

[10] 王敏,马敏,张志.基本路径测试用例设计的改进方法[J].计算机应用与软件,2019,36(10):17-22.

Research and Simulation of Test Cases GenerationBased on Improved Genetic Algorithm

LIN Ya-na

(Computing and Information Science College, Fuzhou Institute of Technology, Fuzhou 350506, China

Path coverage testing is an important method in White-Box Testing.It takes a lot of time to design test cases that cover all paths.To solve this problem, an automatic test case generation tool based on improved genetic algorithm is proposed.The improved genetic algorithm constructs the target path matrix and the actual path matrix by the path construction method. It designs the fitness by comparing the differences between the target path matrix and the actual path matrix, obtains the fitness value through normalization, and finally adjusts the genetics according to the fitness value. This method can get the optimal solution set of the problem and then get all the test data. The improved algorithm can increase the algorithm convergence speed and reduce the premature degree. With the same coverage and accuracy, this tool can do program instrumentation, generate test cases covering all paths, and use the test cases to run the program and feedback test results.These are all operated with a visual interface. It saves test costs and improves test efficiency.

Genetic Algorithm(GA); automated test; fitness; genetic operators

TP311.51

A

1009-9115(2022)03-0072-07

10.3969/j.issn.1009-9115.2022.03.019

福建省教育厅中青年教师教育科研项目（科技类）（JAT191009），福州理工学院校级科研项目（FTKY21057）

2021-04-16

2021-12-03

林亚娜（1985-），女，辽宁沈阳人，硕士，高级工程师，研究方向为软件测试技术、遗传算法。

（责任编辑、校对：田敬军）