基于频繁子图挖掘和粒子群优化的软件错误定位

Any faults can affect the quality of the software significantly and may cause a serious consequence to the national information security and software industry. Software fault localization is an advanced subject in the field of software testing. However, traditional fault locating techniques suffered from some insufficiencies, such as the inaccuracy of locating faults, lack of context information, low efficiency in locating multiple bugs simultaneously. Our previous studies show that data mining can improve the efficiency of fault localization and evolutionary optimization has advantages in search of a solution. Therefore, this project aids in addressing these problems by data mining and evolutionary optimization. The main contents include three aspects. First, we identify coincidental correctness test cases by clustering analysis to mitigate the negative impact on fault localization, and mine the context information of the fault by frequent subgraph mining; thus, we propose a fault localization based on frequent subgraph mining. Second, we use dynamic slicing to narrow the range of the faults and use particle swarm optimization algorithm to search the solution space, and convert multiple-fault localization to solve the problem by searching; thus, we propose a fault localization based on particle swarm optimization. Finally, we develop a theoretical framework and prototype tool based on the proposed approaches and conduct the experimental verification by the large open software in industrial practice. This project, which helps improve the efficiency of fault localization and guarantees the software quality, is of great significance and application prospect to the national economy and information industry.

软件错误影响软件质量，会给国家信息安全和软件产业造成损失或灾难。软件错误定位是软件测试领域的前沿课题，传统错误定位方法存在定位精度不高、定位所需上下文信息缺乏、难以有效定位多个错误等不足。我们前期研究表明数据挖掘可以提高错误定位效率，进化优化在搜索求解方面具有优势。本项目拟采用数据挖掘和进化优化进行软件错误定位研究。研究内容包括：应用聚类分析识别偶然正确性测试用例，并消除偶然正确性的不利影响，采用频繁子图挖掘错误语句相关的上下文信息，提出基于频繁子图挖掘的错误定位方法；应用动态切片缩小错误定位范围，采用粒子群优化算法搜索解空间，将多错误问题转换为搜索求解的问题，提出基于粒子群优化算法的多错误定位方法；构造一套检测大型开源软件系统的错误定位理论框架和原型工具，应用于工业实践。本项目的顺利开展有利于提高软件错误定位的效率，为软件质量提供保障，对国民经济和信息产业发展具有重要意义和应用价值。

本项目研究基于数据挖掘和进化优化的软件错误定位。借鉴聚类分析技术和粒子群优化算法，开展软件错误定位研究，构造一套适合开源软件系统的错误定位理论框架和原型工具。研究成果如下：（1）应用模糊ｃ均值聚类识别偶然正确性测试用例，消除偶然正确性对软件错误定位效率的不利影响，提出面向有效错误定位的偶然正确性识别方法。（2）研究偶然正确性对怀疑度计算公式错误定位效率的影响，提出怀疑度计算公式受偶然正确性影响理论分析框架。（3）聚类分析将失败程序执行轨迹分簇，每簇包含一个错误，采用并行调试模式同时定位程序中的多个错误，提出基于Chameleon聚类分析的软件多错误定位方法。（4）基于搜索的软件工程思想，将多错误定位问题转换为搜索求最优解问题，提出基于改进粒子群算法的软件多错误定位方法。