Automated fault localization with statistically suspicious program states

Abstract

A number of fault localization techniques have been developed to reduce the time in manually debugging a faulty program. The technique of code coverage [8] has been recognized by its effectiveness in identifying suspicious statements that may contain the fault. However, a programmer still needs to manually examine each variable referenced in a suspicious statement and such a process can become extremely time-consuming if this suspicious statement is part of a loop. In this paper, we propose a novel technique called state coverage to significantly reduce the time in examining variables. We first insert a set of checkpoints to record the state of each variable referenced in a branching statement. We next execute the faulty program by a test suite consisting of both passed and failed cases. A state is statistically considered to be more suspicious if it appears more in failed cases and less in passed cases. We implemented both code coverage and state coverage in a debugging tool and used a commonly-used benchmark consisting of 58 faulty programs to evaluate their performance. For 34% of these programs, their faults are within 20 statement steps of the most suspicious statement identified by code coverage. By adding state coverage and breaking at the most suspicious state, we increase this ratio to 64%, an 88% performance improvement. Finally, we also explain a few cases in which both state coverage and code coverage cannot perform well.

References

1. H. Agrawal and J. Horgan. Dynamic Program Slicing. In Proceedings of ACM SIGPLAN 1990 Conference on Programming Language Design and Implementation (PLDI), pages 246--256, 1990.
2. H. Agrawal, J. Horgan, S. London, and W. Wong. Fault Localization Using Execution Slices and Dataflow Tests. In Proceedings of the Sixth IEEE Software Reliability Engineering, pages 143--151, 1995.
3. H. Cleve and A. Zeller. Locating Causes of Program Failures. In Proceedings of 27th International Conference on Software Engineering (ICSE), pages 342--351, 2005.
4. gcov: A Test Coverage Program. http://gcc.gnu.org/onlinedocs/gcc--3.0/gcc_8.html.
5. M. J. Harrold, G. Rothermel, K. Sayre, R. Wu, and L. Yi. An Empirical Investigation of the Relationship Between Spectra Diferences and Regression Faults. Journal of Software Testing, Verification, and Reliability, 10(3):171--194, 2000.
6. M. Hutchins, H. Foster, T. Goraida, and T. Ostrand. Experiments of the Effectiveness of Dataflow and Controlflow--based Test Adequacy Criteria. In Proceedings of 16th International Conference on Software Engineering (ICSE), pages 191--200, 1994.
7. J. Jones and M. J. Harrold. Empirical Evaluation of the Tarantula Automatic Fault--Localization Technique. In Proceedings of the 20th IEEE/ACM International Conference on Automated Software Engineering, pages 273--282, 2005.
8. J. Jones, M. J. Harrold, and J. Stasko. Visualization of Test Information to Assist Fault Localization. In Proceedings of 24th International Conference on Software Engineering (ICSE), pages 467--477, 2002.
9. B. Korel and J. Laski. Dynamic Slicing of Computer Programs. The Journal of Systems and Software, 13(3):187--195, 1990.
10. X. Z. N. Gupta, H. He and R. Gupta. Locating Faulty Code Using Failure--inducing Chops. In Proceedings of the 20th IEEE/ACM International Conference on Automated Software Engineering, pages 263--272, 2005.
11. M. Renieris and S. Reiss. Fault Localization with Nearest Neighbor Queries. In Proceedings of the 18th IEEE/ACM International Conference on Automated Software Engineering, pages 30--39, 2003.
12. M. Weiser. Program Slicing. IEEE Transactions on Software Engineering, SE--10(4):352--357, 1982.
13. N. G. X. Zhang, H. He and R. Gupta. Experimental Evaluation of Using Dynamic Slices for Fault Location. In Proceedings of International Symposium on Automated Analysis-driven Debugging, pages 33--42, 2005.
14. xSlice: A Tool for Program Debugging. http://xsuds.argreenhouse.com/html-man/coverpage.html.
15. A. Zeller. Yesterday, My Program Worked. Today, It Does Not. Why? In Proceedings of ACM SIGSOFT International Symposium on Foundations of Software Engineering, pages 253--267, 1999.
16. A. Zeller. Isolating Cause-Effect Chains from Computer Programs. In Proceedings of ACM SIGSOFT International Symposium on Foundations of Software Engineering, pages 1--10, 2002.
17. A. Zeller and R. Hildebrandt. Simplifying and Isolating Failure-Inducing Input. IEEE Transactions on Software Engineering, 28(2):183--200, 2002.

Index Terms

• Software and its engineering

  • Software creation and management

    • Software verification and validation

      • Process validation

        • Traceability

      • Software defect analysis

        • Software testing and debugging