一种组合式基于调用栈的程序切片方法

戚晓芳 周晓宇 徐晓晶 张迎周

(1东南大学计算机科学与工程学院，南京 210096)

(2南京邮电大学计算机学院，南京 210003)

程序切片最初是由Weiser提出的一种程序调试技术，它通过计算发生故障(程序执行出错)语句的切片来分解原有程序，确定影响该语句执行的语句集，并在该较小的语句集中查找和定位程序错误，以达到缩小程序错误排查范围、方便程序调试的目的［1－6］.对程序的某次执行而言，影响发生故障语句的语句实际上只与当前调用上文相关，在遍历程序依赖图时，如果只考虑当前调用上文，那么可去除静态切片中因考虑所有调用上文而引入的冗余语句，提高分析精度.由于调用上文信息可从当前调用栈中提取，因此本文将这种切片称作基于调用栈的程序切片，该切片一般较小，平均约为静态切片的30%，且因无需记录、分析程序执行信息，其精度和效率达到较好的折中，可进行较为有效的程序调试［7－8］.

基于调用栈的程序切片计算一般通过遍历程序系统依赖图(SDG)获取［7－9］，对大程序来说，SDG庞大复杂，分析需耗费大量的时间和空间.例如，采用Codesurfer2.1切片工具进行实验，大于6万行的程序平均分析时间超过1 h，一些复杂度高的程序则需更长时间，如分析4万行左右的Crypto5.2.1 程序时间超过 5 h［10］.为提高大程序调试的响应速度，本文对传统的基于SDG的切片方法进行改进，提出按需分析的策略，即通过仅分析程序中部分与切片标准相关的子程序，而不是所有子程序来提高分析效率，同时为实现上述分析策略，提出一种组合式的基于调用栈的程序切片方法.本文首先给出组合式依赖性分析方法，然后提出相关子程序分析算法以及组合式的基于调用栈的程序切片方法，最后给出结论.

1 组合式子程序依赖性分析

程序内的依赖关系主要包括由控制条件引起的控制依赖和由访问变量引起的数据依赖.程序依赖图(，PDG)是一个有向图，用二元组(S，E)表示，其中S为节点集，边集E表示节点间的控制或数据依赖关系.顺序程序中依赖关系具有传递性，子程序内的静态切片通过简单遍历PDG获得［9］.子程序间的静态切片通过两趟式遍历系统依赖图计算，SDG由各子程序的PDG通过添加调用节点、形参和实参输入输出附加节点以及调用边、参数依赖边和参数可传递边等连接而成［9］，构造SDG需一次性分析所有子程序.

组合式的子程序依赖性分析方法根据实际需要，分析与程序切片相关的部分子程序.该方法以子程序为基本分析单位，各子程序依赖图相对独立，整个程序的依赖图由各子程序的依赖图组合而成，子程序的对外接口通过参数间的依赖关系实现［6］.根据子程序调用结束后参数值是否返回，可将参数分为读参数、写参数以及读写参数，其中读参数指在子程序调用中作为引用性变量出现、其值不能返回的参数，写参数指作为定义性变量出现、其值可返回的参数，读写参数指既作为定义性又作为引用性变量出现且其值可返回的参数.

定义1 设fI，fO分别为子程序P的某读参数和写参数(当该参数为读写参数时，fI可能与fO相同)，若对fO的定义直接或间接依赖于子程序P入口节点sentry定义的fI，则称参数fO依赖于参数fI，记作PD(fI，fO)，将fO依赖的所有参数集合称作fO的参数依赖集，记为PDS(P，fO).

定义2 设fO为子程序P的某写参数，sexit为子程序P的出口节点，则子程序P关于参数fO的切片是在 sexit处影响 fO值的语句集，记为PSlice(P，fO).

在上述定义中，以〈sexit，{fO}〉为切片标准遍历子程序P的依赖图，直至子程序P的入口节点sentry(在sentry处定义所有的读参数和读写参数)，在sentry处所依赖的参数集合即为fO的参数依赖集.在很多情况下，子程序调用可能返回多个参数值，为区分对不同参数的定义和引用，在每个子程序调用处，为每个写参数或读写参数添加一个实参附加节点，这些节点控制依赖于子程序调用语句.对每个实参附加节点s，设aO为s表示的实参，fO为相应的形参，令s的变量定义集为Def(s)={aO}，变量引用集为并且 aI为 fI对应的实参}.

根据形参间的依赖关系以及形参和实参之间的映射，可获得实参之间的依赖关系(类似于SDG中的参数可传递边)［9］，由此子程序调用语句可作为一般语句处理.在切片过程中，先进行子程序内切片，然后通过实参和形参之间的映射，对调用上下文中的子程序再作相应的切片分析，从而实现以子程序为单位的组合式分析策略.

2 相关子程序分析方法

为实现按需分析策略，需确定与切片标准相关的子程序集合，在程序依赖性分析前不可能也没有必要精确确定这些子程序.为此，本文提出一种综合利用控制流和调用栈信息保守估算相关子程序集的方法.

给定某程序P，其子程序调用图(CG)用二元组〈N，Ec〉表示，其中N为节点集，每个节点对应一个子程序，Ec为边集，边〈pi，pj〉表示子程序pi中调用了pj.

定义3 给定调用语句序列cs=(n0n1…nk)，若cs是由程序P在某次执行过程中调用栈中的调用语句由栈底到栈顶顺序排列而成的语句序列，则称cs为程序P的一个调用栈状态.

在定义3中，称返回cs栈顶元素nk的操作为cs的读操作，记为Rd(cs)，称弹出栈顶元素的操作为cs的取操作，记为 Del(cs)，其中 Rd(cs)=nk，Del(cs)=(n0n1…nk－1).

定义4 给定切片标准〈cs，s〉，其中 cs为某调用栈状态，s为某语句，则基于调用栈cs关于s的切片是由程序中所有可能影响s在调用栈cs下执行的语句集组成，记为Slice(cs，s).

由切片的定义可知，在切片标准之前执行的语句才有可能影响切片标准语句的执行，因此可直接获得下列性质.

性质 1 若语句 s′∈Slice(cs，s)，则 s′在 s之前执行.

利用性质1，通过计算在cs下s的所有可能的前驱所在的子程序集合作为相关子程序集，具体见算法1.

算法1 相关子程序集分析算法

输入:切片标准〈cs，s〉，子程序调用图CG和各子程序的控制流图CFG.

输出:与Slice(cs，s)相关的子程序集Q.

在算法1中，首先分析在切片标准以及当前调用栈中调用语句的前驱，从中找出子程序调用节点对应的子程序，放入集合Q1和工作表W1.W1中的子程序直接或间接调用其他子程序，通过遍历子程序调用图获取这些被调子程序集合Q2.Q2中的子程序在切片标准执行之前可能已全部执行，需完全分析其中所有子程序的参数依赖关系.对Q中不在Q2中的子程序调用语句的参数依赖暂定为参数间完全依赖并作相应标记，以便在后续分析获得相应参数依赖关系后重新修改.

3 组合式的基于调用栈的程序切片

采用组合式的子程序分析方法计算基于调用栈的程序切片的具体算法见算法2.

算法2 组合式基于调用栈的程序切片算法

输入:子程序依赖图，切片标准〈cs，s〉.

输出:关于〈cs，s〉的切片 Slice(cs，s).

算法2分为2个阶段:第1阶段以切片标准s为始点遍历调用上文，即直接或间接调用切片标准所在子程序的PDG;第2阶段遍历第1阶段所涉及子程序的调用下文，即被这些子程序所调用子程序的PDG.在第1阶段，当遍历到实参附加节点时，进行实参到相应形参的映射;当遍历到子程序入口时，从调用栈的顶端依次向下找到对应的调用语句，将形参映射为相应的实参，并通过到达调用语句的变量定义集找到实参表达式中所使用变量的定义语句，上行遍历.在算法2中，DD(sz，sy)表示sy数据依赖于sz，Ref(s)指s中引用的变量集合，In(s)指到达s时变量的定义位置集合.算法2对程序依赖图进行遍历，其时间复杂度为O(n2)，与静态切片的时间复杂度相同.

下面给出一个实例的C++源程序:

实例中除主函数main外还包含4个子程序Acc，Inc，Add和Prod，其子程序调用图以及各子程序的PDG如图1所示.在图1(b)中，在Acc的调用处为实参s和i添加了A1和A2节点，在Prod调用处为返回值添加了A3节点.在图1(d)中，在Acc的调用处为a对应的实参x添加了A4节点，在Inc的调用处为z对应的实参y添加了A5节点.在图1(e)中，在Add的调用处为a对应的实参z添加了A6节点.图1(f)中，在Inc的调用处为z对应的实参k添加了A7节点.

图1 子程序调用图及各子程序的PDG图

下面以S15为例计算S15在不同调用栈状态下的切片以及S15的静态切片.由于子程序调用返回时相应的调用语句已从调用栈中弹出，同一个调用栈状态可能表示多个不同的调用语句历史记录.当调用语句历史记录为〈S7S12〉和〈S7S12S13S12S7S12〉时，在这2个不同的执行中调用栈状态相同，两者都用调用状态〈S7S12〉表示.在实际执行过程中，执行S15时可能有多个调用历史记录，但只有3种调用栈状态，即〈S7S12〉、〈S7S13S17〉和〈S9S24S17〉.

采用算法1计算关于〈(S7S12)，S15〉切片的相关子程序集为{main，Acc，Inc，Add}，其中 Acc，Inc和Add进行完全分析，main进行不完全分析.采用算法2计算切片时，第1阶段访问的节点集为{S15，S14，S12，S11，S7，S6，S3，A2，S4，S5，A1，S1}，其中A1和 A2为实参节点.将{(Acc，{x})，(Acc，{y})}加入PC集，第2阶段访问的节点集为{A4，S11，S12，S13，A5，A6，S14，S15，S16，S17}.去除附加节点后，切片为{S1，S3，S4，S5，S6，S7，S11，S12，S13，S14，S15，S16，S17}.

类似地，〈(S7S13S17)，S15〉的切片为{S1，S3，S5，S6，S7，S11，S13，S14，S15，S16，S17}.〈(S9S24S17)，S15〉的切片为{S1，S9，S14，S15，S16，S17，S18，S20，S22，S24}.

同一个语句s可在不同的调用栈状态下执行，这些调用栈状态可从程序的实际运行收集，也可通过程序的静态分析获得，静态分析的调用栈状态可能不能在程序的实际运行过程中出现.搜索子程序调用图中所有列为S的调用路径，在每个调用路径上组合各子程序中包含的调用语句，可静态生成所有调用栈状态，记这些调用栈状态集合为 CSS(s).关于〈cs，s〉的切片 Slice(cs，s)和关于〈s〉的静态切片Slice(s)之间存在下列关系.

性质2 Slice(s)=∪cs∈CSS(s)Slice(cs，s).

证明 Slice(s)考虑所有的调用上文，每个调用上文对应一个静态调用栈状态，CSS(s)包含了调用图中所有静态调用栈状态，即所有的调用上文.因此，Slice(s)=∪cs∈CSS(s)Slice(cs，s).

静态切片需考虑切片标准的所有调用上文，在图1实例中，关于〈S15〉的静态切片为{S1，S3，S4，S5，S6，S7，S9，S11，S12，S13，S14，S15，S16，S17，S18，S20，S22，S24}.

合并关于〈(S7S12)，S15〉、〈(S7S13S17)，S15〉和〈(S9S24S17)，S15〉的切片，可发现合并结果与关于〈S15〉的静态切片的计算结果完全相同.同时，从上述切片结果可看出，同一个语句在不同的调用栈状态下有不同的影响语句集.与传统的考虑所有调用上文的子程序间切片相比，采用基于调用栈状态的子程序间切片可更有效地帮助程序员进行程序调试.

4 实验分析

比较基于调用栈的程序切片与静态程序切片的大小在文献［8－9］已作了较为详尽的研究.本文对几个不同规模的程序进行实验，初步研究了采用按需分析策略在提高基于调用栈的程序切片分析效率方面的影响.3个实验程序基本信息及Codesurfer分析时间如表1所示，其中Zlib1.2.3提供压缩和解压功能，BNBT是比特流追踪软件，Crypto 5.2.1 实现加密算法［11－13］.实验环境为 Windows XP，Visual Studio 2005，Codesurfer2.1，CPU 为 Intel Q840，主频为 2.66 GHz，内存为3 GB，采用 Codesurfer2.1对上述程序分析.表1中Codesurfer分析时间指程序通过Codesurfer2.1静态分析后可直接进行程序切片计算所需的时间，包含编译、分析源程序生成控制流图(CFG)、子程序调用图以及系统依赖图等时间，其中构建系统依赖图的时间占据了绝大部分分析时间［8］.

表1 程序基本信息及Codesurfer分析时间

根据Codesurfer2.1分析得到的CFG和子程序调用图信息，实现了算法1.根据子程序调用图静态生成所有调用栈，同时以子程序出口语句作为切片标准，计算相关子程序数占程序中子程序总数的比值.表2给出了上述3个程序在不同调用栈深度下的相关子程序数占子程序总数的平均值，表中Zlib1.2.3，BNBT 和 Crypto5.2.1 的最大调用深度分别为7，17和13.由表2可看出，相关子程序集的大小与调用栈深度关系不大，没有明显的规律，而与程序本身有关.在一般情况下，相关子程序数占总子程序数的比例较小，约为0.03% ～17.1%，尤其在大规模程序中，如 Crypto5.2.1中不大于1%.如果采用本文提出的组合式子程序切片方法，将使分析时间大大缩短.可以预测就某个切片标准而言，其平均分析时间约为原有时间的1%，即3 min左右.切片计算时间一般很短，可忽略不计，这将满足使用基于调用栈程序切片在调试过程中快速响应的需求.

表2 不同调用栈深度下平均相关子程序比例 %

5 结语

为提高分析效率，本文首先提出一种与切片标准相关的相关子程序分析算法，以实现按需分析策略，然后在此基础上提出组合式基于调用栈的程序切片方法.该方法以子程序为依赖性分析单位，通过参数间的映射实现子程序间的分析.初步的相关子程序分析实验结果表明，本文提出的方法是可行的，可有效地提高大程序的分析效率，改善调试响应时间.在今后的工作中，将在本文工作的基础上，实现基于调用栈的组合式程序切片方法，并进行相应的实验分析.

References)

［1］ Weiser M.Program slicing［J］.IEEE Transactions on Software and Engineering，1984，10(5):498－509.

［2］ Xu B，Qian J.A brief survey of program slicing［J］.ACM SIGSOFT Software Engineering Notes，2005，30(2):1－36.

［3］Binkley D，Gold N，Harman M.An empirical study of static program slice size［J］.ACM Transactions on Software Engineering and Methodology，2007，16(2):1－30.

［4］ Harman M，Binkley D，Gallagher K，et al.Dependence clusters in source code［J］.ACM Transactions on Programming Languages and Systems，2009，32(1):1－33.

［5］戚晓芳，徐宝文，周晓宇.一种基于程序可达图的并发程依赖性分析方法［J］.电子学报，2007，35(2):287－291.Qi Xiaofang，Xu Baowen，Zhou Xiaoyu.An approach to analyzing dependence of concurrent programs based on program reachability graph［J］.Acta Electronica Sinica，2007，35(2):287－291.(in Chinese)

［6］徐宝文，陈振强，周晓宇.基于依赖性分析的面向对象Ada95程序切片［J］.软件学报，2001，12(增刊):208－213.Xu Baowen，Chen Zhenqiang，Zhou Xiaoyu.Slicing object－oriented Ada95 programs based on dependence analysis［J］.Journal of Software，2001，12(supp)，208－213.(in Chinese)

［7］ Horwitz S，Liblit B，Polishchuk M.Better debugging via output tracing and callstack－sensitive slicing［J］.IEEE Transaction on Software Engineering，2010，36(1):7－19.

［8］ Krinke J.Effects of context on program slicing［J］.Journal of System and Software， 2006， 79(9):1249－1260.

［9］ Horwitz S，Reps T，Binkley D.Inter－procedural slicing using dependence graphs［J］.ACM Transactions on Programming Languages and Systems，1990，12(1):26－60.

［10］ Gramma Tech.Codesurfer2.1［EB/OL］.(2007－05－30) ［2011－05－25］.http://www.grammatech.com/products/codesurfer/overview.html.

［11］ Gailly J，Adler M.Zlib1.2.3［EB/OL］.(2005－07－18)［2011－05－25］.http://gnuwin32.sourceforge.net/packages/zlib.htm.

［12］ Hogan T. BNBT easytracker beta7.7 ［EB/OL］.(2003－09－05) ［2011－05－25］.http://sourceforge.net/projects/bnbteasytracker/.

［13］ Dai W.Crypto++5.2.1［EB/OL］.(2004－07－21)［2011－05－25］.http://www.cryptopp.com/.