（计算机应用技术专业论文）回归测试选择技术研究.pdf

硕士学位论文 摘要 回归测试是软件测试中的一个十分重要且成本昂贵的过程。所以，针对如何 减少回归测试成本，提高回归测试效率的研究将具有十分重要的意义。回归测试 选择技术已经成为国际上研究的热点。 本文围绕回归测试选择这个主题，首先介绍了回归测试选择技术的研究进展。 重点讨论了面向过程和面向j a v a 程序的回归测试选择算法。针对面向j a v a 程序 的回归测试选择算法没有考虑连续方法调用从而使用例选择精度降低的问题，本 文提出了一种新的方法“l i n k ”法，可以有效的解决该问题，并能提高用例选 择精度，从而避免对程序修改正确性做出错误估计。 针对无法完成所有用例的测试时不能保证测试可信度的问题，本文采用了用 例排序算法。本文首先描述了用例排序的基本概念以及常用算法，并对这些算法 的进行了初步讨论。然后本文在原有的边覆盖排序算法的基础上提出了基于j i g 边覆盖算法。并结合用例选择算法和基于j i g 边覆盖算法的优点，提出了基于j i g 的用例选择排序算法。本算法既可以获得较低的用例选择率，又能使用例序列具 有较高的错误检测能力。 本文对影响回归测试选择效率的因素进行了详细分析，并提出了一个基于测 试状态的回归测试选择策略的选择方法。使用该方法，可以在已知测试状态的情 况下，选择一个较好的回归测试选择策略，从而获得较好的效费比。 本文最后实现了本文提出的基于j i g 的用例选择排序算法的回归测试系统原 型。该系统通过对j a v a 源程序进行解析，可以生成j i g ，并对用例进行选择排序， 按用例优先级进行自动测试。本文在该实验平台上对算法进行了相关实验分析。 关键词：回归测试；回归测试选择：用例排序； 回归测试选择技术研究 a b s t r a c t r e g r e s s i o nt e s ti s av e r yi m p o r t a n tb u te x p e n s i v ep r o c e s sd u r i n gs o f t w a r et e s t t h e r e f o r er e s e a r c ho nh o wt or e d u c et h ec o s to fr e g r e s s i o nt e s ti se s p e c i a l l yi m p o r t a n t ， a n d r e g r e s s i o nt e s ts e l e c t i o nt e c h n i q u e h a sa l l u r e dm a n ye y e so fr e s e a r c h e r s t h i s p a p e r f i r s t b r i e f l y i n t r o d u c e s r e g r e s s i o n t e s t s e l e c t i o n ( r t s ) t h e n w e d i s c u s st w om e t h o d so fr t s ，o n em e t h o du s e df o rr t s o f p r o c e d u r e o r i e n t e ds o f t w a r e ， a n dt h eo t h e rf o rr t so f o b j e c t o r i e n t e ds o f t w a r e r e g a r d i n g t h e p r o b l e m t h a t a l g o r i t h m sa v a i l a b l ec a n n o th a n d l es e q u e n t i a l - c a l l ，t h i sp a p e rp r e s e n t s an e wm e t h o d c a l l e d l i n k ，w h i c hc a nt h u si m p r o v ep r e c i s e n e s so fr t s m o r e o v e r ，t oi m p r o v ec o n f i d e n c eo fs o f t w a r em o d i f i c a t i o ni nr e g r e s s i o n t e s to n c o n d i t i o nt h a tn o ta l lt e s t sc a nb ee x e c u t e d ，w ei n t r o d u c et e s t c a s e s p r i o r i t i z a t i o n a f t e rd i s c u s s i n gs e v e r a la l g o r i t h m so ft e s tc a s e sp r i o r i t i z a t i o n ，t h i sp a p e rp r e s e n t sa n e w a l g o r i t h m ，w h i c hi sc a l l e dj i g - b a s e db r a c h c o v e r a g ep r i o r i t i z a t i o na l g o r i t h m b y c o m b i n i n g t h er t s t e c h n i q u e m e t i o n e da b o v ea n d j i g - b a s e d b r a c h - c o v e r a g e p r i o r i t i z a t i o na l g o r i t h m ，t h i sp a p e rp r e s e n t san e w m e t h o d ，w h i c hi sc a l l e dj i g - b a s e d r e g r e s s i o nt e s ts e l e c t i o nw i t hp r i o r i t i z a t i o n t h i sp a p e ra l s od i s c u s s e sh o ws u c hf a c t o r sa st e s tf r e q u e n c ya n dd e m a n do ff a u l t d e t e c t i o na f t e c te f t e c t i v e n e s so fr t s f i n a l l y ，w ei m p l e m e n tar e g r e s s i o n t e s ts e l e c t i o ns y s t e mb a s e do nj i g b a s e d r e g r e s s i o n t e s ts e l e c t i o nw i t hp r i o r i t i z a t i o n k e y w o r d s ：r e r e s s i o nt e s t ；r 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 e sp r i o r i t i z a t i o n ； - i i 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何 其他个人或集体己经发表或撰写的成果作品。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法 律后果由本人承担。 作者签名：多，2 吃胁 日期：由哮年月0 百 日期：咖哮年月2 i 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编 本学位论文。 本学位论文属于 1 、保密，在年解密后适用本授权书。 2 、不保密 。 ( 请在以上相应方框内打“ ”) 作者签名： 导师签名： 南教日期：乡v 一烽争月2 - _ u f t 日期：洳昨月2 面 硕士学位论文 1 1 1 研究背景 第1 章绪论 软件测试在软件的整个开发过程中占有非常重要的地位，是保证软件质量、 提高软件可靠性的关键。根据b o e h m 的统计，目前软件测试在软件开发的总成 本中，其开销占到了3 0 一5 0 m 。而随着软件开发规模的逐渐扩大，软件的出错 率也越来越高。具体来说，软件出错的原因主要有：应用需求不够清晰、软件复 杂性、超大型关系数据库以及庞大的系统规模等，这些都使得软件及系统的复杂 性呈指数增长。总之，随着软件工程技术的发展，软件设计规模的增大，软件测 试在软件开发过程中的作用也会越来越重要。 回归测试是软件测试中一个很重要的环节。其目的是保证程序在修改后不会 引入新的错误1 4 - 1 2 1 。而随着软件规模的日益庞大，回归测试的成本也相应增大，甚 至达到了整个测试成本的一半以上1 1 3 1 。所以回归测试已经成为整个软件测试的关 键，是软件质量的重要保证。 回归测试的研究包括测试环境自动化1 1 4 m l 、捕获一回放 i s i 和构建程序小版本i ”】 以及回归测试选择m _ 2 2 1 等方面。在目前，回归测试选择已经成为回归测试的研究 热点l l l l 。 1 1 2 研究进展 回归测试选择( r e g r e s s i o n t e s ts e l e c t i o n ) 是复用已有用例集来进行回归测试 的方法。该方法相对于重测所有测试用例，具有如下优点1 1 8 - 2 2 1 ： r 1 ) 复用原有的用例，从而减少构造测试用例的成本； ( 2 ) 不必对所有用例进行测试，减少测试时执行测试用例的成本。 回归测试选择的研究，主要包括以下几个方面 1 1 1 ：( 1 ) 基于系统规格信息的 回归测试选择( s p e c i f i c a t i o n b a s e d ) 。此领域的研究主要针对软件规格相关的用 例进行选择，通常用于系统测试阶段；( 2 ) 基于代码信息的回归测试选择 ( c o d e b a s e d ) 。该方法主要研究在已知代码的情况下，对代码相关的测试用例进 行选择。而基于代码信息的回归测试选择研究又是目前回归测试选择研究的主流。 回归测试选择技术研究 本文后面章节提到的回归测试选择如未特别说明均指基于代码信息的回归测试选 择。针对回归测试选择算法的研究经历了面向过程程序和面向对象程序的回归测 试选择等阶段。 面向过程程序的回归测试选择算法有：1 ) 基于文本信息的方法。该方法即对 程序修改前后的版本进行简单的文本比较，找到所修改的部分，然后根据修改的 部分程序来选择测试用例。2 ) 基于程序语句的用例选择算法。v o k o l o s 和f r a n k p z 0 1 提出了基于文本信息的测试选择算法，该算法为每个语句块和每个测试用例之间 建立一个映射，然后比较程序修改前后的版本，找出程序中被修改的语句。可以 把v o k o l o s f r a n k l 算法看成是选择d a n g e r o u s 块的算法，该算法使用u n i x 下自带 的d i f f 程序来进行比较。由于该算法是基于程序语句的，而不是基于控制流图 的，所以其精度较差。3 ) b a l l l 2 ，1 提出了e d g e o p t i m a l 的用例选择算法，该算法具 有较高的用例选择精度。4 ) 基于c o d ee n t i t y 的用例选择算法。c h e n 、r o s e n b l u m 和v o l 2 提出的测试选择算法是基于代码e n t i t y ，通过找到修改的e n t i t y ，然后选择 与这些e n t i t y 相关的用例进行测试。该算法比基于程序语句和c f g 的算法粒度要 粗，因而其用例选择精度较差。6 ) d a t af l o w 算法一t “。该算法通过对程序进行 数据流分析，找到被修改的r i s e d e f i n e 对，然后选择经过该n s e d e f i n e 对的用例进 行测试。但其用例选择精度不是很高。7 ) 基于图遍历的算法。包括r o t h e r m e l 和 h a r r o l d l 4 川提出的基于c f g 的用例选择算法。该方法根据给定的程序来构造相应 的c f g 或p d g ，然后再比较程序修改前后的图，找出修改部分来进行用例选择。 由于面向对象技术的发展针对面向对象程序的回归测试选择的研究也开展 了起来，r o t h e r m e l 、h a r r o l d 。d e d h i a 提出了面向c + + 程序的回归测试选择算法i ”l ， w h i t e 和a b d u l l a h 提出了f i r e w a l l 算法f 2 2 】。r o t h e r m e l ，h a r r o l d l q 提出了面向j a v a 程 序的回归测试选择算法。该方法使用j i g ( j a v ai n t e n a lg r a p h ) 来表示j a v a 程序。 比较上述几种算法，面向j a v a 程序的回归测试选择算法具有较高的用例选择精 度，同时可以处理j a v a 程序的各种特性。本文的工作正是基于文献【6 】提出的算法。 那么，如何评价一个回归测试选择算法的效率呢? 目前主要的评价体系采用 文献f 1 1 】提出的指标：1 ) 概括性；2 ) 精确性；3 ) 通用性。指标1 和2 分别指 算法选择所有能够暴露错误的用例和避免选择不能暴露错误的测试用例的能力， 统称为用例选择精度。 按以上评价体系，e d g e o p t i m a l 算法、r o t h e r m e l h a r r o l d 基于c f g 的用倒选 择算法在应用到面向过程程序的回归测试用例选择时，具有较好的精度； r o t h e r m e l h a r r o l d 面向对象程序的用例选择算法具有较好的精度。 硕士学位论文 1 1 3 测试用例排序 回归测试选择技术可以通过减少测试用例集中的用例数量来达到提高测试效 率的目的。但是，很多回归测试用例选择策略都会导致有效用例流失，如最小化 选择技术，缺点是大量的有效用例没有被选择，从而使测试效率降低【6 ，8 】。而重 测所有和安全选择策略，虽然可以保证有错误探测能力的用例全部被选择，但是 有时由于种种原因( 如时问、成本或者测试目的不同) ，使得测试人员没有条件执 行用例集中的所有用例。测试用例优先排序技术( t e s tc a s ep r i o r i t i z a t i o n ) 允许 测试人员根据某种准则对用例集中的测试用例进行排序，克服了上述几个问题， 从而使得优先级较高的用例先被测试，提高了测试效率 2 7 m 1 。 测试用例优先排序问题的几个准则：1 ) 错误检测率，即尽可能早的在测试过 程中暴露错误；2 ) 覆盖率，即使用例覆盖尽可能多的程序语句、程序流图的边和 分支等；3 ) 系统可靠性，尽可能早的确认系统可靠性；4 ) 高风险错误检测率， 即尽可能早的发现可能导致较高风险的错误；5 ) 相关代码错误检测率，即尽可能 发现与特定代码相关的错误。本文采用准则1 来进行用例排序。 目前使用最著名的用例排序算法是f e p 算法12 7 l 。该算法使用m u t a t i o n 分析， 计算出每个用例t 在语句s 上的互斥分值m ( s ，t ) ，再计算出f e p 值f e p ( t ；) ，进而 按f e p ( t ，) 值来对用例进行排序。a f e p 是在f e p 算法基础上改进而来，通过在选 择用例t ；后，降低其它用例中t ；执行过的语句的互斥分值，表明对其它语句的信 任度提高。 但是以上算法需要为程序中的每个用例构造大量的互斥版本( m u t y v e r s i o n ) ， 所以进行f e p 分值分析的成本较大。而相比之下，t o t a l 语句覆盖、t o t a l 边覆盖 算法仅需对用例执行时的语句或边覆盖信息进行分析，然后根据覆盖率对用例进 行排序，成本较小。本文的工作正是基于t o t a l 边覆盖算法的这个特点进行的改 进的。 用例排序算法的错误检测率采用a p f d ( a d d i t i o n a lp e r c e n t a g e f a u l t d e t e c t i o n ) 分值来评价。文献 2 9 1 表明，t o t a l 语句覆盖和t o t a l 边覆盖算法具有比 较好的a p f d 分值。 回归测试选择技术的关键在于如何提高用例选择精度和测试可信度。为了解 决这两个关键问题，本文在对现有算法研究的基础上，将回归测试选择技术和测 试用例排序结合，并对r o t h e r m e l ，h a r r o l d t 6 j 提出的算法和t o t a l 边覆盖算法进行改 3 回归测试选择技术研究 迸，使之适合于j a v a 程序的用例选择和排序。论文所做工作如下： ( 1 ) 深入研究分析r o t h e r m e l ，h a r r o l d 6 l 提出的面向j a v a 程序的测试用例选择 算法的不足：1 ) 没有考虑到连续方法调用的情况，因而在使用连续方法调用的场 合，出现用例选择精度不够，从而导致对程序修改的正确性做出错误估计( 参见 4 3 ) ；2 ) 由于在无法完成所选择测试用例不能充分保证测试可信度，本文通过对 r o t h e r m e l h a r r o l d 算法中j i g 进行扩展，提出“l i n k ”方法，可以有效提高用例 选择精度；并且通过引入用例排序算法，使测试可信度提高。 ( 2 ) 深入研究了现有的用例选择算法。重点研究边覆盖用例选择算法，由于 现有边覆盖算法基于c f g ，而面向j a v a 程序的测试选择算法是基于j i g 的，所以 本文将其扩展到j i g 中，提出基于j i g 的边覆盖排序算法。并且结合用例选择和 用例排序的优点，提出了基于基于j i g 的用例选择排序算法。 ( 3 ) 对不同的回归测试选择策略在不同的测试频次下的效率进行了研究。并 针对不同的测试状态，提出一个用例选择策略的经验选择方法。 f 4 1 在本文改进的回归测试选择算法的基础上，实现了一个面向j a v a 程序的 回归测试选择系统的原型系统。该系统通过对j a v a 源程序进行解析，可以生成 j i g ，并对用例进行选择排序，按用例优先级进行自动测试。 本文共分七章，主要内容如下： 第二章介绍了软件测试和回归测试的相关理论。第三章介绍了面向过程的回 归测试选择技术研究进展，并重点讨论了几种典型的回归测试选择算法。第四章 研究了面向j a v a 程序的回归测试选择算法，并针对其用例选择精度作了相应改 进。第五章介绍了用例选择技术的基本概念，重点讨论了几种典型的用例排序算 法。并将边覆盖算法扩展到j i g ，使之适应本文改进的回归测试选择算法。本文 在此基础上提出了基于j i g 的回归测试选择排序算法。第六章研究了回归测试选 择策略在不同的测试频次下的性能表现。并针对不同的测试状态，提出一个用例 选择策略的经验选择方法。第七章实现一个基于改进回归测试选择算法的系统原 型，并对改进部分进行了相应测试。最后总结全文，给出了本文结论和今后研究 方向。 2 1 引言 第2 章软件测试与回归测试 信息技术的飞速发展，使软件产品应用到社会的各个领域，软件质量自然成 为人们共同关注的焦点。 在过去的四分之一世纪里，以软件测试为中心的软件质量保障技术在软件生 产实践中得到了迅速发展，软件测试已成为软件生产中必不可少的质量保障手段。 软件生命周期中的任何一个阶段，只要软件发生了变化，就可能给该软件带 来问题。软件的变化可能是源于发现了错误并做了修改，也有可能是因为在集成 或维护阶段加入了新的模块。为了验证修改的正确性及其影响就需要进行回归测 试。 2 2 1 软件测试的目的 软件测试的目的决定了如何去组织测试。文献3 1 认为： ( 1 ) 软件测试是为了发现错误而执行程序的过程：测试是为了证明程序有错， 而不是证明程序无错误。一个好的测试用例是在于它能发现至今未发现的错误； ( 2 ) 一个成功的测试是发现了至今未发现的错误的测试。 这种观点可以提醒人们测试要以查找错误为中心。而不是为了演示软件的正 确功能。但是仅凭字面意思理解这一观点可能会产生误导，认为发现错误是软件 测试的唯一目，查找不出错误的测试就是没有价值的，事实并非如此。 首先，测试并不仅仅是为了要找出错误。通过分析错误产生的原因和错误的 分布特征，可以帮助项目管理者发现当前所采用的软件过程的缺陷，以便改进。 同时，这种分析也能帮助我们设计出有针对性地检测方法，改善测试的有效性。 其次，没有发现错误的测试也是有价值的，完整的测试是评定测试质量的一 种方法。详细而严谨的可靠性增长模型可以证明这一点。例如b e yl i t t l e w o o d 发 现一个经过测试而正常运行了n 小时的系统有继续正常运行n 小时的概率m 。 回归测试选择技术研究 2 2 2 软件测试阶段划分 软件测试可以分为若干个小的阶段，阶段的划分标准有多种，我们按软件开 发的生命周期模型将其分为以下四个阶段l ”1 ： ( 1 ) 单元测试：在这个测试步骤中发现的往往是编码和设计的错误，目的是 为了检查每个模块是否能独立地正确运行。 ( 2 ) 集成测试：在这个阶段把经过模块测试运行正确的模块放在一起形成子 系统后再测试。主要测试模式块间的协调和通信问题，测试该系统是否达到功能 要求i 州。 ( 3 ) 系统测试：在这个阶段把经过测试运行的子系统组装成完整的系统后再 进行测试。在这个过程不仅能发现设计和编码的错误，还验证系统是否能提供 需求说明书中指定的功能，系统的动态特性是否符合预定要求。 ( 4 ) 验收测试：把软件系统作为单一的实体进行测试，测试内容与系统测试 基本类似。但它是在用户积极参与下进行的，主要使用实际数据进行测试，目的 是验证系统是否满足用户的需求。在这个步骤中发现的往往是系统需求说明书中 的错误。 测试的四个阶段完全逆向检测了软件开发的各个阶段。单元测试主要测试程 序代码；集成测试主要对软件设计的检测；系统测试主要测试系统环境中的软件 功能；验收测试主要是对用户需求的一种检测。但是每个测试阶段仍要对其他测 试阶段的内容加以测试，只是测试重点不同而已。 2 2 3 软件测试方法 软件测试的方法多种多样，从是否针对系统内部结构和具体实现算法的角度 来分类，可以为黑盒测试和白盒测试i ”】。 2 ，2 4黑盒测试 黑盒测试也称功能测试或资料驱动测试，它是在已知产品所应具有的功能， 通过测试来检测每个功能是否都能正常使用，在测试时，把程序看作一个不能打 开的黑盒子，在完全不考虑程序内部结构和内部特性的情况下，测试者在程序接 口进行测试，它只检查程序功能是否按照需求规格说明书的规定正常使用，程序 是否能适当地接收输入资料而产生正确的输出信息，并且保持外部信息( 如数据 库或文件) 的完整性m j 。其目的是： ( 1 ) 发现函数的使用错误： 6 硕士学位论文 ( 2 ) 发现接口错误； ( 3 ) 发现数据结构错误和外部数据库访问错误； ( 4 ) 性能问题。 黑盒测试方法主要有等价类划分、边界值分析、因果图和错误推测等，主要 用于软件确认测试。 2 2 5 白盒测试 白盒测试也称结构测试或逻辑驱动测试，它是知道产品内部工作过程的条件 下，通过测试来检测产品内部动作是否按照规格说明书的规定正常进行。白盒测 试按照程序内部的结构测试程序，检验程序中的每条通路是否都有能按预定要求 正确工作m 1 。其主要目的是： f 1 ) 确保所有独立路径至少会被执行一次：。 ( 2 ) 确保条件判断的“真”、“假”分支均须执行一次； ( 3 ) 确保循环在边界处被执行； ( 4 ) 确保所有内部数据结构的正确性。 白盒测试的主要方法有逻辑驱动、基本路径测试等，主要用于软件验证。 2 2 6 软件测试策略 软件测试通常是指实际运行被测程序，输入相应的测试用例，判定执行结果 是否符合要求，从而检验程序的正确性、可靠性和有效性。软件测试可采取的方 法和技术是多种多样的，但通常情况下不论采用什么方法和技术，其测试都是不 彻底的，也是不完全的，因为任何一次完全测试或者叫穷举测试( 即让被测程序 在一切可能的操作情况下，包括正确的操作，也包括错误的操作情况下全部执行 一遍) 的工作量太大，在实践上是行不通的，因此任何实际测试都不能够保证被 测试程序中不存在遗留的错误。 为了最大程度的减少这种遗留的错误，同时也为了最大限度的发现已经存在 的错误，在测试实施之前，软件测试工程师必须确定将要采用的测试策略和测试 方法，并以此为依据制定详细的测试用例。而一个好的测试策略和测试方法必将 给软件测试带来事半功倍的效果，它可以充分利用有限的人力和物力资源，高效 率、高质量地完成测试。 那么，究竟如何才能确定一个好的测试策略和测试方法呢，一般来说，在确 定测试方法时，应该遵循以下原则：第一，要根据程序的重要性和一旦发生故障 将造成的损失来确定它的测试等级和测试重点；第二，要认真研究测试策略，以 回归测试选择技术研究 便能使用尽可能少的测试用例，发现尽可能多的程序错误，因为一次完整的软件 测试过后，如果程序中遗留的错误过多并且很严重，则表明本次测试是失败的， 是不足的，而测试不足意味着让用户承担隐藏错误带来的危险，同时反过来说如 果过度测试则又会浪费许多宝贵的资源。我们需要在这两点上进行权衡，找到一 个最佳平衡点。 以下是m e y e r s 提出的使用各种测试方法的综合策略i ”1 ： f 1 ) 在任何情况下都必须使用边界值分析方法。经验表明用这种方法设计出 测试用例发现程序错误的能力最强。 ( 2 ) 必要时用等价类划分方法补充一些测试用例。 ( 3 ) 用错误推测法再追加一些测试用例。 ( 4 ) 对照程序逻辑，检查已设计出的测试用例的逻辑覆盖程度。如果没有达 到要求的覆盖标准，应当再补充足够的测试用例。 f 5 ) 如果程序的功能说明中含有输入条件的组合情况，则一开始就可选用因 果图法。 2 2 _ 7 软件测试技术的发展方向 目前，软件测试存在以下几个发展方向1 3 7 ： ( 1 ) 验证技术。验证的目的在于证明在软件生命周期各个阶段，以及阶段间 的逻辑协调性和正确性。验证技术目前仅适用于特殊用途的小程序。静态测试正 逐步地从代码的静态测试往高层开发产品的静态测试发展。 f 2 ) 测试用例选择。用于从已有的用例集中选取部分用例来进行测试。本文 将对测试用例选择技术作深入研究。 ( 3 ) 测试技术的自动化。这是一个新的发展方向。自动测试也是一门技术， 但与测试技术存在着较大区别。 在软件生命周期中的任何一个阶段，只要软件发生了变化，就可能给该软件 带来问题。为了验证修改的正确性及其影响就需要进行回归测试i 。”1 。 接下来的使用到的一些符号将在全文使用。令p 代表某个程序，p 代表对p 进行修改后的程序，t 为对p 进行测试的测试用例集。则回归测试过程可以描述 如下1 9 i ： ( 1 ) 选择t c t ，其中z 是程序p 运行时用来测试的用例集； ( 2 ) 利用丁测试程序尸，以确认程序p 在丁的正确性； 8 f 3 ) 如果必要，产生r ”，其中r ”为p 测试新增部分的用例； ( 4 ) 利用r “测试程序p + ，以确认p 。在r ”上的正确性； ( 5 ) 根据t 、z ”来产生新的测试用例集r 。 从上文可以知道，回归测试主要包括四个问题，一是找出程序中受影响的部 分：二是重新测试被影响的部分；三是重新测试，对要选择的用例确定标准；四 是重用并修改现有用例，并产生新的测试用例库。 2 3 1 回归测试过程 为了最大限度地满足客户的需要和应用的要求，软件在其生命周期中会频繁 地被修改和不断地推出新的版本，修改后的或者新版本的软件会添加一些新的功 能或者在软件功能上产生某些变化。随着软件的改变，测试用例库中的一些测试 用例可能会失去针对性和有效性，而另一些测试用例可能会变得过时，还有一些 测试用例完全不能运行。为了保证测试用例库中测试用例的有效性，必须对测试 用例库进行维护。同时，还存在着被修改的或新增添的软件功能。因此，测试用 例库的维护工作还应包括开发新测试用例，这些新的测试用例用来测试软件的新 特征或者覆盏现有测试用例无法覆盖的软件功能和特征。 测试用例的维护是一个不问断的过程，通常可以将软件开发的基线作为基准， 维护的主要内容包括以下几个方面1 1 2 i ： 2 3 1 1 删除过时的测试用例 由于版本的升级，软件会在功能上有所变化。或者增加了新的功能，或者去 掉了某些功能。或者某些功能实现方式发生变化。这时，测试用例库中针对这些 功能所设计的测试用例就不能反应软件正确性，就应当作为过时的用例从用例库 中删除。 2 3 1 2 改进不受控的测试用例 随着软件项目的进展，测试用例库中的用例会不断增加。其中会出现一些对 输入或运行状态特别敏感的用例。这些用例不容易重复，而且结果难以控制。会 影响回归测试的效率，必须对其加以改进，使其达到可重复、可控制的要求。 2 3 1 3 删除冗余测试用例 有时候，在已有的测试用例集中存在两个或多个相同的用例是针对相同的输 回归测试选择技术研究 入和输出，那么则称这些用例是冗余的。冗余的测试用例会降低回归测试的效率， 所以要经常性的对用例集进行整理，并将冗余的测试用例删除掉。 2 3 1 1 增添新的测试用例 由于软件版本的不断修改，会出现某些新的程序段、构件或关键的接口没有 被测试到。那么应该产生新的测试用例重新对其进行测试，并将新的测试用例合 并到原有测试用例集中去。 通过对测试用例库的维护，不仅改善了测试用例的可用性，更重要的是提高 了现有测试用例集的可信性，同时还可以将上一个版本的测试用例集的效率和效 用保持在一个较高的级别上。 2 3 2 回归测试策略 在软件开发过程中，软件维护的成本可以占到整个开发成本的5 0 以上。而 回归测试的成本则可能占软件维护成本的1 2 1 。因此如何选择经济( 可以节省成 本) 而有效( 尽可能找出存在软件中的错误) 的回归测试方法，就显得十分必要 了。 由于回归测试存在测试时已经存在构造好的测试用例集，所以对已有用例加 以复用。在实际测试过程中，复用已有用例的一种方法是对所有原有用例进行测 试。这种方法称作“重测所有”( r e t e s t a 1 1 ) 。但是，重测所有的测试用例可能花 费大量不必要的时间和资源。而且由于重要软件的回归测试进行得更加频繁，从 而使软件开发成本大幅提高。为了减少测试成本，可以从原有的测试用例中，根 据某种规则来选取部分用例进行测试。这种测试测试技术叫作选择性回归测试。 目前主要的选择性回归测试主要有四种策略m l s l 。一是安全选择策略，即选择 覆盖所有程序中受影响部分的测试用例1 6 ，s ，3 4 1 ；一种是最小化选择策略，其做法是 选择已有的测试用例的最小子集，保证程序中受影响部分至少被覆盖一次【3 1 1 1 第 三种是随机选择策略，由测试人员从原有测试用例集t 中随机选择测试用例，或 根据个人知识、经验来进行选择。第四种是重测试所有策略，即选择所有已有用 例来进行测试。 这四种策略各有其特点( 7 | 9 r 1 1 m 1 ( 1 ) 重测所有策略适合于程序修改较大的情况，通过重测所有用例可以保证 在程序修改后原来正确工作的代码不会产生新的错误。 ( 2 ) 随机选择策略依赖于测试人员本身的经验，随意性较大。但是其用例选 择的成本小，有经验数据表明，其错误检测能力也尚可。 1 0 硕士学位论文 ( 3 1 最小化选择策略选择的用例集最小，所以对用例测试成本较小。但其错 误检测能力较差。 ( 4 ) 安全选择策略错误检测能力较强，且用于回归测试的用例集也不会很大， 所以适合于一般情况下的回归测试。但如果程序规模过大，对程序进行分析的成 本也会可观。 2 4 小结 本章阐述了回归测试方法所要考虑两个方面，一是怎样来维护用例库：另一 个是怎样来选择用例进行回归测试。最后讨论了几种回归测试策略，并分析了它 们所适用的场合。 回归测试选择技术研究 3 1 引言 第3 章面向过程的回归测试选择算法 在面向对象技术得到发展以前，大量的程序都是面向过程的。针对面向过程 的程序提出了很多测试选择算法，如算法等。但是以上这些算法的用例选择精度 较低，所以r o t h e r m e l 和h a r r o l d 提出了s a f e 回归测试选择算法【4 1 。本文将详细讨 论r o t h e r m e l h a r r o l d 面向过程的测试选择算法。 3 2 1 回归测试选择 选择性的回归测试( s e l e c t i v er e g r e s s i o nt e s t ) 是一种非常重要的回归测试方 法。该方法可以通过复用已有用例集，在原有用例集中选择部分用例来进行测试， 从而达到降低测试成本的目的。 典型的回归测试过程可以描述如下l ，1 ： ( 1 ) 选择t c t ，其中丁是程序p 运行时用来测试的用例集： ( 2 ) 用z 测试p 1 ，以确认程序p 在r 的正确性； f 3 ) 如果必要，产生r ”，其中丁”为p 测试新增部分的用例； ( 4 ) 用丁”测试p ，以确认p 。在丁”上的正确性： ( 5 ) 根据t 、r 来产生新的测试用例集r 。 从以上描述可知，选择性回归测试主要包括以下几个问题： ( 1 ) 回归测试选择问题( r e g r e s s i o n t e s ts e l e c t i o n ) ，即根据修改后的程序p ， 从原有的测试用例集t 中选出一个子集r 。这个问题也包括了如何从原有用例集 t 中选出过时用例。所谓过时用例，是指根据程序p 的规格s ，该用例t 所指明 的对于程序p t 一个( i n p u t ，o u t p u t ) 不合法，或者t 所规定的输入对p 不合法。 ( 2 ) 是否需要进行附加测试的问题： ( 3 ) 测试执行问题，即有效的执行测试并进行测试结果验证； f 4 ) 钡l j 试维护问题，包括更新用例库和存储测试信息。 硕士学位论文 3 2 2c f g 令p 代表一个程序，尸代表修改后的程序；s 和次s 分别指p 和尸的规格。 p ( i ) 为p 在输入为i 时的输出，p ( i ) 为p 在输入为i 时的输出；s ( i ) 指p 在输入为 i 时的预期输出；s ( i 、为p 在输入为i 时的预期输出；t 为用来测试p 的用例集i 。 压a 怂 惑 ( 割 鬯岁 i n tc o u n t p o s i t i v e ( i n ta 【 。i n ts i z e ) s 1i n tc o u n l = o ： p 2 , h i l e ( s i z e 0 ) f p 3i f ( a s i z e 一1 0 ) s 4c o u l l t + 4 ： s 5s iz e 一：) s 6r e t u r nc o u n t ： 图3 ，1 蟊数c o u n t p o s i t i v e ( 其控制流固 一个测试用例可以用一个三元组 。其中i d e n t i f i e r 用来 标志一个测试用例，i n p u t 为程序执行时的输入，o u t p u t 则为预期输出s ( i n p u t ) 。 控制流图是一种用节点代表程序段，边代表从给定程序段到别的程序段的一种网 络图。图3 1 给出了函数c o u n t p o s i t i v e 0 及其控制流图。 在图3 1 中语句节点用椭圆表示，代表简单语句。谓词节点用矩形表示，代 表条件语句。标记为“t ”或“f ”的边描出了在谓词节点对条件进行取值( 真或假) 后出发到下一个节点的控制流。节点标志与其在程序中的位置一一对应。图3 1 中使用语句行号作为节点标志。而声明语句和非可执行语句可以用一个单独的节 点d 来表示。e n t r y 和e x i t 分别代表程序的入口和出口。每个程序只有一个出口 和入口。构造控制流图的复杂度为o ( n ) ，n 为程序中简单语句和条件语句的数量。 图3 2 给出了控制流图的样例。 回归测试选择技术研究 3 2 3 代码执行 l l 、顺序2 、条仆3 、循环 图3 2 控制流图样例 给定程序p 及其控制流图g ，并创建测试用例t 用来执行程序p 。在程序执 行过程中，可以记录下来一些相关信息，如经过的节点和边。我们把这个过程日q 作 “分支追踪”( b r a n c ht r a c e ) 【6 ，r _ ”。通过这种方式，可以确定程序执行时，其对应 的控制流图g 中有哪些边被遍历。对于边( n l ，n 2 ) ，称其被遍历当且仅当与节点n 1 和n 2 对应的语句在执行过程中至少被顺次执行1 次。通过这种方法收集到的信息 称为程序p 在使用测试用例t 作输入时的“边轨迹”( e d g et r a c e ) 。该信息可以用 一个位向量( b i tv e c t o r ，见表3 2 ) 来表示。得到该信息所需要的开销为o ( e ) ， 其中e 为g 中的边的数目。 表3 1 测试用例执行信息 用例输入输出遍历边 ( e n t r y , d ) ，( d ，p 2 ) ，( p 2 ，p 3 ) ，( p 3 ，s s ) ， t 1 ( - 1 ) 0 ( s 5 ，p 2 ) ，( p 2 ，s 6 ) ，( s 6 ，e x i t ) ( e n t r y ，d ) ，( d ，p 2 ) ，( p 2 ，p 3 ) ，( p 3 ，s 5 ) ， t 2 ( 0 ，1 ) 1 ( p 3 ，s 4 ) ，( s 4 ，s s ) ，( s 5 ，p 2 ) ，( p 2 ，s 6 ) ，( s 6 ，e x i t ) ( e n t r y , d ) ，( d ，p 2 ) ，( p 2 ，p 3 ) ，( p 3 ，s 4 ) ，( s 4 ，s s ) t 3 ( 1 ，2 ，3 ) 3 ( s 5 ，p 2 ) ，( p 2 ，s 6 ) ，( s 6 ，e x i t ) 对给定的程序p 的测试用例集t ，其测试信息( t e s th i s t o r y ) 可以通过对测 试用例集t 中的每个测试用例收集“边轨迹”来构造。在测试信息中，每一个遍 历边( n l ，h e ) 的用例被记录下来。这种表示方法需要o ( e l t i ) 位比特，其中e 为控制 流图g 中的边的数目，为测试用例的个数。特别地，对于控制流图c f g 而言， 边的数目应当不大于节点数目的两倍，因此。e 与程序大小呈线性关系。表3 1 和表3 , 2 分别给出了函数c o u n t p o s i t i v e 0 的测试用例执行信息及测试历史。 硕士学位论文 为了便于研究，我们假定可以通过函数t e s t s o n e d g e ( ) 来获得经过边( n 1 ，n 2 ) 的测试用例。其返回值形式如1 0 1 ，每一位代表一个比特位。第k 位表示第k 个 用例是否经过该边，0 代表不经过，1 代表经过。 表3 , 2 用例边映射信息 e d g et e s t s o n e d g e ( e d g e ) ( e n t r y ，d ) 1 l l ( d ，p 2 ) 1 1 1 ( p 2 ，p 3 ) 1 1 1 c e 3 ，s 4 ) 0 1 1 ( s 4 ，s 5 ) 0 1 1 ( s 6 ，rm t ) 1 1 1 ( p z s o 1 1 1 ( p 3 ，s 5 ) 1 1 0 ( s 5 ，p 2 ) 1 1 l 回归测试选择的主要目的就是从原有的测试用例集t 中选出所有没有过时的 用例来对程序p i 中对比程序p 改变了的部分进行测试。这些被选择的用例应该满 足如下条件之一： ( 1 ) 所执行的程序部分应该是新增加的或已更改的； r 2 ) 在程序p 中执行的部分在p t 已被删除。 为了便于描述我们用到程序p 在用例t 上的执行轨迹( e x e c u t i o nt r a c e ) e t ( p ( t ) ) 。e t ( p ( t ) ) 是指程序p 在使用测试用例的执行过程中所经过的一系列语句。 两个执行轨迹e t ( p ( t ) ) 、e t ( p i ( t ) ) 相等当且仅当其长度相同且这两个轨迹中 相互对应的元素有相同的用文本表示。特别地，称个测试用例t 是“遍历修改” 的，当且仅当e t ( p ( 0 ) 和e t ( p ( t ) ) 不等。要从测试用例集t 中找出所有“遍历 修改”的用例，必须把用例集中未过时即e t ( p ( t ) ) 和e t ( p ( t ) ) 不等的用例找出 来。 下文将分别对过程内回归测试选择和过程间回归测试选择算法进行详细讨 论。 回归测试选择技术研究 3 3 1 过程内回归测试选择算法 本文3 2 2 讨论了控制流图的生成及表示方法。对于每个程序的c f g 及用例 t ，可以有一个唯一的执行轨迹与之对应。这种对应关系可以通过将执行轨迹中的 语句用c f g 中的节点或节点标号来获得。而从这种对应关系又可以得到所谓的 “遍历轨迹”( t r a v e r s