How to read the tables?
Meaning of the model-checker's results| Model-checker on the instrumented program | Observed state in Litmus | Picture |
| VERIFICATION FAILED | YES | ![]() |
| VERIFICATION SUCCESSFUL | NO | ![]() |
Reading the results in the experiments tables
The table below is an excerpt of former results we obtained for x86/podwr experiments.
- In the first column, we can read the name of the original Litmus test (with a link to the file), and the expected violation cycle. The second column gathers the results of the model-checkers for SC. As we are interested in WMM bugs, the verification for SC should be
. - The three next columns concern TSO model. The last column tells which result we should get for this program under TSO, namely
. We see in the third column that Satabs indeed finds the correct result when checking the instrumented program. ESBMC in this example is missing the counterexample. Threader is either returning an error, or killed by timeout (here, it is an error).
- Note that there are two columns for TSO results: in the first one, we instrument all the delays; in the second one, we instrument only one delay per cycle.
- We also experiment under PSO, RMO and Power, and with additional model-checkers: additional columns of results (and expected results) appear after TSO's columns.
| Name | SC | TSO (all delay/cyc) | TSO (1 delay/cyc) | Expected (TSO) | ... |
|
x86/podwr000 Fre PodWR Fre PodWR |
SatAbs: ![]() 0.60sec ESBMC:
0.30secThreader:
7.92sec... |
Cycles SatAbs:
3.94sec (x6.56) ESBMC:
8.34secThreader: ERROR/TIMEOUT[1] 491.99sec ... |
Cycles SatAbs:
2.43sec (x4.05) ESBMC:
7.58sec
Threader: ERROR/TIMEOUT[1] 182.60sec ... |
|
... |
Standard C programs
This family consists of Dekker, Szymanski, Lamport, Peterson's mutual exclusion algorithms, and Lamport's bakery algorithm.
They should answer Yes in litmus terms, or Verification Failed in verification terms, starting from x86/TSO.
All tools successfully check these programs on SC, as expected. SatAbs fails to verify their instrumented versions for every model, as expected (except in the cases where it times out). The other tools either wrongly claim to have verify it, or timeout.
| Name | SC | CAV'11 | TSO (all delay/cyc) | TSO (1 delay/cyc) | TSO (opt delay/cyc) | Expected (TSO) | PSO (all delay/cyc) | PSO (1 delay/cyc) | PSO (opt delay/cyc) | Expected (PSO) | RMO (all delay/cyc) | RMO (1 delay/cyc) | RMO (opt delay/cyc) | Expected (RMO) | Power (all delay/cyc) | Power (1 delay/cyc) | Power (opt delay/cyc) | Expected (Power) |
|
gb_dekker.c |
SatAbs: ![]() 0.23sec Satabs-prefix-first:
0.12sec
CBMC-WMM:
0.12sec
CBMC-SC:
0.13sec
C code |
Cycles
SatAbs: ![]() 2.27sec (x9.86) Satabs-prefix-first:
2.57sec
CBMC-WMM:
0.22sec
CBMC-SC:
269.04sec
Instrumented C code |
Cycles
SatAbs: ![]() 2.31sec (x10.04) Satabs-prefix-first:
3.16sec
CBMC-WMM:
0.16sec
CBMC-SC:
6.31sec
Instrumented C code |
Cycles
SatAbs: ![]() 1.63sec (x7.08) Satabs-prefix-first:
2.27sec
CBMC-WMM:
0.19sec
CBMC-SC:
4.64sec
Instrumented C code |
Cycles
SatAbs: ![]() 1.68sec (x7.30) Satabs-prefix-first:
2.37sec
CBMC-WMM:
0.22sec
CBMC-SC:
4.69sec
Instrumented C code |
UNKNOWN |
Cycles
SatAbs: ![]() 18.57sec (x80.73) Satabs-prefix-first:
25.49sec
CBMC-WMM:
0.17sec
CBMC-SC:
182.65sec
Instrumented C code |
Cycles
SatAbs: ![]() 18.54sec (x80.60) Satabs-prefix-first:
25.04sec
CBMC-WMM:
0.22sec
CBMC-SC:
182.66sec
Instrumented C code |
Cycles
SatAbs: ![]() 17.83sec (x77.52) Satabs-prefix-first:
24.87sec
CBMC-WMM:
0.18sec
CBMC-SC:
182.70sec
Instrumented C code |
UNKNOWN |
Cycles
SatAbs: ![]() 16.71sec (x72.65) Satabs-prefix-first:
26.80sec
CBMC-WMM:
0.29sec
CBMC-SC:
279.01sec
Instrumented C code |
Cycles
SatAbs: ![]() 8.44sec (x36.69) Satabs-prefix-first:
11.06sec
CBMC-WMM:
0.20sec
CBMC-SC:
205.57sec
Instrumented C code |
Cycles
SatAbs: ![]() 1.48sec (x6.43) Satabs-prefix-first:
2.46sec
CBMC-WMM:
0.23sec
CBMC-SC:
7.40sec
Instrumented C code |
UNKNOWN |
Cycles
SatAbs: ![]() 3.38sec (x14.69) Satabs-prefix-first:
4.31sec
CBMC-WMM:
0.19sec
CBMC-SC:
785.99sec
Instrumented C code |
Cycles
SatAbs: ![]() 8.04sec (x34.95) Satabs-prefix-first:
12.40sec
CBMC-WMM:
0.19sec
CBMC-SC:
484.69sec
Instrumented C code |
Cycles
SatAbs: ![]() 4.32sec (x18.78) Satabs-prefix-first:
6.28sec
CBMC-WMM:
0.23sec
CBMC-SC:
404.25sec
Instrumented C code |
UNKNOWN |
|
gb_lamport.c |
SatAbs: ![]() 0.62sec Satabs-prefix-first:
0.42sec
CBMC-WMM:
0.61sec
CBMC-SC:
0.60sec
C code |
Cycles
SatAbs: ![]() 7.27sec (x11.72) Satabs-prefix-first:
5.90sec
CBMC-WMM:
0.64sec
CBMC-SC: ERROR/TIMEOUT[130] 0.01sec Instrumented C code |
Cycles
SatAbs: ![]() 5.38sec (x8.67) Satabs-prefix-first:
4.64sec
CBMC-WMM:
0.95sec
CBMC-SC: ERROR/TIMEOUT[130] 0.01sec Instrumented C code |
Cycles
SatAbs: ![]() 16.00sec (x25.80) Satabs-prefix-first:
113.34sec
CBMC-WMM:
1.12sec
CBMC-SC: ERROR/TIMEOUT[130] 0.01sec Instrumented C code |
Cycles
SatAbs: ![]() 11.52sec (x18.58) Satabs-prefix-first:
37.40sec
CBMC-WMM:
1.01sec
CBMC-SC: ERROR/TIMEOUT[130] 0.01sec Instrumented C code |
UNKNOWN |
Cycles
SatAbs: ![]() 6.56sec (x10.58) Satabs-prefix-first:
6.70sec
CBMC-WMM:
5.69sec
CBMC-SC: ERROR/TIMEOUT[130] 0.01sec Instrumented C code |
Cycles
SatAbs: ![]() 6.59sec (x10.62) Satabs-prefix-first:
6.32sec
CBMC-WMM:
5.51sec
CBMC-SC: ERROR/TIMEOUT[130] 0.01sec Instrumented C code |
Cycles
SatAbs: ![]() 30.51sec (x49.20) Satabs-prefix-first:
44.65sec
CBMC-WMM:
4.65sec
CBMC-SC: ERROR/TIMEOUT[130] 0.01sec Instrumented C code |
UNKNOWN |
Cycles
SatAbs: ![]() 5.73sec (x9.24) Satabs-prefix-first:
6.88sec
CBMC-WMM:
1.31sec
CBMC-SC: ERROR/TIMEOUT[130] 0.01sec Instrumented C code |
Cycles
SatAbs: ![]() 5.47sec (x8.82) Satabs-prefix-first:
10.02sec
CBMC-WMM:
1.34sec
CBMC-SC: ERROR/TIMEOUT[130] 0.01sec Instrumented C code |
Cycles
SatAbs: ![]() 12.21sec (x19.69) Satabs-prefix-first:
15.65sec
CBMC-WMM:
1.69sec
CBMC-SC: ERROR/TIMEOUT[130] 0.01sec Instrumented C code |
UNKNOWN |
Cycles
SatAbs: ![]() 8.07sec (x13.01) Satabs-prefix-first:
8.72sec
CBMC-WMM:
3.03sec
CBMC-SC: ERROR/TIMEOUT[130] 0.00sec Instrumented C code |
Cycles
SatAbs: ![]() 5.89sec (x9.50) Satabs-prefix-first:
8.21sec
CBMC-WMM:
2.86sec
CBMC-SC: ERROR/TIMEOUT[130] 0.01sec Instrumented C code |
Cycles
SatAbs: ![]() 5.19sec (x8.37) Satabs-prefix-first:
5.95sec
CBMC-WMM:
2.90sec
CBMC-SC: ERROR/TIMEOUT[130] 0.01sec Instrumented C code |
UNKNOWN |
|
gb_peterson.c |
SatAbs: ![]() 0.21sec Satabs-prefix-first:
0.13sec
CBMC-WMM:
0.07sec
CBMC-SC:
0.06sec
C code |
Cycles
SatAbs: ![]() 1.05sec (x5.00) Satabs-prefix-first:
0.88sec
CBMC-WMM:
0.10sec
CBMC-SC:
27.25sec
Instrumented C code |
Cycles
SatAbs: ![]() 1.30sec (x6.19) Satabs-prefix-first:
3.11sec
CBMC-WMM:
0.09sec
CBMC-SC:
15.15sec
Instrumented C code |
Cycles
SatAbs: ![]() 0.77sec (x3.66) Satabs-prefix-first:
1.74sec
CBMC-WMM:
0.09sec
CBMC-SC:
5.20sec
Instrumented C code |
Cycles
SatAbs: ![]() 0.92sec (x4.38) Satabs-prefix-first:
1.69sec
CBMC-WMM:
0.07sec
CBMC-SC:
4.84sec
Instrumented C code |
UNKNOWN |
Cycles
SatAbs: ![]() 1.61sec (x7.66) Satabs-prefix-first:
1.17sec
CBMC-WMM:
0.09sec
CBMC-SC:
27.05sec
Instrumented C code |
Cycles
SatAbs: ![]() 1.36sec (x6.47) Satabs-prefix-first:
2.90sec
CBMC-WMM:
0.07sec
CBMC-SC:
14.19sec
Instrumented C code |
Cycles
SatAbs: ![]() 0.96sec (x4.57) Satabs-prefix-first:
1.62sec
CBMC-WMM:
0.10sec
CBMC-SC:
3.91sec
Instrumented C code |
UNKNOWN |
Cycles
SatAbs: ![]() 1.70sec (x8.09) Satabs-prefix-first:
1.35sec
CBMC-WMM:
0.11sec
CBMC-SC:
31.67sec
Instrumented C code |
Cycles
SatAbs: ![]() 24.74sec (x117.80) Satabs-prefix-first:
22.72sec
CBMC-WMM:
0.09sec
CBMC-SC:
32.06sec
Instrumented C code |
Cycles
SatAbs: ![]() 4.72sec (x22.47) Satabs-prefix-first:
12.91sec
CBMC-WMM:
0.13sec
CBMC-SC:
20.09sec
Instrumented C code |
UNKNOWN |
Cycles
SatAbs: ![]() 1.41sec (x6.71) Satabs-prefix-first:
1.05sec
CBMC-WMM:
0.10sec
CBMC-SC:
52.72sec
Instrumented C code |
Cycles
SatAbs: ![]() 16.89sec (x80.42) Satabs-prefix-first:
51.74sec
CBMC-WMM:
0.10sec
CBMC-SC:
16.64sec
Instrumented C code |
Cycles
SatAbs: ![]() 0.36sec (x1.71) Satabs-prefix-first:
0.36sec
CBMC-WMM:
0.11sec
CBMC-SC:
15.97sec
Instrumented C code |
UNKNOWN |
|
gb_szymanski.c |
SatAbs: ![]() 0.28sec Satabs-prefix-first:
0.17sec
CBMC-WMM:
3.99sec
CBMC-SC:
4.14sec
C code |
Cycles
SatAbs: ![]() 0.31sec (x1.10) Satabs-prefix-first:
0.30sec
CBMC-WMM:
2.08sec
CBMC-SC: ERROR/TIMEOUT[130] 0.01sec Instrumented C code |
Cycles
SatAbs: ![]() 0.10sec (x.35) Satabs-prefix-first:
0.15sec
CBMC-WMM:
1.94sec
CBMC-SC: ERROR/TIMEOUT[130] 0.01sec Instrumented C code |
Cycles
SatAbs: ![]() 3.57sec (x12.75) Satabs-prefix-first:
5.40sec
CBMC-WMM:
2.65sec
CBMC-SC: ERROR/TIMEOUT[130] 0.01sec Instrumented C code |
Cycles
SatAbs: ![]() 0.26sec (x.92) Satabs-prefix-first:
0.22sec
CBMC-WMM:
2.05sec
CBMC-SC: ERROR/TIMEOUT[130] 0.01sec Instrumented C code |
UNKNOWN |
Cycles
SatAbs: ![]() 0.20sec (x.71) Satabs-prefix-first:
0.10sec
CBMC-WMM:
2.17sec
CBMC-SC: ERROR/TIMEOUT[130] 0.01sec Instrumented C code |
Cycles
SatAbs: ![]() 0.12sec (x.42) Satabs-prefix-first:
0.21sec
CBMC-WMM:
2.09sec
CBMC-SC: ERROR/TIMEOUT[130] 0.01sec Instrumented C code |
Cycles
SatAbs: ![]() 0.16sec (x.57) Satabs-prefix-first:
0.11sec
CBMC-WMM:
2.17sec
CBMC-SC: ERROR/TIMEOUT[130] 0.01sec Instrumented C code |
UNKNOWN |
Cycles
SatAbs: ![]() 0.22sec (x.78) Satabs-prefix-first:
0.23sec
CBMC-WMM:
2.34sec
CBMC-SC: ERROR/TIMEOUT[0] 20.47sec Instrumented C code |
Cycles
SatAbs: ![]() 1.18sec (x4.21) Satabs-prefix-first:
1.37sec
CBMC-WMM:
2.44sec
CBMC-SC: ERROR/TIMEOUT[0] 59.37sec Instrumented C code |
Cycles
SatAbs: ![]() 0.18sec (x.64) Satabs-prefix-first:
0.28sec
CBMC-WMM:
2.26sec
CBMC-SC: ERROR/TIMEOUT[0] 19.87sec Instrumented C code |
UNKNOWN |
Cycles
SatAbs: ![]() 0.26sec (x.92) Satabs-prefix-first:
0.24sec
CBMC-WMM:
2.24sec
CBMC-SC: ERROR/TIMEOUT[0] 24.11sec Instrumented C code |
Cycles
SatAbs: ![]() 1.01sec (x3.60) Satabs-prefix-first:
1.45sec
CBMC-WMM:
2.22sec
CBMC-SC: ERROR/TIMEOUT[0] 31.89sec Instrumented C code |
Cycles
SatAbs: ![]() 30.44sec (x108.71) Satabs-prefix-first: ERROR/TIMEOUT[130] CBMC-WMM:
2.17sec
CBMC-SC: ERROR/TIMEOUT[0] 18.34sec Instrumented C code |
UNKNOWN |