Effective generation of test sequences for structural testing of concurrent programs

One common approach to test sequence generation for structurally testing concurrent programs involves constructing a reachability graph (RG) and selecting a set of paths from the graph to satisfy some coverage criterion. It is often suggested that test sequence generation methods for testing sequential programs based on a control flow graph (CFG) can also be used to select paths from a RG for testing concurrent programs. However, there is a major difference between these two, as the former suffers from a feasibility problem (i.e., some paths in a CFG may not be feasible at run-time) and the latter does not. As a result, even though test sequence generation methods for sequential programs can be applied to concurrent programs, they may not be efficient. Moreover, in order to reduce testing effort and costs, it is important to reduce the number of test sequences being generated. Stated differently, we need methods which can generate efficient test sequences to increase the coverage in an effective way. We propose four different methods - two based on hot spot prioritization and two based on topological sort -to effectively generate a small set of test sequences that cover all the nodes in a RG. The same methods are also applied to the corresponding dual graph for generating test sequences to cover all the edges. A case study was conducted to demonstrate the use of our methods.