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 ﬁnd a 1minimal test case:
1. Reduce to subset: Split the current conﬁguration into n partitions. Test each partition for failure. If a partition does induce the failure, then treat it as the current conﬁguration 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 conﬁguration and resume at Step 1.
3. Increase granularity: Try splitting the current conﬁguration into smaller partitions, 2n if possible, where n is the current number of partitions. Resume at Step 1 with the smaller partitions. If the conﬁguration cannot be broken down into smaller partitions, the current conﬁguration is 1minimal and the algorithm terminates.
Leave a Reply