TY - GEN
T1 - Unfolding Based Minimal Test Suites for Testing Multithreaded Programs
AU - León, Hernán Ponce De
AU - Saarikivi, Olli
AU - Kahkonen, Kari
AU - Heljanko, Keijo
AU - Esparza, Javier
N1 - Publisher Copyright:
© 2015 IEEE.
PY - 2015/12/10
Y1 - 2015/12/10
N2 - This paper focuses on the problem of computing the minimal test suite for a terminating multithreaded program that covers all its executable statements. We have in previous work shown how to use unfoldings to capture the true concurrency semantics of multithreaded programs and to generate test cases for it. In this paper we rely on this earlier work and show how the unfolding can be used to generate the minimal test suite that covers all the executable statements of the program. The problem of generating such a minimal test suite is shown to be NP-complete in the size of the unfolding, and as a side result, covering executable transitions of any terminating safe Petri net is also NP-complete in the size of its unfolding. We propose SMT-encodings to these problems and give initial results on applying this encoding to compute the minimal test suite for several benchmarks.
AB - This paper focuses on the problem of computing the minimal test suite for a terminating multithreaded program that covers all its executable statements. We have in previous work shown how to use unfoldings to capture the true concurrency semantics of multithreaded programs and to generate test cases for it. In this paper we rely on this earlier work and show how the unfolding can be used to generate the minimal test suite that covers all the executable statements of the program. The problem of generating such a minimal test suite is shown to be NP-complete in the size of the unfolding, and as a side result, covering executable transitions of any terminating safe Petri net is also NP-complete in the size of its unfolding. We propose SMT-encodings to these problems and give initial results on applying this encoding to compute the minimal test suite for several benchmarks.
KW - Multithreaded programs
KW - SMT
KW - Testing
KW - unfoldings
UR - https://www.scopus.com/pages/publications/84959888790
U2 - 10.1109/ACSD.2015.12
DO - 10.1109/ACSD.2015.12
M3 - Conference contribution
AN - SCOPUS:84959888790
T3 - Proceedings - International Conference on Application of Concurrency to System Design, ACSD
SP - 40
EP - 49
BT - Proceedings - 2015 15th International Conference on Application of Concurrency to System Design, ACSD 2015
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 15th International Conference on Application of Concurrency to System Design, ACSD 2015
Y2 - 21 June 2015 through 26 June 2015
ER -