面向理解的软件错误定位方法：状态转移概率推理建模

It is difficult to understand the software errors by using existing software fault localization methods. To solve this problem, a comprehension oriented software fault localization method is proposed by integrating the theories and techniques of program analysis, model reasoning, statistics,and optimization. Test case selection, fault localization, and fault comprehension, are integrated into a uniform framework. Firstly, two criteria "test case prioritization by similarity of failure statement coverage vector", "test case selection by equivalent failure execution coverage division" are defined, and a test case selection model is created based on these criteria. Thus test cases which can improve the effectiveness of the fault localization are selected. Next, a software fault localization model, i.e. lightweight state transition probability reasoning model, is built. During this process, dynamic data dependence is derived by analyzing the static data dependence of the program and the dynamic control dependence of the successful test case executions, program states are abstracted, and state transition probabilities along the control flow and data flow are computed. As a result, this model sufficiently analyzes the exection state transitions and the interactions between program statements. Finally, a software fault comprehension overview is defined. Failure related control dependence and data dependence, values of failure execution, and expected states as well as expressions of the suspicious program point are analyzed to assist developers to understand the cause of software failure. This project lays a theoretical foundation for automatic software debugging and software reliability enhancement.

针对已有错误定位方法难于理解软件错误等问题，综合运用程序分析、模型推理、统计、优化算法等理论与技术，提出面向理解的软件错误定位方法，将测试用例优选、错误定位、理解有机结合：首先，定义"失效语句覆盖向量相似度优先排序"和"失效执行覆盖等价划分优化选择"准则，在此基础上建立测试用例优选模型，选择有利于提高错误定位有效性的测试用例；然后，定义并构建软件错误定位模型-轻量级的状态转移概率推理模型，解析程序静态信息和成功测试用例执行时的动态控制依赖，推导动态数据依赖，抽象程序状态并统计其沿控制流及数据流转移的概率，从而充分分析程序执行状态转移及语句间的相互影响，有效定位缺陷，并为软件错误理解奠定基础；最后，定义软件错误理解全景视图，建模推导失效相关的控制依赖及数据依赖、失效执行数据、可疑程序点的期望状态和表达式，辅助开发人员理解软件失效的产生原因。为软件自动化调试、增强软件可靠性奠定理论基础。

针对已有错误定位方法难于理解软件错误等问题，综合运用程序分析、模型推理、统计、优化算法等理论与技术，提出面向理解的软件错误定位方法，将测试用例选择、错误定位、理解有机结合，为软件自动化调试提供一种新思路。项目组发表研究论文15篇，其中SCI国际期刊3篇，一级学报4篇，EI国际会议3篇，核心期刊5篇；获国家发明专利2项。取得的主要研究成果如下。（1）提出面向有效错误定位的测试用例优选方法，突破已有方法在提高错误定位有效性方面的局限性。定义了“失效语句覆盖向量相似度优先排序”准则和“失效执行覆盖等价划分优化选择”准则，并基于这两条准则建立测试用例优选模型，解决适于错误定位的测试用例的选择问题，提高错误定位的有效性。（2）定义并构建了一种新的软件错误定位模型——轻量级的状态转移概率推理模型，解决有效定位软件缺陷并为软件错误理解奠定基础的问题。针对已有的模型检查错误定位方法建立系统模型复杂度高，覆盖分析方法缺少对程序执行状态的描述、忽略了程序感染状态的传播等问题，利用程序的静态信息和成功测试用例执行时的动态控制依赖，推导动态数据依赖，降低计算复杂度，在此基础上抽象程序状态、统计分析其沿控制流及数据流转移的概率。不但充分分析程序的执行状态转移及程序元素间的相互影响，有效定位软件缺陷，还为软件错误理解提供充分的程序语义及执行状态信息。（3）针对已有错误定位方法缺少对失效产生原因的分析及解释的问题，定义了软件错误理解全景视图，并建模推导失效相关的控制及数据依赖上下文、失效执行路径上的值、可疑程序点的期望状态和期望表达式，从而辅助开发人员理解软件错误，使其有效地发现、应用及验证软件缺陷修正方法。