面向对象软件回归测试技术研究
摘要
面向对象技术正逐渐代替被广泛使用的面向过程的开发方法，被看做是解决软件危机的新兴技术。面向对象技术产生了更好的系统结构，更规范的编程风格，极大的优化了数据使用的安全性，提高了程序代码的重用，一些人就此认为面向对象技术开发出的程序无需进行测试。应该看到，尽管面向对象技术的基本思想保证了软件应该有更高的质量，但实际情况却并非如此，因为无论采用什么样的编程技术，编程人员的错误都是不可避免的，而且由于面向对象技术开发的软件代码重用率高，更需要严格测试，避免错误的繁衍。因此，软件测试并没有面向对象编程的兴起而丧失掉它的重要性。
回归测试是软件生命周期中的一个组成部分，在整个软件测试中都占有比较大的工作比重，软件开发的每个阶段都会进行很多次回归性测试。在渐进和快速迭代的开发中，新的版本连续发布让回归测试进行得更频繁，然而在极端的编程方法中，更要求每天都要进行无数次回归测试。所以，通过利用正确的回归测试策略来改进回归测试的效率和有效性是很有意义的。
关键词:面向对象;软件测试;回归测试;测试选择;测试用例排序
Abstract
Object-oriented technology is gradually replacing the widely used process-oriented development method, to solve the software crisis was seen as an emerging technology. Object-oriented technology architecture produced better, more standardized programming style, great use of optimized data security, improve code reuse, some people conclude that the development of object-oriented program without the need for test. It should be noted, although the basic idea of object-oriented software should ensure a higher quality, but the reality is not so, because no matter what kind of programming, programmer mistakes are inevitable, and because object-oriented technology development of software code reuse rates, but more rigorous testing, to avoid the error propagation. Therefore, software testing and the rise of object-oriented programming does not lose its importance lost.

Software life cycle, regression testing is an integral part in the possession of the entire software testing are relatively large proportion of the work, each stage of software development will be a lot of time regression testing. In the gradual and rapid iterative development, continuous release of new versions more frequently so that regression tests, but in extreme programming methods, but also require many times every day for regression testing. So by using the right regression testing strategy to improve the efficiency and effectiveness of regression testing is of great significance.
Keywords: object-oriented; software testing; regression testing; Test Selection; test cases ordering

目录
第一章 绪  论 3
1.1 研究背景 3
1.2 国内外研究现状及进展 4
1.3 本文主要的工作及意义 4
1.4 论文的组织形式 5
第二章 面向对象程序的回归测试 5
2.1 面向对象软件的特点对测试的影响 6
2.1. 1封装性对测试的影响 6
2.1. 2继承性对测试的影响 7
2.1. 3多态性和动态绑定对测试的影响 8
2.2 面向对象程序回归测试问题 8
2.3 面向对象程序回归测试范围 9
2.4 面向对象程序回归测试套 9
2.5 小结 10
第三章 回归测试选择算法 10
3.1 引言 10
3.2 回归测试选择算法 10
3.3  面向过程回归测试选择算法 11
3.3. 1控制流图 ( CFG) 11
3.3. 2自代码执行 12
3.3. 3过程间测试选择算法 13
3.3. 4面向对象回归测试选择算法 15
3.4 回归测试选择算法 16
3.5 小结 17
第四章 新的面向对象回归选择测试算法和测试用例排序 17
4.1 引言 17
4.2 类的划分 18
4.2. 1类的关系分析 18
4.2. 2类的关系分析算法 19
4.3 测试用例选择 21
4.3. 1自然概况 21
4.3. 2进行测试用例选择 22
4.4 本文方法的有效性 22
4.5 测试用例排序 23
4.6 小结 24
第五章 总  结 24
参考文献 25
致谢 25
第一章 绪  论
软件测试是保障软件质量、提高软件产品可靠性的重要手段，是实施软件项目 不可缺少的环节。从计算机诞生起，计算机安全问题就伴随其左右，尤其是软件方 面，层出不穷的软件故障以及由此带来的严重后果使人们意识到软件测试对软件质 量具有重要的意义。许多计算机科学家在展望二十一世纪计算机科学的发展方向和 策略时，都十分注重提高软件质量。因此，作为保证软件质量最有效手段的软件测试技术，已成为令人关注的一个研究领域。    
Rcogry  Tasscy博士对美国软件业现状研究表明:到2姗年为止，美国软件 从业人员达到1，282，000人，软件年销售总额达到1，800加亿美元，同时，软件失效 导致每年595亿美元的经济损失，据估计，若能减少当前软件中1/3的缺陷，就能 挽回222亿美元经济损失。    
软件测试是软件工程的重要组成部分。软件测试的直接目的是发现软件中存在 的缺陷。随着软件工程技术的发展，软件规模的增大，软件测试在软件开发过程中 的作用显得越来越重要。据Boehm统计，软件开发总成本中，用在测试上的开销 要占40%~50%，软件测试在国内外己经受到广泛重视并进行了长期的研究。
1.1 研究背景
面向对象编程 (OOP ) 近年来己经广为流行，已逐渐代替被广泛使用的面向 过程的开发方法，被看成是解决软件危机的新兴技术。OOP适用范围非常广， 提供了抽象方法和类库来支持各个领域的应用程序开发。从理论上来说， 面向 对象编程技术应该能够保证软件有更高的质量，但实际情况却并非如此。因为无论采用什么样的编程技术，程序的错误都是不可避免的，而且由于面向对象编程技术的特征 (抽象)使得程序代码重用率增高，因 此更需要严格测试，以 避免错误的繁衍. 面向对象软件具有面向过程软件所没有的特点，与传统顺序结构式方法在开发思想上有着根本的不同， 面向 对象软件具有类、继承、封装等特性，而过程软件则以功能模块间的控制流程为重点。这些特点决定了测试面向 对象软件需要新的策略，使得面向对象测试在测试步骤的划分以及测试策略的选择上有别与传统的测试。   
由于面向对象软件的复杂性，给基于程序代码的测试带来困难，同样也使回归测试的难度增加. 回归测试有两种常见的策略，一种是重新测试所有部分的方法，它运行所有的测试用例，但这种策略可能消耗大量的时间及资源;另一种是回归测试选择技术，通过选择某些现存的测试库的子集去重新测试修改的程序，以降低时间需求。而回归测试选择技术也有两种方法:安全方法和最小化方法. 安全方法是选择所有覆盖了受影响的测试用例，而最小化方法是选择测试用例的最小子集，使得每一个受影响的部分被覆盖至少一次. 对于回归测试选择技术，首先考虑的是如何高效的识别软件修改和修改所影响的部分，从而能集中精力对这些修改和修改受影响的部分进行测试， 因此我们要理清程序代码中的各种关系，然后考虑如何重用现存的测试用例和测试库。国内外在这些方面都提出了一些相关的策略来提高回归测试的效率。
1.2 国内外研究现状及进展
(1 )方菲等人针对面向对象软件，通过分析对象系统的特性，定义了对象之间的依赖关系，通过这个依赖关系，导出测试对象的方法序列，并应用程序切片技术，标识那些受到程序修改影响的测试用例，只有这些测试用例才需要在回归测试中重新执行。   
( 2) 王影提出了一种利用“条件切片”技术 ，来专门检验对于循环和选择结构中“ 控制谓词”的修改方法，从而更进一步降低回归测试的成本。   
(3)K.Abdullah and White提出了回归测试的防火墙概念。针对面向对象的程序扩展类防火墙，以类为测试的基本单元，先标识出改变的类与受改变影响的类，即构造一个类防火墙，然后对类防火墙中的类根据对象关系图以一定的顺序进行回归测试。   
( 4) Roth e rm e l 提出的基于CP G 的用例选择算法. 该方法根据给定的 程序来构造相应的CF G 或P民，然后再比较程序修改前后的图，找出修改部分来进行用例选择，主要针对是面向过程的用例选择算法。   
( 5) H arro l d和他的同事提出面向Java程序的回归测试选择算法阁 。 该方法使用J IG ( J a va lnterclass G raph) 来表示Java程序， 他的方法对整个系统的类构造J I G图，来分析修改的部分以及所影响的部分。   
比较上述几种算法，面向Ja v a程序的回归测试选择算法具有较高的用例选择精度，同时可以处理 Ja v a 程序的各种特性。本文的工作正是基于文献提出的算法。   
还有许多针对 不同面向 对象语言特点进行回归 测试选择技术方面的文章.总之，回归测试是一项很耗时，成本很高的活动，各种研究都主要是围绕着降低成本，减少测试时间但又要确保软件的可靠性来进行的，来尽可能找出软件中未发现的错误。
1.3 本文主要的工作及意义
回归测试作为软件生命周期的一个组成部分，在整个软件测试过程中占有很大的比重，软件开发的各个阶段都会进行多次回归测试。在渐进和快速迭代开发中，新版本的连续发布使回归测试更加频繁，甚至是要求每天都进行若干次回归测试。因此，选择正确的回归测试策略来改进回归测试的效率和有效性是非常有意义的。   
回归测试主要解决的是怎样有效地确定修改受影响部分以及重利用测试用例库的问题。修改影响分析为测试用例的选择提供了依据，因此在进行回归测试选择之前，必须要确定修改以及修改受影响的部分。回归测试需要解决的四个基本问题对应于回归测试的过程如下:
1.修改影响分析: 鉴别修改和修改受影响的部分。
2.测试顺序: 重测影响部分的策略。
3. 覆盖标准: 重测部分的覆盖标准。
4. 测试用例库(Test Suite )的维护: 测试用例库的维护包括测试用例库的选择、重用和更新。
   本文的重点是围绕上面的四个基本问题中的前两个， 即如何鉴别修改影响的部分和重测影响部分的策略做以下几方面的工作: 
(1 )深入研究 现有的回归 测试选择方法，包括面向 过程的回归测试选择方法和面向对象的回归测试选择方法。 
(2)针对现有的面向对象回归测试选择方法的缺点，在本文中提出一种新的面向对象回归测试选择方法。这是一种基于高层到底层对程序的回归测试方      法，在高层是对类源程序进行分析，构造类间关系图 (IRG ) ，然后用类间关      系图分析修改类以及所影响的类。 
(3)在底层是对修改的类以 及所影响的 类， 用J I G 图构造类成员关系图，然后根据J I G 图来识别d a n g e r o u s 边 (重新执行的边)，从而选择测试用例。 对于选择的测试用例进行排序，提高代码的检测率。
(4)由以 上的内 容，提出一种针对J A VA 语言的回归测试框架。
1.4 论文的组织形式
    第一章 介绍了研究背景及国内外回归测试研究状况，然后介绍了本文的主要工作。     
第二章 阐述了面向对象回归测试的主要特点和存在的问题。     
第三章 研究了目前面向过程的回归测试选择算法以及面向对象的回归测试选择算法。     
第四章 提出一种新的面向对象回归测试选择算法， 并对选择的测试用例进行排序。
第五章 总结

第二章面向对象程序的回归测试
   面向对象软件测试技术的研究是面向对象开发方法中不可缺少的一环，是保证软件质量、提高软件可靠性的关键。软件测试的任何阶段均涉及到回归测试问题。回归测试的目的是在程序修改后，只对进行修改和修改受影响的部分重新测试，从而达到与完全测试相同的测试覆盖效果。对于面向对象程序来说，进行完全的回归测试不仅没有必要，而且从测试代价上讲也是不现实的。目前己 提出的回归测试技术大都是针对结构化程序的，对面向对象软件的回归测试技术还在进一步研究中，有待加强和提高。
2.1 面向对象软件的特点对测试的影响
从1 9 8 2 年在美国北卡罗 来纳大学召开首次软件测试的正式技术会议至今，软件测试理论迅速发展，井相应出现了各种软件测试方法，使软件测试技术得到极大的提高。然而，一度实践证明行之有效的软件测试对面向对象技术开发的软件多少显得有些力不从心。尤其是面向对象技术所独有的多态，继承，封装等新特点，产生了传统语言设计所不存在的错误可能性，或者使得传统软件测试中的重点不再显得突出，或者使原来测试经验认为和实践证明的次要方面成为了主要问题。   
面向对象程序的结构不再是传统的功能模块结构，作为一个整体，原有集成测试所要求的逐步将开发的模块搭建在一起进行测试的方法己成为不可能，而且，面向对象软件抛弃了传统的开发模式，对每个开发阶段都有不同于以往的要求和结果，已经不可能用功能细化的观点来检测面向对象分析和设计的结果。因此，传统的测试模型对面向对象软件已经不再适用。针对面向对象软件的开发特点，面向 对象的开发 模 型突破了传统的瀑布模型，将开发分为面向对象分析( OOA) ，面向 对象设计 (OOD) ，和面向对象编程 (OOP) 三个阶段。分析阶 段产生整个问题空间的抽象描述，在此基础上，进一步归纳出 适用于面向 对象编程语言的类和类结构，最后形成代码。由于面向对象的特点，采用这种开发模型能有效的将分析设计的文本或图表代码化，不断适应用户需求的变动。针对这种开发模型，结合传统的测试步骤的划分，提出一种整个软件开发过程中不断测试的测试模型，使开发阶段的测试与编码完成后的单元测试、集成测试、系统测试成为一个整体。
 O0A Test 和OOD Test 是对分析结果和设计结果的测试，主要是对分析设计产生的文本进行测试，是软件开发前期的关键性测试。OOP Test主要针对编程风格和程序代码实现进行测试，其主要的测试内容在面向对象单元测试和面向对象集成测试中体现。面向对象单元测试是对程序内部具体单一的功能模块进行测试，如果程序是用 Ja v a语言实现，主要就是对类成员函数进行测试。面向对象单元测试是进行面向对象集成测试的基础。面向对象集成测试主要对系统内部的相互服务进行测试，如成员函数间的相互作用，类间的消息传递等。面向对象集成测试不但要基于面向 对象单元测试，更要参见OOD或OOD Tcst 结果。面向对象系统测试是基于面向对象集成测试的最后阶段的测试，主要以用户需求为测试标准，需要借鉴OOA 或00A Tcst 结果。面向对象的回归测试与上面的测试都穿插在一起，每一阶段测试完成后有错误就要修改，修改后就要进行相应的回归测试。   
以上是关于面向对象技术对测试的整体影响，下面我们对面向对象的几项常见的特点对测试的影响进行分析。
2.1. 1封装性对测试的影响
封装是将类和对象的接口与实现分离，屏蔽类和对象的内部实现细节，封装大多数的情况下是通过信息隐蔽实现的。信息隐蔽是指仅仅显示类和对象的外部使用者所需的属性和方法，而将一些无关的信息隐蔽起来。不管在设计阶段还是以后的维护阶段，类和对象暴露在外面的信息越多，发生错误的可能性就越大，程序员需要考虑的 事情就越多。 通过封装和信息隐蔽，类和对象的使用者就无法随便读取和修改类和对象的内部信息，这就在很大程度上防止了错误的发生，提高了程序的可维护性. 对于测试人员，类是组成系统的 基本单元(例如Ja v a ) ， 单元测试中以类为基本单元进行测试就很容易得到要测试的单元，方便测试人员划分测试单元，但是类的封装性使测试人员无法了解对象的状态信息，因而也不知道一个输入所对应的对象状态是否正确.例如对象Us t 中有Ad d ， De l e t 。和助ng i h等方法，如果我们通过方法A d d增加了一个表项，那么我们如何知道该表项所插入的位置正确呢?正是由于封装和信息隐蔽，我们无法直接考察对象的内部实现，从而无法确认操作的正确性。通常我们只有在类和对象上添加一个成员函数，该函数用于读取 (而不是修改 )对象的 状态信息，为测试人员 提供对象的 一些隐蔽信息，考察对象的状态变化的正确性，即在测试点加入探针。但这种方法在有些情况是不适合的，如果被测试的代码中也有相同的成员函数时，你所加的成员函数重载了原来的函数，可能会影响到其他调用成员函数的类。   
另外对于非实例化的类，我们不能用这个类的实例来验证类中的属性和操作的正确性。共有抽象类、泛型类和混合类这三种不能实例化的类，测试人员必须开发一个最小的测试套来测试这些非实例化的类与其他类绑定后的情况能否满足需求说明。
2.1. 2继承性对测试的影响
继承性是面向对象软件系统的主要特征，在一定程度上实现了软件代码的重用，允许派生类继承一个或多个类的属性和操作，派生类可以修改、删除或增加属性和操作。因为派生类是从基类继承而来，假设基类经过测试了，那么从其派生出来的类的那些继承属性和操作就不再要测试了。在文献中己证明这种直观的 想法是 错误的， 结合weyuckcr的 测试充 分性公理， 从派生 类中 继承的 属性由于上下文的不同需要重新测试。因此根据己经测试过的基类的一些情况来测试派生类，即增量测试，并不需要重新测试所有继承的属性，我们可以先判别出需要重测的属性，即最小化不同于父类的属性行为集。
继承可分为严格继承和非严格继承 . 严格继承是指派生类与基类的关系是一般与特殊的关系，派生类继承了基类的所有属性和操作，并且派生类还增加了一些特殊的属性或操作。对于这种情况，测试很简单，基类的所有测试用例仍然可以用来测试派生类，但是还要增加一些新的测试用例来测试新加的特征以及它是否会对原来的特征产生影响。非严格继承是指基类中的一些属性操作在派生类中没有或者己经改名，这可能是简单的非严格继承、多重继承或者重复继承。 派生类仅继承于一个基类，且派生类中增加了一些新的特征，还重定义了基类的一些特征，这就是简单的非严格继承，这时与派生类中同名的基类的特征在基类中就变了，基类的对象集合可能还会调用这个同名的操作，如果基类的对象集合中有一个对象是派生类的对象，那么就可能出现错误，需要测试人员对这方面进行考虑。多重继承是指一个派生类从两个或两个以上的基类继承而来，基类的所有特征构成一个新的类。从两个基类继承而来的特征名必须用不同的标识符表示，这就需要进行重命名，类结构也不再是一个简单的层次结构而是一个连通图，基类的改变可能使派生类之间有负面影响，这些都是测试人员在测试多重继承时需要考虑的，不然程序在这些方面就会出现错误，这样增加了测试的难度。重复继承是指一个派生类多次继承于同一个基类，这意味着许多重复相同的特征需要重命名或删除，重复继承比多重继承更复杂，需要测试人员做更多的分析来决定祖先类、父类和子孙类之间如何进行测试，以排除其中可能会产生的错误。
2.1. 3多态性和动态绑定对测试的影响
   多态性和动态绑定是面向对象方法的关键特性之一。同一消息可以根据发送消息对象的不同 采用多 种不同的行为方式，这就是多态的概念。如根据当前指针引用的对象类型来决定使用正确的方法，这就是多态性行为操作。运行时系统能自 动为给定消息选择合适的实现代码，这给程序员提供了高度柔性、问题抽象和易于维护的方便。但多态性和动态绑定所带来的不确定性，使得传统测试实践中的静态分析法遇到了不可逾越的障碍，而且它们也增加了系统运行中可能的执行路径，加大了测试用例的选取难度和数量。   
   由以上分析可知，在面向对象系统中，系统的基本构造模块是封装了的数据和方法的类和对象，而不再是一个个能完成特定功能的功能模块。每个对象有自己的生存周期，有自己的状态。消息是对象之间相互请求或协作的途径，是外界使用对象方法及获取对象状态的唯一方式。对象的功能是在消息的触发下，由对象所属类中定义的方法与相关对象的合作共同完成，且在不同状态下对消息的响应可能完全不同。工作过程中对象的状态可能被改变，产生新的状态。对象中的数据和方法是一个有机的整体，测试过程中不能仅仅检查输入数据产生的输出结果是否与预期的吻合，还要考虑对象的状态。模块测试的概念已不再适用于对象的测试。类测试将是整个测试过程的一个重要步骤，它与传统测试方法的区别如图2 . 1 所示。
图2. 1 两种不同的测试模型

2.2 面向对象程序回归测试问题
   回归测试是在软件维护阶段，对软件进行修改之后，对修改以及修改受影响的部分进行测试。回归测试的目的是检验对软件进行的修改是否正确。在此，修改的正确性有两重含义: 一是对软件的修改达到了预期目的; 二是软件的修改对软件的其他功能没有产生副作用，即没有导致其他功能的不正常。回归测试将大幅降低系统测试、维护升级等阶段的成本。   
   回归测试包括两部分: 对修改部分的测试以及与修改相关代码的测试。对被修改部分的重新测试，如果修改部分的功能以及接口没有发生变化，可以直接运行原来的测试用例。但是如果修改导致功能或接口发生变化，则要根据修改后的功能点或接口的变化增加、删除或改进测试用例。由于程序的修改会对软件产生涟漪效应，因此对与修改部分有交互关系的代码也要进行重新测试，以此来保证修改没有对软件产生不良作用。
   第一章的1.3节中提到了回归测试过程四个问题，在进行回归测试时，首先对程序的修改和修改影响范围进行确定，这部分工作用于确定进行测试的对象。确定测试对象后，需要对测试对象选择测试用例，这牵涉到第 2、3、4 个问题。在重测策略方面可以 选择重测所有测试用例或选择性测试，由于重测所有策略的工作量大，效果不明显，因此大部分回归测试都进行选择性测试，只选取一部分测试用例进行测试。这导致需要确定选择测试用例的标准，即测试用例的覆盖标准。通常，进行选择性回归测试的覆盖标准是要保证测试用例覆盖修改和修改影响的部分。   
   回归测试还有一个重要的部分就是对测试套 (测试用例库) 进行维护。由于程序的不断改进和发展，其测试套越来越大，因此有些测试用例是冗余的，需要对测试套进行精简。
2.3 面向对象程序回归测试范围
软件的测试套是由测试该软件的所有测试用例组成的。在进行回归测试的时候，根据所确定的回归测试策略，从测试用例库中提取合适的测试用例组成回归测试套，通过运行回归测试套来实现回归测试。不同的回归测试策略将直接导致不同的测试结果. 常用的回归测试策略根据测试的目标不同可分为以下三种：
 （1）局限在修改范围内的 测试。这类回归测试仅根据修改的内容来选择测试用例，这种测试只能保证修改的缺陷或新增的功能被实现了，对于修改是否对整个系统产生影响并不加以考虑。因此，该类测试方法效率最高，但风险最大。  
 ( 2)在受修改影响的功能范围内进行回归测试。这类回归测试需要分析对当前的修改可能影响到哪部分代码或功能，对于所有受影响的功能和代码都将被重新测试。这类测试避免了第一类测试方法的不足，同时其测试效率比全部重测的方法高。现有的回归测试策略基本上都采用这种方式。   
( 3) 根据一定的覆盖率指标选择回归测试. 该方法一般是在相关功能影响范围难以界定的时候使用。由于功能范围难以界定，测试的对象就难以确定。为了确定测试对象，同时提高测试效率，可以设定一个测试指标来进行测试. 这种方式最简单的策略是规定修改范围内的测试是 10 0 %，其他范围内的测试规定一个用例覆盖阀值，例如 60 %。
2.4 面向对象程序回归测试套
   在面向对象程序不断地发展和维护过程中，程序会经常变动，如进行修改、添加或删除等操作，将会导致软件功能、应用接口以及实现方式等发生变化。因此在测试套中的某些测试用例就失去了有效性，甚至完全不能运行，而且由于添加了新的软件功能，在原测试套中对这些新增功能的测试用例往往都不存在，这将导致程序测试的遗漏，可能会引起整个系统的错误，产生严重的后果。为了保证测试套中测试用例的有效性和完整性，必须对测试用例库进行维护和升级。对程序中现有的测试用例无法测试的部分，必须设计添加新的测试用例。因此，测试套的维护工作不仅包括确定测试套中测试用例的有效性，还包括设计增加新的测试用例来保证测试的完整性。用这些新的测试用例来测试软件新功能或覆盖现有测试用例无法覆盖的软件功能或特征。
2.5 小结
   本章介绍了面向对象程序测试存在的问题，根据回归测试需要解决的问题，整体上介绍了回归测试的基本过程， 回归测试用例的选择以 及测试用例库的维护。

第三章 回归测试选择算法
3.1 引言
    对于基于程序代码的回归测试，国内外提出了很多测试选择算法。但是这些算法的用例选择精度较低，所以Rothcrmel 和Harrold提出了安全的回归测试选择算法。本章将详细讨论Rothermcl 面向过程的测试选择算法门和Harmld 和他的同事提出的面向对象的测试选择算法，下一章根据他们算法的缺点提出本文的算法。
3.2 回归测试选择算法
   在软件生命周期中的任何一个阶段，只要软件发生了变化，就可能给该软件带来问题。为了验证修改的正确性及其影响就需要进行回归测试，选择性的回归测试 ( seleCtivc Rcgression Test ) 是一种非常重要的回归测试方法。 该方法可以 通过复用己有用例集，在原有用例集中选择部分用例来进行测试，从而达到降低测试成本的目的。   
   接下来使用到的一些符号 将在全文中 使用。令 P 代表某个程序，P ’代表对 P进行修改后的程序，T为对P进行测试的测试用例集.则回归测试过程可以描述如下:
   (1)回归测试选择问题 (Rcgression Test sclection )，即根据修改后的程序P ’， 从原有的测试用例集T 中选出一个子集T。这个问题也包括了如何从原有用例集T 中选出过时用例。所谓过时用例，是指根据程序P ’的规格s ’，该用例t所指明的对程序P ’的一个(InPut,Output )不 合法， 或者t所规定的输入对P不合法;
(2) 是否需要进行附加测试的问题;
(3) 测试执行问题，即有效的执行测试并进行测试结果验证;
(4) 测试维护问题，包括更新用例库和存储测试信息。
3.3  面向过程回归测试选择算法
  介绍面向过程回归测试选择算法之前，先介绍跟面向过程有关的控制流图  (CFO) 和代码执行。
3.3. 1控制流图 ( CFG)
令5和5.分别 指P和F的 规格. P ( i ) 为P在 输入为1时的 输出， P ’ ( i ) 为P在输入为1时 的 输出 ; s ( i )指P在输入为1时的 预期输出; s ’ ( i ) 为P在输入为1时 的 预期输出; T 为用来测试 P 的用例集。
    一 个测 试用例可以 用一个三元组< identifier，input ，output >来表示. 其中记 identifier用来标识一个测试用例， inPut为程序执行时的输入，outPut则为预期输出s ( input) .控制流图是一种用节点表示的 程序段， 用边代表从给定程序段到别的程序段的一种网 络图。图3 . 1给出了函数couniPositivce() 及其控制流图。
图3.1函致couniPositivce()及其控制流图

在图3 . 1中语句节点用椭圆表示，代表简单语句. 谓词节点用矩形表示，代表条件语句。标记为“T”或“F” 的边表示在谓词节点对条件进行取值(真或假)后出发到下一个节点的 控制流。节点标识与其在程序中的位置一一对应。 图3 . 1中使用语句行号作为节点标识。而声明语句和非可执行语句可以用一个单独的节点D 来表示。Entry 和Exit 分别代表程序的入口和出口 。每个程序只有一个入口和出口。构造控制流图的复杂度为0( n) ，其中n为程序中简单语句和条件语句的数量。
3.3. 2自代码执行
   给定程序P及其控制流图G，并创建测试用例t，用来执行程序P。在程序执行过程中，可以记录一些相关信息，如经过的节点和边。我们把这个过程叫作 “分支 追踪” (Branch trace)。通过这种方式，可以确定程序执行时，其对应的控制流图G中有哪 些边被遍历。对于边(n l ，n2) 称其被遍历当且仅当与节点n l 和n2 对应的语句在执行过程中至少被顺次执行1次。 通过这种方法收集到的信息称为程序P在使用 测试用例t作 输入时的“边轨迹” (Edge Trace). 该信息可以用一个位向量(Bit Vector，见表3 . 2)来表示。得到该信息所需要的开销为O(e)。 其中e为G中边的数目。
对给定的程序P的测试用例集T， 其测试信息( Test History )可以通过对测试用例集T 中的每个测试用例收集 “边轨迹” 来构造。在测试信息中，每一个遍历边( nI ，n2 ) 的用例被记录下来. 这种表示方法需要O((e)ITI)位比特， 其 中e为控制流图G中的边的数目，ITI为测试用例的个数。特别地，对于控制流图CFG 而言，边的数目 应当不大于节点数目 的两倍，因此，e与程序大小呈线性关系。表3 . 1和表3 . 2分别给出了函数couniPositivce()的测试用例执行信息及测试信息。
表3. 1测试用例执行信息用例表

第五章总  结
    软件测试在将来相当长一段时间内仍然是软件可靠性保证的有效方法. 回归测试是测试的重要成分，在软件生命周期中扮演着重要的角色，在整个软件测试过程中占有很大的比重。软件开发的各个阶段都会进行多次回归测试，很多情况下，测试组没有足够的时间对一个频繁变化的软件进行回归测试，如何进行有效测试，减小回归测试用例集是软件回归测试研究的重点和难点。   
本文围绕回归测试选择这个主题， 首先对回归测试选择技术进行了深入研究。重点讨论了面向过程和面向Java程序的回归测试选择算法。   
本文的工作重点是面向Java 程序的回归测试选择算法，针对现有的面向对象回归测试选择方法缺点，本文提出了一种新的回归测试选择方法. 这是一种基于高层到底层对程序的回归测试方法，在高层是对类源程序分析，构造类间关系图( l RG)，然后用类间关系图分析修改类以及所影响的类. 在底层是对修改的类以及所影响的类，用JIG图构造类成员关系图。
参考文献
1、柳纯录 软件评测师教程 清华大学出版社 2008
2、梅宏译 软件工程实践者的研究方法 机械工业出版社 2009
3、杨文宏，李新辉，杨洁等译 面向对象的软件测试方法 2009
4、晏华， 袁海东， 尹立阵.代码自 动插装技术的研究与实现. 电子科技大学学报，2009， 31(1) :62一 66
5、姚励一种改进的基于动态链接库的代码插装技术. 山东师范大学学报(自然    科学版，2008， 18(3) :63一 64
6、http://www.javaworld.com/javaworld/jw-12-2006
7、软件质量保证. 王振宇， 陈利， 王志海等. 北京: 机械工业出版社，2007，128一 150
8、李刚毅，金蓓弘. 自动化回归测试的技术和实现. 计算机应用研究，2006， (02)
9、尤永康，刘乃琦. 自动化回归测试在 J a v a 项目中的实现，计算机应用，2005， (01)
10、http:.iti sedu.com / Phrase/200603120943595. htm l
致谢