基于遗传算法软件测试用例自动生成分析与研究.pdf

基于遗传算法软件测试用例自动生成分析与研究 关键词：测试用例自动生成；多路径测试；软件测试；遗传算法 论文类型：应用基础研究 兰州交通大学硕士学位论文 a b s t r a c t i ti se s t i m a t e dt h a t8 0 o fs o f t w a r ed e v e l o p m e n tc o s ti ss p e n to nd e t e c t i n ga n df i x i n g d e f e c t s t ot a c k l et h i si s s u e ，an u m b e ro ft o o l sa n dt e s t i n gt e c h n i q u e sh a v eb e e nd e v e l o p e dt o i m p r o v et h et e s t i n gf r a m e w o r k a l t h o u g ht e c h n i q u e ss u c ha ss t a t i ca n a l y s i s ，r a n d o mt e s t i n g a n de v o l u t i o n a r yt e s t i n gh a v eb e e n u s e dt oa u t o m a t et h et e s t i n gp r o c e s s ，i ti sn o tc l e a rw h a ti s t h e b e s t a p p r o a c h p r e v i o u sr e s e a r c ho ne v o l u t i o n a r yt e s t i n gh a sm a i n l yf o c u s e d o n p r o c e d u r a lp r o g r a m m i n gl a n g u a g e sw i t hs i m p l et e s td a t ai n p u t ss u c h 觞n u m b e r s i nt h i sw o r k ， w ep r e s e n ta l le v o l u t i o n a r yt e s t i n ga p p r o a c ht h a tc o m b i n e sag e n e t i ca l g o r i t h mw i t hs t a t i c a n a l y s i st oi n c r e a s et h en u m b e ro ff a u l t sf o u n dw i t h i nat i m ef r a m e g e n e t i ca l g o r i t h m s ( g a ) h a v eb e e nu s e ds u c c e s s f u l l yt oa u t o m a t et h eg e n e r a t i o no ft e s t d a t af o rs o f t w a r ed e v e l o p e di na d a 8 3 t h et e s td a t aw e r ed e r i v e df r o mt h ep r o g r a m s s t r u c t u r ew i t ht h ea i mt ot r a v e r s ee v e r yb r a n c hi nt h es o f t w a r e t h ei n v e s t i g a t i o nu s e sf i t n e s s f u n c t i o n sb a s e do nt h eh a m m i n gd i s t a n c eb e t w e e nt h ee x p r e s s i o n si nt h eb r a n c hp r e d i c a t e a n do nt h er e c i p r o c a lo ft h ed i f f e r e n c eb e t w e e nn u m e r i c a le x p r e s s i o n si nt h ep r e d i c a t e t h e i n p u tv a r i a b l e sa r er e p r e s e n t e di ng r a yc o d ea n da sa l li m a g eo ft h em a c h i n em e m o r y t h e p o w e ro fu s i n gg al i e si nt h e i ra b i l i t yt oh a n d l ei n p u td a t aw h i c hm a yb eo fc o m p l e x s t r u c t u r e ，a n dp r e d i c a t e sw h i c hm a yb ec o m p l i c a t e da n d1 j l l k n o w nf u n c t i o n so ft h ei n p u t v a r i a b l e s t h u s ，t h ep r o b l e mo ft e s td a t ag e n e r a t i o ni st r e a t e de n t i r e l ya sa no p t i m i z a t i o n p r o b l e m r a n d o mt e s t i n gi su s e da sac o m p a r i s o no ft h ee f f e c t i v e n e s so ft e s td a t ag e n e r a t i o nu s i n g g aw h i c hr e q u i r e su pt ot w oo r d e r so fm a g n i t u d ef e w e rt e s t st h a nr a n d o mt e s t i n ga n d a c h i e v e s10 0 b r a n c hc o v e r a g e t h em a i nf e a t u r e so ft h eg e n e t i ca l g o r i t h mi si n i t i a l l y u n k n o w ns e a r c hs p a c et oc o l l e c ti n f o r m a t i o na n dt h e ni n d i c a t et ot h ea b i l i t yo fo t h e ru s e f u l s u b s p a c e i ft h el o g i c a ls t r u c t u r eo fs p a t i a lv a r i a t i o ni sn o tt o ol a r g e ，i tc a nb ee x h a u s t i v e d e v e l o p m e n to fh e u r i s t i cs e a r c hs t r a t e g yt or e m a i nu n d e rt h ec o n t r o l o ft h ec a l c u l a t i o nt i m e g e n e t i cc a nb eu s e da sa na d a p t i v es a m p l i n gs t r a t e g yt os e a r c hal a r g ea n dc o m p l e xs p a c e t h es a m p l i n gs t r a t e g yi st oa d a p tt h es a m p l e ( o f f s p r i n g ) a r eu s e dt ot h es u b s e q u e n ts a m p l i n g b i a si n t ot h es a m p l i n go ft h eh i g h - e x p e c t e dp e r f o r m a n c ei nt h eg l o b a lb e s td o m a i nf e e d b a c k t h i sm e a n st h a t ，e v e ni fas o l u t i o nh a sg e n e r a t e dag o o dg e n e t i co p t i m i z a t i o np a r a m e t e r s v a l i d i t ya l s od e p e n d so nt h eu s e f u l n e s so fi n f o r m a t i o no b t a i n e dt h r o u g hf e e d b a c k i m p o r t a n t t os e l e c tt h ea p p r o p r i a t ef e e d b a c km e c h a n i s mt ob ea d a p t i v es e a r c hs t r a t e g y t h ea d v a n t a g eo f g ai st h a tt h r o u g ht h es e a r c ha n do p t i m i z a t i o np r o c e s s ，t e s ts e t sa r ei m p r o v e ds u c ht h a tt h e y a r ea to rc l o s et ot h ei n p u ts u b d o m a i nb o u n d a r i e s t h eg ag i v e sm o s ti m p r o v e m e n t so v e r r a n d o mt e s t i n gw h e nt h e s es u b d o m a i n sa r es m a l l m u t a t i o na n a l y s i si su s e dt oe s t a b l i s ht h e q u a l i t yo ft e s td a t ag e n e r a t i o na n dt h es t r e n g t h sa n dw e a k n e s s e so ft h et e s td a t ag e n e r a t i o n i i i 基于遗传算法软件测试用例自动生成分析与研究 s t r a t e g y f i n a l l y ，w ed e s i g n e da n di m p l e m e n t e das y s t e mb a s e do ng e n e t i ca l g o r i t h mt e s tc a s e s a u t o m a t i c a l l yg e n e r a t e d t h eb a s i cd e s i g ni d e ao ft h es y s t e mi st h et r i a n g l ep r o g r a ma sa t y p i c a le x a m p l e ，t h es p e c i f i e dd a t ar a n g ea n di n p u td a t at og e n e r a t et e s tc a s e st ot h ef u l l e s t e x t e n tp o s s i b l et h ec o m p l e t ep a t hc o v e r a g e d e r i v e db a s e do ne x p e r i m e n t a ld a t a ，t h i ss y s t e m n o to n l yt oc o m p l e t et h es i m p l eg e n e r a t i o no ft h et e s tc a s eo ft h ep r e - s e tt a r g e tp a t h ，b u ta l s o c a nf u l l yt r a v e r s et h et a r g e tp a t hg e n e r a t e dt om e e tt h er e q u i r e m e n t so ft h et e s tc a s e a tt h e s a m et i m e ，t h ep r o g r a mp a t ht ob ec o v e r e do rn o tr e c o r d e d ，t h eb e s ts o l u t i o nc u r r e n t l yc a n a l s ob eg i v e nw h i l ep a t ha r en o tf u l l yc o v e r e d e x p e r i m e n t ss h o wt h a tg a r e q u i r e dl e s sc p u t i m ei ng e n e r a lt or e a c hag l o b a ls o l u t i o nt h a nr a n d o mt e s t i n g t h eg r e a t e s ta d v a n t a g ei sw h e n t h ed e n s i t yo fg l o b a lo p t i m ai ss m a l lc o m p a r e dt oe n t i r ei n p u ts e a r c hd o m a i n k e yw o r d s ：a u t o m a t i ct e s tc a s eg e n e r a t i o n ；p a t hw i s et e s t ；s o f tw a r et e s t ；g e n e t i c a l g o r i t h m i v 兰州交通大学硕士学位论文 目录 摘要i a b s t r a c t i i i 1 绪论1 1 1 课题研究的背景和意义1 1 2 国内外研究现状2 1 3 本文的主要工作3 1 4 论文结构。3 2 软件测试及其测试方法5 2 1 软件测试5 2 1 1 黑盒测试5 2 1 2 白盒测试：5 2 2 测试数据自动生成6 2 2 1 路径测试生成器j 8 2 2 2 数据规范发生器11 2 2 3 随机测试11 3 遗传算法1 3 3 1 遗传算法的介绍1 3 3 2 遗传算法的应用1 3 3 3 遗传算法的特点1 5 3 4 影响遗传算法的因素1 7 3 4 1 编码方法17 3 4 2 适应度函数1 9 3 4 3 遗传操作2 0 4 遗传算法测试用例自动生成2 5 4 1 系统框架结构2 5 4 2 遗传算法的设计实现2 5 4 2 1 参数编码策略2 5 4 2 2 适应度函数的构造2 7 4 2 3 遗传算子的改进2 8 4 2 4 程序插装实现31 基于遗传算法软件测试用例自动生成分析与研究 5 试验和分析3 3 5 1 软件测试工具的开发3 3 5 2 测试工具的实现3 4 5 2 1 测试实验的演示3 4 5 2 2 三角形程序的说明3 6 5 3 实验结果分析3 9 结论4 2 致 射4 4 参考文献。4 5 攻读学位期间的研究成果4 7 兰州交通大学硕士学位论文 1 绪论 1 1 课题研究的背景和意义 在过去的5 0 年里，软件在所有工业领域的发展导致了其复杂性和可靠性不断增长 的需求。由美国国家标准与技术研究所进行的一项研究显示，约8 0 的软件开发成本是 用于识别和纠正软件缺陷和错误的。同样的研究发现在软件缺陷的成本花费上，美国一 年的经济是5 9 5 个十亿美元左右，有三分之一被用于不良的软件测试基础设施中。在现 有的测试基础设施里，已经开发了大量的工具来执行自动化测试。但是，测试数据自动 生成仍然是一个时下主要的研究目标。 软件测试是增加程序员在软件的正确性和可靠性方面巨大信心的主要可行的方法 之一。有时候，不恰当的测试在某个项目中正确执行数月甚至数年之后才发现一些输入 组存在严重的错误。一些不正确的软件投放市场不能够得到完全测试，可能会导致客户 的不满，甚至在关键领域的应用软件造成的后果是非常严重的，某些免费的软件存在的 故障可能导致巨大的经济损失，甚至危及生命。在过去的几十年里，软件的测试程序和 工具已经用于系统开发的方法中，以避免许多困难存在于项目专案中。然而，在今天的 软件产业中软件测试已经是最常见的错误检测技术。软件测试的主要目的是确保被测试 的程序的正确性从而增加它的信心。 软件测试的目的是生成测试数据和找到这些测试数据其中的的错误。因此，一个优 秀的系统的测试环境应该具有从坏的测试数据( 不适合) 分化出良好的( 合适的) 的测 试数据的能力，它应该是能够检测到良好的测试数据并将它们生成。如今的测试工具可 以自动生成测试数据并且满足某些标准，如分支测试，路径测试等。然而，这些工具在 进行复杂的软件测试时会发生某些问题。 测试工具应该是通用的，相应的强大的测试软件在现实测试中对应正确的测试标准 从而准确产生正确的测试数据。因此，搜索算法的最佳值( 测试数据) 必须被决定在哪 里产生并集中搜索。不难找到正确的测试数据是因为它可以在软件中的谓词条件或限制 的输入域中输入一套有效的数据。 一个良好的测试数据则未必适合另一个程序，即使它们具有相同的功能。因此，自 适应条件下的软件测试工具的测试是必要的。自适应装置在它所监测的测试数据的环境 中，产生新的解决方案并检验测试的有效性。最近，一些超启发式搜索，随机测试生成 和静态分析的方法已被完全用于自动化的测试过程中，但该类软件工具的真正应用仍然 有限。随机测试生成了大量的工具以及测试案例的自动生成，但一些研究发现了遗传算 法( 进化测试) 更加有效在结构测试中优于随机测试。 基于遗传算法软件测试用例自动生成分析与研究 1 2 国内外研究现状 遗传算法作为一种技术，用于自动化测试案例的过程中，根据已有研究进化测试在 文献中经常被称为遗传算法。软件测试是增加程序员在软件的正确性和可靠性方面巨大 信心的主要可行的方法之一1 1 。2 0 世纪9 0 年代初以来，大量的研究已经完成进化测试。 这些研究根据问题的复杂性和适用性的不同而不同。为了这个项目的相关性，过去的许 多研究已被分类，根据测试和优化参数的复杂性情况下使用遗传算法产生的测试用例的 复杂性是非常重要的，因为生成测试用例的结构化程序只需要简单的输入，如数字，比 生成测试用例的面向对象的程序要简单明了，这是该项目的目标之一。 s t a k n i s 提出了深度测试可被用于自动化测试领域，其优点是减少软件测试的时间， 精力，劳力和成本【2 】。自动测试工具包括一般的测试生成器，测试工具和测试数据生成 软件。d e m i l l o 指出的静态分析工具，无论是手动或自动的情况下都可分析测试软件下 不执行的代码【3 1 。它是一种有限的计划，其中包含数组引用，指针变量和其他动态结构 分析技术。实验已经表明，这种代码检查对发现评价静态分析是非常有效的，可寻找3 0 至7 0 的逻辑设计和编码得典型的软件错误。 与静态分析相反，动态测试工具涉及的软件执行是根据软件测试和依赖软件实现生 成测试数据的反馈。采取原软件的逻辑预防措施，以确保这些额外的指令没有任何影响。 g a l l a g h e rm j 是描述该方法的一位杰出代表，使用仪器将信息返回给测试数据生成系统 的各种变量，路径谓词和+ 测试覆盖率的状态【4 】。使用函数计算一个分支谓词约束值是 目前的测试数据的手段。关于分支谓词有三种类型的测试数据生成器：路径，数据说明 书和随机测试数据生成器。测试仪上运行下的软件测试，作为测试用例的实际输出，其 输出并且被储存。该方案经过测试仪检查输出，并决定是否是正确的，通过比较实际输 出与预期输出来实现。如果输出是不正确的，错误已被发现，程序必须改变，必须重新 进行测试。这将导致回归测试执行以前所有的测试数据必须经过验证，修正无新的错误 出现。 我国常年致力于软件测试自动化领域的专家教授也研究出许多行之有效的测试用 例自动生成的方法。汪浩等人提出遗传算法的形式化表示，并建立了基于此种算法的测 试用例自动生成的简单系统模型，通过与一个具体的简单测试单元相互结合，给大家提 出了遗传算法的参数编码序列、适应度函数的构造及驱动化模块自动生成方法等关键性 问题【5 】。d b i r d 等采用随机法自动生成测试用例，而c r a m a n m o o r t h y 等人和p d c o w a r d 提出的都是符号执行法【6 - 9 】。金虎【1 0 】等人针对遗传算法在基于面向路径的测试用例的自 动生成策略中的应用进行了深入的研究，得出面向路径的遗传算法来实现测试用例的自 动生成。 兰州交通大学硕士学位论文 1 。3 本文的主要工作 这一研究项目的总体目标是研究遗传算法的有效性，并自动生成测试数据并且遍历 所有分支机构的软件。研究活动的目标可以定义如下： ( 1 ) 需要基本知识来促进开发新的技术进行自动检测： ( 2 ) 使用遗传算法自动生成测试数据的各种数据类型变量和复杂的数据结构，并对 软件测试的可行性进行评估； ( 3 ) 分析遗传算法在各种情况下的性能，如大型系统； ( 4 ) 简单的自动数据采集( a d a ) f 拘随机测试软件开发下的遗传算法的有效性的比 较； ( 5 ) 复杂的软件程序的自动测试： ( 6 ) 充分利用突变检测分析测试数据； ( 7 ) 遗传算法应用在自动生成测试数据的小程序的性能进行评估和分析。遗传算法 库的开发，然后应用到更大的系统； ( 8 ) 遗传算法生成测试数据的效率相比随机测试生成的测试数据的数目和所需的 c p u 时间的比较分析； 该研究项目使用了一个系统生成的测试数据编写软件。针对测试数据生成的问题， 形成一个数值优化问题，采用遗传算法和结构测试技术彻底解决他们。软件测试是在一 个域内来满足测试标准的搜索和生成特定的测试数据。遗传算法是在一个给定的过程 中，根据测试得到的测试集产生一个既定的搜索并且在优化过程中会遍历所有的分支的 方法。 这篇论文是标准的测试分支的测试。我们的目标是开发测试系统行使的每一个分支 下的软件测试。为了生成分支测试所需的测试数据，使用遗传算法和随机测试。这两个 测试技术将被比较通过覆盖他们每个分支都可以实现的百分比，并有充分的分支覆盖率 已经达到之前生成的测试数据的数量。 1 4 论文结构 本文共分为6 章。 第1 章主要介绍课题的背景和研究意义，国内外的研究现状，并提出研究目标和主 要工作。 第2 章主要介绍一些软件测试的基本问题，对软件测试的各种测试方法和应用进行 评论。并检查和解释了这些技术的优点和缺点。 第3 章主要介绍遗传算法的总体思路。介绍遗传算法，并给出他是如何以及为什么 基于遗传算法软件测试用例自动生成分析与研究 工作，并用一个例子来解释。对g a 所使用的各种运算符和程序的解释。针对遗传算法 的重要和必要的问题进行了阐述。 第4 章是本文的重点，论述了如何将遗传算法应用于指定路径的测试用例的自动生 成当中，并在此基础上结合改进的适应度函数开发了一个可用的工具。首先介绍了系统 的整体框架；然后阐述了g a 算法的实现过程中的关键技术，具体包括参数的编码、适应 度函数的构造、遗传算子的改进方法等。 第5 章是运用了具体程序实例进行实验，成功生成了有针对性的测试数据，验证了 遗传算法的可行性，同时对结果数据作了比较分析。揭示了特定的错误的存在或不存在， 并检测测试数据集和测试工具的充分性。该算法的一个显着的改善是考虑到随机测试所 需的测试次数。该技术需要到少于两个数量级的测试和较少的c p u 时间。 第6 章对本课题的主要研究成果和未完善的诸多问题进行了总结，并针对存在的这 些问题指出了下一步的工作重点。 兰州交通大学硕士学位论文 2 软件测试及其测试方法 2 1 软件测试 软件测试是一种最常用的软件的质量评估方法。面向对象的软件测试时，有两个重 要的过程。首先，该软件已被初始化为一组值，这些值用于设定一个数字相关的测试用 例的变量。这些变量定义为一个单独的状态值，从尽可能多的软件种群中得到。这些值 可以是原始值，如整数；或复杂的值，如对象。软件初始化后，就可以进行测试，其测 试方法是通过调用定义过的变量值。如果一个方法需要一个或多个对象作为参数，这些 对象也要被初始化。要确定是否测试用例通过或失败，那么软件规范就要被使用。软件 规范未列明什么是有效的输入，则可能有一个软件的可能状态的数目是指数，它是不可 能测试所有这些输入的值。在实践中，有趣的状态是正常识别由开发商设定一个软件规 范，程序结构或自己的经验决定。然而有许多类型的测试都可以根据c l a s s i c 版“黑盒或 白盒“ 测试来完成。 2 1 1 黑盒测试 黑盒测试也称功能测试，会考虑被测单元作为一个黑盒子送入数据和输出数据，是 一个被证实的软件规范。该功能测试具有的优点在于它是从源代码脱开，根据给定的软 件指定的规范，可以生成测试数据，甚至在已实施的功能当中。功能测试必须与用户的 需求密切相关，因为它是要测试一个程序的函数。它的主要缺点是，它需要一个软件规 范，它可能在无法探索的单位下测试，因为它不知道被测试代码结构。在黑盒子测试中， 被测程序的内部结构和行为是不被考虑的。我们的唯一目标是找出不匹配其规范程序的 输入输出行为。在这个过程中，软件的测试数据是从它的规范中被构建 i h 3 】。黑盒测试 的强度可以在软件开发周期的早期得出。它可以检测到缺少的逻辑故障【1 4 1 。该软件被视 为一个黑盒子，它的功能是提供输入测试数据的各种组合。黑盒测试也被称为功能性或 规格为基础的测试。与此相反，是白盒测试。 2 1 2 白盒测试 白盒测试技术，也称为结构测试，将考虑到代码的内部结构。通过分析代码的结构， 根据不同的测试数据可以被生成，探讨这些特定的区域。结构测试也可能被用来衡量多 少代码已经被覆盖在一些结构标准中。在程序的执行流和路径中l 个代码覆盖率要被分 析，并且可以给予一定的标准，如语句覆盖，计算执行的语句独特的计算。 在白盒测试中，被测程序的内部结构和行为需要被考虑。软件结构的检查通过执行 基于遗传算法软件测试用例自动生成分析与研究 的代码来完成。测试数据均来自程序的逻辑结构。这也被称为基本测试或结构测试【l 5 1 ， 此方法在软件的覆盖率上提供反馈。有几个白盒( 结构) 测试标准： ( 1 ) 语句测试：软件的每个语句至少执行一次测试过程，而一个更广泛和更强的策 略是分支测试。 ( 2 ) 分支测试：是比语句覆盖，分支覆盖更为强大的测试标准。它需要将所有的输出 结果至少进行一次遍历，即控制程序中的每一个可能的转移遍历【1 6 】。这意味着，执行所 有的控制传输，它包括语句覆盖，就是将程序中的每一个语句都执行一次。然而，在一 个特定的顺序下，有些错误可能不能被检测到，从而导致执行路径测试的语句和分支覆 盖的不完整。 ( 3 ) 路径测试：在测试所有可能的路径下执行的软件测试，这增加了检测错误的概率， 比起语句测试和分支测试是一个更强大的方法。通过软件的路径可以被描述为在关系到 软件的输入变量的谓词的联合。但是，路径测试通常被认为是不切实际的，因为循环语 句的程序可以具有无限数量的路径。当存在一个输入该路径遍历的程序执行期间，这个 路径被说成是“可行的”，但是其他的路径就被说成是“不可行”的。 2 2 测试数据自动生成 自动化测试过程中产生测试数据并执行测试用例以实现自动化。现在已经有一些自 动化测试的情况在执行，但主要的问题在于测试数据生成的自动化工具，除了已有进化 的测试，还有一些工具在自动化测试过程中使用静态分析，软件模型和随机测试。随机 测试是被广泛采用的方法和工具，但也有很多算法的性能比随机算法更能优化问题。 深度测试可被用于自动化测试领域【1 7 】。其优点是减少软件测试的时间，精力，劳力 和成本。自动测试工具包括一般的测试生成器，测试工具和测试数据生成软件。 静态分析工具，无论是手动或自动的情况下都可分析测试软件下不执行的代码。它 是一种有限的计划，其中包含数组引用，指针变量和其他动态结构分析技术。实验已经 表明，这种代码检查( 目视检查) 的评价被发现静态分析是非常有效的，可寻找3 0 至 7 0 的逻辑设计和编码当中典型的软件错误。符号执行和评估是一个典型的静态生成测 试数据的工具。 许多自动化测试数据生成是基于符号执行的【博】。符号执行通过解释这些语句的符号 和路径的谓词名，提供了一个功能表示，即在一个程序的路径分配的输入值的符号名和 路径的评估。符号执行需要系统的表达式的推导，可以提高计算能力。作为符号名的代 数表达式中的所有变量的保持值。每个程序变量的值被确定在每个节点唯一未知的程序 输入的值，一个符号式( 表达式) 的流图作为一个变量的符号表达式进行足够的信息表 兰州交通大学硕士学位论文 示，例如，一个数值可以为变量，如果这个数值分配为输入值，这就是所谓的符号计算。 符号执行的特点是符号表达式的生成和显示的必然要求就是执行一定的路径或分 支【憎j 。符号执行的结果是一组输入变量的等式和不等式约束，这些约束可能是线性的或 非线性的，并定义在输入空间的一个子集中，这将导致所选择的路径的执行；如果符号 表达式解决的测试路径是可行的，并将该执行对应于一组输入数据，这将为测试执行路 径。如果没有办法可以解决，那么测试路径是不可行的：操纵代数表达式，在计算上是 昂贵的，尤其是当大量的路径上执行；常见的问题依赖于循环条件变量，输入变量依赖 于阵列( 有时只在运行时的值) 的参考标，模块调用和指针。 这些问题放慢了符号执行的成功应用，特别是如果有很多的限制相结合，通过检查 程序，如果程序有输出的计算的数学公式符号，那么一些程序错误很容易被识别。在这 样的事件中，输出结果对公式来看，仅是进行检查他们的匹配度。 与静态分析相反，动态测试工具涉及的软件的执行是根据软件测试和依赖的软件实 现生成测试数据的反馈 2 0 , 2 1 】。采取原软件的逻辑预防措施，以确保这些额外的指令没有 任何影响。使用的仪器将信息返回给测试数据生成系统的各种变量，路径谓词和测试覆 盖率的状态。使用函数计算一个分支谓词约束值是目前的测试数据的手段。关于分支谓 词有三种类型的测试数据生成器：路径，数据说明书和随机测试数据生成器。在测试仪 上运行下的软件测试，作为测试用例的实际输出，其输出并且被储存。该方案经过测试 仪检查输出，并决定是否是正确的，通过比较实际输出与预期输出来实现。如果输出是 不正确的，错误已被发现，程序必须改变，必须重新开始测试。这将导致回归测试执行 以前所有的测试数据必须经过验证，修正无新的错误。 回归测试定义为重新测试先前的程序并作以下修改，以确保未被发现的故障或检查 未做更改的结果【2 2 1 。为了完成测试，测试仪将手动检查，以确定它们是否是将正确的测 试用例输出。使用整数和实变量为基础规则的测试方法。他的系统使用先前的测试输入 数据产生额外的测试数据。测试数据发生器【2 3 】直接分配值的条件的输入变量与常量，然 后由少量值的递增和递减输入值的一倍来更接近边界。所得在快得多的时间内通过搜索 空间减半。最后每一次的一个输入变量被设置为一个随机数。 这个项目的结果是，以规则为基础的方法几乎总是比随机进行来得好。迪森称他的 方法是多条件边界线覆盖多条件测试数据，决定出行使条件的所有可能组合( t r u e 和f a l s e ) 的结果。这里指的是测试数据具有尽可能接近的切换的条件从t r u e 改为f a l s e 边界。他 提到的是不可能的生成测试数据，这将导致会去执行任意软件中的所有分支，即没有算 法存在求解一般非线性谓词。此外，他的方法只限于数字类型，如整型数据类型。基于 有规则的方法的缺点是存在不可预见的问题，它可能是难以实现的。如果不存在这样的 基于遗传算法软件测试用例自动生成分析与研究 规则，生成的测试数据可以结束在一个局部最优解，而不是在一个全局性的解决方案， 它会遍历每一个分支。 2 2 1 路径测试生成器 路径测试数据生成系统测试软件的测试标准是它可以是路径覆盖，语句覆盖，分支 覆盖，系统会自动根据选择要求来生成测试数据的。一个路径测试信号发生器由程序控 制流图，路径选择和测试数据生成工具组成。 确定性启发式已被提出。他使用一个动态的测试数据生成方法，是根据路径测试数 据发生器【2 4 】自动定位为一个选定的路径被遍历的输入变量的值。他的步骤是很程序的控 制流图构建和测试数据生成。在路径选择阶段是不使用的，因为如果不可行的选择路径， 其结果是浪费在努力计算研究这些路径上。大多数这些方法使用符号评估，以生成测试 数据。该方法是基于数据流分析和函数最小化的方法，它是基于被测试的软件的执行来 生成测试数据。由于被测试的软件被执行时，数组的索引和指针的值是已知的软件中执 行的每个点，这就克服了象征性评价的问题和局限。 上述方法形成分支谓词控制流的一个分支功能。这些功能是依赖于输入变量来表示 代数可能是困难的，但可以通过程序的执行确定值。现在的想法是，尽量减少这些分支 功能的同时，正值所需的分支不会被执行。只要其值将变为负的分支，就能满足最小的 分支功能的要求，应执行的节点的同级节点，路径，将会被保留为下一个的测试数据。 一个布尔条件是带有一个真实的和一个虚假的节点的两个分支，见图2 1 。同级节点是 参考节点，其他节点对应于目前的执行节点，例如，同级节点中“真正的分支”是“假 分支“ 。 图2 1 同级节点 这种生成测试数据的方法是基于交替变量的方法，该方法包括最小化当前分支，依 次输入一个增加或是减小的输入变量，来完成探索搜索以及大量的图案搜索。这样做的 效果是下列之一： ( 1 ) 分支中的函数值在减少的方向上继续进行用于改变一个已知变量，并保持这个 基于遗传算法软件测试用例自动生成分析与研究 浅灰色区域，而子域的节点2 包括浅灰色区域( 节点2 ) 附加的对角线( 节点3 ) 。 域测试是指用来检查是否是子域的边界段，正确测试域由该软件执行测试数据以找 到数据流中的错误【2 6 1 。这些测试数据被划分成一组属于在软件中的某个路径的子域的输 入空间。这些结构域的边界是通过以下方式获得：边界段是由一个单一的路径条件创建 的边界的路径条件中的谓词。 i f a - ，- ，1 中的一个。此外，应该可以做到假定一些谓词不含有诸如a n d ，o r 和其它关系运算。然后再应用等式谓词把每一个分支谓词都给代换掉： fr e l0 在此处的f 表示的是函数的标准值，即“分支函数“ 。f 和r e l 为表4 1 所示。 由以上概念不难看出分值函数的正负是由分支谓词的假与真来判断的，要是把分支 基于遗传算法软件测试用例自动生成分析与研究 量化的难题解决掉，就完全可以构造出适应度函数依据已有的分函数。进一步推算的“分 支函数叠加方法”是在谓词函数的基础上构造适应度函数最常用的方法。 针对分支函数叠加给以较大的改善，即将g o l d b e r g 函数的线性拉伸技术应用于针对 分支函数叠加法推算出的个体适应度函数当中，促使个体和个体之间体现出比较大的差 别。这样才能很好的表现出参数的优劣程度在比较的时候。g o l d b e r g 的线性拉伸适应度 函数如下： 八x ) ： ；二! 上季生厂( x ) + 警丘曙 ( 4 5 ) j i n x 。 jo v g j i n x j 4 v 霉 其中，f ( x ) 是经过线性拉伸处理过的，该适应度函数是基于目标函数拉伸变换推算得出； 丘在目前的种群里是最好的值；z 坦是目前的种群中每一个子值均等适应度值；c 是常 数，c 的选取来自实验。 4 2 3 遗传算子的改进 ( 1 ) 自适应交叉 在个体层面上交叉操作可施加在交叉算子之前，即个体可以被转换成二进制表示。 在交叉过程中，两个亲本( 染色体) 交换信息( 遗传物质) 的子字符串在染色体上的随 机位置产生两个新的字符串( 后代) 。交叉算子寻找更好的基因内的遗传物质。这里的 目标是创造更好的个体，随着时间的推移得到更好的个体( 更健康) 从母体相结合中获 得。 在前文中介绍的交叉方法有单一交叉，双交叉和均匀交叉。单一交叉和双交叉在交 叉操作中方法简单，就是将个体在交叉点处切割成了小断片，而均匀交叉意味着父母的 每一个位可以根据一些概率来选择，通过父代多个位交换创建后代，通过这样做可以有 效减少二进制码和目标参数特殊码之间的差距。 综上，我们针对前面讲到的“多参数级联编码”这个实用性问题，对交叉算子做以有效改进提 出了自适应交叉算法。在自适应交叉算法里，通过控制交叉率p 来得到个体交叉点的选取，经试验 验证只不适宜固定常数值，因为会降低整体搜索力。所以本文采用交叉率为： 叶一亨：麓 【 只i 曙 ( 4 6 ) 其中，f 眦代表适应度函数在群体里函数值最大；c 曙代表适应度函数在种群的每一代 里的平均值；f 代表适应度函数值在需要交叉个体中那个偏大的；只，只：代表交叉率 在初始化时候的第1 ，2 代。 兰州交通大学硕士学位论文 采用此交叉率能够将所有参数位串进行高效的交叉运算，可以完成单点交叉和多点 交叉两不误的任务，完全避免了传统交叉的低效性，使得搜索效率大大的提升。 ( 2 ) 自适应变异 有了前面选择和交叉操作的阐述可以看出这两种操作在遗传算法中的重要地位，然 而不进行变异操作就很难保证重要的遗传信息会被遗漏。变异是偶然的随机改变的位值 来改变某些功能不可预测的后果。在二进制代码中，这意味着只是改变一个基因的状态， 从0 到1 或反之亦然。变异是通过搜索空间向一个随机状态游走，是用来维持种群的多 样性，使种群过早地收敛于一个( 本地) 解决方案。变异可以避免局部最优的和创建的 可能不存在的遗传物质，因为它是在目前的种群中永远不存在的，又或者是因为它丢失 了由交叉产生的运算操作符。当我们把变异和交叉巧妙地结合应用时，它就能成为保护 遗传当中重要遗传信息不丢失的保障策略。 变异率己的大小对于种群的多样性的优劣起到至关重要的作用，当变异率只较大 的时候群体多样性表现良好且具有概率很小的过早成熟现象，但是如果当变异率只特别 大的时候，就会发现遗传算法就会完全变成传统的随机搜索算法，种群进化很慢导致效 率极低。反言之，变异率只特别小的话也是不能达到高效搜索的目的。所以本文采用变 异率为： 絮予曙 ( 4 7 ) 。a v g f 代表适应度函数值所属的变异个体：己。，己：代表变异率在初始化时候的第1 、2 代。实验表明这样的变异率就可以达到自适应变化的目的。 针对以上变异率的详细的操作方法就是计算每个个体的变异率只，个体位串上的所 有基因位都会被o 1 区间里的任意常数所代替，假使某个个体的变异率只大于该个体基 因位的替代常数，我们就需要对这样的重要位给以变异操作，反之则不对其进行变异操 作。 假定个体变异率己推算出的值是o 0 1 ，对于8 位的基因编码来说生成的8 个随机数 如下：0 2 0 6