覆盖表生成的禁忌搜索算法

作者：王燕^*; 聂长海; 钮鑫涛; 吴化尧; 徐家喜

来源：软件学报, 2018, 29(12): 3665-3691.

DOI：10.13328/j.cnki.jos.005369

• 基于搜索的软件工程
• 组合测试
• 覆盖表
• 禁忌搜索
• 并行化

组合测试可以有效检测待测系统中由参数间交互作用而引发的故障.在其30多年的发展过程中,覆盖表生成一直是关键问题之一,相关研究文献已达200多篇.作为一种有效的覆盖表生成算法,已有的禁忌搜索算法在所生成的覆盖表规模上具备一定的优势,但其解的质量和运算速度仍有提升空间;同时,这些算法实际应用能力较差,既不支持约束处理,也无法生成可变力度覆盖表.针对以上问题,提出了一种禁忌搜索算法.该算法从3个方面对已有的算法进行了改进:1)算法参数配置调优分pair-wise和爬山两阶段进行,确保使用较少配置条数最大程度击中最优配置,进一步提高算法生成覆盖表的规模;2)进行算法并行化,加速算法生成覆盖表的速度;3)增加约束处理和变力度处理,使算法可适应多种测试场景.实验结果表明,该算法在固定力度、变力度、带约束等多种类型覆盖表的规模上都具有一定优势,同时,并行化使算法平均加速2.6倍左右.

• 单位
  南京大学; 南京晓庄学院; 计算机软件新技术国家重点实验室