[[Concurrency Tool Comparison]]


== Model Description == 

The benchmark contains a data race. As the number of threads are created the value of a global variable is updated. An incorrect assumption on atomicity allows more threads to be created leading to a data
inconsistency. The two parameters to the '''airline''' model are: '''ticketsIssued''' and '''cushion'''. The minimum depth of the error is pushed deeper in the execution trace when we increase the value of the '''cushion''' and keep the total number of threads, '''ticketsIssued''', constant.


Classes: 2

SLOC: 31

Parameters: (#ticketsIssued, cushion)

== Summary Results Table ==

{| align=center | border=1
|- bgcolor="white" |
| colspan=5 align="center" | airline (20,1)
|- bgcolor="lightblue"
! Tool
! Trials (successful)
! Time
! Transition (paths)
! Max Depth (error depth)
|-
| JPF "Randomized DFS"
| 4996 (0) 0.00
| align="right"| NA
| NA (NA)
| NA (NA)
|-
| JPF Stateless Random Walk
| 11125 (1) 0.00
| align="right"| NA
| NA (NA)
| NA (NA)
|-
| ConTest
| 1000 (0) 0.00
| align="right"| NA
| NA (NA)
| NA (NA)
|-
| CalFuzzer
| 100 (0) 0.00
| align="right"| NA
| NA (NA)
| NA (NA)
|-
| JPF "Abstraction Guided Refinement"
| 1 (1) 1.00
| align="right"| 7.46s
| 3609.00 (NA)
| 95.00 (95.00)
|- bgcolor="white" |
| colspan=5 align="center" | airline (20,2)
|- bgcolor="lightblue"
! Tool
! Trials (successful)
! Time
! Transition (paths)
! Max Depth (error depth)
|-
| JPF "Randomized DFS"
| 4999 (6) 0.00
| align="right"| 562.24s
| 8577017.83 (0.00)
| 122.17 (120.00)
|-
| JPF Stateless Random Walk
| 14998 (0) 0.00
| align="right"| NA
| NA (NA)
| NA (NA)
|-
| ConTest
| 1000 (0) 0.00
| align="right"| NA
| NA (NA)
| NA (NA)
|-
| CalFuzzer
| 100 (0) 0.00
| align="right"| NA
| NA (NA)
| NA (NA)
|-
| JPF "Abstraction Guided Refinement"
| 1 (1) 1.00
| align="right"| 7.46s
| 3279.00 (NA)
| 78.00 (78.00)
|- bgcolor="white" |
| colspan=5 align="center" | airline (20,3)
|- bgcolor="lightblue"
! Tool
! Trials (successful)
! Time
! Transition (paths)
! Max Depth (error depth)
|-
| JPF "Randomized DFS"
| 4992 (24) 0.00
| align="right"| 375.78s
| 5905884.67 (0.00)
| 121.75 (119.75)
|-
| JPF Stateless Random Walk
| 11132 (19) 0.00
| align="right"| NA
| NA (NA)
| NA (NA)
|-
| ConTest
| 1000 (0) 0.00
| align="right"| NA
| NA (NA)
| NA (NA)
|-
| CalFuzzer
| 100 (0) 0.00
| align="right"| NA
| NA (NA)
| NA (NA)
|-
| JPF "Abstraction Guided Refinement"
| 1 (1) 1.00
| align="right"| 7.46s
| 3210.00 (NA)
| 75.00 (75.00)
|- bgcolor="white" |
| colspan=5 align="center" | airline (20,4)
|- bgcolor="lightblue"
! Tool
! Trials (successful)
! Time
! Transition (paths)
! Max Depth (error depth)
|-
| JPF "Randomized DFS"
| 5000 (116) 0.02
| align="right"| 461.52s
| 6711300.33 (0.00)
| 121.91 (119.87)
|-
| JPF Stateless Random Walk
| 11129 (70) 0.01
| align="right"| NA
| NA (NA)
| NA (NA)
|-
| ConTest
| 1000 (0) 0.00
| align="right"| NA
| NA (NA)
| NA (NA)
|-
| CalFuzzer
| 100 (0) 0.00
| align="right"| NA
| NA (NA)
| NA (NA)
|-
| JPF "Abstraction Guided Refinement"
| 1 (1) 1.00
| align="right"| 7.46s
| 3134.00 (NA)
| 72.00 (72.00)
|- bgcolor="white" |
| colspan=5 align="center" | airline (20,5)
|- bgcolor="lightblue"
! Tool
! Trials (successful)
! Time
! Transition (paths)
! Max Depth (error depth)
|-
| JPF "Randomized DFS"
| 5000 (360) 0.07
| align="right"| 448.37s
| 6595025.32 (0.00)
| 121.91 (119.97)
|-
| JPF Stateless Random Walk
| 11140 (197) 0.02
| align="right"| NA
| NA (NA)
| NA (NA)
|-
| ConTest
| 1000 (0) 0.00
| align="right"| NA
| NA (NA)
| NA (NA)
|-
| CalFuzzer
| 100 (0) 0.00
| align="right"| NA
| NA (NA)
| NA (NA)
|-
| JPF "Abstraction Guided Refinement"
| 1 (1) 1.00
| align="right"| 5.46s
| 3042.00 (NA)
| 69.00 (69.00)
|- bgcolor="white" |
| colspan=5 align="center" | airline (20,6)
|- bgcolor="lightblue"
! Tool
! Trials (successful)
! Time
! Transition (paths)
! Max Depth (error depth)
|-
| JPF "Randomized DFS"
| 4999 (876) 0.18
| align="right"| 464.12s
| 6820760.72 (0.00)
| 121.75 (119.74)
|-
| JPF Stateless Random Walk
| 11159 (405) 0.04
| align="right"| NA
| NA (NA)
| NA (NA)
|-
| CalFuzzer
| 100 (0) 0.00
| align="right"| NA
| NA (NA)
| NA (NA)
|-
| JPF "Abstraction Guided Refinement"
| 1 (1) 1.00
| align="right"| 5.46s
| 2935.00 (NA)
| 66.00 (66.00)
|- bgcolor="white" |
| colspan=5 align="center" | airline (20,7)
|- bgcolor="lightblue"
! Tool
! Trials (successful)
! Time
! Transition (paths)
! Max Depth (error depth)
|-
| JPF "Randomized DFS"
| 5000 (1665) 0.33
| align="right"| 300.64s
| 4332959.57 (0.00)
| 121.48 (119.28)
|-
| JPF Stateless Random Walk
| 11206 (790) 0.07
| align="right"| NA
| NA (NA)
| NA (NA)
|-
| CalFuzzer
| 100 (0) 0.00
| align="right"| NA
| NA (NA)
| NA (NA)
|-
| JPF "Abstraction Guided Refinement"
| 1 (1) 1.00
| align="right"| 5.46s
| 2680.00 (NA)
| 60.00 (60.00)
|- bgcolor="white" |
| colspan=5 align="center" | airline (20,8)
|- bgcolor="lightblue"
! Tool
! Trials (successful)
! Time
! Transition (paths)
! Max Depth (error depth)
|-
| JPF "Randomized DFS"
| 5000 (2507) 0.50
| align="right"| 285.85s
| 4111966.14 (0.00)
| 121.07 (118.62)
|-
| JPF Stateless Random Walk
| 10123 (696) 0.07
| align="right"| NA
| NA (NA)
| NA (NA)
|-
| CalFuzzer
| 100 (0) 0.00
| align="right"| NA
| NA (NA)
| NA (NA)
|-
| JPF "Abstraction Guided Refinement"
| 1 (1) 1.00
| align="right"| 5.46s
| 2680.00 (NA)
| 60.00 (60.00)
|- bgcolor="white" |
| colspan=5 align="center" | airline (4,1)
|- bgcolor="lightblue"
! Tool
! Trials (successful)
! Time
! Transition (paths)
! Max Depth (error depth)
|-
| JPF "Randomized DFS"
| 200 (200) 1.00
| align="right"| 0.81s
| 5776.74 (0.00)
| 14.28 (13.23)
|-
| JPF Stateless Random Walk
| 1011 (98) 0.10
| align="right"| NA
| NA (NA)
| NA (NA)
|-
| CalFuzzer
| 100 (0) 0.00
| align="right"| NA
| NA (NA)
| NA (NA)
|-
| JPF "Abstraction Guided Refinement"
| 1 (1) 1.00
| align="right"| 3.46s
| 61.00 (NA)
| 17.00 (17.00)
|- bgcolor="white" |
| colspan=5 align="center" | airline (4,2)
|- bgcolor="lightblue"
! Tool
! Trials (successful)
! Time
! Transition (paths)
! Max Depth (error depth)
|-
| JPF "Randomized DFS"
| 200 (200) 1.00
| align="right"| 0.25s
| 655.86 (0.00)
| 13.75 (12.59)
|-
| JPF Stateless Random Walk
| 1021 (433) 0.42
| align="right"| NA
| NA (NA)
| NA (NA)
|-
| CalFuzzer
| 100 (0) 0.00
| align="right"| NA
| NA (NA)
| NA (NA)
|-
| JPF "Abstraction Guided Refinement"
| 1 (1) 1.00
| align="right"| 3.46s
| 46.00 (NA)
| 14.00 (14.00)
|- bgcolor="white" |
| colspan=5 align="center" | airline (5,1)
|- bgcolor="lightblue"
! Tool
! Trials (successful)
! Time
! Transition (paths)
! Max Depth (error depth)
|-
| JPF "Randomized DFS"
| 200 (200) 1.00
| align="right"| 58.19s
| 670929.50 (0.00)
| 25.28 (22.17)
|-
| JPF Stateless Random Walk
| 1021 (111) 0.11
| align="right"| NA
| NA (NA)
| NA (NA)
|-
| CalFuzzer
| 100 (0) 0.00
| align="right"| NA
| NA (NA)
| NA (NA)
|-
| JPF "Abstraction Guided Refinement"
| 1 (1) 1.00
| align="right"| 3.46s
| 98.00 (NA)
| 21.00 (21.00)
|- bgcolor="white" |
| colspan=5 align="center" | airline (5,3)
|- bgcolor="lightblue"
! Tool
! Trials (successful)
! Time
! Transition (paths)
! Max Depth (error depth)
|-
| JPF "Randomized DFS"
| 200 (200) 1.00
| align="right"| 0.31s
| 689.12 (0.00)
| 16.77 (15.96)
|-
| JPF Stateless Random Walk
| 1098 (725) 0.66
| align="right"| NA
| NA (NA)
| NA (NA)
|-
| CalFuzzer
| 100 (0) 0.00
| align="right"| NA
| NA (NA)
| NA (NA)
|-
| JPF "Abstraction Guided Refinement"
| 1 (1) 1.00
| align="right"| 3.46s
| 65.00 (NA)
| 15.00 (15.00)
|- bgcolor="white" |
| colspan=5 align="center" | airline (6,1)
|- bgcolor="lightblue"
! Tool
! Trials (successful)
! Time
! Transition (paths)
! Max Depth (error depth)
|-
| JPF "Randomized DFS"
| 100 (100) 1.00
| align="right"| 394.33s
| 8876025.11 (0.00)
| 37.99 (36.33)
|-
| JPF Stateless Random Walk
| 10129 (29) 0.00
| align="right"| NA
| NA (NA)
| NA (NA)
|-
| ConTest
| 1000 (0) 0.00
| align="right"| NA
| NA (NA)
| NA (NA)
|-
| CalFuzzer
| 100 (0) 0.00
| align="right"| NA
| NA (NA)
| NA (NA)
|-
| JPF "Abstraction Guided Refinement"
| 1 (1) 1.00
| align="right"| 3.46s
| 163.00 (NA)
| 28.00 (28.00)
|- bgcolor="white" |
| colspan=5 align="center" | airline (6,2)
|- bgcolor="lightblue"
! Tool
! Trials (successful)
! Time
! Transition (paths)
! Max Depth (error depth)
|-
| JPF "Randomized DFS"
| 100 (100) 1.00
| align="right"| 54.62s
| 1166530.67 (0.00)
| 38.01 (35.77)
|-
| JPF Stateless Random Walk
| 10129 (306) 0.03
| align="right"| NA
| NA (NA)
| NA (NA)
|-
| ConTest
| 1000 (0) 0.00
| align="right"| NA
| NA (NA)
| NA (NA)
|-
| CalFuzzer
| 100 (0) 0.00
| align="right"| NA
| NA (NA)
| NA (NA)
|-
| JPF "Abstraction Guided Refinement"
| 1 (1) 1.00
| align="right"| 3.46s
| 127.00 (NA)
| 22.00 (22.00)
|}

==Chess==

* ChessMonitorVolatiles=true
* The Bound column specifies the ChessBound parameter

{| align=center | border=1 | -bgcolor=grey
! Airline Params !! Bound !! Tests !! Found Error !! Time Taken !! Steps (Depth)
|- 
| 4,1 ||  2 || 45,618  || No || 231.240 secs || 114
|- 
| 4,1 ||  3 || >=394,000  || Yes || 1983.522 secs || 114
|-
| 4,2 ||  2 || >=13,000 || Yes || 67.533 secs || 
|-
| 5,1 ||  2 || 115,648  || No || 672.582 secs || 
|-
| 5,1 ||  3 || >=638,000  || No || 3604.559 secs || 
|-
| 5,1 ||  4 || >=654,000  || No || 3602.187 secs || 
|-
| 5,3 ||  2 || 115,694  || No || 640.290 secs || 
|-
| 5,3 ||  3 || >=655,000  || No || 3647.179 secs || 
|-
|}

==Java PathFinder==
===Stateless Random Walk===

* 10,000 Trials of Random Walk
* The ratio of the error discovery trials over the total number of trials is the 
path error density. 

{| align=center | border=1 | -bgcolor=grey
! Parameters !! Path Error Density
|-
| 6,1 || 0.003
|-
| 6,2 || 0.030
|-
| 20,1 || 0.0
|-
| 20,2 || 0.0
|- 
| 20,8 || 0.069
|-
| 20,2 || 0.000
|-
| 20,3 || 0.0
|-
| 20,4 || 0.0002
|- 
| 20,5 || 0.002
|-
| 20,6 || 0.008
|-
| 20,7 || 0.023
|-
| 20,8 || 0.067
|}

===Stateful Randomized Depth-first search===

* 100 randomized depth-first search trial, where each trial is time-bounded at
one hour. A total of 100 computation hours dedicated in discovering the error. 

* 2 MB of RAM allocated on each machine

* The Error Discovering Trials is the number of trials that discovered an error
among the initially launched trials (100). 

{| align="center" | border=1
|- bgcolor="lightblue"
! Parameters
! Trials (successful)
! Time
! Transition (paths)
! Max Depth (error depth)
!  abs time (ms)
!  rel. time (ms)
!  search depth
!  errorDepth
!  new states
!  revisited states
!  end states
!  backtracks
!  processed states
!  restored states
!  total memory (kB)
!  max total memory
!  free memory (kB)
!  heap objects
!  max heap objects

|-
|(4,1)
| 200 (200) 100.00%
| align="right"| 0.81s
| 5776.74 (0.00)
| 14.28 (13.23)
| align="right" | 809.18
| align="right" | 809.18
| align="right" | 14.28
| align="right" | 13.23
| align="right" | 1564.63
| align="right" | 4212.11
| align="right" | 1.19
| align="right" | 5763.02
| align="right" | 1549.78
| align="right" | 0.00
| align="right" | 15553.28
| align="right" | 466048.00
| align="right" | 0.00
| align="right" | 126.00
| align="right" | 126.00
|-
|(4,2)
| 200 (200) 100.00%
| align="right"| 0.25s
| 655.86 (0.00)
| 13.75 (12.59)
| align="right" | 248.02
| align="right" | 248.02
| align="right" | 13.75
| align="right" | 12.59
| align="right" | 224.00
| align="right" | 431.86
| align="right" | 0.65
| align="right" | 642.76
| align="right" | 210.31
| align="right" | 0.00
| align="right" | 10607.04
| align="right" | 466048.00
| align="right" | 0.00
| align="right" | 125.67
| align="right" | 125.67
|-
|(5,1)
| 200 (200) 100.00%
| align="right"| 58.19s
| 670929.49 (0.00)
| 25.27 (22.17)
| align="right" | 58193.73
| align="right" | 3638.97
| align="right" | 25.27
| align="right" | 22.17
| align="right" | 162604.83
| align="right" | 508324.66
| align="right" | 2.25
| align="right" | 670906.62
| align="right" | 162579.92
| align="right" | 0.00
| align="right" | 86600.00
| align="right" | 647806.72
| align="right" | 25705.27
| align="right" | 185.53
| align="right" | 185.81
|-
|(5,3)
| 200 (200) 100.00%
| align="right"| 0.31s
| 689.12 (0.00)
| 16.77 (15.96)
| align="right" | 305.05
| align="right" | 305.05
| align="right" | 16.77
| align="right" | 15.96
| align="right" | 217.67
| align="right" | 471.45
| align="right" | 0.41
| align="right" | 672.66
| align="right" | 200.84
| align="right" | 0.00
| align="right" | 12360.00
| align="right" | 466048.00
| align="right" | 0.00
| align="right" | 135.50
| align="right" | 135.50
|-
|(20,1)
| 4996 (0) 0.00%
| align="right"| 
| 
| 
| align="right" |
| align="right" |
| align="right" |
| align="right" |
| align="right" |
| align="right" |
| align="right" |
| align="right" |
| align="right" |
| align="right" |
| align="right" |
| align="right" |
| align="right" |
| align="right" |
| align="right" |
|-
|(20,2)
| 4999 (6) 0.12%
| align="right"| 562.24s
| 8577017.83 (0.00)
| 122.17 (120.00)
| align="right" | 562241.83
| align="right" | 3794.33
| align="right" | 122.17
| align="right" | 120.00
| align="right" | 1550536.17
| align="right" | 7026481.67
| align="right" | 5.17
| align="right" | 8576896.83
| align="right" | 1550410.50
| align="right" | 0.00
| align="right" | 290080.00
| align="right" | 932096.00
| align="right" | 170562.17
| align="right" | 241.00
| align="right" | 241.00
|-
|(20,3)
| 4992 (24) 0.48%
| align="right"| 375.78s
| 5905884.67 (0.00)
| 121.75 (119.75)
| align="right" | 375779.33
| align="right" | 4861.17
| align="right" | 121.75
| align="right" | 119.75
| align="right" | 1036133.12
| align="right" | 4869751.54
| align="right" | 4.54
| align="right" | 5905763.92
| align="right" | 1036008.00
| align="right" | 0.00
| align="right" | 291136.00
| align="right" | 932096.00
| align="right" | 144767.75
| align="right" | 241.00
| align="right" | 241.00
|-
|(20,4)
| 5000 (116) 2.32%
| align="right"| 461.52s
| 6711300.33 (0.00)
| 121.91 (119.87)
| align="right" | 461516.77
| align="right" | 4707.47
| align="right" | 121.91
| align="right" | 119.87
| align="right" | 1153254.41
| align="right" | 5558045.91
| align="right" | 4.46
| align="right" | 6711179.46
| align="right" | 1153129.28
| align="right" | 0.00
| align="right" | 278695.17
| align="right" | 932096.00
| align="right" | 124799.82
| align="right" | 241.00
| align="right" | 241.00
|-
|(20,5)
| 5000 (360) 7.20%
| align="right"| 448.37s
| 6595025.33 (0.00)
| 121.91 (119.97)
| align="right" | 448365.35
| align="right" | 4467.86
| align="right" | 121.91
| align="right" | 119.97
| align="right" | 1147611.88
| align="right" | 5447413.44
| align="right" | 4.42
| align="right" | 6594904.36
| align="right" | 1147486.72
| align="right" | 0.00
| align="right" | 277988.27
| align="right" | 932096.00
| align="right" | 115750.97
| align="right" | 241.00
| align="right" | 241.00
|-
|(20,6)
| 4999 (876) 17.52%
| align="right"| 464.12s
| 6820760.72 (0.00)
| 121.75 (119.74)
| align="right" | 464123.49
| align="right" | 4134.85
| align="right" | 121.75
| align="right" | 119.74
| align="right" | 1171490.87
| align="right" | 5649269.84
| align="right" | 4.13
| align="right" | 6820639.98
| align="right" | 1171366.22
| align="right" | 0.00
| align="right" | 258675.51
| align="right" | 932096.00
| align="right" | 101841.83
| align="right" | 241.00
| align="right" | 241.00
|-
|(20,7)
| 5000 (1665) 33.30%
| align="right"| 300.64s
| 4332959.57 (0.00)
| 121.48 (119.28)
| align="right" | 300641.40
| align="right" | 4031.49
| align="right" | 121.48
| align="right" | 119.28
| align="right" | 748081.85
| align="right" | 3584877.72
| align="right" | 3.73
| align="right" | 4332839.30
| align="right" | 747958.06
| align="right" | 0.00
| align="right" | 227616.67
| align="right" | 932096.00
| align="right" | 95063.95
| align="right" | 240.99
| align="right" | 240.99
|-
|(20,8)
| 5000 (2507) 50.14%
| align="right"| 285.85s
| 4111966.14 (0.00)
| 121.07 (118.62)
| align="right" | 285851.37
| align="right" | 3876.37
| align="right" | 121.07
| align="right" | 118.62
| align="right" | 711998.03
| align="right" | 3399968.11
| align="right" | 3.41
| align="right" | 4111846.51
| align="right" | 711875.19
| align="right" | 0.00
| align="right" | 209404.25
| align="right" | 932096.00
| align="right" | 89145.86
| align="right" | 240.89
| align="right" | 240.89
|-
|(6,1)
| 100 (100) 100.00%
| align="right"| 394.33s
| 8876025.11 (0.00)
| 37.99 (36.33)
| align="right" | 394325.24
| align="right" | 4607.12
| align="right" | 37.99
| align="right" | 36.33
| align="right" | 1618914.82
| align="right" | 7257110.29
| align="right" | 5.10
| align="right" | 8875987.78
| align="right" | 1618872.63
| align="right" | 0.00
| align="right" | 1310046.72
| align="right" | 6990528.00
| align="right" | 580593.25
| align="right" | 185.00
| align="right" | 185.00
|-
|(6,2)
| 100 (100) 100.00%
| align="right"| 54.62s
| 1166530.67 (0.00)
| 38.01 (35.77)
| align="right" | 54619.07
| align="right" | 3717.12
| align="right" | 38.01
| align="right" | 35.77
| align="right" | 226845.59
| align="right" | 939685.08
| align="right" | 3.73
| align="right" | 1166493.90
| align="right" | 226805.31
| align="right" | 0.00
| align="right" | 317019.52
| align="right" | 6990528.00
| align="right" | 116839.71
| align="right" | 185.00
| align="right" | 185.00
|}


==ConTest==

* 1000 independent trials

* The ratio of the error discovery trials over the total number of trials is the 
path error density. 

{| align=center | border=1 | -bgcolor=grey
! Airline Params !! Path Error Density
|- 
| 6,1 || 0.00
|-
| 6,2 || 0.00
|-
| 20,1 || 0.00
|-
| 20,2 || 0.00
|-
| 20,3 || 0.00
|-
| 20,4 || 0.00
|-
| 20,5 || 0.00
|}

==CalFuzzer==

* 100 independent trials

* The ratio of the error discovery trials over the total number of trials is the 
path error density. 

{| align=center | border=1 | -bgcolor=grey
! Airline Params !! Path Error Density
|- 
| 4,1 || 0.00
|-
| 4,2 || 0.00
|- 
| 5,1 || 0.00
|-
| 5,3 || 0.00
|- 
| 6,1 || 0.00
|-
| 6,2 || 0.00
|-
| 20,1 || 0.00
|-
| 20,2 || 0.00
|-
| 20,3 || 0.00
|-
| 20,4 || 0.00
|-
| 20,5 || 0.00
|-
| 20,6 || 0.00
|-
| 20,7 || 0.00
|-
| 20,8 || 0.00
|}