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.