Delta Debugging

Once we have reproduced a program failure, we must find out what is relevant:

• What does the failure actually depend on. We should simplify test cases to make debugging easier so we can identify what faults depend on, and make test cases easier to communicate.

To simplify…

• Use binary search to cut a test case in half and iterate
• We can automate this
  • Using a binary search, throw away half the input and see if the output is wrong, if not go back to the previous state and discard the other half of the input. Repeat until we have simplified our complex input to our minimally simplified input
  • If both halves pass, instead of a binary, we can divide our input into many subsets (our deltas), each subset having a small change. This increases the change of finding the failing input subset but is slower
  • In general, start with few and large changes and increment to more and smaller changes
• Let $R$ be the set of possible inputs
• $r_P\in R$ corresponds to an input that passes
• $r_F\in R$ corresponds to an input that fails
• We let R denote the set of all possible inputs
• We can go from one input r1 to another input r2 by a series of changes
• A change $\delta$ is mapping $R\to R$ which takes one input and changes it to another input
• A change $\delta$ can be decomposed to a number of elementary changes ${\delta }_1,{\delta }_2,\dots ,{\delta }_n$ where $\delta$ is the composition of each sub-delta function in a left to right order (we apply ${\delta }_i$ to $r$ then apply ${\delta }_j$ to that output)

In summary

• We have an input without failure $r_P$
• We have an input with failure $r_F$
• We have a set of changes $C_F=\{{\delta }_1,{\delta }_2,\dots ,{\delta }_n\}$ such that $r_f=({\delta }_1\circ {\delta }_2\circ \cdots \circ {\delta }_n)(r_P)$
• Each subset c of $C_F$ is a test case

Given a test case c we should like to know if the input generated by applying changes in c to $r_P$ causes the same failure as $r_F$.

• We define the function $Powerset(c_F)=\{P,F,?\}$ such that, given $c=\{{\delta }_1,{\delta }_2,\dots ,{\delta }_n\}\subseteq c_F$, $test(c)=F$ iff $({\delta }_1\circ {\delta }_2\circ \cdots \circ {\delta }_n)(r_P)$ is a failing input

Hint

Once again, the whole point of this is to minimize our test cases so they are not so big

We want to find the smallest test case c such that $test(c)=F$, a failing test case is called the global minimum of $c_F$ if for all $c^{\prime }\subseteq c_F$, $|c^{\prime }|<|c|⟹test(c^{\prime })\ne F$.

The global minimum is the smallest set of changes which will make the program fail.

Finding the global minimum may require performing an exponential number of tests. Instead of looking for this global minimum, we can search for a 1-minimal input which is a set of changes that cause the failure but removing any change causes the failure to go away.

A failing test case $c\subseteq c_F$ is called a local minimum of $c_F$ if: for all $c^{\prime }\subset c,test(c^{\prime })\ne F$. A failing test case $c\subseteq c_F$ is n-minimal if for all $c^{\prime }\subset c,|c|-|c^{\prime }|\le n⟹test(c^{\prime })\ne F$ and it is 1-minimal if for all ${\delta }_i\in c,test(c-{\delta }_i)\ne F$.

The main trade off here is minimality guarantees vs computational costs. 1 minimality is the sweet spot.

To find a 1-minimal subset of c:

• If for all changes in the test case, if you remove a a change (try this on each change) and the failure disappears, then c is 1-minimal
• Otherwise, if removing the element still causes a failure, we found a smaller subset, recurse

Runtime

In the worst case, we remove one element from the set per iteration, after trying every other element:

• Work is potentially $N+(N-1)+(N-2)+\dots$ This is $O(N^2)$

It is silly to remove one element at a time, we can try to Divide and Conquer by dividing the change set in 2 initially and increase the number of subsets if we can’t make progress.

Minimization Algorithm

This delta debugging algorithm finds a 1-minimal test case: The idea is:

• Partition the set $c_F$ to ${\Delta }_1,{\Delta }_2,\dots ,{\Delta }_n$ roughly equal chunks
• ${\Delta }_1,{\Delta }_2,\dots ,{\Delta }_n$ are pairwise disjoint and $c_F={\Delta }_1\cup {\Delta }_2\cup \cdots \cup {\Delta }_n$
• The complement of ${\Delta }_i$ is defined as ${\nabla }_i=c_F-{\Delta }_i$
• Start with n = 2
• Test each test case defined by each partition and its complement
• Reduces the test case if a smaller failure inducing set is found, otherwise it refines the partition Steps

1. Start with n=2 and $\Delta$ test set
2. Test each ${\Delta }_1,{\Delta }_2,\dots ,{\Delta }_n$ and each ${\nabla }_{}1,{\nabla }_2,\dots ,{\nabla }_n$
3. There are three possible outcomes:
   1. Some ${\Delta }_i$ causes failures: go to step 1 with $\Delta ={\Delta }_i$ and n = 2
   2. Some ${\nabla }_i$ causes failures: Go to step 1 with $\Delta ={\nabla }_i$ and n = n-1
   3. No test causes failure: If granularity can be refined, go to step 1 with n = n*2, otherwise you found the 1 minimal set The worst case here is still quadratic but single failures converge in log N time.