Delta Debugging

References:
Download Delta from delta.tigris.org
Why Programs Fail has won a Software Development Jolt Productivity Award!
Eclipse Plug-Ins - Software Engineering Chair (Prof. Zeller) - Saarland University
DDchange - DDchangeWiki
Delta Debugging article on Wikipedia
Delta Debugging articles by Andreas Zeller



See Also:
Episode 101: Podcast with Andreas Zeller on Debugging | Software Engineering Radio

Video by Andreas Zeller on Debugging the Debugging activities
Video YouTube - Learning from Code History
Mining Software Archives by Andreas Zeller
About Andreas Zeller - S/W Engg. Chair at Saarland University


Publications by Prof. Andreas Zeller

Adv Debugging - My Program Worked Yesterday, but Not Today (WYNOT) by Andreas Zellar

Brief Notes of my understanding of on Delta Debugging as discussed in “Worked Yesterday, NOt Today" by Andreas Zeller 
Note:  To understand the basic premise and constraints/approaches of Delta-Debugging referred to the pdf link to:

1. Analyse the tables/graphs carefully. (80% of the understanding comes from the example tables/graphs)
2. Connect the WYNOT talk with Andreas Zellar's podcast on Software Engineering Radio.

Problem: Yesterday's code works but Today's code doesn't. How do we find the change(s) which induces the test-case failure.
Context: Looking through the CVS history we find that N changes have been added since Yesterday.

Alternative: Normally we would need run the debugger to reproduce the failure and then try to collect information which induces it.  But this requires a programmer to interactively query the program state using a debugger.
Can the debugging be automated without needing the programmer?

Strategy: Delta Debugging using a test-case to reproduce the failure.
Data Method:
Using the Scientific Method we can first try to reduce the Input Data in a binary search mechanism to isolate the minimum data which causes the failure.
Code Method:

1. Simple Method: When failure is caused by a single change. We can try to isolate the change which causes the failure by doing a binary search through the change history. If there are N changes between Y(esterday) and T(oday) we test 'k/2'th change where 1 <= k <= N. We go on partitioning until we find a failure-free change. The latest failing change is the culprit. Complexity of this binary search is O (log N)
2. Complex Method: When failure is caused by a combination of changes. Unfortunately it's Not always possible to use the Simple Method in the case when combination of changes cause the failure. In such a situation we need to identify at least 2 (or more) changes which together cause the failure. 

• Divide the change history into N changes
• Group N changes into say 4 units i.e. N = N/4 * 4
• Generate combinations with different units.
• Test combinations for the failure. 
• Prune any units which don't participate in the failure at all.
• Recursive above steps by sub-dividing the units above (quarters into octets and so on) until we finally we end up with minimal changes that reproduce the failure.

Proposed Plans to Reduce to Reduce Computation and Avoid Inconsistent Configurations :
a) Group related changes - changes on common date/file/variable are more likely to be related. Group them into a single unit to avoid dependency across units.
b) Prune configurations when they're obvious dead-ends e.g. Where change dependency is chained all the way (Today) 10->9->8->7->6->5->4->3->2->1 (Yesterday)
c) Exclude changed code which is never executed.

See Also:
Pdf: "WYNOT - Worked Yesterday, NOt Today"
Andreas Zeller
Podcast on Software Engineering Radio
Delta Debugging