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

research-article

HDDr: a recursive variant of the hierarchical Delta debugging algorithm

Authors:

Renáta Hodován,

Tibor GyimóthyAuthors Info & Claims

A-TEST 2018: Proceedings of the 9th ACM SIGSOFT International Workshop on Automating TEST Case Design, Selection, and Evaluation

Pages 16 - 22

https://doi.org/10.1145/3278186.3278189

Published: 05 November 2018 Publication History

Abstract

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 contributing to the failure. Naturally, minimization is most helpful if it is automated. The original minimizing Delta Debugging algorithm and the follow-up Hierarchical Delta Debugging approach have been invented to give a solution to this challenge. Although automated, the minimization of inputs from real-life scenarios can take hours for both approaches. This paper builds on and improves the hierarchical minimization algorithm and experiments with a recursive variant called HDDr. After evaluating HDDr on various test cases, it turns out that it can give minimal results in 29–65% less time than the baseline hierarchical algorithm. On our largest test case, this means that the minimization process gets shorter by more than 4 hours.

References

[1]

David Binkley, Nicolas Gold, Syed Islam, Jens Krinke, and Shin Yoo. 2017. Tree-Oriented vs. Line-Oriented Observation-Based Slicing. In Proceedings of the 17th IEEE International Working Conference on Source Code Analysis and Manipulation (SCAM 2017). IEEE, 21–30.

[2]

Robert Brummayer and Armin Biere. 2009. Fuzzing and Delta-debugging SMT Solvers. In Proceedings of the 7th International Workshop on Satisfiability Modulo Theories (SMT ’09). ACM, 1–5.

Digital Library

[3]

Nicolas Bruno. 2010. Minimizing Database Repros Using Language Grammars. In Proceedings of the 13th International Conference on Extending Database Technology (EDBT ’10). ACM, 382–393.

Digital Library

[4]

Lazaro Clapp, Osbert Bastani, Saswat Anand, and Alex Aiken. 2016. Minimizing GUI Event Traces. In Proceedings of the 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering (FSE 2016). ACM, 422–434.

Digital Library

[5]

James Clause and Alessandro Orso. 2009. Penumbra: Automatically Identifying Failure-relevant Inputs Using Dynamic Tainting. In Proceedings of the 18th International Symposium on Software Testing and Analysis (ISSTA ’09). ACM, 249–260.

Digital Library

[6]

Alex Groce, Mohammed Amin Alipour, Chaoqiang Zhang, Yang Chen, and John Regehr. 2014. Cause Reduction for Quick Testing. In Proceedings of the 2014 IEEE International Conference on Software Testing, Verification, and Validation (ICST ’14). IEEE Computer Society, 243–252.

Digital Library

[7]

Mouna Hammoudi, Ali Alakeel, Brian Burg, Gigon Bae, and Gregg Rothermel. 2017. Facilitating debugging of web applications through recording reduction. Empirical Software Engineering (09 May 2017).

[8]

Satia Herfert, Jibesh Patra, and Michael Pradel. 2017. Automatically Reducing Tree-structured Test Inputs. In Proceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering (ASE 2017). IEEE Press, 861–871.

Digital Library

[9]

Ralf Hildebrandt and Andreas Zeller. 2000. Simplifying Failure-Inducing Input. In Proceedings of the 2000 ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA ’00). ACM, 135–145.

Digital Library

[10]

Renáta Hodován and Ákos Kiss. 2016. Modernizing Hierarchical Delta Debugging. In Proceedings of the 7th International Workshop on Automating Test Case Design, Selection, and Evaluation (A-TEST 2016). ACM, 31–37.

Digital Library

[11]

Renáta Hodován and Ákos Kiss. 2016. Practical Improvements to the Minimizing Delta Debugging Algorithm. In Proceedings of the 11th International Joint Conference on Software Technologies (ICSOFT 2016) – Volume 1: ICSOFT-EA. SciTePress, 241–248.

[12]

Renáta Hodován, Ákos Kiss, and Tibor Gyimóthy. 2017. Coarse Hierarchical Delta Debugging. 2017 IEEE International Conference on Software Maintenance and Evolution (ICSME 2017), 194–203.

[13]

Renáta Hodován, Ákos Kiss, and Tibor Gyimóthy. 2017. Tree Preprocessing and Test Outcome Caching for Efficient Hierarchical Delta Debugging. In Proceedings of the 12th IEEE/ACM International Workshop on Automation of Software Testing (AST 2017). IEEE, 23–29.

Digital Library

[14]

Bo Jiang, Yuxuan Wu, Teng Li, and W. K. Chan. 2017. SimplyDroid: Efficient Event Sequence Simplification for Android Application. In Proceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering (ASE 2017). IEEE Press, 297–307.

Digital Library

[15]

Yong Lei and James H. Andrews. 2005. Minimization of Randomized Unit Test Cases. In Proceedings of the 16th IEEE International Symposium on Software Reliability Engineering (ISSRE ’05). IEEE Computer Society, 267–276.

Digital Library

[16]

Andreas Leitner, Manuel Oriol, Andreas Zeller, Ilinca Ciupa, and Bertrand Meyer. 2007. Efficient Unit Test Case Minimization. In Proceedings of the 22nd IEEE/ACM International Conference on Automated Software Engineering (ASE ’07). ACM, 417–420.

Digital Library

[17]

Yun Lin, Jun Sun, Yinxing Xue, Yang Liu, and Jinsong Dong. 2017. Feedbackbased Debugging. In Proceedings of the 39th International Conference on Software Engineering (ICSE ’17). IEEE Press, 393–403.

Digital Library

[18]

Ghassan Misherghi and Zhendong Su. 2006. HDD: Hierarchical Delta Debugging. In Proceedings of the 28th International Conference on Software Engineering (ICSE ’06). ACM, 142–151.

Digital Library

[19]

Ghassan Shakib Misherghi. 2007. Hierarchical Delta Debugging. Master’s thesis. University of California, Davis.

[20]

Kristi Morton and Nicolas Bruno. 2011. FlexMin: A Flexible Tool for Automatic Bug Isolation in DBMS Software. In Proceedings of the 4th International Workshop on Testing Database Systems (DBTest ’11). ACM, Article 1, 6 pages.

Digital Library

[21]

John Regehr, Yang Chen, Pascal Cuoq, Eric Eide, Chucky Ellison, and Xuejun Yang. 2012. Test-case Reduction for C Compiler Bugs. In Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’12). ACM, 335–346.

Digital Library

[22]

Colin Scott, Vjekoslav Brajkovic, George Necula, Arvind Krishnamurthy, and Scott Shenker. 2016. Minimizing Faulty Executions of Distributed Systems. In Proceedings of the 13th USENIX Symposium on Networked Systems Design and Implementation (NSDI ’16). USENIX Association, 291–309.

Digital Library

[23]

Chengnian Sun, Yuanbo Li, Qirun Zhang, Tianxiao Gu, and Zhendong Su. 2018. Perses: Syntax-guided Program Reduction. In Proceedings of the 40th International Conference on Software Engineering (ICSE 2018). ACM, 361–371.

Digital Library

[24]

Frank Tip. 1994. A Survey of Program Slicing Techniques. Technical Report. CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands.

Digital Library

[25]

Jie Wang. 2016. Constraint-based Event Trace Reduction. In Proceedings of the 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering (FSE 2016). ACM, 1106–1108.

Digital Library

[26]

Andreas Zeller. 1999. 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) (Lecture Notes in Computer Science), Vol. 1687. Springer-Verlag, 253–267.

Digital Library

[27]

Andreas Zeller and Ralf Hildebrandt. 2002. Simplifying and Isolating Failure-Inducing Input. IEEE Transactions on Software Engineering 28, 2 (Feb. 2002), 183–200. Abstract 1 Introduction 2 Background 3 Recursive HDD 4 Experimental Results 5 Related Work 6 Summary Acknowledgments References

Digital Library

Cited By

Qiu YHu JZhang QYin HChristakis MPradel M(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
https://dl.acm.org/doi/10.1145/3650212.3680399
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
Vince DKiss Á(2024)Evaluation of the fixed‐point iteration of minimizing delta debuggingJournal of Software: Evolution and Process10.1002/smr.2702Online publication date: 23-Jun-2024
https://doi.org/10.1002/smr.2702
Show More Cited By

Index Terms

HDDr: a recursive variant of the hierarchical Delta debugging algorithm
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis
        Software testing and debugging

Recommendations

Probabilistic Delta debugging
ESEC/FSE 2021: Proceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering

The delta debugging problem concerns how to reduce an object while preserving a certain property, and widely exists in many applications, such as compiler development, regression fault localization, and software debloating. Given the importance of delta ...
Modernizing hierarchical delta debugging
A-TEST 2016: Proceedings of the 7th International Workshop on Automating Test Case Design, Selection, and Evaluation

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 ...
Iterating the minimizing Delta debugging algorithm
A-TEST 2022: Proceedings of the 13th International Workshop on Automating Test Case Design, Selection and Evaluation

Probably the most well-known solution to automated test case minimization is the minimizing Delta Debugging algorithm (DDMIN). It is widely used because it “just works” on any kind of input. In this paper, we focus on the fixed-point iteration of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

A-TEST 2018: Proceedings of the 9th ACM SIGSOFT International Workshop on Automating TEST Case Design, Selection, and Evaluation

November 2018

66 pages

ISBN:9781450360531

DOI:10.1145/3278186

General Chair:
Wishnu Prasetya,
Program Chairs:
Tanja E. J. Vos,
Sinem Getir

Copyright © 2018 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: 05 November 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Ministry of Finance of Hungary

Conference

ESEC/FSE '18

Sponsor:

SIGSOFT

ESEC/FSE '18: 26th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering

November 5, 2018

FL, Lake Buena Vista, 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

17
Total Citations
View Citations
179
Total Downloads

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

Reflects downloads up to 20 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Qiu YHu JZhang QYin HChristakis MPradel M(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
https://dl.acm.org/doi/10.1145/3650212.3680399
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
Vince DKiss Á(2024)Evaluation of the fixed‐point iteration of minimizing delta debuggingJournal of Software: Evolution and Process10.1002/smr.2702Online publication date: 23-Jun-2024
https://doi.org/10.1002/smr.2702
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
Eberlein MSmytzek MSteinhöfel DGrunske LZeller AChandra SBlincoe KTonella P(2023)Semantic DebuggingProceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3611643.3616296(438-449)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3611643.3616296
Gharachorlu GSumner NJust RFraser G(2023)Type Batched Program ReductionProceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3597926.3598065(398-410)Online publication date: 12-Jul-2023
https://dl.acm.org/doi/10.1145/3597926.3598065
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
Song XLin YWu YZhang YNg SPeng XDong JMei HRoychoudhury ACadar CKim M(2022)RegMiner: mining replicable regression dataset from code repositoriesProceedings of the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3540250.3558929(1711-1715)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3540250.3558929
Song XLin YNg SWu YPeng XDong JMei HRyu SSmaragdakis Y(2022)RegMiner: towards constructing a large regression dataset from code evolution historyProceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3533767.3534224(314-326)Online publication date: 18-Jul-2022
https://dl.acm.org/doi/10.1145/3533767.3534224
Vince DKiss Á(2022)Cache Optimizations for Test Case Reduction2022 IEEE 22nd International Conference on Software Quality, Reliability and Security (QRS)10.1109/QRS57517.2022.00052(442-453)Online publication date: Dec-2022
https://doi.org/10.1109/QRS57517.2022.00052
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