电子学报 ›› 2016, Vol. 44 ›› Issue (10): 2514-2521.DOI: 10.3969/j.issn.0372-2112.2016.10.033

• 学术论文 • 上一篇    下一篇

结合Craig插值分析的软件错误诊断方法

徐勇1,2, 毋国庆1, 袁梦霆1   

  1. 1. 武汉大学计算机学院, 湖北武汉 430072;
    2. 广东肇庆学院数学与统计学院, 广东肇庆 526061
  • 收稿日期:2015-11-03 修回日期:2016-02-16 出版日期:2016-10-25
    • 作者简介:
    • 徐勇,男,1977年生,博士生,主要研究方向为软件工程、软件调试.E-mail:xyus@whu.edu.cn;毋国庆,男,1954年生,教授、博士生导师,主要研究领域为软件需求工程、形式化方法.E-mail:wgq@whu.edu.cn
    • 基金资助:
    • 国家自然科学基金 (No.91118003,No.61003071); 深圳战略性新兴产业发展专项资金 (No.JCYJ20120616135936123); 中央高校基本科研业务费专项资金 (No.3101046,No.201121102020006)

Software Fault Localization Based on Model-Based Diagnosis Combined Craig Interpolant Analysis

XU Yong1,2, WU Guo-qing1, YUAN Meng-ting1   

  1. 1. Computer School, Wuhan University, Wuhan, Hubei 430072, China;
    2. School of Mathematics and Statistics, Zhaoqing University, Zhaoqing, Guangdong 526061, China
  • Received:2015-11-03 Revised:2016-02-16 Online:2016-10-25 Published:2016-10-25

摘要:

基于模型诊断(MBD)的理论应用到软件错误定位中取得了一定的效果.但是经典MBD理论基于元件间独立地发生故障这一假设,导致软件错误定位的结果中存在假阳性的诊断.论文对现有基于MBD的软件错误定位方法进行了改进,提出了冲突中元件的冗余分析方法.该方法既包括了基于Craig插值的元件冗余分析机制,同时利用条件语句取值的二元性(真或假)的特点,对冲突中的条件语句元件进行软件错误的无相关分析.实验结果表明:冲突中的元件冗余分析方法可以有效地减少诊断的假阳性率,将诊断结果数减少了48.4%,碰集树生成的结点数减少了47.6%.

关键词: 基于模型诊断, 软件错误定位, 冗余分析, Craig插值

Abstract:

Model-based diagnosis,an intelligent diagnosis theory has been successfully applied in software fault localization with promising results.However,traditional MBD relies on the assumption that components in the system fail dependently which makes the diagnoses with high false positives in software fault localization.In this paper,a component redundancy analysis approach is presented.The approach not only uses Craig interpolant to filter redundant components,but also employs a fact that a branch predicate evaluates to either true or false to filter some branch condition components.Experimental results show that the proposed approach effectively reduces the false positive rates of diagnoses,i.e.,reducing the number of diagnosis by 48.4%,and reducing the number of nodes of hitting set tree generated during diagnosis computation by 47.6%.

Key words: model-based diagnosis (MBD), fault localization, redundancy analysis, Craig interpolant

中图分类号: