10. Delta debugging

Question 1

General Delta Debugging Algorithm

Answer 1

Divides input into larger blocks and tests all subsets for failures.
smaller and smaller if still failing, remove the passing ones

Question 2

R

Answer 2

set of possible inputs

Question 3

rp E R

Answer 3

corresponds to an input that passes

Question 4

rf E R

Answer 4

corresponds to an input that fails

Question 5

Change (represented by a backwards 6)

Answer 5

is a mapping R->R which takes one input and changes it to another input

Question 6

test:Powerset(cf)->

Answer 6

either P, F or ?

Question 7

Goal of delta debugging

Answer 7

find the smallest test case c such that test(c) = F

Question 8

global minimum

Answer 8

a failing test case c of cf if every other smaller size test from cf does not cause the test to output F

smallest set of changes which will make the program fail
can require an exponential number of tests

Question 9

1-minimal

Answer 9

Find a set of changes that cause the failure but removing any change causes the failure to go away

Question 10

local minimum: failing test case c in cf

Answer 10

if for all c’ in c, test(c’) != F

c’ is all things not c

Question 11

n-minimal: failing test case c in cf

Answer 11

if for all c’ in c, |c|-|c’| <= n –> test(c’) != F

if the difference in size between c and c’ is less than n then the test function applied to c’ does not return false

Question 12

1-minimal: failing test case c in cf

Answer 12

if for all changes in c, test(c-{change}) != F

if we remove a change from c and it doesn’t = false

Question 13

Naive Algorithm for 1 minimal subset

Answer 13

if for all changesI in c, test(c-{changesI}) != F, then c is 1-minimal
else recurse on c-{change} for some change in c, test(c-{change}) = F

Question 14

Naive Algorithm for 1 minimal worst case runtime

Answer 14

O(N^2)

work is potentially N+ (n-1) + (n-2)…

Question 15

Minimization algorithms

Answer 15

Start with n=2
partition the set cf into delta1, delta2, …, deltan
define the complement of deltai as updsidedownDeltai=cf - deltai

test each test case defined by each partition and it complement
reduce the test case if a smaller failure inducing set is found, otherwise it refines the partition by n=n*2

Question 16

minimization algorithm psuedo code

Answer 16

1. n=2 and delta as test case
2. test each delta and each nambla (upsidedown delta)
3. Possible outcomes:
   3a. Some deltai causes failure: go to step 1 with delta =deltai and n=2
   3b. some namblai causes failure: go to step 1 with delta = namblai and n=n-1
   3c. no test causes failure: if granularity can be redefined, go to step1 with delta = delta and n=n*2. If not, Done. Found 1-minimal subset

Question 17

Example of minimization algo

Answer 17

lesson 10.28

Question 18

Use case of minimization?

Answer 18

fuzzing input
input find a failure but it is likely huge
so minimize the fuzz input

Question 19

Delta debugging is fully automatic

Answer 19

False

Question 20

Delta debugging finds the smallest failing subset of a failing input in polynomial time

Answer 20

false

Question 21

Delta Debugging finds 1-minimal instead of local minimum test case due to performance

Answer 21

true

Question 22

delta debugging may find a different sized subset of a failing input depending on the order in which it tests different input partitions

Answer 22

true

Question 23

delta debugging is also effective at reducing non-deterministically failing inputs

Answer 23

false

Question 24

Delta debugging bad news

Answer 24

probably must be re-implemented for each significant system to exploit knowledge changes
not portable

Question 25

delta debugging good news

Answer 25

relatively simple algorithm, big payoff

worth reimplementing