Precise slicing of interprocedural concurrent programs
Precise slicing of interprocedural concurrent programs
复制标题
DOI：
10.1007/s11704-017-6189-3
复制
发表时间：
2017-12
影响因子：
4.2
通讯作者：
Xiaofang Qi;Zhenliang Jiang
中科院分区：
文献类型：
--
作者：
Xiaofang Qi;Zhenliang Jiang
程序切片是分析并发程序的一种有效技术。然而，当传统的基于闭包的顺序程序切片算法应用于并发过程间程序时，由于干扰依赖的不传递性，切片通常是不精确的。当一个语句使用了在并发执行的另一个语句中定义的变量时，就会产生干扰依赖。在这项研究中，我们提出了一种基于程序可达图的全局依赖分析方法，并构造了一种新的依赖图标记语句依赖图（MSDG），其中每个顶点是程序状态和语句的二元组。与传统的程序依赖图中的顶点是语句不同，MSDG中的依赖关系是可传递的。当遍历MSDG时，将获得精确的切片。为了提高切片效率而不损失精度，我们的切片算法采用了混合策略。基于程序可达图的切片算法将包含线程间交互语句的过程内联切片，同时允许其他过程作为顺序程序切片。我们已经实现了我们的算法和其他三个代表切片算法，并进行了并发Java程序的实证研究。实验结果表明，该算法比其他算法计算出更精确的切片。使用偏序约简技术，这是有效的减少程序可达图的大小，而不损失精度，我们的算法进行了优化，从而提高其性能在一定程度上。
Program slicing is an effective technique for analyzing concurrent programs. However, when a conventional closure-based slicing algorithmfor sequential programs is applied to a concurrent interprocedural program, the slice is usually imprecise owing to the intransitivity of interference dependence. Interference dependence arises when a statement 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 calledmarking-statement dependence graph (MSDG), in which each vertex is a 2-tuple of program state and statement. In contrast to the conventional program dependence graph where the vertex is a statement, the dependence relation in MSDG is transitive. When traversing MSDG, a precise slice will be obtained. To enhance the slicing efficiency without loss of precision, our slicing algorithm adopts a hybrid strategy. The procedures containing 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 sequential programs. We have implemented our algorithm and three other representative slicing algorithms, and conducted an empirical study on concurrent Java programs. The experimental results show that our algorithm computes more precise slices than the other algorithms. Using partial-order reduction techniques, which are effective for reducing the size of a program reachability graph without loss of precision, our algorithm is optimized, thereby improving its performance to some extent.