（计算机软件与理论专业论文）回归测试下测试用例优化使用技术研究.pdf

摘要 回归测试是软件演化过程中一项频繁进行且开销巨大的任务。研究表明回归测试阶段 的耗费藩至会占到软件维护总费用的i 分之一以上。为了降低这部分工作的开销，提高回归 测试中测试用例的使用效率，研究者们围绕测试用例集的选择和优化使用等问题进行了大量 研究，相关的成果包括测试用例的选择性复用技术、测试用例集约简技术以及测试用例优先 级技术等。 回归测试中测试用例的选择和优化使用方法认为，不同测试用例对于测试目标的完成有 着不同的贡献程度，为了能够更快地达成测试目标，有必要将测试用例进行选择和优先绒排 序后使用。本文深入研究了影响测试用例选择使用的因素以及不同应用环境下的优化使用技 术等问题。主要工作包括：( 1 ) 在影响测试用例选择和使用因素方而，研究与已有测试用例 优化使用技术不同的方法：( 2 ) 在不同的应用环境下，研究具有更高适应性的测试用例优化 使用方法；( 3 ) 在优先级技术模型方1 面，研究现有对测试用例目标描述的改进方式；( 4 ) 在 度量方面，对王见有度量的物理意义进行了解释，并对其进行了相应的改进。 论文工作的主要成果表现在以下几个方面： 基于测试用例的设计信息，提出了新的测试用例优先级方法。作为已有技术的有益补 充，这种方法利用测试用例设计信息作为指导，将待复用的测试用例集进行排序和使 用，可以避免由于收集运行时测试用例覆盖率等相关信息带来的额外开销。与已有方 法相比，新方法具有些优良特性，例如算法时间复杂度与待测程序的规模无关等。 相关实验表明这种新方法适用于大规模程序的回归测试。 为了解决现有技术不能很好地应用于黑盒测试情况这一问题，提出了适用于黑盒环境 下的测试用例优先级技术及相应的算法。这种方法通过研究测试用例检测出错误种类 之间的关系，充分利用回归测试过程中的实时反馈信息，对测试用例进行比较和排序 使用，从而提高测试用例集的使用效率。此外，为了对测试结果进行评估，还对已有 的度量方法进行了修改，提出了针对黑盒测试的检错效率度量标准。 ， 在对已有的测试用例优先级技术模型改进的基础上，结合测试用例的选择和使用过程， 对测试用例的优先级排序问题做出了新的描述，提出了测试用例动态优先级的概念和 模型。以此为基础，本文还提出了测试用例动态优先级的基本过程和通用算法，以及 各种相关度量方法的改进。 针对现有测试用例优先级技术只能输出一个测试用例使用序列的问题，研究并提出了 并行环境下的测试用例选择和优先级技术。着重考虑了存在临界资源情况下，多处理 队列的测试用例优化使用问题，并分别就存存调度进程和不存在调度进程这两种情 况，讨论了相应的测试用例选择分配和优先级排序算法。并通过实例研究比较并验证 了这种方法的有效性。 关键词：软件工程、回归测试、测试用例优先级技术，动态优先级技术 a b s t r a c t r e g r e s s i o nt e s t i n gi san e c e s s a r yb u te x p e n s i v em a i n t e n a n c et a s kw h e ns o t s a r ee v o l v e s e s t i m a t e si n d i c a t et h a tr e g r e s s i o nt e s t i n ga c t i v i t i e sa c c o u n tf o ra sm u c ha so n e t h i r d so ft h ec o s to f s o f t w a r ep r o d u c t i o n i no r d e rt ol o w e rt h ec o s ta n dt oi n c r e a s et h ee f f e c t i v e n e s so fu s a g eo ft e s t s u i t e ，n u m e r o u st e c h n i q u e sh a v e b e e nr e p o r t e di nt h el i t e r a t u r eo ne f f t i v er e g r e s s i o nt e s t i n g ， i n c l u d i n gs e l e c t i v er e g r e s s i o nt e s t i n g , t e s ts u i t em i n i m i z a t i o na n dt e s tc a s ep r i o r i t i z a t i o n r e s e a r c h e so nt e s tc a s ep r i o r i t i z a t i o ni n d i c a t et h a td i f f e r e n tt e s tc a s e sc o u l dm a k ed i f f e r e n t c o n t r i b u t i o n st o w a r d st e s t i n gg o a l t oa c h i e v eb e t t e rp e r f o r m a n c e ，i ti s n e c e s s a r yt os o r ta n d p r i o r i t i z et e s tc a s e sf o rr e g r e s s i o nt e s t i n g t h em a i nr e s e a r c hi nt h i sd i s s e r t a t i o ni n c l u d e st e s ts u i t e p r i o r i t i z a t i o nt e c h n i q u e sa n dt h e i ri m p l e m e n t a t i o n si nd i f f e r e n te n v i r o n m e n t s ：( 1 ) o nt h er e s e a r c h o ft e s tc a s ep d o r i t i z a t i o n ，an e wp r i o d t i z a t i o nt e c h n i q u eb a s e do nt e s ec a s ed e s i g n i n gi n f o r m a t i o ni s s t u d i e d ( 2 ) o nt h ei m p l e m e n t a t i o no ft e s te a s ep r i o d t i z a t i o n , s o m en e wp r i o r i t i z a t i o nt e c h n i q u e s f o rd i f f e r e n tt e s t i n ge n v i r o n m e n t sa r ep r o p o s e d ( 3 ) o nt h em o d e lo ft e s tc a s ep r i o r i t i z a t i o n , an e w d y n a m i ct e s te a s ep r i o t i z a t i o nm e t h o da n di t si m p l e m e n t a t i o na r ed i s c u s s e d ( 4 ) o nt h em e a s u r eo f t e s tc a s ep d o r i t i z a t i o t t , e x i s t i n gm e a s u r e sa r ed i s c u s s e di nt h e i rp h y s i c a lm e a n i n g sa n dr e f i n e d t h em a i nc o n t r i b u t i o n so f t h ed i s s e r t a t i o na r el i s t e da sf o l l o w s an e wp r i o r i t i z a t i o nt e c h n i q u e sb a s e do nt e s td e s i g n i n gi n f o m a t i o ni ss t u d i e d a sa l l i m p o r t a n ts u p p l e m e n t a r yo fe x i s t i n gt e c h n i q u e s ，t h i sm o t h o dc a l la v o i de x t r ac o s t so f c o l l e c t i n gc o v e r a g ei n f o r m a t i o nb ys o r t i n gt e s tc a s e sa c c o r d i n gt ot h e i rd e s i g ng o a l s a l s oi t h a sb e e np r o v e dt h a tt h en e wm e t h o dh a ss o m em e r i t so nt i m ec o m p l e x i t ya n dr e g r e s s i o n t e s t i n gf o rl a r g es c a l es o f t w a r eu n d e rt e s t 1 r i 他a p p r o a c ho ft e s te a s ep r i o r i t i z a t i o nf o rb l a c kb o xt e s t i n gi sp r e s e n t e d 1 1 h i sa p p r o a c h e x p l o i t st e s th i s t o r yt ob u i l dt h er e l a t i o no fp o t e n t i a la b i l i t i e so fd e t e c t i n gf a u l t sb e t w e e n t e s tg a s e s ，b a s e do nw h i c ht e s tc a s e sa r ep r i o r i t i z e dt oi m p r o v et h ee f f c t i v e n e s so ft e s ts u i t e b e s i d e s t oa s s e s si t se f f e t i v e n e s s , n e wm e a s u r ei sa l s op r o p o s e df o rt e s t i n gi nb l a c kb o x e n v i r o n m e n t t h ed i s s e r t a t i o np r e s e n t san e wd y n a m i cp r i o d t i z a t i o nc o n c e p ta n dm o d e lb yc o m b i n i n gt h e p r o c e d u r eo ft e s ts e l e c t i o na n dr u nt i m ef e e d b a c k so ft e s tc a s ee x e c u t i o n b a s e d0 1 1t h i s m o d e l ，au n i v e r s a lp r i o r i t i z a t i o na l g o r i t h mi sd i s c u s s e d , a n dm e a s u r e sf o rt e s ts u i t ea r e c o m p a r e da n dr e f i n e d m o r e o v e r , t h ed i s s e r t a t i o np r o p o s e san e wp r i o r i t i z a t i o na p p r o a c hf o rp a r a l l e lt e s t i n g e n v i r o n m e n tb ye o m i d e r i n gc i r i t c a lr e s o u r c e s ae a s es t u d yi sa l s op e r f o r m e dt ov a l i d a t ei t s e f f e c i t i v e n e s s k e y w o r d s ：s o f t w a r ee n g i n e e r i n g , r e g r e s s i o nt e s t i n g ，t e s tc a s ep r i o r i t i z a t i o n , d y n a m i cp r i o r i t z a t i o n 东南大学学位论文 独创性声明及使用授权说明 一、学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名： 二、关于学位论文使用授权的说明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学 位论文的复印件和电子文档，可以采用影印、缩印或其它复制手段保存论文。 本人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外， 允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文 的公布( 包括刊登) 授权东南大学研究生院办理。 躲阵翩虢组 第一章引言 1 1 选题依据 第一章引言 信息技术的飞速发展，使得软件系统在社会的各个领域中起着越来越重要的作用。随着 软件功能和复杂度的增加，软件规模的逐渐变大，软件的质量和可靠性也逐渐成为人们关注 的焦点。作为保证软件质量的重要手段，软件测试是成功实现软件开发目标的重要保障。 回归测试是软件测试中的一项重要内容【l 】。由于软件开发是一个迭代的过程，需求和功 能的更改常会引起软件版本的不断更新，为了验证更新后软件的正确性，软件开发人员常使 用回归测试来检查修改部分代码的正确性及是否引入了新的错误。研究表明，软件维护费用 约占开发费用的三分之- - 2 1 ，而其中回归测试占软件维护阶段总费用半左右【3 】，因此降低 回归测试的成本有利于减少软件开发的总费用。围绕高效地进行l 旦l 归测试这二问题，人们针 对回归测试的方法和策略进行了大量的研究工作【1 4 】。 回归测试同普通测试的重要区别是，回归测试进行时有一个可供使用的测试用例集，因 此，最简单的回归测试方法是完全重用已有的测试用例集。然而，由于所修改的代码往往只 是程序中的一小部分，若完全复用已有测试用例，不仅代价高且效率低下。另种【旦i 归测试 方法是在资源允许的范围内，随机地重用部分已有的测试用例，这种策略代价相对较低但测 试效果不佳。为了能够解决测试用例复用的难题，人们根据代码修改的特点以及测试用例集 的自身特性，研究并提出了各种高效复用测试用例的方法和技术【5 9 】。现有对回归测试的研 究主要集中在如何根据程序分析结果以及测试历史对测试用例集进行有效的选择复用上，相 关技术包括测试用例的选择性复用 1 0 - 2 3 、测试用例集的约简 2 4 - 3 3 以及测试用例优先级技 术等。围绕这些研究内容，研究者们对而向对象程序的回归测试等进行了深入讨论 3 4 - 3 8 1 ， 进行了实验比较 3 9 - 4 3 1 并开发和介绍了相关工具用于提升测试的自动化程度【4 4 4 8 】。 测试用例优先级技术着重于研究回归测试中测试用例使用策略的问题【4 9 】。这种技术认 为，不同测试用例对于测试目标的完成有着不同的贡献程度，为了能够更快地达成测试目标， 有必要将不同的测试用例进行比较和排序，然后优先执行相对重要的测试用例。与普通的回 归测试方法相比，测试用例优先级技术依据测试的历史信息，以代码覆盖率或检错效率等为 标准，为每个待复用的测试用例赋予一个优先级，并在刚归测试过程中按优先级顺序选取和 执行这些测试用例 5 0 ，5 1 。研究人员通过实验表明，测试用例优先级技术可以很好地解决回 归测试中测试用例高效使用的问题，能够帮助测试人员尽早达到预期的覆盖率目标或检错目 标，有利于提高测试效率，降低测试的时问开销和人力成本。 围绕测试用例的优先级问题，现有的研究内容主要包括：寻找影响测试用例使用优先等 级的因素，测试用例优先级的计算方法，测试用例集的排序准则和方法等。在寻找影响测试 用例优先级的因素和测试用例优先级计算方面，研究者主要结合测试用例的历史执行情况， 综合各种因素对测试用例的优先级进行计算。在测试用例集的排序方面，针对影响测试用例 优先级的不同因素，研究者们提出了各种确定性的排序算法、遗传算法和动态调整等方法， 分别适用于不同的回归测试环境 5 2 ，5 3 1 。此外，为了给工程实践人员提供实验数据参考，指 导其选择适用的测试用例优先级技术，研究人员还提出各种有效性度量，并对各种排序方法 进行了实验和比较。 本文在广泛调研的基础上。试图通过对回归测试中测试用例的优化使用相关问题研究 一定程度上解决目前在大型程序的回归测试方面等存在的问题，提高测试用例优先级技术在 东南人学博： = 学位论文 不同环境下的应用效率；进一步拓宽测试用例优先级技术的应用范围，研究其在黑盒测试、 并行环境等方而的应用；改进测试用例优先等级的演化模型和计算方法：对现有各种度量方 法的物理意义进行解释并针对其4 i 足进行改进。论文还将对测试用例优先级技术的一些周边 问题。例如补充生成的测试用例的优先级设定与调整等问题进行探索。 1 2 国内外研究现状 与普通测试相比，回归测试进行时已经存在一个可用的测试用例集和相应的测试用例执 行历史，这部分信息可以被利用于有效地指导回归测试的进行，提高回归测试的效率。因此， 除少量文献研究了新生成测试用例优先级的问题外，测试用例优先级技术大多考虑测试历史 对测试用例优先级的影响。各种测试用例优先级技术区别主要在设置测试用例优先级时考虑 的因素不同，除此之外，是否考虑测试中的实时反馈信息、是否有测试者的参与等也是区别 不同技术的重要方面。 ( 1 ) 覆盖率相关技术 覆盖率相关的测试用例优先级技术是最早提出，且研究最为广泛和深入的方向，目前国 内外已有大量的相关研究成果。这一类技术主着重考虑了测试用例在代码或需求覆盖率上的 区别，将巧i 同的测试用例依据其历史一卜的覆盖能力进行排序后使用，以达到测试用例优化使 用的目的。常见的优先级分析和计算基础有语句覆盖率、函数覆盖率、分支覆盖率以及m a d c 覆盖率等。相关实验结果表明这类技术可以提高测试用例集的使用效率。 覆盖率相关技术能够适用于大部分的情况下怛1 归测试过程中，但由于需要收集测试用例 使用历史上的覆盖率信息，因此这类技术应用上存在一定的额外开销，同时会受到待测程序 规模的影响。此外，由于黑盒测试的代码不可见性，覆盖率相关的测试用例优先级技术很难 应用于黑盒测试过程中。 ( 2 ) 非覆盖率相关技术 一些研究者注意到了与覆盖率相关测试用例优先级技术的不足之处，围绕其他影响测试 用例性能的因素进行了研究工作。h s r i k a n t h 从需求的角度出发，同时结合测试用例满足需 求的情况以及需求的权重，提出了新的测试用例优先级的设定方法。k w a l c o t t 等认为测试 用例的执行时问是怛l 归测试过程中一个重要因素。他们结合测试过程可用的资源，提出了按 照测试用例的历史执行时间对其进行优先级排序的方法。b k o r e l 等通过比较修改前后的代 码在系统模型上的区别，在基于状态的模型的基础上对测试进行排序和优化。pt o n e l l a 等从 测试者经验的角度出发，提出了一种机器学习的方法，利用用户知识对测试用例重要程度进 行评估和排序。 非覆盖率相关的测试用例优先级技术从另外的角度对不同测试用例的重要程度进行了 审视，提出了一些新的优先级方法，是对测试用例优先级方法的扩展以及覆盖率相关技术的 有益补充。目前相关研究方向还包括寻找其他影响测试用例优先等级的因素，研究针对黑盒 测试下有效的优先级排序方法等。 ( 3 ) 测试用例优先级的计算方法 在测试用例优先级的计算方面，不同的技术采用了不同的方法。以覆盖率相关技术为例， 一部分技术基于测试用例的语句覆盖率、函数覆盖率等，将所有的测试用例按照其覆盖能力 的强弱进行排序。这类技术在对测试用例进行排序完毕后，不再根据测试用例的使用结果对 顺序进行再次调整。另一部分技术则关注了代码的整体覆盖情况。这些技术首先选择使用覆 盖能力最强的测试用例，然后根据测试的反馈结果或对结果的预测，选择对未测试代码部分 具有最强覆盖能力的测试用例，逐个选取测试用例以达到间接排序的目的。这一类技术本质 2 第一章引言 上采用的是一种逐个挑选的方法。 现有各种计算方法存在的主要缺点是每次选取一个局部最优的测试用例或序列，未能考 虑动态反馈信息对测试用例集的整体影响情况。相关研究方向包括寻找有效的优先等级计算 方法，综合测试反馈信息对测试用例优先集进行再调整的方法，多目标测试用例优化技术的 计算方法等。 ( 4 ) 并行环境下的优先级技术 现有各种优先级技术仅考虑单机环境下的测试活动，但在工程实践中，可能存在着多台 机器相互协作同时进行叫归测试，一旦测试过程中存在临界资源使用问题，如何将测试用例 有效地分配给每台参与测试的机器将成为一个难题。因此，有必要在对测试用例进行优先级 排序的时候考虑多机并行处理的情况，将测试用例处理并输出到对应的多个顺序使用序列， 同时考虑尽量高效地利用临界资源。相关问题及算法的研究，目前尚无文献见诸报道。 并行环境下的优先级技术研究需要解决的问题有：寻找影响并行环境下测试用例优先级 的因素，寻找优先级的计算方法以及并行环境下优先级技术有效性的度量方法等。 1 3 主要研究内容 根据国内外在测试用例优先级技术方而的研究现状及其最新发展动态，本文主要在测试 用例优先级技术、测试用例优先级的动态调整技术以及并行环境下的测试用例优先级技术等 方而展开了深入的研究。具体而言，论文主要包含以下研究内容。 1 3 1 测试用例优先级技术研究 在测试用例优先级研究方而，本文将主要针对非覆盖率相关因素，寻找新的影响测试用 例优先级的各种因素，以及相应的优先级计算和调整方法。相关研究内容主要有： ( 1 ) 基于测试用例设计信息的优先级技术 测试用例优先级技术的目的足将不同能力的测试用例进行有效区分，并优先执行对完成测 试目标具有最大贡献的测试用例。传统的优先级技术主要考虑了覆盖率等相关信息，忽略了测 试用例自身属性对测试用例优先级的影响，特别是设计目的等测试用例的设计信息，未能在测 试过程中对其进行有效利用。 我们拟从测试用例的设计信息出发，研究基于测试用例设计目的的测试用例优先级技 术。首先定义基于测试用例设计目的的测试用例关系矩阵，获得测试用例在设计信息一卜的关 联属性，然后以此为基础，考虑待复用测试用例和后续补充测试用例的优先级赋予和计算等 相关问题，并通过相关实验来验证这种方法的实际应用效果。最后，我们还将进一步讨论算 法的改进方向。 ( 2 ) 面向黑盒测试环境的优先级技术 现有各种优先级技术大多基于代码相关或测试用例覆盖率相关的信息，但由于黑盒环境 下的代码不可见性，使得现有各种优先级算法无法应用于黑盒测试环境中。针对这一情况， 我们拟设计一种能够有效应用于黑盒环境的测试用例优先级算法。我们将通过分析测试用例 执行的反馈信息，建立测试用例在检测错误方面的内在关联，并根据实时的检错信息计算和 调整测试用例的优先级，以达到高效使用测试用例集的目的。此外，我们还将基于部分应用 软件，开展真实实验，验证方法的有效性，同时基于实验的结果讨论这一方法的适用范围以 及优先级的改进计算方法。 3 东南人学博： j 学位论文 1 3 2 优先级的演化及度量研究 测试用例优先等级的计算方法是优先级技术中的重要研究方向。现有各种方法中，大部 分都是采用的贪心算法或者各种启发式搜索算法，计算并寻求一个最佧或者接近最佳的测试 用例使用序列。这种方法的特点是一旦计算完毕后，在随后的整个回归测试过程中，测试用 例的使用顺序将不再改变。 由于测试用例的最佳使用策略同实际测试时的各种凼素密切相关，因此很难预先确定一 个适合的最佳测试用例使用序列。我们拟提出种测试用例优先级的动态调整技术，通过在 测试过程中获取实时的反馈信息，对尚未使用的测试用例的优先等级进行不断调整，使整个 测试用例顺序集不断演化，逐步适应当前的测试环境，从而获得更好的测试效果。我们还将 对这一动态演化的模型进行一些理论分析，此外，还会设计一系列试验验证这种方法实际性 能。最后，我们还将结合工程实践讨论测试用例优先级动态调整方法的特点、适用环境以及 未来的改进方向等。 1 3 3 并行环境下的测试用例优先级技术研究 传统的测试用例优先级技术定义指出，优先级问题的目标是寻找给定目标下测试用例集 的最优排列，因此各种优先级算法通常将测试用例排列并输出成一个序列。在单机进行测试 的情况下，这个输出序列可以很好的满足需求，但如果同时存在多个主机同时进行测试活动 时，如何将这个测试序列有效地分配至各个参与测试的主机将成为一个难题。特别是当存在 临界资源时，现有的各种优先级方法将不再能够适用。 我们将从并行的角度出发，重新定义测试用例优先级技术在这种环境下的目标，并以此 为基础，研究存在调度进程和不存在调度进程两种情况下，测试用例的优化使用方法。作为 辅助，我们还将研究相关的有效性度量方法。最后，我们将通过实例研究检验这种方法的有 效性，并对相关问题的未来研究方向作初步的讨论。 1 4 论文主要成果 本文围绕回归测试中的测试用例优先级相关问题，对基于非覆盖率信息的优先级技术、 面向黑盒的优先级技术、优先级的动态调整技术及并行环境下的优先级技术进行了深入研究。 论文的丰要成果表现在以下几个方面： 研究了测试用例设计信息对测试用例优先级的影响，提出了基于测试用例设计信息的 优先级方法，讨论了复用测试用例部分和新增测试用例部分的优先级设定和调整算 法，并通过实验验证了方法的有效性。 针对现有优先级技术不能应用于黑盒测试环境这问题，结合黑盒测试的特点，提出 了一种新的以测试输出结果为基础的测试用例优先级方法，同时进行了相关实验，并 通过实验结果对方法的有效性进行了验证。 针对测试过程中测试用例优先级未随实时反馈结果进行更新的问题，提出了优先级动 态调整的技术，并建立了相关模型。同时讨论了在回归测试中测试用例优先级演化以 及在回归测试间测试用例优先级演化的相关问题。以优先级动态调整模型为基础，提 出了一种通用的优先级演化算法，结合对测试用例之间联系的描述，根据测试过程中 实时的反馈信息对剩余测试用例的优先级进行及时的调整。此外，还从理论上证明了 这种算法的一些优良特性。 研究了已有各种度量方法的适用范围和物理意义，指出了现有度量存在的不足，并针 对考虑资源约束的环境提出了改进的度量标准及相关的计算方法。针对黑盒环境等特 殊的测试场景，进行了度量计算公式的推导和化简，并对改进度量方法的扩展以及相 4 第一章弓i 言 应计算方法进行了简要的介绍。 针对现有技术不能很好适用于并行环境这一问题，提出了并行环境下的测试用例优先 级技术，并给出了存在调度进程和不存在调度进程时的测试用例集划分方法。探讨了 在并行环境下测试用例优先级的目标、适用的度量标准、补充生成测试用例的优先级 设定等问题，并通过实例研究比较了优先级算法与随机选取算法性能的差异，结果有 利于指导测试人员根据测试环境选择适宜的技术。 1 5 论文结构 论文共七章，论文篇章结构安排如下： 第一章作为论文的引言，初步介绍了回归测试中测试用例优化使用技术的研究背景和意 义，介绍了国内外的相关研究现状，描述了论文的研究内容，最后简要地介绍了论文的创新 点和论文结构。 第二章给出了测试用例优先级技术的相关定义，介绍了当前研究工作以及研究方向，同 时介绍了i = l 前研究工作存在的不足和问题。 第三章提出了一种全新的基于非覆盖率因素的测试用例优先级技术及相关计算方法，并 通过实验证明这种方法的有效性。 第四章针对现有技术不能应用于黑盒测试环境这一问题，提出了一种新的测试用例优先 级技术，给出了测试用例优先级相应的计算方法，并给出了相应的度量标准，最后通过实验 验证了该优先级技术的有效性。 第五章讨论了测试用例的计算相关问题，提出了测试用例优先级的动态调整模型，给出 了一种通用的优先级方法，并从理论一卜证明了这种方法的一些优良特性。作为评估方法有效 性的重要指标，本章还详细讨论了现有度量的局限性及相关扩展和改进方法。 第六章针对并行环境的特点，提出了针对并行环境的测试用例优先级方法，同时讨论了 并行环境下测试用例优先级的i = t 标、度量标准、资源约束下的回归测试以及补充生成测试用 例的优先级设定与演化等相关问题。 第七章是对整个论文的总结，综述了我们在回归测试中测试用例优先级技术领域取得的 研究成果，简单阐述了当前正在进行工作，并对测试用例优先级技术的未来研究方向进行了 展望。 5 第二：章回归测试的测试用例优先级技术 2 1 引言 第二章回归测试的测试用例优先级技术 软件开发是一个迭代的过程，需求和功能的更改会引起软件版本的不断更新。为了验证 更新后软件的正确性，软件开发人员常进行回归测试来检查修改后代码的正确性及是否引入 了新的错误。在软件生命周期中，回归测试是一项耗费巨大的软件维护活动，研究表明，软 件维护费用约占开发费用的三分之- - 2 1 ，而其中恒i 归测试活动又占软件维护阶段总费用一半 左右【3 】。为了降低这部分的费用，提高回归测试效率，研究者们提出了各种测试用例的优化 使用方法【1 ，4 1 ，相关技术包括测试用例的选择性复用【l 】，测试用例集的约简 2 6 1 以及测试用 例优先级技术等 4 9 1 。 测试用例优先级技术认为，不同的测试用例在检测错误或覆盖代码等方而的能力不同， 如果将测试用例按照一定的准则进行排序后使用，有利于在较短的时问内检测出更多的错误， 或是尽快达到覆盖率标准，从而降低回归测试的成本。另一方而，由于工程实践中的叫归测 试行为常受到时问等资源的限制，采用测试用例优先级技术能够在有限的资源下运行更多有 效的测试用例，有利于保证软件质量。 理想的回归测试环境下。测试人员可以从已有的测试用例集中选择出供复用的测试用例 子集，并在随后的回归测试过程中逐个执行选出的测试用例，直至所有的测试用例被执行完 毕。与普通测试相比，回归测试进行时已经存在个可用的测试用例集和相应的测试用例执 行历史，这部分信息可以被利用于有效地指导回归测试的进行。因此，理想环境下的测试用 力优先级技术应用过程可以被捕述为如下步骤：首先基于测试用例历史执行情况对复用的测 试用例集进行评估，选取并执行具有最高优先级的测试用例；然后根据执行的反馈信息调整 剩余测试用例的优先级，反复这一过程直至测试结束。 在工程实践环境中，测试过程常受到诸如软件交付时问等资源的约束，选出供复用的测 试用例不一定能够被全部执行。因此在受资源约束的情况下，测试用例优先级技术应用的技 术条件有所不同。测试用例优先级技术的相关研究同时考虑了这种应用情况。j m k i m 等人 将资源受限下测试用例优先级技术应用的过程描述为如下四个步骤【5 0 】；( 1 ) 对测试用例集应 用选择复用技术，获得复用的测试用例子集；( 2 ) 对每个带复用的测试用例赋予一个选择概率； ( 3 ) 依据第二步赋予的选择概率选择并执行一个测试用例；( 4 ) 重复第三步直至资源耗尽。其中 最重要的工作是第二步，即对测试用例选择概率的计算问题。 尽管对测试用例优先级赋予这一核心问题的表述不同，但现有关于测试用例优先级的研 究主要都集中在如何确定和表述测试用例的重要程度，即如何对测试用例进行排序这一问题 上。现有技术多采用直接的排序或是各种成熟的搜索算法，也有部分技术考虑了资源约束的 情况，使用启发式的方法在相对较短的时间内获得一个近似最优解以满足需求。 测试用例优先级本身是一个时间复杂度比较高的过程。z l i 等认为，若单纯从寻找最优 集合这过程上考虑，求解测试用例优先级问题等同于求解背包问题。所以，测试用例优先 级问题至少是个n p 难问题 5 2 1 。但相关实验研究表明，利用启发式方法对测试用例集进行 排序处理后获得效率上的提高大于其开销。因此测试用例优先级方法依然是一种实用高效的 回归测试方法。 7 东南大学博士学位论文 2 2 相关研究 本节对同归测试及测试用例优先级问题中的一些基本概念进行了描述，并讨论了测试用 例优先级技术的相关问题。随后介绍了国内外研究工作及存在的问题，指出本文研究的着眼 点和思路。 2 2 1 基本概念 回归测试同普通测试的重要区别是，回归测试进行时有一个可供使用的测试用例集，因 此，最简单的同归测试方法是重用所有的测试用例，但这种方法效率低且代价高，所以现有 对同归测试的研究主要集中在如何有效地对测试用例进行复用。 gr o t h e r m e l 等指出，典型的同归测试过程可以描述为【l 】： 1 从现有的测试用例集t 中选出一个子集t 。 2 在修改后的代码p 上运行t ，用以确定p 的正确性。 3 建立新的测试用例集t ”。 4 在修改后的代码p 上运行t ”，用以确定p 的正确性。 5 由t ，t ，t ”建立p 的测试历史和测试用例集t ”。 其中，针对第一步的研究着重于测试用例的选择问题，针对第二、四步的研究着重测试用例 的执行问题，针对第三步的研究着重覆盖率和测试用例生成问题，针对第五步的研究着蕈于 测试用例的维护问题。e w o n g 等进一步指出，为了提高测试用例的使用效率，可以对每个 待使用的测试用例赋予一个优先级，在同归测试过程中按照优先级顺序来执行测试用例 4 9 1 。 j k i m 等将优先级技术的应用过程描述为如下几个步骤 5 0 1 - 1 使用测试用例选择技术从测试用例集t 中选出子集t 。 2 对t 中每个测试用例赋予一个选择概率。 3 根据第二步中赋予测试用例的概率选择一个测试用例并运行。 4 重复第三步直到资源耗尽。 测试用例优先级技术应用过程的第二步，即如何确定测试用例的选择概率是优先级技术 研究中的关键问题。由于设定测试用例选择概率的最终目标是将测试用例集进行排序使用。 研究者们也常用测试用例的顺序来间接描述测试用例的选择概率。g r o t h e r m e l 等从排序的 角度对优先级技术进行了描述，他们将这一问题抽象成寻找测试用例全排列中的最优集合问 题，形式化给出了测试用例优先级技术研究目标的定义【5 1 】。 定义2 1 ：测试用例优先级技术研究目标。给定测试用例集lr 的全排列集合尸乃以 及从尸r 到实数的函数，求个t p t 使得( v r ”x r ”尸z ) ( r ，n 吠功颚r 伽。 这里，集合p r 包含了测试用例所有可能的执行顺序，而函数厂的值代表对测试结果的评价。 g r o t h e r m e l 等的定义实际指出了研究中两个需要解决的问题：函数f 的定义和在此基 础上最优排列的寻找方法。对于第一个问题，当前的研究主要通过测试用例的历史执行情况， 定义与需要达到的测试目标相关的函数。对于第二个问题，现有技术多采用直接的排序或是 各种成熟的搜索算法，也有部分技术考虑了资源约束的情况，使用启发式的方法在相对较短 的时问内获得一个近似最优解以满足需求。需要指出的是，由于难以直接构造出研究目标定 义中描述的函数f ，大部分研究工作仅给出了对于单个测试用例优先级计算方法，以及在此 之上的最优排列的构造或搜索方法。 为了能对各种优先级技术的有效性进行度量，同时为不同测试用例优先级方法之间的比 较提供定量标准，研究者们在讨论测试用例优先级计算方法之外，还提出了关于排序后使用 的度量标准。由于测试的一个直接目标是检查待测软件是否存在着错误，因此研究者们首先 关注了测试用例优先级方法在错误检测方面的能力。g r o t h e r m e l 等指出，与采用随机顺序 8 第二：章回归测试的测试用例优先级技术 的测试相比，测试用例优先级技术的一个重要贡献是能够更快地检查h 错误，这种优势可以 用测试用例使用个数和检测错误个数之问的关系来量化。为此，g r o t h e r m e l 等提出了a p f d ( w e i g h t e da v e r a g eo f t h ep e r c e n t a g eo f f a u l t sd e t e c t e d ) 度量标准【5 1 】。 用例 检测出的错误 l234567891 0 a xx b xx xx c xx x x x xx d x e x x x a 测试用例及检测出的错误 测试用例执行顺序：a - b - c - c 卜e 丑 求 l 跨 船 制 靼 00 20 40 60 81 0 测试用例使用情况 b 排序后测试用例集t l 的a p f d c 排序后测试用例案1 2 的- 址f d 图2 1 a p f d 度量示例 图2 1 是对a p f d 度量标准的一个综合描述。图2 1 a 表示测试用例及对应检测出的错误， 例如，对测试用例b ，执行后会检测出编号为l 、5 、6 、7 的错误。图2 - 1 ( b ) 和图2 1 ( c ) 分别 表示在不同测试用例使用顺序下测试用例的使用个数与检测出错误个数之间的关系。以图 2 1 ( b ) 为例，测试用例的执行顺序是a b c d e ，在a 被执行后共检测出2 个错误，占所有 能够被检测出错误总数的2 0 ，对应图中( o 2 ，2 0 ) 这个点。将所有测试用例对应的点连成一条 折线，对应当前测试用例顺序集的a p f d 值即为曲线下方用阴影表示的部分占整个而积的百 分比。图2 1 ( b ) 与( c ) 的a p f d 值分别为5 0 与8 4 。 s e l b a u m 等给出了a p f d 的计算公式。设测试用例集r 包含刀个测试用例，表示测试 用例集能够检测出的错误集合，包含所个错误，z e 表示顺序集r 中第一个检测出错误f 的测试用例，r 的a p f d 值可以用如下公式计算： apfd：ltfi+tf2+tf1-一1 ( 1 ) 删2 n 其中，a p f d 的取值范围是0 到1 0 0 。不同测试用例顺序集中，a p f d 的值越高表示对应测 试用例顺序集检测错误的效率相对越i 苗。 a p f d 度量标准主要针对回归测试中错误的检测速率，对测试用例顺序集的能力进行了 量化。除此之外，研究者们还根据测试用例优先级技术不同的应用环境，提出了a p f d 的各 种改进表示方式。 2 2 2 测试用例优先级技术 为了寻求测试用例最优的使用顺序，研究人员提出了多种测试用例优先级方法。以影响 测试用例优先级的因素作为分类，现有研究工作可以分为基于覆盖率相关信息和非覆盖率相 关信息的两大类。 ( 1 ) 覆盖率相关技术 优先级技术最初作为一种回归测试的辅助技术被提出。e w o n g 等在文献【4 9 】中首先指 出，回归测试中选择出待复用的测试用例集后，对其进行进一步进行精简和优化可能会耗费 过多的资源。作为已有方法的有益补充，可以将待复用的测试用例集按照其对代码的覆盖能 力进行排序，并以此标准依次选择和执行测试用例，从而提高回归测试中错误检测的速度和 效率。e w o n g 等的初步研究表明测试用例优先级技术是有效的，因此研究者随后做了许多 9 东南大学博士学位论文 工作。主要围绕测试用例历史覆盖率来指导进行高效【旦l 归测试。 s e l b a u m 等首先结合覆盖率对测试用例优先级排序问题进行了研究。他们的基本思路是 优先运行覆盖能力较强的测试用例，当单独考虑测试用例能力时，测试用例的执行顺序应该 是按照测试用例各自的覆盖率，当整体考虑代码的覆盖率时，测试用例应该按照对代码累计 覆盖牢的贡献来排序。s e l b a u m 等分别钏。对语句覆盖、函数覆盖和对重要代码覆盖的情况， 给 h 了1 2 种不同的测试用例排序方法【5 4 】。这些方法通过评估测试用例的历史覆盖率对回归 测试中累计覆盖率的贡献程度和潜在检错能力，逐个选取并使用当前情况下具有最佳代码覆 盖率或最强潜在检错能力的测试用例，最终达到优化使用测试用例的h 的。随后，gr o t h e r m e i 等进行了进一步研究，补充了在测试用例的分支覆盖能力基础上进行优先级计算的方法，并 将其与随机顺序和理想的最优化顺序进行了简单的比较【5 l 】。 s e l b a u m 等认为已有的方法仅考虑了覆盖率因素，忽略了工程实践所关注的测试耗费问 题，在这个基础上，他们提出了综合考虑测试耗费和错误严重程度的测试用例优先级方法 【5 5 。新方法是对文献【5 4 】中所述各种优先级方法的扩展，即在之前的覆盖率标准基础一卜增加 了对测试开销的考虑，将原来的覆盖率改进为单位覆盖消耗比率，同时结合错误的严重程度 重新评估测试用例的潜在检错能力。以此为标准，他们对累计语句覆盖、累计函数覆盖和累 计错误索引等j 种测试用例优先级方法进行了改进。 j k i m 等受统计质量控制方法的启发，提出了新的测试用例优先级技术。他们指h ，在 工程实践中，回归测试视是具有偏序关系的一组测试行为序列，且测试过程受到资源约束影 响【5 0 】。以此为模型，他们提出了基于各种测试覆盖率历史的测试用例优先级技术。与已有 技术小同，j 。k i m 等的方法首先为历史卜各阶段测试历