计  算  机  学  报  2019 年 regression  testing  is  split  into  two  processes,  and  two  approaches  are  put  forward  respectively:  agile  test  case prioritization and agile regression test selection. Agile test case prioritization follows the idea of history-based test case prioritization and combines requirement, fault feedback, and test history to form a novel test case prioritization technique with memory. Agile regression test selection, designed by combining fault information and requirement correlation  information,  selects  the  test  cases  that  detected  faults  in  previous  test  versions  and  the  test  cases interacting with the new tests to form a test subset. It can not only verify whether the functions that have been wrong in  the  previous  testing  are  correct,  but  also  check  whether  the  addition  of  new  functions  affects  the  stability  of delivered functions. Secondly, these two methods are combined to design a regression testing optimization model and an agile regression testing optimization algorithm. The failure-tag is assigned to each test case of the test subset to dynamically adjust the number of test cases in the subset. Finally, the effectiveness of the agile regression testing optimization algorithm is analyzed by experiments on different-scale experimental objects. The representatives of test case prioritization techniques, regression test selection techniques, and their hybrid techniques are compared with  our  agile  regression  testing  optimization  algorithm.  Experimental  results  show  that  the  proposed  agile regression testing optimization technique can achieve the higher fault detection rate in a shorter time with higher safety  compared  with  existing  test  prioritization,  test  selection  and  hybrid  methods.  According  to  the  statistical analysis  results  of  t  test,  our  agile  regression  testing  optimization  method  is  superior  to  the  other  five  test  case prioritization methods in terms of fault detection rate, because t values are all greater than 0 and p values are all less than 0.05. In addition, in terms of the composite index of fault detection rate, percentage of efficiency-cost, reduction ratio of running time, and percentage of detecting faults, our agile regression testing optimization method is superior to the others.  Key words  regression  testing;  test  case  prioritization;  regression  test  selection;  agile  development;  software testing 1    前言 敏捷开发是一种快速迭代的开发模式，是一个可持续集成开发过程. 在敏捷开发环境中，一次回归测试会话是指从上一版本发布开始，直至下一版本测试完成并发布的一个周期.从软件需求功能的角度可将一次回归测试会话分割为旧版本已发布功能的测试和新版本新增功能的测试.由于新功能的添加，新版本的测试会产生新的测试用例.测试者需要利用全部新测试用例去测试软件新功能，保证新功能的正确性、可靠性和稳定性.本文将这类测试命名为“新测试”. 旧版本功能的测试是指对已交付的功能进行维护测试，旨在保证软件的稳定，不受新增功能的影响.由于每个新版本都会产生新的测试用例，当版本更迭增长时，测试用例集规模逐渐庞大，测试者需要在有限时间内高效地利用这些测试用例，以期达到最大的测试效率.这里称这类测试为“旧测试”.  在敏捷开发环境中，测试者既要保证新功能正确，又要保证已交付功能遇到新功能集成时可正常运行，所需开销提升.管理者希望减少测试运行时间，降低测试成本，但要保证高质量测试效率，于是测试达到一个瓶颈.有调研分析[1]，成熟的组织管理、合理的测试理念以及测试基建的高投资等会从策略上影响回归测试的效果；测试研究方法会在操作上影响回归测试的结果.早期有学者提出一些优化方法，在不考虑新功能加入的情况下，对测试用例进行优先排序或者选择，以提高测试效率.测试用例优先排序[2](Test Case Prioritization，  TCP)是根据某些预设规则将待执行的测试用例重新排序，旨在最快地揭露出更多错误.回归测试选择[3](Regression Test  Selection，RTS)是从测试用例集中挑选一部分作为子集去执行，确保软件修改没有引入新的错误.这些排序或选择方法对于瀑布式开发模型的一次性交付软件具有较好的测试效率.但对于频繁交付新版本的敏捷开发环境来说，传统 TCP 或 RTS 技术没有考虑处理新测试用例的排序和选择及新旧测试用例叠加的情况.另外，Petschenik[4]曾讨论过这样一个现象，要想有效地组织一个测试过程，所需资源必须达到 15%以上.Jussi 等人[5]也发现，资源的可用性达到 60%-70%时，说明使用了测试用例优先排序技术.也就是说，排序技术可提高资源的利用率，尤其在敏捷开发中时间和资源有限的情况下，测试用例优先排序技术是必要的. 本文主要贡献是：(1)针对敏捷开发环境的“新计算机学报 作者名等：论文题目  3 测试”，提出敏捷测试用例优先排序方法.该方法将需求、错误反馈及历史优先级结合，形成一种新型的基于历史的优先排序技术；(2)针对  “旧测试”，提出敏捷回归测试选择方法.该方法选择已发布版本的失效测试用例和交互测试用例作为子集，并为每一个测试用例赋予一个失效标签以动态调整子集规模；(3)将敏捷测试用例优先排序和敏捷回归测试选择结合，设计适用于敏捷开发环境的回归测试优化模型及优化算法；(4)运用 Google 的开源数据集 Google Shared Dataset of Test Suite Results[6]和一个实际工业项目 ChipTest 进行评估分析. 本文第 2 节将介绍回归测试优化领域的背景知识及相关研究.第 3 节重点描述我们提出的敏捷开发环境中的回归测试的优化技术.第 4 节设计具体实验并分析实验结果.第 5 节是结论与展望. 2  背景及相关研究 回归测试[3].已知 P 为一程序,�′为 P 的修改版本,T 为 P 的一组测试用例集.回归测试过程如下: (1)  选择�′ ⊆ � ,并用�′去测试修改版本�′以确保�′在�′上的正确性； (2)  为�′的新功能创建新的测试用例集�′′,并用�′′测试�′以确保�′在�′′上的正确性； (3)  从 T, �′, �′′中为�′创建新的测试用例集�′′′用于执行测试. 回归测试重复利用旧的测试用例集测试新版本�′,旨在验证�′的正确性.如果新功能迭代添加,测试集会随回归测试会话数的增加逐渐庞大,重复利用全部测试用例开销巨大.据统计[7],回归测试占整个测试过程的 80%,在软件维护过程中占到50%[8].因此,一些学者研究如何对测试用例进行优先排序[9-12]或选择部分测试用例[13-16]进行测试，以提高测试效率.近年来，软件演化中如何对测试用例集进行有效扩增[17-19]也成为回归测试的研究热点. 2.1   测试用例优先排序 测试用例优先排序问题[2]的定义为： 给定一组测试集 T，T 的全排列 PT 以及应用于每一个排列的从 PT 到实数的一个函数 f，f：PT-R.找 出 �′ ∈ �� ， 使 得 (∀�′′)(�′′∈ ��)(�′′≠�′)[�(�′) ≥ �(�′′)]. TCP 寻找满足测试准则的最优排序，以提高错误检测率.唯一不足的地方是它需利用全部的测试用例，测试集基数大，花费时间较长. Rothermel 和 Elbaum 团队[20,21]最早研究细粒度代码级 TCP 技术.这类方法效果显著，但开销较大.后来他们[9]又分析程序实体粒度对排序的影响，发现粒度越大，开销越小，但排序效果会降低.Just 等人[22]从变异分析出发，研究程序代码的冗余变异对测试效率的影响.Zhang 等人[23]结合测试约减与排序技术实现提高符号执行的效率.此外，基于重构方法是利用一组重构故障模型重新排序测试序列[24].代码级 TCP 技术属白盒测试，执行时必须拿到源代码，开销昂贵.黑盒测试不需要源代码及结构化信息，操作相对简单.有数据[25]显示，白盒测试和黑盒测试之间的错误揭露平均百分比值差异仅为 2%到4%，且仅在执行 56%到 60%的测试用例时白盒测试效果较好.近年来，研究者逐渐将研究重点转移到黑盒测试.Sihan 等人[26]对比五种 TCP 算法，指出在重叠率适中的情况下，Additional 贪心算法和 2-优化对贪心算法都达到较好的效果.Srikanth 等人[11]提出 需 求 优 先 排 序 测 试 算 法 (Prioritization  of Requirements for Test，  PORT)，以数值驱动的方式排序测试用例.Kim[10]利用回归测试产生的历史数据对测试用例进行排序，但对有新增测试的情况效果不明显，因为赋予新增测试用例的执行概率与从未发现错误的测试用例执行概率相等.Garg 和Datta[27]在 web 应用方面针对已修改功能提出新的TCP 技术.Arafeen 和 Do[28]提出一种基于需求聚类的 TCP 方法.有学者从信息检索的角度出发提出一种名叫 REPIR 的回归测试有效排序方法  [29].Wang等人[30]从资源感知出发，通过修改适应度函数，提出基于多目标优化的面向工业环境的 TCP 方法.Tyagi 等人[31]对于多目标的TCP 问题采用多目标粒子群(MOPSO)算法进行测试选择及排序.随后，他们[32]又提出考虑故障检测率、故障检测百分比和风险识别能力三方面因素的多目标 TCP 方法.张娜等人[33]引入关注需求覆盖率、基于需求测试用例重要度和测试用例失效率这三个因素共同确定一个基于需求的 TCP 问题. Ray 等人[34]假定测试用例的优先级就是其覆盖组件的优先级的总和，使用遗传算法解决多目标 TCP 问题.Lu 等人[35]针对现有传统TCP 技术进行对比实验，得出：新增测试将显著影响测试效率，使得传统技术效果甚微，仅源代码的更改对测试效果没什么影响；所有对比技术中，additional 排序技术和基于搜索的排序技术效果最好. Spieker 等人[36]利用强化学习[37]设计适应于可执行集成环境的一种自动 TCP 技术. 计算机学报 计  算  机  学  报  2019 年 2.2   回归测试选择 给定程序 P 及 P 的测试集 T，回归测试选择[3,38]为 P 的修改版本�′选择子集�′ ⊆ �，使其测试�′. RTS 技术重点选择能测试修改部分及与受修改影响的软件部分相关的测试用例.RTS 减少了测试执行时间，但该技术存在不安全因素，当选择策略漏选了可发现错误的测试用例时，其测试效果将下降.这个缺点 TCP 技术可以弥补. RTS 的研究相对于 TCP 较早.Rothermel  和 Harrold 在文献[3]中给出 RTS 的形式化定义，并详细分析几组 RTS 技术.Yoo 等人[13]对回归测试优化中的约减、选择、排序进行概况总结，详细地描述各个方法的区别及优缺点.Daniel 等人[39]在一个实际工业系统上进行实验，分析基于覆盖的回归测试选择、约减和排序的特点.王克朝等人[40]提出面向有效错误定位的测试用例优选方法.吴川等人[41]研究基于分支覆盖的回归测试路径选择问题.基于文件依赖的测试选择技术[42]是选择新版本中修改文件所依赖的测试用例作为子集，虽比传统 RTS 选择更多测试用例，增加了执行时间，但降低了整体端到端时间，且提高了安全性.RTS 已存在多种方法适用于不同测试场景，但经验发现，目前难以存在一种RTS 技术普遍优于其他技术[14,43]. 2.3   排序与选择结合 一些学者将排序和选择结合提出新的混合方法.Bharti 和 Shweta[44]提出一种基于蚁群优化的测试用例选择与排序的方法.Ruchika 和 Arvinder 等人[45]提出一种回归测试选择与优化技术.根据修改程序的覆盖率对测试集 T 进行优先排序，选择覆盖所有修改程序的测试用例作为子集�′，执行�′.郑锦勤和牟永敏[46]根据函数调用路径与测试用例的映射关系选出回归测试子集，根据绝对贡献度、缺陷检测能力及缺陷影响度对测试子集进行优先级排序，最后对优先排序结果再次选择，确定最小的测试集. 3  敏捷开发环境中回归测试优化技术 敏捷开发的一个回归测试过程既包括对新增功能的“新测试”，又包括对已交付功能的“旧测试”.图 1 为敏捷开发环境回归优化的整体框架图. 图 1 中，首先，将回归测试依据前言的划分思想分为“新测试”和“旧测试”，见上方矩形框所示.其次，中间的三个圆角矩形为本节技术的设计重点.对“新测试”，结合敏捷开发中迭代更新多历史数据多的特点，将需求信息、错误信息和历史信息三者结合设计敏捷测试用例优先排序技术(Agile  Test case Prioritization，A-TCP)；对“旧测试”，秉承精简执行测试集的思想，结合错误信息和需求关联信息设计敏捷回归测试选择技术(Agile  Regression Test Selection，A-RTS)；将 A-TCP 和 A-RTS 结合，设 计 回 归 测 试 优 化 模 型 (Regression  Test Optimization Model，RTOM)，最终输出待执行的测试序列，如图 1 下方的输出文档。最后，执行有序的测试用例，本次优化完成。 敏捷开发环境中的回归测试新测试 旧测试测试用例优先排序技术 回归测试选择技术回归测试优化模型待执行测试序列执行需求错误历史错误需求关联 图 1   敏捷开发环境中的回归优化整体框架图 3.1   “新测试”中的测试用例优先排序 由于敏捷开发过程中，每一次版本开发都是细分为不同阶段迭代式开发，所以测试也为逐步集成测试.首先引入“阶段”[47]的概念. 定义 1 测试阶段 ST. 假设软件版本交付之前分为 �(� ≥ 1) 个开发阶段,那么测试阶段相应的定义为�� (1 ≤ � ≤ �).每个测试阶段会产生测试用例集��= {�1,�2, ⋯ , ��}，���对应���，为第 i 个测试阶段新增的测试用例集，�(� = 1 … �)为测试用例.所有测试阶段的��组成全体测试用例集组� ={��1, ��2, ⋯ ���}，表示本次版本所有新增测试用例集的集合. 给出 A-TCP 规则.对于有 n 个测试阶段的“新测试”，每进入一个新的测试阶段，其相应的当前阶段测试用例集��整体放于待执行测试序列�′的首位.也就是说，先对测试阶段排序，新阶段的测试用例集赋予最高优先级；然后再进行阶段内测试用例排序. 借助图 2 解释 A-TCP.假设“新测试”过程共有5 个测试阶段，前 4 个阶段已经测试完成，当前为计算机学报———— 本课题得到国家自然科学基金  (No. 61572306)资助.王晓琳(通信作者)，女，1989年生，博士研究生，主要研究领域为测试用例优先排序、回归测试和软件测试.E-mail: wangxiaolin@shu.edu.cn.  曾红卫，男，1966年生，博士，研究员，中国计算机学会(CCF)会员,主要研究领域为形式化方法、形式化验证和软件测试.E-mail: zenghongwei@shu.edu.cn.  林玮玮，女，1981年生，博士研究生，,主要研究领域为形式化方法和软件测试.E-mail: newstart@shu.edu.cn. 敏捷开发环境中的回归测试优化技术*  王晓琳 1),2)   曾红卫 1)   林玮玮 1) 1)(上海大学  计算机工程与科学学院,  上海  200444)  2)(上海市计算机软件评测重点实验室,  上海  201112) 摘  要  版本频繁交付、功能不断新增或修改、测试用例不断增多是敏捷开发环境的特点.  回归测试是软件测试的一个重要组成部分，它在敏捷开发环境中更应基于环境特点进行设计.  但是，传统的回归测试优化技术（测试用例优先排序或回归测试选择等）各有其优缺点，且没有考虑敏捷开发环境对测试效率的影响.  测试用例优先排序技术利用设计规则对所有测试用例进行排序，以提高错误检测率，但测试集基数大，花费时间长.  回归测试选择技术选择部分测试用例执行，减少了测试执行时间，但存在不安全因素.  为了解决这个问题，本文提出新的敏捷开发环境中的回归测试优化技术.  首先，将回归测试拆分成两个过程，提出在这两个过程中的测试方法：敏捷测试用例优先排序和敏捷回归测试选择.  敏捷测试用例优先排序方法利用基于历史排序的思想，将需求、错误反馈及历史信息三者结合，形成一个具有记忆的优先排序技术.  敏捷回归测试选择方法结合错误信息和需求关联信息进行设计，选择以往版本中发现错误的测试用例及与新增测试有交互的测试用例作为测试子集，既检验曾经出错的功能是否正确，又检验新增功能加入是否影响已交付功能的稳定.  其次，将敏捷排序和敏捷选择方法结合，设计回归测试优化模型，提出优化算法.  为测试子集中的每一个测试用例设置一个失效标签以动态调整子集规模.  最后，通过在不同规模的实验对象上进行实验，分析优化算法的有效性.  实验结果表明，与现有的测试排序和测试选择及其混合方法相比，敏捷开发环境中的回归测试优化技术即可达到高错误检测率又可减少待执行测试用例数量同时保证较高的安全性.  从统计分析 t 检验结果看，我们的方法在纠错速率上优于其他五种测试排序方法，因为 t 值均大于 0 且 p 值均小于 0.05;  从纠错速率、效率成果百分比、运行时间缩减率及揭露错误百分比这四方面的综合指数看，我们的方法最佳. 关键词  回归测试；测试用例优先排序；回归测试选择；敏捷开发；软件测试 中图法分类号  TP311 Techniques for Regression Testing in Agile Development Environment WANG Xiao-Lin1),2)   ZENG Hong-Wei1)   LIN Wei-Wei1)   1)(School of Computer Engineering and Science, Shanghai University, Shanghai 200444)  2)(Shanghai Key Laboratory of Computer Software Evaluating & Testing, Shanghai 201112) Abstract  The  frequent  delivery  of  new  versions,  the  frequent  addition  or  modification  of  functions,  and  the increasing number of test cases are the characteristics of agile development environment. Regression testing, as an important  part  of  software  testing,  should  be  designed  based  on  these  characteristics  in  agile  development environment.  However,  most  of  traditional  regression  testing  optimization  techniques  (test  case  prioritization  or regression test selection, etc.) have their own advantages and disadvantages. And, they do not take into account the impact of environment on test efficiency. Test case prioritization sorts all of test cases by using specific rules to improve the rate of fault detection, but it takes a long time to perform because its test set has a large cardinality. Regression test selection selects part of available test cases which seems to be more effective in execution to reduce the test execution time, but it may be unsafe because some test cases that can detect faults may be missed. To address this  problem,  this  paper  proposes  new  regression  testing  techniques  for  agile  development  environment.  Firstly, 计算机学报 作者名等：论文题目  5 第 5 阶段.右上角的虚框矩形为第 5 测试阶段新产生的测试用例集.根据 A-TCP 规则应将其优先级设为最高级 1 并置于待执行的测试序列首位，如图 2斜线框矩形.其余前几阶段产生的测试用例集赋次优先级 2，并排列在 1 级之后.对于 1 级测试用例集 ， 采 用 基 于 需 求 的 测 试 用 例 初 始 化 方 法(��������������������������)对新产生的测试用例进行排序；对于 2 级测试用例集，采用基于历史的动态 TCP 方法(�������������������)进行排序.最后输出排好序的新执行序列�′. 2 2 2 2 11已完成阶段的测试用例集新阶段的测试用例集执行方向 图 2   “新测试”中的测试用例执行序列 3.1.1   基于需求的测试用例初始化 基于需求的测试用例初始化具体思想如下. 1). 对 每 一 个 需 求 进 行 重 要 性 计 算 ， 用IV(Importance Value)代表需求的优先级. 需求 r 重要性��(�)的计算等式为： ��(�) = �1∗ ��_��(�) + �2∗ ��_��(�).           (1) ��(�)由两部分组成：一个是客户分配的需求重要性值��_��(�)；另一个开发者分配的需求重要性值��_��(�).二者均为五个等级，可采用线性赋值，如 n，(� ∈ {1,2,3,4,5})，也可采用非线性赋值，如�，(� ∈ �, � ∈ {1,2,3,4,5}).最终，二者加权平均，得到一个需求的优先级. �(�1, �2)为权值，总和为1，可根据实际情况进行分配.如未特别指定哪个因素的特定权值时，默认均等权值，即�1= �2= 0.5.本文采取均等权值计算. 2). 构造需求 - 测试用例关系矩阵 . 假设 � ={�1, �2, ⋯ ��}为需求集， �� = {�1,�2, ⋯ ��}为测试用例集.对于每一个需求，至少有一个测试用例覆盖它；对于每一个测试用例，则有 1 或多个需求与之对应.算法 1 为计算 R-T 关系矩阵.矩阵的列为需求，行为测试用例.第 i 行第 j 列表示�所覆盖的��的优先级，用��(�, ��)表示，其值由��的需求优先级��(��)赋予.当��(�, ��)大于 0，表示��覆盖��，即��与��有关联关系；为 0 表示�不覆盖��，即��与��没有关系.R-T 矩阵构造完成后，可获得两点内容：一是测试用例覆盖需求的个数；二是测试用例覆盖需求的重要性. 算法 1  计算关系矩阵 R-T 1. FOR EACH  �∈ ��,  ��∈ �    2.     IF (�  覆盖  rj  ) THEN    3.     IV(ti, rj) = IV(rj);     4.    ELSE   IV(ti, rj) = 0;    5.    ENDIF 6. ENDFOR 3).计算测试用例的优先级.已知 t 覆盖的需求个数为 m，令��(�)为测试用例 t 的优先级： ��(�) = ∑ ��(�, �)��=1                          (2) 一个测试用例的优先级即为其覆盖的所有需求的优先级之和.当每个需求的优先级均等，即不考虑需求的优先等级时，��(�, �) = 1，等式(2)简化为基于需求覆盖数的测试用例优先级赋值等式： ��(�) = {∑ (1)        � > 1�=11                      � = 1,                    (3) 其中 m 为 t 覆盖的需求个数. 根据��(�)大小排序即可得到初始状态下测试用例的优先排序. 3.1.2   基于历史的动态测试用例优先排序 基于历史的动态 TCP [48]具体思想如下. 1).首先根据每次回归测试的错误揭露情况动态调整需求优先级. r1r2r3r4r5t1t2t3t4f1f2f3f4f5f6 图 3   需求、测试用例和错误的三元关系图 对于每一个测试用例每次揭露的错误，可根据R-T 关系映射得到 R-T-F 三元关系，如图 3.图 3 中，有 5 个需求(�1− �5)，4 个测试用例(�1− �4)，6 个错误(�1− �6).如果测试用例 t 与需求 r 是一对一关系，这时需求 r 与错误 f 的间接关系可以明确得到，如图 3 的�2、�3和�4.如果 t 和 r 是一对多关系，这时需要深入分析错误并在三元关系中明确指明 r 和 f的关系，如图 3 中�1和�2到�1的虚线箭头. 得到 R-T-F 三元关系后，根据相邻两次测试揭计算机学报 计  算  机  学  报  2019 年 露错误个数的差值 Dvalue_fault 对每个需求进行优先级调整，等式如下. {������_�����  = �����−1(��, ��) −������−2(��, ��)��(��, ��) = ���−1(��, ��) + ������_�����      (4) 其中�����−1(��, ��)为前一次回归测试中测试用例�覆盖的��对应的揭露错误的个数. ���(��, ��)即为�在当前第 k 次回归测试中的优先级值. 例如，假设有 5 个需求，4 个测试用例.第一轮回归测试的错误揭露结果如图 3 所示，第一轮需求初始化后的 IV 值如表 1 所示，调整后的需求 IV 值在表 1 中展示. 表 1   调整需求优先级   IV1  Dvalue_fault  IV2 r1  3  2  5 r2  3  0  3 r3  2  1  3 r4  1  1  2 r5  4  2  6 2).根据调整后的需求优先级，利用等式(2)重新计算每个测试用例的 RP. 根据表 1 的结果，可以计算出第二轮回归测试中每个测试用例的 RP 值，如表 2. 表 2   第二轮回归测试中测试用例的基于需求优先级以及基于历史优先概率（σ = 0.8）   RP1  RP2  P2 t1  6  8  0.4291 t2  2  3  0.1571 t3  1  2  0.0996 t4  4  6  0.3134 3).利用 RP 和以往历史数据对所有测试用例重新排序.每个测试用例的优先执行概率由其当前基于需求的优先级和历史数据的长期影响计算获得，计算等式如下. { P1= NRP1                                                                              Pk= σNRPk+ (1-σ)Pk-1        0 ≤ σ ≤ 1 , k ≥ 1     (5) NRP 为 RP 的标准化形式，每个 t 的 NRP 用其占所有 t 的 RP 值之和比率进行计算，即���(�) =��(�)∑ ��(��)�=1，所得结果用小数表示，小数点后保留 4 位数字.� 代表的是第 k 次回归测试中测试用例执行的优先概率；σ为历史数据的权重.当σ设定大于 0.5时，�主要取决于最近两次回归测试会话的历史数据���；反之，�主要取决于整个测试生命周期中除最近一次回归历史数据外其他全部回归测试会话的历史数据�−1.如果测试用例 t 的�值越高，被优先执行的概率越大.表 2 展示了 4 个测试用例经过计算后得到的第二轮回归测试的优先概率. 3.1.3   A-TCP A-TCP 算法的伪代码见算法 2.假设当前测试阶段产生的新的测试用例集为��.该算法输入为当前阶段的全体测试用例集组 T，输出为新的测试序列�′.首先，搜索 T 中的所有��，进行阶段排序.其次，对不同的阶段采用不同的方法进行阶段内排序.阶段排序和阶段内排序混合的好处是，优先级层次分明，减少冗余处理测试用例，提高测试效率. 算法 2 A-TCP //  假设当前测试阶段为  �� 输入: �  //输入当前阶段下已产生的全体测试用例集组. 输出:�′  //输出新的测试序列. 1.  �′= ∅; 2. FOR j = n DOWNTO 1 DO 3. IF(��是���的测试用例集) THEN  4.   ��. �������� = 1;    //将���的优先级赋予最高级 1 5.  ��′ = ��������������������������(���);  6.  �′= ��′ + �′;   //将有序序列���′置于�′队首位置 7. ELSE  ��. �������� = 2;   //其余 TS 赋予次优先级 2              8.   ��′ = �������������������(���);  9.   �′= �′ + TSj′;   //将TSj′置于输出队列的队尾位置 10. ENDIF; 11.ENDFOR; 沿用表 1 和表 2 的例子继续进行解释.假设当前测试阶段为第二轮回归测试 ST2，表 2 中的测试用例�1-�4为测试阶段 ST1的测试用例集 TS1.首先为ST2 产生新的测试用例集 TS2={�5, �6, �7, �8, �9, �10}.根据初始化方法得到每个测试用例的初始化优先级 为 RP( �5)=2,  RP( �6)=7,  RP( �7)=4,  RP( �8)=3, RP(�9)=1, RP(�10)=5.其次，根据 A-TCP 将 TS2赋予优先级 1，按照测试用例初始化方法进行排序，排序后置于输出队列的队首；将 TS1赋予优先级 2，按照基于历史的方法进行排序，排序后置于输出队列队尾.最后，得到最终的�′为�6-�10-�7-�8-�5-�9-�1-�4-�2-�3. 3.2   “旧测试”中的回归测试选择 “旧测试”主要涉及两部分内容：一是检验曾经出错的功能是否还会发生错误，保证功能的正确性；二是检验新增功能加入是否会影响已交付功能出错，保证功能的稳定性.“重测所有”策略(Retest-计算机学报 作者名等：论文题目  7 All) [3,38]无疑是最能保证已交付功能正确性和稳定性的方法.但对于敏捷开发环境下逐渐庞大的测试集，执行所有测试用例显然效率低下.本节提出一种敏捷回归测试选择技术(A-RTS).与 A-TCP 对应，这里给出“版本”的概念. 定义 2  测试版本 VT.  假设一个系统分为�(� ≥ 1)个开发版本，那么测试版本相应的定义为�� (1 ≤ � ≤ �).一个测试版本中包含若干测试阶段.一个��的测试用例即为其所有测试阶段全体测试用例集组�中的测试用例.所有测试版本的 T 形成的容器称为测试池�� = {�1, �2, ⋯ ��}. 定义 3  失效测试用例 ft.  测试过程中发现错误导致软件失效的测试用例称为失效测试用例 ft. 定义 4  交互测试用例 nt.  新版本中新增功能加入有时会涉及与旧版本功能有交互，测试这些存在旧版本已发布功能中被交互的功能的测试用例称为交互测试用例 nt.交互测试用例可根据需求功能关联关系图[49,50]得到. B1B2 B3B4B5 B6B7 (a)  需求功能关联关系图 B2B4B5B7T2T4T5T7 (b)  获得交互测试用例 图 4   关于交互测试用例的例子 用图 4 解释如何获得交互测试用例.假设每个需求的粒度为模块，每个需求均有一个测试用例测试.图中有 7 个需求：B1-B7，则有 7 个测试用例(T1-T7)与之对应.图 4.(a)为需求功能关联关系图，展示了 7 个需求之间的关联关系.其中，矩形框为需求，有向边为两个需求的直接对应关系.假设 B5 这个功能为新增功能，抽取与 B5 有直接对应关系的关联子图如图 4.(b)左侧图示.根据 3.1.1 节算法 1 中得到的 R-T 关系矩阵得到测试 B5 的新增测试用例 T5的交互测试用例为 T2、T4 和 T7. 定义 5 “旧测试”子集 LT.  在“旧测试”过程中通过测试选择技术得到的子集称为“旧测试”子集LT.它包含失效测试用例 ft 和交互测试用例 nt. A-RTS 的伪代码见算法 3.该算法的输入是测试池中现有的全部测试用例，且以 T、TS 为单位分组分层划分.输出为子集 LT.搜索 TP 中所有的 T，如果不是当前版本的 T，遍历其内部所有阶段的测试用例集 TS，将失效测试用例 ft 及交互测试用例 nt 加入到 LT 当中.重复上述过程直至搜索结束. 算法 3 A-RTS //  假设当前测试版本为  �� 输入:�� = {�1, �2, ⋯ ��}  //输入测试池中所有测试用例 输出:LT //输出通过选择技术筛选出来的“旧测试”子集 1. �� = ∅;   //初始 LT 为空 2. FOR EACH  �∈ ��       //遍历测试池中每个 T 3.   IF  (�不是���的全体测试用例集组) THEN // ��为已             //交付旧版本的 T 4.    FOR  EACH  �∈ ���,  ���∈ ��//遍历每个�中每个         //阶段的��中的测试用例 5.     IF (�是 ft  或 nt) THEN  6.         �� = �� + {�};  7.     ENDIF; 8.    ENDFOR; 9.   ENDIF; 10. ENDFOR;                       …     T2     ...T1   ...TS1...TS2...LTT4T3TkTS3TSnTPft1ft2“旧测试”子集测试池nt 图 5   “旧测试”中待执行的测试用例集 借助图 5 解释 A-RTS 算法.假设测试池 TP 中有 k 个全体测试用例集组 T，如图 5 的圆角矩形.当前版本的全体测试用例集组为�，且初始时“旧测试”子集��为空集.搜索所有的�，如果��不是��，则：1).找出�中曾经发现错误的测试用例，作为失效测试用例 ft 加入 LT 中；2).找出�中与当前版本有功能交互的测试用例，作为交互测试用例 nt 加入LT 中.搜索�1，�1不是��，遍历发现�1中第 1 测试阶段的测试用例集��1中存在发现错误的测试用例(黑色五角星)，将其作为��1加入左下角的圆形 LT 中.继续搜索，当搜索到�3时，发现�3中存在与��中某个阶段的测试用例存在功能上交互的测试用例(黑计算机学报8  计  算  机  学  报  2019 年 色六角形)，将其作为 nt 加入 LT 中.最终筛选得到 “旧测试”子集 LT.图 5 中，LT 中测试用例数量明显减少，因此可以有效减少测试时间，节省开销. 3.3   回归测试优化 本节将前文提出的 A-TCP 和 A-RTS 有效融合，建立回归测试优化模型 RTOM，并设计适用于敏捷开发环境的回归测试优化算法(Agile  Regression Test Optimization，A-RTO). 3.3.1   优化模型 RTOM 由于敏捷开发环境中的回归测试不断交付新功能，对于“旧测试”，其 LT 也逐渐庞大，为此设置一个失效标签以动态调整 LT 中的测试用例个数. 定义 6  失效标签 Tag.每个加入 LT 的测试用例lt 被赋予一个失效标签 Tag，初始值为 0.每次测试执行后：如果该 lt 没有失效，即没有发现错误，Tag值加 1；如果中途某一次测试发现错误，Tag 值清 0.当��� > �(θ为阈值)时，则将该 lt 从 LT 中剔除. 如图 6 所示，RTOM 的输入是当前版本当前测试阶段产生的新测试用例集��，目的是通过测试用例优先排序和测试用例选择得到一个待执行的测试序列�′′，最终执行��′′. 执行Ti" 采用A-TCP进行排序新测试用例集TSiLTi测试序列Ti" 测试池TP当前版本VTi当前阶段STi  Ti         ...TS1TS2TS3 TSnTi' 采用A-RTS策略采用A-RTO进行回归测试进入下一测试阶段更新每一个lt.Tag 图 6   敏捷开发环境中的回归测试优化模型 RTOM 第 1 步.产生当前版本当前阶段的新测试用例集��，并加入到��中，同时更新��在��中的数据. 第 2 步.采用 A-TCP 对当前版本的�进行排序，得到当前版本所有测试用例的一个优化序列�′. 第 3 步.采用 A-RTS 搜索��并将 ft 和 nt 筛选出来，得到��. 第 4 步.采用回归测试优化算法(A-RTO)将��与�′融合成一个新的测试序列��′′. 第 5 步.执行�′′. 第 6 步.根据�′′的执行情况，更新每一个 lt 在��中的失效标签��. ���值，测试进入下一阶段. 3.3.2   优化算法 A-RTO A-RTO 的过程见算法 4.该算法从初始版本开始循环迭代：首先，为当前版本创建新的 T，并进行优先排序，得到“新测试”的测试优先排序队列�′；其次，对上一版本的�−1进行测试选择，将 ft 或nt 加入“旧测试”的待执行子集��，并为新加入的成员初始化 Tag；再次，对上一版本的测试执行进行失效标签修改与判断，从而动态调整 LT 的规模；最后，将�′置于输出�′′的队首位置， ��按默认顺序置于�′′的队尾位置，形成一条优化�′′并执行. 算法 4 A-RTO 过程 输入:�� = {�1}  //从初始版本时输入 TP,此时池中只有�1  1.  � = 1, � = 0, � = 10, �� = ∅; //初始化全局变量 i, q, �, LT 2. WHILE(  ��不是最终版本  ���) DO  3.  T′′ = ∅,   �′= ∅; //执行序列T′′、“新测试”排序�′置空 4. Create new  �  for  ���; //为当前���产生新的�� 5.  �� = �� + {�};     //将新测试用例集组��加入 �� 6.  �′= �_���(�);   //使用 A-TCP 得到新的优先排序�′ 7. FOR EACH  �∈ ���,  ���∈ ��−1  8.    IF (�是 ft 或 nt) THEN 9.       ��  =  ��;          //将��赋值给��� 10.      �� = �� + {��};    //将���加入“旧测试”子集中 11.      ��. ��� = 0;      //将���的失效标签初始化为 0 12.      � + +;  13.    ENDIF; 14. ENDFOR; 15. FOR EACH  ��∈ ��   //遍历每一个 LT 中的测试用例��� 16.   IF (��在上一版本���−1执行时未揭露错误) THEN  17.      ��. ��� + +;   //该测试用例的失效标签值加 1 18.   ELSE  ��. ��� = 0;   //反之，其 Tag 值清零 19.   ENDIF; 20.   IF (��. ��� > �) THEN //如果���的 Tag 值大于阈值� 21.      �� = �� − {��};   //将该测试用例从 LT 中剔除 22.   ENDIF; 23. ENDFOR; 24.  �′′ = �′ + �′′;           //将�′置于�′′队首 25.  �′′ = �′′ + ��;          //将��按默认顺序置于�′′队尾 26. Run  �′′;                     //执行测试序列�′′ 27. Submit  ��, i++, and enter   ���+1; //���交付，进入���+1 28. ENDWHILE; 4  实验验证 为了验证本文提出的 A-RTO 的有效性，本节计算机学报