（计算机应用技术专业论文）遗传算法在路径覆盖测试数据生成中的研究与应用.pdf

上海师范大学硕士研究生学位论文遗传算法在路径覆盖测试数据生成中的研究与应用 摘要 随着软件技术的发展和软件项目规模的不断扩大，软件测试的作用越来越重 要。在软件测试中，测试数据的选择是进行结构测试的一个难题，测试数据合适 与否直接关系到错误能否被预期测出。对于测试数据自动化生成方法，目前虽然 有一些方法被提出并使用，但由于其局限性，在实际中还没有完善的解决方法， 只能凭借工程经验判断。在此背景下，本文使用遗传算法进行了对测试数据自动 生成方法的研究。 本文首先介绍了软件测试技术和遗传算法。对于软件测试技术，介绍了软件 测试的概念、分类、阶段划分及测试用例的选择方法，并着重介绍了现有的各种 面向路径覆盖的测试数据生成方法。对于遗传算法，介绍了它的产生发展、基本 概念、特点和基本术语，阐述了遗传算法的一般过程，分析了影响遗传算法的重 要因素。 接着，文章提出了遗传算法在测试数据生成中的应用方法。首先分析了使用 遗传算法生成测试数据的理论依据，指出了应用遗传算法的可行性。其次研究了 使用遗传算法生成测试数据所要考虑的若干问题，特别在路径表示和选择、适应 度函数设计和程序插装方式上，根据实际应用的需要作出了改进，提出了适用于 实际的应用算法。最后用一个简单的实例说明了使用遗传算法生成基本数据类型 测试数据的过程。 本文详细研究了在面向对象程序中遗传算法生成测试数据的一个难点：类对 象测试数据的生成。首先设计了一种新的类对象编码方法，使其能够适合于遗传 操作。其次分析研究了广义海明距离法，在此基础上提出了适用于本系统的类对 象生成适应度函数，并用一个简单的实例说明了使用遗传算法生成类对象测试数 据的过程。 最后，本文将该方法应用于交通银行数据大集中项目个贷子系统的单元测试 中，创建了个工具模型，使其根据需要自动生成测试数据，最后给出实验结果 和结果分析与比较。实验证明，使用遗传算法进行面向路径覆盖的测试数据生成 方法，是灵活、有效、具有一定实用价值的。 关键词：测试用例生成，遗传算法，面向路径覆盖的测试，适应度函数 上海师范大学硕士研究生学位论文 遗传算法在路径覆盖测试数据生成中的研究与应用 a b s t r a c t w i t ht h ed e v e l o p m e n to fs o f t w a r et e c h n o l o g ya n d t h ei n c r e a s e m e n to fs o f t w a r e p r o j e c ts c a l e ，t h ee f f e c to fs o f t w a r et e s t i n gb e c o m e sm o r ea n dm o r ei m p o r t a n t i n t e s t i n g ，t h es e l e c t i o no ft e s td a t ai san o d u st os t r u c t u r et e s t i n g w h e t h e rt h e e r r o r so fp r o g r a m sc a nb ed e t e c t e do rn o t & r ed i r e c t l yr e l a t e dt ow h e t h e rt h et e s t d a t aisr i g h to rn o t a l t h o u g hs o m em e t h o d sa r eb r o u g h to u tt oa u t o m a t i c a l l yg e n e r a t e t e s td a t a ，i nt h ep r a c t i c a la p p l i c a t i o nt h e r ea r en op e r f e c ts o l u t i o n sb e c a u s eo f t h e i rl o c a l i z a t i o n s t h et e s td a t ac a nb eg a i n e do n l yb yt h ee x p e r i e n c e s t h i sp a p e r f o c u s e so nt h em e t h o do fa u t o m a t i c a l l yg e n e r a t et e s td a t au s i n gg e n e t i ca l g o r i t h m s ( g a ) i np a t hc o v e r a g et e s t i n g a t t h eb e g i n n i n g ，t h isp a p e ri n t r o d u c e st h es o f t w a r et e s t i n gt e c h n o l o g ya n d g e n e t i ca l g o r i t h m s ( g a ) o nt h es o f t w a r et e s t i n gt e c h n o l o g y ，w ei n t r o d u c et h e c o n c e p t s ，c l a s s e sa n dp h a s e s ，i n v e s t i g a t e st h em e t h o d so fs e l e c t i n gp r o p e rt e s td a t a ， a n de m p h a s i z e so nt h ev a t i o u so ft h em e t h o d sw h i c hu s ep a t hc o v e r a g et e s t i n g o n t h eg a w ei n t r o d u c et h eg e n e r a t i o n 、d e v e l o p m e n t 、b a s i cc o n c e p t 、f e a t u r ea n db a s i c g l o s s a r y ，e x p a t i a t e st h eg e n e r a lp r o c e s so fg a ，a n a l y s et h ei m p o r t a n tf a c t o r sw h i c h e f f e c tg a s e c o n d l y ，t h ep a p e rp r o p o s e st h ea p p l i e a t i o nm e t h o do fg au s e di nt e s td a t a g e n e r a t i o n w ea n a l y s et h ea c a d e m i cg i s to ft e s td a t ag e n e r a t i o nu s i n gg aa n dt h e p o s s i b i l i t yo fu s i n gg a t h e nw ed i s c u s ss o m ep r o b l e m sn e e d e dt ob ec o n s i d e r e du s i n g g ag e n e r a t et e s td a t ai np a t hc o v e r a g et e s t i n g ，e s p e c i a l l yo nt h ep r o b l e mo fa n a l y s i s a n de x p r e s s i o n so fp a t h s ，t h ed e s i g nm e t h o do ff i t n e s sf u n c ti o n ，a n dt h em e t h o do f p r o g r a mi n s t r u m e n t i o n ，w ei m p r o v eo nt h e ma c c o r d i n gt ot h ep r a c t i c a lr e q u i r e m e n t s a tl a s tw eu s eas i m p l ee x a m p l et os h o wt h ep r o c e s so ft e s td a t ao fb a s i ct y p e g e n e r a t i o nw i t hg a t h ep a p e rd e e p l yi n v e s t i g a t e sad i f f i c u l tp r o b l e mi nt e s td a t ag e n e r a t i o nw i t h g a t h eg e n e r a t i o no fc l a s s o b j e c tt e s td a t a f i r s tw ei n t r o d u c ean e wm e t h o do f c o d i n gc l a s s o b j e c tt om a k ei ts u i t a b l ef o rg e n e t i co p e r a t i o n s t h e nw ea n a l y s et h e e x t e n d e dh a r m m i n gd i s t a n c e ( e 皿) ，a n dp r o p o s e st h ef i t n e s sf u n c t i o nf o rc l a s s - o b j e c t g e n e r a ti o nb a s e do ne i d a tl a s tw eu s e as i m p l ee x a m p l et os h o wt h ep r o c e s so f c l a s s o b j e c tt e s td a t ag e n e r a t i o nw i t hg u l a s t l y ，t h ep a p e ru s e st h em e t h o di nt h ep e r s o n a ll o a ns u b s y s t e mo fb a n ko f c o m m u n i c t i o ni nt h eu n i tt e s tp h a s e w ec r e a t eat o o lm o d e lt oa u t o m a t i c a l l yg e n e r a t e t e a td a t aa c c o r d i n gt ot h er e q u i r e m e n ta n dg i v eo u tt h ee x p e r i m e n tr e s u l t w ea n a l y s e t h er e s u l t sa n dc o m p a r et h e m t h er e s u l t sp r o v et h a tt h em e t h o do fg e n e r a t i n gt e s t d a t ai np a t hc o v e r a g et e s t i n gu s i n gg ai sa g i l i t y ，e f f i c i e n t t h em e t h o dh a ss o m e p r a c t i c a lv a l u e sa n di sv a l u a b l et ob ei n v e s t i g a t e df u r t h e r k e y t o r d s ：t e s td a t ag e n e r a t i o n g e n e t i ca l o g r i t h m s ( g a ) ，p a t hc o v e r a g et e s t i n g ， f i t n e s sf u n c t i o n 2 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或机构已经发表或撰写过的研究 成果。其他同志对本研究的启发和所做的贡献均已在论文中做了明确的声明并表 示了谢意。 作者签名；翟埠日期2 彩，腰 论文使用授权声明 本人完全了解上海师范大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其它手段保存论文。保密的论文在解密后遵守此 规定。 作者签名l 礁哞导师等名 日期：j 叼矗j g 上海师范大学硕士研究生学位论文遗传算法在路径覆盖测试数据生成中的研究与应用 1 。1 论文研究背景 第一章绪言 随着计算机科学技术的飞速发展，作为计算机的灵魂，软件起着举足轻重的 作用，软件的失效可能造成巨大的经济损失甚至危及生命安全。人们对软件测试 重要性的认识越来越深刻，软件测试阶段在整个软件开发周期中所占的比重日益 增大。对于某些性命攸关的软件，其测试费用甚至高达所有其它软件工程阶段费 用总和的3 到5 倍。美国微软公司软件测试人员与开发人员的比例为2 比l “1 。 现有的软件测试技术，从是否需要被执行被测试软件的角度通常分为静态测 试和动态测试“。静态测试是不执行程序代码而寻找程序代码中可篚存在的错误 或评估程序代码的过程。动态测试通过在抽样测试数据上运行程序来检验程序的 动态行为和运行结果以发现错误。动态测试包括三部分核心内容：生成测试用例、 运行程序和验证程序的运行结果。动态测试最重要的问题是生成测试用例的策 略。测试用例包括输入数据、功能和预期结果。一般说到测试用例生成时，由于 预期结果构造的困难性，都侧重或仅生成输入数据，并称之为测试数据。 目前，测试人员一般采用手工方法设计测试数据。测试数据的自动生成将有 效地减轻测试人员的劳动强度，节省软件开发的成本。根据估算，对于一个典型 的大型软件项目，若能自动生成测试数据，则能节省接个软件开发费用的4 ”1 。 目前在测试数据自动化生成领域中，较为常见的是符号执行法、根据需求规 约产生随机数法“3 、k o r c ! 法等。符号执行法是静态的撄4 试数撂生成方法，对于 动态的面向对象程序不适合使用；按需求规约产生随机数法属于动态方法，在采 用测试用例抽样测试时，这种方法对产生测试数据非常有效，但在约束要求较高 的测试方法中，比如分支覆盖或路径覆盖，它的效率非常低下，很难产生符合要 求的解集；k o r c l 法属于面向路径覆盖的动态测试数据生成法，它根据程序动态 运行时的分支函数的信息，不断调整对当前分支函数有影响的输入变量的值，使 分支函数最小化。但缺点是如果初始数据选得不好，容易陷入不一定能执行期望 路径的局部最优解。此外，在进行测试数据生成时，它们还存在一些共同的不足： 1 不能对大规模程序进行测试数据生成； 2 对生成测试数据的程序限制较多，如不能有库函数，不能有函数调用等； 3 面向对象的程序测试数据生成困难等。 遗传算法采用编码技术，将输入数据域d 映射到基因空间g ，并通过选择、 交叉、变异等遗传操作和优胜劣汰的自然选择确定搜索方法。由于它采用种群方 式组织搜索，因此可以同时搜索g 内多个区域。交叉和变异操作为种群引入新 的信息，更有利于找到全局最优解，避免了以往算法容易陷入局部最优解的问题。 上海师范大学硕士研究生学位论文遗传算法在路径覆盖测试数据生成中的研究与应用 目前，遗传算法应用于测试数据生成的研究主要是集中在如何生成面向目标 覆盖的测试数据问题上。“，而对于面向路径覆盖的测试数据的生成方法，国 内外研究甚少。j i n c h e m gl i n “”等对适应度函数进行了研究，提出了使用广义 海明距离构建适应度函数，但是文中对该适应度函数能否用于类对象生成，没有 分析讨论；w i l l e mv i s s e r 。”等研究了在面向路径时所需要考虑的路径选择问题， 但是研究的问题比较简单，不能用于复杂逻辑的路径分析。基于以上提到的不足， 本文着重研究了遗传算法在路径覆盖测试数据生成中的应用。本文重点讨论了在 路径覆盖测试中使用遗传算法生成测试数据时所要考虑的几方面内容： 1 怎样将遗传算法应用到路径覆盖测试数据的自动生成中； 2 怎样用遗传算法生成基本数据类型的测试数据和类对象的测试数据； 3 怎样使用遗传算法以使产生测试数据的性能最佳： 4 怎样将该方法使用到实际中，提高测试效率。 1 2 论文的主要工作 本文主要研究了以下几方面的内容： 1 将遗传算法应用到路径覆盖测试数据的生成中。 本文分析讨论了在面向路径覆盖的测试数据生成中使用遗传算法的理论依 据。本文将程序中的各个分支谓词和循环谓词设计成若干个函数，将它们作为运 用遗传算法所需的适应度函数，将求得的适应度值作为评判目标解的依据。当适 应度值取得预期最小值时，输入的测试数据即为符合要求的测试数据。对路径的 表示和选择、适应度函数、程序插装方式作了改进，使之能符合实际应用的需要。 2 设计了遗传算法产生类对象测试数据的方法。 在面向对象语言编写的程序中，测试数据不仅仅包含了基本数据类型，还包 含了类对象。类对象的生成不同于基本数据类型的生成。本文以类对象产生过程 为基础，设计了类对象的编码方式，提出了计算类对象适应度的函数，并运用遗 传操作，将遗传算法应用到类对象洌i 试数据的生成中。 3 建立了测试数据自动生成工具模型。 为了将遗传算法应用到实际系统的测试数据生成中，需要一些辅助的工具。 本文建立了一套基于遗传算法的测试数据自动生成工具模型，与以前测试数据生 成工具模型不同的是，本工具模型的核心模块是基于遗传算法的，其它辅助模块 也是根据本文讨论的若干问题而建立的。 4 进行了详细的实验和数据分析。 为了验证整个工具模型的实用性，在实际系统的平台上进行了有针对性的实 验，对影响遗传算法的各个因素、遗传算法的生成效率分别进行比较，得出了大 上海师范大学硕士研究生擎岔论文 遗传算法在路径覆盖测试数据生成孛秘研究与应用 量的实验数据，通过分析比较实验数据得出结论。实验的结论对以后运用遗传算 法在测试数据自动化生成中进行进一步研究具有一定的参考和实用价值。 1 3 论文创新点 论文的创新点如下： 1 将遗传算怯应用到面向路径覆盖的测试数据自动化生成中； 2 设计了在面向对象程序中遗传算法自动生成类对象测试数据的方法： 3 建立了一个基于遗传算法的工具模型，并初步实现了模型的核心部分：测试 数据生成器； 4 使用该方法对实际系统进行实验，对实验结果进行分析，归纳总结遗传算法 怎样使用性能最佳。 1 。4 论文结构 本文的章节安排如下： 第一章绪言。介绍了论文的研究背景、主要工作、论文创新点及论文结构。 第二章软件测试技术与遗传算法。着重介绍了组成文章的两个方面：软件 测试和遗传算法。在软件测试技术部分，介绍了软件测试技术中的概念、分类、 阶段划分及测试用例的选择方法，并概括介绍了现有的面向路径覆盖的溯试数据 生成方法。在遗传算法部分，简单介绍了遗传算法中的产生发展、基本概念和特 点，阐述了遗传算法的一般过程和影晌遗传算法的重要因素。 第三章遗传算法在测试数据生成中的应用。分析了使用遗传算法生成测试 数据的理论依据，研究了使用遗传算法生成测试数据所要考虑的若干问题，在路 径表示和选择、适应度函数和程序插装方式上根据需要作出了改进，提出了适用 于实际的应用方法。最后用一个简单的实例详细阐述了使用遗传算法生成测试数 据的过程。 第四章类对象测试数据的自动生成。详细研究了面向对象程序中遗传算法 生成测试数据过程中的难点问题：类对象测试数据的生成。设计了一种新的类对 象编码方法，在广义海明距离法的基础上提出了适用于本系统的类对象生成适应 度函数，并通过一个简单的实例详细阐述了生成类对象的过程。 第五章测试实例及分析。将该方法应用于交通银彳亍数据大集中项目个贷子 系统的单元测试中，建立了一个使用该方法的工具模型，使其根据需要自动生成 测试数据。最后给出实验结果和结果分析，进行比较，证明基于遗传算法的面向 路径的测试数据生成方法是灵活的、有效的和实用的。 第六章总结与展望。对本文的工作进行了总结并提出下一步的工作。 上海师范大学硕士研究生学位论文遗传算法在路径覆盖测试数据生成中的研究与应用 第二章软件测试技术与遗传算法 2 。1 软件测试技术 2 1 1 较件测试技术概述 软件测试是软件开发的重要环节。软件测试的目的在于按照规定的步骤，采 用适当的方法，对软件进行严格的检查，以发展和改正软件的错误，使软件的质 量在测试过程中不断提高，逐渐达到规定的要求，能够交付用户使用。软件开发 的经验表明，软件测试需要消耗大量的资源，软件测试所需工时通常高达开发期 总工时的4 0 一5 0 。美国n a s a 的a p o l l o 登月计划，更是有约8 0 的经费用于系 统测试中。由此可见，软件测试不仅仅是软件开发中的一个技术措旅，软件测试 对于整个项目能否顺利实施具有非常重要的作用。随着人们对软件系统的期望值 日益提高，软件的规模和软件的复杂程度也会日益增加，软件测试所占的比重和 地位也会越来越高。 近年来，尽管软件测试技术有了长足的进步，但总的来说，仍然和软件开发 实践提出的要求有相当大的距离。测试手段的进展也远远没有达到令人满意的程 度。 2 1 2 软件测试分类 对于软件测试技术，可以从不同的角度加以分类“7 。 1 从程序执行的方式，分为人工涮试和自动化测试。 2 从是否需要执行被测试软件的角度，分为静态测试和动态测试。 3 从在动态测试中是否需要研究程序代码的角度，分为白盒测试和黑盒测试。 4 从静态测试中是否需要研究原程序语法的角度，分为语法测试和语义测试。 5 从如何选择测试数据的角度，分为功能测试、结构测试。 6 从使用的测试数据的类型，分为确定性测试和随机测试。 7 从被测试软件的程序语言，分为面向过程测试和面向对象测试。 2 1 3 软件测试的阶段划分 传统的软件测试阶段包括单元测试、集成测试、确认测试、系统测试、验证 和确认以及回归测试。 1 单元测试。单元是程序的最小组成单位，单元测试是检验程序最小单位有无 错误。主要检查单元接口、局部数据结构、重要执行路径、错误处理、边界 这五方面的内容。 上海师范大学硕士研究生学位论文遗传算法在路径覆盏测试数据生成中的研究与应用 2 集成测试。集成测试是在单元测试基础上，对软件进行集成的过程中进行测 试。传统的集成测试主要测试模块间的接口问题。 3 系统测试。系统测试是将软件作为一个计算机系统的组成成分，与计算机硬 件、外设、支撑软件、数据、人员等其他系统成分结合进行测试。系统测试 包括功能测试、性能测试、压力测试、安全测试、恢复测试等。 4 验证和确认。验证测试是为了确定给定开发阶段产品是否满足该阶段开始时 提出的条件而对软件进行的测试过程，它说明了软件是否正确。确认测试是 指在开发过程期间或结束时，为确定软件是否满足规定的需求而对软件进行 测试的过程。它说明了软件是否与需求一致。 5 回归测试。回归测试就是针对已测试并进行错误修改的功能模块及可能受到 影响的模块子集进行重新测试，它能够发现耦合度较高的模块间，由于其中 一模块更改而产生的相关联的错误。 2 1 4 测试用例的选择 测试用例的选择0 1 是进行结构测试的一个难题，现在还没有完善的解决方 法，只能凭借工程经验判断。现在应用得最多的方法是经验测试法，这种方法是 由测试员在研究程序内容的基础上，任意选择一条路径，标志出条件，选择适当 的输入数据，启动程序运行。这种方法在进行测试时，要不断地启动程序运行， 直至分析器显示出测试已经实现了预期的覆盖才停止测试。经验检测法的主要问 题是效率低，为了要通过一条尚未测试的路径，往往需要运行程序多次，甚至上 百次。而且，实现分支覆盖或路径覆盖并不是测试的最终目的，更重要的是要发 现和改正错误，因此需要为每个测试用例提供预期的结果，这种方法工作量非常 大，使测试人员难以承受。 还有一种方法是按程序流程图列举出为实现分支覆盖或路径覆盖所需的全 部路径，然后根据每个路径输入数据，启动程序运行。在采用这个方法时，输入 数据的选择尤为重要。对于复杂程序，输入数据的选择非常困难，现在多用向前 核查法来解决。向前核查法是指沿着预期的路径向前检查，每到达一个判断点， 确定该点的判断变量所能提供的最宽数值区间，然后继续前行。在这个过程中， 每个变量的可能取值范围将逐渐缩小。到达程序出口后，就能找到启动这条路径 所需的输入数据。 乏2 面向路径覆盖的测试数据生成方法 在软件测试中，面向路径覆盖的测试数据生成问题可以描述为：给定一个程 序p 和p 中一条路径w ，设p 的输入空间为d ，求军d ，使得p 以i 为输入运 上海师范大学硕士研究生学位论立遗传算法在路径覆盖测试数据生成中的研究与应用 行，所经过的路径为w 。软件测试中的控制流测试中诸如语句覆盖、分支覆盖、 条件覆盖、判定一条件覆盖、路径覆盖等问题，数据流测试中的定义覆盖、引用 覆盖等问题，组装测试中的调用对覆盖、数据流测试等问题，以及面向断言的测 试和回归测试中的一些问题都可以归结为该问题“1 ， 目前，国内外面向路径的测试数据生成方法可分为静态法和动态法。静态法 又包括符号执行法和区间算术法。动态法则包括随机数法、k o r e l 法、试探法等。 下面，就几种面向路径的动态法做一下简单介绍。 2 2 1 随机数法 随机法是最简单的动态生成测试数据的方法，在实际运用中甚至可以产生 几乎任何种类型的测试数据。因为任何数据类型在计算机中的表示归根到底都 是一组二进制串，它的基本思想是对输入数据域d 进行随机取样。其主要优点是 生成单个测试数据的开销较小，简便易行。它不受d 的结构的限制。可以迅速生 成大量的测试数据，并能够将它们应用于黑盒测试。 在采用测试用例抽样测试时，这种方法对产生测试数据非常有效。只要限定 抽样的范围，它就能产生符合条件的测试数据，组成有效的测试用例。但是，该 方法最大的缺点是盲目性，在约束要求较高的测试方法中，比如分支覆盖或路径 覆盖，它的效率非常低下，很难产生符合要求的解集，也就是说对分支覆盖或路 径覆盖，很难达到1 0 0 的覆盖要求。因而不适合用于逻辑复杂、约束要求高的 程序的测试数据自动生成中。 k o r e l 法0 1 从d 中任选一组数据，按步迸的方式运行p ，即一次前进一个分 支谓词。若当前分支谓词的值不符合要求，就建立一个分支函数，然后用函数 最小化方法调整输入变量值，使得在仍能经过已成功经过的子路径的前提下， 值为负数( 或0 ) 。该方法先用探测性搜索确定前进方向，再用模式性搜索使分支 函数值尽快达到最小值，并采用动态数据流分析技术确定影响分支谓词的变量， 减小搜索的盲目性。虽然该方法对于输入变量无整数限制的线性路径约束是完整 的，但是模式性搜索的步长与谓词函数的系数相关，从而导致求解问题q 的时间 与谓词函数的系数相关。 由于采用了步进方式，故这种方法可以尽早发现不可行路径。然而，由于该 方法一次只考虑一个分支谓词和一个输入变量，并且使用回溯技术，所以即使矽 上所有谓词函数都是输入变量的线性函数，它也耍进行大量的迭代。如果上 几个分支谓词依赖于公共的输入变量，那么在回溯时会造成大量的浪费。另外， 上海师范大学颞研究生学位论文遗传算法在路径疆盖剁试数据生成中的研究与应用 对于非线性路径约束，该方法只能找到局部极小值，当谓词函数有多个局部极小 值时难以找到问题q 的解，所以该方法对于非线性路径约束是不完备的。该方法 不能用于黑盒测试。1 9 9 6 年，这种方法被扩充为面向目标的链方法”3 。后者被应 用于面向断言的测试数据自动生成。3 和回归测试数据自动生成。 2 2 3 试探法 试探法的基本思想是从d 中选择输入数据，运行p ，然后根据运行结果，结 合概率论的思想产生新的输入数据继续试探，其优点是不受搜索空间限制性条件 ( 如可微、连续、单峰) 的约束，并且不需要其他辅助性信息( 如导数) ，对于一些 传统方法难于处理的大空闯、多峰、菲线性、全局优化等复杂闯题。试探法具有 独特的优势和高效性。试探法主要包括遗传算法和模拟退火算法两种。它们都能 用于黑盒测试。 遗传算法是生物进化的一个计算机模型，它借助于进化学中的相关原理，将 自然选择学说中的“选择、交叉、变异”这三个基本方面应用于问题的搜索过程 中。遗传算法能够应用于测试数据生成领域的基本理论依据是函数最小化原理。 将程序的部分看作是函数，执行函数直到代码中的某个位置被达到。记录下该 位置一个或多个变量的值，并将这些值看作是函数的值。为了找到符合要求的输 入数据，只要找到一个输入数据能使函数达到最小值就可以了。关于遗传算法将 从下一节开始做详细介绍。 2 3 遗传算法 2 3 1 遗传算法简介 遗传算法( g e n e t i c a l g o r i t h m s ，g a ) “5 “研究的历史比较短，2 0 世纪6 0 年 代末到2 0 世纪7 0 年代初期，由美国m i c h i g a n 大学的j o h n h o l l a n d 与其同事、 学生们形成了一个较完整的理论和方法，从试图解释自然系统总生物的复杂适应 过程入手，模拟生物进化的机制来构造人工系统的模型。h o l l a n d 于1 9 7 5 年出版 的专著自然与人工系统中的自适应标志着遗传算法的正式诞生。如今，遗传 算法已广泛应用于生物、工程技术、运筹学、计算机科学、图象处理、模式识别、 社会科学等领域。它的主要特点有； ( i ) 自组织、自适应和自学习性。 ( 2 ) 并行性。能以并行方式同时搜索解空间内的多个区域。 ( 3 ) 独立性。不需要求导或其他辅助知识，只需影响搜索方向的适应度函数。 ( 4 ) 多解性。对给定问题，遗传算法可以产生许多的潜在解，由使用者确定。 上海师范丈学硕士研究生学位论文遗传算洼在路径覆盖测试数据生成中的研究与应用 2 3 2 遗传算法的一般流程 遗传算法的一般流程如下，其流程图如图2 3 2 - l 所示： 第一步：随机产生初始种群，个体数目一定，每个个体表示为染色体的基因编码： 第二步：计算个体的适应度，并判断是否符合优化准则，若符合，输出最佳个体 及其代表的最优解，并结束计算，否则转向第三步； 第三步：依据适应度选择再生个体，适应度高的个体被选中的概率高，适应度低 的个体可能被淘汰； 第四步：按照一定的交叉概率和交叉方法，生成新的个体； 第五步：按照一定的变异概率和变异方法，生成新的个体； 第六步：由交叉和变异产生新代静种群，返回至第二步。 图2 3 2 - 1 遗传算法的流程图 上海师范大学硕士研究生学位论文 遗传算法在路径覆盖测试数据生成中的研究与应用 2 4 影响遗传算法的因素 2 4 1 编码方法 从表现型到基因型的映射称为编码。编码方法在遗传算法中是非常关键的环 节，编码的好坏直接影响到问题解决的优劣。编码方式分为二进制编码( b i n a r y c o d i n g ) n 7 1 、格雷码( g r a y c o d i n g ) t a j 、实数编码( r e a l c o d i n g ) d g 、海明码 ( h a r m m i n gc o d i n g ) 啪1 以及根据问题领域的不同设计有特色的编码方式等。使用 哪种编码形式，要看问题的原则而定，有效的编码方法将会提高运算处理速度。 2 4 1 1 数值型数据编码 对于数值类型，通常采用二进制“”编码形式，将某个变量值代表的个体表示 为一个 0 ，1 ) 二进制串。串的长度取决于求解的精度。 对于整型、长整型的测试数据，根据需求规约中测试数据值，规定产生的二 进制串的长度。例如，对于在- 1 2 8 1 2 7 之间的数，可以用8 位的二进制串 表示，其中最高位为符号位；而在- 3 2 7 6 8 3 2 7 6 7 之间的数，可以用1 6 位的 二进制串，其中最高位为符号位。对于无符号数，也可用同样的方法来表示， 唯一不同之处就是最高位不是符号位。 对于浮点型、双精度浮点型数，可以先划定产生数据的区间范围，规定好产 生二进制串的长度，在此范围内依照一定的规则生成二进制串。如将一个二 进制串慨，b 2 0 b o ) 转化为区间 - 1 ，2 内对应的实数值，只需采用以下两步： 1 将一个二迸制串( 6 ：。b = o 6 0 ) 代表的二迸制数转化为1 0 迸制数： 吣”b 。) ：一i 三6 f 心i 1 甜 2 一对应的区间 一1 ，2 内的实数： 一m ”错 2 4 1 2 非数值型数据编码 非数值型数据主要指的是字符串型、字符型、布尔型等非实数类型的数据。 对布尔型，因为其只有t r u e 和f a l s e 两种状态用遗传算法对其进行演化计 算反而增加了复杂性，用试探法就可以解决问题，不需要对其进行编码； 对字符型，可以使用其a s c i 码转成二进制作为编码； 对字符串型，先将其每个字符的a s c i 码转成二迸制码，然后将每个二进制 码按字符顺序串联起来，就形成对字符串的编码； 对于其他类型，因为用到比较少，暂时不予考虑。 上海师范大学硕士研究生学位论文遗传算法在路径覆盖测试数据生成中的研究与应用 2 4 2 初始种群规模 在产生初始种群之前，需先决定种群的大小。种群过大会耗费过多的计算时 间，过小则会造成过早收敛。初始种群的产生方式可以在问题值域范围内随机产 生或由启发式产生，也可以根据需求规约指定初始种群，使以后的进化过程更容 易收敛到目标解。 2 4 3 适应度函数 遗传算法中，基本不用搜索空间的知识，而仅用适应度函数来评价染色体 的优劣，因此适应度函数选择是否适当对算法的性能好坏影响很大，应根据实际 问题的特性具体确定。通常遗传算法要求适应度函数值非负，同时要求把待解优 化问题表达为最大化问题，即目标函数的优化方向为适应度函数的增大方向，因 此常常对所选择的适应度函数进行某些数学变换。几种常见的变换方法如下： ( 1 ) 非负变换：把最小化优化目标函数变换为以最大值为目标的适应度函数 r p 一9 ，( z ) = ：一。式中，厂( z ) 是适应度函数；c 一是常数，通常取为迄今 l u 为止进化过程中z 的最大值，或者为了保证，( z ) 为正而预先设定的一个与 种群无关的常数。 ( 2 ) 线性变换：把优化目标变换为适应度函数的线性函数，0 ) - a + z + 6 ，口， b 是系数，可根据具体问题的特点和所期望适应度值的分散程度在算法开 始时确定或在每一代过程中重新计算。 ( 3 ) 幂函数：把优化目标函数变换为适应度函数的幂函数，仁) tz 4 ，式中a 是 常数，据经验确定。 ( 4 ) 指数变换：把优化目标函数变换为适应度函数的指数函数，0 ) 一e ( 哪“。 式中口是常数。 2 4 。4 遗传操作 遗传操作决定了染色体之间信息的组合及交换规则和方式。不同的问题，必 须采用最合适的遗传操作设计方法。基本遗传算法包含了三种遗传操作：( a ) 选择 操作：根据个体适应度的大小，决定该个体复制到下一代的概率。一般适应度较 高的个体，被选择复制到下一代的概率也较大。( b ) 交叉操作：它提供了一个种 群中的同源染色体进行信息交换的机制。( c ) 变异操作；它将染色体上的某个基因 位用它的等位基因来代替，以引进新的基因品种，避免出现收敛过早的情况，维 持种群的多样性，便于生成更优化的染色体。 上海师范大学硕士研究生学位论文遗传算法在路径覆盖测试数据生成中的研究与应用 2 4 4 1 选择操作 遗传算法的基本原理是达尔文的自然选择理论，因此选择是遗传算法的推动 力。在本课题中，选择算子使用的是轮盘赌选择法。这是比较简单和有效的选择 方法。每代种群中，被复制的个体数目由复制概率只控制，只常取0 1 o 2 ， 也就是种群中有1 0 个体被复制，相应地有1 0 个体被淘汰，以保持种群大小。 轮盘选择法是最常用的方法，该方法的讲解将在3 7 ，2 中详细介绍。其他方法有 随机选择和按适应度大小选择等。 2 4 4 2 交叉操作 在遗传算法中，交叉是产生新个体的主要手段。它仿造生物学中杂交的原理， 将两个个体( 染色体) 的部分字符( 基因) 互相交换。执行交换的个体是随机选 择的。首先要确定交换的概率p ，大致为0 8 0 9 5 左右，也就是约8 0 9 5 的个体要执行交叉，然后采用上述轮盘赌选择方法，按适应度大小选择被交叉的 个体，两两进行交叉。该方法的讲解将在3 7 2 中详细介绍。 根据交叉点的数目不同，分单点交叉和两点交叉。单点交叉如前所述，只选 择个交叉点，该点之后的字符全部参加交叉。两点交叉选取两个交叉点，只有 两点间的字符才参加交叉。当字符串长度大时，常使用两点交叉。 2 4 4 3 变异操作 变异是遗传算法中产生新染色体的另一种方法，它是将某一染色体的某一位 字符进行补运算，使0 变为1 ，或将l 变为0 。 变异染色体的选择以及变异位置的确定，都是采用随机的方法产生。首先确 定变异的概率只，只通常较小，约为0 0 0 1 0 0 1 ，也就是说1 0 0 0 个字符中有 l 1 0 个发生突变。在本课题中，由于染色体编码后字符长度有限，适当增加了 1 变异概率只，设为染色体长度l 的倒数。然后，针对每个字符在 o ，1 之间产 l 生三位有效数的均匀分布随机数。若只= 0 0 0 8 ，凡是随机数小于0 0 0 8 所对应 的字符，将实行交异。该方法的讲解将在3 7 2 中详细介绍。 上海师范大学硕士研究生学位论文 遗传算法在路径覆盖测试数据生成中的研究与应用 第三章遗传算法在测试数据生成中的应用 3 1 研究背景和目标 3 1 1 研究背景 在大型系统的开发中，测试占了非常重要的比例。面向路径覆盖测试属于动 态测试的一种，它要求在程序测试过程中，尽可能覆盖程序能够到达的所有的路 径。研究显示，完全的路径覆盖测试是不可能的，特别是在带有循环的程序中， 路径的数目是不确定的。图3 1 卜1 是某一程序段的控制流程： 圈3 1 11 莱一程序段的控制流程 如图3 1 卜l 所示，对于面向路径覆盖测试，可能存在以下无数条路径： l 一3 5 6 8 一1 0 一1 2 1 3 5 6 8 1 0 一8 1 0 1 2 1 3 5 6 8 一1 0 8 1 0 一8 1 0 一8 一l o 一1 2 对于不同的路径，需要专门的测试数据来覆盖目标路径。但随着程序逻辑的 不断复杂，测试用例的编写工作越来越困难。特别是存在若干分支的路径，用人 工的方式编写测试用例咀覆盖目标路径需要耗费大量的时间，且常常无效。 3 1 2 研究目标 如3 1 1 所述，因为测试用例是测试过程的必备元素，而随着程序逻辑复杂 程度的不断提高，想要编写出能够覆盖目标路径的狈试用例也日益困难，因此需 要寻找一种算法用于自动生成测试数据，产生的测试数据能够导致程序执行目标 路径。在前面中讨论的路径覆盖的测试数据生成算法中，随机法吲效率低下，对 于简单逻辑还能使用，但对于复杂逻辑效率太低，不适合应用于大型程序中； 上海师范大学硕士研究生学位论文 遗传算法在路径覆盖测试数据生成中的研究与应用 k o r e l 方法吲”1 和遗传算法都属于动态方法，考虑到k o r e l 方法一次只考虑一个 分支谓词和个输入变量，并且使用回溯技术，需要进行大量的迭代，而遗传算 法具有并行搜索的特点，因此将遗传算法作为对测试数据自动化生成的研究。 在确定遗传算法作为测试数据自动化生成方法后，提出研究目标如下： 在面向对象程序中，从被测程序的控制流程中选择一条典型的分支路径，以 此路径作为目标路径，使用遗传算法用于测试数据自动化生成，产生的测试数 据能够导致程序执行目标路径。 3 2 遗传算法用于测试数据生成的理论依据 3 2 1 测试数据生成的函数最小化闷题 测试数据生成基于的概念是程序的一部分可以被看作是函数。可执行函数直 到代码中的某个位置被达到，记录下该位置一个或多个变量的值，并将这些值看 作是一个函数的值。 例如，假设一个程序的3 2 4 行包含条件：i f ( p o s = 2 1 ) 我们的目标是要保证这个条件为t r u e 的分支被执行。必须找到一个输入，当 3 2 4 行被到达时变量p o s 的值大于等于2 l 。确定p o s 值的最简单方法是将程序执 行到第3 2 4 行然后记录此时p o s 的值。 用p o s 3 2 4 表示目标程序在输入数据x 上执行时p o s 的值。那么在3 2 4 行时执 行t r u e 分支的问题就可以转化为函数最小化问题： f 2 1 一p o s3 “) ，珊3 “( 石) 2 1 ，扛) - 【 o 其它 要找到符合要求的输入数据，只要找到一个x 使函数俐达到最小值就可以了。 ，( 指出了输入数据逼近期望结果的程度。一般情况下可以认为，f i x ) 自q 值越 小，输入数据越逼近期望的结果。这样就可以利用只 的值来评价当前的输入数 据z 逼近期望目标的程度，并指导遗传算法的函数优化过程。可以通过调整初始 输入数据j ，并用，f 来评价何种调整方法能使数据更接近期望的目标；测试数 据生成器可以以触) 的函数值为指导，通过一系列的调整使其逐步逼近最后的目 标。在遗传算法中，胸可以作为适应度函数来计算测试用例的适应度值，由此 决定测试用例能否存活到下一世代中。 在参考文献 6 3 中使用了一种基于动态数据流分析的启发式搜索方法对函 数舷) 进行最小化。不妨要设到达的路径u - ( r t l , n ：，) 目标是找到一个测试 数据x d ，使得程序p 以x 为输入数据时的执行路径就是u 。那么可以把问题转 上海师范大学硕士研究生学