（计算机软件与理论专业论文）进化测试中嵌套ifelse和函数调用结构的适值函数设计.pdf

摘要 进化测试是近年来兴起的非常重要的一种自动化测试数据生成技术。进化测 试的主要思想是将测试数据的生成问题转化成为进化搜索问题，从而实现测试的 自动化。进化测试利用进化算法的全局搜索能力，在具有导向性的适值函数的引 导下，能够快速高效的自动生成测试数据。 适值函数是进化测试中非常重要的一个方面。一个设计良好的适值函数能够 为进化搜索提供更好更准确的导向，从而提高进化搜索的效率。因此适值函数一 直是进化测试领域的研究热点。许多设计良好的适值函数被应用到进化搜索中。 但是对于嵌套i f - e l s e 结构，由于其特殊的多层嵌套结构，当测试数据在某一 层中偏离了目标分支时，嵌套在该层内的其它分支将不再执行而在此时直接计算 适值。这种情况导致测试数据在内层未执行的分支上的满足程度信息的丢失。造 成了对测试数据的不公平评价。针对这个问题，本文借鉴可测变换的思想，提出 分支乐观度的概念。通过分支乐观度来计算测试数据在未执行的分支上的累积分 支距离。通过将规格化后的分支乐观度加入到原有的适值函数中，一种针对嵌套 i f - e l s e 结构的适值函数被成功提出。 当测试目标的执行涉及到函数调用结构时，现有的适值函数就不再适用。这 是由于，现有的适值函数的静态分析仅仅针对测试目标所在的函数内部，而没有 考虑测试目标对函数调用的依赖。针对这种涉及函数调用的测试目标，本文通过 对函数调用的静态分析，突出在函数调用链上的关键分支认定方法，提出了函数 逼近度的概念。函数逼近度用来衡量测试数据在函数调用依赖链上对测试目标的 满足程度。最终，本文为涉及函数调用的测试目标提出了一种新的适值函数。 通过实验检验证明，本文针对嵌套i f - e l s e 结构和函数调用结构提出的两种适 值函数都能够更有效的引导进化搜索，提高搜索效率。 关键词：软件测试自动化测试数据生成进化测试适值函数 a b s t r a c t e v o l u t i o n a r yt e s t i n gi s ap r o m i s i n gt e c h n o l o g yf o rt h ea u t o m a t i ct e s t d a t a g e n e r a t i o n i tr e f o r m u l a t e st h et e s td a t ag e n e r a t i o np r o b l e mi n t oa ne v o l u t i o n a r ys e a r c h u n d e rt h eg u i d a n c eo faf i t n e s sf u n c t i o n aw e l l d e s i g n e df i t n e s sf u n c t i o ni sc r u c i a lt o t h ee f f i c i e n c ya n de f f e c t i v e n e s so fe v o l u t i o n a r ys e a r c h m a n ye f f o r t sh a v e b e e nd i r e c t e da tt h ed e s i g no ff i t n e s sf u n c t i o n h o w e v e r , i nt h e p r e s e n c eo ft h en e s t e di f - e l s ec o n s t r u c lt h ee x i s t i n g f i t n e s sf u n c t i o nc a n n o t 僦l y e v a l u a t et e s td a t a s i n c ef o rt h en e s t e di f - e l s ec o n s t r u c t ，o n c et e s td a t ad r i v et h ep r o g r a m e x e c u t i o ni n t ot h eb r a n c ht h a tw i l ld e f i n i t e l yc a t l s et h et a r g e tt ob em i s s e d ，t h ep r o g r a m e x e c u t i o nw i l lb ee n d e da n dt h ef i t n e s sw i l lb ec a l c u l a t e d i nt h i sc a s e ，t h ei n n e r b r a n c h e so ft h eb r a n c hw h e r et h ed i v e r g e n c eh a p p e n sc a nn o tb ee x e c u t e d ，a n dt h u st h e s a t i s f a c t i o no ft h et e s td a t ao nt h e s eb r a n c h e sc a nn o tb ea s s e s s e d i n s p i r e db yt e s t a b i l i t y t r a n s f o r m a t i o n ，an e wf i t n e s sf u n e t i o ni sp r o p o s e df o rt h en e s t e di f - e l s ec o n s t r u c tw i t ha n e wt e r mo p t i m i s ml e v e lt or e c o r dt h ea c c u m u l a t e db r a n c hd i s t a n c e so f t h et e s td a t ao n t h eu n e x e c u t e db r a n c h e s w h e nf u n c t i o nc a l l se x i s ti nt h ed e s i r e de x e c u t i o nt r a c et ot h et a r g e t ，t h ee v a l u a t i o n o ft h et e s td a t ao nt h ec o v e r a g eo ft h e s ef u n c t i o nc a l l s ，w h i c hs h o u l db ep r o v i d e dt ot h e e v o l u t i o n a r ys e a r c h ，i sn o tc a p t u r e db yt h ee x i s t i n gf i t n e s sf u n c t i o n i nt h i sc a s e ，t h e e x i s t i n gf i t n e s sf u n c t i o nc a nn o tf a i f l ye v a l u a t et h e t e s td a t a a n dt h ee v o l u t i o n a r y s e a r c hw i l lb eh a m p e r e do re v e nf a i li ns e v e r ec a s e s i nt h i st h e s i s ，an e wt e r mf u n c t i o n l e v e li sf i r s tp r o p o s e dt o i n c o r p o r a t ei m ot h ee x i s t i n gf i t n e s sf u n c t i o n i ti sa p p l i e dt o e v a l u a t et h et e s td a t a sc o v e r a g eo ff u n c f i o nc a l l sa l o n gt h ed e s i r e dp a t ht ot h et a r g e t e x p e r i m e n t sv a l i d a t e dt h ee f f e c t i v e n e s so f t h ef i t n e s sf u n c t i o n sp r e s e n t e di nt h i s t h e s i sa n dd e m o n s t r a t e dt h e i re f f i c i e n c y k e y w o r d ：s o f t w a r et e s t i n g a u t o m a t i ct e s td a t ag e n e r a t i o n e v o l u t i o n a r yt e s t i n g f i t n e s sf u n c t i o n 西安电子科技大学 学位论文创新性声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在导 师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注 和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果； 也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明 并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：经盟日期壶坚蔓：! ：i 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保留 送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容， 可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后结合 学位论文研究课题再攥写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 套赏篓耋需巯一本人签名：堡型 导师签名：羔牛 年解密后适用本授权书。 日期 日期 第一章绪论 第一章绪论 1 1 研究工作 本文的研究工作来源于西安电子科技大学软件工程研究所承担的某“十一五 国家项目，该项目主要针对提高软件可信的手段与技术进行研究。 随着现代信息技术的飞速发展，软件在越来越多的工程应用中扮演着至关重 要的角色。因此，软件系统的质量成为人们愈加关注的问题f 1 。在实际工程应用中， 任何一个细小的软件错误都可能给我们带来巨大的甚至是致命的损失，特别是在 大量的安全应用系统中，关键时刻的软件错误不仅可能导致无法挽回的致命损失， 往往还威胁到人的生命安全。然而由于软件系统自身的复杂性和软件开发人员思 维的局限性，在开发过程中出现软件错误是不可避免的。所以，我们若能及早发 现并排除软件系统中的错误，就可以避免不必要甚至是令人无法容忍损失的发生 并提高软件系统的安全性。软件测试作为一种有效的软件质量验证方法在工程界 中得到了广泛使用，并因此在整个软件开发过程中占据了非常重要的地位l l j 。 随着软件规模的不断扩大，软件测试的工作量也随之增大。有研究表明，在 整个软件系统开发过程中，软件测试或系统测试大约占用5 0 的项目时间和超过 5 0 的总成本【1 1 。软件测试在整个软件开发过程中占用如此高比例的项目时间和成 本，制约着整个软件开发过程的发展。软件测试从类别上分为黑盒测试和白盒测 试。黑盒测试主要从用户的角度检测软件系统的实现是否满足预定的要求。但若 想在更高的层次上对软件质量进行保证，则需要对程序中的逻辑进行测试。白盒 测试是对程序代码进行的一种测试，致力于发现程序代码中的逻辑错误。因此， 白盒测试是软件质量保证中的一种重要方法。 在白盒测试中，测试数据生成是非常重要但又非常烦琐的一个环节。在传统 的白盒测试中，测试数据需要通过手动生成。测试人员通过阅读大量被测代码， 对其进行分析推敲，而后再设计测试数据对被测程序进行测试。这种测试数据的 手动生成技术极大的限制的白盒测试以及整个软件测试技术的发展，延缓了软件 开发过程。同时，由于人工的阅读代码，导致很多程序的死角无法被发现，使得 应用系统潜藏着致命缺陷的程序的存在成为可能。因此，测试数据自动生成技术 应运而生1 2 1 。测试数据自动生成技术致力于加快软件系统开发速度，降低软件开发 成本，提高软件质量，并将测试人员从大量的手动测试中解放出来。 自动化测试数据生成技术开始于2 0 世纪九十年代，包括美国航天局，i b m ， 戴姆勒克莱斯勒奔驰公司等研究机构或公司就已展开了自动化软件测试技术的 进化测试中嵌套i f - e l s e 和函数调用结构的适值函数设计 研究。其中，进化测试技术就是戴姆勒克莱斯勒奔驰公司所倡导的一项新兴且具 有潜力的测试数据自动生成技术【2 ，3 ，4 ，5 1 。进化测试技术将测试数据的生成问题转化 成最优化搜索问题。进化测试技术在被测程序指数级别的测试输入空间内，利用 进化算法，在有效的适值函数的引导下，可以搜索到覆盖指定目标的测试数据。 包括本课题在内的众多实践表明【6 ，7 】，进化测试能够在巨大的测试输入空间中根据 覆盖准则以较低的代价自动生成高质量的测试数据，从而发现软件错误。因此， 在本项目的研究中，本文致力于研究通过进化测试技术为被测程序在白盒测试的 分支覆盖准则下自动生成高质量的测试数据，从而更好的发现软件错误。 1 2 国内外研究现状 进化测试技术从二十世纪九十年代发展至今取得了长足的进步。世界各国学 者和研究机构对其倾注了大量的研究精力。由于本文致力于进化测试中适值函数 的研究，因此本节主要介绍进化测试中适值函数的发展历程。 在进化测试研究的初始阶段，由于所利用的静态信息也较少，因此为进化搜 索定义的适值函数相对简单和粗糙，基本上只根据程序的控制流结构设计简单适 值函数。而2 0 0 1 年是进化测试研究领域中具有里程碑意义的一年，这一年以戴姆 勒一克莱斯勒奔驰公司j o a c h i mw e g e n e r 研究员等为代表的研究人员首次将结构化 测试中的适值函数加以分类，划分为面向节点的适值函数，面向路径的适值函数， 面向节点节点的适值函数以及面向节点一路径的适值函数四种例。并且首次将程序 的控制流和程序的数据流加以综合，定义了面向分支覆盖测试的适值函数【引。并且 研制出自动化测试工具，该工具可针对c 语言代码自动生成满足指定白盒覆盖准 则的测试数据集合。目前，这个工具已被戴姆勒一克莱斯勒一奔驰公司大量应用 于嵌入式系统的测试数据生成中，并处于不断研究完善中。2 0 0 1 年之后，针对结 构化测试的适值函数向着更加细致的方向发展，包括对面向对象程序的进化测试 技术【9 】、针对“状态 问题【1 0 , 1 1 , 1 2 、标志变量问题【1 3 , 1 4 , 1 5 】、以及非结构化程序中的 标志变量问题的研究1 6 , 1 7 。本课题组针对状态问题【l o 】，标志变量问题f 1 3 】，嵌套i f - e l s e 结构问题【1 8 】，和涉及到函数调用的适值函数设计【1 9 】问题进行了研究。相应的研究 成果和论文被第2 0 届i e e e a c m 的自动化软件工程会议( a s e2 0 0 5 ) 、第1 2 届i e e e 的亚太软件工程会议( a p s e c2 0 0 5 ) 、a c m 的国际遗传与进化会议( g e c c o 2 0 0 7 ) 、第1 4 届i e e e 的亚太软件工程会议( a p s e c2 0 0 7 ) 收录。 尽管从上述分析可以看出进化测试在国外正处于如火如荼的发展中，而且应 用的领域也在不断地扩展，但在国内仍然处于研究的起步阶段，采用的进化算法 也相对单一，而且定义的适值函数相对简单，应用也仅仅停留在测试数据生成这 一领域，还有待深入的研究。 第一章绪论 1 3 研究问题 在进化测试中，元启发式搜索算法是在适值函数的引导下去搜索测试数据的。 因此，适值函数设计的好坏对进化搜索的过程有着至关重要的影响作用。自动化 测试技术提出至今，适值函数的设计与实现始终都是该领域的研究热点。大量的 研究学者和机构将精力放在适值函数的设计上。迄今为止，已有针对结构化测试 而提出的各种适值函数公式，针对标志变量问题而提出的统一适值函数计算规 则，针对非结构化程序的标志变量问题的适值函数计算方法等等。 本文的工作主要有两个方面。首先本文针对嵌套i f - e l s e 结构的适值计算问题 就行了研究。虽然，现有的适值函数公式可以用来为这种结构进行指导并生成测 试数据，然而由于多层嵌套的问题和适值函数自身的局限性，测试数据无法在内 层的分支上进行充分的评价。因此，针对这个问题，本文通过对程序的静态分析， 对原有的适值函数进行了修改，以适应嵌套i f - e l s e 结构。其次，由于本项目一直 致力于单元测试，而当测试目标不是在被测程序的入口函数时，现有的适值函数 计算方法也就不再适用，这是由于没有对函数的调用流进行分析，同时，函数的 调用流也没有被参考进来。本文作者也同样针对这个问题进行了研究。 1 4 论文的组织结构 本文共分为六章。第一章为绪论部分，主要讨论了本文的研究背景，国内外 研究现状，本文所研究的问题和主要工作。第二章简要介绍了进化测试技术的基 本知识，定义了与本文工作相关的若干基本概念，并给出了进化测试中的适值函 数计算公式。第三章讨论了嵌套i f - e l s e 结构的适值函数计算问题。通过对嵌套 i f - e l s e 结构的控制流分析，同时又借鉴了可测变换技术的思想，提出了一种更适 用于嵌套i f - e l s e 结构的适值函数，使得进化搜索能够为嵌套i f - e l s e 结构更有效的 生成测试数据。第四章针对涉及函数调用的测试目标的适值函数进行了讨论，提 出在函数调用序列上关键分支的认定方法，引入函数逼近度使得在函数调用级别 上对测试数据加以评价成为可能，从而为进化搜索提供更有效的导向。第五章为 实验验证。首先介绍了进行实验验证时使用的进化测试工具的基本框架结构，描 述了适值函数计算工具的设计与实现。然后并分别针对嵌套i f - e l s e 结构和基于函 数调用流的适值函数公式进行了实验检验。实验结果表明，本论文所提出的适值 函数能够的确能够更为有效的引导进化搜索为本文研究的特定的程序结构生成测 试数据。第六章对本论文进行了总结并对进一步的工作进行了展望。 第二章进化测试技术 5 第二章进化测试技术 进化测试是近年来兴起的一种以进化算法为基础的测试用例自动生成技术。 它通过将测试数据的生成问题转化为最优化搜索问题，将一定测试准则下的测试 目标作为该搜索问题的全局最优化目标，并在基于静态信息的适值函数的引导下， 利用进化搜索算法强有力的全局寻优能力，在巨大的几何空间中找到所需的测试 数据。 2 1 进化测试 自从上个世纪七十年代以来，如何自动地为被测程序生成测试数据便一直是 软件工程师的重要研究课题之一，然而，由于软件测试数据自动生成一般情况下 是一个不可判定问题，因此，这个领域的进展一直非常缓慢。即使在工程实践中 实际有意义的程序都是有限状态的，其测试数据搜索空间仍然随着程序输入参数 个数的变化以及参数取值范围的变化而成指数级增长。故而，在这样一个指数级 爆炸的测试输入空间中，显然不可能进行穷举搜索。只有应用启发式算法，我们 才有可能在近似多项式的时间内找到满足指定覆盖准则的测试数据。然而，由于 测试输入本身的非线性，测试数据的搜索空间往往是不连续的、非线性的、多峰 的，在这种情况下，类似模拟退火等邻居搜索算法往往就很容易陷入局部最优解， 从而导致搜索测试数据的失败，为了跳出局部最优解而发现全局最优解，进化算 法例如遗传算法等被广泛用于测试数据的自动生成。 进化算法是建立在自然遗传以及达尔文生物进化理论基础上的的自适应搜索 技术【2 0 , 2 1 j 。其中，遗传算法( g e n e t i ca l g o r i t h m ) 借鉴生物界的进化规律，如适者 生存，优胜劣汰等机制，演化而来的搜索方法。它的主要特点它的全局寻优能力。 遗传算法己被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和 人工生命等领域【2 2 ，2 3 j 。 而在软件测试领域的应用，其主要思想在于将测试数据的生成问题转换为最 优化的搜索问题。首先需要将测试目标转换为搜索的目标。并根据测试目标定义 目标函数( 即适值函数) 来对个体的优劣进行评价。进化测试生成测试数据的过 程也就是整个种群不断进化，迭代的过程，直至定义的搜索目标出现或者终止条 件已经满足。整个进化测试过程如下。 种群中的第一批个体被随机产生，被测程序中的参数被编码成种群中的个体。 首先，将种群中的个体解码为参数并作为输入来执行被测程序，通过监控被测程 6 进化测试中嵌套i f - e l s e 和函数调用结构的适值函数设计 序的执行，被测程序的参数对目标的偏离程度将为种群中的个体计算出适值。然 后，进化算法根据个体的适值来进行选择哪些个体将作为父本来生成下一代，在 这里主要利用进化算法中的交叉算子和变异算子。需要注意的是，在生成下一代 中的个体对应的参数也要在被测程序的输入范围内。生成的下一代对应的测试数 据同样需要作为被测程序的输入来被考核并依据进化算法的选择标准被回插入到 待进化的种群中。从此开始，整个进化过程将反复进行，一直到生成目标测试数 据或者满足进化算法的终止条件。整个进化测试的过程可由图2 1 表示。 图2 ，i 进化测试流程图2 3 i 2 2 基本概念 由于涉及到众多专业术语和概念，本节先给出若干基本术语和概念的定义。 控制流图是静态分析方面的一个基本概念，如定义2 1 所示。 定义2 1 【2 4 】：一个程序f 的控制流图g 指的是有向图g = ( n ，e ，s ，e ) ， 其中n 是一个节点集，而e 则是一个边集，s 和e 分别表示了该图唯一的入口 和出口，每一个节点n n 都是程序中的一个状态，比如条件语句或者赋值语句， 两个节点之间存在一条边e = ( n i ，n j ) e ，当且仅当它们之间存在一个从节点n i 到 节点n j 的控制迁移。 定义2 2 ：一个程序中具有相同执行条件的语句组称为一个分支( b r a n c h ) ，即 b r a n c h = s l ，s 2 ，s k ，其中s j 和s j 是具有相同执行条件的程序语句。 在进化测试的面向节点测试类别中，一个测试目标通常指的是控制流图g 上 的一个节点或者分支。由测试目标和分支的定义出发，我们可以得到关键分支 ( c r i t i c a lb r a n c h ) 的定义。 第二章进化测试技术 7 定义2 3 ：关键分支指的是在控制流图上导致测试目标被偏离的分支【2 5 1 ，为了 提高处理嵌套在循环中的测试目标的情况，在进化测试中，循环内部偏离测试目 标的分支也被称作关键分支。 图2 2 一个根据控制流图计算分支逼近度的例子，其中虚线表示关键分支 例如图2 2 是一个控制流图的一部分，假设测试目标为节点6 ，则因为在控制 流图上节点1 中为真的分支和节点4 中为假的分支都能够使得测试目标被偏离， 因此它们都是关键分支，特别是，由于节点5 中为假的分支能够使得节点6 在一 个循环体中被偏离，因此它同样被认为是关键分支。 定义2 4 ：分支b 1 可被称为分支b 2 的反向分支或者配对分支，当且仅当b 1 和b 2 分别是一个i f e l s e 语句结构的两个分支。 分支逼近度( a p p r o x i m a t i o nl e v e l ) 是进化测试中非常重要的概念，它指的是在 控制流图上一个关键分支与测试目标距离的远近。其计算如定义2 5 所示。 定义2 5 ：分支逼近度a p p r o x i m a t i o nl e v e l 可如下定义： a p p r o x i m a t i o nl e v e l = c c t 一1 ，其中，c c t 指的是从当前关键分支开始到测试目 标之间所包含的关键分支个数。 在图2 2 中，仍然假设测试目标为节点6 ，则节点5 中为假的分支的分支逼近 度为0 ；而节点4 中为假的分支的分支逼近度则为1 ；节点1 中为真的分支的分支 逼近度则为2 。 定义2 6 ：一个变量v 的定义分支指的是定义该变量的程序分支。 术语控制依赖被用来表示在控制流图上一个节点对另一个节点的依赖程度。 当且仅当从节点y 到程序出口节点的任何一条路径都经过节点z 时，节点z 是节点 y 的后必经节点；当且仅当从分支( y ，x ) 到程序出口的任何一条路径都经过节点z 时， 节点z 是分支( y ，x ) 的后必经节点。由后必经节点，可以得到控制依赖的定义。 定义2 7 ：节点z 控制依赖于节点y ，当且仅当满足以下两个条件： ( 1 ) 节点z 是分支( y ，x ) 的后必经节点， ( 2 ) 节点z 不是节点y 的后必经节点。 假如节点z 控制依赖于节点y ，同时节点z 是分支( y ，x ) 的后必经节点，我们称 节点z 控制依赖于分支( y ，x ) ，由控制依赖于分支的定义出发，我们可以得到控制依 赖分支链的定义。 进化测试中嵌套i f - e l s e 和函数调用结构的适值函数设计 定义2 8 ：一个有序的分支链b c h a i n = 可称为节点z 的控制依赖分支链，当前仅当其满足下列条件： 对任意( y i ，x i ) b c h a i n ，节点z 控制依赖于分支( y i ，x i ) ； 对任意的( y i ，x i ) 和( y j ，x j ) ，如果i 勺，则在任意一条经过( y i ，x i ) 和( y j ，x j ) 的控制流 路径上，节点( y i ，x i ) 在节点( ) i ：j ，墨i ) 之前； 对任何不属于b c h a i n 的分支( y i ，x i ) ，节点z 与其不存在控制依赖关系。 在实际应用中，为了使得b c h a i n 一直不为空，在本文中，一个程序的入口分 支也被认为是目标节点的控制依赖分支，并且处在控制依赖分支链上的第一个位 置上。 由控制依赖可以得出，实际上关键分支是与控制依赖相关的。测试目标的关 键分支集合实际上是其控制依赖分支链中，除了程序入口分支之外所有分支的反 向分支集合。 定义2 9 ：一个程序的输入向量i = ( x l ，x 2 ，x k ) 指的是程序f 的输入变量集。 2 3 适值函数计算公式 进化测试中，适值函数是用来评价种群中个体优劣的，它是建立在对程序进 行静态分析的基础上。 而针对具体的测试准则，比如结构化测试中的分支覆盖测试，语句覆盖测试 等，则会分别定义不同的适值函数以及相应的计算方法。针对面向节点( 程序分 支) 的测试类别，传统工作认为其适值函数公式应该由两部分组成：分支逼近度 ( a p p r o x i m a t i o nl e v e l ) 和分支距离( b r a n c hd i s t a n c e ) 1 2 酬，如公式( 2 1 ) 所示。 f i t n e s s = a p p r o x i m a t i o nl e v e l + n o r m a l i z e ( d i s t a n c e ) n o r m a l i z e ( d i s t a n c e ) = 1 1 0 0 1 司 ( 2 - 1 ) ( 2 2 ) 其中，a p p r o x i m a t i o nl e v e l ( 也叫a p p r o a c hl e v e l ) 艮p 是2 2 节中定义2 5 所定义 的分支逼近度，分支逼近度是在程序的控制流角度来衡量一个测试数据与目标测 试数据之间的“距离 。在程序运行过程中，当执行路径一旦偏离目标分支而进入 关键分支时，就在该关键分支中计算其分支距离，这个分支距离被用来描述当前 输入与进入其相反分支所需输入之间的接近程度。例如，如果要使分支条件( x 一- - y ) 成立，那么相应的分支距离可以定义为d = l x y i ，通过正规化函数n o r m a l i z e 的运算， d 可被映射到 0 ，1 ) 区间。分支距离的规格化函数如公式( 2 2 ) 所示搜索过程中通 过最小化由a p p r o x i m a t i o nl e v e l 和n o r m a l i z e ( d ) 所形成的适值函数值，我们就可以 第二章进化测试技术 9 在得到这个函数的最小值o 时，同时得到期望的测试数据：x 和y 值相等的输入向 量 。在分支距离计算中，对于像p 1 八p 2 和p 1v p 2 这样的复合谓词，分支距 离的定义如公式( 2 3 ) 【2 7 1 和公式( 2 4 ) f 2 6 】所示，其中p 1 和p 2 都是谓词。在任 何情况下，根据n t r a c e y 等人提出的方法所计算的d ( p ) 都不小于0 ，并且当且仅 当p 被满足时d ( p ) 才等于0 。本文中，我们按照n t r a c e y 等人所提出的方法计算 分支距离，这种方法已被广泛应用在进化测试中。 d ( 五 昱) = a ( e 0 + d ( 最) 榔v 驴船器 “i j 十“i _ j ( 2 3 ) ( 2 - 4 ) 第三章嵌套i f - e l s e 结构的适值函数设计 第三章嵌套i f - e l s e 结构的适值函数设计 嵌套i f - e l s e 结构是一种简单和常见的可以进行多次多层条件筛选的程序结 构，被广泛的应用于实际的工业代码中【3 0 l 。对于嵌套的i f - e l s e 结构，为覆盖目标 分支，程序的执行流必须从外到内依次满足目标分支所控制依赖的各个判断分支 的条件。如果某个测试输入无法满足目标分支所控制依赖的某层判断分支条件， 此时测试输入对该层以外的判断分支条件的满足程度可以用分支比逼近度来衡 量，而该层判断分支条件的满足程度可以用分支距离来评价。但是，却无法在该 层以内的判断分支条件上对测试数据进行评价。这是由于，当程序的控制流已经 在外层判断分支处偏离了目标分支时，内层的判断分支是不可能得到执行的，因 此也就无法使用适值函数评估测试输入对各个内层判断分支条件的满足程度。因 此由公式( 2 1 ) 所计算出来的适值实际上不能够充分的评估候选测试输入在整个嵌 套i f - e l s e 结构上的表现。 针对嵌套i f - e l s e 结构，p h i lm e m i n n 提出了采用可测变化 2 9 , 3 0 】的方法来评价 测试输入，但该方法彻底抛弃了传统方法中的分支逼近度，而忽略了内层判断分 支对外层分支的控制依赖，导致基于分支距离的适值计算方法不能很好的评价测 试数据。在实际的代码当中，尤其是对于含有较多嵌套层次的i f - e l s e 结构的程序， 由于程序控制流上导向性的丢失这种方法还面临着严重的效率问题。本文借鉴了 可测变换的思想1 2 9 1 ，首次提出用“分支乐观度”来评价测试输入对各个内层判断 分支条件的满足程度，并将其引入到原有的适值函数公式中，从而提出了一种新 的适值计算方法。区别于可测变换的方法，本文提出的适值计算方法考虑了嵌套 分支间的控制依赖，将分支乐观度加入到了适值计算公式中。 3 1 嵌套i f - e l s e 结构的适值函数计算问题 对于结构化测试中的大部分程序结构，根据公式( 2 一1 ) 计算得到的适值能形成 一个有坡度的适值地形。然而对于多层嵌套的i f - e l s e 结构，当目标分支所控制依 赖的某个外层判断分支条件没有被满足时，目标分支就会被偏离，此时就需要计 算适值。但是由于所有嵌套在这层判断分支内的内层判断分支都无法被执行到， 也就意味着传统的适值计算方法无法评估测试输入对各个内层分支条件的满足程 度，所以公式( 2 1 ) 无法在这些内层的判断分支上对测试数据进行评价。因此，对 于那些没有满足某个外层判断分支的条件却能够满足内层判断分支条件的测试数 据，现有的适值计算公式无法对它们进行公平的评价。同时，由于受到外层判断 1 2 进化测试中嵌套i f - e l s e 和函数调用结构的适值函数设计 分支条件的限制，在适值地形上就很容易出现没有坡度的大面积的平坦地形，但 当某个条件被满足时，适值地形会从一片平坦的高地上陡然下降到一个较低的平 坦地形上。显然这种适值地形不能为进化搜索提供良好的导向性，这将直接导致 搜索效率的下降，甚至在某些苛刻的条件下，可能会导致进化搜索的失败。图3 1 是一个简单的嵌套i f - e l s e 结构，它的嵌套深度只有两层，测试目标是标号为4 的 语句。 图3 1 一个简单的两层i f - e l s e 结构的例子 由于测试目标在最深层的嵌套分支中，因此只有外边的两层判断分支条件 x 一- - - 0 和) ，= = 3 同时被满足时目标才能被覆盖。 由于只有当第一层判断分支条件 x 一- - - 0 被满足时，才能够在第二层判断分支条件y = = 3 上对测试数据进行评价。图 3 1 的适值地形图如图3 2 所示。 图3 2 图3 1 代码片段的适值地形 从这个图中可以看出，我们期望的测试输入萨= o 的适值是一个在一大片的平 坦地形上陡然凹下去的一个坑，而对于所有不等于o 的测试输入，它们的适值都 位于一个平坦地形上，这种平坦的适值地形无法为进化搜索提供导向，导向性的 丢失将导致进化搜索退化为随机搜索。在没有导向性的情况下，要在整数空间内 搜索到测试输入0 这个值非常困难。因此，大多数的测试数据会在第一层判断分 4 2 1 8 6 4 2 o o 化 1 啦 。伽 竹竹鼙5 啊 第三章嵌套i f - e l s e 结构的适值函数设计 支处偏离目标，此时这些测试数据具有相同的分支逼近度，它们唯一的区别仅在 于值在 0 ，1 ) 区间内的分支距离，这使得各个候选测试数据的差异也被限制在一个很 小的范围内。更糟糕的是随着嵌套i f - e l s e 结构中嵌套层次的增加，可行的输入空 间急剧缩小，从而使得找到目标测试数据的可能性会更少。 为了解释使用传统的适值公式计算嵌套i f - e l s e 结构适值计算的问题，针对图 3 1 ，我们给定两组测试数据：测试数据a 和测试数据b 。这两组测试数 据都会使程序的控制流在第一层判断分支处偏离目标。两者的分支逼近度均为1 ， 分支距离d 均为1 ，规格化后均为0 0 0 1 ，根据公式( 2 1 ) 可知二者的适值相同，都 为1 0 0 1 。但经过分析程序的语义结构，不难发现，测试数据a 要好于测试数据b ， 因为测试数据a 中变量y 的值能满足第二层判断分支的条件，也就是) ，= 3 。而测 试数据b 不能够满足第二层判断分支的条件，显然，测试数据a 要优于测试数据 b 。然而，按照公式( 2 1 ) 计算所得，这两组测试数据有着相同的适值。因此适值的 导向性就丢失了。由这两组测试数据可以看出，针对嵌套的i f - e l s e 结构，现有的 适值计算方法不能够公平的评价出各个测试输入的好坏，究其原因，是因为只要 外层的判断分支条件不满足，测试输入与内层的判断分支的条件的距离就不能够 被衡量，而只有测试输入与外层的判断分支条件的距离可以被分支距离所评价。 因此，如果内层嵌套分支能被到达，测试数据与这些内层判断分支条件的距离能 够在这些分支处被评价，这样得到的适值就可以更加准确地评价各个测试输入。 这些测试数据的适值中存在的差异就会扩大，种群的多样性也得到了提升。对于 图3 1 中，如果把测试数据对分支条件y = 3 的分支满足程度也作为一个评价因素加 入到候选测试输入的评价当中，适值地形将会呈现出如图3 3 所示的一个带有较好 坡度的适值地形，进化搜索就可以在该适值的导向下找到测试数据。 a n d r eb a r e s e l 等人【2 8 】针对嵌套i f - e l s e 结构提出了一种解决方案。其主要思想 是在嵌套结构的顶层计算适值。然而，当嵌套的分支之间存在数据依赖时，由于 内层分支的判断分支条件中的变量可能在外层分支中被改变，因此想要直接在嵌 套结构的顶层计算适值是不可能的。所以，这种方法仅仅适用于那些在各层嵌套 分支的判断语句之间没有数据依赖的嵌套i f - e l s e 结构。 1 4 进化测试中嵌套i f - e l s e 和函数调用结构的适值函数设计 图3 3 期望的图3 1 代码片段的适值地形 3 2 基于分支距离的适值计算方法 由3 1 节可知，对于嵌套的i f - e l s e 结构，由公式( 2 1 ) 计算得到的适值对进化 搜索的导向性非常小。这种对测试输入评价不充分的根源在于当外层判断分支条 件不能被满足时，嵌套i f - e l s e 结构的控制流无法进入内层嵌套分支，当然也就无 法评价测试输入与这些内层判断分支条件的满足程度。 基于以上分析，为了也能够在内层分支上对测试数据进行评价，一种最直接 的方法就是将嵌套的i f - e l s e 结构展平为并列的i f - e l s e 结构，使得内层的判断分支 语句的执行不依赖于外层的分支语句的执行结果，也就是无论外层判断分支的条 件满足与否，嵌套结构中内层判断分支都可以被执行。这样测试数据与各个内层 判断分支的满足程度就可以被评价。 3 2 1 累计分支距离的适值计算方法 2 0 0 5 年p h i lm c m i r m 提出了一种基于分支距离的适值计算方法【3 0 】，该方法使 用了可测变换技术( 2 9 】。可测变换的形式化定义如定义3 1 和3 2 所示。 定义3 1 1 2 9 1 ：面向测试的变换：假设p 是一个程序的集合，c 是一个测试准则 的集合。则程序变换是p p 上的一个偏序函数，面向测试的变换是( p + c ) 一 ( p 堆c ) 上的一个偏序函数。 定义3 2 【2 9 】：面向测试的变换t 是可测变换的充分必要条件是，对于所有的程 第三章嵌套i f - e l s e 结构的适值函数设计 序p 和所有的测试准则c ，如果c ( p ，c ) = ( p ，c ) ，并且对于所有的测试集合t ，如 果根据测试准则集合c ，t 对d 来说是足够的，那么根据测试准则集合c ，t 对p 来说也是足够的。 可测变换是一种从源代码到源代码的变换，其目标是提高测试数据生成算法 的性能。可测变换后的程序仅仅是一个满足一定条件的，用来满足某一目的而进 行操作的中间代码，而绝不是目标本身。但是，可测变换可以保证在对程序进行 可测变换的同时，不需要对测试准则进行变换，这就保证了在变换后的程序上的 测试用例集上同样可以应用到没有变换的程序上去，这也就实现了我们进行可测 变换的目的，使得程序可测。转换过程不需要保留传统的程序语义。在嵌套的 i f - e l s e 结构的适值计算过程中，使用可测变换就是为了改变嵌套结构的控制流， 使得测试数据能够在内层的分支被充分的评价，这样测试数据才能被更有效的评 价。p h i lm e m i n n 3 0 1 使用了可测变换的思想，把每个判断语句都用一个计算测试数 据与该判断分支条件距离的函数替换，这样嵌套的i f - e l s e 结构中的每一层都可被 到达，测试输入与每一层判断分支条件的距离都可以被评价。 图3 4 图3 1 代码片段使用可测变换转换后的程序 图3 1 中的程序经过转换如图3 4 所示。由于程序在控制依赖链上的偏离导 致无法在内层的分支上对测试数据进行评价，因此基于分支距离的方法首先使用 可测变换将嵌套的i f - e l s e 结构展平，虽然可测变换改变了程序的语义，但是在保 证测试准则和测试用例等价的基础上，使得程序变得可测了。转换后的程序使用 计算分支距离的函数沿着目标分支的控制依赖链累加各层次判断分支的分支距 离。 3 2 2 累计分支距离的适值计算方法问题 这种基于分支距离的适值计算方法最大的优点在于它展平了嵌套结构，使得 也可以在内层的分支上对测试数据进行评价，所以这种方法能更有效地评价测试 数据，并为进化测试提供较好的导向性。但即使是这样，基于分支距离的这种方 法依然存在它的不当之处。基于分支距离的适值计算方法只保留了分支距离，而没 1 6 进化测试中嵌套i f - e l s e 和函数调用结构的适值函数设计 有在程序控制流上对测试数据进行评价，即该方法没有考虑经典适值计算公式( 2 1 ) 中的分支逼近度。分支逼近度是基于程序的控制依赖图的，它反映了内层分支对 于外层分支的控制依赖关系。这种依赖关系是客观存在并且决定着程序的执行行 为的，只有外层分支的条件得以满足，内层的分支才有可能被执行，内层分支的 执行控制依赖于外层分支。基于分支距离的适值计算方法简单的将各个嵌套分支 展平，将各个层次的分支同等对待，忽略了它们直接的控制依赖关系，彻底抛弃 了分支逼近度，因而不能很好的评价测试数据。 分支逼近度的作用是在被测程序的整个控制流上评价测试数据。由于程序的 控制流在宏观的角度上评价了测试数据的优劣，而“分支距离”仅仅是在搜索过 程中对适值的微调，因此分支逼近度在适值评价中发挥着至关重要的作用。也正 是由于分支逼近度的存在，使得在不同层次的判断分支处偏离的个体能够被赋予 不同的适值。在更早的适值计算公式中，没有分支逼近度的存在，对于在不同层 次的判断分支处偏离的个体，适值公式是没有办法提供公平的评价准则的。 图3 s 一个三层嵌套i f = e l s e 结构的例子 对于公式( 2 1 ) ，分支逼近度是在程序控制流上对测试数据进行宏观的评价， 针对嵌套的i f - e l s e 结构，对于给定的目标分支，测试数据满足越多的外层的嵌套 分支，离目标分支越近，其分支逼近度就越小。这就使得，在判断分支计算出的 分支距离对整个适值的影响程度都仅仅局限于在当前的分支逼近度级别下的更小 级别的微调，一个覆盖了更深控制流的测试数据的适值不可能比一个覆盖了较浅 的控制流的测试数据的适值小。根据程序的语义，程序执行时的控制流距离目标