research-article

Exploiting count spectra for Bayesian fault localization

Authors:

Alberto Gonzalez-Sanchez,

Arjan J. C. van GemundAuthors Info & Claims

PROMISE '10: Proceedings of the 6th International Conference on Predictive Models in Software Engineering

Article No.: 12, Pages 1 - 10

https://doi.org/10.1145/1868328.1868347

Published: 12 September 2010 Publication History

Abstract

Background: Automated diagnosis of software defects can drastically increase debugging efficiency, improving reliability and time-to-market. Current, low-cost, automatic fault diagnosis techniques, such as spectrum-based fault localization (SFL), merely use information on whether a component is involved in a passed/failed run or not. However, these approaches ignore information on component execution frequency, which can improve the accuracy of the diagnostic process. Aim: In this paper, we study the impact of exploiting component execution frequency on the diagnostic quality. Method: We present a reasoning-based SFL approach, dubbed Zoltar-C, that exploits not only component involvement but also their frequency, using an approximate, Bayesian approach to compute the probabilities of the diagnostic candidates. Zoltar-C is evaluated and compared to other well-known, low-cost techniques (such as Tarantula) using a set of programs available from the Software Infrastructure Repository. Results: Results show that, although theoretically Zoltar-C can be of added value, exploiting component frequency does not improve diagnostic accuracy on average. Conclusions: The major reason for this unexpected result is the highly biased sample of passing and failing tests provided with the programs under analysis. In particular, the ratio between passing and failing runs, which has a major impact on the probability computations, does not correspond to the false negative (failure) rates associated with the actually injected faults.

References

[1]

}}R. Abreu, A. González, P. Zoeteweij, and A. van Gemund. Automatic software fault localization using generic program invariants. In Proc. SAC'08, Fortaleza, Brazil, March 2008. ACM Press.

Digital Library

[2]

}}R. Abreu, W. Mayer, M. Stumptner, and A. J. C. van Gemund. Refining spectrum-based fault localization rankings. In Proceedings of the Annual Symposium on Applied Computing (SAC'09).

Digital Library

[3]

}}R. Abreu and A. J. C. van Gemund. A low-cost approximate minimal hitting set algorithm and its application to model-based diagnosis. In Proceedings of Symposium on Abstraction, Reformulation, and Approximation (SARA'09).

[4]

}}R. Abreu, P. Zoeteweij, R. Golsteijn, and A. J. C. van Gemund. A practical evaluation of spectrum-based fault localization. Journal of Systems and Software, 82(11):1780--1792, 2009.

Digital Library

[5]

}}R. Abreu, P. Zoeteweij, and A. J. van Gemund. Spectrum-based multiple fault localization. In Proceedings of the International Conference on Automated Software Engineering (ASE'09).

Digital Library

[6]

}}R. Abreu, P. Zoeteweij, and A. J. C. van Gemund. On the accuracy of spectrum-based fault localization. In Proceedings of The Testing: Academic and Industrial Conference - Practice and Research Techniques (TAIC PART'07).

Digital Library

[7]

}}R. Abreu, P. Zoeteweij, and A. J. C. van Gemund. A new Bayesian approach to multiple intermittent fault diagnosis. In C. Boutilier, editor, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI'09), pages 653--658, Pasadena, California, USA, 11--17 July 2009. AAAI Press.

Digital Library

[8]

}}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

[9]

}}G. K. Baah, A. Podgurski, and M. J. Harrold. The probabilistic program dependence graph and its application to fault diagnosis. In Proceedings of International Symposium on Software Testing and Analysis (ISSTA'08).

Digital Library

[10]

}}J. de Kleer. Diagnosing intermittent faults. In Proceedings of International Workshop on Principles of Diagnosis (DX'07), May.

[11]

}}J. de Kleer. Diagnosing multiple persistent and intermittent faults. In Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI'09), pages 733--738, Pasadena, California, USA, 11--17 July 2009. AAAI Press.

Digital Library

[12]

}}J. de Kleer, A. K. Mackworth, and R. Reiter. Characterizing diagnoses and systems. Artificial Intelligence, 56:197--222, 1992.

Digital Library

[13]

}}H. Do, S. G. Elbaum, and G. Rothermel. Supporting controlled experimentation with testing techniques: An infrastructure and its potential impact. Empirical Software Engineering: An International Journal, 10(4):405--435, 2005.

Digital Library

[14]

}}M. J. Harrold, G. Rothermel, R. Wu, and L. Yi. An empirical investigation of program spectra. In Proceedings of International Workshop on Program Analysis for Software Tools and Engineering (PASTE'98).

Digital Library

[15]

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

Digital Library

[16]

}}T. Janssen, R. Abreu, and A. J. C. van Gemund. Zoltar: A toolset for automatic fault localization. In Proceedings of the International Conference on Automated Software Engineering (ASE'09) - Tool Demonstrations.

Digital Library

[17]

}}J. A. Jones, M. J. Harrold, and J. Stasko. Visualization of test information to assist fault localization. In Proceedings of International Conference on Software Engineering (ICSE'02).

Digital Library

[18]

}}B. Liblit, M. Naik, A. X. Zheng, A. Aiken, and M. I. Jordan. Scalable statistical bug isolation. In Proceedings of Conference on Programming Language Design and Implementation (PLDI'05).

Digital Library

[19]

}}C. Liu, X. Yan, L. Fei, J. Han, and S. P. Midkiff. Sober: Statistical model-based bug localization. In Proceedings of European Software Engineering Conference (ESEC) and the ACM SIGSOFT Symposium on the Foundations of Software Engineering (ESEC/FSE-13).

Digital Library

[20]

}}W. Mayer and M. Stumptner. Abstract interpretation of programs for model-based debugging. In Proceedings of International Joint Conference on Artificial Intelligence (IJCAI'07).

Digital Library

[21]

}}W. Mayer and M. Stumptner. Evaluating models for model-based debugging. In Proceedings of International Conference on Automated Software Engineering (ASE'08).

Digital Library

[22]

}}M. Renieris and S. P. Reiss. Fault localization with nearest neighbor queries. In Proceedings of International Conference on Automated Software Engineering (ASE'03).

[23]

}}T. Reps, T. Ball, M. Das, and J. Larus. The use of program profiling for software maintenance with applications to the year 2000 problem. In M. Jazayeri and H. Schauer, editors, Proceedings of the Sixth European Software Engineering Conference (ESEC/FSE 97), volume 1301 of LNCS, pages 432--449. Springer-Verlag, 1997.

Digital Library

[24]

}}X. Wang, S. Cheung, W. Chan, and Z. Zhang. Taming coincidental correctness: Coverage refinement with context patterns to improve fault localization. In Proceedings of International Conference on Software Engineering (ICSE'09).

Digital Library

[25]

}}W. Wong, T. Wei, Y. Qi, and L. Zhao. A crosstab-based statistical method for effective fault localization. In Proceedings of International Conference on Software Testing and Verification (ICST'08).

Digital Library

[26]

}}A. Zeller. Isolating cause-effect chains from computer programs. In Proceedings of Symposium on the Foundations of Software Engineering (FSE'02).

Digital Library

[27]

}}A. X. Zheng, M. I. Jordan, B. Liblit, M. Naik, and A. Aiken. Statistical debugging: Simultaneous identification of multiple bugs. In Proceedings of International Conference on Machine Learning (ICML'06).

Digital Library

Cited By

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
Liu HLi ZWang HLiu YChen X(2022)CRMF: A fault localization approach based on class reduction and method call frequencySoftware: Practice and Experience10.1002/spe.317853:4(1061-1090)Online publication date: 20-Dec-2022
https://doi.org/10.1002/spe.3178
Wang GShen RChen JXiong YZhang LSpinellis DGousios GChechik MDi Penta M(2021)Probabilistic Delta debuggingProceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3468264.3468625(881-892)Online publication date: 20-Aug-2021
https://dl.acm.org/doi/10.1145/3468264.3468625
Show More Cited By

Index Terms

Exploiting count spectra for Bayesian fault localization
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis
        Software testing and debugging

Recommendations

Fault density, fault types, and spectra-based fault localization

This paper presents multiple empirical experiments that investigate the impact of fault quantity and fault type on statistical, coverage-based fault localization techniques and fault-localization interference. Fault-localization interference is a ...
cfaults: Model-Based Diagnosis for Fault Localization in C with Multiple Test Cases
Formal Methods
Abstract
Debugging is one of the most time-consuming and expensive tasks in software development. Several formula-based fault localization (FBFL) methods have been proposed, but they fail to guarantee a set of diagnoses across all failing tests or may ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

PROMISE '10: Proceedings of the 6th International Conference on Predictive Models in Software Engineering

September 2010

195 pages

ISBN:9781450304047

DOI:10.1145/1868328

General Chair:
Tim Menzies
West Virginia University
,
Program Chair:
Gunes Koru
University of Maryland Baltimore County

Copyright © 2010 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: 12 September 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

Promise '10

Promise '10: The 6th International Conference on Predictive Models in Software Engineering

September 12 - 13, 2010

Timişoara, Romania

Acceptance Rates

PROMISE '10 Paper Acceptance Rate 19 of 53 submissions, 36%;

Overall Acceptance Rate 98 of 213 submissions, 46%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
277
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)3

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
Liu HLi ZWang HLiu YChen X(2022)CRMF: A fault localization approach based on class reduction and method call frequencySoftware: Practice and Experience10.1002/spe.317853:4(1061-1090)Online publication date: 20-Dec-2022
https://doi.org/10.1002/spe.3178
Wang GShen RChen JXiong YZhang LSpinellis DGousios GChechik MDi Penta M(2021)Probabilistic Delta debuggingProceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3468264.3468625(881-892)Online publication date: 20-Aug-2021
https://dl.acm.org/doi/10.1145/3468264.3468625
Idrees Sarhan QVancsics BBeszedes A(2021)Method Calls Frequency-Based Tie-Breaking Strategy For Software Fault Localization2021 IEEE 21st International Working Conference on Source Code Analysis and Manipulation (SCAM)10.1109/SCAM52516.2021.00021(103-113)Online publication date: Sep-2021
https://doi.org/10.1109/SCAM52516.2021.00021
Vancsics BHorvath FSzatmari ABeszedes A(2021)Call Frequency-Based Fault Localization2021 IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER)10.1109/SANER50967.2021.00041(365-376)Online publication date: Mar-2021
https://doi.org/10.1109/SANER50967.2021.00041
Troya JSegura SParejo JRuiz-Cortés A(2018)Spectrum-Based Fault Localization in Model TransformationsACM Transactions on Software Engineering and Methodology10.1145/324174427:3(1-50)Online publication date: 17-Sep-2018
https://dl.acm.org/doi/10.1145/3241744
Wang YLi JYan NLi WLi YLiu S(2018)Bug Patterns Localization Based on Topic Model for Bugs in Program Loop2018 IEEE International Conference on Software Quality, Reliability and Security Companion (QRS-C)10.1109/QRS-C.2018.00070(366-370)Online publication date: Jul-2018
https://doi.org/10.1109/QRS-C.2018.00070
Gao MLi PChen CJiang Y(2018)Research on Software Multiple Fault Localization Method Based on Machine LearningMATEC Web of Conferences10.1051/matecconf/201823201060232(01060)Online publication date: 19-Nov-2018
https://doi.org/10.1051/matecconf/201823201060
Wong WGao RLi YAbreu RWotawa F(2016)A Survey on Software Fault LocalizationIEEE Transactions on Software Engineering10.1109/TSE.2016.252136842:8(707-740)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1109/TSE.2016.2521368
Daniel PSim K(2013)Spectrum-based Fault Localization: A Pair Scoring ApproachJournal of Industrial and Intelligent Information10.12720/jiii.1.4.185-1901:4(185-190)Online publication date: 2013
https://doi.org/10.12720/jiii.1.4.185-190

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