CPTEST
The purpose of our experiments was to check that CPTEST can automatically detect, localize and correct faults in well-known constraint programs, namely Golomb rulers, N-queens, social golfer and car sequencing problems. For that, we manually injected significant faults in these CP programs in order to generate faulty OPL programs, called mutants. We fed CPTEST with the resulting faulty constraint programs and let CPTEST to correct automatically them.
Tab.1 shows the main results on the four problems. It contains four columns, named mutation, detection, localization and correction. The columns related to mutation show the various mutants while the columns named detection give the non-conformity points that reveal the existence of faults in the mutants and the time consumption. The columns localization give the suspicious constraints and the columns correction give two sets of constraints: a set of constraints to be removed and a set of constraints to be added in order to correct P.
Tab1.Fault detection, localization and correction on classical benchmark problems
Golomb Rulers (m=6) |
Mutants |
Fault injected |
Detection |
Localization |
Correction |
||||
non_conformity |
time(s) |
susp_ct |
time(s) |
removed_ct |
added_ct(EC) |
time(s) |
|||
Mut1 | ct2 |
[0 1 3 6 13 20] |
0.86 |
EmptySet |
096 |
EmptySet |
99 |
17.43 |
|
Mut2 | ct3 |
[0 1 3 10 13 20] |
1.32 |
EmptySet |
2.65 |
EmptySet |
84 |
27.03 |
|
Mut3 | ct3 |
[0 1 3 6 13 20] |
0.67 |
EmptySet |
4.96 |
EmptySet |
89 |
46.70 |
|
Mut4 | ct5 |
[0 9 11 12 15 19] |
1.01 |
EmptySet |
10.54 |
EmptySet |
8 |
29.63 |
|
Mut5 | ct1 |
sol(Mut5)=EmtySet |
10.46 |
ct1 |
9.57 |
ct1 |
3 |
1 698.04 |
|
Mut6 | ct7 |
sol(Mut6)= EmptySet |
9.37 |
ct7 |
9.36 |
ct7 |
38 |
107.81 |
|
Mut7 | ct9 |
sol(Mut7)= EmptySet |
35.10 |
ct9 |
13.50 |
ct9 |
EmptySet |
108.45 |
|
N-Queens (n=8) | Mut1 | ct11 |
sol(Mut1)=EmptySet |
8.32 |
ct11 |
7.53 |
ct11 |
EmptySet |
18.21 |
Mut2 | ct12 |
sol(Mut2)=EmptySet |
8.21 |
ct12 |
8.10 |
ct12 |
EmptySet |
18.10 |
|
Mut3 | ct11 |
sol(Mut3)=EmptySet |
7.85 |
ct11 |
8.14 |
ct11 |
EmptySet |
18.35 |
|
Mut4 | ct12 |
sol(Mut2)=EmptySet |
8.06 |
ct12 |
8.16 |
ct12 |
EmptySet |
18.23 |
|
Mut5 | ct4 |
[8 7 6 5 4 3 2 1] |
2.78 |
ct4 |
2.32 |
ct4 |
57 |
7.21 |
|
Mut6 | ct3 |
[7 2 3 6 8 1 5 4] |
3.34 |
EmptySet |
0.98 |
EmptySet |
111 |
9.28 |
|
Mut7 | ct1 |
[8 4 3 6 5 7 2 1] |
3.07 |
EmptySet |
0.53 |
EmptySet |
111 |
9.12 |
|
social golfer (sg_I) | Mut1 | ct1 |
sol(Mut1)=EmptySet |
10.28 |
ct1 |
3.65 |
ct1 |
112 |
32.95 |
Mut2 | ct2 |
sg1 |
0.31 |
EmptySet |
3.51 |
EmptySet |
111 |
18.32 |
|
Mut3 | ct3 |
sol(Mut3)=EmptySet |
9.85 |
ct3 |
3.71 |
ct3 |
112 |
36.28 |
|
Mut4 | ct4 |
sol(Mut4)=EmptySet |
9.37 |
ct4 |
3.64 |
ct4 |
112 |
67.39 |
|
ct5 |
ct5 |
112 |
|||||||
Mut5 | ct5 |
sol(Mut5)=EmptySet |
9.21 |
ct5 |
3.75 |
ct5 |
112 |
34.18 |
|
sg_I: weeks = 4; groups = 3; groupSize = 3; |
|||||||||
sg1=[[1 1 1 1] [1 2 2 2] [1 3 3 3] [2 1 3 3] [2 2 2 1] [2 2 1 1] [3 3 3 2] [3 1 1 2] [3 3 2 3]] |
|||||||||
car sequencing (cSec_I) |
Mut1 | ct2 |
[4 5 4 6 3 6 5 1 3 2] |
5.68 |
EmptySet |
1.34 |
EmptySet |
32 |
6.09 |
Mut2 | ct3 |
[4 1 6 4 3 5 3 6 2 5] |
5.82 |
EmptySet |
1.54 |
EmptySet |
32 |
6.28 |
|
Mut3 | ct2 |
[4 6 2 5 3 6 1 3 5 4] |
7.18 |
EmptySet |
1.51 |
EmptySet |
31 |
3.28 |
|
Mut4 | ct2 |
sol(Mut4)=EmptySet |
2.78 |
ct2 |
3.07 |
ct2 |
37 |
34.95 |
|
Mut5 | ct1 |
sol(Mut5)=EmptySet |
2.62 |
ct1 |
4.96 |
ct1 |
EmptySet |
9.08 |
|
Mut6 | ct6 |
sol(Mut6)=EmptySet |
2.64 |
ct6 |
5.09 |
ct6 |
EmptySet |
9.23 |
|
Mut7 | ct5 |
sol(Mut7)=EmptySet |
2.40 |
ct5 |
5.09 |
ct5 |
EmptySet |
14.98 |
|
ct6 |
ct6 |
EmptySet |
|||||||
cSeq_I: nbSlots = 10; nbCars = 6; nbOptions = 5; demand = [1, 1, 2, 2, 2, 2]; | |||||||||
capacity = [[1,2],[2,3],[1,3],[2,5],[1,5]]; optionDemand = [5 ,6 ,3 ,4 ,2]; | |||||||||
option = [[ 1, 0, 0, 0, 1, 1],[ 0, 0, 1, 1, 0, 1],[ 1, 0, 0, 0, 1, 0],[ 1, 1, 0, 1, 0, 0],[ 0, 0, 1, 0, 0, 0]]; | |||||||||
susp. ct: suspicious constraints, EC: elementary constraint |
All our experiments were performed on Intel Core2 Duo CPU 2.40Ghz machine with 2.00 GB of RAM.
[1] Jeffrey A. Clark and Dhiraj K. Pradhan. Fault injection. Computer, 28(6):47–56, 1995.