（计算机科学与技术专业论文）基于数据流分析的测试用例自动生成技术.pdf

中文摘要 摘要 软件测试是保障软件质量的重要手段，软件测试在软件开发中的地位也日益 重要。其中数据流技术作为一种白盒测试技术，能提供充分的代码覆盖，已经被广 泛应用到面向对象软件测试中，但是已有的数据流测试技术主要关注生成测试方 法序列，而不能提供具体的数据驱动方法进行测试，也就不能实现测试的自动化。 虽然已有的随机测试用例生成器支持自动测试，但其测试用例的生成过程没有与 测试需求结合起来，测试用例的生成具有盲目性，从而导致生成的测试用例不能 很好地覆盖需求。 针对以上问题，本文将数据流分析与遗传算法结合起来提出了一种基于数据 流分析的测试用例自动生成技术，该技术综合了数据流技术与遗传算法的优点。 我们的方法扩展了数据流测试技术，它可以利用遗传算法的搜索能力以保证生成 的测试数据具有充分的定义使用覆盖。 本文从软件测试的相关概念入手，并比较介绍当前一些测试用例生成技术。 然后提出我们的基于数据流分析的测试用例自动生成技术。然后本文再给出了该 技术的原型系统的设计与实现，大量实验结果表明，该技术无论在搜索时间，覆 盖率还是生成测试用例的有效性上都优于随机算法与单纯的数据流技术。最后我 们总结并展望了未来工作的发展方向。 关键字：自动测试；数据流测试；数据流分析；遗传算法；c f g 英文摘要 a b s tr a c t s o f t w a r et e s t i n gp l a y si n c r e a s i n g l yi m p o r t a n tr o l et oe n s u r et h es o f t w a r eq u a l i t yi n s o f t w a r ed e v e l o p m e n t d a t a f l o wt e s t i n gi saw h i t e b o xt e s tt e c h n i q u et h a th a sb e e n w i d e l ya p p l i e dt ot e s to b j e c t - o r i e n t e ds o f t w a r ew i t hs u f f i c i e n tc o d ec o v e r a g e b u tt h e e x i s t i n gr e s e a r c hw o r km a i n l yc a r e st h ec o m p u t a t i o no fm e t h o ds e q u e n c e s ，r a t h e rt h a n f e a s i b l et e s td a t at or u nt h e s es e q u e n c e s t h a t ss a y t h e yc a n ts u p p o r ta u t o m a t i ct e s t i n g a l t h o u g ht h ee x i s t i n gr a n d o mt e s td a t ag e n e r a t o r sc a l lc r e a t et e s td a t aa u t o m a t i c a l l y , t h e g e n e r a t i o np r o c e s si sb l i n dy e te s s e n t i a l l yn o n - g o a ld r i v e n ，i tm a yg e n e r a t eu n f e a s i b l e t e s td a t aa n dt h u sf a i lt oc o v e rt h ei n t e n d e dt e s t i n gr e q m r e m e n t s t os o l v et h i sp r o b l e m ，t h i st h e s i sp r e s e n t sa l la u t o m a t i ct e s td a t a g e n e r a t i o n t e c h n i q u et h a tt a k e st h em e r i t so fg e n e t i ca l g o r i t h m ( g a ) a n dd a t a f l o wa n a l y s i s o u r m e t h o de x t e n d st h ed a t a f l o wt e s t i n gt e c h n i q u ei nt h a ti te x p l o i t st h es e a r c l l i n gc a p a b i l i t y o fg aw i t ht h ea i mt os u f f i c i e n t l yc o v e rt h ed e f - u s ep a i r s t h i st h e s i ss t a r t sw i t hs o m ec o n c e p t sa b o u ts o f t w a r et e s t i n ga n dt h ei n t r o d u c t i o no f c u r r e n tt e c h n i q u e sf o rg e n e r a t i n gt e s tc a s e s n e x tw ep r e s e n to u ra u t o m a t i cd a t a f l o w t e s t i n gm e t h o d ，w h i c hc o n s i s t so ft h ed a t a f l o wc o m p u t a t i o na n dt h ed t g aa l g o r i t h m t h e nw ed e s c r i b et h ed e s i g na n d i m p l e m e u to fo u rp r o t y p es y s t e m e x p e r i m e n t a lr e s u l t s s h o wt h a to u rm e t h o dc a nw o r kw e l lo nw e l lo na v a r i e t yo fp r o g r a m s ，o u t p e r f o r m r a n d o mg e n e r a t i o na n dp u r ed a t a f l o wt e s t i n gt e c h n i q u ei nt e r m so fr u n n i n gt i m ea n d c o v e r a g er a t e i nt h ee n dw ec o n c l u d ea n ds u g g e s to u rf u t u r ew o r k k e yw o r d s ：a u t o m a t i ct e s t ；d a t a f l o wt e s t i n g ；d a t a f l o wa n a l y s i s ，g e n e t i c a l g o r i t h m ；c f g 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成硕士学位论文竺基王数握逋坌扳的测达旦趔自动生盛遮苤：。除论文中 已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中 以明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公开 发表或未公开发表的成果。本声明的法律责任由本人承担。 学位论文作者签名：翌墨垄： 学位论文版权使用授权书 本学位论文作者及指导教师完全了解大连海事大学有关保留、使用研究生学 位论文的规定，即：大连海事大学有权保留并向国家有关部门或机构送交学位论 文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫 描等复制手段保存和汇编学位论文。同意将本学位论文收录到中国优秀博硕士 学位论文全文数据库( 中国学术期刊( 光盘版) 电子杂志社) 、中国学位论文全 文数据库( 中国科学技术信息研究所) 等数据库中，并以电子出版物形式出版发 行和提供信息服务。保密的论文在解密后遵守此规定。 本学位论文属于：保密b 在l 年解密后适用本授权书。 不保密函( 请在以上方框内打“ ) 做作者躲邓乞褒导师躲1 0 牡， 日期：加矽年岁月多日 基于数据流分析的测试用例自动生成技术 第1 章绪论 1 1 研究背景与发展现状 软件测试是保障软件质量的重要手段，软件测试在软件开发中的地位也日益 重要。然而软件测试是一项费时、费力并且单调乏味的活动，测试人员需要设计、 执行、分析大量的测试用例。所以实现软件测试的自动化将可以有效地减轻测试 人员的劳动强度，提高测试的效率和质量，从而节省软件开发的成本，提高软件 的质量。 数据流测试技术【l - 9 】是一种基于代码的白盒测试技术，它能提供充分的代码覆 盖，已经被广泛应用到面向对象软件测试中。m a r yj e a nh a r r o l d 1 】等人提出的对类 进行的数据流测试技术，通过生成控制流图( c o n t r o lf l o wg r a p h ) 辅助数据流计 算，使用计算的数据流关系指导测试用例的选择。该技术的主要优势就是能对整 个类进行数据流测试。通过测试可以找到黑盒测试【l o 。1 3 1 覆盖不到的错误，该技术 甚至在没有规约的情况下可以确定应当执行哪些方法序列去测试一个类，而避免 了测试一些不必要的方法序列。y o g e s hs i n g h l 9 等人提出的通过契约理念加强数据 流分析，该技术通过规约得到类流 ( c l a s sf l o wg r a p h ) ，然后应用传统的数据流技 术选择测试用例。契约理念使我们可以只测试那些可行的方法或者方法序列，即 只有当方法的前置条件得到满足后才执行相应的方法序列，由于程序中的许多条 件都转换为前置条件的一部分，这样就大大减少被测数据流信息。上述技术作为 数据流测试技术能提供充分的代码覆盖，发现黑盒测试不能覆盖的错误，然而它 们主要关注的都是如何安排测试方法序列进行测试，而不能提供具体的数据驱动 方法进行测试，也就不能支持自动测试【1 4 】。虽然已有的随机技术【1 5 】能自动生成测 试用例，但是其测试需求没有与测试过程结合起来，测试用例的生成具有盲目性， 所以生成的测试用例不能很好的覆盖测试需求。 针对以上问题，本文将数据流技术与遗传算法【1 纠8 】( g e n e t i ca l g o r i t h m ) 结合 起来提出了一种基于数据流分析的测试用例自动生成技术。首先作为数据流技术 其可以提供充分的代码覆盖，其次遗传算法作为面向目标的搜索技术，使测试用 第1 章绪论 例的生成过程与测试需求结合在一起，加强了搜索的方向性，能快速搜索有效测 试用例覆盖测试需求( 数据流信息) ，实现了数据流测试的自动化。 1 2 研究内容 针对当前数据流技术以及随机技术存在的问题，本文将数据流技术与遗传算 法结合起来提出了一种基于数据流分析的测试用例自动生成技术。本文的研究目 的就是实现数据流测试的自动化，实现的技术既能提供充分的代码覆盖，又能快 速地自动生成测试用例覆盖测试需求。该技术以控制流图( 方法控制流图与类控 制流图) 辅助数据流计算，计算结果作为测试需求。以方法序列生成器( m e t h o d s e q u e n c eg e n e r a t o r ) 生成测试方法与测试方法序列，即我们的测试对象。为实现 自动测试，我们构造数据类型结构图( d a t av y p es t r u c t u r eg r a p h ) 用来自动创建类 的实例驱动方法进行测试。为实现数据流测试的自动化，本文需要研究以下内容： 一、分析当前的数据流测试技术以及其它测试用例生成技术的优势与不足， 提出用遗传算法自动化数据流测试。既实现充分的代码覆盖又实现了测试的自动 化。 二、解析被测程序，构造其抽象语法树，这是生成其它图形结构的基础。 三、运用抽象语法树构造数据流测试所需的图形结构：控制流图，方法调用 层次图，方法序列生成器，数据类型结构图。 四、在控制流图上进行数据流分析，得到测试需求。 五、实现遗传算法搜索测试用例覆盖测试需求。 六、将实现的数据流测试框架应用到大量实验，统计其覆盖率，搜索时间， 迭代次数以及测试用例规模。分析并比较该框架的性能。 1 3 论文结构 本文共分七章，除本章外其它各章的内容概括如下： 第2 章为“软件测试技术概述”，在本章将详细介绍软件测试的相关概念和 与软件测试技术的分类，并介绍一些典型的软件测试技术。 第3 章为“遗传算法”，在这一章中详细介绍遗传算法的基本概念与流程，并 - 2 - 基于数据流分析的测试用例自动生成技术 介绍遗传算法在软件测试中的应用。 第4 章为“基于数据流分析的自动测试技术，这也是是本论文的重点，将 详细介绍如何实现类的自动化数据流测试。 第5 章为“自动数据流测试系统设计与实现 ，主要介绍本文的数据流测试 框架与框架中各子模块的具体实现。 第6 章为“实验结果与分析”，本章通过大量的实验将本文的自动化数据测 试技术和随机技术以及单纯数据流技术进行了比较，实验结果表明，该技术无论 在搜索时间，覆盖率还是生成测试用例的有效性上都优于随机算法与单纯的数据 流技术。 第7 章为“结论 ，该部分总结了本文已完成的工作，并展望了下一步的研 究内容。 基于数据流分析的测试用例自动生成技术 第2 章软件测试技术概述 2 1 软件测试相关概念 随着信息技术的飞速发展，软件产品广泛应用在社会各个领域，软件产品的 质量成了软件产品的生命力所在。而软件测试1 9 之3 1 作为保障软件质量的重要手段， 其在软件开发中的地位也变得日益重要。软件测试是指使用人工或者自动手段来 运行或测试某个系统的过程，其目的在于检验它是否满足规定的需求或弄清预期结 果与实际结果之间的差别。从软件测试的定义可以看出，软件测试是一个过程， 可以分为手动测试与自动测试，测试的目的就是选择合适的测试用例覆盖测试需 求或检验期望结果其实际结果的差别。下面我们将介绍软件测试的一些重要概念。 2 1 1 测试用例( t e s tc a s e ) 所谓测试用例就是为某个特殊目标编制的一组测试输入、执行条件以及预期 结果，以便测试某个程序路径或核实是否满足某个特定需求。可见测试用例包括 输入数据和期望结果两部分。般说到测试用例生成时，由于期望结果构造的困 难性，我们都侧重或仅生成输入数据，此时可称之为测试数据【1 9 j ( t e s td a t a ) 。 测试用例可以指导测试的实施，在实施测试之前设计好测试用例可以避免盲 目测试并提高测试的效率，使测试重点突出，目的明确。测试用例的设计应遵循 以下原则【2 0 】： ( 1 ) 准确性：测试用例的设计必须有明确的目标，即针对需求设计测试用例。 ( 2 ) 可复用性：设计的测试用例应能在类似的情况下重复使用。可复用性在回归测 试中显尤为重要，这样我们可以利用已有的测试用例设计新的测试用例。 ( 3 ) 可追踪性：测试用例必须能追溯到需求。 ( 4 ) 完整性：考虑到需求的完整性和逻辑完整性。 2 1 2 测试需求( t e s tr e q u jr e m e n t ) 任何测试都对应着测试需求，测试需求是测试的覆盖目标。简单地说，测试 需求就是我们要“测什么”。例如测试一个哈希表的插入操作，可以有如下测试需 求：( 1 ) 插入一个新的条目；( 2 ) 插入失败：条目已经存在：( 3 ) 插入失败：表 第2 章软件测试技术概述 已满；( 4 ) 哈希表在插入前为空。这样我们就可以按照测试需求设计测试用例。 在本文中，我们的测试需求是数据流信息，即定义使用对的集合。测试用例与测 试需求的对应关系可以是一对一或者一对多，即一个测试用例可以覆盖一个测试 需求或多个覆盖需求。 2 1 3 测试充分性准则( t e s ta d e q u a c yc ri t e ria ) 软件测试的充分性是根据被测软件在有限多个测试数据上的行为判断在所有 测试数据上的行为的逻辑基础。测试充分性准则是判定测试数据集对于被测程序 是否充分的准则。良好的软件测试充分性准则应该具有如下基本性质【2 4 】： ( 1 ) 空集不充分性：空测试对任何软件都是不充分的。 ( 2 ) 有限性：对任何软件都存在有限的充分测试集合。 ( 3 ) 单调性：如果一个软件系统在一个测试数据集合上的测试是充分的，那么再多 一些测试数据也应该是充分的。 ( 4 ) 非复合性：即使对软件所有成分都进行了充分的测试，也并不意味着整个软件 的测试已经充分了。 ( 5 ) 非分解性：即使对一个软件系统整体的测试是充分的，也并不意味着软件系统 中各个成分都已经充分地得到了测试。 ( 6 ) 软件测试的充分性应该与软件的需求和软件的实现都相关 ( 7 ) 复杂性：软件越复杂，需要的测试数据就越多。 ( 8 ) 回报递减律：测试得越多，进一步测试所能得到的充分性增长就越少。 目前，通常用测试覆盖准则度量测试充分性。现在已经提出许多针对程序内 部结构的测试覆盖准则，主要包括控制流测试覆盖准则和数据流测试覆盖准则。 控制流测试覆盖准则包括语句覆盖、分支覆盖、条件覆盖、判定条件覆盖、路径 覆盖等。数据流测试覆盖准则包括定义覆盖、使用覆盖、定义使用覆盖等准则。 本文采用的就是数据流覆盖准则。测试覆盖准则不仅可以定量地规定软件测试需 求，指导测试数据的选择，而且可以度量测试数据集揭示软件特定特征的能力， 对测试结果和软件可靠性评估具有重要影响【2 l ，2 2 1 。 - 6 - 基丁二数据流分析的测试用例自动生成技术 2 2 软件测试技术分类 按照不同的分类准则，软件测试技术有不同的分类方法。 2 2 1 静态测试与动态测试 按照运行状态，可将软件测试技术分为静态测试和动态测试【1 9 】( 图2 1 ) 。其 中静态测试是在不执行程序代码而寻找程序代码中可能存在的缺陷或评估程序代 码的过程。静态测试又可分为代码审查、代码走查以及对程序进行的静态分析。 图2 1 软件测试技术的分类 f i g 2 1c l a s s i f i c a t i o no f t h es o f t w a r et e s t i n gt e c h n o l o g i e s 动态测试则以测试数据为输入，通过执行程序来检验程序的动态行为和运行 结果以发现缺陷。动态测试包括生成测试用例、运行程序和验证程序的运行结果 三部分核心内容。而如何生成测试用例是动态测试的关键。按照生成测试数据的 依据可将动态测试分为白盒测试、黑盒测试、灰盒测试。其中白盒测试是基于程 序的测试，又称为结构测试，它以程序的内部结构特性设计测试数据，主要包括 第2 章软件测试技术概述 控制流测试，数据流测试以及程序插装技术。控制流测试以控制流为覆盖需求， 包括语句覆盖、分支覆盖，条件覆盖等。而数据流测试则以数据流关系为覆盖需 求，即覆盖程序中的定义与使用。本文提出的技术就是白盒测试中的数据流技术。 黑盒测试又称功能测试，是基于规约的测试技术，即根据程序的需求规约来确定 测试数据，测试人员无须了解程序的内部结构，直接根据程序输入和输出之间的 关系推断测试结果的正确性。黑盒测试又包括：等价类划分、因果图、判定表、 边值分析等。灰盒测试程序是白盒测试与黑盒测试的结合。 2 2 2 单元测试、集成测试、系统测试 按被测试对象粒度可将软件测试分为单元测试、集成测试以及系统测试。其 中单元测试( u n i tt e s t i n g ) 是集中对源代码实现的每一个程序单元进行测试，检查各 个程序模块是否正确地实现了规定的功能。集成测试( i n t e g r a t e dt e s t i n g ) 则把已 测试过的模块组装起来，主要对与设计相关的软件体系结构的构造进行测试。系 统测试( s y s t e mt e s t i n g ) 把已经经过确认的软件纳入实际运行环境中，与其它系 统成份组合在一起进行测试。在面向过程程序中，单元测试一般是对一个函数方 法的测试，而在面向对象程序中，单元测试一般为类中的一个方法。 2 3 测试技术介绍 随着软件工程的发展，相应的软件测试技术也取得了长足的发展。其中自盒 测试技术中的控制流测试与数据流测试成为了主要的测试技术。由于测试用例的 生成过程也是搜索过程，即在测试用例空间中搜索合适的子空间去覆盖测试需求， 所以各种搜索技术，如遗传算法、随机技术被广泛应用到测试用例生成中。下面 我们将详细介绍这些技术。 2 3 1 基于随机算法的控制流测试技术 基于随机算法的控制流测试技术的主要特点是：从测试用例空间中随机选择 测试用例，直到覆盖所有的控制流信息。其中控制流信息可以是语句集，分支集 合，路径集等。例如我们可以随机生成测试用例去覆盖一条选定的特定路径。一 般而言控制流的覆盖都以程序的控制流图为指导。文献1 5 , 2 3 , 2 6 】都是基于随机算法的 控制流技术。 - 8 - 基于数据流分析的测试用例自动生成技术 由于随机算法本身的缺陷，即搜索空间大，所以可能产生很多用例，并且测 试用例的生成过程没有与测试需求信息很好地协调，这样可能找不到满足需求的 测试用例。对于选定的路径不可达时，生成器也找不到覆盖路径的测试用例。 2 3 2 基于遗传算法的控制流测试技术 遗传算法( g e n e t i c a l g o r i t h m ) 是面向目标的搜索技术，将遗传算法运用到测 试用例生成，就是不断对已有的测试用例进行评价，然后从中选择那些认为优良 的个体交给遗传操作( 交叉，变异) 生成新测试用例的过程，其中对测试用例进 行评价的依据就是控制流信息，例如测试用例覆盖的语句数目，覆盖路径以及与 目标路径的相似度等。由于评价操作的加入，遗传算法搜索的针对性和方向性都 强于随机算法。文献 1 6 , 1 7 , 1 8 ，2 7 2 8 ，2 9 1 都是基于遗传算法的测试技术，虽然这些技术运 用遗传算法大大减少了测试用例的搜索空间，但它们都只是在遗传算法的层面上 进行的一些改进，例如对评价函数，交叉率，变异率的改进，并没有将测试过程 很好地与程序本身进行结合。 2 3 3 数据流测试技术 所谓的数据流测试就是测试程序中变量的定义与使用，即我们生成的测试用 例的执行路径应该覆盖从变量定义到其使用的子路径。数据流测试技术能提供充 分的代码覆盖已经被广泛应用到软件测试中。文献 1 - 5 , 7 , 9 】都是基于数据流的测试技 术。 m a r yj e a nh a r r o l d 1 】等人提出的对类进行的数据流测试技术，通过生成控制流 图( c o n t r o lf l o wg r a p h ) 辅助数据流计算，使用计算的数据流关系指导测试用例 的选择。该技术的主要优势就是能对整个类进行数据流测试。通过测试可以找到 黑盒测试【1 0 。1 3 1 覆盖不到的错误，该技术甚至在没有规约的情况下可以确定应当执 行哪些方法序列去测试一个类，而避免了测试一些不必要的方法序列。y o g e s h s i n g h 9 1 等人提出的通过契约理念加强数据流分析技术，该技术通过规约得到类流 图( c l a s sf l o wg r a p h ) ，然后应用传统的数据流技术选择测试用例。契约理念使我们 可以只测试那些可行的方法或者方法序列，即只有当方法的前置条件得到满足后 才执行相应的方法序列，由于程序中的许多条件都转换为前置条件的一部分，这 第2 章软件测试技术概述 样就大大减少被测数据流信息。这些数据流测试技术虽然能提供充分的代码覆盖， 发现黑盒测试不能覆盖的错误，然而它们主要关注的都是如何安排测试方法序列 进行测试，而不能提供具体的数据驱动方法进行测试，也就不能支持自动测试【h 】。 2 4 类的自动测试 在面向对象程序中，类是基本构造单元，所以类的测试并是面向对象程序测 试的关键 3 0 , 3 1 , 3 2 】。但是，面向对象程序设计语言特有的封装、继承、多态等机制增 加了面向对象软件测试的难度，尤其是面向对象软件中存在的复杂引用关系给自 动测试带来了如下困难： ( 1 ) 要实现类的自动测试，我们需要能自动创建类的实例，然后才能驱动类的方 法进行测试。 ( 2 ) 为创建类的实例，需要调用其构造方法，此时需要知道构造方法的参数信息： 参数个数，参数类型。对于其中为引用类型的参数需要进一步确定其构造方法的 形式，这样数据类型之间并形成了复杂的层次结构。 ( 3 ) 为自动驱动方法，我们同样需要知道其复杂的参数层次结构。 ( 4 ) 类由成员方法构成，而方法的调用序列是任意的、是无限的，那么对类达到 什么程度的测试可以认为是充分的。 针对类的自动测试现状和面临的问题，本文都提出了相应的解决方案，最终 实现了类的自动数据流测试。 2 5 本章小结 本章介绍了软件测试的相关概念和软件测试技术的分类方法，并介绍了当前 主要的软件测试技术：基于随机算法的控制流测试技术，基于遗传算法的控制流 测试技术，数据流测试技术。同时比较了这些软件测试技术的优缺点。表2 1 为 它们之间的比较结果。可以看出：数据流测试技术能提供充分的代码覆盖但却没 有实现测试的自动化，而遗传算法是高效的搜索算法能大大减少搜索空间。这两 点也正是本论文的切入点，即本论文综合遗传算法与数据流测试的优点，实现数 据流测试的自动化。 基于数据流分析的测试用例自动生成技术 表2 1 主要软件测试技术比较 t a b 2 1c o m p a r eo fd i f f e r e n tt e s t i n gt e c h n i q u e s 式 基于随机算法的控制 基于遗传算法的控制 数据流测试技术 比较点流测试技术流测试技术 覆盖目标 控制流信息控制流信息数据流信息 搜索空间大 小不定 自动化是 是 否 代码覆盖程度中等 中等 高 在本章最后，我们分析了实现类的自动测试所面临的困难，而解决这些困难 并是实现类的自动数据流测试的关键，这也是本论文的亮点所在，在后面章节我 们将详细介绍我们的解决方案，并详细介绍如何实现类的自动测试。 基于数据流分析的测试用例自动生成技术 第3 章遗传算法 3 1 遗传算法基本概念 遗传算法 3 4 - 4 2 1 ( g e n e t i c a l g o r i t h m ) 是模拟达尔文的遗传选择和自然淘汰的生 物进化过程的计算模型，它将“适者生存”的进化理论引入串结构，并在串之间 进行有组织但又随机的信息交换。通过遗传操作，使优良品质被不断保留、组合， 从而不断产生出更佳的个体，子代个体中包含父代个体的大量信息，并在总体上 胜过父代个体，从而使群体向前进化发展，即不断接近最优解。 由于遗传算法是自然遗传学与计算机科学相互渗透的产物，因此借用了很多 自然进化的基础术语。 概念3 1 个体( i n d i v i d u a i ) ：模拟生物个体而对问题中的对象( 一般就是问 题的解) 的一种称呼，一个个体也就是搜索空间中的一个点。 概念3 2 种群( p o p u ia tio n ) ：模拟生物种群而由若干个体组成的群体，它一 般是整个搜索空间的一个很小的子集。种群规模是指种群中个体的数目。 概念3 3 适应度( f i t n e s s ) ：借鉴自然界中生物个体对环境的适应程度，而对 问题中的个体对象所设计的表征其优劣的一种测度。对生存环境适应度高的生物 将获得更多的繁殖机会，反之，机会少甚至被淘汰。 概念3 4 适应度函数( fi t n e s sf u n o tio n ) ：问题中的全体个体与其适应度之 间的一个对应关系。它一般是一个实值函数。该函数就是遗传算法中指导搜索的 评价函数。 概念3 5 染色体( c h r o m o s o m e ) ：问题中个体的某种字符串形式的编码表示， 它是遗传物质的主要载体。字符串中的字符称为基因或遗传因子( g e n e ) 。 概念3 6 编码与解码：遗传算法中两个必需的数据转换操作，其中把搜索空 间中的参数或解转换成遗传空间中的染色体或个体的操作称为编码( c o d i n g ) 操作， 反之，称为解码( d e c o d i n g ) 操作。 遗传算法包括选择、交叉和变异三个遗传操作，它们作为遗传进化的主要过 程使优良品质被不断保留、组合，从而不断产生出更佳的个体，使群体向前进化 第3 章遗传算法 发展。下面将给出三个操作的具体含义。 概念3 7 选择( s e i e c t i o n ) ：从种群中选择优胜的个体，淘汰劣质个体的操作， 它是建立在种群中个体的造应值的基础上，目的足把优化的个体遗传到f 一代。 选择操作有不同的选择策略。主要有轮盘选择法与适应值比例选择法，轮盘 选择方法是将一个圆分为种群大小个扇形区间，区间大小与该区| 日j 所代表的染色 体的适应度成诉比。设一固定指针，转动轮盘，等其自然停i 卜后，看指针指向哪 个区间，则树应的染色体被选中。相应的轮黜如图3 1 所示： 图3 i 轮盘选择法 f i 9 3 1r o u l e t t ew h e e ls e l e c t i o n 适应度比例选择法也是常用的选择方法，它要求适应度函数大于零，并且只能针 对求解适应度函数最大的问题，适应度越大的染色体被选种的机会也越大，设日为 染色体，只( h ) 表示时刻克时染色体在群体中所占比例，则在选择阶段，每个染色 体根据它的适应度被选择，染色体日的选中概率为： 最州) 竽州日) 蒜 g ( 3 1 ) 其中为群体适应度值，可见，染色体的适应度值越高，它被选中的机会越 大。 概念3 8 交叉操作( c r o s s o v e r ) ：通过一对双亲个体r i l 的遗传信息进行随机 重组，产生与双亲遗传信息相i 同、组合不同的新个体。 交叉操作的主要目的就是在解空间中搜索不同的可 j 二解。进行交义操作的具 基于数据流分析的测试用例自动生成技术 体形式依赖于采用的个体遗传信息编码方式，对于二进制位串编码方式，有单点 交叉和多点交叉。图3 2 ，图3 3 分别为单点交叉与多点交叉示意图。图3 2 中只 选择一个交叉点( 第5 到第7 位) ，图3 2 选择了两个交叉点。 图3 2 单点交叉 f i g 3 2o n e p o i n tc r o s s o v e r 图3 3 多点交叉 f i g 3 3m u l t i - p o i n tc r o s s o v e r 概念3 9 变异操作( m u r a ti o n ) ：单独改变个体内一个或者多个基因座上的基 因而产生新的个体。 变异操作用于补偿当前种群中基因种类的丢失，尽管它也用于改变遗传算法 对解的搜索能力，但它的主要作用是保持种群中个体的多样性。以二进制基因编 码的一位变异操作( o n e b i tm u t a t i o n ) 为例进行说明，如图3 4 所示，将变异位置 上的基因从1 刹跳为0 ( 若为0 就翻跳为1 ) ，于是一种新的肇凶被注入到子代种 群中，同时也j 忆 1 - 了一个新的个体。 c 口, o1 , 1o,i l,o i 固口正匝 图3 4 一位变异 f i g 3 4o n e - b i tm u t a t i o n 第3 章遗传算法 概念3 10 交叉率( c r o s s o v e rr a t e ) ：参加交叉运算的染色体占本种群染色体 总数的比例，记为p c ，取值范围通常为0 4 0 9 9 。 概念3 11 变异率( m u r a tio nr a t e ) ：发生变异的基因位数所占本种群染色体 的基因总位数的比例，记为p m ，取值范围通常为0 0 0 0 1 0 1 。 3 2 遗传算法流程 遗传算法的流程如图3 5 所示： 是 矗磊、 、，。， 图3 5 遗传算法流程 f i g 3 5t h ep r o c e s so fg e n e t i ca l g o r i t h m 算法首先将实际问题参数集编码成位串，得到初始种群，将初始种群作为当 前种群，定义适应度函数计算个体适应度，对当前种群进行遗传操作得到子代种 基于数据流分析的测试用例自动生成技术 群，然后判断终止条件是否满足，是则退出遗传算法，否则继续进行迭代。其中 终止条件有两种：一是预先定义一个进化种群代数m a x g e n ，如果进化代数超过 m a x g e n 终止进化过程，此时称为非满意终止，即遗传算法没有找到最优解。二是 全局最优解已经找到，也终止进化过程，此时称为满足终止。 3 3 测试技术中的遗传算法 遗传算法是面向目标的搜索技术【1 6 】，将遗传算法运用到测试用例生成，就是 不断对已有的测试用例进行评价，然后从中选择那些认为优良的个体交给遗传操 作生成新测试用例的过程。此时遗传算法的种群是一个固定数目的测试用例集合， 而种群中的个体就是一个测试用例，遗传算法的求解目标是生成覆盖一定测试需 求的测试用例集合。在不同的遗传算法测试技术中定义不同的适应度函数和不同 测试需求。文献1 8 1 基于程序依赖定义适应度函数，其选择语句覆盖作为测试需求。 而文献【l6 】基于路径相似度定义适应度函数，选择路径覆盖为测试需求。 3 4 本章小结 本章我们详细介绍了遗传算法中的一些重要概念，如种群，个体，编码解码 以及遗传算法的选择、交叉、变异操作等，这些概念都是实现遗传算法的重要实 体。另外本章还详细介绍了遗传算法的普遍流程：算法首先创建初始种群，然后 定义适应度函数对种群中的个体进行评价得到每个个体的适应度，根据适应度进 行选择操作，然后进行交叉与变异，最后直到终止条件得到满足结束算法。在本 章最后，我们还介绍了遗传算法在测试技术中的运用，为本文提出的技术做好铺 挚。 基于数据流分析的测试用例自动生成技术 第4 章基于数据流分析的自动测试技术 4 1 数据流测试基本概念 所谓数据流测试【4 3 4 6 1 就是测试程序中的数据流关系，即测试程序中的变量定 义与变量使用，测试目标是生成测试用例覆盖这些数据流关系。本文提出的数据 流测试技术综合了数据流分析与遗传算法的优点，该技术用数据流分析技术得到 数据流关系，亦即我们的测试需求，然后在数据流关系的指导下运用遗传算法搜 索合适的测试用例覆盖该需求，最后实现了数据流测试的自动化。下面我们将详 细介绍本文提出的数据流测试中的一些重要概念。 4 1 1 变量定义与变量使用 程序中出现的变量，我们可以分为两类，即变量定义( d e f ) 与变量使用( u s e ) 。 下面我们给出变量定义、变量使用【4 7 1 以及相关概念的确切定义。 定义4 1 变量定义设a 是一个赋值语句，v 为a 中被赋值的变量，那么此时 v 为关于v 的变量定义，以( v ，a ) 记之。其中a 标记该变量定义出现的位置。 定义4 2 变量使用设a 是程序中一条语句，v 为8 中出现的变量，并且此时 不是对v 的赋值，那么v 为关于v 的变量使用。如果8 为计算性语句，即为计算 某值而使用v ，例如a 为赋值语句、输出语句，此时我们称该变量使用为计算使用 ( c o m p u t e ru s e ) ，简记为c u s e 。如果a 为谓词判断语句，如i f 条件判断，此时 该变量使用称为谓词使用( p r e d ic a r eu s e ) ，简记为p u s e 。 定义4 3 定义一使用对( d e f - u s ep a ir ) 设a ，b 为程序中的语句，( v ，a ) 为关于变量v 的变量定义，( v ，b ) 为关于同一变量v 的变量使用，并且存在从语 句a 到语句b 的可执行路径，那么( v ，a ，b ) 称为关于变量v 的定义一使用对。 我们以图4 1 中的t h r e e n u m 为例阐述上面的概念( 若无特别说明，本文都以 图4 1 中程序为例) 。例如在t h r e e n u m 中的第9 行，赋值语句m a x = a 对变量m a x 进 行了重新赋值，同时使用了变量a 的值，所以( m a x ，9 ) 为关于变量m a x 的变量 定义，而( a ，9 ) 为关于变量a 的变量使用( 在这使用语句行号代表对应的语句) 。 注意到在程序的第8 行，变量a 和变量b 的使用出现在谓词判断a b 中，所以( a ， 第4 章基于数据流分析的自动测试技术 8 ) 与( b ，8 ) 分别为关于变量a 与变量b 的p u s e 。另外( m a x ，1 3 ，1 4 ) 为关于 变量m a x 的一个定义一使用对。 p u b l i cc l a s st h r e e n u m p u b l i ci n ta , b 。c ，m a x ； p u b l i ct h r e e n u m ( i n ti , i n tj ，i n tk ) a = i ： b = j ； c = k ； p u b l i ci n tm a x ( ) ；f ( a b ) m a x = a ； e l s e m a x = b ； i f ( c m a x ) 1 3 m a x = c ； 1 4r e t u r nm a x ； 1 5 p r i v a t ev o i dm i n u s o n e 0 1 6a - - a l ： 1 7b = b i ： 1 8 c = c - i ； 1 9 p u b l i ci n tm a x a f t e r m i n u s 0 2 0 m i n u s o n e 0 ； 2 1 m a x ( ) ； 2 2r e t u r nm a x ； 2 3 l 图4 1 类t h r e e n u m f i g 4 1c l a s st h r e e n u m 按d e f 与u s e 出现的位置关系，我们将d e f - u s ep a i r 分为三类【l 】：单一方法内定 义一使用对( s in gie m e t h o dd e f - u s ep air ) ，交互方法定义一使用对 ( in t e r a c tiv e - m e t h o dd e f - u s ep air ) ，方法序列定义一使用对( s e tia 卜m e t h o d d e f - u s ep air ) 。在下面定义中，假设类c 是被测试的类，v 是该类中出现的一个 变量，d ，u 分别是类c 中包含变量v 定义与使用的语句，并且( v ，d ，u ) 构成关 于变量v 的定义使用对。 定义4 4 单一方法内定义一使用对假设m 是类c 中的方法，而d 和u 是m 内 分别包含变量v 定义与使用的语句，那么( v ，d ，u ) 就是单一方法内定义一使用 对，简写为s i md e f - u s ep a i r 。s i md e f - u s e 出现在同一方法内部。 定义4 5 交互方法定义一使用对假设m o 是类c 中的公有方法，而( m l ，m 2 ， m n ) 是被m o 直接或间接调用的方法集合。如果d 是m i 中关于变量v 的定义语句， u 是m i 中对同一变量v 的使用语句，并且m i ，m j ( m o ，m l ，m e ，m 。) ，那么( v ，d ，u ) 为交互方法定义一使用对，简写为i n md e f - u s ep a i r 。i n md e f - u s ep a i r 出现在方法 l 2 3 4 5 6 7 8 9 m “眩 基于数据流分析的测试用例自动生成技术 中调用方法的情况下。 定义4 6 方法序列定义一使用对假设m o 是类c 中的公有方法，( m l ，m 2 ，m n 是被m o 直接或间接调用的方法。n o 是类c 中的公有方法， b 中。方法m a x a f t e r m i n u s 中2 1 行调用了m a x 方法，而m a x 方法中的1 3 行 定义了变量m a x 。注意到该m a x 值被2 2 行的返回语句使用，所以( m a x ，1 3 ，2 2 ) 是i n md e f - u s ep a i r 。当调用方法序y l j 时，m a x a t t e r m i n u s 方法调用的m i n u s o n e 的1 6 行定义了变量a ，而m a x 方法的第8 行p u s e 了变量a ， 所以( a ，1 6 ，8 ) 是s e md e f u s ep a i r 。 我们测试的目标就是生成测试用例去覆盖这些d e f - u s ep a i r s ，所谓覆盖了某 d e f - u s e ( v ，d ，u ) ，就是当以生成的某测试用例驱动程序执行时，导致了从定义语 句d 到使用语句u 的路径执行，并且该路径上没有对变量v 的重新定义。对d e f c u s e 来说，执行的路径从定义到使用语句即可，而对d e f - p u s e 来说，必须执行其所有 分支所代表的子路径。例如我们要覆盖关于a 的定义一使用对( a ，4 ，8 ) ，那么我们 需要覆盖i f 语句的两条分支，即覆盖8 ，9 以及8 ，1 1 所在子路经。 4 1 2 类测试的层次 对类的数据流测试就是覆盖类中的数据流信息，由前面知道类的数据流信息 分为三类，而覆盖这三类数据流信息分别对应着对类三个层次的测试，即： 单一方法测试( s i n g i e - m e t h o dt e s t i n g ) ：