SPICED: Simple PROMELA Interpreter with
Crucial Event Detection
SPICED is an experimental model checking tool that implements the lattice theoretic techniques described in our paper: Producing short counterexamples using Crucial Events. SPICED is based on the SPIN implementation, and uses the same input language, PROMELA, to specify models.
Download
The tool, along with all the examples we have run it on, is available here.
SPICED produces error trails in the same format as SPIN. These error trails can be examined using SPIN's guided simulation feature (spin -p).
For now, SPICED only supports UNIX platforms (actually, was only tested on Linux).
You *MUST* gunzip and untar the distribution file in your home directory (wherever ~ redirects to).
Experimental Results
We ran SPICED on a large collection of PROMELA models from the BEEM database. Many models in the BEEM database contain errors injected into them, and specify the LTL properties to be verified on these models. For SPIN, the LTL properties were specified either in the form of simple assert() statements whenever possible, or as never claims. The "Model" column in the table below contains links to the PROMELA source for each of the models. The "Formula" column contains links to the CETL property specified in SPICED.
|
SPICED |
|
SPIN |
|||||||||
Model |
Time |
States |
Transitions |
Memory (MB) |
Formula |
Length of trail |
Trail reduction factor |
Time |
States |
Transitions |
Memory (MB) |
Length of trail |
0.014 |
99 |
90 |
3.147 |
39 |
67.56410256 |
0.018 |
1317 |
1320 |
2.622 |
2635 |
||
0.014 |
246 |
287 |
3.147 |
58 |
51.48275862 |
0.02 |
1492 |
1503 |
2.622 |
2986 |
||
0.03 |
6664 |
12605 |
3.454 |
74 |
413.8918919 |
0.125 |
15312 |
15792 |
4.606 |
30628 |
||
0.032 |
65387 |
141208 |
7.038 |
82 |
382.7926829 |
0.13 |
15692 |
16252 |
6.628 |
31389 |
||
0.016 |
16 |
9 |
3.147 |
8 |
18.875 |
0.009 |
74 |
81 |
2.622 |
151 |
||
0.016 |
16 |
9 |
3.147 |
8 |
18.875 |
0.01 |
74 |
81 |
2.622 |
151 |
||
0.018 |
17 |
10 |
3.147 |
9 |
24.88888889 |
0.01 |
110 |
121 |
2.622 |
224 |
||
0.018 |
18 |
11 |
3.147 |
10 |
29.7 |
0.01 |
146 |
161 |
2.622 |
297 |
||
0.018 |
18 |
11 |
3.147 |
10 |
29.7 |
0.01 |
146 |
161 |
2.622 |
297 |
||
0.018 |
18 |
11 |
3.147 |
10 |
29.7 |
0.01 |
146 |
161 |
2.622 |
297 |
||
0.019 |
19 |
12 |
3.147 |
11 |
33.63636364 |
0.01 |
182 |
201 |
2.622 |
370 |
||
0.018 |
2601 |
2658 |
3.249 |
510 |
1.97254902 |
0.019 |
2071 |
4412 |
2.622 |
1006 |
||
0.012 |
45 |
40 |
3.147 |
28 |
5.714285714 |
0.009 |
163 |
423 |
2.622 |
160 |
||
0.017 |
2257 |
3929 |
3.249 |
55 |
6.509090909 |
0.012 |
179 |
197 |
2.622 |
358 |
||
0.013 |
57 |
52 |
3.147 |
37 |
16.48648649 |
0.034 |
748 |
2397 |
2.622 |
610 |
||
1.226 |
401575 |
912557 |
25.573 |
158 |
8.303797468 |
0.018 |
656 |
701 |
2.622 |
1312 |
||
0.013 |
69 |
64 |
3.147 |
46 |
18.60869565 |
0.016 |
896 |
3181 |
2.622 |
856 |
||
5.797 |
1.74E+06 |
3.99313e |
100.837 |
670 |
2.87761194 |
0.016 |
964 |
1044 |
2.622 |
1928 |
||
5.982 |
1.50E+06 |
4.00E+06 |
92.849 |
77 |
5.662337662 |
0.01 |
218 |
221 |
2.622 |
436 |
||
0.01 |
85 |
74 |
3.147 |
53 |
1.283018868 |
0.01 |
34 |
34 |
2.622 |
68 |
||
0.012 |
747 |
850 |
3.249 |
426 |
1.863849765 |
0.01 |
397 |
397 |
2.622 |
794 |
||
0.011 |
212 |
224 |
3.147 |
123 |
1.382113821 |
0.01 |
85 |
85 |
2.622 |
170 |
||
0.013 |
23 |
15 |
3.147 |
14 |
6.071428571 |
0.008 |
48 |
57 |
2.622 |
85 |
||
0.013 |
24 |
16 |
3.147 |
15 |
15.33333333 |
0.01 |
156 |
224 |
2.622 |
230 |
||
0.013 |
26 |
18 |
3.147 |
17 |
91.88235294 |
0.02 |
1237 |
2348 |
2.622 |
1562 |
||
0.014 |
27 |
19 |
3.147 |
18 |
297.8333333 |
0.05 |
6454 |
16351 |
3.032 |
5361 |
||
0.014 |
28 |
20 |
3.147 |
19 |
268.3684211 |
0.04 |
4744 |
10211 |
2.929 |
5099 |
||
0.015 |
28 |
20 |
3.147 |
19 |
777.3684211 |
0.155 |
21860 |
62703 |
5.118 |
14770 |
||
0.015 |
28 |
20 |
3.147 |
19 |
497.3684211 |
0.07 |
8016 |
19323 |
3.236 |
9450 |
||
0.012 |
1436 |
1481 |
2.724 |
86 |
1 |
0.01 |
1433 |
1479 |
2.622 |
86 |
||
0.036 |
9859 |
17191 |
3.236 |
30 |
1 |
0.03 |
9856 |
7333 |
3.032 |
30 |
||
0.414 |
190318 |
191715 |
16.446 |
261 |
1 |
0.38 |
190315 |
191713 |
13.988 |
261 |
||
0.014 |
1060 |
2102 |
2.827 |
1256 |
2.265923567 |
0.027 |
3186 |
4144 |
2.929 |
2846 |
||
0.03 |
4185 |
7527 |
3.134 |
5056 |
3.836234177 |
0.133 |
22386 |
29769 |
5.502 |
19396 |
||
0.013 |
230 |
352 |
3.147 |
28 |
10.85714286 |
0.01 |
152 |
168 |
2.622 |
304 |
||
0.011 |
92 |
105 |
3.147 |
14 |
21.71428571 |
0.01 |
152 |
168 |
2.622 |
304 |
||
0.011 |
63 |
67 |
3.147 |
17 |
5.411764706 |
0.01 |
46 |
50 |
2.622 |
92 |
||
0.014 |
1221 |
2609 |
3.147 |
29 |
28.89655172 |
0.02 |
419 |
474 |
2.622 |
838 |
||
0.012 |
483 |
683 |
3.147 |
19 |
37.05263158 |
0.01 |
352 |
401 |
2.622 |
704 |
||
0.06 |
6850 |
18913 |
3.454 |
30 |
44.33333333 |
0.02 |
665 |
749 |
2.622 |
1330 |
||
0.015 |
1087 |
2027 |
3.147 |
25 |
4.32 |
0.01 |
54 |
58 |
2.622 |
108 |
||
0.009 |
47 |
79 |
2.724 |
42 |
1 |
0.009 |
363 |
810 |
2.622 |
42 |
||
0.194 |
50931 |
86545 |
9.24 |
52597 |
1.604996483 |
0.634 |
166133 |
340572 |
17.611 |
84418 |
||
0.011 |
345 |
501 |
3.147 |
12 |
22.33333333 |
0.01 |
133 |
147 |
2.622 |
268 |
||
0.011 |
118 |
131 |
3.147 |
29 |
2.482758621 |
0.01 |
35 |
37 |
2.622 |
72 |
||
0.017 |
2710 |
4930 |
3.249 |
13 |
91.15384615 |
0.01 |
591 |
653 |
2.622 |
1185 |
||
0.012 |
771 |
1148 |
3.147 |
30 |
2.3 |
0.01 |
33 |
35 |
2.622 |
69 |
||
0.094 |
30227 |
65051 |
4.888 |
14 |
403.2857143 |
0.03 |
2821 |
3109 |
2.724 |
5646 |
||
0.032 |
8871 |
16010 |
3.659 |
36 |
2.222222222 |
0.01 |
38 |
40 |
2.622 |
80 |
||
0.016 |
83 |
123 |
2.724 |
63 |
3.396825397 |
0.01 |
370 |
433 |
2.622 |
214 |
||
0.011 |
21 |
11 |
2.724 |
11 |
3.363636364 |
0.01 |
296 |
408 |
2.622 |
37 |
||
0.012 |
24 |
13 |
2.724 |
13 |
3.230769231 |
0.01 |
1313 |
1958 |
2.724 |
42 |
||
0.012 |
27 |
15 |
2.724 |
15 |
3.133333333 |
0.03 |
4001 |
6331 |
2.929 |
47 |
||
0.013 |
27 |
15 |
2.724 |
15 |
3.466666667 |
0.04 |
4003 |
6333 |
3.032 |
52 |
||
0.011 |
592 |
849 |
3.147 |
46 |
6.130434783 |
0.01 |
141 |
144 |
2.622 |
282 |
||
0.01 |
93 |
89 |
3.147 |
59 |
6.508474576 |
0.01 |
192 |
203 |
2.622 |
384 |
||
0.01 |
50 |
46 |
3.147 |
37 |
8.162162162 |
0.01 |
151 |
162 |
2.622 |
302 |
||
0.018 |
3004 |
5008 |
3.249 |
95 |
16.16842105 |
0.02 |
768 |
826 |
2.622 |
1536 |
||
0.011 |
175 |
171 |
3.147 |
110 |
56.2 |
0.04 |
3091 |
3344 |
2.929 |
6182 |
||
0.011 |
75 |
71 |
3.147 |
59 |
97.28813559 |
0.03 |
2870 |
3098 |
2.827 |
5740 |
||
0.092 |
29080 |
58572 |
4.888 |
159 |
125.6855346 |
0.098 |
9992 |
11897 |
9.931 |
19984 |
||
0.018 |
15 |
11 |
3.147 |
6 |
4.833333333 |
0.01 |
15 |
18 |
2.622 |
29 |
||
0.011 |
13 |
9 |
3.147 |
5 |
98.8 |
0.01 |
969 |
3236 |
2.622 |
494 |
||
0.011 |
15 |
11 |
3.147 |
6 |
80 |
0.01 |
253 |
353 |
2.622 |
480 |
||
0.011 |
13 |
9 |
3.147 |
5 |
16687.6 |
0.356 |
41719 |
64708 |
9.086 |
83438 |
||
0.011 |
15 |
11 |
3.147 |
6 |
8106.166667 |
0.212 |
24319 |
31584 |
6.36 |
48637 |
||
0.044 |
15 |
11 |
3.147 |
6 |
141948.5 |
3.826 |
425846 |
553093 |
86.219 |
851691 |
||
0.051 |
13 |
9 |
3.147 |
5 |
|
****
Could not complete ****** |
|
|||||
0.011 |
15 |
11 |
3.147 |
6 |
275788.8333 |
7.563 |
827367 |
1.07E+06 |
168.907 |
1654733 |
||
0.888 |
153775 |
197109 |
21.579 |
41 |
5.390243902 |
0.38 |
40161 |
103804 |
6.718 |
221 |
||
0.014 |
80 |
110 |
3.147 |
31 |
17.67741935 |
0.01 |
274 |
297 |
2.622 |
548 |
||
0.061 |
19006 |
45770 |
4.069 |
25 |
9.28 |
0.01 |
116 |
121 |
2.622 |
232 |
||
0.015 |
138 |
249 |
3.147 |
37 |
197.3513514 |
0.04 |
3651 |
4762 |
2.827 |
7302 |
||
4.976 |
1.20251e |
3.63667e |
70.424 |
28 |
56.14285714 |
0.01 |
786 |
828 |
2.622 |
1572 |
||
0.018 |
256 |
592 |
3.147 |
43 |
1811.534884 |
0.313 |
38948 |
47109 |
9.188 |
77896 |