Page 253 - 《软件学报》2024年第6期
P. 253
向毅 等: 基于多样性 SAT 求解器和新颖性搜索的软件产品线测试 2829
TS 是由其新颖得分决定的. 如算法 4 的第 5 TS 中新颖得
新个体 tc 是否能加入档案 行所示, 找到当前测试集
分最小 (最差) 的个体 tc worst . 若 ρ(tc,TS ) > ρ(tc worst ,TS ) 成立, 则用 tc 替换 tc worst 并更新概率向量; 否则, 舍弃新个
′
′
tc . 更新概率向量的操作也非常简单 (第 8 tc i 与
体 行), 只需将当前 p i 加上 (tc i −tc worst,i )/N . 根据上述操作, 若
tc worst,i 取值相同, 则 p i 保持不变; 若 tc i 与 tc worst,i 取值不同, 则 p i 更新为 p i +1/N 或 p i −1/N . 具体而言, 存在两种情形.
tc worst,i = 0 时, 这意味着第 i 个变量取值为 1 的测试用例个数增 p i +1/N .
• 当 tc i = 1 且 1, 自然地 p i 应更新为
• 当 tc i = 0 且 tc worst,i = 1 时, 这意味着第 i 个变量取值为 1 的测试用例个数减 1, 自然地 p i 应更新为 p i −1/N .
p i = p i +(tc i −tc worst,i )/N 进行表达. 从时间复杂度的角度看, 这种更新效率非常高. 相反
这两种情形都可用公式
地, 文献 [34] 的算法更新概率向量时, 每次均需对当前测试集中第 i 个变量取 true 或 false 的测试用例重新计数,
效率相对较低.
算法 4 将新个体与当前测试集的最差个体进行比较. 若新个体更优, 则执行替换操作. 上述归档策略有利于从
全局的角度提升测试集的多样性, 但却忽略了新个体所在区域的局部信息. 例如, 新个体可能与档案中的某个个体
距离非常近, 但由于与其他邻居的距离较远, 导致新个体的新颖得分并不低. 在归档时, 新个体有可能会被加入档
目的在于验证多样性求解器的有效性. 为回答
案. 在这种情况下, 新个体的加入会导致局部聚集现象. 为缓解上述现象, 本文提出了一种基于局部信息的归档策
略 (见算法 5). 首先, 在 TS 中找到与新测试用例 tc 最近的测试用例 tc closest , 然后按照公式 (4) 分别计算 tc 和 tc closest
的新颖得分. 值得说明的是, 计算二者的新颖得分时均将对方排斥在外. 例如, 计算 tc 的新颖得分时, 仅考虑 TS 中
除 tc closest 外的个体, 即 TS \{tc closest } . 类似地, 计算 tc closest 的新颖得分时, 并不将 tc 纳入考虑范围. 最后, 如果 tc 较
tc closest 具有更高的新颖得分, 则用 tc 替换 tc closest 并更新概率向量 p . 由此可见, 在局部归档策略中, 新测试用例及与
其最近的测试用例不能同时存在, 有助于改善测试集的局部多样性.
同时采用全局和局部归档策略有望充分利用各自优势, 达到互补效果. 在第 5.5.2 节本文将从实验上予以充分
论证.
4.4 终止条件
dSATNS 算法终止条件的设置较为灵活. 一般地, 当算法的运行时间达到预设的最大值时, 算法终止并返回最
终的测试集. 由于测试集的多样性是以迭代的方式改进的, 用户完全可以根据自己的需要设置最大运行时间. 例
如, 若用户希望覆盖更多特征组合或发现更多缺陷, 则可将运行时间设置为某个较大值. 在实际应用中, 终止条件
的灵活性非常有益, 因为不同用户可根据实际需要自主地确定何时终止算法.
5 实验部分
为验证 dSATNS 各算法构件的有效性以及评估该算法的性能, 本文将回答以下研究问题.
• RQ1: 在 dSATNS 算法中, 采用 dProbSAT 求解器是否有助于改善覆盖率和缺陷检测率?
• RQ2: 在 dSATNS 算法中, 是否有必要采用两种归档策略?
• RQ3: 与主流算法相比, dSATNS 的性能如何?
P r 如何影响 dSATNS 算法的性能?
• RQ4: 参数
RQ1 RQ1, 将 dSATNS 算法中的 dProbSAT 替换为普通版本的
ProbSAT 得到变体算法 SATNS. 具体地, SATNS 生成种子时随机地将 c i 赋值为 1 或 0, 而 dSATNS 则是以概率
1− p i 将变量 c i 赋值为 1. 注意是否采用多样化的 ProbSAT 求解器是 dSATNS 与 SATNS 的唯一差别. 本文并不对
rSAT4J 是否有效进行消融实验, 其原因在于该求解器的有效性已在既往工作 [20,33] 得到充分验证.
RQ2 旨在验证同时采用两种归档策略的优势. 为回答 RQ2, 将 dSATNS 算法中的两种归档策略分别统一为
GlobalArch 和 LocalArch 得到两个变体算法, 记为 GloArch 和 LocArch. 此外, 在有关 RQ2 的实验与讨论中将
dSATNS 重命名为 TwoArch 以凸显 RQ2 的主题.
RQ3 是为了将本文算法与其他主流算法进行比较. 为回答 RQ3, 将 dSATNS 与 TSENS [33] , TSEGA [33] 和