1、2.2 软件测试的难点112.3 算法122.3.1 算法的思想及流程122.3.2 算法的特点142.4本章小结15第三章 基于算法的测试用例生成163.1基于算法的测试用例生成基本内涵163.1.1 软件测试用例的基本内涵163.1.2 基于算法的测试用例生成的基本内涵173.2 基于算法的测试用例生成框架173.3 基于算法的测试用例生成算法实现193.3.1 编码策略193.3.2 适应度函数及程序插桩203.3.3 策略213.3.4 参数控制233.4 本章小结23第四章 实验及结果分析244.1 待测程序分析244.1.1 待测程序引入244.1.2 程序流程分析244.1.3
2、路径分析254.2 程序插桩254.3 参数设定及程序实现264.3.1 参数设定264.3.2 部分程序实现264.4 结果分析294.5 本章小结31第五章 总结与展望32致谢语33参考文献34第一章 绪论1.1 问题的提出在信息化普及的今天，计算机在人们的生活和工作中占据着重要地位，使人们的工作效率提高，也使生活更丰富多彩。而作为计算机的重要组成部分，软件的重要性不言而喻。随着计算机技术的日益发展，计算机软件的规模越来越庞大，复杂性越来越高，这就为软件质量的保证带来了困难。因为软件的开发过程大部分是由人的智力活动构成，不可能完美无缺。而软件缺陷如果不能及时发现，带来的损失可能是巨大的，有
3、的甚至会危及人的生命。在历史上臭名昭著的软件缺陷案例有1：1999年12月3日，美国航天局的火星基地登陆飞船在试图登陆火星表面时失踪，原因仅仅是一个数据位的意外更改；美国爱国者导弹防御系统曾在几次对抗导弹战役中失利，其中一次竟然误使28名美国士兵丧生，原因是一个很小的系统时钟错误导致系统累计拖延了100多个小时使跟踪系统失去准确度；还有就是大名鼎鼎的“千年虫”问题，起因是在20世纪70年代，为了节省硬盘空间，美国某位程序员在编写工资系统时将4位数日期（如1975）改成了2位数日期（如75），该缺陷一直拖到1995年都没有修复，最终给全球带来了高达数亿美元的损失等等。作为提高软件质量的重要手段，
4、软件测试越来越受到重视。在美国的微软公司，测试人员和开发人员的比例达到了2：12。软件测试伴随着整个开发过程，是一个非常复杂的过程，其消耗的人力和资金一般占整个项目的一半左右。而在某些特别重要的软件开发过程中，为保证软件的质量，测试的费用甚至是其它各阶段之和的3到5倍3。测试过程中，测试人员通常需要分析、设计和执行大量的测试用例，从而耗费了大量资源，因此找出合理的测试用例生成方法可以有效缩短测试时间，减少损耗，一般可以有效降低整个项目的4%费用4。然而，目前生成测试用例的方法主要是向前核查法和逆向回溯法，测试人员根据自己的项目经验手工为指定的程序路径生成测试数据5。向前核查法是指沿预期的路径向
5、前检查，确定到每一个判断点时变量所能提供的最宽数值区间，然后继续前行，从而将多个变量的可能取值范围逐渐缩小，到达程序出口后，就能找到覆盖这条路径所需的输入数据。逆向回溯法正好相反，是指从期望执行的程序位置出发，逆向回溯，在每个判断点处逐渐调整各变量取值，直到退到程序入口，即获得所需的输入数据。向前核查法和逆向回溯法的局限性是，对某些条件要求苛刻的路径使用时非常困难，同时由于大多数程序中包含的路径数非常多，如果按每条路径手工测试，显然带来的工作量是非常巨大的。由于测试的工作量大、测试过程的重复性高等特点，自动化测试正逐渐得到广泛的应用。很多测试工具的使用大大提高了测试人员的工作效率，有效减少了项
6、目开支。然而这些工具主要为测试的执行、管理和度量工具，在测试用例自动生成方面还不完善。而在软件测试过程中，动态测试作为测试的重要环节占了很大比例，动态测试的关键正是测试用例的生成问题。因此，寻找一种有效的测试用例生成方法是提高测试自动化的重中之重。1.2 国内外研究现状自上世纪60年代起，国内外的学者专家对测试用例的自动生成提出了很多方法，应用较为广泛的有随机法、静态法、动态法以及试探法5 6 7 8 9 10 11 12。D.Bird13等提出了采用随机法生成测试用例，其思想是不受限制地随机产生大量的测试用例。该方法产生测试用例的成本很低，在某些抽样测试中效果较好，但是该方法的针对性较弱，在
7、输入空间为无穷大时产生的测试用例集非常庞大，测试效率低，现在的很多工具都是采用的该方法。静态法的典型代表是符号执行法，由P.D.Coward14和C.Ramanmoorthy 15 16等人提出。该方法的主要思想是把符号值作为程序输入，静态“执行”指定路径的语句，从而得到变量的值。这里所谓的执行，是指按照程序执行的顺序将相应的变量用符号表达式代换。该方法的缺点为需要进行复杂的代数运算，难以处理依赖于输入变量的循环条件、数组元素下标和模块调用的情况，特别对于动态的面向对象程序不适合使用。与静态法相对应的是动态法，该方法的基本思想是从输入空间中任取一个假设解作为初始输入，通过实际运行程序不断调整输
8、入，使得程序实际执行路径向指定路径不断逼近，直到与指定路径完全一致。Korel17法是动态法的典型代表：其采用的是步进的方式执行程序，即一次只前进一个分支谓词；Korel还提出了“谓词函数”的概念，用来度量分支谓词的接近满足程度。然而，由于Korel法一次只考虑一个分支谓词，使用回溯技术，所以要进行大量的迭代，浪费了大量的资源。而且由于对于非线性路径约束，该方法只能找到局部极小值，当谓词函数有多个局部极小值时显然将难以找到目标路径的解。除此之外，动态法还包括程序插装的方法和迭代松弛法，M.Gallagher和Neelam Guptal18分别对这两种方法进行了全面的阐述。第四种算法是试探法，该
9、方法的基本思想是从输入数据空间中选择输入数据，运行程序，将运行结果结合概率论的思想产生新的数据继续进行试探。其受搜索空间限制条件的约束小，且不需要其它辅助性信息，对于很多高复杂度问题（如大空间、多峰、非线性、全局优化等）具有独特的优势和高效性。试探法主要包括算法、模拟退火算法、禁忌搜索算法、混合策略的算法等。自20世纪90年代起，算法因其独特的优点而开始被广泛的用于测试用例的生成领域，并取得了良好的研究成果。算法模拟生物学中的变异原理，采用编码技术将待求数据映射到基因空间，并通过选择、交叉、变异等操作和优胜劣汰的自然选择确定搜索方向，从而找到最优解。实验证明，该算法具有隐性并行性和全局寻优能力
10、，可以自动获取搜索过程中的有关信息并用于指导优化。Jones 等人19的实验表明，为使三角形分类等程序达到分支覆盖，算法生成的测试数据比随机法小一到两个数量级。Jin-Cherng Lin等人 20 等人对适应度函数进行了研究，提出了使用广义海明距离来构建适应度函数。荚伟21分析了算法在测试用例产生这一问题上的可行性，提出了要有效解决该问题，必须从以下几个角度进行研究：参数的编码方法、适应度函数的构造、算子的设计以及算法参数的选择等。Berndt等人 22将输入空间划分成多个区间，根据待选输入的多种特性创建了一个最小化函数,使用简单算法进行求解,并使用了求解过程中的化石记录来指导求解过程。景志
11、远23则从数学的角度分析了将MGA和K均值等改进的算法应用于测试用例的自动生成。蔡立志等人24提出了一种基于算法的成对测试生成方法,该方法用于选择当前局部优化覆盖的测试用例，以此构建满足成对测试基准的测试用例套，有效降低了相同覆盖率下的测试用例数量。陈雨等人25将自适应算子和禁忌搜索思想融入到算法中， 充分发挥算法的全局搜索和禁忌搜索算法局部搜索优势, 提高了测试数据的生成能力。全君林等人26提出了一种应用于软件回归测试过程中的基于算法的最小化测试用例集算法模型，该算法较一般的优化算法具有更高算法性能与效率。1.3 论文研究内容本文主要做了以下方面的研究：（1）广泛阅读了国内外相关文献资料，对
12、软件测试和算法的应用现状进行了概述，认为使用算法进行测试用例生成可行。（2）分析了使用算法进行测试用例生成的基本内涵，提出了算法框架及对算法进行实现的具体策略。（3）以三角形分类程序为例进行试验，分析了试验结果，证实了算法的优越性。第二章 软件测试及算法基本概念2.1 软件测试基本概念2.1.1 软件测试的目的1983年IEEE在“软件工程标准术语”中将软件测试定义为：“使用人工或自动手段来运行或测定某个软件系统的过程，其目的在于检验该被测软件是否满足规定的需求或是衡量预期结果和实际结果之间的差别。”定义中指出软件测试的目的是“检验该被测软件是否满足规定的需求或是衡量预期结果和实际结果之间的差
13、别”Grenford. J. Myers在其著作The Art Of Software Testing中提出了与软件测试相关的三个重要观点，指明了软件测试的目的为：软件测试是程序的执行过程，目的在于发现错误；一个好的测试用例是指很可能找到迄今为止尚未发现的错误的用例;一个成功的测试是指发现了迄今为止尚未发现的错误的测试。由此可见，软件测试的目的可以概括为：首先，软件测试要以最少的人力、物力，尽快找出软件中潜在的各种缺陷，通过修正这些缺陷，提高软件产品质量，尽量减少软件产品发布后由潜在的软件缺陷带来的可能的商业风险。其次，通过分析软件缺陷产生的原因，可以帮助发现当前开发开发过程中的软件过程缺陷，
14、以便进行软件过程的改进。同时，通过对测试结果的分析整理，还可以修正软件开发规则，并为软件可靠性分析提供依据。2.1.2 软件测试的原则软件测试作为一门独立的计算机软件技术，在执行过程中必须遵守一定的原则，以保证测试效果。软件测试的专家们经过长期的实践，总结出了软件测试的原则应如下：应把“尽早和不断地进行软件测试”作为软件开发者的座右铭。实践证明单元测试能够尽早发现问题,减少后期测试的错误量。单元测试过程中可以使用相应白盒测试工具（如Junit，Jtest等）进行辅助测试，以提高测试效率。测试用例应由测试输入数据、测试执行步骤和与之对应的预期输出结果三部分组成。应当避免由程序员检查自己的程序。特
15、别在后期的性能测试及系统测试中，应避免程序员测试自己的程序。这其中除了某些心理因素外，该原则还可避免由于程序员个人的惯性思维而导致的某些理解错误。测试用例的设计要确保能覆盖所有可能路径。在设计测试用例时，应当包括合理的输入条件和不合理的输入条件。不合理的输入条件是指异常的、临界的、可能引起问题的输入条件。充分注意测试中的群集现象。经验表明，测试后程序残存的错误数目与该程序中已发现的错误数目或检错率成正比。应该对错误群集的程序段进行重点测试。严格执行测试计划，排除测试的随意性。软件测试是有组织、有计划、有步骤的活动。测试计划应包括：所测软件的功能，输入和输出，测试内容，各项测试的进度安排，资源要
16、求，测试资料，测试工具，测试用例的选择，测试的控制方法和过程，系统的配置方式，跟踪规则，调试规则，以及回归测试的规定等等以及评价标准。应当对每一个测试结果做全面的检查。妥善保存测试计划，测试用例，出错统计和最终分析报告，为维护提供方便。2.2 软件测试的难点（1）测试用例设计测试用例及测试例程是其设计者对被测对象实现原理和外部需求的理解，能否正确反映对被测对象的质量要求，很大程度上取决于其设计者的分析、理解和设计能力。这是一种缺乏指导性方法的、不易制订标准或规范的、需要“技巧”的设计活动。（2）测试管理目前缺乏测试管理方面的资料，几乎没有可供参考的、已实现的、完整的测试管理与测试实施模式。（3
17、）测试的组织软件测试的有效实施需要开发组织与测试组织充分配合。虽然测试活动看似是对开发人员劳动成果的不断“挑剔”，但测试工作的出发点是：确保开发人员的劳动成果成为可被接收的、更高品质的软件产品。因此，测试人员应向开发人员谦虚求教，在测试工作中真正发挥作用，为保证软件产品的高质量起尽可能大的作用。测试的组织者应在促进上级组织协调各组织工作方面发挥作用。（4）测试的估计有效的测试工作需要投入足够的人力和物力，需要对工作的难度和消耗有充分的估计。测试的组织者也应在促进上级组织对资源的统一调度方面发挥作用。2.3 算法2.3.1 算法的思想及流程算法（genetic algorithm）是模拟达尔文的
18、选择和自然淘汰的生物进化过程的计算模型。该算法最先于1975年由美国的J.Holland教授提出。其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。算法作为一种不依赖具体问题的直接搜索方法受到广泛关注，它是现代有关智能计算的关键技术之一。算法的思想源于生物学和适者生存的自然选择规律，因此是具有“生存+检测”的迭代过程的搜索算法。它以一个群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。算法将问题的解空间映射为空间，对
19、解空间进行编码，即将每个可能的解用一串二进制或十进制数字串表示，称为一个染色体，解的每个分量称为一个基因。算法开始时先随机给出一群染色体，即候选解，由预先设定的某个评价指标计算每个染色体的适应值，将适应度低的染色体淘汰掉，而保留适应度高的优良染色体，然后对这些染色体进行选择复制、交叉和变异等操作，从而产生新的一代染色体群体。这样一代一代的“进化”，直至找到算法的最优解，即适应值满足条件的解。由于算法产生的“后代”是由优秀的“父代”和“母代”产生的，因此继承了上代的优良性态而优于上代，从而使算法向着最优解的方向进行，直到满足预先设定的条件。算法过程包括了编码、产生初始群体、计算适应值、选择、交叉
20、、变异等操作。其一般流程图如图2-1所示：j:=0选择变异个体执行变异将变异结果添加到新群体中=j+1j=PmM？YN执行交换根据适应度选择两个交换个体将交换后的两个新个体添加到新群体中j=PcM？复制个体执行复制将复制结果添加到新群体中j=PsM？开始Gen:自左向右执行一次遗传算子计算群体中各个体适应度终止输出结果随机产生M个初始群体确定字符串长度L满足终止条件？PsPcPm=Gen+1图2-1 算法流程图2.3.2 算法的特点算法是一类可用于复杂系统优化计算的搜索算法，与其他一些优化算法相比，它的主要特点有如下几点27：（1）算法以决策变量的编码作为运算对象，而传统优化算法往往直接利用变
21、量的实际值来进行优化计算。这种对决策变量的编码处理方式，使得我们在优化计算过程中可以借鉴生物学中染色体和基因等概念以及和进化机理。特别是对些无数值概念或很难有数值概念，而只有代码概念的优化问题，编码处理方式更显示出了其独待的优越性。（2）算法直接以目标函数值作为搜索信息，而不需要目标函数的导数值等其他辅助信息。这个特性对很多目标函数难以求导的优化问题，以及组合优化问题等，应用算法时就显得比较方便。而且，直接利用目标函数值或个体适应度，也可使得我们可以把搜索范围集中到适应度较高的部分搜索空间中，从而提高了搜索效率。（3）算法同时使用多个搜索点的搜索信息，而传统的优化算法往往是从解空间中的一个初始
22、点开始最优解的迭代搜索过程。单个搜索点的搜索效率不高，甚至可能使搜索过程陷于局部最优解而停滞不前。算法通过对个体组成的群体进行操作运算，产生新的群体，其中包含的群体信息可以避免搜索一些不必搜索的点，所以实际上相当于搜索了更多的点，这是算法所特有的一种隐性并行性。（4）算法使用概率搜索技术，而很多传统的优化算法往往使用的是确定性的搜索方法。确定性的方法由于固定了点与点之间的转移方法和转移关系，往往可能使得搜索永远达不到最优点，因而也限制了算法的应用范围。而算法属于一种自适应的概率搜索技术，其选择、交叉、变异等运算都是以一种概率的方式来进行的，从而增加了算法搜索过程的灵活性和搜索效率。2.4本章小
23、结本章首先介绍了软件测试的一些基本概念，对软件测试的知识做了系统的介绍，包括软件测试的目的、原则、过程，介绍了了软件测试的主要技术难点，其中包括了测试用例的设计。本章后半部分介绍了算法的基本概念，包括算法的思想、流程及特点。第三章 基于算法的测试用例生成3.1基于算法的测试用例生成基本内涵3.1.1 软件测试用例的基本内涵测试用例是为某个特殊目标而编制的一组测试输入、执行条件以及预期结果，以便测试某个程序路径或核实是否满足某个特定需求，包含输入和输出两部分。构造测试用例的目的是为了检查被测软件的操作结果是否与预期的需求相吻合，确定应用程序的某些特性是否正常的工作等。测试用例的质量可以用以下四个
24、标准来描述:（1）有效性:是否能够发现缺陷，或者至少可能发现缺陷；（2）仿效性:可仿效的测试用例能够测试多项内容，从而减少测试用例的数量；（3）经济性:测试用例的执行、分析和调试是否经济；（4）修改性:软件修改后测试用例的维护成本。实践中，设计测试用例需遵守一定的原则，这些原则主要有：（1）全面性包括：应尽可能覆盖程序的各种路径；应考虑存在跨年、跨月的数据；大量数据并发测试的准备等。 （2）正确性输入界面后的数据应与测试文档所记录的数据一致且预期结果应与测试数据发生的业务吻合。（3）符合正常业务惯例测试数据应符合用户实际工作业务流程且兼顾各种业务变化的可能。（4）仿真性 人名、地名、电话号码等应具有模拟功能，符合一般的命名惯例；不允许出现与知名人士、小说中人物名等雷同情况。（5）可操作性 测试用例中应写清测试的操作步骤，不同的操作步骤相对应的操作结果。3.1.2 基于算法的测试用例生成的基本内涵使用算法实现测试用例的自动生成可描述为12：应用算法来求解一组优化的测试用例。在每一步进化计算过程中，测试用例自动生成器使用当前群体（测试用例）驱动被测试程序的执行，每一个测试用例的执行路径被跟踪
