Helsinki Algorithms Seminar: "Minimizing Test Suites with Unfoldings of Multithreaded Programs" Keijo Heljanko

Weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design

Keijo Heljanko

Minimizing Test Suites with Unfoldings of Multithreaded Programs

Abstract:

We show how to compute minimal test suites for multithreaded programs. Based on previous work on test case generation for multithreaded programs using unfoldings, this work shows how this unfolding can be used to generate minimal test suites covering all local states of the program. Generating such minimal 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 multithreaded benchmark programs.

This is joint work with Olli Saarikivi, Hernan Ponce-de-Leon, Kari Kähkönen, and Javier Esparza.

**

Helsinki Algorithms Seminar is a weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design, broadly interpreted to cover both theoretical ideas and algorithm engineering on concrete computing platforms. In most cases we have a presentation prepared for each meeting to communicate an idea, a recent result, work-in-progress, or demo, but this should not be at the expense of discussion and simply having fun with algorithms.

Our affiliations are with Aalto University and the University of Helsinki, and accordingly our activities alternate between the Otaniemi Campus of Aalto University and the Kumpula Campus of University of Helsinki, catalyzed by the Helsinki Institute for Information Technology HIIT, under the Algorithmic Data Analysis (ADA) programme.

Welcome!