More Web Proxy on the site http://driver.im/

research-article

Modernizing hierarchical delta debugging

Authors:

Renáta Hodován,

Ákos KissAuthors Info & Claims

A-TEST 2016: Proceedings of the 7th International Workshop on Automating Test Case Design, Selection, and Evaluation

Pages 31 - 37

https://doi.org/10.1145/2994291.2994296

Published: 18 November 2016 Publication History

Abstract

Programmers tasked with the fixing of a bug prefer working on a minimal test case where every single bit is needed to reproduce the failure. However, cutting off the excess parts of a potentially large test case can be a tedious and time-consuming task if performed manually, which has led to the research and development of automated test case reduction techniques. The decade-old Hierarchical Delta Debugging (HDD) algorithm targets structured test inputs, parses them with the help of grammars and applies the minimizing Delta Debugging algorithm to the built trees.

We have investigated this algorithm and its implementation, and propose improvements in this paper to address the found shortcomings. We argue that using extended context-free grammars with HDD is beneficial in several ways and the experimental evaluation of our modernized HDD implementation, called Picireny, supports the outlined ideas: the reduced outputs are significantly smaller (by circa 25-40%) on the investigated test cases than those produced by the reference HDD implementation using standard context-free grammars. These results, together with the technical improvements that ease the use of the modernized tool, can hopefully help spreading the adaptation of HDD in practice.

References

[1]

N. Bruno. Minimizing database repros using language grammars. In Proceedings of the 13th International Conference on Extending Database Technology (EDBT ’10), pages 382–393. ACM, Mar. 2010.

Digital Library

[2]

J. Clause and A. Orso. Penumbra: Automatically identifying failure-relevant inputs using dynamic tainting. In Proceedings of the Eighteenth International Symposium on Software Testing and Analysis (ISSTA ’09), pages 249–260. ACM, July 2009.

Digital Library

[3]

N. Gupta, H. He, X. Zhang, and R. Gupta. Locating faulty code using failure-inducing chops. In Proceedings of the 20th IEEE/ACM International Conference on Automated Software Engineering (ASE ’05), pages 263–272. ACM, Nov. 2005.

Digital Library

[4]

R. Hildebrandt and A. Zeller. Simplifying failure-inducing input. In Proceedings of the 2000 ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA ’00), pages 135–145. ACM, Aug. 2000.

Digital Library

[5]

R. Hodován and Á. Kiss. Practical improvements to the minimizing delta debugging algorithm. In Proceedings of the 11th International Conference on Software Engineering and Applications (ICSOFT-EA 2016), page (to appear). SciTePress, July 2016.

[6]

B. Korel and J. Laski. Dynamic program slicing. Information Processing Letters, 29(3):155–163, Oct. 1988.

Digital Library

[7]

Z. Lin and X. Zhang. Deriving input syntactic structure from execution. In Proceedings of the 16th ACM SIGSOFT International Symposium on Foundations of Software Engineering (SIGSOFT ’08/FSE-16), pages 83–93. ACM, Nov. 2008.

Digital Library

[8]

Microsoft Corporation. Security development lifecycle (verification phase). https://www.microsoft.com/en-us/sdl/default.aspx.

[9]

G. Misherghi and Z. Su. HDD: Hierarchical delta debugging. In Proceedings of the 28th International Conference on Software Engineering (ICSE ’06), pages 142–151. ACM, May 2006.

Digital Library

[10]

G. S. Misherghi. Hierarchical delta debugging. Master’s thesis, University of California, Davis, June 2007.

[11]

T. Parr. The Definitive ANTLR 4 Reference. The Pragmatic Programmers, 2013.

Digital Library

[12]

J. Regehr, Y. Chen, P. Cuoq, E. Eide, C. Ellison, and X. Yang. Test-case reduction for C compiler bugs. In Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’12), pages 335–346. ACM, June 2012.

Digital Library

[13]

M. Renieris and S. P. Reiss. Fault localization with nearest neighbor queries. In Proceedings of the 18th IEEE International Conference on Automated Software Engineering (ASE 2003), pages 30–39. IEEE, Oct. 2003.

[14]

A. Takanen, J. DeMott, and C. Miller. Fuzzing for Software Security Testing and Quality Assurance. Artech House, 2008.

Digital Library

[15]

M. Weiser. Program slicing. In Proceedings of the 5th International Conference on Software Engineering (ICSE ’81), pages 439–449. IEEE Press, Mar. 1981.

Digital Library

[16]

A. Zeller. Yesterday, my program worked. Today, it does not. Why? In Proceedings of the 7th European Software Engineering Conference Held Jointly with the 7th ACM SIGSOFT International Symposium on Foundations of Software Engineering (ESEC/FSE ’99), volume 1687 of Lecture Notes in Computer Science, pages 253–267. Springer-Verlag, Sept. 1999.

Digital Library

[17]

A. Zeller and R. Hildebrandt. Simplifying and isolating failure-inducing input. IEEE Transactions on Software Engineering, 28(2):183–200, Feb. 2002.

Digital Library

[18]

X. Zhang, S. Tallam, and R. Gupta. Dynamic slicing long running programs through execution fast forwarding. In Proceedings of the 14th ACM SIGSOFT International Symposium on Foundations of Software Engineering (SIGSOFT ’06/FSE-14), pages 81–91. ACM, Nov. 2006.

Digital Library

Cited By

Song XWu YLiu SChen BLin YPeng XChristakis MPradel M(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
https://dl.acm.org/doi/10.1145/3650212.3652129
Jiang JJiang MNie LDing Z(2024)A source model simplification method to assist model transformation debuggingSoftware Quality Journal10.1007/s11219-024-09676-232:3(961-984)Online publication date: 24-May-2024
https://doi.org/10.1007/s11219-024-09676-2
Tian YZhang XDong YXu ZZhang MJiang YCheung SSun C(2023)On the Caching Schemes to Speed Up Program ReductionACM Transactions on Software Engineering and Methodology10.1145/361717233:1(1-30)Online publication date: 5-Sep-2023
https://dl.acm.org/doi/10.1145/3617172
Show More Cited By

Index Terms

Modernizing hierarchical delta debugging
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis
        Software testing and debugging
2. Theory of computation
  1. Formal languages and automata theory
    1. Grammars and context-free languages

Recommendations

HDDr: a recursive variant of the hierarchical Delta debugging algorithm
A-TEST 2018: Proceedings of the 9th ACM SIGSOFT International Workshop on Automating TEST Case Design, Selection, and Evaluation

The minimization of failure-inducing test cases is an important first step in the process of bug fixing. It helps focusing the expensive software engineering resources on the root of the problem by pruning down the excess from the input that is not ...
An LR parsing technique for extended context-free grammars

Extended context-free grammars allow regular expressions to appear in productions right hand sides, and are a clear and natural way to describe the syntax of programming languages. In this paper an LR parsing technique for extended context-free grammars ...
Normal form algorithms for extended context-free grammars

We investigate the complexity of a variety of normal-form transformations for extended context-free grammars, where by extended we mean that the set of right-hand sides for each nonterminal in such a grammar is a regular set. The study is motivated by ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

A-TEST 2016: Proceedings of the 7th International Workshop on Automating Test Case Design, Selection, and Evaluation

November 2016

77 pages

ISBN:9781450344012

DOI:10.1145/2994291

General Chair:
Tanja Vos,
Program Chairs:
Sigrid Eldh,
Wishnu Prasetya

Copyright © 2016 ACM.

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 the author(s) 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

SIGSOFT: ACM Special Interest Group on Software Engineering

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 November 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

FSE'16

Sponsor:

SIGSOFT

FSE'16: 24nd ACM SIGSOFT International Symposium on the Foundations of Software Engineering

November 18, 2016

WA, Seattle, USA

Upcoming Conference

ISSTA '25

Sponsor:
sigsoft

34th ACM SIGSOFT International Symposium on Software Testing and Analysis

June 25 - 28, 2025

Trondheim , Norway

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
244
Total Downloads

Downloads (Last 12 months)29
Downloads (Last 6 weeks)0

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Song XWu YLiu SChen BLin YPeng XChristakis MPradel M(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
https://dl.acm.org/doi/10.1145/3650212.3652129
Jiang JJiang MNie LDing Z(2024)A source model simplification method to assist model transformation debuggingSoftware Quality Journal10.1007/s11219-024-09676-232:3(961-984)Online publication date: 24-May-2024
https://doi.org/10.1007/s11219-024-09676-2
Tian YZhang XDong YXu ZZhang MJiang YCheung SSun C(2023)On the Caching Schemes to Speed Up Program ReductionACM Transactions on Software Engineering and Methodology10.1145/361717233:1(1-30)Online publication date: 5-Sep-2023
https://dl.acm.org/doi/10.1145/3617172
Wang GWu YZhu QXiong YZhang XZhang L(2023)A Probabilistic Delta Debugging Approach for Abstract Syntax Trees2023 IEEE 34th International Symposium on Software Reliability Engineering (ISSRE)10.1109/ISSRE59848.2023.00060(763-773)Online publication date: 9-Oct-2023
https://doi.org/10.1109/ISSRE59848.2023.00060
Vince DHodován RBársony DKiss Á(2022)The effect of hoisting on variants of Hierarchical Delta DebuggingJournal of Software: Evolution and Process10.1002/smr.248334:11Online publication date: 19-Jun-2022
https://doi.org/10.1002/smr.2483
Wang GShen RChen JXiong YZhang LSpinellis DGousios GChechik MDi Penta M(2021)Probabilistic Delta debuggingProceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3468264.3468625(881-892)Online publication date: 20-Aug-2021
https://dl.acm.org/doi/10.1145/3468264.3468625
Gharachorlu GSumner N(2021)Leveraging Models to Reduce Test Cases in Software Repositories2021 IEEE/ACM 18th International Conference on Mining Software Repositories (MSR)10.1109/MSR52588.2021.00035(230-241)Online publication date: May-2021
https://doi.org/10.1109/MSR52588.2021.00035
Kreutzer PKunze TPhilippsen M(2021)Test Case Reduction: A Framework, Benchmark, and Comparative Study2021 IEEE International Conference on Software Maintenance and Evolution (ICSME)10.1109/ICSME52107.2021.00012(58-69)Online publication date: Sep-2021
https://doi.org/10.1109/ICSME52107.2021.00012
Vikram VPadhye RSen K(2021)Growing A Test Corpus with Bonsai FuzzingProceedings of the 43rd International Conference on Software Engineering10.1109/ICSE43902.2021.00072(723-735)Online publication date: 22-May-2021
https://dl.acm.org/doi/10.1109/ICSE43902.2021.00072
Vince DHodovan RBarsony DKiss A(2021)Extending Hierarchical Delta Debugging with Hoisting2021 IEEE/ACM International Conference on Automation of Software Test (AST)10.1109/AST52587.2021.00015(60-69)Online publication date: May-2021
https://doi.org/10.1109/AST52587.2021.00015
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents