种基于强化学习的持续集成环境中测试用例排序技术*赵逸凡1,2, 郝 丹1,21(高可信软件技术教育部重点实验室(北京大学), 北京 100871)2(北京大学 计算机学院, 北京 100871)通信作者: 郝丹, E-mail: haodan@pku.edu.cn摘　要: 在软件交付越来越强调迅速、可靠的当下, 持续集成成为一项备受关注的技术. 开发人员不断将工作副本集成到代码主干完成软件演化, 每次集成会通过自动构建测试来验证代码更新是否引入错误. 但随着软件规模的增大, 测试用例集包含的测试用例越来越多, 测试用例的覆盖范围、检错效果等特征也随着集成周期的延长而变化, 传统的测试用例排序技术难以适用. 基于强化学习的测试排序技术可以根据测试反馈动态调整排序策略, 但现有的相关技术不能综合考虑测试用例集中的信息进行排序, 这限制了它们的性能. 提出一种新的基于强化学习的持续集成环境中测试用例排序方法——指针排序方法: 方法使用测试用例的历史信息等特征作为输入, 在每个集成周期中, 智能体利用指针注意力机制获得对所有备选测试用例的关注程度, 由此得到排序结果, 并从测试执行的反馈得到策略更新的方向, 在“排序-运行测试-反馈”的过程中不断调整排序策略, 最终达到良好的排序性能. 在5个规模较大的数据集上验证了所提方法的效果, 并探究了使用的历史信息长度对方法性能的影响, 方法在仅含回归测试用例的数据集上的排序效果, 以及方法的执行效率. 最后, 得到如下结论: (1) 与现有方法相比, 指针排序方法能够随着软件版本的演化调整排序策略, 在持续集成环境下有效地提升测试序列的检错能力. (2) 指针排序方法对输入的历史信息长度有较好的鲁棒性, 少量的历史信息即可使其达到最优效果. (3) 指针排序方法能够很好地处理回归测试用例和新增测试用例. (4) 指针排序方法的时间开销不大, 结合其更好、更稳定的排序性能, 可以认为指针排序方法是一个非常有竞争力的方法.关键词: 持续集成; 测试用例排序; 强化学习中图法分类号: TP311中文引用格式: 赵逸凡, 郝丹. 一种基于强化学习的持续集成环境中测试用例排序技术. 软件学报. http://www.jos.org.cn/1000-9825/6506.htm英文引用格式: Zhao YF, Hao D. Test Case Prioritization Technique in Continuous Integration Based on Reinforcement Learning.Ruan Jian Xue Bao/Journal of Software (in Chinese). http://www.jos.org.cn/1000-9825/6506.htmTest Case Prioritization Technique in Continuous Integration Based on Reinforcement LearningZHAO Yi-Fan1,2, HAO Dan1,21(Key Laboratory of High Confidence Software Technologies of Ministry of Education (Peking University), Beijing 100871, China)2(School of Computer Science, Peking University, Beijing 100871, China)Abstract: As software delivery increasingly emphasizes speed and reliability, continuous integration (CI) has attracted more and moreattention these years. Developers continue to integrate working copies into the mainline to realize software evolution. Each integrationinvolves automated tests to verify whether the update introduces faults. However, as the scale of software increases, test suites containmore and more test cases. As software evolves, the coverage and fault detection ability of test cases also change among different CIcycles. As a result, the traditional test case prioritization techniques may be inapplicable. Techniques based on reinforcement learning can* 基金项目: 国家自然科学基金(61872008)收稿时间: 2021-07-13; 修改时间: 2021-09-08; 采用时间: 2021-10-08软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cnJournal of Software [doi: 10.13328/j.cnki.jos.006506] http://www.jos.org.cn©中国科学院软件研究所版权所有. Tel: +86-10-62562563网络首发时间：2022-11-18 14:57:12网络首发地址：https://kns.cnki.net/kcms/detail/11.2560.TP.20221116.1747.003.htmladjust prioritization strategies dynamically according to test feedback. But the existing techniques based on reinforcement learning proposedin recent years do not comprehensively consider information in the test suite during prioritization, which limits their effectiveness. Thisstudy proposes a new test case prioritization method in CI, called pointer ranking method. The method uses features like historyinformation of test cases as inputs. In each CI cycle, the agent uses the attention mechanism to gain attention to all candidate test cases,and then obtains a prioritization result. After test execution, it obtains the updating direction from the feedback. It constantly adjusts itsprioritization strategy in the process “prioritization, test execution, test feedback” and finally achieves satisfied prioritization performance.This study verifies the effectiveness of the proposed method on five large-scale datasets, and explores the impact of history length onmethod performance. Besides, it explores the model’s effectiveness on datasets which only contain regression test cases and the model’sexecution efficiency. Finally, the study comes to the following conclusions. First, compared to existing techniques, pointer ranking methodcan adjust its strategy along with the evolution of the software, and effectively enhance the fault detection ability of test sequence in CI.Second, pointer ranking method has good robustness to history length. A small amount of history information can make it achieve theoptimal performance. Third, pointer ranking method can handle regression test cases and newly-added test cases well. Finally, pointerranking method has little time overhead. Considering its better and more stable prioritization performance, pointer ranking method is avery competitive method.Key words: continuous integration (CI); test case prioritization; reinforcement learning1 引　言随着工业软件交付向着敏捷、持续的趋势发展, 为了使得软件迭代更加迅速且可靠, 工业界提出了持续集成方法. 在持续集成中, 软件项目的现有状态称为“主线”, 为了多人同时开发以提高软件交付的速度, 开发人员通过代码管理系统将软件项目拷贝到本地的开发机器上, 这份拷贝称为“工作副本”. 通过对工作副本代码的更新, 开发人员为软件引入新功能或修复旧版本的错误, 并与此同时添加或改变测试用例, 以及时检测改动后的软件功能是否正常, 在编译、链接、运行并通过所有自动化测试后, 变动被集成到“主线”, 该项目被重新构建, 完成一个持续集成周期. 持续集成需要开发者不断提交更新代码, 将工作副本与共享主体部分代码合并, 通过不断提交小的修改并将其整合到主目录中, 完成新功能的添加, 高频率的提交使得软件得以更快地进行版本的更新迭代, 并能够通过软件测试及时发现软件演化过程中引入的新错误, 降低积累错误的风险和修复错误的成本. 近年来, Travis CI[1]、Circle CI[2]、Jenkins[3]、Buildbot[4]等多个持续集成平台发展迅速, 成千上万的软件使用持续集成作为软件交付方式, 逾60 万个用户已选择在Travis CI 上进行项目测试[1], 并从其快速建立、及时测试的特性之中受益, 公司如Google、Facebook、Microsoft 和Amazon 也使用了持续集成来更好地匹配他们的开发速度和规模[5].然而, 持续集成也面临着挑战, 其最受关注、最重要的特性就是为开发者提供快速的反馈, 但实际应用中系统构建和测试运行可能耗费大量的时间和资源, 这与人们所期望的相悖. 据报道, 亚马逊工程师每天进行13.6 万次系统部署, 平均每12 s 进行一次[5]. 在Google, “开发人员必须等待45 分钟至9 个小时才能接收测试结果”[6]. 如前所述, 每个持续集成周期涉及多个任务, 包括版本控制, 软件配置管理, 新软件候选版本的自动构建和回归测试, 在企业应用中, 通常持续集成的时间瓶颈在于回归测试[7], 特别是涉及到外部服务如数据库的测试. 回归测试是持续集成尤为重要的一环, 通过运行确定的测试用例集, 观察软件能否通过全部测试用例, 可以确保更新的代码没有引入新的错误, 且没有影响到原先软件功能. 但越来越大的测试用例集规模对回归测试的时间成本和资源成本提出了更高的要求, 同时, 在代码不断迭代更新的条件下, 持续集成中的回归测试可获取的信息和测试用例特性也不同于传统的回归测试, 新环境下的回归测试为研究人员提出了新的挑战. 为了解决该问题, 持续集成中的测试用例排序技术被提出, 其基本思想是对测试用例集中的元素进行排序, 先执行潜在可能揭示错误的、用时更短的测试用例, 后执行不会揭示错误的、用时较长的测试用例, 及时暴露软件的缺陷, 给予开发者最快的反馈.在持续集成环境中, 由于开发人员的频繁提交, 软件代码在不断发生改变, 传统的白盒测试用例排序技术[8−11]需要使用的测试用例语句覆盖信息、代码依赖关系等需要频繁更新, 而近年来一些新的测试用例排序技术也需要用到这些信息[12−15], 这需要消耗大量资源和时间, 不能满足持续集成对快速反馈的需求. 除此以外, 每个集成周期中可能存在测试用例的增删, 一些测试系统过时特性的测试用例可能被删去, 而一些测试新特性或被改变特性的2 软件学报 ****年第**卷第*期测试用例可能被加入, 单纯依靠历史执行结果的测试用例排序方法不能够捕捉到代码上下文的变化, 因而不能够很好地进行适应性调整. 同时, 随着集成周期数增加, 测试用例的重要性也会发生变化, 非适应性算法不能够捕捉到测试用例重要程度随时间的变化. 综上, 一些传统的测试用例排序技术不能很好地捕捉软件代码和测试用例的变化, 不能合理地利用持续集成中测试用例的历史执行信息(包括历史执行结果、历史执行时长) 等特征, 因而不适用于持续集成环境, 为此, 新的持续集成测试用例排序算法亟待开发. 近年来, 有不少针对持续集成测试用例排序的系统性研究[16,17].机器学习算法通过构建模型, 完全自动化地生成排序, 也被应用于测试用例排序任务中[18−20], 而强化学习是机器学习方法的一个分支, 学习者在与环境的交互中做出序列决策, 选择动作并得到奖励指引, 然后根据执行结果不断调整自己的策略, 强化得到奖励的行为以获得最大效益. 持续集成中每个集成周期都需要确定测试用例的执行次序, 且由于代码改变、测试用例增删, 不同集成周期的测试特性也会发生变化, 强化学习技术能够解决持续集成测试用例排序这个序列决策问题, 也适用于持续集成这个环境不断发生变化的场景[18,21−23]. Spieker 等人提出了第一个基于强化学习的方法RETECS[18], RETECS 方法构建的模型根据单个测试用例特征, 计算并输出其优先级, 根据该测试用例的执行结果及最终排序位次, 计算得到该测试用例的奖励信号, 据此调整模型. 本文提出了一种新的基于强化学习的持续集成环境中测试用例排序方法——指针排序方法, 该方法构建的模型将测试用例集中所有用例的特征一起输入模型, 模型在赋予某个测试用例优先级时, 使用注意力机制, 综合考虑其他所有测试用例的特征, 捕捉测试用例间的相对关系并据此排序. 强化学习通过奖励信号激励模型改进策略, 通过给予智能体合适的反馈信号, 引导模型朝着最大化预期目标的方向前进, 为了与输入相匹配, 本文还提出了两种新的奖励函数, 它们是对测试用例集整体排序效果的评价, 为整个测试用例集而非单个测试用例的排序结果定义激励信号, 引导模型实现更好的排序. 本文在5 个数据集(Paint Control、IOF/ROL、GSDTSR、Bcel、Nfe) 上将本方法与RETECS 方法进行效果比较, 并探究了历史信息长度等输入信息对本方法的表现影响, 本方法在回归测试用例数据集上的表现效果, 以及本方法的执行效率.本文的贡献如下.(1) 提出了一种新的用于持续集成环境中的测试用例排序方法, 该方法综合考虑测试用例集中所有用例信息进行排序, 并使用了评价测试用例集的整体排序效果的奖励函数, 直接用全局目标激励模型, 避免排序陷入局部最优.(2) 在5 个较大规模的实际数据集上验证技术的有效性, 验证了提出的方法具有良好的测试用例排序性能, 在其中4 个数据集上, 所提方法的平均表现优于现有方法, 在全部数据集上, 所提方法在最坏情况下的排序效果远好于现有方法.(3) 探究了影响指针排序方法效果的因素: 历史信息长度、新增测试用例. 得到结论: 指针排序方法受历史信息长度影响较小, 能够很好地处理新增测试用例和回归测试用例.(4) 探究了指针排序方法的执行效率. 得到结论: 指针排序方法具有较小时间开销的同时, 有优秀的排序性能,是一个具有竞争力的排序方法.本文第1 节介绍了本文的研究背景、研究目的及研究内容. 第2 节简要介绍了测试用例排序的相关工作. 第3 节介绍了本文提出的指针排序方法的原理, 所构建模型各个部分的结构和计算公式. 第4 节介绍了本文提出的4 个研究问题, 实验设置, 实验结果与分析, 以及实验有效性威胁. 第5 节对本文工作进行总结和讨论, 阐述本文的研究意义, 展望未来工作.2 相关工作测试用例优先排序最先由Wong 等人在1997 年提出[24], 即对给定的测试用例集, 将最有可能揭示错误的测试用例排到前面最先执行, 从而减少开发人员得到测试反馈的时间, 提升开发效率. Total 和Additional 策略是两种基于贪心算法的传