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: 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: Hiralal Agrawal , Richard A. DeMillo , Eugene H. Spafford, Dynamic slicing in the presence of unconstrained pointers, Proceedings of the symposium on Testing, analysis, and verification, p.60-73, October 08-10, 1991, Victoria, British Columbia, Canada [doi>10.1145/120807.120813]
• 3: Hiralal Agrawal , Richard A. Demillo , Eugene H. Spafford, Debugging with dynamic slicing and backtracking, Software—Practice & Experience, v.23 n.6, p.589-616, June 1993 [doi>10.1002/spe.4380230603]
• 4: Hiralal Agrawal , Joseph R. Horgan, Dynamic program slicing, ACM SIGPLAN Notices, v.25 n.6, p.246-256, Jun. 1990
• 5: H. Agrawal , E. H. Spafford, Bibliography on debugging and backtracking, ACM SIGSOFT Software Engineering Notes, v.14 n.2, p.49-56, April 1989 [doi>10.1145/71647.71653]
• 6: Hiralal Agrawal, Towards automatic debugging of computer programs, Purdue University, West Lafayette, IN, 1992
• 7: ANSI/IEEE. !EEE Standard Glossary of So/tware Enginnering Terminology. IEEE Std 729-1983. IEEE, New York, 1983.
• 8: Barry W. Boehm, Software Engineering Economics, Prentice Hall PTR, Upper Saddle River, NJ, 1981
• 9: Robert S. Boyer , Bernard Elspas , Karl N. Levitt, SELECT—a formal system for testing and debugging programs by symbolic execution, Proceedings of the international conference on Reliable software, p.234-245, April 21-23, 1975, Los Angeles, California
• 10: Gordon H. Bradley, Algorithm and bound for the greatest common divisor of n integers, Communications of the ACM, v.13 n.7, p.433-436, July 1970 [doi>10.1145/362686.362694]
• 11: Timothy Alan Budd, Mutation analysis of program test data, 1980
• 12: Timothy A. Budd , Richard A. DeMillo , Richard J. Lipton , Frederick G. Sayward, Theoretical and empirical studies on using program mutation to test the functional correctness of programs, Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.220-233, January 28-30, 1980, Las Vegas, Nevada [doi>10.1145/567446.567468]
• 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: 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: 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: 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: 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: Phyllis G. Frankl , Stewart N. Weiss, An experimental comparison of the effectiveness of the all-uses and all-edges adequacy criteria, Proceedings of the symposium on Testing, analysis, and verification, p.154-164, October 08-10, 1991, Victoria, British Columbia, Canada [doi>10.1145/120807.120821]
• 19: Matthew Geller, Test data as an aid in proving program correctness, Communications of the ACM, v.21 n.5, p.368-375, May 1978 [doi>10.1145/359488.359495]
• 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: Fred G. Gustavson, Remark on algorithm 408: a sparse matrix package (part 1) [F4], ACM Transactions on Mathematical Software (TOMS), v.4 n.3, p.295, Sept. 1978 [doi>10.1145/355791.356474]
• 22: C. A. R. Hoare, Algorithm 65: find, Communications of the ACM, v.4 n.7, p.321-322, July 1961 [doi>10.1145/366622.366647]
• 23: J. R. Horgan , S. London, Data flow coverage and the C language, Proceedings of the symposium on Testing, analysis, and verification, p.87-97, October 08-10, 1991, Victoria, British Columbia, Canada [doi>10.1145/120807.120815]
• 24: B. Korel, PELAS-Program Error-Locating Assistant System, IEEE Transactions on Software Engineering, v.14 n.9, p.1253-1260, September 1988 [doi>10.1109/32.6169]
• 25: Edward William Krauser, Jr., Compiler-integrated software testing, Purdue University, West Lafayette, IN, 1992
• 26: Myron Lipow. Prediction of software failures. The Journal of Systems and Software, 1(1):71-75, 1979.
• 27: John Michael McNamee, Algorithm 408: a sparse matrix package (part I) [F4], Communications of the ACM, v.14 n.4, p.265-273, April 1971 [doi>10.1145/362575.362584]
• 28: Glenford J. Myers, Art of Software Testing, John Wiley & Sons, Inc., New York, NY, 1979
• 29: P. Naur. Programming by action clusters. BIT, 9:250- 258, 1969.
• 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: 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: Hsin Pan, Software debugging with dynamic instrumentation and test-based knowledge, Purdue University, West Lafayette, IN, 1993
• 33: R S Pressman, Software engineering: a practitioner's approach (2nd ed.), McGraw-Hill, Inc., New York, NY, 1986
• 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: Richard M. Stallman. GDB Manual, third edition, GDB version 3. d. Free Software Foundation, Cambridge, Massachusetts, October 1989.
• 36: Richard M. Stallman. Using and Porting GNU CU, version 1.37. Free Software Foundation, Cambridge, Massachusetts, January 1990.
• 37: Frank Tip, A Survey of Program Slicing Techniques., CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 1994
• 38: Iris Vessey. Expertise in debugging computer programs: A process analysis, international Journal of Man- Machine Studies, 23(5):459-494, November 1985.
• 39: Mark Weiser, Programmers use slices when debugging, Communications of the ACM, v.25 n.7, p.446-452, July 1982 [doi>10.1145/358557.358577]
• 40: Mark Weiser. Program slicing. IEEE Transactions o, Software Engzneer,ng, SE-10(4):352-357, July 1984.
• 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

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.9 Management
          Subjects: Life cycle

General Terms:
Design, Experimentation, Management, Reliability, Theory, Verification

Keywords:
critical slicing, debugging, dynamic program slicing, failures, fault localization, faults, mutation analysis, static program slicing, testing