Unfolding Based Minimal Test Suites for Testing Multithreaded Programs

Hernán Ponce De León, Olli Saarikivi, Kari Kahkonen, Keijo Heljanko, Javier Esparza

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

7 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publicationProceedings - 2015 15th International Conference on Application of Concurrency to System Design, ACSD 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages40-49
Number of pages10
ISBN (Electronic)9781467378826
DOIs
StatePublished - 10 Dec 2015
Event15th International Conference on Application of Concurrency to System Design, ACSD 2015 - Brussels, Belgium
Duration: 21 Jun 201526 Jun 2015

Publication series

NameProceedings - International Conference on Application of Concurrency to System Design, ACSD
Volume2015-December
ISSN (Print)1550-4808

Conference

Conference15th International Conference on Application of Concurrency to System Design, ACSD 2015
Country/TerritoryBelgium
CityBrussels
Period21/06/1526/06/15

Keywords

  • Multithreaded programs
  • SMT
  • Testing
  • unfoldings

Fingerprint

Dive into the research topics of 'Unfolding Based Minimal Test Suites for Testing Multithreaded Programs'. Together they form a unique fingerprint.

Cite this