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] 和
   248   249   250   251   252   253   254   255   256   257   258