Refining spectrum-based fault localization rankings

ABSTRACT

Spectrum-based fault localization is a statistical technique that aims at helping software developers to find faults quickly by analyzing abstractions of program traces to create a ranking of most probable faulty components (e.g., program statements). Although spectrum-based fault localization has been shown to be effective, its diagnostic accuracy is inherently limited, since the semantics of components are not considered. In particular, components that exhibit identical execution patterns cannot be distinguished. To enhance its diagnostic quality, in this paper, we combine spectrum-based fault localization with a model-based debugging approach based on abstract interpretation within a framework coined Deputo. The model-based approach is used to refine the ranking obtained from the spectrum-based method by filtering out those components that do not explain the observed failures when the program's semantics is considered. We show that this combined approach outperforms the individual approaches and other state-of-the-art automated debugging techniques.

REFERENCES

• 1: Rui Abreu , Alberto González , Peter Zoeteweij , Arjan J. C. van Gemund, Automatic software fault localization using generic program invariants, Proceedings of the 2008 ACM symposium on Applied computing, March 16-20, 2008, Fortaleza, Ceara, Brazil [doi>10.1145/1363686.1363855]
• 2: Rui Abreu , Peter Zoeteweij , Arjan J. C. van Gemund, On the Accuracy of Spectrum-based Fault Localization, Proceedings of the Testing: Academic and Industrial Conference Practice and Research Techniques - MUTATION, p.89-98, September 10-14, 2007
• 3: Rui Abreu , Peter Zoeteweij , Arjan J. C. van Gemund, An observation-based model for fault localization, Proceedings of the 2008 international workshop on dynamic analysis: held in conjunction with the ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA 2008), July 21-21, 2008, Seattle, Washington [doi>10.1145/1401827.1401841]
• 4: C. Böttcher. No faults in structure? How to diagnose hidden interaction. In Proc. IJCAI, 1995.
• 5: Patrick Cousot , Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.238-252, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512973]
• 6: Dawson Engler , Daniel Dunbar, Under-constrained execution: making automatic code destruction easy and scalable, Proceedings of the 2007 international symposium on Software testing and analysis, p.1-4, July 09-12, 2007, London, United Kingdom [doi>10.1145/1273463.1273464]
• 7: Alex Groce , Sagar Chaki , Daniel Kroening , Ofer Strichman, Error explanation with distance metrics, International Journal on Software Tools for Technology Transfer (STTT), v.8 n.3, p.229-247, June 2006 [doi>10.1007/s10009-005-0202-0]
• 8: James A. Jones , Mary Jean Harrold, Empirical evaluation of the tarantula automatic fault-localization technique, Proceedings of the 20th IEEE/ACM international Conference on Automated software engineering, November 07-11, 2005, Long Beach, CA, USA [doi>10.1145/1101908.1101949]
• 9: Chao Liu , Xifeng Yan , Long Fei , Jiawei Han , Samuel P. Midkiff, SOBER: statistical model-based bug localization, Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering, September 05-09, 2005, Lisbon, Portugal
• 10: W. Mayer, R. Abreu, M. Stumptner, and A. J. C. van Gemund. Prioritizing model-based debugging diagnostic reports. In Proc. DX'08, 2008.
• 11: W. Mayer and M. Stumptner. Evaluating models for model-based debugging. In ASE'08. ACM Press, 2008.
• 12: M. Musuvathi and D. R. Engler. Some lessons from using static analysis and software model checking for bug finding. ENTCS, 89(3), 2003.
• 13: R Reiter, A theory of diagnosis from first principles, Artificial Intelligence, v.32 n.1, p.57-95, April 1987 [doi>10.1016/0004-3702(87)90062-2]
• 14: M. Renieris and S. P. Reiss. Fault localization with nearest neighbor queries. In ASE'03. ACM Press, 2003.
• 15: RTI. Planning report 02-3: The economic impacts of inadequate infrastructure for software testing. Planning Report 02--3, NIST, 2002.
• 16: Eric Wong , Tingting Wei , Yu Qi , Lei Zhao, A Crosstab-based Statistical Method for Effective Fault Localization, Proceedings of the 2008 International Conference on Software Testing, Verification, and Validation, p.42-51, April 09-11, 2008 [doi>10.1109/ICST.2008.65]
• 17: Cemal Yilmaz , Amit Paradkar , Clay Williams, Time will tell: fault localization using time spectra, Proceedings of the 30th international conference on Software engineering, May 10-18, 2008, Leipzig, Germany [doi>10.1145/1368088.1368100]
• 18: Cemal Yilmaz , Clay Williams, An automated model-based debugging approach, Proceedings of the twenty-second IEEE/ACM international conference on Automated software engineering, November 05-09, 2007, Atlanta, Georgia, USA [doi>10.1145/1321631.1321659]
• 19: Peter Zoeteweij , Rui Abreu , Rob Golsteijn , Arjan J. C. van Gemund, Diagnosis of Embedded Software Using Program Spectra, Proceedings of the 14th Annual IEEE International Conference and Workshops on the Engineering of Computer-Based Systems, p.213-220, March 26-29, 2007 [doi>10.1109/ECBS.2007.31]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Debugging aids

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Diagnostics

General Terms:
Experimentation, Measurement, Reliability

Keywords:
abstract interpretation, fault localization, program spectra