（计算机应用技术专业论文）回归测试方法及测试用例优化研究.pdf

摘要软件测试是软件开发的一个重要环节，随着现代信息技术的飞速发展，软件产品逐渐渗透应用到社会的各个领域，软件产品的质量自然成为人们共同关注的焦点。回归测试是在软件开发过程中为确保软件质量进行的一种常用的验证测试方法。其过程十分重要且成本昂贵。因此，提供有力的机制对测试用例库和测试过程进行统一的维护和管理，减少回归测试的代价，提高效率，是整个软件回归测试研究的重点和难点。本文围绕回归测试这个主题，首先介绍了软件测试的一些基本理论知识，并对回归测试策略简要介绍，比较二者的不同。然后重点讨论了基于代码信息的回归测试选择，优先级技术和测试用例的约简技术，介绍各技术重要算法，并做简要的算法分析，分析其优缺点。文章分别从面向对象和面向过程两个方面，讨论了图形遍历技术及回归测试选择算法。由于现有的测试用例优化技术普遍只对测试某个阶段做出优化，而忽视了测试用例设计信息对测试用例优先级的影响，测试用例的生成和约简，以及优先级排序的整体性，在组织回归测试时，每次回归总是花费大量时间分析程序本身和测试用例，没有利用之前的分析结果建立一个可借鉴的系统。本文提出了基于图形和测试需求的用例选择排序方法。该方法关注测试目标，基于程序构造图形，分析优化需求关系，在回归测试策略改变的情况下，依然可以重用原有的需求集，使之用于用例生成，约简，排序过程中，而不需重新对系统进行分析。该算法能比以往的优化方法更灵活的应对回归测试策略的改变，尤其适用于那些需要多角度评估的系统。本文的最后讨论了其算法描述，做了详细的算法分析，并对下一步的研究方向做出了展望。关键词：软件测试，回归测试，测试用例约简，优先级技术a b s t r a c ts o f t w a r et e s t i n gi sa ni m p o r t a n ta s p e c to fs o f t w a r ed e v e l o p m e n t w i t ht h er a p i dd e v e l o p m e n to fm o d e mi n f o r m a t i o nt e c h n o l o g y , s o f t w a r ep r o d u c t sf i n dt h e i rw a y si n t oa l la r e a so fs o c i e t y t h eq u a l i t yo fs o f t w a r ep r o d u c t sn a t u r a l l yb e c o m et h ef o c u so fc o m m o nc o n c e r n r e g r e s s i o nt e s t i n gi sc o m m o n l yu s e dt ov e r i f yt h eq u a l i t yo fs o f t w a r ei nt h ep r o c e s so fs o f t w a r ed e v e l o p m e n t i t sq u i t ei m p o r t a n ta n de x p e n s i v e t h e r e f o r e ，p r o v i d i n gap o w e r f u lm e c h a n i s mt om a i n t a i na n dm a n a g et h et e s tc a s e sa n dt e s tp r o c e s s ，t or e d u c et h ec o s to fr e g r e s s i o nt e s t i n g , a n dt oi m p r o v et h ee f f i c i e n c yo fr e g r e s s i o nt e s t i n ga r et h ee m p h a s e sa n dd i f f i c u l t i e si nt h ew h o l es o f t w a r et e s t i n g f o c u s i n go nt h et h e m eo fr e g r e s s i o nt e s t i n g , t h i st h e s i sf i r s t l yi n t r o d u c e ss o m eb a s i ct h e o r e t i c a lk n o w l e d g eo fs o f t w a r et e s t i n g , g i v 髂ab r i e fi n t r o d u c t i o nf o rr e g r e s s i o nt e s t i n ga n dc o m p a r e st h ed i f f e r e n c eb e t w e e nt h e m t h e nw ef o c u so nc o d e b a s e dr e g r e s s i o nt e s ts e l e c t i o n ，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 dt e s ts u i t e sr e d u c t i o n t h et h e s i sg i v e ss o m er e l a t e da l g o r i t h m sa n db r i e f l ya n a l y z e st h e i rs t r e n g t h sa n dw e a k n e s s e s i ta l s od i s c u s s e st h eg r a p ht r a v e r s a lt e c h n o l o g ya n dr e g r e s s i o nt e s t i n gs e l e c t i o na l g o r i t h mi nb o t ho b j e c t o r i e n t e dp r o g r a ma n dp r o c e s s - o r i e n t e dp r o g r a m c u r r e n to p t i m i z a t i o nt e c h n i q u e si ng e n e r a lo n l yo p t i m i z es o m ea s p e c t so ft e s tc a s e sb u ti g n o r et h et e s tc a s ed e s i g ni n f o r m a t i o no nt h ei m p a c to ft e s tc a s ep r i o r i t i z a t i o n t h e yn e g l e c tt e s tc a s eg e n e r a t i o n ，r e d u c t i o na n dp r i o r i t ys c h e d u l i n ga r et h ew h o l es y s t e m i na no r g a n i z a t i o no fr e g r e s s i o nt e s t i n g ，al o to ft i m ei su s e dt oa n a l y z et h ep r o g r a mi t s e l fa n dt e s tc a s e si ne a c hr e g r e s s i o nt e s t i n g w ed o n te s t a b l i s har e f e r e n c es y s t e mb yt h ef o r e g o n er e s u l t s t h i st h e s i sg i v e san e wt e s tc a s eo p t i m i z a t i o nm e t h o db a s e do ng r a p ha n dt e s td e m a n d t h em e t h o de m p h a s i z e st e s to b j e c t i v e s i tc o n s t r u c t sg r a p hf o re a c hp r o g r a ma n dp r e d i g e s t st e s td e m a n d s s ow ec a ns t i l lr e u s et h eo r i g i n a ls e to fr e q u i r e m e n t st ot e s tc a s eg e n e r a t i o n ，r e d u c t i o na n ds o r t i n gw i t h o u th a v i n gt or e - a n a l y s i st h es y s t e m t h ea l g o r i t h mc a l lb em o r ef l e x i b l et h a no t h e r sw h e nr e g r e s s i o nt e s t i n gs t r a t e g yi sc h a n g e d ，e s p e c i a l l yf o rt h o s es y s t e m sw h i c hn e e dt ob ea s s e s s e dm u l t i a n g l e f i n a l l y , w ed e s c r i b ea n da n a l y z et h ea l g o r i t h md e t a i l e d l y ，a n da l s om a k et h ep r o s p e c to ft h ef u r t h e rr e s e a r c h k e yw o r d s ：s o f t w a r et e s t 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 er e d u c t i o n ，p r i o r i t yt e c h n i c a li ! i独创性声明本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特j | l , j j j n 以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。签名：整凰园e t 期：趁蜂皿关于论文使用授权的说明本人完全了解武汉理工大学有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权武汉理工大学可以将本学位论文的全部内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段保存或汇编本学位论文。同时授权经武汉理工大学认可的国家有关机构或论文数据库使用或收录本学位论文，并向社会公众提供信息服务。( 保密的论文在解密后应遵守此规定)武汉理工大学硕士学位论文1 1 课题研究背景第1 章绪论软件测试作为软件项目不可缺少的环节，其目的是保证软件质量、提高软件产品可靠性。计算机安全问题由来已久，尤其是在软件方面，软件故障问题层出不穷，软件危机屡屡造成严重后果，这些都使人们意识到软件测试对软件质量保证具有重大意义。随着计算机应用领域的不断扩大，软件系统日趋复杂，规模日益庞大。如何保障软件质量，确保软件的高度可靠性，这一问题技术上面临着巨大挑战。软件方面很小的问题就可能造成对生命，国家或财产带来巨大损失，尤其是在军事，航天科技等方面，更应该全面的杜绝这样的错误发生。r e g o r yt a s s c y 博士对美国软件业现状研究表明：到2 0 0 0 年为止，美国软件从业人员达到1 ，2 8 2 ，0 0 0 人，软件年销售总额达到1 ，8 0 0 亿美元，同时，软件失效导致每年5 9 5 亿美元的经济损失，据估计，若能减少当前软件中1 3的缺陷，就能挽回2 2 2 亿美元经济损失。因此，改进软件质量已经成为取得高投资回报率的直接途径，软件质量在安全和财产中影响重大，是企业生存的基础，是国家，人身安全的保障。软件工程是现代软件设计的重要方法，是高质量，高可靠性软件设计的基础。为了保障软件工程的稳定可靠，一种新的技术应运而生。1 9 7 2 年b i l lh c t z e l首次提出软件测试的概念。在近2 7 年的发展过程中，软件测试技术得到了飞跃发展和进步，软件测试已经成为软件工程的重要组成部分乜1 。软件测试的直接目的是发现软件中存在的缺陷。随着软件工程技术的发展，软件规模的增大，软件测试在软件开发过程中的作用显得越来越重要。据统计，软件开发总成本中，用在测试上的开销要占4 0 、5 0 馏1 ，对于一些对可靠性，安全性要求较高的软件，测试费用则可能占整个软件项目丌发所有费用的3 至5 倍。软件测试在国内外己经受到广泛重视，大量专家学者对其进行了长期的研究。在软件生命周期的任何一个阶段，只要软件发生了改动，就可能给该软件带来问题。此时，就必须重新测试现有功能，以便确定修改是否到达了预期的目的，并且该修改是否产生了新的问题。这种验证修改的正确性及其影响的测试称为回归测试剐n 利。由于程序构建的复杂性，各组件相互关联，很容易在武汉理工大学硕士学位论文修改过程中产生新的错误，历史数据表明在改正错误的过程中引入新的错误的概率高达2 0 5 0 9 6 。回归测试在软件生命周期中扮演着重要的角色，历史上由于忽视回归测试而造成严重后果的例子不计其数，导致美国阿利亚娜5 型火箭发射失败的原因就是在于其软件存在缺陷，软件中被复用的代码没有经过充分的回归测试口1 。回归测试可以重用以前的测试过程，这是一种最简单有效的测试方法。随着工程进展，测试用例的数目会日益庞大，测试人员有限以及人员的流动性，有些测试用例的运行周期可能很长，测试组对测试用例以及回归测试过程的控制能力将会逐渐减弱，这些都将使得前期测试投入加大，在实际操作中，对每次变化都进行全面测试，不仅是不切实际，也完全没有必要。因此，需要在软件频繁变化的时候，提供强有力的机制对测试用例库和测试过程统一维护和管理，合理的组织回归测试，减少回归测试的代价。这是整个软件回归测试研究的重点和难点。1 2 国内外研究现状及进展回归测试方法的研究包括测试环境自动化h 棚，捕获一回放机制哺1 ，测试用例的选择优化技术口吲，测试的覆盖率以及错误点的定位n 们和回归测试的过程管理n 刀等方面。归纳起来，主要是以下四个基本问题的研究：1 ) 如何鉴别修改所影响的部分，即修改影响分析；2 ) 采取何种策略来重测修改的部分；3 ) 如何定义回归测试效果评价问题；4 ) 如何选择，重用和修改现存的测试用例和生成新的测试用例。目前回归测试策略研究已经成为回归测试的研究热点。回归测试选择包括“重测所有”和“选择部分一用例1 。而重测所有的用例虽然可以通过复用原有用例，减少构造测试用例成本。但随着丌发工作的进展，测试用例不断增多，重复原先所有的测试将带来很大的工作量，往往超出了软件的预算和进度。“选择部分 方法就显得尤为重要，选择合适的策略，不但可以减少维护测试用例集的成本，而且可以减少执行测试用例的代价，更快的检测出错误口吲。目前在回归测试研究中有许多这方面的策略和算法。l e u n ga n dw h i t e n 2 1 提出根据用例性质将原始的测试用例分类，然后根据软件修改从这几类测试用例集中选择合适的测试用例来进行回归测试。分类标准如下：可重用的测试用例，可重测的测试用例，可丢弃的测试用例，新增加的与程序结构相关的测试用例，武汉理工大学硕士学位论文新增加的与规格说明相关的测试用例。回归测试选择的研究，主要包括以下几个方面：( 1 ) 基于系统规格信息的回归测试选择。该方法主要针对与软件规格相关的用例的选择问题，通常用于系统测试阶段；( 2 ) 基于代码信息的回归测试选择。该方法主要研究在已知代码的情况下，对与代码相关的测试用例进行选择1 。( 3 ) 测试用例的约简技术n 材，包括传统的非需求驱动和需求驱动。保证用较少的用例实现和原用例集相同的覆盖。( 4 ) 测试用例的优先级研究n 钉 1 8 - 2 1 ，使得重要的用例优先执行。其中，( 2 ) ，( 3 ) ，( 4 ) 是当前回归测试方法研究的热点。本文后面章节着重介绍基于代码信息的回归测试选择，具体对测试用例的优化技术进行比较讨论。针对基于代码信息程序的选择算法研究分为针对面向过程程序和面向对象程序两个方面。面向过程软件以功能模块间的控制流程为重点，可以通过比较文本信息，分析程序数据流，建立控制图模型，通过图的遍历，找出修改部分进行用例选择。而面向对象软件具有类、继承、封装等特性，这些特点决定了测试面向对象软件需要新的策略，使得面向对象测试在测试步骤的划分以及测试策略的选择上有别与面向过程的测试瞳2 1 2 a o 针对两种程序特点，国内外学者都提出了一些相关的策略来提高回归测试的效率。r o t h e r m e l 提出的基于c f g 的用例选择算法】。该方法根据给定的程序代码信息构造相应的c f g 或程序依赖图，然后再比较程序修改前后的c f g 图，找出修改部分来进行用例选择，主要针对的是面向过程的用例选择算法。但这个算法并没有讨论遍历c f g 图时边的控制域问题，这一点后来得到陈茹等人的深入研究，他们借鉴面向对象语言中的继承思想，提出了具体实现方法1 。方菲等人针对面向对象软件晗4 1 ，通过分析对象系统的特性，定义了对象之间的依赖关系，根据依赖关系得到测试对象的方法序列，并应用程序切片技术，找到受到程序修改影响的测试用例，选择这些测试用例加入新的测试用例集中。g a l l a g h e r , k b ，a n dl y l e ，j r 在其著作中提到一种程序切片算法，先用切片算法分解程序，然后根据改变代码和未被改变的代码之间的关系来选择测试用例。王影提出了一种利用“条件切片 技术乜钔，来专门检验对于循环和选择结构中“控制谓词”的修改方法，从而更进步降低回归测试的成本。k a b d u l l a ha n dw h i t e 提出回归测试的防火墙概念1 。针对面向对象的程序扩展类防火墙，以类为测试的基本单元，先标识出修改的类与受修改影响的类，3武汉理工人学硕士学位论文即构造一个类防火墙，然后对类防火墙中的类，根据对象关系图以一定的顺序进行回归测试。黄岩艺等人提出针对面向对象程序建立扩展有限状态自动机模型来分析其数据依赖和控制依赖，确定程序中修改部分的波及影响，再进行测试用例的选择。h a r r o l d 和他的同事提出面向j a v a 程序的回归测试选择算法】。该方法使用j i g ( j a v ai n t e r c l a s sg r a p h ) 来表示j a v a 程序，他的方法对整个系统的类构造j i g图，来分析修改的部分以及所影响的部分。在回归测试中，对于测试用例的选择，优化等方面，很多学者和研究人员做出了大量的研究：朱海燕等人通过对测试用例排序技术的研究，使得具有高优先级的测试用例比低优先级的测试用例在测试过程中更早的执行，根据不同的覆盖准则，得到对应的排序算法，并讨论了测试用例排序算法的有效性汹3 。马雪英等人用遗传算法最小化测试用例啪矧：张玉彬等人的测试用例的设计和复用技术臼，让它们具有统一的输入，输出接口，并且每个测试用例独立性比较强，这样即使以后软件运行环境发生变化，测试用例还能够继续应用在实际测试中；陈伟等人在结合国内外几种算法的策略( 如贪心算法，h g s 算法口剁，g r e 算法汹伽，整数规划方法汹1 ) 的基础上，提出了一种基于测试需求集的最小测试用例集的生成方法呻1 。对于回归测试策略，用例覆盖的全面性和执行时间代价往往有所冲突；更早的确认系统可靠性和使用覆盖更多语句的用例选择有时也不具统一性。选择最小测试策略还是最安全的测试策略，不同的系统，需要采用不同的评估标准。现有的测试用例优化技术有着各自的特点和适用域，都在测试的某个阶段做出了优化，但它们仅仅对针对某一部分做出改进，由于在不同的评估方式下需要采用不同的策略，在新的策略下，往往忽视了以往策略对本次测试的有利部分。本文通过比较分析现有回归测试的选择策略，提出改进策略使得测试过程更具系统性。4武汉理工大学硕士学位论文1 3 本文主要研究工作回归测试选择技术的关键在于如何提高用例选择精度和测试可信度。为了解决这两个关键问题，本文对现有算法研究的基础上，将回归测试选择技术和测试用例排序结合，系统的整合了测试需求的约简，测试用例的生成，测试用例的约简，以及优先级排序这四个方面，新策略能更好适应不同的回归测试效率评估方法。本文着重关注的测试用例集优化的三个方面，讨论测试需求优化和测试用例优先级问题，即鉴别分析测试需求关系和用例优化策略做以下几方面的工作：( 1 )深入研究现有的回归测试选择方法，包括面向过程的回归测试选择方法和面向对象的回归测试选择方法，介绍控制流图的构造及其作用。( 2 )对现有测试用例的优先级技术进行深入研究。( 3 )针对现有回归测试策略的缺点，提出一种新的策略，将需求设计信息，用例优化整合成一个系统，使之能更好适用于不同评价方式。( 4 )实验证明新策略的有效性。1 4 论文组织形式第1 章介绍课题研究背景及国内外回归测试研究现状，并介绍了本文的主要工作。第2 章具体介绍软件测试，回归测试特点，回归测试用例集的热门优化技术并给出了评价方法。第3 章具体研究基于面向过程和面向对象的图形遍历技术在回归测试中的应用。第4 章讨论y 澳v , i 试需求模型和测试用例排序的一般方法，为下章提出基于图形和需求的回归测试模型做准备。第5 章提出了基于图形和测试需求的用例选择排序方法，并进行相关实验和算法分析。第6 章总结与进一步工作的展望。武汉理工大学硕士学位论文第2 章软件测试和回归测试策略随着信息技术的发展，软件应用越来越广阔，在软件开发过程中不可避免会出现各种故障，这些故障引起的软件危机问题逐渐受到人们的重视。为了解决软件危机，软件工程被建立起来，软件工程的目的就是通过提供规范化的分析设计方法及工具软件，来避免或减少软件错误的发生，为最终根除软件危机提供强有力的技术保障。因此，软件工程强调软件开发的工程性，把软件的设计，开发，测试，维护和管理工作当作一项系统工程。软件测试是这项工程的重要组成部分。在软件开发阶段和维护阶段中，一旦发现软件系统中存在错误，则应立即排除它们。由于程序中各元素( 如变量，函数，过程或类等) 往往是相关的，为了保证改正错误后没有引入新的错误，必须对其进行的测试就被称之为回归测试。回归测试作为软件测试的一种重要方法，贯穿整个软件周期，能使用软件测试的一般技术但又具有其单独特点。2 1 软件测试2 1 1 软件测试目的软件测试是发现并指出软件系统缺陷的过程。软件缺陷在开发和维护的任何阶段都有可能发生，并由此产生一系列错误影响整个软件系统。软件测试的目的决定了如何去组织测试。1 9 8 3 年i e e e 对软件测试做出定义：使用人工或自动手段来运行或测定某个系统的过程，其目的在于检验它是否满足规定的需求或弄清预期结果与实际结果之间的差距。由该定义可知，软件测试是检验实际测试结果是否满足需求要求，因此，在软件测试的过程中，必须一切以需求规格说明书为标准。软件测试并不是为了发现错误而执行程序的过程，但可以通过针对软件较复杂的部分或以前出错较多的位置进行测试，来尽可能多地找出错误，提高软件质量。也就是说，软件测试的目的虽不是为了证明程序有错，但可以通过测试用例来检测有可能发生错误的地方，以此判断软件是否符合需求。一个好的测试用例是在于它能发现至今未发现的错误。6武汉理工大学硕十学位论文2 1 2 软件测试方法软件测试的方法和技术多种多样。对于软件测试技术，可以从不同的角度进行分类。从是否需要执行被测软件的角度，可分为静态测试和动态测试。静态测试是对被测程序进行特性分析的一类方法的总称，其主要特点是不实际运行待测程序，而采用其他途径达到检测软件的目的。主要是文档，界面方面的检测。动态测试则需实际运行待测程序，输入相应的测试用例，判定执行结果是否与预期相符，从而检验程序的正确性，可靠性和有效性。动态测试的两种主要方法是黑盒测试和白盒测试：( 1 ) 黑盒测试也称功能测试或资料驱动测试，它是在已知产品所应具有的功能的情况下，通过测试来检测每个功能是否都能正常使用；在测试时，把程序看作一个不能打开的黑盒子，在完全不考虑程序内部结构和内部特性的情况下，对程序的接口进行测试，它只检查程序功能是否完全符合需求规格说明书，并能正常使用；程序是否能正确输入，产生正确的输出信息，并且保持外部信息的完整性。其目的在于发现函数使用错误，接口或数据结构方面的错误，检测是否有性能方面的问题。黑盒测试方法主要有等价类分析法，边界值分析，因果图法和错误推测等，主要用于软件确认测试。( 2 ) 白盒测试也称结构测试或逻辑驱动测试，是已知软件内部结构进行的测试，白盒测试主要针对检测产品内部动作是否按照规格说明书的规定正常运行。该测试方法按照程序内部的结构测试程序，检验程序中的每条通路是否都能按预定要求正常工作。白盒测试的主要方法有逻辑驱动，基路测试等，主要用于软件验证。因此，白盒测试必须全面了解程序内部逻辑结构，对所有逻辑路径进行测试，确保所有内部数据结构的正确性。2 1 3 软件测试策略实际操作中的软件测试策略主要集中在动态测试中，需要实际运行待测程序，采取的方法也是多种多样，除了穷举测试外，任何一种策略都无法保证待测程序中不存在遗留错误，穷举法是指让待测程序在一切可能的操作情况下，包括j 下确的操作和非法操作的情况下全部执行一遍，显然其工作量巨大。因此，为了最大程度的减少遗留错误，同时最大程度的减少测试执行代价，需要采用合适的测试策略达到这两者的平衡。7武汉理工大学硕士学位论文一般来说，一个好的测试策略和测试方法，应该遵循以下原则：要根据程序的重要性和一旦发生故障将造成的损失来确定它的测试等级和测试重点；认真研究测试策略，以便能使用尽可能少的测试用例，发现尽可能多的程序错误，因为一个完整的软件测试后，如果程序中遗留的程序错误过多并且很严重，则表明本次测试是失败的：测试不足，又有可能使隐藏错误给用户造成危险。不必要的过度测试则会浪费许多宝贵的资源。2 2 回归测试2 2 1 回归测试分类软件测试过程中如果是需求变化，或者软件维护的类型是适应性维护或完善性维护，则需要改动程序规格说明，以记录这些功能上的变化。此种回归测试需要设计新的测试用例，该回归测试被称为渐增性回归测试。软件测试过程中如果是设计或编码阶段的错误，或者软件维护的类型是改错性维护，不需要改动程序规格说明，该回归测试被称为改错性回归测试。改错性回归测试可以重用那些只与输入输出相关，而与程序的设计和实现无关的测试用例，因为这部分的测试用例仍然有效，而当软件的控制流和数据流结构发生了改变，如程序算法改进，代码重构等性能的优化，此时，针对这部分功能设计的测试用例失效，不可再被重用，这两种回归测试的主要区别如表2 1 所示。表2 1 渐增性回归测试和改错性回归测试主要区别】渐增性回归测试改错性回归测试l 程序规格说明改变l 程序规格说明不变2 程序改变代码较多2 程序改变代码较少3 可重用的测试用例较少3 可重用的测试用例较少8武汉理工大学硕士学位论文2 2 2 回归测试策略根据是否改动规格说明，回归测试主要有两类策略n ：1 改动较大时的“重测所有 回归测试策略；2 改动较小时的“选择性 回归测试策略。前者是重用开发过程中形成的完整测试用例库( 即“基线测试用例集) 进行的测试，但随着程序规模的扩大，修改次数的增加，维护庞大的测试用例集，会花费更多的时间。因此，为节省时间，需采取另一种策略，选取基线测试用例集的一个子集来覆盖程序中被修改和受影响的部分，该这个子集被称为“再测试用例集一。当测试组选择缩减的回归测试时，有可能丢弃了可以揭示回归错误的测试用例，消除了发现回归错误的机会。然而，如果采用了代码依赖性分析等安全的缩减技术，就可以决定哪些测试用例可以被丢弃而使得回归测试达到相同的目的。这样会使回归测试既有高效率又强有效。选取回归测试策略应该兼顾效率和有效性两个方面，除了“重测所有一策略外，目前主要的“选择性 回归测试有以下三种：1 安全选择策略，即选择覆盖所有程序中受影响部分的测试用例：如基于代码修改的测试用例选择。2 最小化选择策略，即选择已有的测试用例的最小子集，保证程序中受影响部分至少被覆盖一次；3 随机选择策略，由测试人员从原有测试用例集t 中随机选择测试用例，或根据个人知识，经验来进行选择：有基于风险用例的回归测试，该方法把所有用例分为几个风险等级，设定经程序部分相对稳定的用例风险等级较低，不稳定的用例风险等级较高。首先运行最重要的，最关键的和可疑的测试用例，而跳过那些非关键的，优先级别低的或者高稳定的测试用例。因为这些用例即使可能测试出缺陷，这些缺陷的严重性也不是很高。现存通用的评价不同“选择性 回归测试策略，有概括性，精确性，通用性三种不同指标。根据这三种标准，比较以上几种策略，“重测所有 策略概括性最强，适用于程序大规模改动，但执行代价大：随机选择策略依赖于测试人员本身的经验，随意性较大，精度不高，而且因为这个选择是基于用例比较而不是代码比较，可以不用代码分析器和其他技术，只是对以往修改经验进行分析，所以这类情形下测试的时间和成本受程序修改影响不大。最小化选择策略选择的用例集最小，执行代价小，但其错误检测能力较差。安全选择策略错误9武汉理：t = 大学硕士学位论文检测能力较强，且用于回归测试的用例集也不会很大，所以适合于一般情况下的回归测试。但如果程序规模过大，对程序进行分析的成本也很可观。2 3 软件测试与回归测试比较软件测试过程是首先编写测试用例，配置测试环境，然后执行测试用例，对测试的结果进行评价，如果符合需求规格说明书，就完成软件测试；如果有错误，就要对错误进行修改，修改后为了检验修改是否达到目标，要进行回归测试。在软件的维护阶段，也会出现一些修改错误或添加新的功能，也同样需要进行回归测试。图2 1 给出了软件测试的一般过程。为了讨论方便，需做着相关符号说明，该说明将在全文使用。令p 表示某个程序，f ，表示p 修改后的程序，厂为针对尸测试的测试用例集。则回归测试过程可以描述如下：( 1 ) 选择r 7 t 其中丁是程序p ，运行时用来检测的用例集；( 2 ) 利用r 7 测试程序p ，以确认程序p 在r 的正确性；( 3 ) 如果必要，产生r 。，其中r ”为p 7 测试新增部分的用例；( 4 ) 利用r 。测试程序p ，以确认p 7 在丁”上的正确性；( 5 ) 根据瓦丁”来产生新的测试用例集r 。从上述过程可知，回归测试和开发过程中的测试明显的不同在于测试用例的来源，两者发生的频率和时间分配。回归测试的大部分测试用例是从开发过程中的测试用例库中取得，只需针对新增加部分编写新的测试用例或删除减少部分的冗余用例；回归测试在每一次修改后就要进行，而开发过程中的测试是在软件每一阶段完成后进行的一次性测试，不需要重复进行。测试时间一般在软件产品开发之前就计划好，而且这个时间可能占整个产品开发时间的一半以上，但回归测试时间通常是无法预算的，一旦发生修改就必须进行回归测试，以此确认修改是否达到目的而没有产生新的问题。因此，一次完整的回归测试时间比软件开发测试时间少，但软件产品的所有回归测试时间要比软件开发测试的时间长的多。1 0武汉理工大学硕士学位论文图2 1 软件测试一般过程图2 4 回归测试用例集约简概念为了最大程度地满足客户需求和应用的要求，软件在其生命周期中会被频繁地修改和不断推出新的版本，修改后的或者新版本的软件会添加一些新的功能或者在软件功能上产生某些变化。随着软件的修改变化，测试用例库中的一些测试用例可能会失去针对性和有效性，而另一些测试用例可能会变得过时，还有一些测试用例完全不能运行。因此，维护测试用例库显得尤为重要。另一方面，针对被修改的或新增添的软件功能，必须开发新的测试用例集。随着软件规模的扩大，测试用例库的维护工作负担越来越重，选择高效的用例进行回武汉理工人学硕十学位论文归测试成为必然。1 9 9 3 年，m j h a r r o l d 等人首次提出了测试用例集约简的概念啪3 。测试用例约简技术，就是在原始用例集中，找到一个较小的测试用例子集，并能够提供与原始测试用例集一样的测试覆盖率。用r 表示测试需求集( r e r ) ，丁表示测试用例集( t e t ) ，假定这两个集合都是非空有限集。分别用r e q ( 幻和r e q ( r ) 表示所有被测试用例t 和测试用例集丁满足的测试需求所组成的集合用t e s t ( 力和t e s t ( r ) ( r7 是r 的非空子集) 分别表示所有满足测试需求，和尺的测试用例组成的集合腔1 。则有如下几种测试用例分类的定义：过时测试用例若r e q ( 幻正r ，则称t 是过时的测试用例。必不可少的测试用例对于测试用例t e t ，若r e q ( t l t ) ) 一r ，则称t 是必不可少的测试用例。用e s s ( s ) 表示s 中所有必不可少的测试用例组成的集合。冗余的测试用例若r e q ( t l t ) ) = r ，则称t 是冗余的测试用例。对于测试用例蛭t ，如果存在测试用例t 得到r e q ( 幻r e q ( t ) ，则称测试用例t 是卜l 冗余的测试用例。约简测试用例集若互t ，且r e q ( 五) = r ，则称互为约简测试用例集。最小测试用例集及最优测试用例集若互的任意真子集正都不能实现对测试需求集r 的充分测试，即r e q ( t 。) = r ，v 五ct 。，r e q ( 五) 一r ，则称五是最小代表集。若对于任意代表集疋有i 五isf 瓦l ，则称五是最优测试用例集。显然，最小代表集合和最优代表集一定存在。最小代表集不一定是最优的，但最优代表集一定是最小代表集最优代表集可以不唯一，但其基数一定相同。武汉理t 大学硕士学位论文2 5 回归测试用例集主要约简算法测试用例集约简问题是n p 完全问题，可以采用贪心算法，一些启发式算法，整数规划，遗传算法等方法。此外还有最近提出的需求驱动方法。本文将主要介绍启发式方法，基于依赖分析的方法和需求驱动方法。2 5 1 启发式方法现有的启发式算法主要包括：贪心算法，h g s 算法，g e & g r e 算法和g a 算法笔寸ov c h v a t a l 最早提出用贪心算法来求解测试用例集约简问题。其算法执行过程如下：逐次从t 中选择一个测试用例，使之能尽可能最多的满足r 中的测试需求，然后从r 中删除这些已被满足的测试需求，循环几次上述操作，直到所有测试需求都能被满足( 即r 为空集) 。该算法的时间复杂度是o 伽以m i n ( m ，以) ) w t i 。t y c h e n 等人提出了必不可少和1 - 1 冗余的分治策略州。该方法是将测试用例集分成k 个相互独立的子集，分别求解这k 个子问题的最优解，将解集合组合后获得原问题的最优解。其局限性在于要求测试用例集满足分治策略所要求的特性，并不适用于所有测试用例集。基于贪心算法和必不可少策略，g e算法做出了改进，先找到必不可少的测试用例，再使用贪心算法，其最坏时间复杂度仍为o ( m 以m i n ( m ，以) ) 。h a r r o l d 等人提出的一种根据测试用例的重要性进行选择的启发式算法( 即h g s 算法) 。该算法首先将测试需求，吃，_ 分成集合墨，恐，兄( d s n ) ，其中，r ( i = 1 ，2 ，d ) 表示所有正好可以被t 中i 条测试用例满足的测试需求。该算法认为，当i j 时，满足咫中测试需求的测试用例比满足尺，中测试需求的测试用例“重要”。特殊的，满足r 中测试需求的测试用例是必不可少的，一定要加入到约简集中。该算法的选择过程如下：( 1 ) 挑选出满足冠中测试需求的测试用例，并从r 中去掉相应满足的测试需求。( 2 ) 再考虑r 中未被满足的测试需求，使用贪心算法，选择测试用例尽可能多1 3武汉理工大学硕士学位论文地满足剩下的测试需求，直到心中的测试需求全部被满足( 3 ) 依次处理r ，r 4 ，毛该算法的最坏时间复杂度为o ( 肌佃+ n ) d ) d 7 1 。c h e n 和l a u 基于以上算法，加入了剔除卜1 冗余测试用例的策略，提出g r e 算法。该算法交替使用“必不可少 策略和“卜1 冗余 策略，直到两种策略都无法再应用，再使用贪心算法选择测试用例满足剩下的测试需求。该方法首先循环的执行：从t 中挑选出必不可少的测试用例，从r 中剔除对应满足的测试需求：然后再从t 中剔除卜1 冗余测试用例，如果此时还有测试需求未被满足，则利用贪心算法从t 中选择测试用例满足剩下的测试需求。该算法的最坏时间复杂度为o ( m i n ( m ，厅) 伽+ j b l 2 ) ) ，其中乒表示一个测试用例最多能满足的测试需求数量。作为一种自适应的智能搜索算法，遗传算法( 简称g a 算法) 被应用于求解许多n p - - c 问题，但由于遗传算法本身存在局限性，如过早收敛，优化效率低等问题，因此它只能在短时间内找到接近全局最优解的近似解，而不能保证收敛到全局最优解。这个局限性可以通过混合其他算法如粒子群算法得到改进。采用上述启发式方法可以获得测试用例集约简问题的近似最优解，但均无法保证是否最优。相关的实验研究也显示，这些方法各有优劣，没有一种方法总能获得比其他方法更好的约简结果。2 5 2 基于依赖分析除了上述测试用例约简算法外，许多研究人员还针对具体待测系统的特性，提出基于依赖分析的方法。目前在功能性测试中存在o b j e c t z 规则，u m l 状态图等多种程序行为描述方式，但最为广泛使用的还是扩展有限状态自动机模型( e x t e n d e df i n i t es t a t em a c h i n e ，e f s m ) 。该方法首先分析e f s m 系统模型中的控n 数据依赖关系，随后构造静态动态依赖图，以提取静态动态交互模式。若两个测试用例对于给定待测需求存在相同的交互模型，则认为这两个测试用例等价，以此定义等价测试用例集合。最后保留等价测试用例集合中的任意一条，删除其他冗余的测1 4武汉理工大学硕士学位论文试用例。该方法和程序切片技术大量用于确定程序修改点和出错点中，进而实现回归测试集的约简。对于大规模结构复杂的程序，其分析代价相对较高。2 5 3 需求驱动方法现有的大多数测试用例集约简方法是直接约简测试用例集，没有对系统做进一步的需求间关系的分析。而需求驱动的测试用例约简方法则首先充分挖掘并使用测试需求的相关信息，一定程度上约简测试需求集；随后再采用传统的测试用例集约简方法。该方法可以通过需求的简化使得用例集规模的缩减。s t a l l a m 等提出基于概念格分析的约简算法。该算法构造用例一需求的关系矩阵，反复删除被包含的行( 即测试用例) 和列( 即测试需求) ，直至矩阵无法再约简。随后选择必不可少的测试用例，使用贪心算法选择测试用例，并再次计算新产生的包含关系。基于概念格的测试用例集约简方法已广泛使用于w e b应用中。然而，概念格的构造与运算开销较大，该方法并不普遍有效，其约简测试集的规模通常要大于h g s 算法的约简结果。研究表明，与已有的启发式算法相比较，需求驱动的测试用例集约简方法通常可以有效减少待处理的测试需求数量，并降低测试需求间关系的复杂度，从而在多项式时间内获得规模相近甚至规模更小的测试用例集，最终实现测试用例集约简的目标。2 6 测试用例集优先技术为提高测试用例集的错误检测能力，与测试用例集约简问题强相关的一个研究课题是测试用例优先级技术。该技术不减少测试用例集的规模，目标在于提高现有测试用例集的性能。测试用例优先级技术充分考虑了不同因素对测试用例重要程度的影响，赋予每个测试用例一个优先级，然后按照优先级的高低顺序依次选择并执行测试用例，使得具有高优先级的测试用例被尽早执行。测试用例优先级技术问题有多个方面值得进一步讨论。首先，目前存在多种优先级排列的目标，主要包括以下几种：力求提高测试集合对缺陷的发现率，即增加运行此测试用例集合时发现软件缺陷的可能性：力求提高待测系统中可能被覆盖到的代码的覆盖速度，使得某个代码覆武汉理工人学硕士学位论文盖的标准能够尽早满足；力求以尽可能快的速度增加对待测系统的可靠性的信心，如尽早的检测关键功能，确保系统能满足基本功能使用；力求提高待测系统的高危险性错误的检测速度，在测试过程中尽可能快的发现此类错误：力求在回归测试中增加测试特定类型代码错误的可能性。需要讨论的第二点是，测试用例优先级技术不仅能用于回归测试中，也可以用于软件的开发测试中。这两者的区别在于开发测试只有以往开发类似系统或代码的经验可以借鉴，而很少有针对待测代码的特定信息。但在回归测试中，可以使用之前对于代码运行所得到的信息，进一步对测试用例的优先级进行调整。第三，需要区别对待两类测试用例的优先技术：一般的测试用例优先级和特定版本的测试用例优先级。前者针对一般要求设定优先级顺序，在软件版本进化发布新版本时，也可以重用该优先级。后者设定的优先级顺序能在特定版本中达到最好的目标，对其他版本不一定能达到同样的最优效率。其优点是能在该版本中达到最优的测试效果，但不利于后续版本的测试。针对上述目标，研究人员进行了大量的研究工作。w o n g 等人最先提出在回归测试选择技术基础上对测试用例集最小化，或者优先级处理，通过判定累计覆盖率等问题对测试用例进行排序h 0 1 ，但是这种方法考虑的测试历史因素过于单一，为此e l b a u m 和r o t h e r m e l 等人基于测试用例执行信息，将测试历史及动态反馈信息用于计算测试用例选择概率h 妇h 朝，从语句覆盖，分支覆盖和检错能力等方面提出了改进算法。k i m 等人在已有回归测试研究的基础上指出应将回归测试视为一系列有序的行为序列，提出综合考虑各种测试历史的优先级技术h 引。本文将在第四章，对测试用例优先级问题做进一步分析，并提出新的排序策略。针对优先级技术的评估方法可以考虑以下的几个准则：( 1 ) 错误检测率，即尽可能早地在测试过程中暴露错误：( 2 ) 代码覆盖率，即尽可能早地使用例覆盖全部代码：( 3 ) 系统可靠性