Minimizing test suites with unfoldings of multithreaded programs

Olli Saarikivi, Hernan Ponce de Leon, Kari Kähkönen, Keijo Heljanko, Javier Esparza

Research output: Contribution to journalArticleScientificpeer-review

5 Citations (Scopus)

Abstract

This article focuses on computing minimal test suites for multithreaded programs. Based on previous work on test case generation for multithreaded programs using unfoldings, this article shows how this unfolding can be used to generateminimal test suites covering all local states of the program. Generating suchminimal test suites is shown to be NP-complete in the size of the unfolding. We propose an SMT encoding for this problem and two methods based on heuristics which only approximate the solution, but scale better in practice. Finally, we apply our methods to compute the minimal test suites for several benchmarks.
Original languageEnglish
Article number45
Pages (from-to)1-24
JournalACM Transactions on Embedded Computing Systems
Volume16
Issue number2
DOIs
Publication statusPublished - 1 Feb 2017
MoE publication typeA1 Journal article-refereed

Keywords

  • Event structure
  • SMT-encoding
  • Testing
  • Unfolding

Fingerprint

Dive into the research topics of 'Minimizing test suites with unfoldings of multithreaded programs'. Together they form a unique fingerprint.

Cite this