2023年蚁群搜索算法在集合覆盖问题中的应用研究.doc

基于遗传算法的测试用例生成方法 软件测试是保证软件质量和可靠性重要手段，在这方面发挥着其它方法不可替代的作用。然而，软件测试是一个复杂的过程，需要消耗巨大的人力、物力和时间，约占整个软件开发本钱的40%～50%。因此，提高软件测试工具的自动化程度对于确保软件开发质量、降低软件开发本钱非常重要。而提高测试用例生成的自动化程度又是提高测试工具乃至整个测试过程自动化程度的关键所在，本文主要针对这一问题进行了研究和设计。 本文在分析软件测试和算法根本概念的根底上，提出软件测试用例的设计是软件测试的难点之一。论文提出了基于算法的测试用例生成的内含是应用算法来求解一组优化的测试用例，其框架包括了测试环境构造、算法及测试运行环境三局部，论文给出了基于算法的测试用例生成的模型。最后以三角形分类程序为例应用算法进行测试用例生成的模拟，结果显示，应用算法进行测试用例生成可行。 关键词：软件测试 测试用例 算法 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 ABSTRACT 3 目录 4 第一章 绪论 6 1.1 问题的提出 6 1.2 国内外研究现状 7 1.3 论文研究内容 9 第二章 软件测试及算法根本概念 10 2.1 软件测试根本概念 10 2.1.1 软件测试的目的 10 2.1.2 软件测试的原那么 10 2.2 软件测试的难点 11 2.3 算法 12 2.3.1 算法的思想及流程 12 2.3.2 算法的特点 14 2.4本章小结 15 第三章 基于算法的测试用例生成 16 3.1基于算法的测试用例生成根本内涵 16 3.1.1 软件测试用例的根本内涵 16 3.1.2 基于算法的测试用例生成的根本内涵 17 3.2 基于算法的测试用例生成框架 17 3.3 基于算法的测试用例生成算法实现 19 3.3.1 编码策略 19 3.3.2 适应度函数及程序插桩 20 3.3.3 策略 21 3.3.4 参数控制 23 3.4 本章小结 23 第四章 实验及结果分析 24 4.1 待测程序分析 24 4.1.1 待测程序引入 24 4.1.2 程序流程分析 24 4.1.3 路径分析 25 4.2 程序插桩 25 4.3 参数设定及程序实现 26 4.3.1 参数设定 26 4.3.2 局部程序实现 26 4.4 结果分析 29 4.5 本章小结 31 第五章 总结与展望 32 致谢语 33 参考文献 34 第一章 绪论 1.1 问题的提出 在信息化普及的今天，计算机在人们的生活和工作中占据着重要地位，使人们的工作效率提高，也使生活更丰富多彩。而作为计算机的重要组成局部，软件的重要性不言而喻。随着计算机技术的日益开展，计算机软件的规模越来越庞大，复杂性越来越高，这就为软件质量的保证带来了困难。因为软件的开发过程大局部是由人的智力活动构成，不可能完美无缺。而软件缺陷如果不能及时发现，带来的损失可能是巨大的，有的甚至会危及人的生命。在历史上臭名昭著的软件缺陷案例有[1]：1999年12月3日，美国航天局的火星基地登陆飞船在试图登陆火星外表时失踪，原因仅仅是一个数据位的意外更改；美国爱国者导弹防御系统曾在几次对抗导弹战役中失利，其中一次竟然误使28名美国士兵丧生，原因是一个很小的系统时钟错误导致系统累计拖延了100多个小时使跟踪系统失去准确度；还有就是大名鼎鼎的“千年虫〞问题，起因是在20世纪70年代，为了节省硬盘空间，美国某位程序员在编写工资系统时将4位数日期〔如1975〕改成了2位数日期〔如75〕，该缺陷一直拖到1995年都没有修复，最终给全球带来了高达数亿美元的损失等等。 作为提高软件质量的重要手段，软件测试越来越受到重视。在美国的微软公司，测试人员和开发人员的比例到达了2：1[2]。软件测试伴随着整个开发过程，是一个非常复杂的过程，其消耗的人力和资金一般占整个项目的一半左右。而在某些特别重要的软件开发过程中，为保证软件的质量，测试的费用甚至是其它各阶段之和的3到5倍[3]。测试过程中，测试人员通常需要分析、设计和执行大量的测试用例，从而消耗了大量资源，因此找出合理的测试用例生成方法可以有效缩短测试时间，减少损耗，一般可以有效降低整个项目的4%费用[4]。 然而，目前生成测试用例的方法主要是向前核查法和逆向回溯法，测试人员根据自己的项目经验手工为指定的程序路径生成测试数据[5]。向前核查法是指沿预期的路径向前检查，确定到每一个判断点时变量所能提供的最宽数值区间，然后继续前行，从而将多个变量的可能取值范围逐渐缩小，到达程序出口后，就能找到覆盖这条路径所需的输入数据。逆向回溯法正好相反，是指从期望执行的程序位置出发，逆向回溯，在每个判断点处逐渐调整各变量取值，直到退到程序入口，即获得所需的输入数据。向前核查法和逆向回溯法的局限性是，对某些条件要求苛刻的路径使用时非常困难，同时由于大多数程序中包含的路径数非常多，如果按每条路径手工测试，显然带来的工作量是非常巨大的。 由于测试的工作量大、测试过程的重复性高等特点，自动化测试正逐渐得到广泛的应用。很多测试工具的使用大大提高了测试人员的工作效率，有效减少了项目开支。然而这些工具主要为测试的执行、管理和度量工具，在测试用例自动生成方面还不完善。而在软件测试过程中，动态测试作为测试的重要环节占了很大比例，动态测试的关键正是测试用例的生成问题。因此，寻找一种有效的测试用例生成方法是提高测试自动化的重中之重。 1.2 国内外研究现状 自上世纪60年代起，国内外的学者专家对测试用例的自动生成提出了很多方法，应用较为广泛的有随机法、静态法、动态法以及试探法[5] [6] [7] [8] [9] [10] [11] [12]。 D.Bird[13]等提出了采用随机法生成测试用例，其思想是不受限制地随机产生大量的测试用例。该方法产生测试用例的本钱很低，在某些抽样测试中效果较好，但是该方法的针对性较弱，在输入空间为无穷大时产生的测试用例集非常庞大，测试效率低，现在的很多工具都是采用的该方法。 静态法的典型代表是符号执行法，由P.D.Coward[14]和C.Ramanmoorthy [15] [16]等人提出。该方法的主要思想是把符号值作为程序输入，静态“执行〞指定路径的语句，从而得到变量的值。这里所谓的执行，是指按照程序执行的顺序将相应的变量用符号表达式代换。该方法的缺点为需要进行复杂的代数运算，难以处理依赖于输入变量的循环条件、数组元素下标和模块调用的情况，特别对于动态的面向对象程序不适合使用。 与静态法相对应的是动态法，该方法的根本思想是从输入空间中任取一个假设解作为初始输入，通过实际运行程序不断调整输入，使得程序实际执行路径向指定路径不断逼近，直到与指定路径完全一致。Korel[17]法是动态法的典型代表：其采用的是步进的方式执行程序，即一次只前进一个分支谓词；Korel还提出了“谓词函数〞的概念，用来度量分支谓词的接近满足程度。然而，由于Korel法一次只考虑一个分支谓词，使用回溯技术，所以要进行大量的迭代，浪费了大量的资源。而且由于对于非线性路径约束，该方法只能找到局部极小值，当谓词函数有多个局部极小值时显然将难以找到目标路径的解。除此之外，动态法还包括程序插装的方法和迭代松弛法，M.Gallagher和Neelam Guptal[18]分别对这两种方法进行了全面的阐述。 第四种算法是试探法，该方法的根本思想是从输入数据空间中选择输入数据，运行程序，将运行结果结合概率论的思想产生新的数据继续进行试探。其受搜索空间限制条件的约束小，且不需要其它辅助性信息，对于很多高复杂度问题〔如大空间、多峰、非线性、全局优化等〕具有独特的优势和高效性。试探法主要包括算法、模拟退火算法、禁忌搜索算法、混合策略的算法等。 自20世纪90年代起，算法因其独特的优点而开始被广泛的用于测试用例的生成领域，并取得了良好的研究成果。算法模拟生物学中的变异原理，采用编码技术将待求数据映射到基因空间，并通过选择、交叉、变异等操作和优胜劣汰的自然选择确定搜索方向，从而找到最优解。实验证明，该算法具有隐性并行性和全局寻优能力，可以自