Delta debugging: Difference between revisions

Revision as of 09:09, 21 January 2022

Latest revision as of 00:46, 31 January 2025

(5 intermediate revisions by 5 users not shown)

Line 1:

{{Sources exist|date=January 2025}}

{{multiple issues|

{{Cleanup|reason = spelling, grammar, capitalization, word usage, and punctuation need to be checked|date = December 2014}}

{{primary sources|date=April 2011}}

{{notability|date=October 2010}}

}}

'''Delta Debuggingdebugging''' is a methodology to automate the [[debugging]] of programs using a scientific approach of hypothesis-trial-result loop. This methodology was first developed by Andreas Zeller of the Saarland University in 1999.<ref>{{cite bookconference |last1=Zeller |first1=Andreas |book-title=Software Engineering — ESEC/FSE '99 |volume=1687 |pages=253–267 |chaptertitle=Yesterday, my program worked. Today, it does not. Why?|date=1999 |publisher=Springer|edition=Software Engineering—ESEC/FSE’99 [https://dx.doi.org/10.1007/3-540-48166-4_16 doi:10.1007/3-540-48166-4_16]|doi=10.1007/3-540-48166-4_16 |series=Lecture Notes in Computer Science |isbn=978-3-540-66538-0}}</ref>

InThe practice,delta the Delta Debuggingdebugging algorithm builds on [[unit testing]] to isolateisolates failure causes automatically - by systematically narrowing down failure-inducing circumstances until a minimal set remains. For example, if you can supply a test case that will produce the bug you are looking for, then you can feed that to the Deltadelta Debuggingdebugging algorithm, which will then simply try to trim useless functions and lines of code that are not needed to reproduce the bug, until a 1-minimal program is found.

Delta Debuggingdebugging has been applied to isolate failure-inducing program input (e.g. an HTML page that makes a Web browser fail), failure-inducing user interaction (e.g. the keystrokes that make a program crash), or failure-inducing changes to the program code (e.g. after a failing regression test).

Later, some softwareSoftware development tools have been inspired by Delta Debugging,delta suchdebugging asinclude the [[Bisection (software engineering)|bisect commands]] of [[revision control]] systems (e.g., git-bisect, svn-bisect, hg-bisect, etc.), which, instead of working on the program's code, apply the delta debugging methodology on the code history by comparing various versions until the faulty change is found.

Recently, '''Network Dialog Minimization''' a technique based on delta debugging is proposed to find the smallest subset of network traffic from the original dialog, that when replayed still achieves the same goal as the original dialog <ref>{{cite conference|last1 = M. Zubair Rafique|title=Network Dialog Minimization and Network Dialog Diffing: Two Novel Primitives for Network Security Applications|book-title = In Proceedings of 30th Annual Computer Security Applications Conference (ACSAC 2014)|publisher = ACM|url=https://zubairrafique.files.wordpress.com/2014/09/ndm_acsac14_cr.pdf|display-authors=etal}}</ref>

== Software ==

* [https://github.com/dsw/delta delta] - a computer program to minimize "interesting" files subject to a test of their interestingness <ref>danielwilkerson.com</ref>

* [https://www.st.cs.uni-saarland.de/dd/DD.py DD.py] - a Python implementation of Delta Debugging; also see its [https://www.st.cs.uni-saarland.de/dd/ddusage.php3 tutorial]

* [http://www.squarefree.com/lithium/using.html Lithium] - a Python implementation of an enhanced Delta Debugging algorithm

* [http://embed.cs.utah.edu/creduce/ C-Reduce], which reduces source files written in C/C++, uses the Delta algorithms

* [https://github.com/perses-project/perses Perses] - a language-agnostic reducer for program minimization, which employs Delta debugging algorithm.

* [https://github.com/CyberShadow/DustMite DustMite] - A general-purpose data reduction tool, mainly used to reduce [[D_(programming_language)|D]] programs <ref>[https://dlang.org/blog/2020/04/13/dustmite-the-general-purpose-data-reduction-tool/| DustMite, the general purpose data reduction tool]</ref>.

* [http://www.st.cs.uni-sb.de/eclipse/ Eclipse Plug-Ins]

** DDinput - Failure-Inducing Input

** [https://archive.today/20060223234113/http://ddchange.martin-burger.de/ DDchange] - Failure-Inducing Changes

** DDstate - Failure-Inducing States

* [https://www.st.cs.uni-saarland.de/testing/xmlmate/ XMLmate]<ref>{{cite news|title=Detecting Software Errors via Genetic Algorithms|url=http://www.pddnet.com/news/2014/03/detecting-software-errors-genetic-algorithms|accessdate=22 July 2015|date=2014-03-05}}</ref>

* [https://github.com/eschulte/delta-debug Common Lisp implementation]

* [http://www.st.cs.uni-saarland.de/askigor/downloads/ Igor - command line tool]

==See also==

Line 36 ⟶ 15:

==References==

* Andreas Zeller: <cite>Why Programs Fail: A Guide to Systematic Debugging</cite>, Morgan Kaufmann, {{ISBN|1-55860-866-4}}

* [https://www.youtube.com/watch?v=SzRqd4YeLlM Learning from Code History] A presentation at Google Tech Talk from the original inventor of the Delta Debugging

<references />

==External links==

*[http://www.st.cs.uni-sb.de/dd/ Delta Debugging project] - extensive collection of links to delta debugging tools and methods

*[https://www.udacity.com/course/software-debugging--cs259 Udacity course on Software Debugging by Andreas Zeller]

[[Category:Debugging]]

{{Compu-prog-stub}}