基于GPGPU的软件回归测试用例多目标预优化

回归测试是软件演化过程中一项频繁执行且开销巨大的任务，其耗费甚至会占到软件维护总费用的三分之一以上。测试用例预优化技术是一种高效实用的回归测试技术，其目的是将不同的测试用例按照其重要程度排序后使用，从而获得更高的回归测试效率。课题申请者首先提出并应用现代启发式搜索算法到软件回归测试用例预优化中，并将研究成果发表在TSE上，受到该领域专家学者的广泛关注，文章已经被引用120多次。在本申请课题研究中，申请者提出了一种基于多目标优化的软件回归测试用例预优化技术。这项技术将为实现为实际软件回归测试提供有效的指导和帮助。同时，申请者还提出用GPGPU技术解决多目标优化演化算法的效率问题。这种技术可以以很小的成本获取算法运算效率的数十倍提高，不但能有效的提高软件回归测试用例预优化的效率，而且对整个多目标演化算法领域中广泛存在的效率问题有重大的指导作用，因此本课题研究具有重要的理论和现实意义。

测试用例优先排序技术是一种高效实用的回归测试技术，其目的是将不同的测试用例按照其重要程度排序后使用，从而获得更高的回归测试效率。在本课题研究中，我们提出了一种基于多目标优化的软件回归测试用例优先排序技术，设计了三种可用于排序的目标，并分别研究了NSGA-II算法、蚁群算法（ACO）、粒子群算法（PSO）和协同演化算法在多目标测试用例优先排序中的应用。同时采用了先进的 GPU 图形卡通用并行计算技术，提出了面向 CPU+GPU 异构计算下的多目标测试用例优先排序技术，提高测试用例优先排序的计算效率。在实验过程中，除了使用广泛应用的benchmark程序验证外，使用开源的 Google浏览器Chrome的JavaScript引擎，V8程序，程序代码行超过10万，有效代码行近6万。基于真实的具有一定规模开源程序的实验能够有效的证明课题提出技术的有效性，发表在SSBSE2015的论文Epistatic Genetic Algorithm for Test Case Prioritization获得基于真实工业数据的最佳论文奖(Best SBSE Paper based on actual industry data)。为了能够更好的帮助相关领域的研究人员使用本项目研究的技术，我们在CUDA平台下开发并实现了原型工具，并将程序设计成开源库模式，程序代码遵循GNU GPL2.0开源协议发布在github上。..在研究过程中，我们积极探索研究新方向，在把测试用例优先排序和软件错误定位技术相结合的基础上，提出了一种基于动态相似度的错误定位优先排序方法，节约了测试时间和成本。. .在项目资助下，项目负责人在中国计算机学会（CCF）软件工程专委会中组建了基于搜索的软件工程学组，自2012年起每年举办中国基于搜索的软件工程研讨会，组织相关领域的专家学者一起交流研讨，促进该领域在中国的发展。同期建立了中国基于搜索的软件工程网站www.csbse.org，收集本领域内的各种资源，为相关研究人员提供服务。2014年，项目负责人牵头撰写了《基于搜索的软件工程研究与进展》，发表在《CCF2013-2014中国计算机科学技术发展报告》中，极大推动了该领域在中国的发展。2015年成功申办了软件学报《基于搜索的软件工程研究专刊》，并将于2016年发表。