research-article

Automatic software fault localization using generic program invariants

Authors:

Alberto González,

Peter Zoeteweij,

Arjan J. C. van GemundAuthors Info & Claims

SAC '08: Proceedings of the 2008 ACM symposium on Applied computing

Pages 712 - 717

https://doi.org/10.1145/1363686.1363855

Published: 16 March 2008 Publication History

Abstract

Despite extensive testing in the development phase, residual defects can be a great threat to dependability in the operational phase. This paper studies the utility of low-cost, generic invariants ("screeners") in their capacity of error detectors within a spectrum-based fault localization (SFL) approach aimed to diagnose program defects in the operational phase. The screeners considered are simple bit-mask and range invariants that screen every load/store and function argument/return program point. Their generic nature allows them to be automatically instrumented without any programmer-effort, while training is straightforward given the test cases available in the development phase. Experiments based on the Siemens program set demonstrate diagnostic performance that is similar to the traditional, development-time application of SFL based on the program pass/fail information known before-hand. This diagnostic performance is currently attained at an average 14% screener execution time overhead, but this overhead can be reduced at limited performance penalty.

References

[1]

R. Abreu, P. Zoeteweij, and A. J. C. van Gemund. An evaluation of similarity coefficients for software fault localization. In Proc. PRDC '06, pages 39--46, 2006.

Digital Library

[2]

R. Abreu, P. Zoeteweij, and A. J. C. van Gemund. On the accuracy of spectrum-based fault localization. In Proc. TAIC PART'07, Sep 2007.

Digital Library

[3]

A. Avižienis, J.-C. Laprie, B. Randell, and C. E. Landwehr. Basic concepts and taxonomy of dependable and secure computing. IEEE Trans. Dependable Sec. Comput., 1(1):11--33, 2004.

Digital Library

[4]

M. Y. Chen, E. Kiciman, E. Fratkin, A. Fox, and E. Brewer. Pinpoint: Problem determination in large, dynamic internet services. In Proc. of DSN'02, pages 595--604. IEEE CS, 2002.

Digital Library

[5]

H. Cleve and A. Zeller. Locating causes of program failures. In Proc. ICSE'05, Missouri, USA, 2005.

Digital Library

[6]

A. da Silva Meyer, A. A. Franco Farcia, and A. Pereira de Souza. Comparison of similarity coefficients used for cluster analysis with dominant markers in maize (Zea mays L). Genetics and Molecular Biology, 27(1):83--91, 2004.

[7]

V. Dallmeier, C. Lindig, and A. Zeller. Lightweight defect localization for Java. In A. P. Black, editor, Proc. ECOOP 2005, volume 3586 of LNCS, pages 528--550. Springer-Verlag, 2005.

Digital Library

[8]

M. D. Ernst, J. Cockrell, W. G. Griswold, and D. Notkin. Dynamically discovering likely program invariants to support program evolution. In Proc. ICSE'99, pages 213--224, 1999.

Digital Library

[9]

M. D. Ernst, J. H. Perkins, P. J. Guo, S. McCamant, C. Pacheco, M. S. Tschantz, and C. Xiao. The daikon system for dynamic detection of likely invariants. In Science of Computer Programming, 2007.

Digital Library

[10]

A. González. Automatic error detection techniques based on dynamic invariants, Aug. 2007. Master's thesis.

[11]

S. Hangal and M. S. Lam. Tracking down software bugs using automatic anomaly detection. In Proc. ICSE'02, May 2002.

Digital Library

[12]

M. J. Harrold, G. Rothermel, R. Wu, and L. Yi. An empirical investigation of program spectra. ACM SIGPLAN Notices, 33(7):83--90, 1998.

Digital Library

[13]

M. Hutchins, H. Foster, T. Goradia, and T. Ostrand. Experiments of the effectiveness of dataflow- and controlflow-based test adequacy criteria. In Proc. ICSE'94, pages 191--200, Los Alamitos, CA, USA, 1994. IEEE CS Press.

Digital Library

[14]

A. K. Jain and R. C. Dubes. Algorithms for clustering data. Prentice-Hall, Inc., 1988.

Digital Library

[15]

J. A. Jones and M. J. Harrold. Empirical evaluation of the tarantula automatic fault-localization technique. In Proc. ASE'05, pages 273--282, NY, USA, 2005.

Digital Library

[16]

J. O. Kephart and D. M. Chess. The vision of autonomic computing. Computer, 36(1):41--50, January 2003.

Digital Library

[17]

C. Lattner and V. Adve. LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation. In Proc. CGO'04, Palo Alto, California, Mar 2004.

Digital Library

[18]

C. Liu, L. Fei, X. Yan, J. Han, and S. P. Midkiff. Statistical debugging: A hypothesis testing-based approach. IEEE Transactions on Software Engineering, 32(10):831--848, 2006.

Digital Library

[19]

T. Menzies, D. Owen, and J. Richardson. The strangest thing about software. Computer, 40(1):54--60, January 2007.

Digital Library

[20]

D. Patterson, A. Brown, P. Broadwell, G. Candea, M. Chen, J. Cutler, P. Enriquez, A. Fox, E. Kiciman, M. Merzbacher, D. Oppenheimer, N. Sastry, W. Tetzlaff, J. Traupman, and N. Treuhaft. Recovery Oriented Computing (ROC): Motivation, definition, techniques, and case studies. Technical Report UCB/CSD-02-1175, U. C. Berkeley, March 2002.

Digital Library

[21]

B. Pytlik, M. Renieris, S. Krishnamurthi, and S. Reiss. Automated fault localization using potential invariants. In Proc. AADEBUG'03, 2003.

[22]

P. Racunas, K. Constantinides, S. Manne, and S. Mukherjee. Perturbation-based fault screening. In Proc. HPCA'2007, pages 169--180, Feb. 2007.

Digital Library

[23]

M. Renieris and S. P. Reiss. Fault localization with nearest neighbor queries. In Proc. ASE'03, Montreal, Canada, October 2003. IEEE CS.

[24]

X. Zhang, H. He, N. Gupta, and R. Gupta. Experimental evaluation of using dynamic slices for fault location. In Proc. AADEBUG'05, pages 33--42, Monterey, California, USA, 2005. ACM Press.

Digital Library

Cited By

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
Sun DYue XLiu CQin HHu H(2024)SFLVis: visual analysis of software fault localizationJournal of Visualization10.1007/s12650-024-00979-x27:4(585-602)Online publication date: 2-Apr-2024
https://doi.org/10.1007/s12650-024-00979-x
Abreu AMacedo NMendes A(2023)Exploring Automatic Specification Repair in Dafny Programs2023 38th IEEE/ACM International Conference on Automated Software Engineering Workshops (ASEW)10.1109/ASEW60602.2023.00019(105-112)Online publication date: 11-Sep-2023
https://doi.org/10.1109/ASEW60602.2023.00019
Show More Cited By

Index Terms

Automatic software fault localization using generic program invariants
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis
        Software testing and debugging

Recommendations

Factorising the Multiple Fault Localization Problem: Adapting Single-Fault Localizer to Multi-fault Programs
APSEC '12: Proceedings of the 2012 19th Asia-Pacific Software Engineering Conference - Volume 01

Software failures are not rare and fault localizations always an important but laborious activity. Since there is no guarantee that no more than one fault exists in a faulty program, the approach to locate all the faults is necessary. Spectrum-based ...
Extended comprehensive study of association measures for fault localization

Spectrum-based fault localization is a promising approach to automatically locate root causes of failures quickly. Two well-known spectrum-based fault localization techniques, Tarantula and Ochiai, measure how likely a program element is a root cause of ...
Iterative Feedback-Based Fault Localization Approach
SEAA '11: Proceedings of the 2011 37th EUROMICRO Conference on Software Engineering and Advanced Applications

Most current fault-localization approaches merely use the information from testing to locate faults, assuming that test cases satisfying a certain test adequacy criterion can provide adequate information for fault localization. Unfortunately however, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SAC '08: Proceedings of the 2008 ACM symposium on Applied computing

March 2008

2586 pages

ISBN:9781595937537

DOI:10.1145/1363686

Conference Chairs:
Roger L. Wainwright
University of Tulsa
,
Hisham M. Haddad
Kennesaw State University

Copyright © 2008 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]

Sponsors

SIGAPP: ACM Special Interest Group on Applied Computing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 March 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Netherlands Ministry of Economic Affairs

Conference

SAC '08

Sponsor:

SIGAPP

SAC '08: The 2008 ACM Symposium on Applied Computing

March 16 - 20, 2008

Fortaleza, Ceara, Brazil

Acceptance Rates

Overall Acceptance Rate 1,650 of 6,669 submissions, 25%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
479
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
Sun DYue XLiu CQin HHu H(2024)SFLVis: visual analysis of software fault localizationJournal of Visualization10.1007/s12650-024-00979-x27:4(585-602)Online publication date: 2-Apr-2024
https://doi.org/10.1007/s12650-024-00979-x
Abreu AMacedo NMendes A(2023)Exploring Automatic Specification Repair in Dafny Programs2023 38th IEEE/ACM International Conference on Automated Software Engineering Workshops (ASEW)10.1109/ASEW60602.2023.00019(105-112)Online publication date: 11-Sep-2023
https://doi.org/10.1109/ASEW60602.2023.00019
Wong WGao RLi YAbreu RWotawa FLi D(2023)Software Fault Localization: an Overview of Research, Techniques, and ToolsHandbook of Software Fault Localization10.1002/9781119880929.ch1(1-117)Online publication date: 21-Apr-2023
https://doi.org/10.1002/9781119880929.ch1
Jarman DBerry JSmith RThung FLo D(2022)Legion: Massively Composing Rankers for Improved Bug Localization at AdobeIEEE Transactions on Software Engineering10.1109/TSE.2021.307521548:8(3010-3024)Online publication date: 1-Aug-2022
https://doi.org/10.1109/TSE.2021.3075215
Lei YXie HZhang TYan MXu ZSun C(2022)Feature-FL: Feature-Based Fault LocalizationIEEE Transactions on Reliability10.1109/TR.2022.314045371:1(264-283)Online publication date: Mar-2022
https://doi.org/10.1109/TR.2022.3140453
Konate SLebrat LCruz RSmith EBradley AFookes CSalvado O(2021)A Comparison of Saliency Methods for Deep Learning Explainability2021 Digital Image Computing: Techniques and Applications (DICTA)10.1109/DICTA52665.2021.9647419(01-08)Online publication date: Nov-2021
https://doi.org/10.1109/DICTA52665.2021.9647419
Reis SAbreu RD'Amorim M(2019)Demystifying the combination of dynamic slicing and spectrum-based fault localizationProceedings of the 28th International Joint Conference on Artificial Intelligence10.5555/3367471.3367705(4760-4766)Online publication date: 10-Aug-2019
https://dl.acm.org/doi/10.5555/3367471.3367705
Zhang BZhang HChen JHao DMoscato P(2019)Automatic Discovery and Cleansing of Numerical Metamorphic Relations2019 IEEE International Conference on Software Maintenance and Evolution (ICSME)10.1109/ICSME.2019.00035(235-245)Online publication date: Sep-2019
https://doi.org/10.1109/ICSME.2019.00035
Lee SKim JLee E(2019)Dynamic Invariant Prioritization-Based Fault LocalizationProceedings of the 13th International Conference on Ubiquitous Information Management and Communication (IMCOM) 201910.1007/978-3-030-19063-7_55(682-693)Online publication date: 23-May-2019
https://doi.org/10.1007/978-3-030-19063-7_55
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 Table of Contents