Microsoft powerpoint - somadeltadebugging.ppt

ƒ Have a large input that causes a failure (e.g., a core dump) but this input is to ƒ Example: gcc takes input and crashes!
ƒ Question: What is the smallest input
ƒ Developed by Andreas Zeller et al.
Institute for Software Technology
Institute for Software Technology
double mult(double z[], int n) {
WHICH PART OF
BUG.C CAUSES
double mult(double z[], int n) {
CRASH?????
void copy(double to[], from[], int count) {
void copy(double to[], from[], int count) {
int main (.) { . return copy(y,x,SIZE);}
int main (.) { . return copy(y,x,SIZE);}
Institute for Software Technology
Institute for Software Technology
t(double z[],int n){int
ƒ The resulting substring is substantially Institute for Software Technology
Institute for Software Technology
ƒ Testing function that takes a program and tests whether it produces a failure. There are three different outcomes of such a testing function: test(x)
ƒ The test produces the failure (FAIL, 8) ƒ The test produces indeterminate results Delta Debugging
Institute for Software Technology
Institute for Software Technology
ƒ Given:
ƒ An input c‘ ⊆ c is said to be the global ƒ A testing function test(x) mapping an input minimum iff test(c‘) = 8 and there exists no c‘‘ with |c‘‘|≤|c‘| where ƒ An input c with test(c) = 8.
ƒ Goal: Search for a smaller c‘ ⊂ c so that
ƒ An input c‘ ⊆ c is said to be the local minimum iff test(c‘) = 8 and there exists no c‘‘⊂ c‘ where test(c‘‘) = 8.
Institute for Software Technology
Institute for Software Technology
Minimizing delta debugging algorithm
ƒ Input: Let test and c be given such that
test(c)=8 and test(∅)=9 hold.
ƒ Output: A c‘ ⊆ c such that test(c‘)=8
ƒ An input c‘⊆ c is n-minimal iff test(c‘) = 8 and there exists no c‘‘⊂ c‘ with |c‘| - |c‘‘| ≤ n where test(c‘‘) = 8.
Institute for Software Technology
Institute for Software Technology
ƒ ddmin2(c,n) =
ddmin2(∆ ,2) if ∃i∈{1,.,n}: test(∆ )=8
ddmin2(∇ ,max(n-1,2))
ddmin2(c,min(|c|,2n)) else if n<|c|
4. DONE otherwise
test(c)=8 and n≤|c| Institute for Software Technology
Institute for Software Technology
ƒ ddmin returns a 1-minimal result.
ƒ The complexity of ddmin is O(|c|2).
ƒ In the best case the complexity of ddmin ƒ test(x) = 8 iff “2“ ⊆ x ⊆ c Institute for Software Technology
Institute for Software Technology
ƒ test(x) = 8 iff “18“ ⊆ x ⊆ c ƒ Not only for inputs of type STRING ƒ Extensions of ddmin can be used to Institute for Software Technology
Institute for Software Technology

Source: http://www.ist.tugraz.at/_attach/Publish/Soma/SOMADeltaDebugging.pdf