Page 290 - 《软件学报》2026年第7期

王海宁 等: 融合因果效应的高效软件产品线缺陷定位方法 2975

所提方法基于以下两点特性来提升检查效率.
1) 未通过产品的可疑特征选择集合之间存在包含关系, 这会导致生成重复的特征交互. 例如, 存在两个未通过
产品的可疑特征选择集合分别为 DS 1 = {−f 1 ,− f 2 ,+ f 3 ,−f 4 } 和 DS 2 = {−f 1 ,− f 2 ,+ f 3 ,−f 4 ,−f 5 }. 显然 DS 1 ⊆ DS 2 , 导致它
们存在许多相同的子集 (特征交互). 若不进行处理, 这些相同的特征交互将被重复生成并检查它们的可疑性. 因
此, 舍弃被包含的可疑特征选择集合, 以避免相同的特征交互被重复生成.
2) 不同潜在特征交互集合之间存在相同的子集, 将使算法重复检查相同的特征交互. 例如, 存在另一个差异特征
集合 D 3 = {+f 1 ,+f 2 ,+ f 3 ,− f 4 }, 其子集集合为 {...,(+f 2 ,+ f 3 ),(+ f 3 ,− f 4 ),...}, 而 D 2 的子集集合为 {...,(−f 2 ,+ f 3 ),(+ f 3 ,− f 4 ),
(+f 3 ,− f 4 ). 这里仅展示了它们的部分子集, 事实上存在大量相同的特征交
...}, 它与 D 3 的子集集合存在相同的子集
互, 意味着许多相同的特征交互会被重复检查. 为此, 利用缓存机制 (如哈希表) 保存被检查过的特征交互, 若当前
特征交互在缓存中, 则不进行可疑性检查, 反之进行可疑性检查. 通过这种方法, 可以有效避免重复检查, 进而提高
特征级缺陷定位的效率.
可疑特征交互识别方法的伪代码如算法 1 所示. 首先, 见算法 1 第 5 行, 对于每个未通过产品的配置, 计算它
们的可疑特征选择集合. 对于不同未通过产品之间的可疑特征选择集合可能存在包含关系, 如第 6–8 行所示, 舍弃
被包含的可疑特征选择集合. 接着, 算法 1 中第 9–19 行表示, 对未被舍弃的可疑特征选择集合, 基于缓存机制生成
相应的特征交互并进行可疑性检查. 最后, 输出可疑的特征交互集合.
算法 1. 高效的可疑特征交互识别方法.

输入: 所有的产品配置集合 C = PCs∪FCs, 其中 PCs 和 FCs 分别表示通过与未通过的产品配置集合;
输出: 可疑的特征交互集合 FIs.
1. FIs ← ∅
2. Cache ← ∅ //用于保存检查过的特征交互
3. ∆ ← ∅ //保存未通过产品的可疑特征选择集合
4. for i ← 1 to |FCs| do //遍历未通过产品集合
5. ∆ i ← DS (FCs i ) // ∆ i 存储 FCs i 的潜在特征交互集合
6. if ∆ i 被包含于 ∆ 中任意一个集合
7. continue
8. end if
9. for k ← 1 to 7 do
10. Ω ← KItemSet(∆ i ,k) // KItemSet(∆ i ,k) 表示计算 ∆ i 的 k 阶子集
11. for j ← 1 to |Ω| do
12. if Ω j ∈ Cache
13. continue
14. else if Ω j 满足缺陷相关性和最小性
15. FIs ← Ω j
16. end if
17. Cache ← Ω j
18. end for
19. end for
20. end for
21. return FIs

本文所提可疑特征交互识别方法的效率与被检查系统本身有关, 包括其特征的数量和测试的配置数. 在最坏