基于模式组合的粒子群优化测试用例生成方法

来源：软件学报杂志2016年第4期北京时间：

作者：姜淑娟,王令赛,薛猛,张艳梅,于巧,姚慧冉

单位：姜淑娟，中国矿业大学 计算机科学与技术学院, 江苏 徐州 221116;广西可信软件重点实验室(桂林电子科技大学), 广西 桂林 54100411,王令赛，中国矿业大学 计算机科学与技术学院, 江苏 徐州 22111602,薛猛，中国矿业大学 计算机科学与技术学院, 江苏 徐州 22111603,张艳梅，中国矿业大学 计算机科学与技术学院, 江苏 徐州 221116;计算机软件新技术国家重点实验室(南京大学), 江苏 南京 21002304,于巧，中国矿业大学 计算机科学与技术学院, 江苏 徐州 22111605,姚慧冉，中国矿业大学 计算机科学与技术学院, 江苏 徐州 22111606

摘要：适应度函数的设计在基于搜索的测试用例生成技术中占据重要的位置,然而在某些特殊的程序中,如存在嵌套、非结构性跳转或因return,break等语句跳出循环的程序,已有的适应度函数无法评价到所有的分支.目前的方法是修改程序的源代码,以使每个分支得到评价.但修改源代码不但可能影响程序的原有结构、引入错误,而且很难实现自动化.针对这一问题,提出一种基于模式组合的粒子群优化测试用例生成方法.首先,将分支条件定义为"模式",即,一类具有相同特征且能提高适应度值的个体集合,并改变其分支函数的插桩方式,可解决分支条件不完全评价的问题;然后,设计一种新的交叉算子,寻找到所有使模式的分支函数值最小的个体,将这些个体中含有模式的部分通过交叉算子组合到一个个体上,既可防止模式在进化过程中被破坏,又可因多种模式的组合而提高个体的适应度值;最后,使用局部搜索策略对种群中的最优个体进行搜索,提高粒子群优化算法的局部搜索精度,进一步提高测试用例生成效率.为了评价该方法的有效性,基于一组基准程序和开源程序进行实验.实验结果表明:对于含有模式的程序,该测试用例生成方法与已有方法相比,在覆盖率和平均进化代数上均有明显优势.

关键词：测试用例生成;粒子群优化算法;交叉算子;局部搜索策略

基金资助：国家自然科学基金(61502497);广西可信软件重点实验室研究课题(kx201530);南京大学计算机软件新技术国家重点实验室基金(KFKT2014B19)