skip to main content
10.1145/1134285.1134307acmconferencesArticle/Chapter ViewAbstractPublication PagesicseConference Proceedingsconference-collections
Article

HDD: hierarchical delta debugging

Published: 28 May 2006 Publication History

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]
H. Agrawal, R. A. DeMillo, and E. H. Spafford. Debugging with dynamic slicing and backtracking. Software - Practice and Experience, 23(6):589--616, 1993.
[2]
H. Agrawal and J. R. Horgan. Dynamic program slicing. In Proceedings of the ACM SIGPLAN '90 Conference on Programming Language Design and Implementation, pages 246--256, June 1990.
[3]
T. Ball, M. Naik, and S. K. Rajamani. From symptom to cause: Localizing errors in counterexample traces. In Proceedings of 30th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL 2003), pages 97--105, 2003.
[4]
J.-D. Choi and A. Zeller. Isolating failure-inducing thread schedules. In ISSTA '02: Proceedings of the 2002 ACM SIGSOFT international symposium on Software testing and analysis, pages 210--220, 2002.
[5]
H. Cleve and A. Zeller. Locating causes of program failures. In Proceedings of the 27th International Conference on Software Engineering, May 2005. to appear.
[6]
M. Das, S. Lerner, and M. Seigle. ESP: path-sensitive program verification in polynomial time. In Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language Design and Implementation, pages 57--68, 2002.
[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]
B. Liblit, A. Aiken, A. X. Zheng, and M. I. Jordan. Bug isolation via remote program sampling. In Proceedings of the ACM SIGPLAN 2003 Conference on Programming Language Design and Implementation, San Diego, California, June 9--11 2003.
[10]
B. Liblit, M. Naik, A. X. Zheng, A. Aiken, and M. I. Jordan. Scalable statistical bug isolation. In Proceedings of the ACM SIGPLAN 2005 Conference on Programming Language Design and Implementation, pages 15--26, June 2005.
[11]
B. P. Lientz, E. B. Swanson, and G. E. Tompkins. Characteristics of application software maintenance. Commun. ACM, 21(6):466--471, 1978.
[12]
R. Manevich, M. Sridharan, and S. Adams. PSE: explaining program failures via postmortem static analysis. In SIGSOFT '04/FSE-12: Proceedings of the 12th ACM SIGSOFT twelfth international symposium on Foundations of software engineering, pages 63--72, 2004.
[13]
S. McPeak. Elsa: The Elkhound-based C/C++ parser. http://www.cs.berkeley.edu/~smcpeak/elkhound/sources/elsa/index.html.
[14]
C. Sterling and R. A. Olsson. Automated bug isolation via program chipping. In Sixth International Symposium on Automated Debugging and Analysis-Deiven Debugging (AADEBUG'05), 2005. To appear.
[15]
F. Tip. A survey of program slicing techniques. Journal of programming languages, 3:121--189, 1995.
[16]
M. Weiser. Program slicing. In Proceedings of the 5th International Conference on Software Engineering, pages 439--449, 1981.
[17]
M. Weiser. Programmers use slicing when debugging. Communications of the ACM, 25(7):446--452, 1982.
[18]
D. B. Whalley. Automatic isolation of compiler errors. ACM Trans. Program. Lang. Syst., 16(5):1648--1659, 1994.
[19]
A. Zeller. Isolating cause-effect chains from computer programs. In Proceedings of the 10th ACM SIGSOFT Symposium on Foundations of Software Engineering, pages 1--10, 2002.
[20]
A. Zeller and R. Hildebrandt. Simplifying and isolating failure-inducing input. IEEE Trans. Software Engineering, 28(2), Febuary 2002.

Cited By

View all
  • (2024)T-Rec: Fine-Grained Language-Agnostic Program Reduction Guided by Lexical SyntaxACM Transactions on Software Engineering and Methodology10.1145/369063134:2(1-31)Online publication date: 30-Aug-2024
  • (2024)GreeDDy: Accelerate Parallel DDMINProceedings of the 15th ACM International Workshop on Automating Test Case Design, Selection and Evaluation10.1145/3678719.3685690(1-4)Online publication date: 13-Sep-2024
  • (2024)Calico: Automated Knowledge Calibration and Diagnosis for Elevating AI Mastery in Code TasksProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3680399(1785-1797)Online publication date: 11-Sep-2024
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
ICSE '06: Proceedings of the 28th international conference on Software engineering
May 2006
1110 pages
ISBN:1595933751
DOI:10.1145/1134285
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 28 May 2006

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. automated debugging
  2. delta debugging

Qualifiers

  • Article

Conference

ICSE06
Sponsor:

Acceptance Rates

Overall Acceptance Rate 276 of 1,856 submissions, 15%

Upcoming Conference

ICSE 2025

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)183
  • Downloads (Last 6 weeks)27
Reflects downloads up to 13 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)T-Rec: Fine-Grained Language-Agnostic Program Reduction Guided by Lexical SyntaxACM Transactions on Software Engineering and Methodology10.1145/369063134:2(1-31)Online publication date: 30-Aug-2024
  • (2024)GreeDDy: Accelerate Parallel DDMINProceedings of the 15th ACM International Workshop on Automating Test Case Design, Selection and Evaluation10.1145/3678719.3685690(1-4)Online publication date: 13-Sep-2024
  • (2024)Calico: Automated Knowledge Calibration and Diagnosis for Elevating AI Mastery in Code TasksProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3680399(1785-1797)Online publication date: 11-Sep-2024
  • (2024)SQLess: Dialect-Agnostic SQL Query SimplificationProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3680317(743-754)Online publication date: 11-Sep-2024
  • (2024)Isolation-Based Debugging for Neural NetworksProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3652132(338-349)Online publication date: 11-Sep-2024
  • (2024)C2D2: Extracting Critical Changes for Real-World Bugs with Dependency-Sensitive Delta DebuggingProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3652129(300-312)Online publication date: 11-Sep-2024
  • (2024)LPR: Large Language Models-Aided Program ReductionProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3652126(261-273)Online publication date: 11-Sep-2024
  • (2024)Improving Program Debloating with 1-DU Chain MinimalityProceedings of the 2024 IEEE/ACM 46th International Conference on Software Engineering: Companion Proceedings10.1145/3639478.3643518(384-385)Online publication date: 14-Apr-2024
  • (2024)Automatic Debugging of Design Faults in MapReduce ApplicationsIEEE Transactions on Software Engineering10.1109/TSE.2024.336976650:4(956-978)Online publication date: 26-Feb-2024
  • (2024)ReduJavator: A Tool to Simplify Developer-Written Java Unit Tests2024 IEEE International Conference on Data and Software Engineering (ICoDSE)10.1109/ICoDSE63307.2024.10829914(199-204)Online publication date: 30-Oct-2024
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media