slicing concurrent programs
Slicing is a well-known program analysis technique for analyzing sequential programs and found useful in debugging, testing and reverse engineering. This paper extends the notion of slicing to concurrent programs with shared memory, interleaving semantics and mutual exclusion. Interference among concurrent threads or processes complicates the computation of slices of concurrent programs. Further, unlike slicing of sequential programs, a slicing algorithm for concurrent programs needs to differentiate between loop-independent data dependence and certain loop-carried data dependences. We show why previous methods do not give precise solutions in the presence of nested threads and loops and describe our solution that correctly and efficiently computes precise slices. Though the complexity of this algorithm is exponential on the number of threads, a number of optimizations are suggested. Using these optimizations, we are able to get near linear behavior for many practical concurrent programs.
slice concurrent program concurrency program program analysis debugging test reverse engineer paper shared memory semantic mutual exclusion interference thread process computation algorithm dependencies data dependence data method precise presence complexity optimality behavior practical static program slicing