摘要
软件测试是保证软件质量和可靠性重要手段，在这方面发挥着其它方法不可替代的作用。然而，软件测试是一个复杂的过程，需要耗费巨大的人力、物力和时间，约占整个软件开发成本的4要。而提高测试用例生成的自动化程度又是提高测试工具乃至整个测试过程自动化程度的关键所在，本文主要针对这一问题进行了研究和设计。
本文在分析软件测试和算法基本概念的基础上，提出软件测试用例的设计是软件测试的难点之一。论文提出了基于算法的测试用例生成的内含是应用算法来求解一组优化的测试用例，其框架包括了测试环境构造、算法及测试运行环境三部分，论文给出了基于算法的的模型。最后以三角形分类程序为例应用算法进行测试用例生成的模拟，结果显示，应用算法进行测试用例生成可行。
关键词：软件测试 测试用例 算法
1
基于遗传算法的测试用例生成方法
ABSTRACT
Software test is the important means that guarantee software quality and reliability， and in this respect，it plays the role that other method cannot replace. However software test is a complex process , it needs to consume huge manpower，material resources and time，which takes the 40%~50% of entire software development cost approximately . Therefore，raising the automation level of software test tool is very important for ensure software development quality and reduction software development cost . And then，the most important is raising the automation level of the test case generation for raising the automation level of test tool and even entire test process，so this paper study and design mainly according to this problem.
Based on the analysis of basic concepts of software testing and genetic algorithm, this article proposes that software test case design is one of the difficulties of software testing. Paper presents the inherent in software test case designing based on genetic algorithm is using genetic algorithm to solve a set of optimization test cases, and the framework includes three parts which are test environment construction, genetic algorithm and the environment for test . Paper presents the model of software test case generation based on genetic algorithm. Finally, we take the triangle categorizer as an example, simulate software test case generation based on genetic algorithm. The results display that software test case generation basing on genetic algorithm is possible.
KEY WORDS: software test , test case , genetic algorithm
2
基于遗传算法的测试用例生成方法
目录
摘要............................................................ 1 ABSTRACT........................................................ 2 目录............................................................ 3 第一章 绪论..................................................... 5
1.1 问题的提出.............................................. 5 1.2 国内外研究现状.......................................... 6 1.3 论文研究内容............................................ 8 第二章 软件测试及算法基本概念.................................. 9
2.1 软件测试基本概念........................................ 9
2.1.1 软件测试的目的.................................... 9 2.1.2 软件测试的原则.................................... 9 2.2 软件测试的难点......................................... 10 2.3 算法................................................... 11
2.3.1 算法的思想及流程................................. 11 2.3.2 算法的特点....................................... 13 2.4本章小结 ............................................... 14 第三章 基于算法的测试用例生成.................................. 15
3.1基于算法的测试用例生成基本内涵 ......................... 15
3.1.1 软件测试用例的基本内涵........................... 15 3.1.2 基于算法的测试用例生成的基本内涵................. 16 3.2 基于算法的测试用例生成框架............................. 16 3.3 基于算法的测试用例生成算法实现......................... 18
3.3.1 编码策略......................................... 18 3.3.2 适应度函数及程序插桩............................. 19 3.3.3 策略............................................. 20 3.3.4 参数控制......................................... 21 3.4 本章小结............................................... 22
3
基于遗传算法的测试用例生成方法
第四章 实验及结果分析.......................................... 23
4.1 待测程序分析........................................... 23
4.1.1 待测程序引入..................................... 23 4.1.2 程序流程分析..................................... 23 4.1.3 路径分析......................................... 24 4.2 程序插桩............................................... 24 4.3 参数设定及程序实现..................................... 25
4.3.1 参数设定......................................... 25 4.3.2 部分程序实现..................................... 26 4.4 结果分析............................................... 28 4.5 本章小结............................................... 30 第五章 总结与展望.............................................. 31 致谢语......................................................... 32 参考文献....................................................... 33
4
基于遗传算法的测试用例生成方法
第一章 绪论
1.1 问题的提出
在信息化普及的今天，计算机在人们的生活和工作中占据着重要地位，使人们的工作效率提高，也使生活更丰富多彩。而作为计算机的重要组成部分，软件的重要性不言而喻。随着计算机技术的日益发展，计算机软件的规模越来越庞大，复杂性越来越高，这就为软件质量的保证带来了困难。因为软件的开发过程大部分是由人的智力活动构成，不可能完美无缺。而软件缺陷如果不能及时发现，带来的损失可能是巨大的，有的甚至会危及人的生命。在历史上臭名昭著的软件缺陷案例有[1]：1999年12月3日，美国航天局的火星基地登陆飞船在试图登陆火星表面时失踪，原因仅仅是一个数据位的意外更改；美国爱国者导弹防御系统曾在几次对抗导弹战役中失利，其中一次竟然误使28名美国士兵丧生，原因是一个很小的系统时钟错误导致系统累计拖延了100多个小时使跟踪系统失去准确度；还有就是大名鼎鼎的“千年虫”问题，起因是在20世纪70年代，为了节省硬盘空间，美国某位程序员在编写工资系统时将4位数日期（如1975）改成了2位数日期（如75），该缺陷一直拖到1995年都没有修复，最终给全球带来了高达数亿美元的损失等等。
作为提高软件质量的重要手段，软件测试越来越受到重视。在美国的微软公司，测试人员和开发人员的比例达到了2：1[2]。软件测试伴随着整个开发过程，是一个非常复杂的过程，其消耗的人力和资金一般占整个项目的一半左右。而在某些特别重要的软件开发过程中，为保证软件的质量，测试的费用甚至是其它各阶段之和的3到5倍。测试过程中，测试人员通常需要分析、设计和执行大量的测试用例，从而耗费了大量资源，因此找出合理的测试用例生成方法可以有效缩短测试时间，减少损耗，一般可以有效降低整个项目的4%费用[4]。
然而，目前生成测试用例的方法主要是向前核查法和逆向回溯法，测试人员根据自己的项目经验手工为指定的程序路径生成测试数据[5]。向前核查法是指沿预期的路径向前检查，确定到每一个判断点时变量所能提供的最宽数值区间，然
5
[3]
基于遗传算法的测试用例生成方法
后继续前行，从而将多个变量的可能取值范围逐渐缩小，到达程序出口后，就能找到覆盖这条路径所需的输入数据。逆向回溯法正好相反，是指从期望执行的程序位置出发，逆向回溯，在每个判断点处逐渐调整各变量取值，直到退到程序入口，即获得所需的输入数据。向前核查法和逆向回溯法的局限性是，对某些条件要求苛刻的路径使用时非常困难，同时由于大多数程序中包含的路径数非常多，如果按每条路径手工测试，显然带来的工作量是非常巨大的。
由于测试的工作量大、测试过程的重复性高等特点，自动化测试正逐渐得到广泛的应用。很多测试工具的使用大大提高了测试人员的工作效率，有效减少了项目开支。然而这些工具主要为测试的执行、管理和度量工具，在测试用例自动生成方面还不完善。而在软件测试过程中，动态测试作为测试的重要环节占了很大比例，动态测试的关键正是测试用例的生成问题。因此，寻找一种有效的测试用例生成方法是提高测试自动化的重中之重。
1.2 国内外研究现状
自上世纪60年代起，国内外的学者专家对测试用例的自动生成提出了很多方法，应用较为广泛的有随机法、静态法、动态法以及试探法
[5] [6] [7] [8] [9] [10] [11] [12]
。
D.Bird[13]等提出了采用随机法生成测试用例，其思想是不受限制地随机产生大量的测试用例。该方法产生测试用例的成本很低，在某些抽样测试中效果较好，但是该方法的针对性较弱，在输入空间为无穷大时产生的测试用例集非常庞大，测试效率低，现在的很多工具都是采用的该方法。
[15] [16]
静态法的典型代表是符号执行法，由P.D.Coward[14]和C.Ramanmoorthy
等人提出。该方法的主要思想是把符号值作为程序输入，静态“执行”指定路径的语句，从而得到变量的值。这里所谓的执行，是指按照程序执行的顺序将相应的变量用符号表达式代换。该方法的缺点为需要进行复杂的代数运算，难以处理依赖于输入变量的循环条件、数组元素下标和模块调用的情况，特别对于动态的面向对象程序不适合使用。
与静态法相对应的是动态法，该方法的基本思想是从输入空间中任取一个假设解作为初始输入，通过实际运行程序不断调整输入，使得程序实际执行路径向指定路径不断逼近，直到与指定路径完全一致。Korel[17]法是动态法的典型代表：
6
基于遗传算法的测试用例生成方法
其采用的是步进的方式执行程序，即一次只前进一个分支谓词；Korel还提出了“谓词函数”的概念，用来度量分支谓词的接近满足程度。然而，由于Korel法一次只考虑一个分支谓词，使用回溯技术，所以要进行大量的迭代，浪费了大量的资源。而且由于对于非线性路径约束，该方法只能找到局部极小值，当谓词函数有多个局部极小值时显然将难以找到目标路径的解。除此之外，动态法还包括程序插装的方法和迭代松弛法，M.Gallagher和Neelam Guptal[18]分别对这两种方法进行了全面的阐述。
第四种算法是试探法，该方法的基本思想是从输入数据空间中选择输入数据，运行程序，将运行结果结合概率论的思想产生新的数据继续进行试探。其受搜索空间限制条件的约束小，且不需要其它辅助性信息，对于很多高复杂度问题（如大空间、多峰、非线性、全局优化等）具有独特的优势和高效性。试探法主要包括算法、模拟退火算法、禁忌搜索算法、混合策略的算法等。
自20世纪90年代起，算法因其独特的优点而开始被广泛的用于测试用例的生成领域，并取得了良好的研究成果。算法模拟生物学中的变异原理，采用编码技术将待求数据映射到基因空间，并通过选择、交叉、变异等操作和优胜劣汰的自然选择确定搜索方向，从而找到最优解。实验证明，该算法具有隐性并行性和全局寻优能力，可以自动获取搜索过程中的有关信息并用于指导优化。
Jones 等人[19]的实验表明，为使三角形分类等程序达到分支覆盖，算法生成的测试数据比随机法小一到两个数量级。
Jin-Cherng Lin等人 [20] 等人对适应度函数进行了研究，提出了使用广义海明距离来构建适应度函数。
荚伟[21]分析了算法在测试用例产生这一问题上的可行性，提出了要有效解决该问题，必须从以下几个角度进行研究：参数的编码方法、适应度函数的构造、算子的设计以及算法参数的选择等。
Berndt等人 [22]将输入空间划分成多个区间，根据待选输入的多种特性创建了一个最小化函数,使用简单算法进行求解,并使用了求解过程中的化石记录来指导求解过程。
景志远[23]则从数学的角度分析了将MGA和K均值等改进的算法应用于测试用例的自动生成。
7
基于遗传算法的测试用例生成方法
蔡立志等人[24]提出了一种基于算法的成对测试生成方法,该方法用于选择当前局部优化覆盖的测试用例，以此构建满足成对测试基准的测试用例套，有效降低了相同覆盖率下的测试用例数量。
陈雨等人[25]将自适应算子和禁忌搜索思想融入到算法中， 充分发挥算法的全局搜索和禁忌搜索算法局部搜索优势, 提高了测试数据的生成能力。
全君林等人[26]提出了一种应用于软件回归测试过程中的基于算法的最小化测试用例集算法模型，该算法较一般的优化算法具有更高算法性能与效率。
1.3 论文研究内容
本文主要做了以下方面的研究：
（1）广泛阅读了国内外相关文献资料，对软件测试和算法的应用现状进行了概述，认为使用算法进行测试用例生成可行。
（2）分析了使用算法进行测试用例生成的基本内涵，提出了算法框架及对算法进行实现的具体策略。
（3）以三角形分类程序为例进行试验，分析了试验结果，证实了算法的优越性。
8
基于遗传算法的测试用例生成方法
第二章 软件测试及算法基本概念
2.1 软件测试基本概念 2.1.1 软件测试的目的
1983年IEEE在“软件工程标准术语”中将软件测试定义为：“使用人工或自动手段来运行或测定某个软件系统的过程，其目的在于检验该被测软件是否满足规定的需求或是衡量预期结果和实际结果之间的差别。”
定义中指出软件测试的目的是“检验该被测软件是否满足规定的需求或是衡量预期结果和实际结果之间的差别”
Grenford. J. Myers在其著作《The Art Of Software Testing》中提出了与软件测试相关的三个重要观点，指明了软件测试的目的为：
1软件测试是程序的执行过程，目的在于发现错误； ○
2一个好的测试用例是指很可能找到迄今为止尚未发现的错误的用例; ○
3一个成功的测试是指发现了迄今为止尚未发现的错误的测试。 ○
由此可见，软件测试的目的可以概括为：
首先，软件测试要以最少的人力、物力，尽快找出软件中潜在的各种缺陷，通过修正这些缺陷，提高软件产品质量，尽量减少软件产品发布后由潜在的软件缺陷带来的可能的商业风险。其次，通过分析软件缺陷产生的原因，可以帮助发现当前开发开发过程中的软件过程缺陷，以便进行软件过程的改进。同时，通过对测试结果的分析整理，还可以修正软件开发规则，并为软件可靠性分析提供依据。
2.1.2 软件测试的原则
软件测试作为一门独立的计算机软件技术，在执行过程中必须遵守一定的原则，以保证测试效果。软件测试的专家们经过长期的实践，总结出了软件测试的原则应如下：
9
基于遗传算法的测试用例生成方法
1应把“尽早和不断地进行软件测试”作为软件开发者的座右铭。 ○
实践证明单元测试能够尽早发现问题,减少后期测试的错误量。单元测试过程中可以使用相应白盒测试工具（如Junit，Jtest等）进行辅助测试，以提高测试效率。
2测试用例应由测试输入数据、○测试执行步骤和与之对应的预期输出结果三
部分组成。
3应当避免由程序员检查自己的程序。 ○
特别在后期的性能测试及系统测试中，应避免程序员测试自己的程序。这其中除了某些心理因素外，该原则还可避免由于程序员个人的惯性思维而导致的某些理解错误。
4测试用例的设计要确保能覆盖所有可能路径。 ○
在设计测试用例时，应当包括合理的输入条件和不合理的输入条件。不合理的输入条件是指异常的、临界的、可能引起问题的输入条件。
5充分注意测试中的群集现象。 ○
经验表明，测试后程序残存的错误数目与该程序中已发现的错误数目或检错率成正比。应该对错误群集的程序段进行重点测试。
6严格执行测试计划，排除测试的随意性。 ○
软件测试是有组织、有计划、有步骤的活动。测试计划应包括：所测软件的功能，输入和输出，测试内容，各项测试的进度安排，资源要求，测试资料，测试工具，测试用例的选择，测试的控制方法和过程，系统的配置方式，跟踪规则，调试规则，以及回归测试的规定等等以及评价标准。
7应当对每一个测试结果做全面的检查。 ○
8妥善保存测试计划，测试用例，出错统计和最终分析报告，为维护提供方○
便。
2.2 软件测试的难点
（1）测试用例设计
测试用例及测试例程是其设计者对被测对象实现原理和外部需求的理解，能否正确反映对被测对象的质量要求，很大程度上取决于其设计者的分析、理解和
10
基于遗传算法的测试用例生成方法
设计能力。这是一种缺乏指导性方法的、不易制订标准或规范的、需要“技巧”的设计活动。
（2）测试管理
目前缺乏测试管理方面的资料，几乎没有可供参考的、已实现的、完整的测试管理与测试实施模式。
（3）测试的组织
软件测试的有效实施需要开发组织与测试组织充分配合。虽然测试活动看似是对开发人员劳动成果的不断“挑剔”，但测试工作的出发点是：确保开发人员的劳动成果成为可被接收的、更高品质的软件产品。因此，测试人员应向开发人员谦虚求教，在测试工作中真正发挥作用，为保证软件产品的高质量起尽可能大的作用。测试的组织者应在促进上级组织协调各组织工作方面发挥作用。
（4）测试的估计
有效的测试工作需要投入足够的人力和物力，需要对工作的难度和消耗有充分的估计。测试的组织者也应在促进上级组织对资源的统一调度方面发挥作用。
2.3 算法
2.3.1 算法的思想及流程
算法（genetic algorithm）是模拟达尔文的选择和自然淘汰的生物进化过程的计算模型。该算法最先于1975年由美国的J.Holland教授提出。其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。算法作为一种不依赖具体问题的直接搜索方法受到广泛关注，它是现代有关智能计算的关键技术之一。
算法的思想源于生物学和适者生存的自然选择规律，因此是具有“生存+检测”的迭代过程的搜索算法。它以一个群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。算法将问题的解空间映射为空间，对解空间进行编码，即将每个可能的解用一串二进制或十进制数字串表示，
11
基于遗传算法的测试用例生成方法
称为一个染色体，解的每个分量称为一个基因。算法开始时先随机给出一群染色体，即候选解，由预先设定的某个评价指标计算每个染色体的适应值，将适应度低的染色体淘汰掉，而保留适应度高的优良染色体，然后对这些染色体进行选择复制、交叉和变异等操作，从而产生新的一代染色体群体。这样一代一代的“进化”，直至找到算法的最优解，即适应值满足条件的解。由于算法产生的“后代”是由优秀的“父代”和“母代”产生的，因此继承了上代的优良性态而优于上代，从而使算法向着最优解的方向进行，直到满足预先设定的条件。
算法过程包括了编码、产生初始群体、计算适应值、选择、交叉、变异等操作。其一般流程图如图2-1所示：
12
基于遗传算法的测试用例生成方法
开始 Gen:=0 确定字符串长度L 随机产生M个初始群体 满足终止条件？ Y 输出结果 终止 N 计算群体中各个体适应度 自左向右执行一次遗传算子 j:=0 Ps j:=0 Pc j:=0 Pm 根据适应度选择 复制个体 执行复制 将复制结果添加到新群体中 j:=j+1 j=PsM？ 根据适应度选择 两个交换个体 执行交换 将交换后的两个新个体添加到新群体中 j:=j+1 选择变异个体 执行变异 将变异结果添加到新群体中 j:=j+1 N j=PcM？ N j=PmM？ N Y Y Gen:=Gen+1 图2-1 算法流程图
Y 2.3.2 算法的特点
算法是一类可用于复杂系统优化计算的搜索算法，与其他一些优化算法相比，它的主要特点有如下几点[27]：
（1）算法以决策变量的编码作为运算对象，而传统优化算法往往直接利用变量的实际值来进行优化计算。这种对决策变量的编码处理方式，使得我们在优化计算过程中可以借鉴生物学中染色体和基因等概念以及和进化机理。特别是对—些无数值概念或很难有数值概念，而只有代码概念的优化问题，编码处理方式
13
基于遗传算法的测试用例生成方法
更显示出了其独待的优越性。
（2）算法直接以目标函数值作为搜索信息，而不需要目标函数的导数值等其他辅助信息。这个特性对很多目标函数难以求导的优化问题，以及组合优化问题等，应用算法时就显得比较方便。而且，直接利用目标函数值或个体适应度，也可使得我们可以把搜索范围集中到适应度较高的部分搜索空间中，从而提高了搜索效率。
（3）算法同时使用多个搜索点的搜索信息，而传统的优化算法往往是从解空间中的一个初始点开始最优解的迭代搜索过程。单个搜索点的搜索效率不高，甚至可能使搜索过程陷于局部最优解而停滞不前。算法通过对个体组成的群体进行操作运算，产生新的群体，其中包含的群体信息可以避免搜索一些不必搜索的点，所以实际上相当于搜索了更多的点，这是算法所特有的一种隐性并行性。
（4）算法使用概率搜索技术，而很多传统的优化算法往往使用的是确定性的搜索方法。确定性的方法由于固定了点与点之间的转移方法和转移关系，往往可能使得搜索永远达不到最优点，因而也限制了算法的应用范围。而算法属于一种自适应的概率搜索技术，其选择、交叉、变异等运算都是以一种概率的方式来进行的，从而增加了算法搜索过程的灵活性和搜索效率。
2.4本章小结
本章首先介绍了软件测试的一些基本概念，对软件测试的知识做了系统的介绍，包括软件测试的目的、原则、过程，介绍了了软件测试的主要技术难点，其中包括了测试用例的设计。本章后半部分介绍了算法的基本概念，包括算法的思想、流程及特点。
14
基于遗传算法的测试用例生成方法
第三章 基于算法的测试用例生成
3.1基于算法的测试用例生成基本内涵 3.1.1 软件测试用例的基本内涵
测试用例是为某个特殊目标而编制的一组测试输入、执行条件以及预期结果，以便测试某个程序路径或核实是否满足某个特定需求，包含输入和输出两部分。
构造测试用例的目的是为了检查被测软件的操作结果是否与预期的需求相吻合，确定应用程序的某些特性是否正常的工作等。测试用例的质量可以用以下四个标准来描述:
（1）有效性:是否能够发现缺陷，或者至少可能发现缺陷；
（2）仿效性:可仿效的测试用例能够测试多项内容，从而减少测试用例的数量；
（3）经济性:测试用例的执行、分析和调试是否经济； （4）修改性:软件修改后测试用例的维护成本。
实践中，设计测试用例需遵守一定的原则，这些原则主要有： （1）全面性
包括：应尽可能覆盖程序的各种路径；应考虑存在跨年、跨月的数据；大量数据并发测试的准备等。
（2）正确性
输入界面后的数据应与测试文档所记录的数据一致且预期结果应与测试数据发生的业务吻合。
（3）符合正常业务惯例
测试数据应符合用户实际工作业务流程且兼顾各种业务变化的可能。 （4）仿真性
人名、地名、电话号码等应具有模拟功能，符合一般的命名惯例；不允许出现与知名人士、小说中人物名等雷同情况。
15
基于遗传算法的测试用例生成方法
（5）可操作性
测试用例中应写清测试的操作步骤，不同的操作步骤相对应的操作结果。
3.1.2 基于算法的测试用例生成的基本内涵
使用算法实现测试用例的自动生成可描述为[12]：应用算法来求解一组优化的测试用例。在每一步进化计算过程中，测试用例自动生成器使用当前群体（测试用例）驱动被测试程序的执行，每一个测试用例的执行路径被跟踪和记录，以最大化程序执行路径的覆盖为适应性目标函数进行计算，产生出下一代群体。在多代进化之后，得到最优种群或超过特定的循环限制条件而结束。
因为测试用例的自动生成是在一个数据域中寻找满足给定的测试标准的一组测试输入数据的过程，所以近年来出现了把测试用例的生成问题转化成路径搜索问题的思想。由于一般情况下，测试数据的产生是一个不可判定性问题，再加上被测程序的规模和复杂性，一般的搜索算法受到了极大的限制。算法在处理不确定搜索问题时有着非常明显的优势。
算法能针对程序路径生成大量有效测试用例，因此符合测试用例设计的全面性、正确性等原则。生成的测试用例符合上节中的测试用例设计标准，特别是有效性和经济性等，由此可见算法应用于测试用例生成是可行的。
3.2 基于算法的测试用例生成框架
本文基于算法的测试用例生成基本流程如下所示： （1）分析源程序代码，获得程序控制流程图；
（2）由程序控制流程图得到程序分支路径集合，选择目标路径； （3）根据各谓词条件给程序插桩并制定适应度函数；
（4）设定算法参数，包括群体大小、变异率等，随机产生初始测试数据集合；
（5）使用测试数据执行经过插装的源代码，获得适应度值，根据适应度值判断，若满足程序终止条件则输出结果并退出程序，若不满足条件则进入步骤（6）；
16
基于遗传算法的测试用例生成方法
（6）根据得到的适应度值，使用算法的选择、交叉、变异等操作，生成新的测试数据，并回到步骤（5），重复执行；
程序框架如图3-1所示，包含测试环境构造、算法和测试运行环境三部分。
图3-1 程序框架图
静态分析 路径选择 程序插桩 GA初始化 变异 交叉 选择 N 解码 评估 Y 结束 遗传算法 测试环境构造 测试运行环境 驱动模块 待测程序 桩模块
测试环境构造部分是整个系统的基础，它主要利用静态分析提供的基本信息并借助于各种插装技术来构造相应的测试运行环境。
算法部分是系统的核心，它主要按照第一部分生成的编码参数格式构造相应的染色体串，并生成初始种群，然后通过对该种群进行反复的GA运算（选择、交叉和变异）从而引导种群不断地向目标值进化直到最终找到解或达到限定的运行代数为止。
最后部分是测试运行环境。算法第二部分需要对种群中每一个个体的优劣进行评估，它主要是通过实时地调用并运行插装后的测试系统来返回适应度值，从而来指导算法的搜索。
17
基于遗传算法的测试用例生成方法
3.3 基于算法的测试用例生成算法实现 3.3.1 编码策略
使用算法求解问题时，必须将目标问题的实际表示与算法的染色体位串结构之间建立映射关系，这一过程即为编码。编码就是将目标问题的解用一种特定字符串来表示，从而将问题的解空间（有效的候选解，即表现型个体）与算法的码空间（基因型个体）相对应。编码过程是算法的基础，编码方法除了决定了个体的染色体排列形式之外，还决定了个体从GA空间的基因型变换到问题空间的表现型时的解码方法（即为编码方法的逆方法）。同时，编码方法也影响到交叉算子、变异算子等算子的运算方法。
由此可见，编码方法的好坏是影响算法性能及效率的重要因素。一个好的编码方法，有可能会使得交叉运算、变异运算等操作可以简单地实现和执行。相反，选择了不当的编码方法有可能会使得交叉运算、变异运算等操作难以实现，甚至可能会产生很多不属于可行解集合内的无效解。因此Goldberg提出了三条编码评估规范：
①完备性（Completeness）：问题空间中的所有点都能作为GA空间中的点(染色体)表现。
②健全性（Soundness）：GA空间中的染色体能对应所有问题空间中的候选解。
③非冗余性（Nonredundancy）：染色体和候选解一一对应。
常见的编码方法有二进制编码方法、格雷码编码方法、浮点数编码方法、符号编码方法等，在应用中具体使用何种编码方法应根据问题的实际情况而定，这里我们使用二进制编码方法。
二进制编码方法是算法中使用最多的编码方法，不光是由于其编码解码操作简单，便于实现交叉、变异等操作，而且该编码方法符合最小字符集编码原则，能使染色体与候选解一一对应。
使用二进制编码方法进行编码时，先根据问题所要求的求解精度确定符号串的长度，假设某一参数的取值范围为[Xmin,Xmax]，可用长度为L的二进制编码符号
18
基于遗传算法的测试用例生成方法
来表示该参数，则能产生2L个不同的编码，设编码精度为δ，则： Xmin 表示为 0000...000=0 Xmax 表示为 1111...111=2L -1
δ=
XmaxXmin （3-1）
2L1若某个体编码为X：aLaL-1aL-2...a2a1 ，则其解码公式为：
x= Xmin(ai2i1)i1LXmaxXmin （3-2） L213.3.2 适应度函数及程序插桩
（1）适应度函数
在算法中，不需要用到搜索空间的知识，而使用适应度函数对染色体进行评价，一般来说，适应度高的染色体的评价较高，适应度低的染色体评价较低而可能被淘汰，因此，适应度函数直接决定了种群的进化方向，对算法的好坏具有很大影响。同时，适应度函数的复杂度是算法复杂度的主要组成部分，因此适应度函数要求尽可能简单。
适应度函数通常可以从目标函数转化而来。一般来说，要求适应度的取值越大越好。但在实际问题中，有的目标函数是求最大值（如利润问题），也有的目标函数是求最小值（如费用问题）。因此在很多场合需要将目标函数转换为最大值形式并且函数值为非负的适应度函数。
（2）程序插桩
在程序流程图中，每个分支都可以用一个判断表达式来表示，该判断表达式称为分支谓词，其作用是描述了程序遍历该分支的条件，如判断语句“if(a>b)...”中分支谓词为“a>b”。
分支谓词的一般形式为：E1 op E2，E1和E2是算数表达式，关系运算符
op,,,,,!。每个分支谓词都可以转换成等价形式为：F rel 0，其中F为分支函数，其构造方法如表3-1所示。
表3-1 分支函数的构造 分支谓词 E1>E2
分支函数 E2-E1 19 rel < 基于遗传算法的测试用例生成方法
E1>=E2 E1 1f(x1)1f(x2)1f(x3)其中，f(xi)为各分支插桩后的分支函数值。 3.3.3 策略 （1）选择策略 选择运算也叫复制运算，模拟了生物界优胜劣汰的自然选择现象。通过选择将优胜的个体直接到下一代或通过配对交叉产生新一代个体再到下一代。选择运算的依据是个体的适应度，适应度高的个体被选择到下一代的概率就大，甚至可能被多次复制，而适应度低的个体则可能一次都没被选中而淘汰。选择的概率一般取Ps 为0.1至0.2 。 常用的选择运算的方法有轮盘赌转法、随机遍历抽样、锦标赛选择等，其中以轮盘赌转法最为常用。该算法将所有染色体的适应度总和看做一个轮子的圆周，而各染色体按其适应度占适应度总和的比例值大小占据一个扇区。每次进行选择时相当于轮盘的一次转动，转到哪个扇区则该扇区的染色体被选中。这样适应度越高的染色体被选中的概率就越大。若某染色体的适应度为f(xi)，则被选中的概率为： Psf(xi) （3-4） f(xi)20 基于遗传算法的测试用例生成方法 图3-2是一个简单的赌轮的例子： 13% 35% 15% 0.67 37% |---------|--------------------------|-----------|-*-------------------------| 个体1 个体2 个体3 个体4 图3-2 轮盘赌转法示意 图3-2中随机数为0.67落在了个体4的段内，本次选择了个体4。 （2）交叉策略 交叉运算是算法中产生新个体的主要手段，其模拟的是生物学中的杂交现象。交叉运算通过使两个体的局部交换而使双方的优点有可能结合产生更好的新个体。一般控制产生交叉运算的概率Pc 为0.5至0.8 。 在二进制编码中，根据交叉点的不同可以分为单点交叉、两点交叉、均匀交叉等。在本文中采用的是单点交叉的方法，即首先在亲代中随机选取一个交叉点（染色体的某个码位），然后将两个亲代在该点及之后的染色体部分进行交换。 （3）变异策略 变异运算模拟的是生物中的基因突变现象。通过变异操作可以增强算法中群体的多样性，防止未成熟收敛现象，同时也使算法具备了局部随机搜索能力，是实现全局优化性能的重要算子之一。通常，变异的控制概率较小，Pm 一般取值为0.001至0. 1。 在二进制编码方式中，变异运算即是将某些基因位上的基因值取反，即0变1或1变0。一般变异个体的选择及变异位置都是随机确定的。二进制编码中的变异方法有基本位变异、均匀变异、高斯变异和二元变异等。 本文采用的是基本位变异方法，即先随机选择某变异个体，再随机确定染色体的一个变异点将该码位置反。 3.3.4 参数控制 除了上面提到的选择、交叉、变异的概率外，在算法中还有一些参数主要如下： 1种群规模 ○ 群体规模较大可以增加算法的多样性，提高GA搜索的质量，防止算法未成 21 基于遗传算法的测试用例生成方法 熟收敛。但是群体规模大使个体适应度的计算量大大增加，影响了算法的效率。因此应根据不同的实际情况确定不同的种群规模。Goldberg证明了在二进制编码的前提下，若个体长度为L，则种群规模的最优值为2L/2。 2染色体长度 ○ 染色体长度即是编码长度，也即是表示个体的字符串的长度。染色体的长度由具体问题决定，当解的取值范围越大、求值精度越大则染色体长度越大，带来的计算时间也相应越长。 3算法终止条件 ○ 一般来说，算法的终止条件为预先设定的最大进化代数，通常取100到500 。也可以为某一特定条件，事具体问题而定。 以上参数为通常情况下的取值，当然并非是固定不变的。在不同的算法中可以根据实际情况作相应的调整，只要能提高算法的运行效率就是可行的。 3.4 本章小结 本章是论文的核心章节，对算法应用于测试用例的生产方法进行了系统的介绍。首先介绍了算法生成测试用例的基本内含，然后提出了基本框架，最后对本文中算法实现的相关操作进行了描述，包括编码策略、适应度函数构造、选择策略、交叉策略、变异策略等。 22 基于遗传算法的测试用例生成方法 第四章 实验及结果分析 4.1 待测程序分析 4.1.1 待测程序引入 本章中将以三角形分类程序为例来验证算法。三角形分类程序在许多软件测试研究中被作为基准程序来使用，因为其包含清晰而又复杂的逻辑，并且即使将一个较大范围的整数作为输入，也只有少量的输入组合能满足代码的某些特定分支。例如当输入为1到10 的整数时，1000组输入只有10组能满足判断为“等边三角形”的分支。三角形源程序为： String tri_type(int a,int b,int c) { string type; if(a>b) change(a,b); if(a>c) change(a,c); if(b>c) change(b,c); if(a+b>c) { if(a==b||b==c) { if(a==c) type=“等边三角形”; else type=“等腰三角形”; }else type=“普通三角形”; } else type=“不是三角形”; return type; } 4.1.2 程序流程分析 该程序流程图如图4-1所示，程序分为两部分，先将输入值由小到大排序，再将三角形进行分类。 23 基于遗传算法的测试用例生成方法 输入a,b,c a>b? Y 交换a,b Y Y 交换a,c N a>c? N b>c? 交换b,c N a+b>c? 1 Y ○N 2 ○不是三角形 a==b||b==c? 3 Y ○N 普通三角形 4 ○N 5 ○等腰三角形 a==c? Y ○6 等边三角形 图4-1 三角形分类程序流程图 结束 4.1.3 路径分析 通过对程序流程分析可知，该程序对三角形进行分类的语句为图4-2中标有 1”至“○6”号的分支，对这些分支进行路径分析如表4-1所示： “○ 表4-1 路径分析 路径号 w1 W2 W3 W4 分支 2 ○1-○4 ○1-○3-○5 ○1-○3-○6 ○结果 不是三角形 普通三角形 等腰三角形 等边三角形 4.2 程序插桩 根据3.3.2，对待测程序插桩： String tri_type(int a,int b,int c) { string type; if(a>b) change(a,b); if(a>c) change(a,c); if(b>c) change(b,c); 24 基于遗传算法的测试用例生成方法 f1=c-(a+b) ; //插桩1 if(a+b>c) { f2=min(abs(a-b),abs(b-c)); //插桩2 if(a==b||b==c) { f3=abs(a-c); //插桩3 if(a==c) type=“等边三角形”; else type=“等腰三角形”; } else type=“普通三角形”; } else type=“不是三角形”; return type; F=1/(1+f1)+1/(1+f2)+1/(1+f3); //适应度函数 return F; } 4.3 参数设定及程序实现 4.3.1 参数设定 （1）编码 在本例子中，由于程序输入为三角形的三条边的长度，因此设定输入值类型为0~63的整数，采用二进制级联编码方法，每个参数编码长度为6位，精度为1，并将三个参数进行级联（如参数000000、111111、101010级联后为000000111111101010），级联后染色体长度为18位。 （2）操作参数 在本实验中，设定操作的参数如表4-2所示： 表4-2 操作参数设定 种群大小 100 选择策略及概率 轮盘赌转法，0.1 交叉策略及概率 单点交叉，0.8 变异策略及概率 基本位变异，0.1 最大进化代数 100 （3）算法终止条件 本实验中设定算法终止条件为满足以下两个条件之一： 1找到最优解，即适应度为100的解； ○ 2达到最大进化代数，○当程序进化满100代后，不管有没找到最优解都将退 出。 25 基于遗传算法的测试用例生成方法 4.3.2 部分程序实现 本文中的三角形分类程序是在Microsoft Visual Studio2005的环境下采用C++语言实现的。以下为该程序的主要算法模块： （1）染色体定义模块，该模块完成了染色体的编码： struct sides { int a; int b; int c; //测试的三个数据 bitset<3*BIT> chromosome; //该组的染色体 int sufficiency; //该组数的适应度 bool isOp ; } //标记是否操作过 （2）计算适应度，采用插桩法： int getSufficiency(int a, int b, int c) { int f, f1, f2, f3; if(a>b) change(a,b); if(a>c) change(a,c); if(b>c) change(b,c); f1 = c - (a + b); //if(a+b>c) f2 = min //if(a==c) type=“等边三角形”; //else type=“等腰三角形”; //else type=“普通三角形”; //else type=“不是三角形”; //return type; if (f1 < 0) { f1 = 0; } f = ( 100/(1+f1) + 100/(1+f2)+ 100/(1+f3))/3; return f; } （3）选择操作，使用了轮盘赌转法： void select(sides newGroup[], sides oldGroup[]) { resetFlag(oldGroup); int aPos[GROUP]; //存储每组数据在转盘中的位置 aPos[0] = oldGroup[0].sufficiency; for (int i = 1; i < GROUP; i++) { aPos[i] = oldGroup[i].sufficiency; aPos[i] += aPos[i - 1]; 26 基于遗传算法的测试用例生成方法 } for(int i = 0; i < SELECTION; ) { int random = rand()%aPos[GROUP - 1]; //产生随即数,0到群体中的最后一组数据所在的位置找到该随机数所在位置,如果位置重复了就重新选择 for (int j = 0; j < GROUP; j++) { if(random <= aPos[j]) { if(!oldGroup[j].isOp) { newGroup[i] = oldGroup[j]; oldGroup[j].isOp = true; i++; break; } else { break; }}}}} （4）交叉操作，先用轮盘赌转法选择，再用单点交叉法进行交叉： void cross(sides newGroup[], sides oldGroup[]) { int aPos[GROUP]; aPos[0] = oldGroup[0].sufficiency; for (int i = 1; i < GROUP; i++) { aPos[i] = oldGroup[i].sufficiency; aPos[i] += aPos[i - 1]; } for(int i = 0; i < CROSS; ) { int random = rand()%aPos[GROUP - 1]; for (int j = 0; j < GROUP; j++) { if(random <= aPos[j]) { if(!oldGroup[j].isOp) { newGroup[int(SELECTION) + i] = oldGroup[j]; oldGroup[j].isOp = true; i++; break; } else { break; }}}} //两两进行交叉,并更新每组的适应值 for (int i = SELECTION; i < SELECTION + CROSS; i += 2) { int random = rand()%(3*BIT); //随机选一个位置进行交叉 string str1 = newGroup[i].chromosome.to_string(); string str2 = newGroup[i + 1].chromosome.to_string(); string new1 = str1.substr(0, random + 1) + str2.substr(random); string new2 = str2.substr(0, random + 1) + str1.substr(random); bitset<12> bsNew1(new1); bitset<12> bsNew2(new2); //更新染色体 newGroup[i].chromosome = bsNew1; newGroup[i+1].chromosome = bsNew2; //更新数字 27 基于遗传算法的测试用例生成方法 resetNum(newGroup[i]); resetNum(newGroup[i + 1]); //更新适应度 newGroup[i].sufficiency = getSufficiency(newGroup[i].a, newGroup[i].b, newGroup[i].c); newGroup[i + 1].sufficiency = getSufficiency(newGroup[i + 1].a, newGroup[i + 1].b, newGroup[i + 1].c); }} （5）变异操作，采用基本位变异方法： void aberrance(sides newGroup[], sides oldGroup[]) { int pos = SELECTION + CROSS; for(int i = 0; i < GROUP; i++) { if (!oldGroup[i].isOp) { int random = rand()%(3*BIT); //随机产生变异位 newGroup[pos] = oldGroup[i]; newGroup[pos].chromosome.flip(3*BIT - random -1); resetNum(newGroup[pos]); //更新适应度 newGroup[pos].sufficiency = getSufficiency(newGroup[pos].a, newGroup[pos].b, newGroup[pos].c); pos++; }}} 4.4 结果分析 （1）对算法自身的进化能力分析 以三角形分类程序的判为“等边三角形”的路径w4为例，运行程序，发现在51代时找到了最优解，表4-3、4-4、4-5分别为第0代、第13代、第51代的适应度为前10的个体情况： 表4-3 第0代适应度前10的个体 个体编号 1 2 3 4 5 6 7 8 9 10 染色体编码 110101011100011100 100110101001100111 011011011010010110 000111001100001000 100110101101101100 011011100011100010 111011111010101011 110110111000111011 100001011110011100 110011111000111010 参数值 A 53 38 27 7 38 27 59 54 33 51 28 B 28 41 26 12 45 35 58 56 30 56 C 28 39 22 8 44 34 43 59 28 58 适应度 67 58 55 55 54 53 51 49 49 48 基于遗传算法的测试用例生成方法 表4-4 第13代适应度前10的个体 个体编号 1 2 3 4 5 6 7 8 9 10 染色体编码 010000001011010000 101000111101101000 101000101000010010 101011001011101011 010100010111010110 111101101100111110 100111100110001010 011010111101111100 000011101001101000 011111100101100111 参数值 A 16 40 40 43 20 61 39 26 3 31 B 11 61 40 11 23 44 38 61 41 37 参数值 A 45 15 39 38 63 16 9 48 24 14 B 45 15 15 55 63 15 14 58 39 16 C 45 17 39 38 6 17 15 59 25 18 C 16 40 18 43 22 62 10 60 40 39 适应度 72 68 68 67 58 51 51 50 50 48 表4-5 第51代适应度前10的个体 个体编号 1 2 3 4 5 6 7 8 9 10 染色体编码 101101101101101101 001111001111010001 100111001111100111 100110110111100110 111111111111000110 010000001111010001 001001001110001111 110000111010111011 011000100111011001 001110010000010010 适应度 100 77 68 68 67 61 54 52 52 51 由这三张表可见，随着进化过程的继续，群体的总体适应度在增加，说明算法正朝着最优解的方向收敛，直至找到最优解。这说明算法在程序测试数据自动生成中是有一定作用的，它能逐渐改善个体，使其越来越接近我们的标准路径，最终达到我们设定的标准路径。 （2）算法与随机法比较 随机法是目前大多数测试工具生成测试用例所使用的算法，其思想已在本文第一章中介绍过。 为了显示算法的优越性，现分别使用算法和随机法对三角形分类程序中的四条路径进行20次的搜索，分析这两种算法的成功率与运行速度，对比结果如表4-6所示： 29 基于遗传算法的测试用例生成方法 表4-6 两种算法运行结果 路径号 W1 W2 W3 W4 算法 平均进收敛化代数 次数 0 0 0 27 20 20 20 20 成功率（%） 100 100 100 100 平均运行时间（ms） 2 2 3 81 平均进收敛化代数 次数 0 20 0 0 33 20 20 16 随机法 成功率（%） 100 100 100 80 平均运行时间（ms） 0 0 0 0 由表4-6可知，使用随机法的平均运行时间较算法短，但随机法对于稍微复杂的路径进行搜索时成功率明显下降，表中在w4路径的搜索结果中，随机法的成功率为80%，搜索效果较算法差。而算法虽然运行时间稍久于随机法，但其四条路径的成功率均为100%，特别是在复杂路径中也能找到最优解，充分发挥了其全局寻优能力。在实际运用中，测试数据覆盖率的高低是软件质量的基本保障，因此算法成功率显然比运行时间更为重要，可见算法的优越性。 4.5 本章小结 本章以三角形分类程序为例使用算法进行测试用例的生成，是前几章内容的结晶。文中先对待测程序的流程和路径等进行了分析，然后对程序进行插桩，并对相关参数进行了设定，然后展示了程序主要模块的代码，最后通过分析程序的运行结果，并和随机法作了比较，显示了算法的优越性。 30 基于遗传算法的测试用例生成方法 第五章 总结与展望 软件测试是软件工程中的重要环节，随着软件技术的发展和软件规模的扩大，软件测试日益凸显其重要性。而测试数据是软件测试的基础。传统的手工构建测试数据工作量大，浪费了大量的人力、物力资源，且测试效率低。因此测试用例的自动生成成为了国内外学者研究的热点。算法作为一种优化的搜索算法，在软件测试中得到了广泛的应用和研究。 本文作者通过对大量文献中测试用例生成方法和算法的学习，将算法应用到测试用例的生成上。文中首先介绍了软件测试及算法的国内外研究现状，然后介绍了软件测试和算法的基本概念，接着提出了基于算法生成测试用例的内含、框架及模型，最后以三角形分类程序为例验证了基于生成测试用例的可行性。 由于时间问题，本文还存在许多问题和不足，将作为进一步研究的主要内容和方向： 第一，本文只用到了算法，并没有将其它算法与之混合使用以改进性能。 第二，本文中算法所使用的适应度函数及算子均采用的是比较简单且使用广泛的算法，并没有将这些算法做进一步的研究和改进。 第三，本文最后实现的程序只是一个产生测试数据的原始工具模型，特别在用户界面方面还很欠缺，需要进一步完善。 31 基于遗传算法的测试用例生成方法 致谢语 四年的本科学习生涯很快就要过去了，在本论文完成之际，我首先要感谢***老师，*老师在我从论文选题至今给了我不少建议，使我受益良多，是我能顺利完成论文的关键所在。*老师治学严谨，待人和蔼，使我以后工作、学习中为人处事的榜样。 同时还要衷心感谢***老师。*老师在担任班导师期间时常给我们教授学习和工作的实际经验，使我对于日后的工作方向有了明确的定位，也将在我日后的工作中继续产生良好的作用。 感谢***同学在程序实现部分的帮助。 感谢我的家人以及所有在生活中、学习中帮助过我或给予过我良好启发的人。 32 基于遗传算法的测试用例生成方法 参考文献 [1] Ron Patton.软件测试(第二版)[M].北京:机械工业出版社，2006:4-5 [2]赵晓华，计算机软件可靠性与质量管理[M].北京:中国经济出版社,1992 [3]徐仁佐.软件可靠性工程[M].清华大学出版社，2007.5 [4]王小平，曹立明.算法理论、应用与软件实现[M].西安:西安交通大学出版社,2001. [5]许秀梅.基于退火免疫算法的测试数据生成方法研究[D].北京：北京交通大学，2007 [6]乐鑫喜.基于退火算法的测试用例自动生成[D].武汉：武汉理工大学, 2005 [7]律亚楠.基于算法的测试数据生成研究[D].汕头：汕头大学，2008 [8]钱肖英.基于算法的测试数据自动生成方法的研究[D].杭州：浙江工商大学，2008 [9]马志兵.基于算法的测试数据自动生成技术研究[D].青岛：青岛大学，2009 [10]顾鹏.基于算法的测试用例产生系统关键技术研究[D].武汉：华中科技大学，2006 [11]陈雨.基于算法的测试用例生成[D].上海：东华大学，2009 [12]林惠娟.基于算法的测试用例自动生成技术研究[D].成都：四川大学，2006 [13] D.Bird and C.Munoz. Automatic generation of random self-checking test cases[J]. IBM System J. vol.22, NO.3. 1983:229-245 [14] P.D.Coward. Symbolic execution and testing[J]. Information and Software Teehnology. 1991, 2: 53-64 [15] C.V.Ramamoorthy, S. Ho. And W.Chen. On the automated generation of Program test data[J]. IEEE Trans. Software Eng. Vol.SE – 2, NO.1. 1981 : 117-127 [16] Ramamoorthy C.V. On the automated generation of Program test data[J]. IEEE Trans on Software Eng, 1976, 4 : 215-222 [17] Korel B. Automated software test data generation [J]. IEEE Trans. 33 基于遗传算法的测试用例生成方法 on Software Engineering, 1990, 16(8) : 870-879. [18] Neelam GuPta , Aditya P . Mathur , Mary Lou Soffa . Generating test data from branch coverage[C] . The Fifteenth IEEE International Conference on Automated Software Engineering(ASE’00) . France : Grenoble , 2000. [19] Jones B.F., Eyres D.E., A strategy for using genetic algorithms to automate branch and fault-based testing[J] . The Computer Journal, 1998, 41(2): 98-107. [20] Jin-Cherng Lin and Pu-Lin Yeh. Using Genetic Algorithms for Test Case Generation inPath Testing [J]. Ninth Asian Test Symposium(ATS’00): 241 -246 [21] 荚伟,高仲仪. 用算法实现软件结构测试数据的自动生成[J]. 计算机与数字工程, 1996, 24(01): 7-14 [22] Berndt D, Fisher J, Johnson L. Breeding Software Test Cases with Genetic Algorithms[C]. Proceedings of the 36th Hawaii International Conference on System Sciences,2003. [23] 景志远.K均值算法在软件测试算例自动生成中的应用研究[J].油气田地面工. VOL. 22. No.4 , 2003 , 4: 15-16. [24]蔡立志,童维勤,杨根兴. 基于两两覆盖准则的算法测试用例生成[J]. 计算机应用与软件，2008，12. [25]陈雨,姚砺. 基于改进算法的测试用例生成[J]. 电子科技, 2009, 07. [26]全君林,陆璐. 基于算法测试用例集极小化研究[J]. 计算机工程与应用,2009,45(19). [27] Godberg D.E. Genetic Algorithms in search, Optimization and Machine Learning[M]. Addison-Wesley, 1989. 34 因篇幅问题不能全部显示，请点此查看更多更全内容