Critical slicing for software fault localization

ABSTRACT

Developing effective debugging strategies to guarantee the reliability of software is important. By analyzing the debugging process used by experienced programmers, we have found that four distinct tasks are consistently performed: (1) determining statements involved in program failures, (2) selecting suspicious statements that might contain faults, (3) making hypotheses about suspicious faults (variables and locations), and (4) restoring program state to a specific statement for verification. This research focuses support for the second task, reducing the search domain for faults, which we refer to as fault localization.We explored a new approach to enhancing the process of fault localization based on dynamic program slicing and mutation-based testing. In this new approach, we have developed the technique of Critical Slicing to enable debuggers to highlight suspicious statements and thus to confine the search domain to a small region. The Critical Slicing technique is partly based on "statement deletion" mutant operator of the mutation-based testing methodology. We have explored properties of Critical Slicing, such as the relationship among Critical Slicing, Dynamic Program Slicing, and Executable Static Program Slicing; the cost to construct critical slices; and the effectiveness of Critical Slicing. Results of experiments support our conjecture as to the effectiveness and feasibility of using Critical Slicing for fault localization.This paper explains our technique and summarizes some of our findings. From these, we conclude that a debugger equipped with our proposed fault localization method can reduce human interaction time significantly and aid in the debugging of complex software.

References

1. 1.H. Agrawal, R. A. DeMillo, B. Hathaway, W. Hsu, W. Hsu, E. W. Krauser, R. J. Martin, A. P. Mathur, and E. H. Spafford. Design of mutant operators for the C programming language. Technical Report SERC- TR-41-P, Software Engineering Research Center, Purdue University, West Lafayette, Indiana, March 1989.]]
2. 2.H. Agrawal, R. A. DeMillo, and E. H. Spafford. Dynamic slicing in the presence of unconstrained pointers. In Proceedings of the 1991 Symposium on Software Testing, Analys~s, and Verification (TA VJ), pages 60- 73, Victoria, British Columbia, Canada, October 8-10 1991.]]
3. 3.H. Agrawal, R. A. DeMillo, and E. H. Spafford. Debugging with dynamic slicing and backtracking. Software Practice and Experience, 23(6):589-616, June 1993.]]
4. 4.H. Agrawal and J. R. Horgan. Dynamic program slicing. In Proceedings of the ACM SIGPLAN '90 Con/ercnce on Programming Language Design and Implementation, pages 246-256, White Plains, New York, June 1990. (ACM SlGPLAN Notices, 25(6), June 1990).]]
5. 5.H. Agrawal and E. H. Spafford. A bibliography on debugging and backtracking. ACM Software Engineering Notes, 14(2):49-56, April 1989.]]
6. 6.Hiralal Agrawal. Towards A utomatzc Debugging of Computer Programs. PhD thesis, Purdue University, West Lafayette, Indiana, August 1991. (Also released as Technical Report SERC-TR-103-P, Software Engineering Research Center, Purdue University, West Lafayette, Indiana, September 1991).]]
7. 7.ANSI/IEEE. !EEE Standard Glossary of So/tware Enginnering Terminology. IEEE Std 729-1983. IEEE, New York, 1983.]]
8. 8.B. W. Boehm. Software Eng~nner~ng Economics. Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1981.]]
9. 9.R. S. Boyer, E. Elspas, and K. N. Levitt. SELECT a system for testing and debugging programs by symbolic execution. In Proceedings o/International Conference on Reliable Software, pages 234-245, 1975. (ACM SIC- PLAN Notices, 10(6), June 1990).]]
10. 10.Gordon H. Bradley. Algorithm and bound for the greatest common divisor of n integers. Communications o/ the ACM, 13(7):433-436, July 1970.]]
11. 11.T. A. Budd. Mutatzon Analysis of Program Test Data. PhD thesis, Yale University, New Haven, Connecticut, 1980.]]
12. 12.T. A. Budd, R. A. DeMillo, R. J. Lipton, and F. G. Sayward. Theoretical and empmcal studies of using program mutation to test the functional correctness of programs. In Proceedings o/the 7th A CM Symposium on Principles o/Programming Languages, pages 220- 233, Las Vegas, January 1980.]]
13. 13.B. J. Choi, R. A. DeMillo, E. W. Krauser, R. J. Martin. A. P. Mathur, A. J. Offutt, H. Pan, and E. H. Spafford. The Mothra tool set. In Proceedzngs o/the 22nd Annual Hawaz~ International Conference or, Systems Sciences, pages 275-284, Kona, Hawaii, January 1989.]]
14. 14.M. E. Delamaro. Um ambiente de teste baseado na anglise de mutantes (proteum: A test environment based on mutation analysis). Master's thesis, ICMSC- USP, S~o Carlos, SP, Brazil, October 1903.]]
15. 15.M. E. Delamaro, J. C. Maldonado, M. Jino, and M.L.Chaim. Proteum: Uma ferramenta de teste baseada na anglise de mutantes (proteum: A testing tool based on mutation analysis). In Software Tools Proceedzngs of VII Brazdian Symposium on Software Engineering, Oct 1993.]]
16. 16.R. A. DeMillo, R. J. Lipton, and F. G. Sayward. Hints on test data selection: Help for the practicing programmer. Computer, 11(4):34-43, April 1978.]]
17. 17.R. A. DeMillo, H. Pan, and E. H. Spafford. Failure ~nd fault analysis for software debugging. Technical Report 03.574, Application Development Technology institute, Software Solutions Division, I.B.M., San Jose, California, July 1994.]]
18. 18.Phyllis G. Frankl and Stewart N. Weiss. An experimental comparison of the effectiveness of the all-uses and all-edges adequacy criteria. In Proceedings of the 1991 Symposzum on Software Testing, Analysis and Verification (TAV~), pages 154-164, Victoria, British Columbia, Canada, October 8-10 1991.]]
19. 19.M. Geller. Test data as an aid in proving program correctness. Communications of the ACM, 21(5):368-375, May 1978.]]
20. 20.J. B. Goodenough and S. L. Gerhart. Towards a theory of test data selection. IEEE Transactions on Software Engineering, SE-1(2):156-173, June 1975.]]
21. 21.F. Gustavson. Remark on algorithm 408. A CM Transactions on Mathematzcal Software, 4:295, 1978.]]
22. 22.C. Hoare. Algorithm 65: FIND. Communications of the ACM, 4(1):321, April 1961.]]
23. 23.J. R. Horgan and S. London. Dat~ flow coverage and the C language. In Proceedings of the 1991 Symposium on Software Testing, Analysis, and Verzficatzon (TAVd), pages 87-97, Victoria, British Columbia, Canada, October 8-10 1991.]]
24. 24.Bogdan Korel. PELAS- program error-locating assistant system. IEEE Transact2ons on Software Engineering, SE-14(9):1253-1260, September 1988.]]
25. 25.Edward W. Krauser, Jr. Compiler-Integrated Software Tcst,ng. PhD thesis, Purdue University, West Lafayette, Indiana, December 1991. (Also released as Technical Report SERC-TR-118-P, Software Engineering Research Center, Purdue University, West Lafayette, indiana, July 1992).]]
26. 26.Myron Lipow. Prediction of software failures. The Journal of Systems and Software, 1(1):71-75, 1979.]]
27. 27.J. M. McNamee. Algorithm 408: A sparse matrix package (part I) If4}. Communications of the A CM, 14(4):265-273, April 1971.]]
28. 28.Glenford J. Myers. The Art of Software Testzng. John Wiley /2 Sons, Inc., New York, 1979.]]
29. 29.P. Naur. Programming by action clusters. BIT, 9:250- 258, 1969.]]
30. 30.H. Pan and E. H. Spafford. Toward automatic localization of software faults. In Proceed, ngs of the l Oth Pacific Northwest Software Quality Conference, pages 192-209, Portland, Oregon, October 19-21 1992.]]
31. 31.Hsin Pan. Debugging with dynamic instrumentation and test-based knowledge. Technical Report SERC- TR-105-P, Software Engineering Research Center, Purdue University, West Lafayette, Indiana, September 1991.]]
32. 32.Hsin Pan. Software Debugging with Dynamic Instrumentat, on and Test-Based Knowledge. PhD thesis, Purdue University, West Lafayette, Indiana, August 1993. (Also released as Technical Report SERC-TR- 145-P, Software Engineering Research Center, Purdue University, West Lafayette, Indiana, August 1993).]]
33. 33.Roger S. Pressman. Software Enginner, ng: A Pract,- t,oner's Approach. McGraw-Hill, Inc., New York, second edition, 1987.]]
34. 34.C. V. Ramamoorthy, S. F. Ho, and W. T. Chen. On the automated generation of program test data. IEEE Transactions on Software Engineerzng, SE-2(4):293- 300, December 1976.]]
35. 35.Richard M. Stallman. GDB Manual, third edition, GDB version 3. d. Free Software Foundation, Cambridge, Massachusetts, October 1989.]]
36. 36.Richard M. Stallman. Using and Porting GNU CU, version 1.37. Free Software Foundation, Cambridge, Massachusetts, January 1990.]]
37. 37.Frank Tip. A survey of program slicing techniques. Technical Report CS-R9438, Centrum voor Wiskunde en Informatica (CWI), Amsterdam, The Netherlands, 1994.]]
38. 38.Iris Vessey. Expertise in debugging computer programs: A process analysis, international Journal of Man- Machine Studies, 23(5):459-494, November 1985.]]
39. 39.Mark Weiser. Programmers use slices when debugging. Commun,cat,ons of the A CM, 25(7):446-452, Julv 1982.]]
40. 40.Mark Weiser. Program slicing. IEEE Transactions o, Software Engzneer,ng, SE-10(4):352-357, July 1984.]]
41. 41.W. E. Wong, J. C. Maldonado, M. E. Delamaro, and A. P. Mathur. Constrained mutation in C programs. In Proceedings o/ VIII Symposium on Software Enginer- ,ng, Oct 1994. in Curitiba, Brazil.]]

Index Terms

• Software and its engineering

  • Software creation and management

    • Software verification and validation

      • Software defect analysis

        • Software testing and debugging