基于进化优化的大型软件演化中的错误定位

Fault Localization is one of the most expensive and time-consuming activities of software testing and debugging process. These characteristics of large software, such as large scale, high complexity, long term running, make fault localization more difficult in the process of continuous evolving... We aim to resolve the fault localization issues occurred in large software evolution, by using the techniques such as program analysis, machine learning and evolutionary computation. The research contents are listed as follows: (1) we will propose the method of definition and extraction of program features for large software, based on which to perform change impact analysis and predict the suspicious locations of faults in new version, thereby narrowing the search scope of faults; (2) we will study the impact analysis and measurement method of test suite during fault locating for large software evolving, and design the optimal objective functions and constraints oriented to fault localization. Based on multi-objective optimization, we then construct a model of test suite reduction and augmentation; (3) with program features obtained, we will propose the techniques for the individuals encoding, initial population constructing, and mutation operator designing that are suitable for large software, and then construct a framework of fault localization based on evolutionary optimization; (4) we will develop a supporting platform and conduct the experimental verification. .. This interdisciplinary project, combined with computer science, automation and applied mathematics, can provide important theoretical significance and practical application value.

软件错误定位是软件测试和调试过程中代价最昂贵和耗时的活动之一。大型软件的规模庞大、结构复杂、运行周期长等特点使得其在持续演化过程中的错误定位更加困难。..本项目基于进化优化思想，结合程序分析和机器学习技术，以期解决目前大型软件演化过程中的错误定位问题。研究内容包括：(1)研究大型软件中的程序特征定义与提取方法，在此基础上开展修改影响分析，并预测新版本中的错误可疑位置，缩小错误搜索范围；(2)研究大型软件演化中测试用例对错误定位的影响分析及度量方法，设计面向错误定位的目标函数及约束条件，建立基于多目标优化的测试用例集约简与扩增模型；(3)结合程序特征，研究适用于大型软件的个体编码方式、初始种群的构造方法、以及变异算子的设计方法，进而构建基于进化优化的软件错误定位框架；(4)支撑平台的开发和实验验证。..本项目是结合计算机科学、自动化与应用数学的交叉研究方向，具有重要的理论意义和实际应用价值。

软件错误定位是软件测试和调试过程中代价最昂贵和最耗时的活动。申请人及合作者针对大型软件演化过程中错误定位存在的问题进行了为期四年的深入研究，提出了一整套解决相关问题的理论和方法。主要体现在如下4个方面:. (1) 在软件错误可疑范围分析与预测方面，我们收集了大量软件演化信息和历史Bug数据，结合机器学习的方法对错误分布进行预测。对跨项目缺陷预测中的类不平衡、条件分布及边缘概率分布差异性、特征异构、类重叠的相关理论进行了深入研究，提出了若干基于迁移学习的跨项目缺陷预测方法。. (2) 在面向错误定位的多目标测试用例演化方面，我们首先提出了多邻域Kalman滤波粒子群测试数据生成方法。然后，针对数据流测试准则，提出了基于遗传算法的测试用例生成方法。最后，针对分支条件不能完全评价的问题，提出一种基于模式组合的粒子群优化测试用例生成方法。. (3) 在基于进化优化的错误定位模型构建方面，我们首先根据距离度量测试方法对测试用例进行约减，由此降低执行结果判断和运行时信息收集等过程的代价，提高错误定位效率。其次，针对多缺陷场景下缺陷定位技术进行理论建模，并对比分析了主流的缺陷定位技术的效率。同时，针对多个错误相互干扰影响错误定位的问题，提出了两种基于不同聚类方式的解决方法。最后，针对流行的基于频谱的错误定位技术中存在的问题，提出了基于路径分析和信息熵的错误定位方法。. (4) 为了验证我们前面提出的方法的有效性，我们构建了一个实验平台，从GitHub、 Mozilla、SourceForge、Defect4J、NASA、AEEEM、PROMISE、SOFTLAB、MORPH及ReLink等开源网站和不同的数据集中下载大型软件及其相关演化版本信息作为实验对象，通过大量的统计性实验来定量地分析和论证我们所提出方法的准确度和时空效率。. 研究成果深化和丰富了已有的错误定位方法，扩大了进化优化算法在软件工程中的应用范围，在软件工程领域具有重要理论意义和应用价值。. 项目资助共发表论文36篇，其中，SCI论文16篇，国内学报论文10篇。申请国内发明专利10项，其中授权4项。