Testing, debugging, and analysis of concurrent software
Richard H. Carver · 1989
An execution of a concurrent program P non-deterministically exercises a sequence of synchronization events, referred to as a feasible synchronization sequence. A synchronization error in P refers to the existence of a feasible synchronization sequence of P that is not allowed according to P's specification. One approach to detecting synchronization errors in P is to execute P with a number of test cases. The non-deterministic execution behavior of P creates the following problems during the testing and debugging phases of P: (1) When testing P with input X, a single execution is insufficient to determine the correctness of P with input X, and (2) when debugging an erroneous execution of P with input X, there is no guarantee that this execution will be repeated by executing P with input X. In the first part of this thesis, we describe how to solve these testing and debugging problems by forcing a deterministic execution of a concurrent program according to a given synchronization sequence. First, we present a language-based approach to deterministic execution testing and debugging. Then, to demonstrate this approach, we show how to debug a concurrent Ada program by using deterministic execution. Deterministic execution is accomplished by using program transformation. It is shown that the transformation of concurrent Ada programs for deterministic execution debugging can be easily automated. Another approach to detecting synchronization errors in P is to analyze, but not execute, P. Existing analysis methods for detecting synchronization errors in P derive the set of syntactically possible synchronization sequences of P. The effectiveness of syntax-based synchronization analysis is limited due to the fact that P's semantic information is ignored. In the second part of this thesis, we introduce a new analysis method for detecting synchronization errors. This method is to derive feasibility on the synchronization sequences of a concurrent program (or program module) P according to P's syntactic and semantic information. Feasibility constraints for P, can be compared with the specification of P for error detection or used to improve the results of syntax-based synchronization analysis of P.