一种基于加权软件行为图挖掘的软件错误定位方法

Fault Localization Based on Weighted Software Behavior Graph Mining

已有错误定位方法通常仅给出可疑语句排序而缺少必要的上下文信息,导致难于理解软件失效的产生原因.为了解决该问题,定义了加权软件行为图来表示成功和失败的程序执行路径,由于图中边的权重表示了路径的执行频率,因此与LEAP方法相比,可以较好地分析与循环和递归等结构相关的软件错误.在此基础上,执行基于分支限界搜索的加权软件行为图挖掘算法,识别成功和失败执行之间最有差异的子图来获得错误签名,不但可以有效定位错误位置,还能输出缺陷语句相关的执行路径,从而提供失效产生的上下文.分析Siemens基准测试集和flex程序的结果表明,在检查相同百分比的语句的情况下,文中方法可以比Tarantula方法和LEAP方法定位到更多的错误.特别是对于冗余代码、缺失代码和变量替换,以及会直接改变执行路径类的错误,文中方法具有较高的定位精度.

The result of most fault localization approaches are given in the form of suspicious statement sequence ranking in descending order.However,examining a suspicious statement in isolation is hard for developers to understand the cause of failure,often they need more context information associated with the error.To solve this problem,this paper proposed a weighted software behavior graph to represent the path of passed execution or failed execution.It uses the execution frequency as weights,so that it can better handle loops,recursive and other structures than LEAP.Then,branch and bound search graph mining algorithm is performed on the weighted software behavior graphs to identify differences between passed and failed weighted software behavior graph as a bug signature.The proposed approach can not only localize the fault but also provide the failure context to facilitate fault comprehension.Experimental results on Siemens and Flex showed that the proposed approach can localize more faults than Tarantula and LEAP,when examining the same percent of code.In particular,the proposed approach has higher fault localization accuracy,especially in dealing with redundant code,missing codes,variable substitution errors,and errors that will directly change the execution path.