Page 251 - 《软件学报》2024年第6期

向毅 等: 基于多样性 SAT 求解器和新颖性搜索的软件产品线测试 2827

4. else
c ← dProbSAT (p) //多样性 ProbSAT 求解器 (SLS 类型)
5.
6. end if
7. return c
算法 3 给出了 dProbSAT 的详细流程. 首先将测试用例 c 初始化为空 (null). 然后, 根据第 i 个特征的类型为变
c i 赋初值. 具体地, 若第 c i 赋值为 1; 若第 c i 赋值为 0. 所谓强
量 i 个特征是强制性的, 则将 i 个特征是废弃的, 则将
制特征指的是该特征必须出现在任何有效软件配置, 而废弃特征任何时候均不能被选中 [30] . 强制和废弃特征对应
c i 赋值为 1 的概
变量的赋值是固定的, 这是因为任何违反都将直接导致不可行测试用例. 若非上述两种情形, 则将
率为 1− p i , 赋值为 0 的概率为 p i (算法 3 的第 8–12 行). 最后, 若以上规则生成的 c 不可行, 则调用原始的 ProbSAT
求解器修复 c (第 15 行). 针对第 5 节中的所有特征模型, 本文统计了 c 为不可行解的百分比, 其最大值为 99.89%,
最小值为 97.56%, 平均值为 99.79%. 以上现象的解释并非难事. 事实上, 特征模型的约束众多且复杂, 对各变量进
行独立赋值几乎必然会导致不可行解. 因此, 采用 ProbSAT 等求解器修复 c 是必要的. 值得一提的是, 除了 ProbSAT
求解器外, 还可以采用其他任意 SLS 类型的 SAT 求解器. 作为一个通用框架, 算法 3 适用于任何 SLS 类型的
SAT 求解器.
算法 3. c ← dProbSAT(p) .

1. c ← null
2. for i ← 1 to n do
3. if 第 i 个特征是强制的

4. c i ← 1
5. elseif 第 i 个特征是废弃的
6. c i ← 0
7. else
8. if rand(0,1) < 1− p i 1
9. c i ← 1
10. else

11. c i ← 0
12. end if
13. end if
14. end for
c 不可行, 则运用 ProbSAT
15. 若 求解器修复 c
16. return c
算法 3 的第 8–12 行是提升测试用例多样性的关键所在. 在当前测试集 TS 中, 第 i 个变量取值为 1 的测试用
p i , 则在种子 中第 i 个变量取值为 p i 越大 (小), 说明当前测试集
例的比例为 c 的概率为 1− p i , 而非 p i . 事实上,
中第 i 个变量取值为 1 的测试用例的个数越多 (少). 相反地, 种子中第 i 个变量取值为 1 的概率就越小 (大). 这样
c i 取 1 和取 0 的测试用例的个数不至于相差太大, 进而避免产生聚集的测试
处理的目的是形成一种“对抗”, 迫使
用例. 相反, 若采用与分布估计算法相同的做法, 即以概率 p i 将 c i 赋值为 1, 则当 p i 较大时, c i 赋值为 1 的概率也
较大. 这样有可能导致最终测试集中绝大多数甚至全部测试用例的第 i 个变量都取值为 1, 必将对测试用例的多样
性产生不利影响. 值得说明的是, 本质上文献 [34] 也采用了概率向量产生种子. 但与本文不同的是, 文献 [34] 的概
率向量也参与了后续的随机搜索, 为选择待翻转的变量提供重要启发式信息. 本文的概率向量仅用于生成种子, 这
样做的目的是将种子生成阶段与随机局部搜索阶段进行分离, 从而提高本文方法的灵活性. 例如, 本文将基于概率