Research On Testing Theories And Technologies Of Concurrent Programs

During the whole lifecycle of software development, software testing is one of the key steps to ensure the high quality of software. With the development of multi-core CPUs and parallel distributed systems, the design methodologies of concurrent programs are deep concerned and discussed. Taking a view of current software industry, concurrent programs are used everywhere, from operating systems to Internet. Because of the inherent nondeterminism of such programs, testing is notoriously hard. On one hand, some traditional testing strategies and methods can be adjusted or improved for testing the concurrent programs. On the other hand, exploiting a new system of testing theory and technology for these new specialties is essentially important.Efficient test cases come from the accurate analysis of the program. The Analysis of concurrent programs can be classified into two classes, static analysis and dynamic analysis. The former analyses the source codes and the latter analyses the runtime information. Concurrent programs have nondeterministic behaviors, some testing methods control them, and some not. According to this, the testing methods of concurrent programs can be classified into deterministic testing and non-deterministic testing. Test cases of non-deterministic testing, similar to those of traditional sequential programs, are composed of test inputs and outputs. Besides these two parts, test cases of deterministic testing usually include test sequences, which are used to control the behaviors of concurrent programs.One approach to testing concurrent programs, called reachability testing, generates test sequences automatically and on-the-fly, without constructing any static models. If the test inputs are given, this method guarantees that every partially ordered test sequence will be exercised exactly once without having to save any sequences that have already been exercised. Based on analyzing the reachability testing procedure, it can be found that the root cause of the additional runtime control for the deterministic execution is the inaccurate computation of the race table. The reachability testing method is improved by redefining control structure and race difference. The new method can execute all the test sequences exactly once without any runtime control, so the efficiency of the method is enhanced.Structural testing methods of concurrent programs generally suffer from their scalability due to the large test set size. In the structural testing of traditional sequential programs, exercising all feasible paths is usually not practical, but the branch coverage criterion solves the problem pretty well. In light of the above idea, based on analyzing the cause of the large test set size, a testing criterion for concurrent programs, called ASRSP, is proposed, and a novel algorithm to generate test sequences, called ASRSP-RT, is further proposed. The evaluation shows that compared to traditional methods, the proposed ASRSP-RT can significantly reduce the set of the test sequences as a result of satisfying the ASRSP criterion.Concolic testing is another general approach to testing concurrent programs. It combines concrete execution and symbolic execution to generate test inputs, which is not concerned by reachability testing. The happened-before relation is used to determine the order of the concurrent events in distributed systems. The relation of the test set size and happened-before relation are carefully studied. The weak happened-before relation is redefined, and a test sequence selection algorithm, called WHB-TS, is proposed. The weak happened-before relation has the ability to find out all the outputs of the given concurrent program, so it is sufficient for testing to a degree. The partition of the original test set with the weak happened-before relation can produce fewer equivalence classes than traditional ones. The experiment shows that, the proposed WHB-TS can significantly reduce the test set that jCUTE generated.