基于图形遍历算法的回归测试方法的研究以及应用硕士学位论文

《基于图形遍历算法的回归测试方法的研究以及应用硕士学位论文》由会员分享，可在线阅读，更多相关《基于图形遍历算法的回归测试方法的研究以及应用硕士学位论文（64页珍藏版）》请在装配图网上搜索。

1、浙江大学硕士学位论文 摘要 基于图形遍历算法的回归测试方法的研究及应用 摘要自从发明计算机以来，信息技术飞速发展，相应的软件开发与测试也在飞速成长。软件并没有人们想象当中的那么抽象与遥远，在日常生活中接触到的电脑软件、手机软件都涉及到了软件开发。当然，软件在开发出来之后就需要经过测试来检测一下软件开发的结果，这就是软件测试。在软件测试当中经常用到的验证测试方法当属回归测试。虽然回归测试成本比较贵，但是其测试结果较准确。当然，在现实中是非常激烈的。如果使用一种有效手段，通过这种机制既可以大大降低回归测试所带来的成本又可以提高监测的效率，那么就会在竞争中处于领先地位。因此，如何研发这种机制是当今软

2、件测试的重点和难点。Extend-Dejavu算法是目前使用广泛的回归测试用例选择算法，但是该算法需要利用元数据来构造控制流图和收集覆盖信息，因此在实际使用中难度很大。本文借鉴Extend-Dejavu算法精华，开发了基于修改点控制流图的回归测试用例选择算法，能够对C语言单元函数进行逻辑结构上的比较。从而减少测试用例，提高测试效率。算法主要包括以下内容：根据控制流图对比技术检测出有效修改点；根据语句节点的数据和控制之间的依赖关系构建基于修改点的软件切片；以切片得到的节点集合作为目标覆盖集合，从基准用例库中选取相关测试用例构造回归用例选择子集T0；运行T0中测试用例；基于覆盖情况分析是否存在未覆

3、盖的目标节点，若存在则构造回归用例新增子集T1；最后合并T0和T1得到回归测试用例集合。与Extend-Dejavu算法相比，本论文主要有以下改进和创新：基于控制流图对比技术检测有效修改点，能够精确定位代码修改点；在修改点的基础上进行语句级别切片，降低了回归测试的覆盖范围；补充新的用例以保证回归测试的充分性。所以，本文提出的回归测试方法具有用例选择精度高、回归测试更加充分的特点，显著提高了回归测试的效率，明确体现了其有效性。关键词：软件测试，回归测试，Extend-Dejavu，测试切片i浙江大学硕士学位论文 AbstractAbstractSince the computers have b

4、een invented, the information technology is developing rapidly, at the same time, the corresponding software development and testing is also developing rapidly. In the process of software development, the more important aspect is the regression test. Software development is not so far from us, in ou

5、r life, we are all exposed to computer software and cell phone software, and they are all related to the software development. Of course, software developers need to come out after the software has been tested to detect what the result of the development, and this is what we know software testing. R

6、egression test is often used to software development. Although the cost of regression testing is very expensive, its test results are very accurate. Of course, in todays society, competition is very fierce. If you master an effective mechanism, we can greatly reduce the cost of regression testing at

7、 the same time, we can improve the efficiency of monitoring through this mechanism .It will compete in a leading position. Therefore, how to develop such a mechanism is the focus and difficulty of todays software testing.The Extend-Dejavu algorithm is widely used the regression test cases selection

8、algorithm, but the algorithm needs to use metadata to control flow graph and collect information, so in the practical use is very difficult. Essence, this paper Extend - Dejavu algorithm is developed based on the modified point control flow graph of regression test case selection algorithm, can carr

9、y on the logical structure to the function C language unit in comparison. To reduce the test cases, improve the test efficiency. Algorithm mainly includes the following content: according to the control flow chart compares technology to detect the effective modification point; According to the state

10、ment data dependency and control dependency between nodes based on modified point build of the software section; To slice the node set as the target coverage set, from the baseline test cases selecting the related test case library T0 select subset regression cases; Run test cases in the T0; Based o

11、n the analysis whether the cover has not covered the target node, if there is the structure new subset regression case T1; Finally merge T0 and T1 regression test case set. Compared with the Extend-Dejavu algorithm, this thesis mainly has the following improvements and innovations: detection based o

12、n control flow chart compares technology modification, can accurate positioning point code change; At modify the statements on the basis of the level section, narrowed the range of regression testing; Add new test cases to ensure the adequacy of the regression test. Regression testing method is prop

13、osed in this paper, therefore, the use cases with higher precision, more fully the characteristics of regression testing, greatly improve the efficiency and effectiveness of the regression test.Key Words：Software Testing,Regression Testing, Extend - Dejavu,Test Sectioniii浙江大学硕士学位论文 目录目录摘要IAbstractII

14、图目录III表目录IV第1章 绪论11.1 课题背景11.2 国内外研究现状及进展21.3 本文主要研究工作51.4 论文组织形式51.5 本章小结6第2章 软件测试和回归测试的策略72.1 软件测试72.1.1 软件测试的目的72.1.2 软件测试方法72.1.3 软件测试策略82.2 回归测试92.2.1 回归测试分类92.2.2 回归测试策略92.3 软件测试与回归测试比较112.4 本章小结12第3章 基于字节码控制流图的回归测试用例选择算法综述133.1 Dejavu算法以及扩展算法的介绍133.2 UT2测试实例153.2.1 测试环境153.2.2 新旧版本字节码163.2.3

15、原始Dejavu算法控制流图163.2.4 Extend-Dejavu算法控制流图173.2.5 测试结果183.3 本章小结18第4章 基于修改点控制流图的回归测试用例选择算法194.1 算法概述194.2 无效修改点判定设计194.2.1 基本概念194.2.2 设计原理与算法234.3 确定测试切片294.3.1 基本概念304.3.2 设计原理与算法324.4 UT3测试实例344.4.1 无效修改点判定测试344.4.2 确定测试切片测试364.5 本章小结39第5章 优化算法对比分析及实际应用405.1 对比分析405.1.1 单测试用例算法精度对比415.1.2 多测试用例算法精

16、度对比425.2 TD-LTE项目中自动化测试平台应用435.2.1 用例库管理445.2.2 系统运行445.2.3 OMCR-CT及DEBUGTOOL475.2.4 测试结果及分析49（一）测试报告49（二）结果分析505.3 本章小结51第6章 总结与展望52参考文献54作者简历57致谢59II浙江大学硕士学位论文 图目录图目录图2.1 软件测试一般过程图11图3.1 TD-LTE项目中旧版本方法Dispenser.dispenseO的控制流图17图4.1 删减语句导致的控制流图的变化24图4.2 广度优先对比25图4.3 深度优先对比26图4.4 N1为终结符节点，N2为普通节点的示例

17、图28图4.5 N1为普通节点，N2为终结符节点的示例图28图4.6 计算修改点的流程图29图4.7静态切片（左）与动态切片（右）30图4.8 静态切片（上）与动态切片（下）31图4.9 TD-LTE项目中equation函数的原代码（左）和修改后代码（右）35图4.10 被测单元f1的控制流图36图4.11 被测单元f修改前后的代码37图4.12 被测单元f的控制流图38图4.13 被测单元f关于节点decl_stmt_1的依赖图39图5.1配置文件存放形式44图5.2用例库管理操作界面44图5.3 TR-PC启动45图5.4 TmView操作界面45图5.5 TmView操作界面46图5.

18、6 TR-PC执行操作界面46图5.7 TR-PC执行操作界面47图5.8 OMCR-CT工具操作显示界面48图5.9板件消息显示48图5.10 OMCR-CT启动48图5.11 OMCR-CT结束48图5.12 DEBUGTOOL启动49图5.13 DEBUGTOOL结束49III浙江大学硕士学位论文 表目录表目录表2.1渐增性回归测试和改错性回归测试主要区别8表4.1 修改点有效性分析23表4.2 函数f的控制流图和源程序的对应关系35表5.1两种回归测试用例选择算法的回归测试用例选择集42表5.2 2种不同算法针对3个实例运算的运算结果对比44IV浙江大学硕士学位论文 第1章 绪论第1章

19、 绪论1.1 课题背景其实计算机在安全上的问题已经存在很久了，特别在软件层面上，软件产生的故障问题越发的频繁，随之造成的危机也经常导致严重的后果，给人们带来了很多的教训。从这些教训中我们可以总结出：软件开发过程中软件测试对最后软件成功与否意义重大。当然，随着计算机的普及，各种软件进入了人们的视野。从普通的软件到一些专业的软件，软件的应用领域非常广泛，规模也是非常庞大。现在人们面临的技术层面的难题就是如何在琳琅满目的软件当中选择符合人们要求的软件，如何在符合要求的基础上确保这些软件的质量及可靠性。软件的一些很小的差错就有可能对国家、财产、军事、航天事业以及生命等方面造成巨大的损失，我们必须极力的

20、阻止这类事件的发生。有人对美国当今的软件的现状进行了相应的研究，这些研究表明：到上个世纪末为止，美国的软件领域的从业人员已经达到了接近130万人。作为关键领域的巨头，微软每年在软件方面的销售总额在整个美国也是相当可观的。但是，虽然销售总额很高，利润却没有人们想象当中的那么高。这些损失很大成份是由软件错误造成的。降低了软件产生的错误，就可以挽回很大的损失。如何改进软件系统的质量问题已然成为取得高回报的有效手段，在安全和财产保障中，软件质量影响深远，也是国家、人身安全、军事航天事业等方面的保障。软件工程概念的提出是针对高质量和高可靠性的软件设计提供了基础。而在软件工程中的软件测试的概念由Bill

21、Hctzel在1972年首次提出。在软件开发过程中，软件测试更是重中之重，它是软件开发过程的最后一道保障环节。软件测试经过最近几十年的发展已经越来越迅速，尤其是最近几年。软件测试最重要的也是最直接的目的就是发现系统软件中的漏洞以及错误，及时通知软件开人员，避免重大损失。据统计，在美国，那些对于安全性要求较高的软件来时，软件测试所要花费的费用可能会超过40%以上。因此，软件测试已经受到越来越多的专家的重视，很多专家也对如何降低测试费用进行了探讨。在软件的整个生命周期中，软件的代码这一因素也是相当重要的。如果软件设计过程中软件的代码发生了变化，那么软件开发会带来很多的问题，所以，在软件开发之前就应

22、该把相应的需求分析做好。软件测试的时候必须注意以前已经测试过得基本模块，以便确定相应的修改是否有影响到原来的功能实现，并要确认其修改是否产生了新的问题，这种测试就是著名的回归测试。软件在开发过程中所涉及的软件代码是相当复杂的，而且代码之间都具有关联性，如果软件部分代码被改正以后相关联的代码可能就会瘫痪掉。特别容易放生在修改后产生新的错误，有数据表明这种情况发生的概率高达20%以上。回归测试自从被提出来之后就获得了广泛的应用。在基本的回归测试用例确定以后，后面即使有更改，先前确定的测试用例还是可以重用的。随着项目的不断发展，后期加入的测试用例数目越来越多，在测试人员的流动性，测试用例的运行周期的

23、冗长性等因素的影响下，对后期测试用例的控制性回越加把握不住，这些相关问题都会使得前期测试投入很大，也导致在后期测试工作中，每当有改动都要从头到尾重新测试，这不仅浪费时间也是没有必要的。软件在开发过程中一定要有相关经验的软件人员，这样软件可以尽可能的减少代码的重写，从而降低由于代码重写所带来的回归测试的成本的增加。当然，软件开发的时候最好是有一定的人员对软件测试用例库进行相关的维护以及管理，这样就会有个合理的组织、统一的管理。计算机的发展带动了许多相关学科的发展，如今全球化的迅速发展也对移动通信提出了较高的要求。随着移动通信系统的发展，我们的“空间”变得越来越小。当今移动通信系统中的最新进展就是

24、LTE，它延续了移动通信家族的技术演进，而且LTE完成了对移动通信业务的扩展。世界上第一部电话发明出来的时候人们都被惊呆了，多年以后谁会想到移动通信系统会发展的这么迅速。它不仅仅解决了人们日常生活中所用到的语音通信功能还建立了多业务空中接口。因此，LTE现在已经被各个通信公司所看重，都当作通信企业的研究中心。软件测试在软件开发工作中所占据的重要位置使得各个企业正向研发一个幼小的机制。本课题即基于上述背景，设计并实现了用于TD-LTE项目的基于图形遍历方法的回归测试用例优化算法。1.2 国内外研究现状及进展回归测试方法在软件测试当中广泛应用，它的研究包括许多方面，包括捕获回放机制以及测试环境的自

25、动化，当然还包括测试用例时所用到的选择优化技术等等3，这些在回归测试当中应用十分广泛。回归测试涉及面十分广泛，归纳起来主要包括四个方面的问题。首先，代码修改后给软件开发带来的影响如何评估；其次，修改部分的测试如何单独进行；再次，回归测试评价的结果如何进行定义；最后就是修改代码之前的用例与修改代码之后的用例如何选择、重用和修改。在回归研究当中最重要的是回归策略的研究，如何开发一个有效的策略使得以最低的成本对软件开发的测试结果做到最有效的评估这一问题已经受到越来越多的关注。回归测试在进行测试的时候有两种模式可供选择及“重测所有”和“选择部分”用例，这两种模式是比较常见的。前一种模式虽然可以将所有的

26、用例进行重测但是成本比较高，而且随着软件开发的进展，测试用例会不断增多，这样重复性的重测原来的用例不仅使成本越来越高，也会带来很大的工作量，这样就会将软件开发的时间大大的推迟。相比之下后一种模式的优势在于低成本、高效率，在软件回归测试当中人们用到的最多的还是“选择部分”这一模式。近几年随着回归测试技术的发展，相应的策略与算法也相应的增多。回归测试领域当中的著名学者Leung and Whiten曾经提出一种回归测试的方法：将测试之前原始的用例进行分类划分，然后将用例进行相应的筛选，选出其中比较重要的用例，然后将这些用例进行整理，最后将用例集合进行回归测试。这样测试结果不仅包括各个领域而且测试结

27、果也具有一定的代表性，而且随着软件的不断开发，新增的用例也不用全部加入测试用例集合。回归测试的研究主要包括四个方面：首先，选择系统的规格信息进行回归测试，在测试之前主要对系统的规格信息调查清楚后才能进行后续的工作；其次，对软件开发过程当中的代码信息进行回归测试，这主要是针对软件规格相关，代码要有一定的规格才能进行；再次，回归测试当中用到的测试用例所涉及到的约简技术，它主要包括一些驱动方面的需求；最后就是测试用例选择的优先级问题的研究，在进行回归测试之前现将测试用例的优先级进行排序，将最重要的测试用例放在测试的第一位也就是越重要的最先执行。在这里我们先进行简单的说明，在文章的后续部分我们会加以详

28、细的讨论。回归测试用例当中所用到的代码信息进行选择时一般都会用到选择算法，这里的选择算法主要分为两类，也是我们在编程过程当中经常提到的面向过程与面相对性两个方面。什么是面向过程呢？它是指将软件的各个功能模块之间的控制流程作为编程的重点，通过几个过程找出代码的修改部分来进行用例的选择。而面向对象将测试的策略当作一个对象来加以研究，它具有面向过程所不具有的类、继承、封装等几个特性。编程过程中用到的c语言可以说是面向过程的语言，而c+语言则是面向对象的语言。面向对象的这几个特征决定了其测试用例的步骤和策略上的选择不同于面向对象的测试用例。从面向过程与面向对象这两个程序特点，许多学者都提出了相应的策略

29、以此来提高回归测试的效率。国外学者Rothermel提出了面向过程的测试用例选择算法，这就是著名的基于CFG的用例选择算法。这一用例算法将程序修改前后的CFG图进行比较，然后查看不同来查找软件开发的问题所在。虽然这个算法比较实用，但是这个算法并没有考虑CFG所涉及的控制域问题。值得庆幸的是，经过这些年的发展，学者们通过对CFG的研究之后借鉴面向对象的思想，发展了面向对象的测试用例的方法，并且把这些方法应用到了测试用例当中。面向对象的测试用例的主要思想就是通过程序代码之间的依赖关系得到测试对象之间的方法序列，然后应用一定的技术将程序修改后的受到影响的测试用例加入到新的测试用例集合当中许多学者提出

30、了一种面向对象的算法，比如经常用到的“切片算法”，“切片算法”的主要思想就是先将程序进行分解，然后根据分解之后查看代码改变与未改变之间的关系，将这一结果进行分析之后选择相应的测试用例。我国学者王影在“切片算法”的基础上提出了“条件切片”技术，这种技术不仅解决了面向过程当中所没有考虑到的控制域问题，而且大大降低了回归测试的成本。我们每个人所用的电脑中都会用到防火墙，这样可以保护电脑以免受到非法操作与攻击。国外学者提出了关于在回归测试方面的防火墙的概念，主要思想就是将程序中修改过的类进行标示，构建一个新的防火墙，然后对防火墙之中的类进行相应回归测试。回归测试方法在软件测试当中广泛应用，它的研究包括

31、许多方面，包括捕获回放机制以及测试环境的自动化，当然还包括测试用例时所用到的选择优化技术等等4，这些在回归测试当中应用十分广泛。许多专家学者对回归测试进行了深入的研究工作，包括测试用例的排序问题、优先级问题等等。还有的学者将遗传算法应用到测试用例当中，其他算法还包括贪心算法、GRE算法等等，这些算法的应用使得回归测试的成本大大降低，应用范围也越来越广泛，提高了软件开发的成功率。现有的测试用例优化技术各有各的特色和适用范围，效果仅仅只是针对部分的。本文在现有回归测试的选择策略基础上，提出的改进策略能让测试过程更具系统性和规范性。1.3 本文主要研究工作本文的研究工作将着重解决C语言程序的单元自动

32、化回归测试优化问题，在对目前应用广泛的基于字节码控制流图的回归测试用例选择算法的基础上，本文设计和实现了基于修改点控制流图的回归测试用例选择算法，通过实际程序验证该算法的可行性，表明基于该策略生成的单元回归测试用例集合，能够对被测单元进行有效而高效的回归测试。本文的研究内容主要有以下几点：（1）对现有的Extend-Dejavu算法进行深入分析，并以案例的方式验证算法的有效性。但是复杂的控制流图构造流程及繁琐的收集覆盖信息操作表明该算法在现实使用中存在困难以及缺陷。（2）软件修改点检测技术的研究：本论文构造的回归测试用例集合的原则是与软件修改点相关的，因此首先需要解决的问题是如何检测出被测单元

33、的修改位置。为了将修改点检测技术更好地应用于回归测试，需要鉴别出哪些修改内容能够被判定为“有效的”修改点。举例来说，若被测代码在一条声明语句中添加了一个变量声明，这条声明语句的改变并不会直接影响测试用例执行新旧代码得到的运行结果，因此这样的修改点会被忽略，而一条赋值语句中涉及到的常量被修改，则很有可能导致相关的测试用例运行结果发生改变，因此需要纳入回归测试修改点范畴。 （3）程序切片技术的结合：程序切片39是一种程序分析和理解技术，从广义上来说，程序切片是指将一个程序中，某一功能的程序设计人员所需要的相应代码提取出来，形成一个程序子集，也可以将其看作一个规模更小的新程序。在本论文中，将重点研究

34、如何使用程序切片技术分析修改点所能影响的范围，在此范围内根据一定准则筛选测试用例或构造新的测试用例。 （4）测试分析：本章选择TD-LTE项目中代码对比基于修改点控制流图的回归测试用例选择算法及Extend-Dejavu算法，以单测试用例算法精度及多测试用例算法精度两方面证明本文设计算法的优点。并将将把TD-LTE项目中的控制面软件代码放入已在运用的自动化测试工具中测试，得出数据并对它进行分析。1.4 论文组织形式第1章 介绍课题研究背景意义，国内外研究现状和本文的主要工作。第2章 具体回归测试的相关内容，为后面回归测试用例优化算法设计的开展打下基础。第3章对目前使用广泛的Extend-Dej

35、avu算法的概念、流程进行介绍，并通过实际程序分析Extend-Dejavu算法的优缺点。第4章对本文设计的基于修改点控制流图的回归测试用例选择算法进行设计。本文从修改点的判定及确定测试切片两方面对算法进行优化，最后以实际程序的方式进行算法展示。第5章 采用对比的方式对两种算法进行分析。并对TD-LTE项目中自动化测试平台应用进行介绍。第6章 总结与展望。1.5 本章小结本章内容主要讨论了论文的研究背景以及现今国内外在此方向上研究的现状和进展，接着介绍了论文主要研究工作和目标以及组织形式。6浙江大学硕士学位论文 第2章 软件测试和回归测试的策略第2章 软件测试和回归测试的策略回归测试方法在软件

36、测试当中广泛应用，它的研究包括许多方面，包括捕获回放机制以及测试环境的自动化，当然还包括测试用例时所用到的选择优化技术等等3，这些在回归测试当中应用十分广泛。如今是信息大爆炸的时代，信息技术的发展十分迅猛，各种软件应用的范围也是越来越广泛，在软件开发过程中的问题也是越来越多。为了解决上述危机，许多专家学者们建立了“软件工程”，其目的就是为了减少软件开发过程当中所遇到的各种错误，为最终顺利的开发软件提供一个更加有效的保护机制。而软件测试则是软件工程当中的十分重要的一个环节，如果在关键测试过程当中发现软件开发中的错误就会及时停止，并将错误进行标记排除。2.1 软件测试2.1.1 软件测试的目的软件

37、测试的重要性相信人们在软件开发过程当中都已经非常清楚了，它的重要作用就是发现软件开发过程当中所出现的各种缺陷与漏洞。而这些缺陷与漏洞在软件开发的任何一个过程都可能会随时出现，如果这些缺陷与漏洞相互关联的话就会影响整个软件的开发过程。我们熟知软件测试的目的就是为了决定软件测试方向。软件开发的定义包括检验软件是否满足规定的需求或弄清预期结果与实际结果之间的差距2。其实软件测试的实际目的是为了测试软件的结果是否满足实际需求。因此，在软件开发之前，一定要将需求分析做好，这样在软件后期的开发过程中才能尽量的减小错误。在软件开发过程中一个有经验的软件开发人员会根据以前软件开发过程中所遇到的问题来进行分析，

38、尽可能地减少不必要的错误，提高软件的质量。与此同时也可以根据经验筛选出一个好的测试用例，这样会大大降低软件测试的成本。2.1.2 软件测试方法从上面的文章中我们提到了软件测试，回归测试用例当中所用到的代码信息进行选择时一般都会用到选择算法，这里的选择算法主要分为两类，也是我们在编程过程当中经常提到的面向过程与面相对性两个方面。对于软件测试所涉及到的技术从不同的角度我们会发现其方法和技术不胜枚举，可以按照不同的领域进行分类。从直观来讲，静态测试就是不运行待测程序进行检测，而动态测试则是需要运行被测程序。不过动态测试需要将实现筛选的测试用例进行输入，然后根据程序执行的结果进行判定与预期的相差有多远

39、。平时我们用的比较多的动态测试法包括黑盒测试和白盒测试。(1)黑盒测试正如它的名字一样，我们并不熟知被测试软件的具体的内部结构与功能，在测试的过程中，我们只需把所要测试的软件看成一个黑盒子，对程序的一些接口进行相应的测试。黑盒子测试关注的的输入输出信息的正确性以及信息的完整性，对于软件的内部功能以及程序的具体实现的工程并不关心。黑盒测试方法主要有等价类分析法，边界值分析，因果图法和错误推测等，主要用于软件确认测试3。(2)白盒测试与黑盒测试形成鲜明的对比，它是在已知软件的内部结构的基础上进行的软件测试方法。白盒测试主要是为了测试软件内部的程序执行的过程是否按照需求说明来加以实现。当然，白盒测试

40、要求比较严格，它要求必须软件内部结构进行详细的了解。白盒测试的主要方法有逻辑驱动，基路测试等，主要用于软件验证3。2.1.3 软件测试策略软件测试策略在实际操作当中应用的比较广泛，其软件测试策略主要集中在动态测试方面。动态测试根据程序执行的结果进行判定与预期的相差有多远，云中在其中的测试策略需要运行待测程序，这点与静态测试区分还是很明显的。在动态测试中的测试策略所应用到的方法是很多的，我们用的比较多的就是“穷举测试”，除了“穷举测试”之外其它的策略都不能保证程序没有错误遗留下来。任何事物都具有两面性，虽然穷举测试的结果很准确但是它的工作量却是很大，它不仅执行正常操作性的代码，还执行非法操作下的

41、代码，工作量巨大。因此当今亟待解决的问题就是寻找一个合适的策略来平衡工作量与成本。一般好的测试策略和方法，有以下原则：软件设计当中的软件测试等级与测试的重点需要根据程序或者代码的重要性来进行评测。在软件测试过程中测试用例选择的优先级问题已经有很多研究，在进行回归测试之前现将测试用例的优先级进行排序，将最重要的测试用例放在测试的第一位也就是越重要的最先执行。一个合适的测试策略能够让软件开发人员以尽可能少的测试用例来达到相同或者更优的结果。合适的测试策略不仅会让软件测试结果正确而且会让程序中的错误尽可能的减少，也不会因程序中隐藏的错误使得测试失败，给用户带来危险。2.2 回归测试2.2.1 回归测

42、试分类软件开发之前需要将需求用例说明说明设计，在软件开发过程中，如果需求发生了变化，软件的维护则要相应的做出变化。回归测试自从被提出来之后就获得了广泛的应用。回归测试给人们带来的影响与损失在历史上的例子还是很多的。回归测试方法在软件测试当中广泛应用，它的研究包括许多方面，包括捕获回放机制以及测试环境的自动化，当然还包括测试用例时所用到的选择优化技术等等，这些在回归测试当中应用十分广泛。回归测试涉及面十分广泛，归纳起来主要包括四个方面的问题。首先，代码修改后给软件开发带来的影响如何评估；其次，修改部分的测试如何单独进行；再次，回归测试评价的结果如何进行定义；最后就是修改代码之前的用例与修改代码之

43、后的用例如何选择、重用和修改。回归测试在进行测试的时候有两种模式可供选择及“重测所有”和“选择部分”用例，这两种模式是比较常见的。渐增性回归测试与改错型回归测试的区别还是比较明显的，前者主要是设计用例方面的改变，可以允许需求用例的增加，但是不支持程序代码的更改。与此同时，改错型回归测试不允许程序规格发生改变，可以允许程序代码发生改变，其主要区别如表2.1所示。表2.1渐增性回归测试和改错性回归测试主要区别2.2.2 回归测试策略上面我们介绍道软件测试中的策略在实际操作当中应用的比较广泛，其软件测试策略主要集中在动态测试方面。动态测试根据程序执行的结果进行判定与预期的相差有多远，云中在其中的测试

44、策略需要运行待测程序，这点与静态测试区分还是很明显的。在动态测试中的测试策略所应用到的方法是很多的，我们用的比较多的就是“穷举测试”，除了“穷举测试”之外其它的策略都不能保证程序没有错误遗留下来。任何事物都具有两面性，虽然穷举测试的结果很准确但是它的工作量却是很大，它不仅执行正常操作性的代码，还执行非法操作下的代码，工作量巨大。因此当今亟待解决的问题就是寻找一个合适的策略来平衡工作量与成本。正如软件测试策略中所描述的那样，回归测试的策略主要包括两大类：“重测所有”型回归测试策略以及“选择性”回归测试策略3。两种测试策略的区别还是比较明显的，一种是将所有的测试用例进行重测，另一种是将测试用例进行

45、有目的的选择，然后进行测试。如果程序规模不是很大的情况下后一种测试策略更加优异，但是，如果程序规模很大或者程序的规模越来越大的话前两种策略都会带来很大的工作量。这时，我们可以选择另一种策略方式来进行软件测试，我们可以设定一个基线测试用例集，每次进行测试的时候选取用例集的一个子集将程序中被修改的部分进行覆盖，这样下一次进行软件测试的时候就没必要重复性的软件测试。选取的那个子集我们经常用“再测试用例集”来表示。回归型测试策略的选取主要考虑效率与成本两个因素，在选择测试策略的过程中优先考虑这两个因素。“重测所有策略”我们比较容易理解，“选择性”回归测试根据我们选取所考虑的角度分为三种，包括；安全选择

46、策略、最小化选择策略以及随机选择策略4。首先，安全选择策略主要基于软件开发程序中所影响到的测试用例，将这些用例进行相应的选择；其次，最小化选择策略的思路就是在测试用例集当中选取最小的一个子集，保证软件开发过程当中的程序被影响的那部分至少被覆盖一次；再次，随机选择策略，这种选择策略比较具有代表性。随机性选择策略运用数学中随机性的知识，从程序最初的测试用例集中随机性的选取一些测试用例，然后测试人员根据自己以往的经验从中进行筛选。这样做的好处就是测试用例的选取的测试用例既没有盲目性又具有一定的代表性，而且最为重要的测试用例都会被运行，那些优先级别低的或者非关键的测试用例都被跳过了。“选择性”回归测试

47、策略在回归测试中广泛应用，它的评价指标也有多个，包括：概括性、精确性以及通用性。上面介绍的三种回归测试策略根据软件开发的具体情况应用也不一样。虽然“重测所有”这一策略代价比较大，但是在软件开发过程中如果程序代码改动比较大的话还是用这种策略比较明智。而“随机性选择策略”很多时候都要视情况而定，大多数情况下都要看软件测试人员经验如何，一个有丰富经验的软件测试人员用“随机性选择策略”还是很有效的。至于第二种选择策略最小化选择策略，它花费的成本最低、代价最小，但是同样的，在软件测试当中发现的问题可能不是很全面。2.3 软件测试与回归测试比较2.1节与2.2节我们分别讲了软件测试与回归测试，并分别介绍了

48、软件测试策略与回归测试策略。经过上面的了解我们可以发现回归测试是软件测试一个更加深入的测试，修补软件测试所发现的错误。图2.1给出了软件测试的一般过程。图2.1 软件测试一般过程图从图2.1中我们可以看出软件测试是软件开发过程中的第一道测试，如果软件测试成功没有发现软件的错误的话就会退出测试。相反，如果软件测试当中发现错误或者比较实际与预期不符的话就需要进行回归测试。回归测试是在软件测试的基础上进行的，它将软件测试当中发现的错误进行修改，然后添加一些新的测试用例或者减少一些没必要的用例，然后进行回归测试。当然，回归测试的时间并没有一个固定值，软件开发过程中如果遇到的问题很多的话可能会需要很多次

49、回归测试。有时候回归测试的时间可能会占用整个软件开发过程的一半以上的时间。由此，可以看出软件测试的重要性。2.4 本章小结本章介绍了软件测试和回归测试的一般策略，简单的介绍了软件测试和回归测试的基本概念和流程。表达了软件测试的重要性，也间接说明了回归测试在软件测试中的重要位置。18浙江大学硕士学位论文 第3章 基于字节码控制流图的回归测试用例选择算法综述第3章 基于字节码控制流图的回归测试用例选择算法综述3.1 Dejavu算法以及扩展算法的介绍Extend-Dejavu算法是目前使用广泛的回归测试用例选择算法，但是该算法需要利用元数据来构造控制流图和收集覆盖信息，因此在实际使用中难度很大。本

50、文借鉴Extend-Dejavu算法精华，开发了基于修改点控制流图的回归测试用例选择算法，能够对C语言单元函数进行逻辑结构上的比较。从而减少测试用例，提高测试效率。算法主要包括以下内容：根据控制流图对比技术检测出有效修改点；根据语句节点间的数据依赖和控制依赖关系构建基于修改点的软件切片；以切片得到的节点集合作为目标覆盖集合，从基线测试用例库选取相关测试用例构造回归用例选择子集T0；运行T0中测试用例；基于覆盖情况分析是否存在未覆盖的目标节点，若存在则构造回归用例新增子集T1；最后合并T0和T1得到回归测试用例集合。Dejavu算法是Rothermel等人于1991年提出了控制流图的基础上的源代

51、码回归测试用例选择算法。这种算法是在新老版本的程序的源代码的基础上构建相应的控制流图（简称CFG）。然后比较旧的和新的版本的控制流图，计算出软件开发过程中变化的程序。然后集成回归测试用例，根据旧版本控制流图运行覆盖掉的信息，而那些没有发生覆盖的程序就没必要接着运行下去了。 字节码的控制流图的回归测试用例选择算法的通用程度是很强的，它不仅可以处理与java虚拟机平台并支持多种编程语言，而且给以组件的开发范式的回归测试用例为基础的选择技术带来了新的挑战。然而，基于控制流图的字节码回归测试用例选择算法需要构建元数据来构建控制流图，并收集覆盖信息。但是，这迫使开发人员提供一个附加的元数据的方法，虽然理

52、论上看着很简单，但是现实中这是很难实现的。 目前应用比较广泛的是由Rock于2000年提出的Extend-Dejavu算法，该算法在一定程度上对Dejavu算法做出了改进，但是仍然难以弥补算法需要强迫构件开发者额外提供元数据的缺陷。图3.1 Dejavu RTS algorithm and Extend-Dejavu RTS algorithm流程图图3.1中左图表示的Rothermel提出的Dejavu回归测试用例选择算法的流程图。这种算法是在新老版本的程序的源代码的基础上构建相应的控制流图。然后比较旧的和新的版本的控制流图，计算出软件开发过程中变化的程序。然后集成回归测试用例，根据旧版本控

53、制流图运行覆盖掉的信息，而那些没有发生覆盖的程序就没必要接着运行下去了。其中左图当中的C(P,T)指的就是回归测试当中所覆盖掉的信息，如果进行下一次回归测试的时候就需要加入一条以上的测试用例，然后软件测试人员从这些测试用例当中进行select。图3.1中右图表示的是扩展的Dejavu回归测试用例选择算法的流程图。它与大部分都是相似的，这里我们就不加以详细介绍了。算法扩展DEJAVU是基于控制流图的字节码回归测试用例选择算法。其基本思想是利用新老版本的C程序的字节码直接构造相应的控制流图，通过控制流图的新老版本的比较分析，计算出的危险变化的程序，代表集之间的新老版本的程序变化的边缘。最后全面的回

54、归测试套件T，和回归测试套件旧版本的P R的测试覆盖率信息收集，当C（P，T），选择全险至少一侧的回归测试用例添加回归测试使用病例选择T选择。Extend-Dejavu算法是目前使用广泛的回归测试用例选择算法，但是该算法需要利用元数据来构造控制流图和收集覆盖信息，因此在实际使用中难度很大。本文借鉴Extend-Dejavu算法精华，开发了基于修改点控制流图的回归测试用例选择算法，能够对C语言单元函数进行逻辑结构上的比较。从而减少测试用例，提高测试效率。算法主要包括以下内容：根据控制流图对比技术检测出有效修改点；根据语句节点间的数据依赖和控制依赖关系构建基于修改点的软件切片；以切片得到的节点集合

55、作为目标覆盖集合，从基线测试用例库选取相关测试用例构造回归用例选择子集T0；运行T0中测试用例；基于覆盖情况分析是否存在未覆盖的目标节点，若存在则构造回归用例新增子集T1；最后合并T0和T1得到回归测试用例集合。递归的方法计算方案比较新老版本之间的控制流图的变化。输入法是旧版本和新版本的基本块的控制流图。8表示控制流图G的较旧版本的基本块，而8表示在控制流图G的新版本基本块。方法的输出是新老版本之间的控制流图的变化。运算过程如下。（1） 在基本块8被标记为B访问后，就意味着是成对的旧版本和新版本的控制流图是能够配对的。（2） 将每个基本块C的B序列，在新版本中的控制流图G搜索，以发现是否有一个

56、基本块C能够与其匹配。这意味着基本块B和C不完全匹配。而（B，C）是一个危险的侧面，它标志着新老版本之间的控制流是否有所变更。如果变化了，那么Lequivalent（C，C）返回真，这意味着，基本块C和C比赛正是新老版本的基本块没有改变，程序继续递归。3.2 UT2测试实例TD-LTE项目是某企业目前对eNB公网及专网的研发项目，目前公司正在紧张的进行研发工作。因此本课题是基于以上需求来开启的，当前基站的多个项目，以及各种版本的专网项目逐渐进入系统集成测试阶段，这样软件开发与测试的任务艰巨，时间短。而自动化测试却能解决这个问题。自动化测试系统包括什么呢，它主要包括：自动测试系统软件的基站CP（

57、控制面）、平面GRM（全球资源管理）、RCP（遥控飞机无线电控制飞机）模块设计的代码等等。下面我们展开详细的讨论。3.2.1 测试环境软件测试的环境要求一般是比较严格的，国外著名学者Orso提出了一种测试的算法，这种测试用例的算法的举出是元数据，这点是比较特殊的。本章使用相同的实例程序和回归用例集，用于该算法。一般情况下，该案例软件测试的硬件配置如中央处理器是英特尔奔腾双核E5200 CPU。内存2GB，硬盘320GB，主板是技嘉EP31-DS3L。该软件测试的操作系统是微软的Windows Vista。测试程序和认证算法采用C高级编程语言开发，使用的开发工具是Eclipse，版本号为3.7。

58、 C运行环境JRE版本号为C（TM）SE运行时环境（build1.6.0-26-B03）。回归测试用例集使用C测试框架JUnit的4.0。3.2.2 新旧版本字节码UT2是代码级测试，测试对象原则上应为各个代码。UT2过程中，测试用例应针对被测对象接口函数来设计。UT2不像其它的测试，它关心的重点是功能测试。因此，软件测试用例在设计的时候就应该注意到，应该把软件开发过程中遇到的对象尽可能地进行涵盖。在这里TD-LTE项目是以R3.0的版本UPBEAR UT2模块测试为例。而UPBEAR则是位于其中的子模块的用户面GTPU配置的实际的管理者。模块实现GTPU与RCP模块配置的接口功能。配置参数根

59、据UPBEAR模块的消息发送到目标函数板UP板。前面的模块我们已经介绍了，与模块相关的过程包括UPBEAR配置，重排UPBEAR，释放UPBEAR，UE状态指示和GTPU错误指示这几个流程，每道工序都分为正常和不正常的流程，而且他们分别用用例定义。对于每个用例中调用的UPBEAR模块将会调用代码中所用到的相应的函数，根据使用情况下设置的参数，采取正常或不正常的进程。此外通过比较每个消息参数的功能以及其他模块的功能，返回的成功或失败的消息，然后进行各种处理，以便确定流程是否是正常的。测试过程中需要子一个特定的文件夹创建一个测试项目（这里我们是在public#301文件夹中建立的）。程序在编译过程

60、中所生成的dll与lib文件都要放到这个文件夹当中，当我们编译完测试程序后会生成一个测试报告，根据测试报告进行测试用例的选取等工作。并且生成的DLL和LIB文件到文件夹中。试验结束后，根据测试程序，并生成测试报告。3.2.3 原始Dejavu算法控制流图基于表3.1左边所示的旧版本的方法Dispenser.dispenseO的字节码，再经过原始Dejavu算法一系列运算之后，可以构造出对应的控制流图，用图3.2的表示。图3.2 TD-LTE项目中旧版本方法Dispenser.dispenseO的控制流图本文主要选择TD-LTE项目中代码对比基于修改点控制流图的回归测试用例选择算法及Extend

61、-Dejavu算法，以单测试用例算法精度及多测试用例算法精度两方面证明本文设计算法的优点。并将将把TD-LTE项目中的控制面软件代码放入已开发好自动测试系统进行测试，得出测试结果数据，并对结果进行分析。而图3.3则是TD-LTE项目中的一个旧版本的控制流图。3.2.4 Extend-Dejavu算法控制流图算法扩展DEJAVU是基于控制流图的字节码回归测试用例选择算法。其基本思想是利用新老版本的C程序的字节码直接构造相应的控制流图，通过控制流图的新老版本的比较分析，计算出的危险变化的程序，代表集之间的新老版本的程序变化的边缘。最后全面的回归测试套件T，和回归测试套件旧版本的P R的测试覆盖率信

62、息收集，当C（P，T），选择全险至少一侧的回归测试用例添加T选择。字节码的控制流图不仅可以处理与java虚拟机平台并支持多种编程语言，而且给以组件的开发范式的回归测试用例为基础的选择技术带来了新的挑战。然而，基于控制流图的字节码回归测试用例选择算法需要构建元数据来构建控制流图，并收集覆盖信息。但是，这迫使开发人员提供一个附加的元数据的方法，虽然理论上看着很简单，但是现实中这是很难实现的。从表3.1中我们可以看出，新旧版本的字节码指令序列只有一处是不同的，因此它们的控制流程图也是相似的，这里我们就不再具体讨论了，下文直接给出运算结果。3.2.5 测试结果算法Extend-Dejavu比较分析方法

63、Dispenser.dispense（）新老版本的控制流图，我们可以计算出控制流图的新老版本改变了危险的边缘集DangerousEdges= E14，其中E14=（B8，B10，YES）。算法扩展Extend-Dejavu选择全部覆盖至少一侧的回归测试用例，即如果C(P,T)DangerousEdges != null,则回归测试用例t必须被加入回归测试用例选择集Tselect。由于DangerousEdges = E14，即危险的边的集合中只有唯一的有向边E14。因此，必须选择所涵盖的边缘E14测试用例。全面覆盖信息，只有T5，T6，T9，T11，T12，T13这六个回归测试用例覆盖了危险的边缘E14，最终计算出的回归测试用例选择集为