PhD Proposal: A Framework for Testing Concurrent Programs

A Framework for Testing Concurrent Programs
(Presentation, PowerPoint,PDF)

This study proposes a new framework that can effectively apply unit
testing to concurrent programs, which are difficult to develop and
debug. Test-driven development, a practice enabling developers to
detect bugs early by incorporating unit testing into the development
process, has become wide-spread, but it has only been effective for
programs with a single thread of control. The order of operations in
different threads is essentially non-deterministic, making it more
complicated to reason about program properties in concurrent programs
than in single-threaded programs. Because hardware and operating
systems influence the order in which operations in different threads
are executed, debugging is problematic since a problem often cannot be
reproduced on other machines. Multi-core processors, which have
replaced older single-core designs, have exacerbated these problems
because they demand the use of concurrency if programs are to benefit
from new processors.

The existing tools for unit testing programs are either flawed or too
costly. JUnit, for instance, assumes that programs are single-threaded
and therefore does not work for concurrent programs; ConTest and
rstest predate the revised Java memory model and make incorrect
assumptions about the operations that affect synchronization.
Approaches such as model checking or comprehensive schedule-based
execution are too costly to be used frequently. All of these problems
prevent software developers from adopting the current tools on a large
scale.

The proposed framework (i) improves JUnit to recognize errors in all
threads, a necessary development without which all other improvements
are futile, (ii) places some restrictions on the programs to
facilitate automatic testing, (iii) provides tools that reduce
programmer mistakes, and (iv) re-runs the unit tests with randomized
schedules to simulate the execution under different conditions and on
different machines, increasing the probability that errors are
detected.

The improvements and restrictions, shown not to seriously impede
programmers, reliably detect problems that the original JUnit missed.
The execution with randomized schedules reveals problems that rarely
occur under normal conditions.

With an effective testing tool for concurrent programs, developers can
test programs more reliably and decrease the number of errors in spite
of the proliferation of concurrency demanded by modern processors.