一种基于最弱前置条件的软件错误定位算法

doi:10.3969/j.issn.0372-2112.2019.01.004

PDF(1476 KB)

电子学报 ›› 2019, Vol. 47 ›› Issue (1) : 25-32. DOI: 10.3969/j.issn.0372-2112.2019.01.004

学术论文

一种基于最弱前置条件的软件错误定位算法

李雅^1,2, 黄少滨², 李艳梅², 迟荣华², 郎大鹏²

作者信息 +

Technique of Software Fault Localization Based on Weakest Pre-condition

LI Ya^1,2, HUANG Shao-bin², LI Yan-mei², CHI Rong-hua², LANG Da-peng²

Author information +

文章历史 +

摘要

错误定位是软件调试中非常耗时费力的活动之一，自动错误定位技术可以有效地提高调试效率，降低调试成本.基于最弱前置条件的错误定位技术，首先计算出程序需要满足的最弱前置条件，并为其构造错误分析图；然后在错误分析图上依照失败测试用例进行初始化标记；最后限定分析图的输入和输出，自顶向下再次对其进行标记，找到冲突的结点，从而进行错误定位.实验结果表明，相对于其它方法，文中提出的方法能有效地提高程序错误定位的效率，使得调试人员只需检查更少的语句即可找到出错的位置.

Abstract

Fault localization is one of the most time-consuming activities in software debugging,and automatic fault localization technique can effectively improve the efficiency and reduce the cost.In this paper,a fault localization technique based on weakest pre-condition is proposed.Firstly,we compute the weakest pre-condition,and construct the fault analysis graph.Secondly,label the nodes according to the failing test case.Finally,label the graph top-down again while the output is limited to true,and the input cannot be changed.The conflicting nodes were found as the possible errors.The experimental results suggest that the proposed method in this paper has better performance compared to other methods.So that the debugger can only check fewer statements to find out the location of the error.

导出引用

李雅, 黄少滨, 李艳梅, 迟荣华, 郎大鹏. 一种基于最弱前置条件的软件错误定位算法[J]. 电子学报, 2019, 47(1): 25-32. https://doi.org/10.3969/j.issn.0372-2112.2019.01.004

LI Ya, HUANG Shao-bin, LI Yan-mei, CHI Rong-hua, LANG Da-peng. Technique of Software Fault Localization Based on Weakest Pre-condition[J]. Acta Electronica Sinica, 2019, 47(1): 25-32. https://doi.org/10.3969/j.issn.0372-2112.2019.01.004

中图分类号： TP316

参考文献

[1] JOSE M,MAJUMDAR R.Cause clue clauses:error localization using maximum satisfiability[J].Acm Sigplan Notices,2010,46(6):437-446.
[2] WEN W,LI B,SUN X,et al.Program slicing spectrum-based software fault localization[A].Proceedings of the 23rd International Conference on Software Engineering & Knowledge Engineerin[C].Miami:DBLP,2011.213-218.
[3] HOLZMANN G J,SMITH M H.Software model checking[A].Proceedings of the IFIP TC6 WG6.1 Joint International Conference on Formal Description Techniques for Distributed Systems and Communication Protocols (FORTE XⅡ) and Protocol Specification,Testing and Verification (PSTV XIX)[C].Netherlands:ACM,1999.1729-1739.
[4] 文万志,李必信,孙小兵,等.一种基于层次切片谱的软件错误定位技术[J].软件学报,2013(5):977-992. WEN W-Z,LI B-X,SUN X-B,et al.Technique of software fault localization based on hierarchical slicing spectrum[J].Journal of Sotfware,2013(5):977-992.(in Chinese)
[5] LEI Y,MAO X,DAI Z,et al.Effective statistical fault localization using program slices[A].Proceedings of the IEEE 36th Annual Computer Software and Applications Conference[C].Washington DC:IEEE,2012.1-10.
[6] 曹鹤玲,姜淑娟,鞠小林,等.基于动态切片和关联分析的错误定位方法[J].计算机学报,2015(11):2188-2202. CAO H-L,JIANG S-J,JU X-L,et al.Fault localization based on dynamic slicing and association analysis[J].Chinese Journal of Computers,2015(11):2188-2202.(in Chinese)
[7] ZHANG X,HE H,GUPTA N,et al.Experimental evaluation of using dynamic slices for fault location[A].Proceedings of the Sixth International Symposium on Automated Analysis-driven Debugging[C].California:ACM,2005.33-42.
[8] 赵磊,王丽娜,高东明,等.基于关联挖掘的软件错误定位方法[J].计算机学报,2012,35(12):2528-2540. ZHAO L,WANG L-N,GAO D-M,et al.Mining associations to improve the effectiveness of fault localization[J].Chinese Journal of Computers,2012,35(12):2528-2540.(in Chinese)
[9] ABREU R,ZOETEWEIJ P,VAN GEMUND A J C.On the accuracy of spectrum-based fault localization[A].Proceedings of the Testing:Academic and Industrial Conference Practice and Research Techniques[C].Washington DC:IEEE,2007.89-98.
[10] JONES J A.Empirical evaluation of the tarantula automatic fault-localization technique[A].Proceedings of the 20th IEEE/ACM International Conference on Automated software Engineering[C].New York:ACM,2005.273-282.
[11] 王建峰,魏长安,盛云龙,等.基于错误交互集的组合测试软件故障定位方法[J].电子学报,2014,42(6):1173-1178. WANG Jian-feng,WEI Cang-an,SHENG Yun-long,et al.Locating errors in combinatorial testing using set of possible faulty interactions[J].Acta Electronica Sinica,2014,42(6):1173-1178.(in Chinese)
[12] 曹鹤玲,姜淑娟.基于Chameleon聚类分析的多错误定位方法[J].电子学报,2017,45(2):394-400. Cao He-ling,JIANG Shu-juan.Multiple-fault localization based on chameleon clustering[J].Acta Electronica Sinica,2017,45(2):394-400.(in Chinese)
[13] GRIESMAYER A,STABER S,BLOEM R.Fault localization using a model checker[J].Software Testing Verification & Reliability,2010,20(2):149-173.
[14] WANG C,YANG Z,IVANCIC F,,et al.Whodunit? Causal analysis for counterexamples[J].Lecture Notes in Computer Science,2006,4218:82-95.
[15] 黄宏涛,黄少滨,陈志远,等.基于克雷格插值的反例理解方法[J].吉林大学学报:理学版,2013,51(1):94-100. HUANG H-T,HUANG S-B,CHEN Z-Y,et al.Understanding counterexamples based on craig interpolation[J].Journal of Jilin University (Science Edition),2013,51(1):94-100.(in Chinese)
[16] JOSE M,MAJUMDAR R.Cause clue clauses:error localization using maximum satisfiability[J].Acm Sigplan Notices,2010,46(6):437-446.
[17] 徐勇,毋国庆,袁梦霆.结合Craig插值分析的软件错误诊断方法[J].电子学报,2016,44(10):2514-2521. XU Yong,WU Guo-qing,YUAN Meng-ting.Software fault localization based on model-Based diagnosis combined craig interpolant analysis[J].Acta Electronica Sinica,2016,44(10):2514-2521.(in Chinese)
[18] HUTH M,RYAN M.Logic in Computer Science:Modeling and Reasoning About Systems[M].London:Cambridge University Press,2004.201-205.
[19] HUTCHINS M,FOSTER H,GORADIA T,et al.Experiments on the effectiveness of dataflow and control-flow-based test adequacy criteria[A].Proceedings of 16th International Conference on Software Engineering[C].USA:IEEE,1994.191-200.
[20] JOSE M,MAJUMDAR R.Cause clue clauses:error localization using maximum satisfiability[J].Acm Sigplan Notices,2010,46(6):437-446.
[21] RENIERIS M,REISS SE.Fault localization with nearest neighbor queries[A].Proceedings of the 18th International Conference Automated Software Engineering (ASE 2003)[C].Quebec:IEEE,2003.30-39.
[22] GROCE A,CHAKI S,KROENING D,et al.Error explanation with distance metrics[J].International Journal on Software Tools for Technology Transfer,2006,8(3):229-247.
[23] GROCE A,VISSER W.What went wrong:explaining counterexamples[A].Proceedings of the 10th International Conference on Model Checking Software[C].Portland:Springer-Verlag,2002.121-136.