Page 165 - 《软件学报》2026年第5期

2044 软件学报 2026 年第 37 卷第 5 期

phase, fine-grained prioritization of test cases is performed. Key test cases are further subdivided based on the number of iterations. To
mitigate the randomness inherent in the Additional strategy, a TP-Additional strategy based on test case potency is introduced to prioritize
a portion of the key test cases. Meanwhile, a simple and efficient Total strategy is applied to prioritize the ordinary test cases and
remaining key test cases. The results from the Total strategy are appended to those produced by the TP-Additional strategy. This method
improves both the effectiveness and efficiency of test case prioritization. Experimental results on six datasets, compared with eight existing
methods, demonstrate that the proposed method achieves average improvements of 1.29% in APFD and 9.54% in TETC.
Key words: test case prioritization (TCP); two-phase grouping; greedy algorithm; Additional strategy
测试用例优先级排序 (test case prioritization, TCP) 技术在不减少测试用例数量的情况下, 按照某种特定的准
则或目标重新安排整个测试套件中测试用例的执行顺序, 使得有较高优先级的测试用例优先执行, 在缓解测试开
销方面备受关注 [1−4] .
在 TCP 中, 贪心算法因简单高效, 适用性强, 已成为解决用例排序问题的常用算法 [5] , 包括 Additional 策略与
Total 策略, 分别由 Elbaum 等人 [6] 和 Rothermel 等人 [7] 提出. 这两种策略自 1999 年提出以来因其实用性强而受到
广泛关注 [8] . 它们的基本思想是先执行覆盖程序语句多的测试用例. 其中, Total 策略是优先选择总覆盖语句数最
多的测试用例, Additional 策略是优先选择覆盖目前未被覆盖的语句数最多的测试用例 [9] . Additional 策略因其反
馈机制的引入, 相比于 Total 策略可应用于更复杂的场景. 然而, 有研究工作 [10] 指出, 基于 Additional 策略的贪心算
法在优先级划分上耗费的时间过长. 一些方法通过使用额外的数据结构减少冗余数据访问 [8,10,11] 以改进 Additional
策略, 但它们大多使用单一的排序策略, 且每轮迭代排序过程一次性考虑全部测试用例, 而未关注用例间的关系,
导致在覆盖信息和排序方面的处理上耗时过长. 即使某些方法采用多类型排序策略, 但其策略选择指标较单一, 无
法应用于不同程序中, 指标划分不灵活, 应用性较差. 因此, 利用测试用例间的关系以丰富策略选择指标, 并使用多
样性排序策略对缓解 TCP 方法的效率至关重要.
除效率之外, TCP 的有效性也是影响其方法广泛应用的另一个重要方面. Additional 策略在故障检测率方面,
已被认为是最有效的 TCP 技术之一 [11] . 但 Additional 策略易受随机因素干扰, 当出现平局时, 通常会随机选择待
排测试用例, 影响排序的有效性. 已有研究使用历史覆盖值 [11] , 或者根据用例覆盖程序的分支情况与用例覆盖程
序的均衡程度 [5] 减弱 Additional 策略随机性对故障检测有效性的影响. 然而, 这些方法仅考虑用例覆盖标准的整体
性, 忽略了其个体性, 且随机性的改进方法无法提升排序效率, 不能减少每轮排序迭代的时间, 无法同时提升排序
的有效性与效率. 因此, 设计能缓解 Additional 策略受随机性影响, 同时加快每轮排序迭代过程的方法, 对提升排
序有效性和效率有重大意义.
基于上述两个方面的问题, 本文提出一种面向两阶段分组的测试用例优先级排序 (test case prioritization based
on two-phase grouping, TPG-TCP) 方法. 首先, 通过挖掘测试用例间的隐藏关系, 将待排测试用例进行粗粒度分组,
分为关键用例组和普通用例组. 然后, 根据迭代次数将关键用例组进行细粒度分组, 对于一部分关键用例, 提出基
于用例潜力度的 TP-Additional 策略排序得到主序列; 对于普通用例组与另一部分待排关键用例, 采用简单高效的
Total 策略排序得到次序列, 将其追加至主序列后得到一个优先级排序序列, 这样通过多轮迭代后得到一个序列集.
最后, 对每个优先级排序序列实施故障检测操作, 并根据故障检测报告得到最佳优先级排序序列.
本文主要工作与贡献如下.
1) 利用测试用例间的隐藏关系, 将待测用例集分为关键用例组与普通用例组, 为下一阶段采用多样性策略排
序做准备, 以减少在覆盖信息和排序方面的时间消耗, 以提高排序效率.
2) 根据迭代次数, 将关键用例分组, 对部分关键用例采用提出的基于用例潜力度的 TP-Additional 策略排序,
降低 Additional 策略随机性的影响, 提升排序有效性.
3) 提出一种两阶段分组 TCP 框架, 将基于测试用例间隐藏关系的粗粒度分组与基于 TP-Additional 策略的细
粒度分组排序相结合, 同时提升排序的有效性与效率.
4) 与 8 种当前经典的、主流的 TCP 方法在 6 个程序上展开实验对比, 所提 TPG-TCP 在有效性和效率上均占
优势.