（计算机软件与理论专业论文）基于时间限制的测试用例集优化技术.pdf

摘要 摘要 当软件发生变更时，如添加新的功能或修正错误后，就需要进行回归测试，以确保这些变更不会对软 件产生负面影响。然而频繁的回归测试带来的开销，特别是时间上的开销很大，约占软件维护总开销的一 半，这就需要对测试用例集进行优化。现有的测试用例集优化技术主要包括测试用例集选择技术和测试用 例优先级技术，可以提高测试用例集的性能，得到了广泛的应用。 通常情况下，回归测试都存在一定的时间限制，而目前绝大多数的测试用例集优化技术没有考虑到这 一点，因此，研究基于时间限制的测试用例集优化技术具有重要意义。时间约束下的测试用例集优化问题 可以转化为0 1 背包问题，o 1 背包问题是经典的n p c 问题，可以采用多种算法来求解。本文提出了利用 动态规划法、回溯法、分支限界法、基本遗传算法等几种算法求解时间约束下的测试用例集优化技术及其 度量方法，并通过实验验证了该优化技术及度量方法的有效性。 论文的工作包括以下几个方面：( 1 ) 针对基于时间限制的测试用例集优化问题可以转化为经典的0 1 背包问题，给出基于时间限制的测试用例集优化问题的形式化描述，提出用多种算法求解的基于时间限制 的测试用例集优化技术；( 2 ) 提出基于时间限制的测试用例集优化技术度量方法，该度量方法综合考虑了 测试需求的覆盖率和覆盖速度，能更公平有效地对测试用例集的优化效果进行度量：( 3 ) 以e c l i p s e 为平 台，实现了基于时间限制的测试用例集优化工具t - t s o t o o l ，该工具在给出测试用例和测试需求的满足关 系矩阵、测试需求的优先级、测试用例的执行时间的前提下，根据选择的算法给出在时间约束下执行完成 的测试用例子序列及该子序列的优化效果；( 4 ) 利用t - t s o - t o o l 进行了一系列的仿真实验，通过实验分析 比较了动态规划法、回溯法、分支限界法和基本遗传算法的优化效果，同时将以上算法与传统优化算法比 较，验证了以上算法的有效性。 关键词：回归测试、测试用例集优化、0 1 背包、时间限制 a b s t r a c t a b s t r a c t r e g r e s s i o nt e s t i n gi se x e c u t e dt oe n s u r et h a tc h a n g e sm a d et os o f t w a r e s u c ha sa d d i n gn e wf e a t u r e so r m o d i f y i n ge x i s t i n gf e a t u r e s ，h a v en o ta d v e r s e l ya f f e c t e df e a t u r e so fs o f t w a r et h a ts h o u l dn o tc h a n g e h o w e v e et h e c o s to ff r e q u e n tr e g r e s s i o nt e s t i n gt a i lb ev e r ye x p e n s i v e ，e s p e c i a l l yw i t hr e s p e c tt ot i m e ，a n dt h u sa c c o u n t sf o ra s m u c ha sh a l ft h ec o s to fs o f t w a r em a i n t e n a n c e t h e r e f o r e ，t e s ts u i t eo p t i m i z a t i o nt e c h n i q u e sa r en e c e s s a r y t e s t s u i t eo p t i m i z a t i o nt e c h n i q u e si n c l u d et e s ts u i t es e l e c t i o nt e c h n i q u e s , t e s tc a s ep r i o r i t i z a t i o nt e c h n i q u e sa n ds oo n t e s ts u i t es e l e c t i o nt e c h n i q u e sa t t e m p tt or e d u c et h ec o s to f r e g r e s s i o nt e s t i n gb ys e l e c t i n gas u b s e to f ap r o g r a m s e x i s t i n gt e s ts u i t e t e s tc a s ep r i o r i t i z a t i o nt e c h n i q u e ss c h e d u l et e s tc a s e sf o rr e g r e s s i o nt e s t i n gi na l lo r d e rt h a t i n c r e a s e st h e i ra b i l i t yt om e e ts o m e p e r f o r m a n c eg o a l u s u a l l y , t h e r ei sal i m i t e da m o u n to ft i m ea l l o w e df o rr e g r e s s i o nt e s t i n g h o w e v e r , m o s to ft h ee x i s t i n gt e s t s u i t eo p t i m i z a t i o nt e c h n i q u e sd on o ti n c o r p o r a t eat e s t i n gt i m eb u d g e t t h e r e f o r e t h e r ei sac l e a rn e e df o ra n o p t i m i z a t i o nt e c h n i q u eb a s e do nt i m e c o n s t r a i n e d t h et i m e c o n s t r a l n e dt e s ts u i t eo p t i m i z a t i o np r o b l e mc a l lb e r e d u c e dt ot h e0 1k n a p s a c kp r o b l e m w h i c hi sa nn p cp r o b l e ma n dc a nb ee 伍c i e n t l ya p p r o x i m a t e dw i t h m u l t i p l ea l g o r i t h m s t h i sp a p e rp r o p o s e san e wt i m e c o n s t r a i n e dt e s ts u i t eo p t i m i z a t i o nt e c h n i q u eb a s e do n d y n a m i cp r o g r a m m i n g ，b a c k t r a c k i n ga l g o r i t h m ，b r a n c h - b o u n da l g o r i t h m ，a n db a s i cg e n e t i ca l g o r i t h m t h e n , i t p r e s e n t st h ec o r r e s p o n d i n gm e t r i c ，a n di l l u s t r a t e st h ee f f i c i e n c yo ft h et e c h n i q u ea n dm e t r i cb yac a s es t u d y t h em a i nc o n t r i b u t e so f t h ep a p e ra r e1 i s t e da sf o l l o w s ：( 1 ) af o r m a l i z e dd e s c n p t i o no f t i m e c o n s t r a i n e dt e s t s u i t eo p t i m i z a t i o np r o b l e mi sp r o p o s e d a st i m e c o n s t r a i n e dt e s ts u i t eo p t i m i z a t i o np r o b l e mc a l lb er e d u c e dt ot h e 0 1k n a p s a c kp r o b l e ma n dt h e0 1k n a p s a c kp r o b l e mc a l lb es o l v e dw i t hm u l t i p l ea l g o r i t h m s an e wo p t i m i z a t i o n t e c h n i q u eb a s e do nt h o s ea l g o r i t h m si sa l s op r e s e n t e di nt h i sp a p e r ( 2 ) an e wm e t r i cf o rt i m e c o n s t r a i n e dt e s t s u i t eo p t i m i z a t i o ni sp r o p o s e d ，w h i c ht a k e sb o t ht h ec o v e r a g eo ft e s t i n gr e q u i r e m e n ta n dt h es p e e do ft e s t i n g r e q u i r e m e n t sb ec o v e r e di n t oa c c o u n ts ot h a ti tc a nb em o r ef a i ra n de f f i c i e n t ( 3 ) at i m e - c o n s t r a i n e dt e s ts u i t e o p t i m i z a t i o nt o o lt - t s o t o o li sd e v e l o p e db a s e do ne c l i p s e 。w h i c hc a np r o d u c ea no r d e r e ds u b s e q u e n c eo ft e s t c a s e sw h i c hc a nb ee x e c u t e di nt h eg i v e nt i m ea n dt h em e t r i cr e s u l to ft h eo r d e r e dt e s tc a s e s ( 4 ) v a l i d a t et h e e f f e c t i v e n e s so ft h ep r o p o s e dt e c h n i q u eb a s e do nd y n a m i cp r o g r a m m i n g ，b a c k t r a c k i n ga l g o r i t h m ，b r a n c h b o u n d a l g o r i t h ma n db a s i cg e n e t i ca l g o r i t h mw i t ht - t s o - t o o lb ya n a l y z i n gt h er e s u l to fe x p e r i m e n t sa n dc o m p a r i n gw i t h t r a d i t i o n a la l g o r i t h m s k e y w o r d s ：r e g r e s s i o nt e s t i n g ，t e s ts u i t eo p t i m i z a t i o n ，0 1k n a p s a c k , t i m e c o n s t r a i n e d i i 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 研究生签名： 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 研究生签名：望堡超导师签 第一章绪论 1 1 选题依据 第一章绪论 软件系统在社会的各个领域中起着越来越重要的作用，软件系统的质量和可靠性也逐渐成为人们关注 的焦点。作为保证和提高软件质量的一种重要手段，软件测试发挥着其它方法不可替代的作用i l 捌。目前， 对于大型的软件系统来说，迭代开发已经成为一种主流的开发模式。这就需要在开发的每个迭代周期中对 软件进行重新测试，也就是所谓的回归测试。随着软件开发过程的不断迭代、演化，测试人员需要频繁进 行回归测试，用于验证程序的修改是否正确以及是否引入了新的错误【3 1 。 然而，回归测试的资源开销，特别是时间开销很大1 4 1 ，约占软件维护总开销的一半p 一1 。一份工程报告 指出，一个约2 0 ，0 0 0 行代码的软件，运行整个测试用例集将需要近7 周的时间【6 】。因此，在每一次回归测 试中重新执行全部的测试用例是不实际的。在这种情况下，测试人员就需要对测试用例集进行优化。 目前的回归测试用例集优化技术主要包括：测试用例集选择技术和测试用例优先级技术。测试用例集 选择技术按照一定的策略从已有的测试用例集中选择一个子集，通过减少待执行测试用例的数目来降低回 归测试成本【4 7 。1 0 j 。测试用例优先级技术将测试用例按照一定的优先级标准排序，使优先级高的测试用例可 以优先执行，从而帮助测试人员尽早实现测试目标，提高测试效率1 1 1 以6 1 。 通常情况下，回归测试都有一定的时间限制。例如，很多公司采用日间编码、调试，夜间编译构建、 回归测试的制度，使得回归测试有着明确的时间限n t l 7 l 。现有的测试用例集优化技术大多没有考虑回归测 试的时间约束问题。因此，需要一种新的测试用例集优化技术，当明确给出执行测试的时间限制，特别是 时间较为紧张时，能够产生高效的测试用例子集。 基于时间限制的测试用例集优化问题可以转化为0 1 背包问题，0 1 背包问题是经典的n p c 问题，可 以采用多种算法来求解，如动态规划法、回溯法、分支限界法、基本遗传算法等f l 1 9 】。本文将采用以上几 种算法求解该问题，综合应用测试用例集选择技术和测试用例优先级技术，优化后的测试用例集将具有以 下特性：可以在给定的时间限制内执行完成；同时，在时间限制内，能够尽多尽早地覆盖优先级高的测试 需求，提高测试用例集的性能。 1 2 国内外研究现状 测试用例集优化技术，包括测试用例集的生成、选择、约减、排序等，这些技术从不同的角度力求在 保证和提高软件测试质量的同时，降低软件测试的成本。本文重点关注测试用例集选择技术和测试用例优 先级技术。测试用例集选择技术按照一定的策略选择当前测试用例集的一个子集，通过减少测试用例规模 来降低测试成本。测试用例优先级技术则将测试用例按某种标准排序后依次执行，从而改善测试片j 例集性 能，提高测试效率。 1 2 1 测试用例集选择技术 回归测试与一般测试的重要区别是：回归测试有一个可供使用的测试用例集，因此，可以对这些测试 用例进行重用。由于重用全部的测试用例代价很高而且效率低下，所以现有对回归测试的研究主要集中在 如何有效地对测试用例进行复用。测试用例集选择技术能按照一定的策略从已有的测试用例集中选择一个 子集，通过减少执行的测试用例数量有效降低回归测试成本。 在以往的研究中，研究者从很多不同的角度考虑，提出了多种测试用例集选择技术，包括基于代码( 白 盒) 的测试用例集选择技术【7 2 0 也4 】和基于规格说明书( 黑盒) 的测试用例集选择技术【j 2 5 o 同时，测试用 例集选择技术还可以分为安全的测试用例集选择技术1 8 2 4 】和基于风险的测试用例集选择技术。如果选择出 的测试用例子集能够暴露出和原有测试用例全集相同的缺陷，那么就说该测试用集选择技术是安全的。基 东南大学硕士学位论文 于完全执行皿e t e s t a 1 1 ) 的测试用例集选择技术就是一种典型的安全测试用例集选择技术，该技术选择了能 暴露出缺陷的所有测试用例。随机选择则是典型的基于风险的测试用例集选择技术，能暴露出缺陷的测试 用例集有可能被舍弃。o r s o 等人将测试用例集选择技术按照其操作对象的粒度分为基于高层粒度和基于低 层粒度两判2 6 】，高层粒度是指方法、接1 2 1 和类等，而低层粒度指语句级。 作为补充，e n g s t r o m 等人在文献 2 7 中提出了另外三种分类方式。第一种按照测试用例集选择技术的 输入类型分类，最常见的输入类型是程序的源代码文本1 3 ，7 - 8 , 2 0 - 2 2 , 2 4 - 2 5 1 ，除此之外，还有用于虚拟机的中间 码【l l ，2 3 ，2 8 圆域机器码【3 ，3 0 】；第二种按照输入的格式分类，有些技术对输入有一定的格式要求，例如元数据 t 2 6 或者o c l 3 1 】；第三种按照测试用例集选择技术适用的程序语言分类，有些技术是针对面向过程语言的1 8 2 1 五2 ，2 4 3 2 1 ，有些是针对面向对象语言的 1 1 , 2 3 , 2 8 - 2 9 ，而有些则是独立于程序语言的p ，3 们。 针对以上各种选择技术，研究者也相应提出了各种度量方法。由于测试用例集选择技术本身的多样性 和复杂性，目前不存在统一的度量标准。已有的度量方法大致可以分为以下两类：测试成本的压缩和测试 用例集的检错能力。其中，r o t h e r m e l 在文献 2 9 】中提出的用于从理论上评估测试用例集选择技术优劣的框 架得到了广泛的应用，该框架包括四个关键性指标：包含性( i n c l u s i v e n e s s ) ，精确。l 生( p r e c i s i o n ) ，效率( e f f i c i e n c y ) 和普遍性( g e n e r a l i t y ) 。 1 2 2 测试用例优先级技术 测试用例优先级技术能有效提高现有测试用例集的性能，得到了广泛的应用。该技术不减少测试用例 集的规模，在充分考虑了不同因素对测试用例重要程度的影响后，给每个测试用例赋予一个优先级，然后 按照优先级的高低顺序依次选择并执行，优化目标函数以提高测试用例集的性能。 目标函数的不同导致了不同的测试用例优先级技术。在以往的研究中，研究者从多方面考虑了目标函 数的定义，提出了多种测试用例优先级技术，并通过大量的实验验证了测试用例优先级技术的有效性1 1 1 。”j 。 这些优先级技术大致可以分为以下几类【1 6 1 ：分析不同粒度的代码元素，如语句、程序块、函数等l l l ，1 5 矧； 应用反馈机制、动态调整测试用例优先级等【3 4 3 5 】；利用非覆盖率信息，如测试成本、错误严重等级、错误 传播概率等p “1 1 。 针对这些优先级技术，研究者提出了相应的度量方法，如语句覆盖率、累计函数覆盖率、单位时间错 误检测个数、平均错误检测效率等。其中，应用最为广泛的是r o t h e r m e l 等提出的a p f d 度量方法，用于 评估优化测试用例集的平均错误检测效率【1 2 】。在此基础上，e l b a u m 等提出了改进的a p f d c 方法，用于评 估当错误严重等级和测试用例开销不同时，给定优化测试用例集的平均错误检测效率【6 ，4 h 引。 作为现有测试用例优先级技术的有力补充，s r i k a n t h 提出了基于需求优先级的测试用例优先级技术， 给出了基本设计思想【4 1 1 。该技术从测试需求出发，可以有效提高用户满意度，但该技术不考虑测试用例 开销的差异，仍有待进一步改进。 1 3 主要研究内容 根据国内外的研究现状以及最新发展动态，我们在以下几个方面展开研究： ( 1 ) 基于时间限制的测试用例集优化技术 针对基于时间限制的测试用例集优化问题可以转化为经典的彤1 背包问题，我们给出了基于时间限制 的测试用例集优化问题的形式化描述，并将解决o 1 背包问题的经典算法( 动态规划法、回溯法、分支限 界法和基本遗传算法) 与测试用例优先级技术相结合，用于求解基于时间限制的测试用例集优化问题，最 终提出基于动态规划法、回溯法、分支限界法、基本遗传算法求解的时间限制下的测试用例集优化技术。 ( 2 ) 测试用例集优化技术度量方法 测试需求覆盖率是度量测试用例集选择技术的一个重要标准，而测试需求覆盖的速度则可以用来度量 测试用例优先级技术的优劣。本文提出了一种新的测试用例集优化技术度量方法，该方法综合考虑测试需 求的覆盖率和覆盖速度，能更公平有效地对测试用例集的优化效果进行度量。 ( 3 ) 基于时间限制的测试用例集优化工具 为了实现本文提出的基于时间限制的测试用例集优化技术及其度量方法，我们设计了基于时间限制的 2 第一章绪论 测试用例集优化工具t - t s o - t o o l 。输入测试需求个数、测试用例个数、测试时间百分比并选择测试用例集 优化算法，t - t s o - t o o l 能自动生成测试需求的优先级、测试用例的执行时间、测试用例和需求的满足关系 矩阵，最后给出在时间限制内能执行完毕的测试用例子序列以及该子序列的优化效果。 ( 4 ) 基于时间限制的测试用例集优化技术的比较 为了进一步验证本文提出的测试用例集优化技术及其度量方法的有效性，我们利用测试用例集优化工 具t - t s o t o o l 、通过一系列的实验分析动态规划法、回溯法、分支限界法、基本遗传算法的性能、优化效 果，同时将以上几种算法与贪心算法、自然排序法以及随机算法进行比较。 1 4 论文结构 论文主要各章节组织如下： 第一章绪论部分简要地介绍了基于时间限制的测试用例集优化技术的研究背景和意义，介绍了国内外 研究现状，描述了论文的主要研究内容，最后简要介绍了论文的结构。 第二章论述了测试用例集优化技术及度量方法，包括测试用例集选择技术、测试用例优先级技术及对 应的优化度量方法，在此基础上指出了已有研究存在的不足之处，最后通过一个实例分析阐明本文将要重 点研究的优化技术。 第三章首先介绍了0 1 背包问题的基本概念，接着着重介绍了用于求解0 1 背包问题的动态规划法、 回溯法、分支限界法和基本遗传算法，最后简要介绍了贪心算法、自然序列法和随机算法。 第四章在第二章和第三章的基础上，提出了将测试用例集选择技术和测试用例优先级技术相结合的、 采用动态规划法、回溯法、分支限界法、基本遗传算法求解的、基于时间限制的测试用例集优化技术及其 度量方法。 第五章介绍了以e c l i p s e 为平台开发的测试用例集优化工具t - t s o - t o o l ，并利用t - t s o - t o o l 、通过实验 验证了本文提出的基于时间限制的测试用例集优化技术及其度量方法的有效性。 第六章是对整个论文的总结，综述在基于时间限制的测试用例集优化领域获得的成果，并阐述我们正 在进行或将要进行的研究工作。 3 东南大学硕士学位论文 第二章测试用例集优化技术及其度量方法 本章首先介绍了软件测试领域的一些基本概念，接着介绍了测试用例集选择技术、测试用例优先级技 术及对应优化度量方法的背景知识，回顾了相关工作，接着指出已有研究存在的不足之处，并通过一个实 例分析阐明了本文将要重点研究的测试用例集优化技术。 2 1 基本概念 2 1 1 软件测试定义 软件测试是为了提高和度量软件质量而进行的一系列设计、运行、维护等行为m 1 。1 9 8 3 年，i e e e 计 算机协会软件工程技术委员会提出的“软件工程标准术语”中，软件测试被定义为：“使用人工或自动手 段来运行或测定某个软件系统的过程，其目的在于检验该被测软件是否满足规定的需求或是衡量预期结果 和实际结果之间的差别。【4 5 1 ” 2 1 2 测试需求与测试用例 在测试程序之前需要定义一个测试目标，这个测试目标就称之为测试需求。例如，如果测试目标是程 序的每个分支至少被执行一次，那么程序的每一个分支就可以被当作测试需求。显然，不同的标准下有不 同的测试需求集。测试用例是用于特定目标而开发的一组输入、预期条件和预期结果。用来满足测试需求 的测试用例的集合被称为测试用例集。如果测试用例集中有测试用例满足某个需求，那么我们就说这个需 求是可行的。在本文中，我们假设所有的需求都是可行的。 用r 和r 分别表示测试需求集和测试用例集，并假定这两个集合都是非空有限集。用m 和 分别表示 测试需求集r 和测试用例集r 的基数，i ! p i r f = i t ，f 7 1 = r 。一个充分的测试，对于测试需求集尺中每个测 试需求，p e e r ) ，在测试用例集r 中都应存在测试用例f ( t e 乃满足这个测试需求。 2 2 测试用例集选择技术及其度量方法 为了降低回归测试的开销，软件测试工程师们通常会将上一次回归测试的所有测试用例保存起来，留 待下一次的回归测试重用。随着软件的不断迭代，回归测试频繁进行，每一次新的回归测试都可能会引入 新的测试用例，而旧的测试用例一直沿用，这就使得测试用例集不断增大，回归测试的开销也持续增加。 当软件系统增加到一定规模时，执行所有的测试用例几乎是不可能的，因此测试用例的选择性重用是必要 的。 2 2 1 回归测试选择问题 回归测试选择性重用问题的形式化描述如下： 给定程序p ，以及它的修改版本尸，和一组对程序p 实施过测试的测试用例集乃在r 中选择出部分测 试用例集合r ，在尸，上运行，以验证程序尸的正确性。 建立尸到p 7 的映射关系，识别程序尸，对尸所做的修改后，典型的回归测试执行过程如下： ( 1 ) 进行测试用例选择，选择出t ct ，用于测试尸。 ( 2 ) 在尸上运行测试用例集f ，进行回归测试，使得r 能尽量暴露出由于程序修改而引入的缺陷。 ( 3 ) 如果需要，增加新的测试用例集r “，用于对p ，进行测试。 ( 4 ) 在p 上运行测试用例集f ”。 ( 5 ) 由天丁、r 建立p 的测试历史和测试用例集r “。 4 第二章测试用例集优化技术及其度量方法 从上面的过程看，步骤1 包含了回归测试选择问题：从丁中选择r ，用于测试p ；步骤3 涉及了覆盖 率问题：根据需要增加新的测试用例，用于功能测试或结构测试：步骤2 和步骤4 涉及测试用例的执行问 题：执行从原有测试用例集中选择出的测试用例以及根据需要新增的测试用例；步骤5 涉及测试用例集的 维护问题：更新并保存测试用例信息。 2 2 2 测试用例集选择技术 给定测试用例集乃r 对应的程序尸，以及p 的修改版本尸，如何选择r 的子集r 7 来对p 进行有效的 测试是回归测试选择技术研究的问题。 测试用例集选择一般基于规格说明信息的分析和对修改前后程序的分析，而基于分析修改前后程序的 技术又分为最小化技术、安全技术和覆盖技术【4 6 】。最小化技术采用各种策略选择最少的测试用例来达到覆 盖标准；安全技术选择出所有可能检测出错误的测试用例；覆盖技术分析修改过以及受影响的模块，选择 测试用例来覆盖这些模块。 l e u n g 等研究了基于规格说明信息的测试用例集选择技术，并将其应用于回归测试中的集成测试 3 1 ， m a y r h a u s e r 等提出了测试用例生成过程模型，通过规格说明测试基于命令行的系统，并提出基于命令的测 试用例选择方法【2 5 1 。另外，z h e n g 提出了一种集成黑盒测试方法，解决了在源代码不可用的情况下面向组 件的回归测试选择问题1 4 7 j 。 最小化的测试用例集选择技术主要采用已有的经典算法来实现。f i s c h e r 、l e e 、h a r t m a n n 等提出并实 现了基于0 1 整数规划的测试用例集选择技术【2 2 ，4 8 郴】，通过构造测试用例与其经过程序块的关系矩阵，利 用线性方程组选择覆盖修改过代码块的最小测试用例集。m a n s o u r 等将遗传和模拟退火算法引入回归测试 选择技术中，并通过实验比较了两种算法的优缺点和应用范围【50 | 。 基于完全执行的测试用例集选择技术是典型的安全技术，但其效率低代价高，在实际应用中几乎不可 行。为此，r o t h e r m e l 提出了一种测试用例的安全选择方法，通过对比修改前后的控制流图，找出各路径 的首个不同结点，最后选择经过这些结点的测试用例1 2 引。 目前为止，绝大多数的测试用例集选择技术都是基于覆盖的。y a u 等使用符号执行技术，提出了回归 测试的选择以及补充测试用例的方法【5 1 1 。b e n e d u s i 等利用程序分析技术中的样本路径来分析测试用例的复 用问题1 5 引。o s t r a n d 、g u p t a 等利用数据流技术分析待测代码中的定义与i 用对的修改情况，给出了选择执行 到修改后定义引用对测试用例的算法1 2 0 5 3 j 。b a t e s 等使用切片技术比较修改前后程序中可能出现不同行为 的模块，提出了基于程序依赖图的技术来选择执行到这些模块的测试用例【5 4 1 。b i n k l e y 将类似的方法扩展 到过程间的回归测试中，提出基于系统依赖图的测试用例集选择技术【5 引。w h i t e 、l e u n g 等提出了回归测试 的防火墙技术，定义防火墙为包含调用图下所有受修改影响的模块，并进一步定义了在数据流图下的防火 墙概念，用以分析全局变量的回归测试选择问题【25 2 8 ol a s k i 等提出了簇辨别技术，通过计算修改前后程 序的控制依赖关系以及判定语句的作用域，讨论了簇结构下测试用例的重用问题垆引。a g r a w a l 等使用切片 技术来对测试用例进行选择性复用，分别定义了在执行切片、相关切片和动态切片技术下的回归测试选择 方法，并指出了不同切片技术对应的算法和效率【7j 。 2 2 3 选择技术的度量方法 为了验证比较各种测试用例集选择技术的有效性，研究者从不同角度提出了各种度量方法。由于测试 用例集选择技术本身的多样性，目前不存在统一的标准对所有的选择技术进行度量。目前已有的度量方法 大致可以分为以下两类：测试成本的压缩【9 1 1 j ；测试用例集的检错能力【4 3 2 o 测试成本的压缩不仅要考虑 测试用例的数量，同时还要考虑测试用例的执行时间，另外，由于执行测试用例选择算法本身要占用一定 的时间，因此，这部分也纳入测试成本考虑范围。测试用例集的检错能力则分为相对的检错能力和绝对的 检错能力。 r o t h e r m e l 在文献 2 9 】中提出了用于从理论上评估测试用例集选择技术优劣的框架，该框架包括四个关 键性指标：包含l 生( i n c l u s i v e n e s s ) ，精确性( p r e c i s i o n ) ，效率( e f f i c i e n c y ) 和普遍。i 生( g e n e r a l i t y ) 。其中： ( 1 ) 包含性：r 7 中所有可使p 和罗产生不同输出的用例占z 中可使p 和p 7 产生不同输出的用例总数 5 东南大学硕士学位论文 的百分比。例如，f 包含5 0 个测试用例，其中有l o 个是能体现尸，对尸修改的，而r 中只包含了1 0 个中 的3 个，那么对于p 、p ，和r 来说，r 的包含性为3 0 。如果某选择技术选择出的r 包含性总是1 0 0 ， 那么称该技术是安全的。 ( 2 ) 精确性：丁- 中舍弃的可使p 和尸，产生相同输出的用例占r 中可使p 和p 产生相同输出的用例总 数的百分比。例如，丁包含5 0 个测试用例，其中有4 0 个是不体现尸，对j p 修改的，r 舍弃了其中的3 0 个， 那么对于尸、尸和丁来说，r 的精确性为7 5 。 ( 3 ) 效率：从空间和时间两方面进行衡量。一个有效的选择技术，生成r 的代价必须小于舍弃的那 部分测试用例本身的执行代价，两者的差距越大，该技术就越有效。 ( 4 ) 普遍性：回归测试用例集选择技术的应用范围，即适用的测试对象和软件类型。 2 3 测试用例优先级技术及其度量方法 回归测试选择技术解决了测试用例集选择问题，但没有讨论如何高效地使用选择出的测试用例集。测 试用例优先级技术将测试用例按照一定的优先级标准排序，使优先级高的测试用例可以优先执行，可以有 效提高测试用例集的性能。 2 3 1 优先级问题描述 e l b a u m 最早在文献 1 5 】中给出了测试用例优先级排序问题的形式化描述：给定：测试用例集l 尸r 是 ? 的全排列的集合；f 是一个从p 歹中元素映射到某实数的函数，找出蹒足： t 7 e p t 且( v 丁勺( r 7 z p t ) ( r ，丁) 【厂( r ) 厂( 丁”) 】 即寻找丁的某种排列对应的测试用例集合r 7 ，使其经目标函数厂映射后对应函数值最大。 k i m 等人认为优先级的方法同样适用于受时间约束的回归测试，并将优先级过程描述为p 4 j ： ( 1 ) 使用测试用例选择技术从测试用例集r 中选出子集r 。 ( 2 ) 对r 中每个测试用例赋予一个选择概率。 ( 3 ) 根据第二步中赋予测试用例的概率选择一个测试用例并运行。 ( 4 ) 重复第三步直到时间耗尽。 其中，步骤2 如何确定测试用例的选择概率是测试用例优先级技术要研究的主要问题。 研究者从多方面考虑目标函数的定义，提出了多种测试用例优先级技术。一般来说，常用的测试目标 有：尽早将程序中的错误暴露出来以提高测试用例集的错误检测率；尽快满足整个程序的代码覆盖率；尽 早建立测试人员对程序稳定性的信心；尽早将风险大的错误检测出来；尽早将测试人员关心的特殊代码部 分存在的错误暴露出来。 2 3 2 测试用例优先级技术 在之前的研究工作中，针对测试用例优先级技术已经有了大量的描述，这些优先级技术主要分为基于 代码要素的、基于反馈机制的、和基于非覆盖率信息的优先级技术。 大多数优先级技术是基于不同粒度的代码元素，如语句、程序块、函数等，依赖于测试用例和代码元 素之间的信息。w o n g 等最早提出了在回归测试选择技术的基础上，对测试用例集进行最小化或优先级处 理，根据测试用例的累计覆盖率来排序测试用例集【1 1 】。随后，r o t h e r m e l 和e l b a u m 等人利用测试用例的覆 盖率信息，提出了一系列测试用例优先级技术，例如累计的语句覆盖优先级技术、累计的分支覆盖优先级 技术、附加的语句覆盖优先级技术和附加的分支覆盖优先级技术，并进行了大量实验，有效提高了测试用 例集的错误检测效率【1 2 1 4 。6 1 。在此基础上，s r i v a s t a v a 和t h i a g a r a j a n 在文献【3 3 】中提出了基于累计覆盖率的 大型程序的测试用例优先级技术，该技术基于程序的变更并关注受影响的块覆盖目标函数，有效地分析了 二进制文件并实现了相关工具。 k i m 、屈波等人则研究了基于反馈机制、动态调整的测试用例优先级技术。k i m 将回归测试建模为一 个测试片段的有序序列，并且利用以前测试的信息提出了基于历史的优先级技术p 4 j 。屈波等给出了一种根 6 第二章测试用例集优化技术及其度量方法 据测试用例关联矩阵，动态调整测试用例优先级的技术，可以有效地应用于黑盒环境下的回归测试【3 5 1 。 也有一些优先级技术是利用非覆盖率信息的，如测试成本、错误严重等级、错误传播概率等。w a l c o t t 在文献【3 6 】中将时间约束下的测试用例集排序问题转化为0 1 背包问题，提出了基于时间限制的测试用例 优先级技术，并采用遗传算法求解。j e f f r e y 等引入程序分析技术，提出了基于相关切片的测试用例优先级 技术i j7 。“等通过实验分析、比较了用于测试用例集排序优化的多种搜索算法1 3 引。 2 3 3 优先级技术的度量方法 为了比较各种测试用例优先级技术，研究者提出了相应的度量方法，如语句覆盖率、累计函数覆盖率、 单位时间错误检测个数、平均错误检测效率等。其中，应用最为广泛的是r o t h e r m e l 等提出的a p f d 度量 方法，用于评估优化测试用例集的平均错误检测效率f 1 2 】。 钯翳 f a u l t l2345678 91 0 a x x b x 置 c xxxxxxx d x exxx t 1 ) 铡试用倒囊与错误集 t e s t c a s eo r a m e - d 啪a b ) t 1 对应的h p f d 值 t e s tc a s eo r d e r c - e 暑j d ” 00 20 4 覆o r l1 0 o0 20 40 60 g1 0 t e s ts u i t e f r a c t i o n t e s ts u i l ef r a c a i a a ( c ) t 2 对应的 胁值( t 3 对应的k p f d 值 图2 , 1a p f d 度量方法的实例 令测试用例集丁包含 个测试用例，集合f 包含检测出的m 个错误，测试用例集r ，为r 的某种排列， z f f 为r 中第一个检测出错误i 的测试用例在r 中的序号，则测试用例集丁对应的a p f d 值如下所示： a p f d = 、一( 2 1 ) n m2 n 由等式2 1 可知，a p f d 值介于0 和10 0 之间，a p e d 值越大，其平均错误检测效率越高。 如图2 1 所利屹j ，给出了测试用例与错误集的满足关系，当测试用例集n 的执行序列为a b c d e 时，其a p f d 值为5 0 ，当测试用例集砣的执行序列为e d c b - a 时，其a p f d 值为6 4 ，当测试用例 集乃的执行序列为c - e - b - a d 时，其a p f d 值为8 4 。于是有，在a p f d 度量方法下，乃的平均错误检 测效率高于死，而砣的平均错误检测效率高于n 。 在此基础上，e l b a u m 等提出了改进的a p f d c 方法，用于评估当错误严重程度和测试用例开销不同时， 给定的优化测试用例集的平均错误检测效率【6 ，4 2 4 3 1 。 令测试用例集z 包含船个测试用例，测试用例开销分别为龟t 2 ，名。集合f 包含检测出的m 个错误， 7 m雏佟雒外罅势协。 兰蟊k p。馨舌岂耋 粥阳柏鳍始珀o 簟。雌2雹母_芸一警冀#p 东南大学硕士学位论文 错误严重程度分别为石。五，五。测试用例集r ，为丁的某种排列，7 e 为丁7 中第一个检测出错误f 的测试用 例在f 中的序号，则测试用例集? 对应的a p f d c 值如下所示： ：兰三：竺二!三；三竺2二至1apfd 竺竺 。， 22 = 二二_ 兰。一 ( ) 。 二。三z s r i k a n t h 曾提出一种基于需求优先级的测试用例优先级技术及其度量方法【4 0 4 1 1 ，但是该技术不考虑测试用 例的开销差异。章晓芳等在文献 3 9 】中，提出了基于不同测试需求优先级和测试用例开销的优先级技术，并提 出了相应的度量方法，用于度量当测试用例开销及测试需求优先级不同时，优化测试用例集对应的单位测 试资源开销下测试需求优先级的满足比率。 2 4 问题分析 测试用例集选择技术和测试用例优先级技术能有效优化测试用例集，提高测试用例集性能，降低回归 测试成本，在回归测试中得到了广泛的应用。然而，已有研究仍然存在不足：1 ) 大多是基于测试用例开 销和测试用例的检错能力，没有考虑到测试用例开销的差异性，涉及到测试需求的不多；2 ) 大多没有考 虑回归测试的时间限制问题；3 ) 缺乏基于时间限制的测试用例集优化技术度量方法。此外，测试人员经 常面临着满足测试需求与测试时间限制之间的矛盾，需要在两者之间权衡，从而，考虑测试需求的覆盖率 以及单位测试用例开销下测试需求优先级的满足比率有着重要的现实意义。因此，很有必要研究一种新的 测试用例集优化技术，能考虑到测试用例执行时间以及测试需求优先级的差异，并且在明确给出测试时间 限制时，能够产生高效的测试用例集。 表2 1 测试用例与测试需求的满足关系s ( z 固 。， 7 一+ i ”7 。“? 。 u_v ：，r 。 0 t e s t i r 2 如 ，4如一魄 l 撼，。 ，“ ： “， ，* o 、糍 f l xxx ，2 f 3 矗x f 5 玷 表2 2 测试用例的相关统计信息 箩满足需求嗲数。鬟熬衍艄i = 17 恻翻开销下癌是囊求数溪 “ 7 90 7 7 8 f 2l11 0 如 230 6 6 7 “ 3 4o 7 5 f 5 34o 7 5 岛 3 4 0