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.
