基于偏序约简程序可达图的并发程序切片方法  

Slicing Concurrent Programs Based on Program Reachability Graphs with Partial-Order Reduction

作　　者：戚晓芳[1,2] 徐晓晶 江振亮 汪鹏[1] 

机构地区：[1]东南大学计算机科学与工程学院,南京211189 [2]东南大学计算机网络和信息集成教育部重点实验室,南京211189 [3]IBM中国系统与科技实验室,上海201203

出　　处：《计算机学报》2014年第3期568-579,共12页Chinese Journal of Computers

基　　金：国家自然科学基金(60873049);国家自然科学青年基金(61003156)资助~~

摘　　要：并发程序切片是一种重要的并发程序分析手段.基于程序可达图可构造以程序状态和语句二元组为节点的、依赖关系具有可传递性的并发程序依赖图,解决依赖关系的不可传递性问题,提高切片精度.程序可达图通过交织执行模拟并发活动,分析代价较高.偏序约简是一种十分有效的并发系统状态空间约简技术,约简的并发系统状态空间包含所有的并发程序执行代表.为提高效率,该文将偏序约简技术扩展到程序可达图的约简中,在偏序约简理论的基础上,证明了基于未约简和约简的并发程序可达图构造的并发程序依赖图在进行切片计算时是等价的.实验结果表明,采用偏序约简技术使基于程序可达图的并发程序切片方法在保证切片精度不受损失的前提下显著提高切片效率.与其它高精度切片方法相比,基于约简程序可达图的切片方法的精度更高,在大多数情况下,切片效率也有一定提高.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 pre- cise slice is thus be obtained by traversing it as the intransitivity problem is solved. However, in a program 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 pro- gram 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 pro- gram 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-precision slicing algorithms, a more precise slice is computed with the slicing algorithm based on a reduced program teachability graph. The performance is also improved in most cases.

关 键 词：并发程序 程序切片 依赖性分析 可达性分析 偏序约简 程序分析 软件测试中图法 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]