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

钱忠胜 等: 面向两阶段分组的测试用例优先级排序方法 2045

1 相关工作

在测试用例优先级排序中, 基于相似性的 TCP 方法和基于贪心算法的 TCP 方法是两种常见的技术. 基于相
似性的 TCP 方法优先考虑已选择用例中最不相似的测试用例, 增加测试的广度和深度, 旨在快速发现软件中的缺
陷. 这种方法通常利用聚类分析技术来识别测试用例的相似性, 可有效减少冗余测试行为并提高测试效率. 然而,
聚类分析法常涉及较复杂的数据处理操作, 若将其与基于贪心算法的 TCP 方法结合会极大地降低算法效率. 但是,
受基于相似性的 TCP 方法的启发, 利用测试用例表现出的相似行为, 即用例覆盖信息相似性, 可简化排序操作. 为
避免聚类分析带来的复杂度, 更好地将测试用例的相似性用于基于贪心算法的 TCP 方法中, 我们采用简单的算法
挖掘测试用例间的关系, 将具有包含行为关系的用例分为一组, 可优化用例的排序策略, 提高排序效率.
基于相似性的 TCP 方法主要关注测试用例之间的相似性, 将相似的测试用例分组, 从而在测试阶段进行更有
效的排序和执行. Miranda 等人 [10] 提出 Fast 技术, 借用大数据领域常用的算法来查找相似性, 并在白盒与黑盒测试
中提供可扩展的基于相似性的测试用例优先级排序. 此外, 近年来大多数基于相似性的 TCP 研究通过聚类分析法
捕获相似的测试用例. Wang 等人 [12] 提出一种基于聚类的自适应测试用例优先级排序方法, 可在预优先级排序中
添加新的自适应调整内容. Chen 等人 [13] 提出一种基于聚类的静态黑盒测试用例优先级排序方法, 采用 K-medoids
方法捕获测试用例的相似性进行更精细地划分. Li 等人 [14] 提出一种基于语义感知的两阶段 TCP 框架, 利用基于信
息检索对测试用例进行初步排序和过滤, 并使用预训练的 Siamese 语言模型基于语义相似性对用例进行细粒度排序.
基于贪心算法的 TCP 方法通过贪心策略优先选择能够覆盖最多未覆盖代码的测试用例, 以提高测试覆盖率
和缺陷检测效率. 这种方法侧重于最大化每一步的收益, 通过逐步选择最优解来达到整体最优的效果. Elbaum 等
人 [6] 最早提出基于贪心算法的 TCP 技术, 包括 Total 策略和 Additional 策略. Li 等人 [8] 使用多个邻接表以减少基
于 Additional 策略的贪心算法中的冗余数据访问, 并建议将迭代次数减少到相对较小的值, 以在保持方法有效性
的同时提高效率. Zhang 等人 [11] 提出 OCP 算法, 引入一种通用的部分注意机制, 该机制根据先前选择的用例优先
级值进行排序, 并根据上一轮用例优先级值打破 Additional 策略陷入平局的情况. 范书平等人 [5] 提出一种基于关键
用例获取的测试用例排序方法, 根据候选用例的分支偏离度和候选用例覆盖新分支情况, 对用例进行排序.
然而, 在基于贪心算法的 TCP 研究中, 大多数方法将邻接矩阵作为输入, 少部分使用邻接表. 将邻接表作为输
入相比于邻接矩阵排序效率较高, 可在很大程度上缩减集合规模, 以降低用例相关性计算的复杂度. 并且, 以往的
研究只根据用例覆盖标准的整体状态选择测试用例, 忽略了其个体性, 即覆盖标准的被覆盖信息丢失. 此外, 基于
Additional 策略方法排序指标单一, Additional 策略随机性的选择会降低故障检测的有效性.
综上分析可知, 当前基于贪心算法的 TCP 方法未利用低复杂度的可挖掘测试用例覆盖信息相似性的方法, 从
而造成在每轮选择测试用例时将所有的候选用例考虑在内, 影响排序效率; 此外, 多数 TCP 方法采用单一的排序
策略和排序指标, 无法同时提高排序有效性和效率. 针对这两个方面的问题, 本文提出一种面向两阶段分组的测试
用例优先级排序方法 TPG-TCP. 该方法利用集合判断操作挖掘测试用例间的隐藏关系, 将测试用例进行粗粒度分
组, 避免在后续的排序中考虑所有的测试用例, 以提高排序效率; 另外, 根据迭代次数将关键用例进行细粒度分组,
并增加用例潜力度指标改进 Additional 策略, 对更能暴露问题的关键用例进行排序, 剩余用例采用简单高效的
Total 策略排序, 以同时提升排序的有效性与效率.

2 面向两阶段分组的测试用例优先级排序方法

大多数基于贪心算法的 TCP 技术在处理覆盖信息和排序时存在耗时过长、排序效率低的问题. 其中, 贪心算
法的 Additional 策略容易受到随机因素的影响, 导致排序的有效性降低. 基于此, 提出一种面向两阶段分组的测试
用例优先级排序方法 TPG-TCP, 主要包含粗粒度用例分组与细粒度用例分组排序这两个模块, 其整体框架如图 1
所示.
1) 粗粒度用例分组, 减少在覆盖信息和排序处理上的时间消耗. 将用于存储覆盖信息的覆盖矩阵转换为用例-
语句列表, 基于该列表对各用例的语句覆盖关系进行检测, 将待测用例分为关键用例集和普通用例集. 为下一阶段