Tag Archive for Iterative Delta Debugging

Iterative Delta Debugging

Algorithm:

1
2
3
4
5
6
7
8
9
10
11
12
13
original_version = current_version = latest_version();
patchset = {}
original_result = current_result = test(original_version);
while (current_result = pass) {
current_version = predecessor(current_version);
current_result = test(current_version ⊕ patchset);
if (current_result = original_result) {
delta = DD(current_version, original_version);
patchset = patchset∪delta;
original_version = current_version;
}
}
return delta;

The ddmin algorithm proceeds by executing the following steps to find a 1-minimal test case:

1. Reduce to subset: Split the current configuration into n partitions. Test each partition for failure. If a partition does induce the failure, then treat it as the current configuration and resume at Step 1.
2. Reduce to complement: Test the complement of each partition. If any induces the failure then treat it as the current configuration and resume at Step 1.
3. Increase granularity: Try splitting the current configuration into smaller partitions, 2n if possible, where n is the current number of partitions. Resume at Step 1 with the smaller partitions. If the configuration cannot be broken down into smaller partitions, the current configuration is 1-minimal and the algorithm terminates.

www.000webhost.com