《毕业论文基于遗传算法的测试用例生成方法.doc》由会员分享，可在线阅读，更多相关《毕业论文基于遗传算法的测试用例生成方法.doc（21页珍藏版）》请在三一办公上搜索。
1、摘要软件测试是保证软件质量和可靠性重要手段，在这方面发挥着其它方法不可替代的作用。然而，软件测试是一个复杂的过程，需要耗费巨大的人力、物力和时间，约占整个软件开发成本的40%50%。因此，提高软件测试工具的自动化程度对于确保软件开发质量、降低软件开发成本非常重要。而提高测试用例生成的自动化程度又是提高测试工具乃至整个测试过程自动化程度的关键所在，本文主要针对这一问题进行了研究和设计。本文在分析软件测试和遗传算法基本概念的基础上，提出软件测试用例的设计是软件测试的难点之一。论文提出了基于遗传算法的测试用例生成的内含是应用遗传算法来求解一组优化的测试用例，其框架包括了测试环境构造、遗传算法及测试运
2、行环境三部分，论文给出了基于遗传算法的测试用例生成的模型。最后以三角形分类程序为例应用遗传算法进行测试用例生成的模拟，结果显示，应用遗传算法进行测试用例生成可行。关键词：软件测试 测试用例 遗传算法ABSTRACTSoftware 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
3、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
4、 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 g
5、enetic 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 includ
6、es 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 gene
7、tic algorithm. The results display that software test case generation basing on genetic algorithm is possible.KEY WORDS: software test , test case , genetic algorithm目录摘要1ABSTRACT2目录3第一章 绪论51.1 问题的提出5第二章 遗传算法基本概念62.1 遗传算法62.1.1 遗传算法的思想及流程62.1.2 遗传算法的特点72.2本章小结8第三章 基于遗传算法的测试用例生成93.1基于遗传算法的测试用例生成基本内涵9
8、3.1.1 软件测试用例的基本内涵93.1.2 基于遗传算法的测试用例生成的基本内涵93.2 基于遗传算法的测试用例生成框架103.3 基于遗传算法的测试用例生成算法实现113.3.1 编码策略113.3.2 适应度函数及程序插桩113.3.3 遗传策略123.3.4 参数控制133.4 本章小结14第四章 实验及结果分析154.1 待测程序分析154.1.1 待测程序引入154.1.2 程序流程分析154.1.3 路径分析164.2 程序插桩164.3 参数设定及程序实现174.3.1 参数设定174.4 本章小结18第五章 总结与展望19致谢语20参考文献21第一章 绪论1.1 问题的提出
9、在信息化普及的今天，计算机在人们的生活和工作中占据着重要地位，使人们的工作效率提高，也使生活更丰富多彩。而作为计算机的重要组成部分，软件的重要性不言而喻。随着计算机技术的日益发展，计算机软件的规模越来越庞大，复杂性越来越高，这就为软件质量的保证带来了困难。因为软件的开发过程大部分是由人的智力活动构成，不可能完美无缺。而软件缺陷如果不能及时发现，带来的损失可能是巨大的，有的甚至会危及人的生命。然而，目前生成测试用例的方法主要是向前核查法和逆向回溯法，测试人员根据自己的项目经验手工为指定的程序路径生成测试数据5。向前核查法是指沿预期的路径向前检查，确定到每一个判断点时变量所能提供的最宽数值区间，然
10、后继续前行，从而将多个变量的可能取值范围逐渐缩小，到达程序出口后，就能找到覆盖这条路径所需的输入数据。逆向回溯法正好相反，是指从期望执行的程序位置出发，逆向回溯，在每个判断点处逐渐调整各变量取值，直到退到程序入口，即获得所需的输入数据。向前核查法和逆向回溯法的局限性是，对某些条件要求苛刻的路径使用时非常困难，同时由于大多数程序中包含的路径数非常多，如果按每条路径手工测试，显然带来的工作量是非常巨大的。由于测试的工作量大、测试过程的重复性高等特点，自动化测试正逐渐得到广泛的应用。很多测试工具的使用大大提高了测试人员的工作效率，有效减少了项目开支。然而这些工具主要为测试的执行、管理和度量工具，在测
11、试用例自动生成方面还不完善。而在软件测试过程中，动态测试作为测试的重要环节占了很大比例，动态测试的关键正是测试用例的生成问题。因此，寻找一种有效的测试用例生成方法是提高测试自动化的重中之重。第二章 遗传算法基本概念2.1 遗传算法2.1.1 遗传算法的思想及流程遗传算法（genetic algorithm）是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。遗传算法作为一种不依赖具体问题的直接搜索方法受到广泛关注，它是现代有关智能计算的关键技术之一。遗传算法的思想源于生物遗传学和适者生存的自然选择规律，因此是具有“生存+检测”的迭代过程的搜索算法。它以一个群体中的所有个体为对象，并利用随
12、机化技术指导对一个被编码的参数空间进行高效搜索。遗传算法将问题的解空间映射为遗传空间，对解空间进行编码，即将每个可能的解用一串二进制或十进制数字串表示，称为一个染色体，解的每个分量称为一个基因。算法开始时先随机给出一群染色体，即候选解，由预先设定的某个评价指标计算每个染色体的适应值，将适应度低的染色体淘汰掉，而保留适应度高的优良染色体，然后对这些染色体进行选择复制、交叉和变异等遗传操作，从而产生新的一代染色体群体。这样一代一代的“进化”，直至找到算法的最优解，即适应值满足条件的解。由于算法产生的“后代”是由优秀的“父代”和“母代”产生的，因此继承了上代的优良性态而优于上代，从而使算法向着最优解
13、的方向进行，直到满足预先设定的条件。遗传算法过程包括了编码、产生初始群体、计算适应值、选择、交叉、变异等操作。其一般流程图如图2-1所示：j:=0选择变异个体执行变异将变异结果添加到新群体中j:=j+1j=PmM？YN执行交换j:=j+1根据适应度选择两个交换个体j:=0将交换后的两个新个体添加到新群体中j=PcM？NYj:=0根据适应度选择复制个体执行复制将复制结果添加到新群体中j:=j+1j=PsM？Y开始Gen:=0自左向右执行一次遗传算子计算群体中各个体适应度终止输出结果随机产生M个初始群体确定字符串长度L满足终止条件？YNNPsPcPmGen:=Gen+1图2-1 遗传算法流程图2.
14、1.2 遗传算法的特点遗传算法是一类可用于复杂系统优化计算的搜索算法，与其他一些优化算法相比，它的主要特点有如下几点27：（1）遗传算法以决策变量的编码作为运算对象，而传统优化算法往往直接利用变量的实际值来进行优化计算。这种对决策变量的编码处理方式，使得我们在优化计算过程中可以借鉴生物学中染色体和基因等概念以及遗传和进化机理。特别是对些无数值概念或很难有数值概念，而只有代码概念的优化问题，编码处理方式更显示出了其独待的优越性。（2）遗传算法直接以目标函数值作为搜索信息，而不需要目标函数的导数值等其他辅助信息。这个特性对很多目标函数难以求导的优化问题，以及组合优化问题等，应用遗传算法时就显得比较
15、方便。而且，直接利用目标函数值或个体适应度，也可使得我们可以把搜索范围集中到适应度较高的部分搜索空间中，从而提高了搜索效率。（3）遗传算法同时使用多个搜索点的搜索信息，而传统的优化算法往往是从解空间中的一个初始点开始最优解的迭代搜索过程。单个搜索点的搜索效率不高，甚至可能使搜索过程陷于局部最优解而停滞不前。遗传算法通过对个体组成的群体进行操作运算，产生新的群体，其中包含的群体信息可以避免搜索一些不必搜索的点，所以实际上相当于搜索了更多的点，这是遗传算法所特有的一种隐性并行性。（4）遗传算法使用概率搜索技术，而很多传统的优化算法往往使用的是确定性的搜索方法。确定性的方法由于固定了点与点之间的转移
16、方法和转移关系，往往可能使得搜索永远达不到最优点，因而也限制了算法的应用范围。而遗传算法属于一种自适应的概率搜索技术，其选择、交叉、变异等运算都是以一种概率的方式来进行的，从而增加了算法搜索过程的灵活性和搜索效率。2.2本章小结本章首先介绍了软件测试的一些基本概念，介绍了遗传算法的基本概念，包括遗传算法的思想、流程及特点。第三章 基于遗传算法的测试用例生成3.1基于遗传算法的测试用例生成基本内涵3.1.1 软件测试用例的基本内涵测试用例是为某个特殊目标而编制的一组测试输入、执行条件以及预期结果，以便测试某个程序路径或核实是否满足某个特定需求，包含输入和输出两部分。构造测试用例的目的是为了检查被
17、测软件的操作结果是否与预期的需求相吻合，确定应用程序的某些特性是否正常的工作等。测试用例的质量可以用以下四个标准来描述:（1）有效性:是否能够发现缺陷，或者至少可能发现缺陷；（2）仿效性:可仿效的测试用例能够测试多项内容，从而减少测试用例的数量；（3）经济性:测试用例的执行、分析和调试是否经济；（4）修改性:软件修改后测试用例的维护成本。3.1.2 基于遗传算法的测试用例生成的基本内涵使用遗传算法实现测试用例的自动生成可描述为12：应用遗传算法来求解一组优化的测试用例。在每一步进化计算过程中，测试用例自动生成器使用当前群体（测试用例）驱动被测试程序的执行，每一个测试用例的执行路径被跟踪和记录，
18、以最大化程序执行路径的覆盖为适应性目标函数进行计算，产生出下一代群体。在多代进化之后，得到最优种群或超过特定的循环限制条件而结束。因为测试用例的自动生成是在一个数据域中寻找满足给定的测试标准的一组测试输入数据的过程，所以近年来出现了把测试用例的生成问题转化成路径搜索问题的思想。由于一般情况下，测试数据的产生是一个不可判定性问题，再加上被测程序的规模和复杂性，一般的搜索算法受到了极大的限制。遗传算法在处理不确定搜索问题时有着非常明显的优势。遗传算法能针对程序路径生成大量有效测试用例，因此符合测试用例设计的全面性、正确性等原则。生成的测试用例符合上节中的测试用例设计标准，特别是有效性和经济性等，由
19、此可见遗传算法应用于测试用例生成是可行的。3.2 基于遗传算法的测试用例生成框架本文基于遗传算法的测试用例生成基本流程如下所示：（1）分析源程序代码，获得程序控制流程图；（2）由程序控制流程图得到程序分支路径集合，选择目标路径；（3）根据各谓词条件给程序插桩并制定适应度函数；（4）设定算法参数，包括群体大小、变异率等，随机产生初始测试数据集合；（5）使用测试数据执行经过插装的源代码，获得适应度值，根据适应度值判断，若满足程序终止条件则输出结果并退出程序，若不满足条件则进入步骤（6）；（6）根据得到的适应度值，使用遗传算法的选择、交叉、变异等操作，生成新的测试数据，并回到步骤（5），重复执行；测
20、试环境构造部分是整个系统的基础，它主要利用静态分析提供的基本信息并借助于各种插装技术来构造相应的测试运行环境。遗传算法部分是系统的核心，它主要按照第一部分生成的编码参数格式构造相应的染色体串，并生成初始种群，然后通过对该种群进行反复的GA运算（选择、交叉和变异）从而引导种群不断地向目标值进化直到最终找到解或达到限定的运行代数为止。最后部分是测试运行环境。遗传算法第二部分需要对种群中每一个个体的优劣进行评估，它主要是通过实时地调用并运行插装后的测试系统来返回适应度值，从而来指导遗传算法的搜索。3.3 基于遗传算法的测试用例生成算法实现3.3.1 编码策略使用遗传算法求解问题时，必须将目标问题的实
21、际表示与遗传算法的染色体位串结构之间建立映射关系，这一过程即为编码。编码就是将目标问题的解用一种特定字符串来表示，从而将问题的解空间（有效的候选解，即表现型个体）与遗传算法的码空间（基因型个体）相对应。编码过程是遗传算法的基础，编码方法除了决定了个体的染色体排列形式之外，还决定了个体从GA空间的基因型变换到问题空间的表现型时的解码方法（即为编码方法的逆方法）。同时，编码方法也影响到交叉算子、变异算子等遗传算子的运算方法。常见的编码方法有二进制编码方法、格雷码编码方法、浮点数编码方法、符号编码方法等，在应用中具体使用何种编码方法应根据问题的实际情况而定，这里我们使用二进制编码方法。3.3.2 适
22、应度函数及程序插桩（1）适应度函数在遗传算法中，不需要用到搜索空间的知识，而使用适应度函数对染色体进行评价，一般来说，适应度高的染色体的评价较高，适应度低的染色体评价较低而可能被淘汰，因此，适应度函数直接决定了种群的进化方向，对算法的好坏具有很大影响。同时，适应度函数的复杂度是遗传算法复杂度的主要组成部分，因此适应度函数要求尽可能简单。适应度函数通常可以从目标函数转化而来。一般来说，要求适应度的取值越大越好。但在实际问题中，有的目标函数是求最大值（如利润问题），也有的目标函数是求最小值（如费用问题）。因此在很多场合需要将目标函数转换为最大值形式并且函数值为非负的适应度函数。（2）程序插桩在程序
23、流程图中，每个分支都可以用一个判断表达式来表示，该判断表达式称为分支谓词，其作用是描述了程序遍历该分支的条件，如判断语句“if(ab).”中分支谓词为“ab”。分支谓词的一般形式为：E1 op E2，E1和E2是算数表达式，关系运算符。每个分支谓词都可以转换成等价形式为：F rel 0，其中F为分支函数，其构造方法如表3-1所示。表3-1 分支函数的构造分支谓词分支函数relE1E2E2-E1=E2E2-E1=E1E2E1-E2E1=E2E1-E2=E1=E2abs(E1-E2)=E1!=E2-abs(E1-E2)b) change(a,b); if(ac) change(a,c); if(b
24、c) change(b,c); if(a+bc) if(a=b|b=c) if(a=c) type=“等边三角形”; else type=“等腰三角形”; else type=“普通三角形”; else type=“不是三角形”; return type; 4.1.2 程序流程分析该程序流程图如图4-1所示，程序分为两部分，先将输入值由小到大排序，再将三角形进行分类。输入a,b,c交换a,b不是三角形ab?ac?bc?a=b|b=c?a+bc?交换a,c交换b,ca=c?等腰三角形普通三角形等边三角形结束YYYYYYNNNNNN图4-1 三角形分类程序流程图4.1.3 路径分析通过对程序流程分
25、析可知，该程序对三角形进行分类的语句为图4-2中标有“”至“”号的分支，对这些分支进行路径分析如表4-1所示：表4-1 路径分析路径号分支结果w1不是三角形W2-普通三角形W3-等腰三角形W4-等边三角形4.2 程序插桩根据3.3.2，对待测程序插桩：String tri_type(int a,int b,int c) string type; if(ab) change(a,b); if(ac) change(a,c); if(bc) change(b,c); f1=c-(a+b) ; /插桩1 if(a+bc) f2=min(abs(a-b),abs(b-c); /插桩2 if(a=b|b
26、=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）编码在本例子中，由于程序输入为三角形的三条边的长度，因此设定输入值类型为063的整数，采用二进制级联编码方法，每个参数编码长度为6位，精度为1，并将三个参数进行级联（如参数000000、111111、101010级联后为000
27、000111111101010），级联后染色体长度为18位。（2）遗传操作参数在本实验中，设定遗传操作的参数如表4-2所示：表4-2 遗传操作参数设定种群大小选择策略及概率交叉策略及概率变异策略及概率最大进化代数100轮盘赌转法，0.1单点交叉，0.8基本位变异，0.1100（3）算法终止条件本实验中设定算法终止条件为满足以下两个条件之一：找到最优解，即适应度为100的解；达到最大进化代数，当程序进化满100代后，不管有没找到最优解都将退出。4.4 本章小结本章以三角形分类程序为例使用遗传算法进行测试用例的生成，是前几章内容的结晶。文中先对待测程序的流程和路径等进行了分析，然后对程序进行插桩，
28、并对相关参数进行了设定，然后展示了程序主要模块的代码，最后通过分析程序的运行结果，并和随机法作了比较，显示了遗传算法的优越性。第五章 总结与展望软件测试是软件工程中的重要环节，随着软件技术的发展和软件规模的扩大，软件测试日益凸显其重要性。而测试数据是软件测试的基础。传统的手工构建测试数据工作量大，浪费了大量的人力、物力资源，且测试效率低。因此测试用例的自动生成成为了国内外学者研究的热点。遗传算法作为一种优化的搜索算法，在软件测试中得到了广泛的应用和研究。本文作者通过对大量文献中测试用例生成方法和遗传算法的学习，将遗传算法应用到测试用例的生成上。文中首先介绍了软件测试及遗传算法的国内外研究现状，
29、然后介绍了软件测试和遗传算法的基本概念，接着提出了基于遗传算法生成测试用例的内含、框架及模型，最后以三角形分类程序为例验证了基于遗传生成测试用例的可行性。由于时间问题，本文还存在许多问题和不足，将作为进一步研究的主要内容和方向：第一，本文只用到了遗传算法，并没有将其它算法与之混合使用以改进性能。第二，本文中遗传算法所使用的适应度函数及遗传算子均采用的是比较简单且使用广泛的算法，并没有将这些算法做进一步的研究和改进。第三，本文最后实现的程序只是一个产生测试数据的原始工具模型，特别在用户界面方面还很欠缺，需要进一步完善。致谢语本学期的学习很快就要过去了，在本论文完成之际，我首先要感谢孙承福老师，孙
30、老师在我从论文选题至今给了我不少建议，使我受益良多，是我能顺利完成论文的关键所在。孙老师治学严谨，待人和蔼，使我以后工作、学习中为人处事的榜样。同时还要衷心感谢孙承福老师。孙老师在担任班导师期间时常给我们教授学习和工作的实际经验，使我对于日后的工作方向有了明确的定位，也将在我日后的工作中继续产生良好的作用。感谢我的家人以及所有在生活中、学习中帮助过我或给予过我良好启发的人。参考文献1 Ron Patton.软件测试(第二版)M.北京:机械工业出版社，2006:4-52赵晓华，计算机软件可靠性与质量管理M.北京:中国经济出版社,19923徐仁佐.软件可靠性工程M.清华大学出版社，2007.54王
31、小平，曹立明.遗传算法理论、应用与软件实现M.西安:西安交通大学出版社,2001.5许秀梅.基于退火免疫遗传算法的测试数据生成方法研究D.北京：北京交通大学，20076乐鑫喜.基于退火遗传算法的测试用例自动生成D.武汉：武汉理工大学, 20057律亚楠.基于遗传算法的测试数据生成研究D.汕头：汕头大学，20088钱肖英.基于遗传算法的测试数据自动生成方法的研究D.杭州：浙江工商大学，20089马志兵.基于遗传算法的测试数据自动生成技术研究D.青岛：青岛大学，200910顾鹏.基于遗传算法的测试用例产生系统关键技术研究D.武汉：华中科技大学，200611陈雨.基于遗传算法的测试用例生成D.上海：
32、东华大学，200912林惠娟.基于遗传算法的测试用例自动生成技术研究D.成都：四川大学，200613 D.Bird and C.Munoz. Automatic generation of random self-checking test casesJ. IBM System J. vol.22, NO.3. 1983:229-24514 P.D.Coward. Symbolic execution and testingJ. Information and Software Teehnology. 1991, 2: 53-6415 C.V.Ramamoorthy, S. Ho. And W.Chen. On the automated generation of Program test dataJ. IEEE Trans. Software Eng. Vol.SE 2, NO.1. 1981 : 117-127
