TY - JOUR
T1 - State-cover testing for nondeterministic terminating concurrent programs with an infinite number of synchronization sequences
AU - Lin, Che Sheng
AU - Hwang, Gwan Hwan
N1 - Funding Information:
The authors would like to thank the anonymous referees for a number of useful suggestions to improve the paper. Che-Sheng Lin and Gwan-Hwan Hwang’s work was supported in part by the Republic of China Science Council under grant 95-2221-E-003-004 and 98-2220-E-003-002.
PY - 2013/9/1
Y1 - 2013/9/1
N2 - Concurrent programs exhibit nondeterministic behavior in that multiple executions thereof with the same input might produce different sequences of synchronization events and different results. This is because different executions of a concurrent program with the same input may exhibit different interleavings. Thus, one of the major issues in the testing of concurrent programs is how to explore different interleavings or exhaust all the possible interleavings of the target programs. However, for terminating concurrent programs that have cyclic state spaces due to using iterative statements such as busy-waiting loops, they might have an infinite number of feasible synchronization sequences; that is, there is an infinite number of possible interleavings, which makes it impossible to explore all the possible interleavings for this type of concurrent program. To overcome this problem, we propose a testing scheme called dynamic effective testing that can perform state-cover testing for nondeterministic terminating concurrent programs with an infinite number of synchronization sequences. Dynamic effective testing does not require static analysis of the target concurrent program or the assistance of a model checker, and thus is loosely coupled to the syntax of the target concurrent program. It only needs to analyze sequences of synchronization events produced by the execution of the concurrent programs for race detection and state-traversal control. Therefore, the method is easy to port to different programming languages. In addition, only reiterated states discovered in a single SYN-sequence need to be stored. The implementation and experimental results obtained with real code demonstrate that source-code-level dynamic testing can be systematically performed on nondeterministic concurrent programs with infinite synchronization sequences.
AB - Concurrent programs exhibit nondeterministic behavior in that multiple executions thereof with the same input might produce different sequences of synchronization events and different results. This is because different executions of a concurrent program with the same input may exhibit different interleavings. Thus, one of the major issues in the testing of concurrent programs is how to explore different interleavings or exhaust all the possible interleavings of the target programs. However, for terminating concurrent programs that have cyclic state spaces due to using iterative statements such as busy-waiting loops, they might have an infinite number of feasible synchronization sequences; that is, there is an infinite number of possible interleavings, which makes it impossible to explore all the possible interleavings for this type of concurrent program. To overcome this problem, we propose a testing scheme called dynamic effective testing that can perform state-cover testing for nondeterministic terminating concurrent programs with an infinite number of synchronization sequences. Dynamic effective testing does not require static analysis of the target concurrent program or the assistance of a model checker, and thus is loosely coupled to the syntax of the target concurrent program. It only needs to analyze sequences of synchronization events produced by the execution of the concurrent programs for race detection and state-traversal control. Therefore, the method is easy to port to different programming languages. In addition, only reiterated states discovered in a single SYN-sequence need to be stored. The implementation and experimental results obtained with real code demonstrate that source-code-level dynamic testing can be systematically performed on nondeterministic concurrent programs with infinite synchronization sequences.
KW - Concurrent program
KW - Concurrent testing
KW - Nondeterministic behavior
KW - Reachability testing
KW - SYN-sequence
UR - http://www.scopus.com/inward/record.url?scp=84878857287&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84878857287&partnerID=8YFLogxK
U2 - 10.1016/j.scico.2012.06.005
DO - 10.1016/j.scico.2012.06.005
M3 - Article
AN - SCOPUS:84878857287
SN - 0167-6423
VL - 78
SP - 1294
EP - 1323
JO - Science of Computer Programming
JF - Science of Computer Programming
IS - 9
ER -