基于退火Memetic算法和贝叶斯网络的回归测试用例集优化研究

As effective methods to reduce testing costs, regression test case reduction and test case prioritization techniques have been widely hired to regression test. Genetic algorithm and other means are employed to solve problems related to test case reduction and some effects are achieved, whereas the algorithm still needs to be improved due to its slow convergence speed and premature convergence to local optima. Researches on test case prioritization problems based on coverage and other techniques also made great development. However, most previous methods consider factors influencing prioritizing process separately. A more reliable sorting criterion may be produced under integrated consideration. This research first develops a comprehensive information system for regression test, which records static and dynamic information in the process of testing. To improve the genetic algorithm, hybrid algorithm based on simulated annealing and memetic algorithm is employed to solve test suite reduction problem. Thirdly, after investigating factors influencing test case prioritization, especially factors detecting important errors, this research builds a Bayesian network which can evaluate probability of test case detection of important errors, in view of providing key criterion to test suite prioritization. Finally, considering the three processes in test case prioritization in an integrated manner, it constructs a regression test prioritizing platform which includes selection, reduction and prioritization. This subject attempts to compare the above mentioned algorithms based on real data.

回归测试用例约简及优先排序技术作为可降低回归测试成本的有效手段，已被广泛用于回归测试中。遗传算法等被应用于求解约简问题并取得了一定的效果，收敛速度慢及过早收敛等问题使得算法还有一定的改进空间。基于覆盖率等技术对测试用例优先排序问题的研究也取得了一定的进展，但以往方法多单独考虑影响排序的因素，如综合考虑将可能产生更为可靠的排序标准。本课题首先将开发一个回归测试综合信息平台，对测试的静态及动态信息进行记录，为优化提供基础；其次，为改善遗传算法相关问题，拟将模拟退火和Memetic的混合算法应用于求解用例集约简问题；再次，综合考虑影响用例优先排序的因素，特别是检测到"重要错误"的因素，构建评价测试用例检测到"重要错误"概率的贝叶斯网络，为用例集优先排序提供重要的排序标准；最后，综合考虑测试优化的三个阶段，构建一套包括"选择-约简-排序"的回归测试优化平台。本课题将通过真实数据对所提算法进行比较。

本项目设计基于进化算法（遗传算法、模拟退火以及改进的遗传算法（Memetic））和贝叶斯网络对软件测试用例集进行优化的技术，重点研究软件回归测试用例集约简和测试用例排序问题。在研究过程中分别从软件分析、测试用例分析等方面入手，构建贝叶斯网络并基于进化算法对软件测试的排序、最小化等问题进行求解，得出更优的结果，从而降低测试成本，提高软件质量。主要的研究包括三个方面：（1）基于GE-GA的测试用例约简方法。测试用例约简是软件测试优化的一个重要方法，传统的基于贪心算法在某些特殊情况下表现的并不理想，而遗传算法在算法执行过程中效率偏低，在此基础上我们将结合GE和GA的优势，提出一个混合算法，先进行基本覆盖选择，然后用遗传算法进行进化求解，得出更少的测试用例以达到同样的测试效果，从而起到对测试用例集的优化。（2）基于聚类-贝叶斯网络的回归测试用例排序技术。测试用例排序是在回归测试资源较为紧张的情况下为了优先执行更能发现错误的测试用例的一项优化技术。从软件变化分析入手，结合软件缺陷预测技术构建错误易发性模型，并根据测试的覆盖信息构建贝叶斯网络，对每个测试用例求解其发现错误的可能性，并基于此对测试用例进行排序，优先执行那些最有可能发现软件缺陷的测试用例，以提高测试用例的执行效率，优化执行成本。（3）软件缺陷定位技术的研究。本项目在对测试优化问题进行研究的同时，积累了测试相关的数据集及系列工具，在此基础上进行软件缺陷的定位成为可能。在缺陷定位的研究中，我们提出了基于遗传算法的多缺陷定位研究，首先将缺陷位置的可能分布以二进制字符串表示出来，然后基于Ochiai方法并根据测试执行的谱信息来计算每个可能分布的适应度值，并用遗传算法进行进化求解，根据迭代条件终止后得到的最优种群得到可能的缺陷位置分布，以辅助程序员进行错误调试。本项目的研究除了在方法上进行探索之外，还采用Siemens套件、Linux大规模程序以及部分Java程序作为研究对象进行了相关的实证研究，并与各自子领域的现有方法进行了比较，分别取得了不同程度的改善。同时，此次研究也在相关领域进行了拓展，包括软件缺陷预测、遗传算法的本身及应用等方面，分别取得了相应的成果。本项目的研究坚持理论与实际并重的原则，项目研究过程中调研了多个软件开发与测试团队并将所研究的技术应用到实际测试过程中，取得了良好的效果。