基于逆向程序流和函数依赖集的程序切片算法

Program Slicing Algorithm Based on Reverse Program Flow and Function Dependency Set

程序切片技术大多是根据程序依赖图(PDG)和系统依赖图(SDG)的图可达性算法来优化得到感兴趣的程序集合,但是构造PDG和SDG需要很大的空间开销。本文提出一种基于逆向程序流和函数依赖集的切片算法,从兴趣点开始扫描逆向程序流来计算程序切片,只计算与切片相关的数据依赖,并且考虑函数调用时切片的计算,提高计算切片的效率。通过实例表明该算法减少了计算程序切片的复杂度,具有一定的可行性和实用性。

Program slicing technique is mostly based on the accessibility algorithm of program dependence graph （PDG） and sys- tem dependence graph （SDG） to get a set of interested programs which are optimized, but to construct PDG and SDG need a lot of time and space. So this paper presents a slicing algorithm based on reverse program flow and function dependency set, it scans the reverse program flow to calculate program slicing of the interested points which only related to data dependence of program sli- cing. The algorithm mainly considers the calculation of function call, improves the computational efficiency. It also founds that through instances the algorithm reduces the complexity of program slicing calculating, and it is feasible and practical.