research-article

Using likely invariants for automated software fault localization

Authors:

Swarup Kumar Sahoo,

Vikram AdveAuthors Info & Claims

ACM SIGPLAN Notices, Volume 48, Issue 4

Pages 139 - 152

https://doi.org/10.1145/2499368.2451131

Published: 16 March 2013 Publication History

Abstract

We propose an automatic diagnosis technique for isolating the root cause(s) of software failures. We use likely program invariants, automatically generated using correct inputs that are close to the fault-triggering input, to select a set of candidate program locations which are possible root causes. We then trim the set of candidate root causes using software-implemented dynamic backwards slicing, plus two new filtering heuristics: dependence filtering, and filtering via multiple failing inputs that are also close to the failing input. Experimental results on reported software bugs of three large open-source servers show that we are able to narrow down the number of candidate bug locations to between 5 and 17 program expressions, even in programs that are hundreds of thousands of lines long.

References

[1]

Website. http://findbugs.sourceforge.net/.

[2]

Website. http://www.hpenterprisesecurity.com/products/hp-fortifysoftware-security-center/hp-fortify-static-code-analyzer/.

[3]

Website. http://www.coverity.com/products/coverity-save.html.

[4]

NIST: National Institute of Standards and Technology. Software errors cost U.S. economy $59.5 billion annually: NIST assesses technical needs of industry to improve software-testing. June 2002.

[5]

R. Abreu, P. Zoeteweij, and A. J. van Gemund. An evaluation of similarity coefficients for software fault localization. In 12th Pacific Rim International Symposium on Dependable Computing(PRDC), 2006.

Digital Library

[6]

V. Adve, C. Lattner, M. Brukman, A. Shukla, and B. Gaeke. LLVA: A low-level virtual instruction set architecture. In Proc. ACM/IEEE Int'l Symp. on Microarch. (MICRO), page 205,Washington, DC, USA, 2003. IEEE Computer Society.

Digital Library

[7]

S. Artzi, J. Dolby, F. Tip, and M. Pistoia. Directed test generation for effective fault localization. In Proceedings of the 19th international symposium on Software testing and analysis, ISSTA '10.

Digital Library

[8]

S. Artzi, J. Dolby, F. Tip, and M. Pistoia. Practical fault localization for dynamic web applications. In Proceedings of the 32nd ACM/IEEE International Conference on Software Engineering, 2010.

Digital Library

[9]

D. L. Bird and C. U. Munoz. Automatic generation of random selfchecking test cases. IBM Systems Journal, 22(3):229--245, 1983.

Digital Library

[10]

M. Bond. Diagnosing and Tolerating Bugs in Deployed Systems. PhD thesis, University of Texas at Austin, 2008.

Digital Library

[11]

R. N. Charette. Why Software Fails. Spectrum, IEEE, 42(9):42--49, September 2005.

Digital Library

[12]

H. Cleve and A. Zeller. Locating causes of program failures. In ICSE, 2005.

Digital Library

[13]

R. Cytron, J. Ferrante, B. K. Rosen, M. N.Wegman, and F. K. Zadeck. Efficiently computing static single assignment form and the control dependence graph. ACM Trans. on Prog. Langs. and Systs. (TOPLAS), pages 13(4):451--490, October 1991.

Digital Library

[14]

D. Dhurjati, S. Kowshik, and V. Adve. SAFECode: Enforcing alias analysis for weakly typed languages. In ACM SIGPLAN Conference on Programming Language Design and Implementation, 2006.

Digital Library

[15]

W. Dietz, P. Li, J. Regehr, and V. Adve. Understanding Integer Overflow in C/C++. In International Conference on Software Engineering, June 2012.

Digital Library

[16]

M. Dimitrov and H. Zhou. Anomaly-based bug prediction, isolation, and validation: an automated approach for software debugging. In ASPLOS, 2009.

Digital Library

[17]

D. Engler, B. Chelf, A. Chou, and S. Hallem. Checking system rules using system-specific, programmer-written compiler extensions. In Proceedings of the 4th conference on Symposium on Operating System Design & Implementation - Volume 4, OSDI'00, 2000.

Digital Library

[18]

M. D. Ernst, J. Cockrell,W. G. Griswold, and D. Notkin. Dynamically discovering likely program invariants to support program evolution. IEEE Trans. Software Eng., 2001.

Digital Library

[19]

J. E. Forrester and B. P. Miller. An empirical study of the robustness of windows nt applications using random testing. In Proceedings of the 4th conference on USENIX Windows Systems Symposium, 2000.

Digital Library

[20]

K. Glerum, K. Kinshumann, S. Greenberg, G. Aul, V. Orgovan, G. Nichols, D. Grant, G. Loihle, and G. C. Hunt. Debugging in the (very) large: ten years of implementation and experience. In SOSP, 2009.

Digital Library

[21]

P. Godefroid, N. Klarlund, and K. Sen. Dart: directed automated random testing. In Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, PLDI '05, 2005.

Digital Library

[22]

P. Godefroid, M. Y. Levin, and D. A. Molnar. Automated whitebox fuzz testing. In Network Distributed Security Symposium (NDSS). Internet Society, 2008.

[23]

N. Gupta, H. He, X. Zhang, and R. Gupta. Locating faulty code using failure-inducing chops. In ASE, 2005.

Digital Library

[24]

S. Hangal and M. S. Lam. Tracking down software bugs using automatic anomaly detection. In Proceedings of the International Conference on Software Engineering, 2002.

Digital Library

[25]

D. Jeffrey, N. Gupta, and R. Gupta. Effective and efficient localization of multiple faults using value replacement. In ICSM, 2009.

[26]

J. Jones, M. Harrold, and J. Stasko. Visualization of test information to assist fault localization. In Proceedings of the 24th international conference on Software engineering, 2002.

Digital Library

[27]

J. A. Jones and M. J. Harrold. Empirical evaluation of the tarantula automatic fault-localization technique. In ASE, 2005.

Digital Library

[28]

M. Jose and R. Majumdar. Cause clue clauses: error localization using maximum satisfiability. In PLDI, 2011.

Digital Library

[29]

C. Lattner and V. Adve. LLVM: A compilation framework for lifelong program analysis and transformation. In Proc. Conf. on Code Generation and Optimization, 2004.

Digital Library

[30]

B. Liblit, M. Naik, A. X. Zheng, A. Aiken, and M. I. Jordan. Scalable statistical bug isolation. In Proc. ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI), 2005.

Digital Library

[31]

L. Mariani, F. Pastore, and M. Pezze. Dynamic analysis for diagnosing integration faults. IEEE Transactions on Software Engineering, 37:486--508, 2011.

Digital Library

[32]

A. Mockus, N. Nagappan, and T. T. Dinh-Trong. Test coverage and post-verification defects: A multiple case study. In International Symposium on Empirical Software Engineering and Measurement, 2009.

Digital Library

[33]

S. Nagarakatte, J. Zhao, M. M. Martin, and S. Zdancewic. Softbound: highly compatible and complete spatial memory safety for c. SIGPLAN Not., 44(6):245--258, 2009.

Digital Library

[34]

N. Nethercote and J. Seward. Valgrind: A program supervision framework. Electronic notes in theoretical computer science, 89(2), 2003.

[35]

B. Pytlik, M. Renieris, S. Krishnamurthi, and S. P. Reiss. Automated fault localization using potential invariants. In Proceedings of the Workshop on Automated and Algorithmic Debugging, 2003.

[36]

J. Regehr, Y. Chen, P. Cuoq, E. Eide, C. Ellision, and X. Yang. Testcase reduction for c compiler bugs. In Submission, 2012.

[37]

S. K. Sahoo, J. Criswell, and V. Adve. An empirical study of reported bugs in server software with implications for automated bug diagnosis. In ICSE, 2010.

Digital Library

[38]

D. Scott. Making smart investments to reduce unplanned downtime. Tactical Guidelines TG-07-4033, Gartner Group, March 1999.

[39]

W. N. Sumner and X. Zhang. Automatic failure inducing chain computation through aligned execution comparison. In Technical Report 08-023, Purdue University, 2008.

[40]

W. N. Sumner and X. Zhang. Algorithms for automatically computing the causal paths of failures. In FASE, 2009.

Digital Library

[41]

W. N. Sumner and X. Zhang. Memory indexing: canonicalizing addresses across executions. In FSE, 2010.

Digital Library

[42]

J. Tucek, S. Lu, C. Huang, S. Xanthos, and Y. Zhou. Triage: diagnosing production run failures at the user's site. In SOSP, 2007.

Digital Library

[43]

B. Xin, W. N. Sumner, and X. Zhang. Efficient program execution indexing. In PLDI, 2008.

Digital Library

[44]

newblock A. Zeller. Isolating cause-effect chains from computer programs. In SIGSOFT '02: FSE, 2002.

Digital Library

[45]

A. Zeller and R. Hildebrandt. Simplifying and isolating failureinducing input. IEEE Transactions on Software Engineering, 2002.

Digital Library

[46]

X. Zhang, N. Gupta, and R. Gupta. Locating faults through automated predicate switching. In ICSE, 2006.

Digital Library

[47]

X. Zhang, N. Gupta, and R. Gupta. A study of effectiveness of dynamic slicing in locating real faults. Empirical Software Engineering, 2007.

Digital Library

[48]

X. Zhang, R. Gupta, and Y. Zhang. Precise dynamic slicing algorithms. In Proceedings of the 25th International Conference on Software Engineering, 2003.

Digital Library

Cited By

Vancsics BHorváth FSzatmári ABeszédes Á(2022)Fault localization using function call frequenciesJournal of Systems and Software10.1016/j.jss.2022.111429193:COnline publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1016/j.jss.2022.111429
Devecsery DChen PFlinn JNarayanasamy S(2018)Optimistic Hybrid AnalysisACM SIGPLAN Notices10.1145/3296957.317715353:2(348-362)Online publication date: 19-Mar-2018
https://dl.acm.org/doi/10.1145/3296957.3177153
Devecsery DChen PFlinn JNarayanasamy SShen XTuck JBianchini RSarkar V(2018)Optimistic Hybrid AnalysisProceedings of the Twenty-Third International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3173162.3177153(348-362)Online publication date: 19-Mar-2018
https://dl.acm.org/doi/10.1145/3173162.3177153
Show More Cited By

Index Terms

Using likely invariants for automated software fault localization
1. Hardware
  1. Hardware test
  2. Robustness
2. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis
        Software testing and debugging

Recommendations

A learning-to-rank based fault localization approach using likely invariants
ISSTA 2016: Proceedings of the 25th International Symposium on Software Testing and Analysis

Debugging is a costly process that consumes much of developer time and energy. To help reduce debugging effort, many studies have proposed various fault localization approaches. These approaches take as input a set of test cases (some failing, some ...
Using likely invariants for automated software fault localization
ASPLOS '13: Proceedings of the eighteenth international conference on Architectural support for programming languages and operating systems

We propose an automatic diagnosis technique for isolating the root cause(s) of software failures. We use likely program invariants, automatically generated using correct inputs that are close to the fault-triggering input, to select a set of candidate ...
Using likely invariants for automated software fault localization
ASPLOS '13

We propose an automatic diagnosis technique for isolating the root cause(s) of software failures. We use likely program invariants, automatically generated using correct inputs that are close to the fault-triggering input, to select a set of candidate ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 48, Issue 4

ASPLOS '13

April 2013

540 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/2499368

Issue’s Table of Contents

ASPLOS '13: Proceedings of the eighteenth international conference on Architectural support for programming languages and operating systems
March 2013
574 pages
ISBN:9781450318709
DOI:10.1145/2451116
General Chair:
Vivek Sarkar
Rice University, USA
,
Program Chair:
Rastislav Bodik
University of California, Berkeley, USA

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 March 2013

Published in SIGPLAN Volume 48, Issue 4

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

74
Total Citations
View Citations
1,824
Total Downloads

Downloads (Last 12 months)49
Downloads (Last 6 weeks)2

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Vancsics BHorváth FSzatmári ABeszédes Á(2022)Fault localization using function call frequenciesJournal of Systems and Software10.1016/j.jss.2022.111429193:COnline publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1016/j.jss.2022.111429
Devecsery DChen PFlinn JNarayanasamy S(2018)Optimistic Hybrid AnalysisACM SIGPLAN Notices10.1145/3296957.317715353:2(348-362)Online publication date: 19-Mar-2018
https://dl.acm.org/doi/10.1145/3296957.3177153
Devecsery DChen PFlinn JNarayanasamy SShen XTuck JBianchini RSarkar V(2018)Optimistic Hybrid AnalysisProceedings of the Twenty-Third International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3173162.3177153(348-362)Online publication date: 19-Mar-2018
https://dl.acm.org/doi/10.1145/3173162.3177153
Asăvoae IAsăvoae MRiesco A(2018)Slicing from formal semantics: Chisel—a tool for generic program slicingInternational Journal on Software Tools for Technology Transfer10.1007/s10009-018-0500-y20:6(739-769)Online publication date: 17-Jul-2018
https://doi.org/10.1007/s10009-018-0500-y
Ma LDing Z(2018)Software Bug Localization Based on Key Range InvariantsSoftware Analysis, Testing, and Evolution10.1007/978-3-030-04272-1_2(20-32)Online publication date: 20-Nov-2018
https://doi.org/10.1007/978-3-030-04272-1_2
Chen YYing MLiu DAlim AChen FChen MBultan TSen K(2017)Effective online software anomaly detectionProceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3092703.3092730(136-146)Online publication date: 10-Jul-2017
https://dl.acm.org/doi/10.1145/3092703.3092730
RadhaKrishna VAljawarneh SAl-Shargabi B(2015)Design and Analysis of Novel Kernel Measure for Software Fault LocalizationProceedings of the The International Conference on Engineering & MIS 201510.1145/2832987.2833042(1-5)Online publication date: 24-Sep-2015
https://dl.acm.org/doi/10.1145/2832987.2833042
Birch GFischer BPoppleton M(2015)Fast Model-Based Fault Localisation with Test SuitesTests and Proofs10.1007/978-3-319-21215-9_3(38-57)Online publication date: 17-Jul-2015
https://doi.org/10.1007/978-3-319-21215-9_3
Gerten MLathrop JCohen MChristakis MPradel M(2024)Traceback: A Fault Localization Technique for Molecular ProgramsProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3652138(415-427)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3652138
Kuo JHsieh TChen Y(2024)The Study of Student Program Analysis and Feedback System2024 IEEE 48th Annual Computers, Software, and Applications Conference (COMPSAC)10.1109/COMPSAC61105.2024.00231(1546-1547)Online publication date: 2-Jul-2024
https://doi.org/10.1109/COMPSAC61105.2024.00231
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents