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

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

表 2 覆盖信息示例

测试用例 覆盖元素
t 1 e 1 e 2 e 3 e 4
t 2 e 1 e 5 e 7 e 8
t 3 e 1 e 3 e 4 e 6
－
t 4 e 1 e 2 e 5
－
t 5 e 1 e 2 e 6
－
t 6 e 1 e 3 e 4
t 7 e 1 e 2 e 3 e 4
t 8 e 1 e 3 e 4 e 7

2.1 粗粒度测试用例分组
近来, 通过聚类分析法挖掘用例间的关系在 TCP 中得到广泛研究, 但聚类分析法常涉及较复杂的数据处理操
作, 与基于 Additional 策略的 TCP 方法结合会增加算法复杂性. 然而, 利用用例间的关系来优化用例排序仍值得深
入研究.
本文实现了基于邻接表的粗粒度用例分组算法以对用例排序进行优化. 与 Li 等人 [8] 类似, 我们使用代码覆盖
率分析工具 Clover (https://bitbucket.org/atlassian/clover/src/master) 收集各数据集的覆盖信息, 生成的覆盖分析报告
会以矩阵形式表示. 为降低获取用例间隐藏关系的复杂度, 本文将覆盖矩阵转换为用例-语句邻接表来存储用例覆
盖信息. 此外, 采用相比于聚类算法更简单、高效的集合判断操作以计算用例的相关性, 并基于用例间的这种隐藏
关系对测试用例进行粗粒度分组. 这有助于在下一阶段的排序过程中根据测试用例重要性采用多样性的排序策
略, 通过减少在覆盖信息和排序方面的处理时间, 以优化排序. 一方面, 有助于减少用例相关性的计算次数, 以提高
挖掘用例潜在关系效率; 另一方面, 也可在下一阶段减少对覆盖信息的冗余访问, 以提高排序效率.
基于邻接表挖掘用例间的隐藏关系, 将每一个待排用例的覆盖元素视作一个集合, 通过集合判断两用例间的
隐藏包含关系. 这样, 将用例进行粗粒度分组的主要思想为: ① 当某个用例的覆盖信息可真包含另一用例信息时,
选择可覆盖更多程序元素的用例加入关键用例组, 被其他用例包含的用例放入普通用例组; ② 当两个测试用例的
覆盖信息完全相同时, 表示它们的检测功能是一致的, 我们将其视为相同的用例, 为保持关键用例组的简洁性, 我
们仅保留序号较小的用例在关键用例组中, 将序号较大的用例划分到普通用例组; ③ 当两个测试用例的覆盖信息
不存在包含关系时 (即, 除①②情况外), 将它们均加入关键用例组. 隐藏包含关系的表示见公式 (1).


  K ∪t i ,
  S i ⊃ S j , ∀i, j
 
 
 
 
 
 
 K ∪t i , S i = S j , i < j

 K = 

 

 
 
 
  K ∪t i ∪t j , S i ⊈ S j ∧S j ⊈ S i , ∀i, j
 (1)




 

  N ∪t j , S i ⊃ S j , ∀i, j

 
 
 

 N = 
  N ∪t j ,

 S i = S j , i < j
 
其中, K 为关键用例组, N 为普通用例组, S i 为用例 t i 覆盖的语句集, S j 为 t j 覆盖的语句集.
例 1: 本文以表 2 为例, 将邻接表作为算法输入. 通过集合判断操作, 可发现用例 t 3 的覆盖信息 S 3 = {e 1 , e 3 , e 4 ,
e 6 }可真包含 t 6 的覆盖信息 S 6 = {e 1 , e 3 , e 4 }, 故将 t 3 加入关键用例组, t 6 加入普通用例组; 用例 t 1 的覆盖信息 S 1 =
{e 1 , e 2 , e 3 , e 4 }与 t 7 的覆盖信息 S 7 = {e 1 , e 2 , e 3 , e 4 }相同, 且 t 1 的序号小于 t 7 的序号, 故将 t 1 加入关键用例组, t 7 加入
普通用例组; 其余用例 t 2 、t 4 、t 5 、t 8 间不存在包含关系, 故均加入关键用例组. 因此, 关键用例组 K = [t 1 , t 2 , t 3 , t 4 ,
t 5 , t 8 ], 普通用例组 N = [t 6 , t 7 ].
通过对用例进行粗粒度分组, 有助于在后续排序阶段减少冗余覆盖信息的访问, 也简化了测试用例排序和执
行的流程. 粗粒度用例分组的具体过程见算法 1.