一种新的过程间静态切片快速算法

苏小红，龚丹丹，王甜甜，马培军

(哈尔滨工业大学计算机科学与技术学院，150001哈尔滨)

程序切片技术是一种重要的程序分析和理解技术，广泛应用于程序调试、测试及软件维护中［1-2］.其原理和方法最早出现在文献［3］中，文献［3］根据数据流方程的迭代解对程序切片进行了定义，并提出了基于控制流图(control flow graph，CFG)的计算过程内程序切片的算法，但此方法所消耗的时间和空间均比较多，计算所得的程序切片准确性也不是很好.文献［4］引入了基于程序依赖图(program dependence graph，PDG)的图形可达性算法，用于计算过程内切片，但此算法只能计算一个过程内的切片问题，含有多个过程的程序切片计算问题并未得到解决.文献［5］通过把PDG扩展为系统依赖图(system dependence graph，SDG)，以计算过程间切片，根据系统依赖图，将函数间的切片问题转化为图的可达性问题［6］，从而解决了包含多个过程程序的切片计算问题.

目前，计算程序静态切片主要使用的方法是基于依赖图的遍历算法［7］.系统依赖图能够充分表示程序的数据依赖、控制依赖信息以及函数调用信息，但是SDG数据流分析的复杂度较高，而且生成系统依赖图的过程中，需要计算与切片无关的数据依赖，这些不必要的计算造成了时间和空间资源的浪费，并严重影响了切片计算的效率.类似地，传统的动态切片算法使用动态依赖图，复杂性也很高，针对该方法，文献［8］提出利用D/U表达式计算动态切片的方法，不需要使用动态依赖图，可以同时计算程序的控制依赖和数据依赖，空间开销较小.但传统的利用D/U表达式计算动态切片的方法，只考虑了直接控制依赖关系没有考虑多层嵌套的情况，而且由于未考虑函数调用的情况，只能用于过程内动态切片的计算中.

本文提出的基于idUCf五元结构的过程间切片算法，既保留了程序的数据依赖、控制依赖以及函数调用信息，又充分考虑了多层嵌套情况，而且不需要使用SDG，无需计算与切片无关的数据依赖、控制依赖以及不相关函数调用信息.

1 idUCf五元结构及相关定义

本文在分析静态切片与切片准则的基础上，给出了复合语句控制结构信息表以及idUCf五元结构的定义，作为本文切片算法的研究基础.

定义1(静态切片［9］) 一个程序P的静态切片是由P中的一些语句集合，它包含了所有可能影响兴趣变量的语句，考虑了程序中所有可能的执行路径.根据切片方向的不同，可分为前向切片和后向切片.前向切片是指所有受兴趣点变量的值影响的语句的集合;后向切片是指程序中所有能够影响兴趣点变量的值的语句的集合.本文所描述的是后向切片.

定义2(静态切片准则［10］) 静态切片准则是一个二元组C=(n，V)，其中:V为程序P中变量集合的一个子集;n为程序P中的某个兴趣点(对应于P中的一条语句).

定义3(复合语句控制结构信息表(CNT))复合语句控制结构信息表是记录程序P中的所有复合语句(选择、循环)的开始、结束位置等关键信息的集合，它能够精简的记录程序的所有控制依赖关系，以下简称 CNT(compound node table).其结构定义如图1所示.

图1中，key为词法分析时所对应的TOKEN，name为该TOKEN对应的源程序中的单词.在本文所使用的编译器中，经词法分析后将for语句对应的TOKEN记为“CN-FOR”，则key的值为“CNFOR”，name记录了源程序中的单词，则name的值为“for”.对于多分支的选择结构，不仅应该记录选择结构的结束位置(endID)和结束行(endline)，还应该记录各个分支内部的结束位置(ifendID)和结束行(ifendline)，以便进行精确的路径分析.例如图2，多分支选择结构if(第13行)，其内部分支结束位置ifendline=16，总分支结束位置endline=20;对于33行的else分支，其内部分支结束位置即为总分支的结束位置，即endline=ifendline=20.循环结构无需考虑多分支情况，因此for的endline与ifendline的值相同.词法分析过程中记录了每个TOKEN的具体位置，由于图2为实例代码片段，所包含的信息不完整，因此很难表示复合语句开始TOKEN位置、结束TOKEN位置以及内部结束TOKEN位置.因此，并未记录图2中的beginID、endID以及ifendID，在图中用“—”表示.

图1 复合语句控制结构信息表结构

图2 复合语句控制结构信息表实例

定义4(idUCf五元结构)idUCf五元结构＜i，d，U，C，f＞是表示程序中变量定义、使用、控制依赖关系、函数调用关系的表达式，其中:i为语句的行号，d为语句i定义的变量;U为语句i使用变量的集合，C为语句i复合关系集合，存储该语句所在的复合语句所对应的CNT的id号，f为语句i调用函数信息.这样的表达式称为idUCf五元结构.本文主要讨论赋值语句结点(AssignNode)与函数调用结点(FunctionNode)的idUCf五元结构，图3中列出了图2(D:aa.c)中第15行AssignNode和第19行FunctionNode的idUCf五元结构，其中Ø表示空集.

图3 idUCf五元结构实例

2 idUCf五元结构的静态切片模型

本文建立了idUCf五元结构的过程间静态切片模型(如图4所示)，主要包括以下3个步骤:

1)通过词法分析生成 TOKEN序列，在TOKEN序列基础上进行代码标准化［11］，最终生成标准化TOKEN序列.

2)在标准化TOKEN序列基础上，分别生成函数列表、复合语句控制结构信息表 CNT和idUCF五元结构.

3)应用基于idUCf五元结构的过程间静态切片算法，得到过程间静态切片.

图4 程序切片算法模型

3 切片算法

过程间静态切片，以切片准则C=(n，V)，根据程序的idUCf五元结构＜i，d，U，C，f＞，从源程序P中抽取结点n前，影响或间接影响变量v(v∈V)的所有语句和函数.赋值语句以及函数调用语句直接影响变量的取值，本文将程序语句的操作分为赋值操作与函数调用操作，分别对应idUCf五元结构中的 AssignNode与 FunctionNode.当计算任意变量v的后向切片时，应逆序查找idUCf五元结构，直到找到AssignNode或FunctionNode，使其满足v=AssignNode或FunctionNode的定义变量d.因此，计算变量v的后向切片转化为计算相对应的赋值语句切片AssignSlice(d)或函数调用语句切片 FunctionSlice(d)，其中d为AssignNode或FunctionNode的定义变量为

式中“‖”表示“或者”.

1)当d为AssignNode的定义变量时，切片中应加入该赋值语句，并检查其复合关系集合＜C＞及使用变量集合 ＜U＞，首先，依次计算复合关系子切片(ControlSlice(c))，以保证多层嵌套程序的完整性.当使用变量集合 ＜U＞不为Ø时，代表定义的变量d无法直接获得初始值，需要通过其使用的变量进行计算.应依次递归计算其使用变量的子切片slice(u)(u∈U).赋值语句结点切片AssignSlice(d)可确定为

式中“+”为所求切片的和.例如式中计算节点AssignSlice(d)由3部分的和组成，分别为该赋值节点AssignNode(d)，使用变量的子切片Slice(u)(u∈U)以及复合关系子切片(ControlSlice(c)).

当使用变量集合 ＜U＞为Ø时，代表定义变量被赋予常数，即找到了变量的初始值，此时，上式可变为

当计算复合关系子切片ControlSlice(c)时，根据idUCf五元结构中的c(c∈C;c为该复合语句所对应的CNT的id号)查找CNT，找到所对应的复合语句的具体信息.

①如果该复合语句为选择结构，则依次计算该选择结构的判断变量j的后向切片，以计算判断变量的初始值，即

②如果该复合语句为选择结构，为了计算判断变量以及循环累加变量的初始值，首先应依次计算判断变量j和累加变量a的后向切片Slice(j)和Slice(a)，为了保证静态切片的完整性，还应考虑j和a的值在循环体内是否改变，基于上述观点，在循环体内(beginline-endline)，顺序查找idUCf五元结构，当j或a与 AssignNode或FunctionNode的定义变量d相同时，说明在循环体内，j或a发生了改变，则应计算AssignNode或FunctionNode的定义变量d的后向切片.则有

2)当d为FunctionNode的定义变量时，说明此语句调用了函数，且d被赋予所调用函数的return返回值.切片中不仅应加入该赋值语句、复合关系子切片(ControlSlice)，而且要在其调用函数中求得返回值切片(Slice(r))，即

式中:r为所调用函数的return返回值;m为被调函数的形参个数.在计算Slice(r)的过程中，还应记录每个形参的使用标志para-flag.如果调用函数的第i个形参(para-i)为欲求Slice(r)的切片变量，并且AssignNode(para-i)的使用变量始终不为Ø，则para-flag-i的值为1，否则为0.当para-flag-i的值为1时，说明被调函数中使用了主调函数的形参值，因此，应计算形参(para-i)所对应的实参切片Slice(argue-i).

当所求切片变量d∈FunctionNode的使用集＜U＞，说明d为调用函数的参数之一.

①当调用参数传递类型为传值调用时，被调函数中对形参的改变不影响实参的值，所以无需计算实参(para)所对应的形参切片Slice(argue)，则有

②当所求切片变量d∈FunctionNode的使用集＜U＞，并且调用参数传递类型为传地址调用时，对形参的改变实际上是对实参的改变，因此，不仅要在调用函数中求得d所对应的形参切片Slice(para-d)，同时还应记录形参的使用标志para-flag，当第i个形参的使用标志para-flag-i的取值为1时，说明被调函数的切片计算中需要使用第i个形参所对应的主调函数实参的取值，因此，应计算第i个实参的切片Slice(argue-i).

本文在定义了上述公式的基础上，给出了基于idUCf五元结构的过程间静态切片算法，构造标准C=(n，V)的程序切片Slice(V)算法如图5所示.主算法Slice(V)，根据切片准则C=(n，V)，对第n行的每个变量d(d∈V)，首先根据复合语句控制信息，判断其是否处于复合语句结构中，并调用ControlSlice(c)算法依次处理复合语句结构(解决了多层嵌套结构);然后，调用Slicing(d)算法，后向查找变量d的静态切片.

图5 程序切片主算法Slice(V)

复合关系子切片ControlSlice(c)算法如图6所示.算法ControlSlice(c)的功能是计算复合语句结构(选择、循环结构)的程序切片，同时保持复合语句结构切片的完整性.对于复合语句结构中的变量x，首先调用Slicing(x)算法查找变量x的切片，目的是为了找到x的初始值.然后在beginline-endline中查找idUCf的五元结构，如果x为第k个idUCf的定义变量，说明x在此复合结构中被重新赋值，则应依次处理第k个idUCf的使用变量集合U.

后向查找切片变量Slicing(d)算法如图7所示.算法Slicing(d)的功能是根据idUCf五元结构计算变量d的后向静态切片.对于结点d，后向查找idUCf五元结构.

①如果d与第i个idUCf的定义变量相等，且idUCf类型为 AssignNode，则首先调用ControlSlice(c)函数，依次处理复合语句结构的程序切片，然后依次递归调用Slicing(d)函数处理变量使用集U，直到U为Ø.

②如果d与第i个idUCf的定义变量相等，且idUCf类型为FunctionNode，则调用Slicing(r)，在其调用函数中求得返回值切片并返回各形参标志para_flag，根据para_flag的取值判断是否计算形参切片.

图6 复合关系子切片ControlSlice(c)算法

③如果d与第i个idUCf的使用变量集合中元素相等，且idUCf类型为FunctionNode，根据实参-形参对应关系，调用Slicing(para_d)函数，在调用函数中求得形参切片并返回各形参标志，根据para_flag的取值判断是否计算形参切片.

4 实验结果和分析

根据本文算法，以切片准则(24，aboveAver)，计算程序图8中的实例程序的静态切片.本文切片算法只计算切片点所在函数以及与切片点计算相关的调用函数时才计算idUCf五元结构和CNT，切片计算结果为:切片 slice(24，aboveAver)={24，4，20，40，48，45，43，42，41，19，2，10，9，8}，切片集合中元素的顺序为其被加入的顺序.为此，本文使用行号来代表程序切片语句.因为行号与语句具有一一对应关系.图8中的阴影部分为本切片算法所分析的语句，由此可以看出，本文算法只对main函数以及GetAboveAver函数进行分析，只计算main函数以及GetAboveAver函数的idUCf五元结构和CNT，无需计算与切片计算无关的GetDetail函数.

图7 后向查找切片变量Slicing(d)

表1～4列出了main函数和GetAboveAver函数的CNT以及idUCf五元结构.

表1 main函数的idUCf五元结构表

表2 main函数的CNT

图8 实例程序

表3 GetAboveAver函数的idUCf五元结构

表4 GetAboveAver函数的CNT

图9为本文算法所得到的静态切片程序，本文算法充分考虑了程序的控制依赖、数据依赖以及函数调用信息.文献［8］只考虑了直接控制依赖关系，而本文将直接控制依赖关系扩展为复合关系集合 ＜C＞，充分考虑了多层嵌套情况，所得切片精度更高;而且，文献［8］中只计算了过程内动态切片，而本文算法可以计算过程间静态切片.

图9 program1的切片程序

传统的基于PDG、SDG的静态程序切片算法复杂度很高［12-13］.例如对于程序 program1(见图9)，传统方法生成的 SDG共有66个结点(本程序为37行:除去“{”和“}”)，66条控制依赖边，79条数据依赖边，2条函数调用边.采用本文方法建立的idUCF五元结构的元素总个数为10个，CNT中的元素总个数仅为4个，大大低于SDG中的节点个数.在计算程序切片过程中，传统的基于SDG的方法需要根据控制依赖边和数据依赖边遍历所有节点，而本文算法只需计算与切片点相关的控制依赖、数据依赖以及相关的函数.在main函数中，控制依赖信息只分析了与切片点相关的第10行的for循环，无需分析第13行的if语句.数据依赖信息只分析了与aboveAver相关的 aver、score、sum的数据依赖，不需对failnum的数据依赖进行分析.函数调用方面，函数GetDetail与切片点无关，也不用分析.另外，只计算与切片点相关函数的 idUCf五元结构和CNT，在本实例中，只计算了 main函数和GetAboveAver的 idUCf和 CNT，而 GetDetail未计算.综上所述，本文算法在保证多层嵌套结构程序的静态切片完整性的前提下，充分考虑了函数调用信息，有效节省了时间与空间.

1)传统方法分析的对象是PDG或SDG.建立PDG和SDG时需要计算程序的控制流和数据流，复杂度主要集中在数据流分析中.假设程序中包含n个节点，利用迭代算法生成每个节点的定值/引用到达信息，数据流分析的时间复杂度为O(n2).

本文方法分析的对象是函数的CNT和idUCF五元结构.建立CNT和idUCF五元结构只需分析标准化TOKEN序列一次即可，因此时间复杂度为O(n).

2)传统方法计算切片时的时间复杂度普遍为O(n4).对于本文方法，考虑最坏情况，假设idUCF五元结构中元素个数为n(实际上idUCF中的元素个数远小于n)，切片准则中包含了程序中的所有变量，本文方法计算切片的时间复杂度为O(n2).

对于空间复杂度，传统方法通常使用矩阵来存储PDG、SDG的数据依赖关系和控制依赖关系，矩阵大小为n×n，则空间复杂度为O(n2).本文方法只需要存储CNT和idUCF五元结构.考虑最坏情况，假设idUCF五元结构和CNT中元素个数之和为n(实际上应远小于n)，本文方法需要存储空间为5×n，则空间复杂度为O(n).

5 结语

针对传统的基于PDG、SDG的程序切片算法需要计算无关数据依赖，计算复杂度较高的问题，本文提出基于idUCf五元结构的过程间切片算法，对于多层嵌套结构程序在保证其静态切片完整性的前提下，只计算与切片相关的依赖信息，提高了程序切片的计算效率.

［1］WARD M，ZEDAN H.Combining dynamic and static slicing foranalysing assembler［J］. Science of Computer Programming，2010，75(3):134-175.

［2］HALDER R，CORTESI A.Abstract program slicing on dependence condition graphs［J］.Science of Computer Programming，2013，78(9):1240-1263.

［3］WEISER M D.Rrogram slices formal，psychological and practical investigations of an automatic program abstraction method［D］.Michigan:University of Michigan，1979.

［4］ OTTENSTAN K J，OTTENSTAN L M.The program dependence graph in a software development environment［J］.ACM SIGPLAN Notices，1984，19(5):177-184.

［5］ HORWITZ S，REPS T，BNKLEY D.Interprocedural slicing using dependence graths［J］.ACM Trans on Programming Language and System，1990，2(1):26-60.

［6］姜淑娟，徐宝文，史亮.一种基于异常传播分析的数据流分析方法［J］.软件学报，2007，18(4):832-841.

［7］张龙杰，谢晓方，袁胜智.一种改进的静态程序切片算法［J］.计算机应用，2009，29(3):705-711.

［8］ BESZEDES A，GERGELY T，SZABO Z M，et al.Dynamic slicing method for maintenance of large C programs［C］//Proceedings of the Fifth European Conference on Software Maintenance and Reengineering. Washington， DC:IEEE Computer Society，2001:105-113.

［9］SIKKA P，KAUR K.Program slicing techniques and their need in aspectoriented programming ［J］.International Journal of Computer Applications，2013，70(3):11-14.

［10］DANICIC S，HARMAN M，HOWROYD J，et al.A non-standard semantics for program slicing and dependence analysis［J］.The Journal of Logic and Algebraic Programming，2007，(72):191-206.

［11］龚丹丹，王甜甜，苏小红，等.冗余代码缺陷检测方法［J］.哈尔滨工业大学学报，2012，44(7):58-63.

［12］BINKLEY D，GOLD N，HARMAN H.An empirical study ofstatic program slice size ［J］. ACM Transactions on Software Engineering and Methodology，2007，16(2):1-32.

［13］KRINKE J.Effects of context on program slicing［J］.Journal of Systems and Software，2006，79(9):1249-1260.