How to read the tables?
Meaning of the model-checker's resultsModel-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.30sec Threader: 7.92sec ... |
Cycles SatAbs: 3.94sec (x6.56) ESBMC: 8.34sec Threader: 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 |