HDD: hierarchical delta debugging

ABSTRACT

Inputs causing a program to fail are usually large and often contain information irrelevant to the failure. It thus helps debugging to simplify program inputs. The Delta Debugging algorithm is a general technique applicable to minimizing all failure-inducing inputs for more effective debugging. In this paper, we present HDD, a simple but effective algorithm that significantly speeds up Delta Debugging and increases its output quality on tree structured inputs such as XML. Instead of treating the inputs as one flat atomic list, we apply Delta Debugging to the very structure of the data. In particular, we apply the original Delta Debugging algorithm to each level of a program's input, working from the coarsest to the finest levels. We are thus able to prune the large irrelevant portions of the input early. All the generated input configurations are syntactically valid, reducing the number of inconclusive configurations that need to be tested and accordingly the amount of time spent simplifying. We have implemented HDD and evaluated it on a number of real failure-inducing inputs from the GCC and Mozilla bugzilla databases. Our Hierarchical Delta Debugging algorithm produces simpler outputs and takes orders of magnitude fewer test cases than the original Delta Debugging algorithm. It is able to scale to inputs of considerable size that the original Delta Debugging algorithm cannot process in practice. We argue that HDD is an effective tool for automatic debugging of programs expecting structured inputs.

REFERENCES

• 1: 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]
• 2: Hiralal Agrawal , Joseph R. Horgan, Dynamic program slicing, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.246-256, June 1990, White Plains, New York, United States
• 3: Thomas Ball , Mayur Naik , Sriram K. Rajamani, From symptom to cause: localizing errors in counterexample traces, Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.97-105, January 15-17, 2003, New Orleans, Louisiana, USA
• 4: Jong-Deok Choi , Andreas Zeller, Isolating failure-inducing thread schedules, Proceedings of the 2002 ACM SIGSOFT international symposium on Software testing and analysis, July 22-24, 2002, Roma, Italy
• 5: Holger Cleve , Andreas Zeller, Locating causes of program failures, Proceedings of the 27th international conference on Software engineering, p.342-351, May 15-21, 2005, St. Louis, MO, USA [doi>10.1145/1062455.1062522]
• 6: Manuvir Das , Sorin Lerner , Mark Seigle, ESP: path-sensitive program verification in polynomial time, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 7: A. Groce and W. Visser. What went wrong: Explaining counterexamples. In SPIN 2003, pages 121--135, 2003.
• 8: R. M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, pages 85--103. Plenum Press, NY, 1972.
• 9: Ben Liblit , Alex Aiken , Alice X. Zheng , Michael I. Jordan, Bug isolation via remote program sampling, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 10: Ben Liblit , Mayur Naik , Alice X. Zheng , Alex Aiken , Michael I. Jordan, Scalable statistical bug isolation, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 11: B. P. Lientz , E. B. Swanson , G. E. Tompkins, Characteristics of application software maintenance, Communications of the ACM, v.21 n.6, p.466-471, June 1978 [doi>10.1145/359511.359522]
• 12: Roman Manevich , Manu Sridharan , Stephen Adams , Manuvir Das , Zhe Yang, PSE: explaining program failures via postmortem static analysis, Proceedings of the 12th ACM SIGSOFT twelfth international symposium on Foundations of software engineering, October 31-November 06, 2004, Newport Beach, CA, USA
• 13: S. McPeak. Elsa: The Elkhound-based C/C++ parser. http://www.cs.berkeley.edu/~smcpeak/elkhound/sources/elsa/index.html.
• 14: Chad D. Sterling , Ronald A. Olsson, Automated bug isolation via program chipping, Proceedings of the sixth international symposium on Automated analysis-driven debugging, p.23-32, September 19-21, 2005, Monterey, California, USA [doi>10.1145/1085130.1085134]
• 15: F. Tip. A survey of program slicing techniques. Journal of programming languages, 3:121--189, 1995.
• 16: Mark Weiser, Program slicing, Proceedings of the 5th international conference on Software engineering, p.439-449, March 09-12, 1981, San Diego, California, United States
• 17: 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]
• 18: David B. Whalley, Automatic isolation of compiler errors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.5, p.1648-1659, Sept. 1994 [doi>10.1145/186025.186103]
• 19: Andreas Zeller, Isolating cause-effect chains from computer programs, Proceedings of the 10th ACM SIGSOFT symposium on Foundations of software engineering, November 18-22, 2002, Charleston, South Carolina, USA [doi>10.1145/587051.587053]
• 20: Andreas Zeller , Ralf Hildebrandt, Simplifying and Isolating Failure-Inducing Input, IEEE Transactions on Software Engineering, v.28 n.2, p.183-200, February 2002 [doi>10.1109/32.988498]

INDEX TERMS

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

General Terms:
Reliability

Keywords:
automated debugging, delta debugging