Representing a concurrent program as a set of simulating, sequential programs, called serializations, provides (1) a formal foundation for a theory of concurrent program testing. (2) a natural basis for applying the methods and theory of testing sequential programs to concurrent programs, and (3) a system for reproducibly testing concurrent programs. This project will investigate methods of incremental generation of serializations, design a regular language for specifying sets of serializations, and develop an experimental testing environment that incorporates these features. This environment will be used to study a hierarchy of test data selection criteria for concurrent programs, in which the degree of communication among a program's tasks is used to define increasingly more stringent criteria. The criteria use information about how shared objects are accessed in the tasks to establish the degree to which the possible task interactions should be tested. The study of these criteria will include an evaluation of the complexity of using them, and experiments on their effectiveness at exposing timing dependent errors in concurrent software.
