Slicing Concurrent Programs Based on Program Reachability Graphs with Partial-Order Reduction
Qi Xiao · Chinese Journal of Computers · 2014
Concurrent program slicing is an important technique to analyze concurrent programs. Based on a program reachability graph,we can construct a novel dependence graph,in which each node is a 2-tuple of program state and statement and the dependence relation is transitive.A precise slice is thus be obtained by traversing it as the intransitivity problem is solved.However,in aprogram reachability graph,concurrent activities are simulated by interleaving,which makes reachabilty analysis costly.Partial-order techniques are effective for reducing the state space of a concurrent system.A reduced state space includes all representative executions of a concurrent program.To improve the slicing efficiency,we extended partial-order techniques to reduce program reachability graphs.Under the frame of partial-order reduction theory,it is proved that the computation of slicing by traversing the dependence graph constructed based on a reduced program reachability graph is equivalent to that based on completely explored one.Experiment results showed that the efficiency of slicing based on a reduced program reachability graph was highly improved without sacrificing precision.Compared with the other existing high-precisionslicing algorithms,a more precise slice is computed with the slicing algorithm based on a reduced program reachability graph.The performance is also improved in most cases.