Using Unfoldings in Automated Testing of Multithreaded Programs
In multithreaded programs both environment input data and the non-deterministic inter-leavings of concurrent events can affect the behavior of the program. One approach to systematically explore the non-determinism caused by input data is dynamic symbolic execution. For testing multithreaded programs the authors present a new approach that combines dynamic symbolic execution with unfoldings, a method originally developed for petri nets but also applied to many other models of concurrency. They provide an experimental comparison of their new approach with existing algorithms combining dynamic symbolic execution and partial-order reductions and show that the new algorithm can explore the reachable control states of each thread with a significantly smaller number of test runs.