计算机程序切片技术探讨

刘恩娜

摘要：程序切片技术是一种分析和理解程序的技术，在程序切片技术提出的30年来，得到了很快的发展。本文主要介绍了程序切片的基本概念，程序切片的种类、算法以及用途。

关键词：动态程序切片；算法：回归测试

1计算机程序切片的分类

１.１ 前向切片和后向切片

根据计算切片方向的不同，可把程序切片分为前向程序切片和后向程序切片。前向程序切片是指所有受兴趣点变量的值影响的语句的集合；后向切片是指程序中所有能够影响兴趣点变量的值的语句的集合。这两类切片最后是不构成一个可执行程序的。

1.2 过程内切片和过程间切片

根据切片的范围，可以分为过程内切片和过程间切片。过程内切片是指单个过程内影响兴趣点变量的值(或受兴趣点变量的值影响)的语句的集合，不考虑过程调用的情况；过程间切片指在过程内切片的基础上，考虑过程调用的情况。执行过程间切片时，要分析实参和形参相对应的依赖关系，要完成实参和形参之间依赖性的转换。

1.3 静态切片，动态切片和条件切片

根据切片过程对程序某一次具体的输入的依赖程度，可将程序切片分为静态切片和动态切片。静态切片是指不考虑程序运行时的输入，完全利用静态分析方法得到切片，也就是分析程序的源代码，计算所有可能输入情况下的切片。静态切片考虑了程序中所有的执行路径，包含了所有与兴趣点处变量相关的语句，不管某些语句在程序实际的执行中是否被执行，因而，静态切片具有很大的冗余性，工作量较大。

动态切片是指在特定输入下实际影响兴趣点变量值（或受兴趣点变量值影响）的所有语句的集合。动态切片只考虑程序在某个具体输入下，实际执行的路径中，和兴趣点变量相关的语句。因此，动态切片的计算过程依赖于程序的具体输入，因而，每一次的计算工作量较小，但得到的切片相对比较精确。

条件切片技术是一种介于静态切片技术与动态切片技术之间的切片技术。在进行条件切片时，只有满足该切片条件的那些输入才会被分析。这个条件对应着程序的某个或某些初始状态。如果存在从满足切片条件的任一个初始状态出发都不可能被执行的语句，那么把这些语句去除掉后，就得到了在这个切片条件下的程序切片。

2 程序切片的准则

程序切片还要考虑切片准则。对于不同的切片准则，相同的源代码得到的程序切片是不同的。基本上，对每一类切片都有不同的切片准则。常见的切片准则有：

2.1 静态切片准则

如果要对一个程序P进行静态切片，需要构造一个静态切片准则。p是感兴趣点，就是程序中的某条语句。V是p处定义或引用的变量，可以是某一个变量，也可以是几个变量的集合。程序P的静态后向切片就是程序中所有能够影响p处的V中的变量的语句的集合；静态前向切片就是程序中所有受p处的V中的变量影响的语句的集合。

2.2 动切片准则切片

如果要对一个程序进行动态切片，需要构造一个动态切片准则。动态切片准则是一个三元组，其中p是感兴趣点，就是程序中的某条语句。V是p处定义或引用的变量，可以是某一个变量，也可以是几个变量的集合。i是程序本次执行的具体输入。程序的动态后向切片是指在本次执行的语句中，所有能够影响p处的V中的变量的语句的集合；程序的动态前向切片是指在本次执行的语句中，所有受p处的V中的变量影响的语句的集合。

2.3 条件切片准则

如果要对一个程序进行条件切片，需要构造一个条件切片准则。条件切片准则是一个三元组，其中p是感兴趣点，就是程序中的某条语句。V是p处定义或引用的变量，可以是某一个变量，也可以是几个变量的集合。π是一个谓词，是V中变量的关系的集合。构造一个程序P的条件切片，当在一个满足π的初始状态执行时，条件切片必须保持程序P（与V有关）的投影含义。

2.4 迭代切片准则

迭代切片准则是一个三元组C=，其中p是感兴趣点，就是程序中的某条语句。V是p处定义或引用的变量，可以是某一个变量，也可以是几个变量的集合。n是自然数。程序P的第n次(静态)迭代切片是由第n次执行到达p那些保持程序P的投影含义不变的语句组成。当n扩充到N（自然数集）时就变成广义迭代切片准则。

2.5 多点切片准则

多点切片准则是一个二元组C=(V,N)，其中N是程序P中节点的集合，V是变量的集合。当在N中任何一点执行一条语句时，对于V中的所有变量而言，切片和程序P具有同样的效果。

3程序切片的算法

程序切片的算法很多，有weiser提出的数据流方程的算法，Karl Ottenstein和Linda Ottenstein提出的基于程序依赖图的算法。Horwitz, Reps和Binkley扩展了程序依赖图的算法，提出了系统依赖图的方法。Ernst提出了基于另一种图表示的Value dependence graph(VDG)算法。另外还有无定切片算法，Ergeretti的基于信息流关系的算法，杨洪的基于波动图的算法等。其中以基于依赖图的图形可达性算法应用最为广泛。该方法首先根据程序中的数据依赖和控制依赖关系将源程序转化为程序依赖图的表示形式，然后利用两次图遍历算法，得到该源程序的关于某一切片准则的程序切片。

4 程序切片的应用

程序切片技术在软件工程的活动中应用非常广泛。如程序分析、理解、测试、调试、度量以及维护过程中都可以应用程序切片技术。了解程序切片的作用，是我们研究切片技术的基础。

4.1 程序调试

在程序调试过程中，经常需要跟踪程序的执行过程，以定位错误，然后改正。然而对于大型程序来说，程序每次执行的语句都很多。如果采用逐条语句跟踪的调试方法，将会耗费大量的时间，效果也不好。程序切片可以帮助程序员很容易的进行错误定位。通过程序切片技术，可以收集到只和出错变量相关的语句，忽略其他的语句，调试时，那些和出错变量不相关的语句就可以不考虑，这样就加快了调试过程。

4.2 程序理解

对原有软件系统的维护和修改是一项非常繁琐的工作，在开发过程中，对原有系统的理解要占整个软件开发生命周期和软件费用的50％到70％。所谓程序理解就是通过系统的静态描述来理解程序的动态行为。不借助专门的程序理解工具，无论是对经验丰富的维护人员还是一个新手来说，程序理解的过程都是很困难的。程序切片作为一种程序理解的方法能够将用户所关心的变量从复杂的程序中挖掘出来。计算该变量的程序切片，让用户更清晰地理解其它变量与该变量之间的联系，在切片过程中，还能收集程序的调用信息，类，结构等信息，这样用户就能很方便地理解程序了。

4.3 回归测试

回归测试是指在对程序的某一模块进行了修改后，为了确保对模块的修改达到目的并且没有引入新的错误，需要对已经完成的测试重新进行，即重新测试先前测试过的测试用列。但测试用列通常很多，全部进行回归测试需要花费很多的人力和时间，在很多情况下是不切实际的。

运用程序切片技术可以比较新旧版本程序的系统依赖图，找出新旧版本程序的差别所在。这样，就能找到针对那些不同点的测试用列，进行测试，减少了工作量。

4.4 测试数据生成

动态切片应用于软件测试数据自动生成，可以有效地提高基于路径测试数据的生成效率，主要的思想是通过比较动态切片结果与指定路径，不断地调整输入，直到与指定路径相符，输入则为测试数据。应用动态切片来生成测试数据，可以减少反复执行程序花费的时间，并且根据动态切片可以消除调整的盲目性，减少调整次数，提高测试数据的生成效率。

4.5 逆向工程

逆向工程这个术语最初来自硬件，后来发展到软件工程中。在软件工程中是指分析程序．力图在比源代码更高抽象层次上建立程序表示的过程。其中的主要工作就是如何对现存的软件系统进行理解，包括对程序源代码的抽象，对程序基本算法和设计方案的理解等。通过构造程序切片可以对源程序进行精简，除去暂不关心的部分，将源程序中分散的关键部分专门进行分析。

参考文献

[1]杨洪,徐宝文,PSS/Ada程序切片系统的设计与实现,计算机研究与发展,1997,34(3)

[2]朱平,谭毅,李必信等,一种基于分层切片模型思想的源程序信息分析方案,计算机工程,2001,27(12)

[3]王伟,陈平,程序切片技术综述,微电子学与计算机,2002,8

[4]王雪莲,赵瑞莲,李立健,一种用于测试数据生成的动态程序切片算法,计算机应用,2005,6(6)