Precise slicing of interprocedural concurrent programs

Program slicing is an effective technique for an- alyzing concurrent programs. However, when a conventional closure-based slicing algorithm for sequential programs is ap- plied to a concurrent interprocedural program, the slice is usually imprecise owing to the intransitivity of interference dependence. Interference dependence arises when a state- ment uses a variable defined in another statement executed concurrently. In this study, we propose a global dependence analysis approach based on a program reachability graph, and construct a novel dependence graph called marking-statement dependence graph （MSDG）, in which each vertex is a 2-tuple of program state and statement. In contrast to the conven- tional program dependence graph where the vertex is a state- ment, the dependence relation in MSDG is transitive. When traversing MSDG, a precise slice will be obtained. To en- hance the slicing efficiency without loss of precision, our slic- ing algorithm adopts a hybrid strategy. The procedures con- taining interaction statements between threads are inlined and sliced by the slicing algorithm based on program reachability graphs while allowing other procedures to be sliced as se- quential programs. We have implemented our algorithm and three other representative slicing algorithms, and conducted an empirical study on concurrent Java programs. The exper- imental results show that our algorithm computes more pre- cise slices than the other algorithms. Using partial-order re- duction techniques, which are effective for reducing the size of a program reachability graph without loss of precision, ouralgorithm is optimized, thereby improving its performance to some extent.

Variable strength combinatorial testing of concurrent programs

Reachability testing is an important approach to testing concurrent programs. It generates and exercises syn- chronization sequences automatically and on-the-fly without saving any test history. Existing reach, ability testing can be classified into exhaustive and t-way testing. Exhaustive testing is impractical in many cases whilie t-way testing may decrease the capability of fault detection in some cases. In this paper, we present a variable strengda reachability testing strategy, which adopts the dynamic framework of reachability testing and uses a variable strength combinatorial strategy. Different parameter groups are provided with different covering strength. Variable strength testing covers no t-way combinations but the necessary combinations of parameters having mutual interactions in a concurrent program. It is more reasonable than t-way testing because uniform interactions between parameters do not often exist in concurrent systems. We propose a merging algorithm that implements the variable strength combinatorial testing strategy and conduct our experiment on several concurrent programs. The experimental results indicate that our variable strength reachability testing reaches a good tradeoff between the effectiveness and efficiency. It can keep the same capability of fault detection as exhaustive reachability testing while substantially reducing the number of synchronization sequences and decreasing the execution time in most cases.