程序动态切片技术研究

摘 要

程序切片技术是一种重要的程序分析技术，广泛应用于程序的调试、测试与维护等领域。程序切片主要通过寻找程序内部的相关特性，从而分解程序，然后对分解所得的程序切片进行分析研究，以此达到对整个程序理解和认识的目的。而动态程序切片主要是指在某个给定输入的条件下，源程序执行路径上所有对程序某条语句或兴趣点上的变量有影响的语句。

面向对象技术仍是目前软件开发方法的主流，其中封装、继承、多态、并发等特征都为程序的理解与分析提出了新的问题。本文在程序的分析评测中引入使用基于依赖图的程序切片技术，实现其切片功能，解决在程序理解、程序复杂性度量、程序转换和评测中遇到的问题。

本文采用一种基于依赖图的面向对象的动态程序切片方法,核心算法是以静态程序的程序依赖图为基础，先从程序依赖图里提取出对应给定执行历史的数据依赖节点和控制依赖节点，使用图可达性算法，计算得出可达语句集，从而获得所需的动态切片，对程序进行理解分析。 

【关键词】：数据依赖、控制依赖、程序依赖图、程序切片、动态切片 

Abstract

Program slicing is an important program analysis techniques, widely used in debugging, testing and maintenance and other fields. Program slicing within the main 

program by finding the relevant features to break down program, and then proceeds to the decomposition of the analysis of program slicing, in order to achieve the 

overall objective of understanding and awareness programs. The dynamic program slice is the main input in a given condition, the source of all the program execution 

path of a statement or point of interest on the variable impact statement. 

    Object-oriented software development method is still the mainstream, including encapsulation, inheritance, polymorphism, concurrency and other features are the 

understanding and analysis of the program raised new problems. In this paper, the introduction of evaluation procedures for the analysis of dependence graph-based 

program slicing techniques to achieve its slice function to solve the program comprehension, program complexity metrics, program transformation and evaluation of 

problems encountered.

This paper, a dependency graph based on dynamic program slicing of object-oriented approach, the core algorithm is the program that rely on a static picture shows 

the base, starting with the program dependence graph to extract the corresponding implementation of the history of a given node and the control dependence data 

dependence Nodes, using the graph accessibility algorithm calculated statements set up to obtain the necessary dynamic slicing, program understanding of the analysis.

【Key words】：DD,CD,PDG,Program Slicing,Dynamic Slicing 

目  录

摘 要 I

Abstract II

第一章 绪 论 

第一节 课题研究目的和意义 

第二节  研究内容和本文结构 

第二章 程序切片技术 

第一节 程序切片技术的概述 

第二节 切片技术的应用 

第三章 动态程序切片技术 

第一节 动态切片法产生的背景及现有算法 

第二节 动态程序切片实现算法 

第四章 动态程序切片系统设计 

第一节 系统概要设计 

第二节 详细设计 

第三节 实例分析 

第五章 系统的实现环境和运行结果的分析 

第一节 开发与运行环境 

第二节 系统输出 

第六章 结束语 

第一节 本文的主要工作 

第二节 展望 

致谢 

参考文献 

附录 

附录A核心代码 

附录B 英文原文 

附录C英文翻译 

附录D

第一章 绪 论

第一节 课题研究目的和意义

软件危机曾经是软件界甚至整个计算机界最热门的话题为了解决这场危机，软件从业人员、专家和学者做出了大量的努力。现在人们已经逐步认识到所谓的软件危机实际上仅是一种状况，那就是软件中存在故障，正是这些故障导致了软件开发在成本、进度和质量上的失控。故障是软件的属性，而且是无法改变的，因为软件是由人来编写的，所有由人做的工作都不会是完美无缺的。

软件测试就是“为了发现故障而执行程序的过程”，其根本目的就是尽可能地消除软件中的故障，使得软件在正式投入使用之前，软件中的故障密度达到尽可能低或者可以接受的程度。软件测试是软件生命周期中的重要一环，在当前的软件开发过程中发挥着越来越重要的作用。统计表明，在典型的软件开发项目中，软件测试工作量往往占软件开发总工作量的40%以上;在软件开发的总成本中，用在测试上的开销要占到50%左右。

软件测试的实质是根据软件开发各阶段的规格说明和程序的内部结构精心选取一批测试数据，形成测试用例，并用这些测试用例去驱动被测程序，观察程序的执行结果，验证实际运行结果与期望结果是否一致，然后做相应的调整。可见，测试数据生成是软件测试的核心与关键。

白盒测试(结构测试)一般是根据被测程序的内部结构设计测试用例，具有很强的理论基础。这种结构测试要求对被测程序的结构特性做到一定程度的覆盖。路径覆盖是一种相对比较强的覆盖标准，要求生成足够多的测试数据，尽可能覆盖所有程序路径。但是，实际中往往会出现这样的情况：多个测试用例执行的是同一条程序路径，而有的程序路径则从未被执行过。因此，探讨一种有效的手段，以辅助基于路径的测试数据生成，有着很现实的意义。

第二节  研究内容和本文结构

本文在理解M.Weiser的切片算法的基础上，根据H.Agrawai等人提出的基于静态程序依赖图的算法，编写程序，最终实现切片系统。并对程序切片进行测试分析。

本文的第一章简要介绍本课题研究的背景、意义以及关于切片系统的实现目标；第二章主要介绍程序切片的技术概述和应用发展；第三章则是动态程序切片的具体算法设计；第四章关于动态程序切片系统设计的介绍；第五章则是本系统的开发环境和运行结果分析；第六章则是对本文的总结以及展望。 

第二章 程序切片技术

第一节 程序切片技术的概述

程序切片技术是M.Weiser在他的1979年的博士论文中首次提出的一种程序分解技术。主要通过寻找程序内部的相关特性，从而分解程序，然后对分解所得的程序切片进行分析研究，以此达到对整个程序理解和认识的目的。后来在1981年和1984年，M.Weiser博士又发表了两篇论文对这种技术进行推广和完善。后来切片技术引起了研究者们广泛的关注，由于它起到了其他技术无可替代的作用，因此可以说是程序分解领域的一场大变革，无论在程序的分析和理解、调试还是测试和维护过程都起到了巨大的作用，另外切片技术还在硬件描述语言和其他规约语言以及形式化模型等方面的分析有至关重要的作用，因此它的研究具有极其重要的理论和实际意义。

M.Weiser博士首先在1979年定义了程序切片的概念:程序中的某个输出只与这个程序的部分相关语句以及控制谓词有关系，因此如果删除其他的语句或者控制谓词将对这个输出没有任何影响。也就是说，对于一个特定的输出，源程序和对于删除不相关的语句和控制谓词后所得的程序是作用相同的。其形式化定义如下:

把满足如下两个条件的切片称为M.Weiser切片:第一，一个程序切片需要对应一个切片准则，用<n，V>表示，其中n指程序中的某个兴趣点，一般指一条语句，V表示在这条语句使用的变量的集合。第二，程序P的切片s可以通过在P中删除零条或者多条语句后得到，且保证程序P和所得的切片S关于切片准则的作用是相同的。

当时，M.Weiser博士把只与某个输出相关联的语句和控制谓词构成的程序称之为源程序的静态切片。由此可见，一个程序的切片大多数是源程序的一个子集，这个概念准确的说其实就是程序切片的一个核心思想。

后来随着研究的发展，研究者们对M.Weiser博士程序切片的概念进行了扩展，由于程序切片不一定都是可执行的，因此又包含了不可执行的切片思想，这也是一种静态切片，这样就丰富和发展了程序切片的内涵。随后，Korel和Laski又提出了动态切片的概念，它只考虑程序的某个特定执行情况，程序中的信息如数组、指针和循环依赖关系都可以在程序执行时动态确定。因此，动态切片与静态切片相比结果更加的准确。

在程序切片技术二十几年的发展过程中主要经历了如图2.1所示的四个阶段：

图2.1 程序切片技术的发展历程

第一个阶段是基于数据流方程的切片阶段，这其实就是M.Weiser博士提出切片概念的阶段，主要使用了基于控制流图的数据流方程来计算程序切片。

第二个阶段是基于依赖图的程序切片阶段，这一阶段产生了对程序切片提出了很多新的概念和算法。首先，Ottenstein等人在提出了基于程序依赖图的图可达性算法，并可以计算过程内后向程序切片，接着又提出了前向切片的概念和算法，以及基于依赖图的两步遍历图的可达性算法。最后Korel和Laski提出了动态切片的概念和算法。

第三个阶段是面向对象的程序切片阶段，这一阶段是伴随着面向对象的高级程序语言的发展而产生，在1996年M.J.Horrald等人首次使用类依赖图来扩展系统依赖图，从而表示面向对象的c++程序，并通过改进的两步遍历图可达性算法来计算程序的切片。随后Christon Steindl在1999年通过对各种数据流以及控制流的计算，提出了面向对象程序切片计算的解决方法，起到了很重要的作用。

最后一个阶段是程序切片变体阶段，这一阶段出现了各种程序切片的变体形式，例如砍片、削片、层次切片等等，这些都极大地促进了程序切片技术的迅速发展。

通过上面程序切片的发展阶段可以看出程序切片有很多种，主要有静态切片和动态切片，前向切片和后向切片，规约切片，削片，砍片，无定型切片等等。这些种类其实本质都是一致的，也是随着发展阶段一步步演化而来的。

由于本文主要使用到动态切片，因此这里主要对与之相关的静态切片和动态切片以及前向切片和后向切片作简要介绍。后文中将详细分析动态切片。

如果在计算程序切片时不考虑程序的具体输入，计算对某个感兴趣点影响的语句和谓词集合，这样得到的切片就是静态切片。其切片准则为<n，V>。

如果在计算程序切片时考虑程序的某个具体输入，然后计算程序P在这个特定输入。的条件下所有影响V在n点的值的语句和谓词集合，这样得到的切片就是动态切片。其切片准则为<n，V，>。

后向切片是指构造一个集合aflect(v/n)，使得这个集合由所有影响v在n点的语句和谓词组成。例如如果在测试程序时发现了其中的某个错误，我们就需要知道是前面哪条语句或者哪个谓词表达式导致了这个错误，这样也就需要计算程序的后向切片。

前向切片正好相反，是指构造一个集合affect (v/n)，使得这个集合由受到n点的变量V的值的影响的所有语句和谓词构成。前向切片也有广泛的应用，如果对程序的bug修改以后，我们可能想知道这点修改是否会带来其他的副作用，也就是说这点修改会影响后面的哪些语句，这就需要计算程序的前向切片。

第二节 切片技术的应用

由于是程序切片，与程序有关，因此毫无疑问在软件的编码和调试阶段用处是最明显的。尤其在调试阶段，当出现错误时通过程序切片可以快速对程序中的错误进行定位，这样引起错误的代码就被限定在这个程序切片里，从而方便了程序员调试。对于软件度量，可以利用软件体系结构的切片技术验证体系结构是否正确，从而保证按照这个体系结构设计出的软件是正确可靠的，同时在设计阶段利用模块间的切片技术也可以设计出高内聚低祸合的模块，从而为软件的重用性起到大的作用。此外，程序切片技术还应用于软件安全方面和软件测试方面。在软件测试中主要用于回归测试，在软件开发过程中，当系统修改了一处或多处后需要对整个软件重新测试，以防止修改不会带来其他模块的问题、一周此工作量是非常大的，而且也会消耗大量的人力物力。由于在回归测试时，软件只有小部分代码被修改，因此只要通过程序切片技术获得源程序中受到修改代码影响的所有其他代码，这样只要对这些受影响的代码进行测试就可以了，这样就给回归测试带来了极大的方便。本文主要采用程序切片技术来自动生成测试用例，也属于程序切片的一个应用之一。

程序切片技术有着广泛的应用场合，主要应用如图2.2所示:

图2.2 切片技术的应用 

第三章 动态程序切片技术

第一节 动态切片法产生的背景及现有算法

本文主要研究的是动态切片程序，所以在这里对动态切片再进行细致的介绍。顾名思义，动态切片法是与静态切片法相对应的，它由静态切片法演化而来。在1988年，B.Korel和J.Laski首次提出动态切片的概念，主要由基于数据流方程的静态切片扩展而来。他们认为动态切片是源程序的一个可以执行的子集，在对某个变量输入相同的变量值时切片和源程序将会执行相同的程序路径。后来，1990年，H.Agrawal和J.Horgan又提出了新的动态切片的思想:动态切片主要包含在某个给定输入的条件下，源程序执行路径上所有对程序某条语句或兴趣点上的变量有影响的语句。这两种概念的不同之处在于，前者产生的动态切片比较大，常常包含一些多余不必要的语句，而后者产生的切片较小，而且更加的精确。动态切片法相对与静态切片法有很多优点，首先，由于它只考虑程序在某个特定输入条件下的情况，所以很多如数组下标、指针、循环依赖关系等程序信息可以在动态执行时动态确定，所以相比静态切片结果会更加的精确。其次，在某些场合下，例如在程序调试过程中，处理一次bug时通常只关注在某个输入下执行的路径行为，而不会关注变量所有可能输入导致的行为，所以动态切片比静态切片更加的方便，大大的减少了切片的大小，调试也因此大大缩小了范围。当然，动态切片法也有缺点，由于动态切片需要追踪程序的执行行为和执行历史，所以空间代价较高。

从动态切片概念的产生发展至今，主要有以下几个动态切片算法。

1.H.Agrawal和J.Horgan在1990年提出的四种计算动态切片的方法。第一种方法是以静态程序的程序依赖图为基础，先从程序依赖图里提取出对应给定执行历史的一个投影图，再利用静态切片法对投影图进行操作，即使用两次图可达性算法，从而获得所需的动态切片。但是这种方法由于常常包含多余的节点，对同一个变量来说某一个节点可能存在很多由该变量引出的数据依赖边，因此计算出的动态切片不够精确。第二种方法类似第一种方法，也是以静态程序的程序依赖图为基础，在程序执行时首先在程序依赖图中标记出产生的依赖边，然后在图中沿着这些标记的边进行遍历，这样由所有标记经过的节点对应的语句集合就构成了动态切片。这种方法改进了第一种方法产生多余节点的问题，但是缺点是却不能处理包含循环结构的源程序。第三种方法不再基于静态依赖图，而是重新提出了一个新图，即动态依赖图：即为执行历史中语句每一次的出现创建一个节点并只对这一次出现有依赖关系的语句添加引出的依赖边。对于不同的程序执行历史，同一个程序有不同的动态依赖图。当建立了程序的动态依赖图之后，先找到执行历史中变量的最后定义所在的节点，然后在图中使用二次图形可达性算法，从而获得变量的动态切片。

2.B.Korel和s.Yalamanchih在1994年提出的前向计算的动态切片算法。算法的主要思想为把程序看成是若干个基本块，然后通过执行到基本块的出口时判断这个基本块是否应该包含在动态切片中。这种方法虽然不需要建立动态依赖图，因此节省了大量的执行代价和执行空间。

3.Goswami和Mall在2002年提出的基于压缩的动态程序依赖图的算法。算法的主要思想为首先建立程序的控制依赖子图，然后再通过程序的执行序列和数据流信息建立程序的数据依赖子图，最后生成动态切片。

第二节 动态程序切片实现算法

一、相关定义：

这里主要对算法相关的术语和定义作一下介绍，后文将不再解释。动态切片准则用三元组 (，v，)表示，s为程序中的某条语句，s表示在第k步执行语句S，v是程序变量或变量集，为输入数据。

定义1:基本模块:指程序中一组连续执行的语句，在模块的开始处控制流

进入，在模块的结束时离开，而且不能在模块的执行过程中终止或者出现分支。对于基本模块，控制流只能从模块的入口进入，从模块的出口离开。

定义2:控制流图   (Control Flow Graph，CFG):控制流图CFG是一个有向图，该有向图的节点是一个包括唯一入口和出口的基本模块，如果控制流可以从一个模块流入另外一个模块，则这两个模块之间有一条边。可以用四元组表示为G=(N，E， Entry，Exit)，其中N是节点的集合，也就是基本模块的集合，E是边的集合，每一条边为一个有序节点对<ni，nj>，表示从ni执行完以后开始立即执行nj，Entry表示子程序的入口，Exit表示子程序的出口，程序从入口节点Entry到nk的节点序列<n1，n2，n3，…，nk>是一条执行路径，其中n1为入口Entry节点，<ni，ni+l> E，1 i k。

定义3:DEF:在CFG中节点n定义变量的集合，记为DEF[n]。

定义4:USE:在CFG中节点n使用变量的集合，记为USE[nl。

定义5:后必经节点:如果从节点n到程序出口节点Exit的每一条路径都经过节点m，则称m为n的后必经节点，记为nm。

定义6:控制依赖(CD):CFG中，设和是其中的两个节点，如果满足以下三个条件，则称控制依赖于，，记为CD(，)。

(1)节点到节点之间有一条可执行路径A。

(2)在A上除了和外的每一个节点n，节点n:都是它的后必经节点。

(3)节点不是节点的后必经节点。

定义7:控制依赖节点集(CDNC):用CDNC()表示当前执行的第k步语句s的控制依赖节点集合。

定义8:数据依赖(DD):CFG中，设和是其中的两个节点，v为一个

变量，如果满足以下三个条件，则称关于变量v数据依赖于，记为口D(，，v)。

(1)节点，对变量v进行了定义，即v任DEF[]。

(2)节点对变量v进行了使用，即v任USE[]。

(3) 存在一条到的可执行路径A，并且在A上除了处没有语句对v进行重新定义。

定义9:数据依赖节点集(DDNC):用DDNC()表示当前执行的第k步语句s的数据依赖节点集合。

定义10:程序依赖图(PDG):主要由包含控制依赖和数据依赖的控制流图CFG组成。

定义11:直接前驱:在CFG中，如果<，>E，则称为的直接前驱，记为Pre()=。

定义12:执行历史:由程序实际执行时经过的一系列节点语句所构成。

定义13:可到达语句:设和为程序中的两条语句，如果控制依赖于或者数据依赖于，则称为，的可到达语句，记为accessible()=。

定义14:程序的循环依赖:设，…….. ,为语句s在含有循环的程序P中n次循环执行，则称语句循环依赖于，，记为cyd()=。

定义15:动态切片:给定一个动态切片准则(，v，)，Dslice(，v)指在当前执行的第k步语句s处变量v的动态切片。

二、实现算法：

本文根据H.Agrawai等人提出的四种算法中的前两种基于静态程序依赖图的算法，通过程序实际的执行路径上的控制依赖和数据依赖节点以及可到达语句，从而计算出满足给定的切片准则的程序切片。

算法描述：

初始化:     For all v V do Dslice (，v)= 

            For all  do accessible()={s}

依次执行每个之后

accessible()=accessible()  DDNC()  CDNC()

 if Cyd(s)=   then

{

accessible()=accessible()  DDNC()  CDNC()

           For v V do

           If vUse(s)  

then

Dslice(，v)=accessible(DDNC())

End for

}

Else

{

accessible()=accessible()  DDNC()  CDNC()

if  

Cyd()= and  accessible()==accessible()

then 

=Cyd ()

else if  

accessible(Pre())= =accessible()

then  

Pre()=Pre()

For v V do

   vUse(s) then

Dslice(，v)=accessible(DDNC())

  End for

}

 

 

下图是本系统的流程图：

图3.1 程序流程图

算法的主要功能：在确定的源程序的的基础上，给定一个输入即某条语句的动态切片准则(，v，)以及源程序的程序依赖图，求出数据依赖节点集、控制依赖节点集，进而求出可到达语句最后输出的变量v的动态切片Dslice(，v)。

算法分两种情况考虑，设为程序中输入为时当前语句s执行到第k步，v在s中被使用，此时如果程序中不存在循环结构，则语句s也就没有循环依赖，即Cyd(s)= ，则只需要计算所有的数据依赖节点集DDNC()，然后计算该节点集里的所有的可到达语句accessible(DDNC())，从而可以得到护的变量v的动态切片为Dslice(，v)=accessible(DDNC()。如果程序中有循环结构，并且语句s有循环依赖，例如和之间存在循环依赖，即Cyd()=，这时要首先计算的可到达语句accessible()，然后再分两种情况，第一种情况，如果accessible()与accessible()相等时，就可以合并节点和，即合并accessible()与accessilile()，第二种情况，如果s的直接前驱节点的可到达语句与s的可到达语句相等，就把s和s的前驱节点合并，即合并s和其前驱节点的可到达语句，从而最终得到的变量v的动态切片为Dslice (，v)=accessible(DDNC())。 

第四章 动态程序切片系统设计

第一节 系统概要设计

在第三章已经详细介绍了动态切片的技术，而且提出了明确的算法，在本章将阐述动态切片系统的设计与实现，并详细介绍系统中各个模块的功能以及它们之间的关系。

    动态程序切片系统的输入为：源程序、程序依赖图、切片准则。系统的结构示意图4.1如下图所示：

图4.1 程序结构图

动态切片程序系统的切片准则用一个三元组<V,p,x>表示，其中x表示程序的输入，p表示程序中一条语句，V表示程序中的变量。切片结果包含了当前输入下所有影响p点的V变量值的语句。

该系统对程序的处理大致如下：

(1)对于输入的源程序进行代码格式化，以获取符合我们要求的程序；

(2)对格式化后的用改造后的编译器执行，以此得到程序的执行记录；

(3)对格式化后的程序进行静态分析，并利用获取的执行记录，生成动态系统依赖图；

(4)在动态系统依赖图的基础上，根据切片准则，进行切片；

(5)将切片的中间结果还原为程序形式。

以下对于每个子系统进行简单介绍：

代码格式器：由于输入的程序各式各样，很多并不符合系统的输入要求，所以要有一部分专门来处理程序的输入，使之符合系统要求并输出合格源程序，因此定制这个部分来进行系统处理，这部分主要的功能是去除源程序空格，空行，分别不规范写法等。并在下一步，程序编译处理之前做预处理动作，一方面极大的降低编译处理的复杂度，另一方面也可以使得编译处理更加规范化，方便和其他系统进行集成。

程序编译处理器：程序编译处理是本功能中比较重点的子系统，因为这里的输出直接影响到一下步执行顺序的生成。而且由于编译器的复杂性，所以这里不应该承担太多的功能，因此，这里的实现原则应该为最简化处理，即：只负责源程序执行顺序的输出，不再进行任何其他功能处理。所以，本文在这里将外围功能均由第一个子系统中的代码格式器承担。

程序分析处理器：这部分主要负责对源程序进行分析，包括找出类中变量定义，类定义。函数定义等，分析各语句之间的依赖关系，包括数据依赖和控制依赖，通过这些分析结果，就可以得到程序依赖图。这里也是比较重要的一部分。这里的结果将会影响到程序依赖图的生成。

切片生成器：切片生成器是得到切片的核心部分，前面几个子系统都是在为这里的切片生成器做数据准备和预处理动作。它运用前一章节提到的算法，把他们用程序逻辑去实现，最后得到切片结果。它的输入包括依赖图的定义，执行历史顺序，源程序。它的输出应该是包含源程序的一种数据结构的表示。

切片表示器：切片生成器得到的结果是动态系统依赖图上的一些节点的数据结构表示，所以我们需要把它还原成源程序，用直观、简洁的方式将程序切片展现出来。具体的方法是利用语句的标号和源程序之间的关系得到原来的程序。因为标号是唯一的，利用这个中间的表示，我们就可以在源程序中找到切出来的语句。

系统实现难点：这个系统中有三个部分比较难于实现，分别是：程序编译处理器，程序分析处理器，和切片表示器。程序编译处理器涉及Java程序的编译处理。由于一般的优秀的商业编译处理器都无法得知源码进行改造，所以这里会尽量使用开源编译器。程序分析处理器和编译处理器一样，一般在编译处理器中都会有实现。这里要实现相应的功能，也可用开源来实现。在这里我采用JavaCC这个开源的程序编译器和分析处理器。

第二节 详细设计

由前几章的算法以及上面根要设计的分析可得，整个系统实现主要分为以下几个部分：

第一部分：读取输入：读取输入包括源程序读取输入以及程序切片准则输入。

第二部分：程序编译处理：读取源程序后，采用JavaCC进行程序编译，根据切片准则以及源程序生成程序执行历史顺序。

第三部分：程序分析处理：读取源程序，进行采用JavaCC进行程序分析每个节点的数据依赖和控制依赖。

1、基本语句控制依赖分析

语句是程序的基本组成单位，语句间的控制依赖关系在语法分析过程中就可以确定。

顺序执行语句：此类语句的执行结果不会影响程序的执行流程，如变量声明语句、赋值语句等，此类语句中无谓词出现，不存在控制依赖。

if语句：如图所示，语句1执行与否，取决于if语句的执行结果，语句1控制依赖于if语句（语句1不一定是一条语句，可能是一个语句块，此情况下，语句1语句块中所有语句控制依赖于if语句）。

 

图4.2  if语句的流程图和控制流图

if-else语句：如图所示，语句2控制依赖于if语句，实际上语句1也是控制依赖于if语句，为了后面切片过程的方便，我们看作语句1控制依赖于else语句，else语句控制依赖于if语句。

图4.3  if-else语句的流程图和控制流图

while语句：如图所示，语句1控制依赖于while语句。 

图4.4 while语句的流程图和控制流图

for语句：同while语句情况相似。

switch-case语句：此类语句可以看作特殊形式的拥有多个分支的if语句。图中语句1、语句2…….语句n控制依赖于switch语句。 

图4.5  switch-case语句的流程图和控制流图

2、基本语句数据依赖分析

类作为面向对象程序中最重要的概念，引入了面向对象程序的许多重要特性，如封装性、继承、多态性等，对类依赖关系的分析是研究面向对象程序切片的基础。

类成员关系：类成员依赖表示了类与类的成员之间的依赖关系。若类C2中以类C1的对象作为成员，则类C2与类C1之间存在类成员依赖关系。如下示例程序中，类C2成员依赖于类成员m，即类C2成员依赖于类C1。

引用关系：引用依赖关系表示一个类通过另一个类的接口去使用该类（包括成员变量的直接引用与成员方法的直接调用）。如下示例程序中，类C2引用依赖于类C1。

继承依赖：继承依赖表示了类与类之间的继承依赖关系,类C1与类C2之间存在继承依赖关系,当且仅当C1是C2的一个子类。下面示例程序中，C2继承依赖于C1。

实例化关系：一个类可能实例化其它类的对象。若类C1中直接实例化一个类C2的对象，则称类C1和类C2之间存在实例化关系。下面示例程序中，C2实例依赖于C1。

从对面向对象程序类的依赖性分析，我们可以利用如下的算法得到数据依赖图：

图4.6  数据依赖子图的建立算法

第四部分：程序数据依赖节点集（DDNC）控制依赖节点集（CDNC）：由上述算法和程序动态数据依赖图可以得到输入程序的数据依赖节点集（DDNC）以及控制依赖节点集（CDNC）。

动态程序切片的依赖图是基于程序的执行历史的，在第三部分得到了各个

节点的控制依赖和数据依赖子图之后，将其根据算法建立源程序的动态语句依赖图和相应的数据依赖节点集（DDNC）/控制依赖节点集（CDNC）。

图4.7  动态语句依赖图的建立算法

本文旨在研究动态程序切片的求解过程，程序依赖图的的求解并非重点，所以在切片系统中默认程序依赖图已经给出。

所以需要一个程序引用的常量类，用来代表源程序常量数据，所有的源程序常量以及所需的输入数据（如切片准则，源程序内容等），均由此处定义。程序文件CharData用于实现这个功能。这里显示部分源码：

public class CharData {

 private static int[][] history = null;

    private static ArrayList<String> programDNC;

}

CharData这个类中，数据定义如下：history[][]这个二维数组就定义了程序的历史执行顺序，programDNC 这个ArrayList定义了程序要进行分析的源程序。

这个类中包包含四个方法：

public static int[][] getHistory( );

public static void setHistory(int[][] history);

public ArrayList getProgramDNC( );

public void setProgramDNC(ArrayList programDNC);

其中getHistory( )和setHistory(int[ ][ ] history) 相配对，用来取得和设置源程序的历史执行顺序；getProgramDNC( )和setProgramDNC(ArrayList programDNC)配对，用来取得和设置被分析的源程序，实现这四个方法是为了以后和其他系统对接，以后要连接其他系统，只需要调用相应的set方法，即可改变这里和默认分析数据。

程序依赖图也由默认定义给出，Tree源码文件用来定义相应的数据结构：

public class Tree {

private ArrayList<TreeChild> TreeData = new ArrayList<TreeChild>();

TreeData 这个ArrayList定义了依赖图的数据结构，为了能更好的表示依赖图，为此定义了一个元数据结构，给出TreeChild元数据结构：

ArrayList<TreeParent> parents = new ArrayList<TreeParent>();

private Object data;

private ArrayList<TreeChild> children = new ArrayList<TreeChild>();

private ArrayList<String> typeList = new ArrayList<String>();

parents 、children、typeList 三个ArrayList分别定义了依赖图一个节点的父级节点、子级节点、以级子级节点所对应的类型。

程序运行节点的数据结构表示如下图：

图4.8  程序运行节点的数据结构

在图4.8中，每个运行节点都包含N个子节点，其中每个依赖子节点都有其子节点依赖属性其中对每个子节点的依赖类型都做了标注，节点的依赖类型对应该子节点顺序。这样就可以把整个依赖图表示为一个ArrayList结构，其中每个节点都为一个ArrayList，节点的数据结构为多个子结点和节点控制类型组成。 

图4.9  程序依赖图的数据结构

整个程序依赖图的数据结构可表示为图4.9，其中每个依赖图内都包含N个源程序节点，每个源程序节点下面又包含N（n>=0）个依赖子节点，其中每个依赖子节点都有其子节点属性。

第五部分：程序可达语句集：由第四部分的DDNC和以及公式accessible()=accessible()+NNDC()+CNDC()可以得到程序的可达语句集。

可达语句集数据结构如下图：

 

图4.10  数据结构图

利用已知的可达语句求解公式，第一步先设计类AccessibleTable，用于得到可达语句数据集，由于可达语句数据集元数据的具有特殊性，如带顺序，和执行历史相关等等，所以为可达语句数据集设计一个元数据类DNCnode，这个元数据类中应该包括源程序以及执行历史顺序等，每个可达语句集内都包含N个可达语句节点，每个源程序节点下面又包含N（n>=0）个DNCnode子节点数据类型，其中每个DNCnode子节点数据类型都有其子节点属性。即：nodeindex nodestep dDNCnodelist cDNCnodelist。

进而建立getAccessibleTable 这个方法是用来得可达语句，getAccessibleTable是这个类的主方法。以下为部分代码片断：

for (IndexTreeNode cDNCChild : cDNCList) {

                //求出每个控制依赖节点的可达语句

for (Object accessibleBefore : accessibleList.get(cDNCChild.getStep() - 1)) {

          accessibleChildList.add((IndexTreeNode) accessibleBefore);

                }

            }

     ArrayList<IndexTreeNode> dDNCList = node.getdDNCNodeList();

     for (IndexTreeNode dDNCChild : dDNCList) {

       for (Object accessibleBefore : accessibleList.get(dDNCChild.getStep() - 1)) {

          accessibleChildList.add((IndexTreeNode) accessibleBefore);

                }

            } //自身的TreeChild

     Tree tree = new Tree();

     IndexTreeNode indexNode = new IndexTreeNode();

     indexNode.setIndex(node.getNodeIndex()); indexNode.setTreeChild(tree.getTreeData().get(data.getHistory()[node.getNodeIndex() - 1][0] - 1));

     accessibleChildList.add(indexNode);

第六部分：程序的切片集：由第五部分的程序可达语句集和公式：Dslice(，v)=accessible(DDNC())可以得到程序的切片集合。

在前面的模块中已经求出了相应的可达语句表，根据求取切片的公式进而求出程序切片。而ShowTest 是整个系统的入口，也是由这里得到具体的程序切片。这个类中只有一个主方法，用来调用程序，得到切片。 

第三节 实例分析

因为在算法的主要功能是在确定的源程序的的基础上，给定一个输入即某条语句的动态切片准则(，v，)以及源程序的程序依赖图，求出数据依赖节点集、控制依赖节点集，进而求出可到达语句最后输出的变量v的动态切片Dslice(，v)。而不去考虑如何去具体求出源程序的程序依赖图。所以，本文将选取一个具有代表性的程序，进行具体分析，进而通过动态切片系统求出切片。源程序如下：

 

 

图4.11 源程序

输入n=2；切片标准：（，v=x，n=2）；

程序依赖图：

 图4.12  程序依赖图

输入n=2，程序的执行历史为<>。

由源程序、程序依赖图和执行历史可得：数据依赖节点集（DDNC）控制依赖节点集（CDNC）如下：

表4.1 数据依赖/控制依赖节点集

节点（）	DDNC（）	CDNC（）
	、
	、
	、

然后由上表和公式accessible()=accessible()+NNDC()+CNDC()可得每个节点的可达语句如下：

 

 

 

 

 

 

表4.2 可达语句集

	初始化	可达语句
accessible()	1	1
accessible()	2	2
accessible()	3	1,2,3
accessible()	4	1,2,3,4
accessible()	6	1,2,3,4,6
accessible()	7	1，2,3,7
accessible()	3	1,2,3,7
accessible()	4	1,2,3,4,7
accessible()	5	1,2,3,4,5，7
accessible()	7	1,2,3,4,7
accessible()	3	1,2,3,4,7
accessible()	8	1,2,3,4,5，7，8

由于本程序带有循环结构，所以选择程序第一次执行还没有出现循环前的节点作为新的切片标准（，v，），此时，n=2.此时的执行历史为<1,2,3,4,6,7,8,3>。这时节点的切片Dslice(,v)=accessible(DDNC())，根据语句可达表，可知accessible(DDNC())=accessible（）=<2>。

（1） 若accessible()=accessible()，则就将，合并。由此可得，没有可以合并的节点。

（2） 如果s的直接前驱节点的可到达语句与s的可到达语句相等，就把s和s的前驱节点合并，即合并s和其前驱节点的可到达语句。 、可合并 、、可合并。

表4.3 各个节点程序切片

节点	Dslice()
初始化
	1,2
	1,2,3
、
、、
	1，2，3，4，5，7

由此可得到切片标准为为（，v=x，n=2）时的切片为<1，2，3，4，5，7>即：

 

 

 

 

 

 

 

 

 

 

图4.13 最终生成的切片

第五章 系统的实现环境和运行结果的分析

第一节 开发与运行环境

本系统的开发在配置为2.00GHz，2.00G RAM的PC上完成；软件环境是Windows xp，使用JDK 1.6.0_17、MySQL 5.1.43、JAVA语言在MyEclipse 7.5下完成。

JDK、MySQL、MyEclipse的安装文件分别可以从其官方网站http://java.sun.com/javase/downloads/index.jsp、http://www.mysql.com/、http://www.myeclipseide.com/上下载，采用默认安装方式。完成安装后，需要对环境进行配置。JDK的配置步骤如下：（1）我的电脑-->属性-->高级-->环境变量；（2）新建 JAVA_HOME，设置为C:\Program Files\Java\jdk1.6.0_17（JDK的安装路径）；（3）新建PATH，设置为C:\Program Files\Java\jdk1.6.0_17\bin；（4）新建 CLASSPATH，设置为C:\Program Files\Java\jdk1.6.0_17\lib。

本系统的测试与开发在同一台PC、同一软件环境下完成。因JAVA具有可移植的特点，最终本系统也可以成功运行于装有JAVA运行环境的PC上。

第二节 系统输出

程序在调试成功之后第四章引用的程序实例对程序进行了测试，在输入确定的切片准则的情况下对源程序进行动态切片。

1、首先对程序进行数据依赖和控制依赖分析，根据算法求出其程序依赖图，进而得到各个节点的数据依赖节点集合控制依赖节点集：

 

 

 

 

 

 

 

 

图5.1  数据依赖节点集合控制依赖节点集

2、进入系统的下一个功能模块，根据求出的数据依赖节点集合控制依赖节点集计算得出各个节点的可达语句集：

图5.2 可达语句集

3、最后根据可达语句集得到各个节点的切片：

 

图5.3 程序切片输出结果

 

 

 

 

 

 

 

 

 

 

 

 

 

第六章 结束语

第一节 本文的主要工作

软件测试对于软件尤其是大型软件的开发至关重要，高质量的软件花费的测试代价是相当大的，尤其在测试用例的编写上花费了大量的精力，而且常常生成的测试用例覆盖率不高，对一些判断较多的逻辑程序生成测试用例更是困难，如何在有效地时间提高测试用例生成的效率变得更加的重要。本文主要完成的工作有以下二点:

1.对H.Agrawal等人提出的四种动态算法的方法和过程进行了主要的分析和研究，通过程序实际的执行路径上的控制依赖和数据依赖节点以及可到达语句，从而计算出满足给定的切片准则的程序切片。

2.通过具体的实例进行分析表明本文提出的动态切片算法是行之有效的。

第二节 展望

由于技术上和时间等问题，开发出的工具仍然存在一定的问题和不足，比如，系统的总体设计还不够完善，只能对特定的源程序进行分析，不能对其他程序进行分析；实现的切片系统只能对源程序进行粗粒度的切片，不能切割出更为精细的切片。总体来说，该工具距离实用性还有一定的差距，因此进一步的研究将主要放在以下几个方面:

1.进一步提高工具的自动化程度，提高工具的效率。例如对可以导入不同的源程序进行分析，甚至可以标出源程序中的错误。另外增加一些相关功能，例如对测试用例生成后生成相应的报告，.并可以用文件形式导出。

2. 对于多个文件的程序调用问题进行研究，这样工具的应用范围将会显著地扩大。 

参考文献

[1]Mark Weiser. Program slicing. Proceedings of 5th International Conference on Software Engineering, pp. 439-449, San Diego,CA, Mar. 1981.

[2]Glenford J.Myers,Corey Sandler,Tom Badgett,Todd M.Thomas.The Art of

Software Testing(2nd Edition)[M].2004.

[3]Clarke L.A system to generate test data and symbolieally exeeute Progrom.IEEE Transaetions on Software Engineering [J]. September 1976; 215-22.

[4]Huang J C.An~Proach to Program testing Computing Surveys [J]. SeP. 1975.7(3):113-128.

[5]GloverF,Kelly J,Laguna M.Genetic Algorithms and Tabu Seareh,Hybrids for OPtimizations[J].Computers Opa Res,1995,22(1),111-134.

[6]W.Miller and D.SPooner.Automatic generation of floating point test data[J].IEEE Transactions on Software Engineering, 2(3):223-226,SePtember 1976.

[7]B.Korel.Automated software test data generation[J]. IEEE Transactions on Software Engineering,16(8):870-879,1990.

[8]荚伟,高仲仪.基于遗传算法的软件结构测试数据生成技术研究闭.北京航空

航天大学学报.1997,23(1):36-40.

[9]李必信.面向对象程序切片技术及其在软件度量和软件测试中的运用.[D1

南京大学博士论文.2000.

 

附录

附录A核心代码

一、可达语句数据集求解算法：

public class AccessibleTable {

     public AccessibleTable(){

    }

     public ArrayList<ArrayList> getAccessibleTable(){

        ArrayList<ArrayList>accessibleList=new ArrayList<ArrayList>();

        GetDNCTable dncTable = new GetDNCTable();

        CharData data = new CharData();

        ArrayList<DNCNode>ndcNodeList= dncTable.getDNCNodeList(data.getHistory());

        for(DNCNode node : ndcNodeList){

            ArrayList<IndexTreeNode> accessibleChildList  = new ArrayList<IndexTreeNode>();

            ArrayList<IndexTreeNode>cDNCList= node.getcDNCNodeList();

        for (IndexTreeNode cDNCChild : cDNCList) {

                //求出每个控制依赖节点的可达语句

        for (Object 

accessibleBefore: accessibleList.get(cDNCChild.getStep()- 1)) {

             accessibleChildList.add((IndexTreeNode) accessibleBefore); 

                }

            }

       ArrayList<IndexTreeNode> dDNCList = node.getdDNCNodeList();

       for (IndexTreeNode dDNCChild : dDNCList) {

            for (Object 

accessibleBefore : accessibleList.get(dDNCChild.getStep() - 1)) {

                  accessibleChildList.add((IndexTreeNode)

accessibleBefore);

                }

            }//自身的TreeChild

Tree tree = new Tree();

       IndexTreeNode indexNode = new IndexTreeNode();

       indexNode.setIndex(node.getNodeIndex());

       indexNode.setTreeChild(tree.getTreeData()

.get(data.getHistory()[node.getNodeIndex() - 1][0] - 1));

     accessibleChildList.add(indexNode);//去除重复记录

boolean[]  flag = new boolean[8];

       for (int i = 0; i < accessibleChildList.size(); i++) {

             int index = accessibleChildList.get(i).getIndex();

//    System.out.println("---------------->" + index);

             if (flag[index-1]) {

                 accessibleChildList.remove(i);

i--;

             }else {

                 flag[index-1] = true;

                    }

            }

             accessibleList.add(accessibleChildList);

        }

        return accessibleList;

    }/*合并可达语句 

二、依赖节点集（DDNC）控制依赖节点集（CDNC）的数据集算法：

public class GetDNCTable {

   ArrayList<DNCNode> dncTable = new ArrayList<DNCNode>();

      /* 数据依赖节点集（DDNC）控制依赖节点集（CDNC）的list */

public ArrayList<DNCNode> getDNCNodeList(int[][] history){

      Tree tree = new Tree();

      ArrayList<TreeChild> treeChildList = tree.getTreeData();

      String historyTemp = "";

      int j = 1;

      for(int[] i : history){ //已经执行的历史顺序

      historyTemp = historyTemp + i[0] + ":" + j + ",";

      reeChild child = treeChildList.get(i[0]-1);

      DNCNode childNode = new DNCNode();

      childNode.setNodeName(i[0] + "：" + j);

      childNode.setNodeIndex(i[0]);

      childNode.setNodeStep(j);

      ArrayList<IndexTreeNode> cList =  tree.getCDNC(child);

      for(int ic = 0; ic < cList.size(); ic++){

      IndexTreeNode ch = cList.get(ic);

      int jtemp = historyTemp.indexOf(ch.getIndex() + ":");

      if(jtemp >= 0 ){

         ch.setIndex(Integer.parseInt(historyTemp.

(jtemp, jtemp + 1)));//取最近的执行步骤的index

String[] jStemp = historyTemp.split(ch.getIndex() + ":");

String sjtemp =  jStemp[jStemp.length- 1];

.setStep(Integer.parseInt(sjtemp.substring(0, sjtemp.indexOf(","))));

     }else {

         cList.remove(ch);

         ic--;

                }

            }

     childNode.setcDNCNodeList(cList);

     ArrayList<IndexTreeNode> dList =  tree.getDDNC(child);

for(int ic = 0; ic < dList.size(); ic++){

         ndexTreeNode ch = dList.get(ic);

         int jtemp = historyTemp.indexOf(ch.getIndex() + ":");

if(jtemp >= 0){

            ch.setIndex(Integer.parseInt(historyTemp.

substring(jtemp, jtemp + 1)));//取最近的执行步骤的index

            String[] jStemp = historyTemp.split(ch.getIndex() + ":");

            String sjtemp =  jStemp[jStemp.length- 1];

            ch.setStep(Integer.parseInt(sjtemp.substring(0, sjtemp.indexOf(","))));

         }else {

            dList.remove(ch);

            ic--;

                }

            }

        childNode.setdDNCNodeList(dList);

j++;

        dncTable.add(childNode);

        }

        return dncTable;

    }

}

三、切片数据集：

public class GetDslice {

    public GetDslice(){

}/ *  Dslice(sk ,v)=accessible(DDNC(sk)) */

publicArrayList<IndexTreeNode> getDsliceNodeList(int index, int step){

       ArrayList<IndexTreeNode>dsliceNodeList=new ArrayList<IndexTreeNode>();

       AccessibleTable accTable = new AccessibleTable();

       // 取得可达语句表

       ArrayList<ArrayList>acciList=accTable.getAccessibleTable();

       GetDNCTable dncTable = new GetDNCTable();

       CharData data = new CharData();

//取得数据依赖节点集 和 控制依赖节点集

       ArrayList<DNCNode>ndcNodeList= dncTable.getDNCNodeList(data.getHistory())//DDNC(sk)

       DNCNode dsliceNode = ndcNodeList.get(step-1);

       ArrayList<IndexTreeNode>ddncList= dsliceNode.getdDNCNodeList();

  for(IndexTreeNode child : ddncList){

       for(Object accChild : acciList.get(child.getStep()-1)){

           dsliceNodeList.add((IndexTreeNode)accChild);

            }

        }//对求出的结果排序

  for(int i = 0; i < dsliceNodeList.size(); i++){

       IndexTreeNode treeNode = dsliceNodeList.get(i);

       for(int j = i + 1; j < dsliceNodeList.size(); j++){

           ndexTreeNode treeNodeTemp = dsliceNodeList.get(j);

           if(treeNode.getIndex() > treeNodeTemp.getIndex()){

              if(j+1 < dsliceNodeList.size() && (treeNode.getIndex() < dsliceNodeList.get(j+1).getIndex())){

                   dsliceNodeList.add(j, treeNode);

                   dsliceNodeList.remove(i);

                   break;

          }else if(j+1 >= dsliceNodeList.size()){

                   dsliceNodeList.add(j+1, treeNode);

                   dsliceNodeList.remove(i);

                   break;

                    }

                }

            }

        }

        return dsliceNodeList;

}

} 

附录B 英文原文

PROGRAM SLICING

Mark Weiser

Computer Science Department

University of Maryland

College Park, MD 20742

 

Abstract

Program slicing is a method used by experienced computer programmers for abstracting from programs. Starting from a subset of a program's behavior, slicing reduces that program to a minimal form which still produces that behavior. The reduced program, called a "slice", is an independent program guaranteed to faithfully represent the original program within the domain of the specified subset of behavior. 

Finding a slice is in general unsolvable. A dataflow algorithm is presented for approximating slices when the behavior subset is specified as the values of a set of variables at a statement. Experimental evidence is presented that these slices are used by programmers during debugging. Experience with two automatic slicing tools is summarized. New measures of program complexity are suggested based on the organization of a program's slices. 

 

KEYWORDS: debugging, program maintenance, software tools, program metrics, human factors, dataflow analysis

 

Introduction

A large computer program is more easily constructed, understood, and maintained when broken into smaller pieces. Several different methods decompose programs during program design, such as information hiding (Parnas 1972), data abstraction (Liskov and Zilles 1975), and HIPO (Stay 1976). These methods are not mutally exclusive, but rather complement one another. Proposed here is another complementary method of program decomposition: program slicing. Unlike most other methods (but see Tarjan and Valdes, 1980), slicing is applied to programs after they are written, and is therefore useful in maintenance rather than design. Unlike design methodologies, working on actual program text allows slicing to be specified pre-cisely and performed automatically.

Slicing starts with the observation that these are times when only a portion of a program's behavior is of interest. For instance, during debugging a subset of Dehavior is being corrected, and in program modification or maintenance a sub- set of behavior is being improved or replaced. In these cases, a programmer starts from the program behavior and proceeds to find and modify the corresponding portions of program code. Code not having to do with behavior of interest is ignored. Gould and Dronkowski k19/4) report programmers behaving this way during debugging, and a further confirming experiment is presented below.

*This research was supported in part by the Computer Science Center at the University of Maryland, and by grants from the Air Force Office of Scientific Research and the General Research Board at the University of Maryland.

A programmer maintaining a large, unfamiliar program would almost have to use this behavior-first approach to the code. Understanding an en- tire system to change only a small piece would take too much time. Since most program maintenance is done by persons other than the program designers, and since 67 percent of programming effort goes into maintenance (Zelkowitz, Shaw, and annon 1979), decomposing programs by behavior must be a common occurence.

Automatic slicing requires that behavior be speclfied in a certain form. If the behavior of interest can be expressed as the values of some sets of variables at some set of statements, then this specification is said to be a slicing criterion. Dataflow analysis (Hecht 1977) can find all the program code which might have influenced the specified behavior, and this code is called a slice of the program. A slice is itself an executable program, whose behavior must be identical to the specified subset of the original program's behavior.

Figure 1 gives examples of some slicing criteria and their corresponding slices.

There are usually many different slices for a given program and slicing criterion, depending on how minimal a slice is desired. The issue of minimality is discussed further below. There is always at least one slice the program itself. The interesting slices are the ones which, compared to the original program, are significantly smaller and simpler.

The idea of isolating portions of programs according to their behavior has appeared previously. Schwartz (1971) hints at such a possibility for a debugging system. Browne and Johnson (1978) describe a question-answerer for Fortran programs.

 

Examples  of  Slices

The ori ginal program:

1 BEGIN

2 READ(X,Y)

3 TUTAL:=0.0

4 SUM:=0.0

5 IF X<=1

6 THEN SUM:=Y

7 ELSE BEGIN

8 READ(Z)

9 TOTAL:=X*Y

10 END

11 WRITE (TOTAL,SUM)

12 END

Slice on the value of Z at statement 12.

     BEGIN

     READ(X,Y)

     IF X<1

      THEN

      ELSE READ(Z)

         END

Slice on the value of X at statement 9.

     BEGIN

     READ(X,Y)

     END

Slice on the value of TOTAL at statement 12.

     BEGIN

     READ(X,Y)

     TOTAL:=0

     IF X<=1

      THEN

      ELSE TOTAL:=X*Y

         END

Figure 1

which, through a succession of questions, could bemade to reveal the slices of a program although very slowly. Several on-line debuggers permit a limited traceback of the location of variable references (e.g. Aygun, 1973), and this information is a kind of "dynamic slice".

Slicing is a source code transformation of a program. Previous work in program transformation has concentrated on preserving program correctnesswhile improving some desirable property of programs. For instance, Baker (1977) and Ashcroft and Manna (1973) both are concerned with adding "good structure" to programs. Wegbreit (1976), Arsac (1979), Gerhart (1975), and Loveman (1977), are more oriented to improving a program's performance.

 

Slicing  Algorithms

This section more formally discusses the ideas of a slicing criterion and a slicing algorithm, using the reader's intuitive understanding of machine execution. All proofs have been carried out in an abstract operational model (Weiser 1979). This paper considers the slicing of block-structured, possibly recursive programs written in a Pascal-like language. All variables are assumed to be uniquely named, and all procedures are assumed to be single-entry, single exit.

The following notation is used throughout this paper. Due to typesetting limitations, square brackets ([...]) are used to enclose superscripted and subscripted quantities. Set notation is expressed as follows. Let A and B denote sets, let f and g be functions whose values are sets, and let C(i) be a finite family of sets indexed by i. Then:

A union B                           denotes the set union of A and B.

A intersect B                         denctes the set intersection of A and B.

f union g                            denotes the function whose value is f(n) union g(n) for each n in the domain of f and g, and is undefined elsewhere.

UNION C(i)                           denotes the union of all C(i) for each i.

A slicing_ criterion for a program specifies a window for observing its behavior. A window is specified as a statement and a set of variables. The window allows the observation of the values of the specified variables just before executing the specified statement. If the statement specified by the slicing criterion is executed several times while the program is running, then a sequence of variable values will be observed.

Identifying statements by numbers and vari-ables by name, a slicing criterion is a pair < i,v>, where i is the number of the statement at which to observe and v is the set of variable values to be observed.

There are two properties intuitively desirable in a slice. First, the slice must have been obtained from the original program by statement deletion. Second, the behavior of the slice must correspond to the behavior of the original program as observed through the window of the slicing criterion. Both of these informal properties allow several interpretations. The interpretation used here is derived and justified in the next several paragraphs.

The problem with obtaining a slice by state-ment deletion is that the source code of a programmay become ungrammatical. For instance, removing

the THEN clause from an IF-THEN-ELSE statement leaves an ungrammatical fragment if the "null" statement is not permitted between THEN and ELSE.Because of their language dependence, detailed consideration of these issues is beyond the scope of this paper. See Arsac (1979) for some approaces. Instead, a flow-graph will be used to represe a program, with each node in the graph correspond ing to a single source language statement. The terms "node" and "statement" will be used inter-changably.

A flow-graph is a structure G = <N,E,n0>, where N is the set of nodes, E is a set of edges in NxN, and n0 is the distinguished initial node. If (n,m) is an edge in E then n is an immediate predecessor of m, and m is an immediate successor of n. A path of length k from n to m is a set of nodes p(0,p(1), .... p(k) such that p(0) : n, p(k) = m, and (p(i), p(i+l))is in E for all i,0 < i < k-l. There is a path from n0 to every other node in N. A node n is nearer than a node m to some node q if the shortest path from n to q has length less than the shortest path from m to q. A node m is dominated by a node n if n is on every path from n0 to m. An inverse dominator is a dominator on the flow-graph obtained by reversing the direction of all edges and making the final node the initial node.

Deleting statements in a flow-graph produces a meaningful new flow-graph so long as any group of statements deleted have only a single successor (see figure 2). This restriction ensures that no statement increases its number of immediate successors as a result of statement deletion. The graph transformation following statement deletion is just: All predecessors of any member of a deleted group of statements have the deleted group's unique successor as their new successor.

Group of statements with a single successor

 

 

 

 

 

 

 

Nodes C,D, and E form a set with a single successor, F, not in the set. The flow-graph is shown before and after removing this set.

Figure  2

The second desirable property of slices is that they duplicate the behavior observable through the window of the slicing criterion. This means observing original program and slice through the "same" window, and not being able to distinguish between them. But how can a slicing criterion for one program (the original) be used to specify a window for a different program (the slice)? A slicing criterion has the form <i,v>. v can be used in both the slice and the original program, of course. However statement number "i" may not even exist in the slice. Therefore, the window for observation of the slice is specified as <SUCC(i),v>. SUCC(i) is the nearest successor to "i" in the original program which is also in the slice, or "i" itself if present. It is easy to prove that SUCC(i) is unique.

The program and its slice now have corresponding windows for observing behavior. A reasonable requirement for a slice might be that the trajectories of behavior observable through the slice window must be identical to that observable through the original program window for all inputs. Unfortunately this condition is too strong, because it implies the unsolvability of finding slices. Consider the following program skeleton:

1 BEGIN

2 READ(X)

3 IF X=0

4    THEN BEGIN

         .

         perform infinite loop

         without changing X.

         .

5   X:=1

6   END

7 ELSE X:=2

8 END

Let the slicing criterion be the value of X at line 8. A slicing algorithm based on equivalent behavior trajectories for all inputs would necessarily include line 5 unless there were some as- surance that for all input line 5 was never reached. Such a slicing algorithm could be used to determine the termination of an arbitrary procedure by suitably inserting that procedure between lines 4 and 5, and then noticing whether or not line 5 appeared in the slice. But there can be no algorithm to determine if an arbitrary procedure must terminate, and hence no such slicer can exist.

To fix this problem, the requirement of equivalent projected behaviors can be weakened to be: projected behaviors must be equivalent whenever the original program terminates. This definition is the one intended in the remainder of this paper whenever the phrase "equivalent behavior" is used.

A similar problem now arises with finding the smallest possible slice. The reader can easily generalize the above example to show that no algorithm can always find the slice with the mini- mum number of statements, because of the impossibility of evaluating the functional quivalence of two different pieces of code. This problem suggests that a practical definition of a minimal slice must avoid exact knowledge of the functions computed by pieces of code. Dataflow information about a program is of this type, and it permits an exact slicing algorithm. The remainder of this section considers the computation of slices from dataflow information alone.

 

附录C英文翻译

摘要

程序切片是有经验的程序员使用的一种方法，用来将程序抽象化。它从一个程序的行为的子集开始，将程序切片减少为能仍旧产生前者行为的最小形式。被缩小后的程序，就成为一个“切片”，它是一个独立的程序，而且能够保证在指定子集行为的领域里完全代表原始程序。

一般来说，找到一个切片是不可能的。一个数据流的运算法则是用来大致估计（当此行为子集作为一个声明中一系列变量的值是明确的）。实验结果表明这些切片由程序员在调试以排除故障时使用，包括了两个自动切片工具的使用经验。程序的复杂性使得人们用新的方法基于组织去对程序进行切片。

关键词：程序调试排除故障 程序维护 软件工具 程序特性 人为因素 数据流分析

简介

一个大型的电脑程序在切分成小片后是容易构造的，易懂的，并且是容易维护的。在程序设计中，一些不同的方法将程序分解，例如信息隐藏（Parnas，1972），数据提取（Liskov和Zilles 1975），和HIPO（Stay 176）。这些方法不是相互独立排斥的，而是相辅相成的。这里所推荐的是另一种补充的程序切片的方法。不像大多数其他的方法（但是看Tarjan 和Valdes，1980），切片适用于那些写好的程序，因此不是为了设计上有用，而是为了维护是有用。不像设计方法论，它作用于实际的程序文档允许切片精确地指定和自动的执行。

切片始于观察法，有时仅有一部分的程序涉及。

*这个研究是支持于马里兰大学的计算研究中心，资助于美国空军研究协会用于科学研究和普通研究伙同马里兰大学。行为是在兴趣下的。比如，当调试排除故障时一个子集的行为正在被修正，在程序修改或维护一个子集行为在改进或替换。在这些情况下，一个程序员从程序行为开始，然后发现和修饰相应部分的程序代码。不相关的代码则被忽略。Gould和Dronkowski（19/4）报道说程序员在调试排错中表现出这种方式，一个论证的实验如下。

一个程序员若第一次接近代码维护大型的不熟悉的程序大多数最可能必须用这种方法。完全理解一个系统去改变只是一个很小的部分，而且它还会花费很多时间。自从大多数软件维护是由其他个人解决而不仅仅是软件设计者。而且67%的精力花在程序维护上（Zelkowitz，Shaw，和Gannon 1979），按行为分解程序必须是一个普通的事件。

自动切片需要的行为必须要有一个固定格式的规定。如果相关行为能用一系列特点下变量的值表达，那么这个规格可以说成为一个分片判据。数据流分析（Hecht 1977）可以找到所有那些影响到规定行为的程序代码，这些代码就被叫做程序的一个切片。一个切片是一个可执行程序，它的行为对与规定子集来说必须是独立的。而且有原始程序的特性。

图1给了一些例子，它们是切片标准和它们相对应的切片。

一个既定程序和切割标准通常有许多不同的切片，这取决于需要多小的切片。这个最小值的问题将在下面进行讨论。但是通常至少又一个切片，这就是程序它本身。有趣的是切片通常比源程序小而且更简单。

这种通过程序特性分离程序部分的想法以前就已经出现过。Schwartz（1971）暗示了这个调试排错系统的可能性。Browne和Johnson（1978）为公式翻译程序描述了这样一个问题解答器。

切片举例

原始程序：

1 BEGIN

2 READ(X,Y)

3 TUTAL:=0.0

4 SUM:=0.0

5 IF X<=1

6 THEN SUM:=Y

7 ELSE BEGIN

8 READ(Z)

9 TOTAL:=X*Y

10 END

11 WRITE (TOTAL,SUM)

12 END

Slice on the value of Z at statement 12.

     BEGIN

     READ(X,Y)

     IF X<1

      THEN

      ELSE READ(Z)

         END

Slice on the value of X at statement 9.

     BEGIN

     READ(X,Y)

     END

Slice on the value of TOTAL at statement 12.

     BEGIN

     READ(X,Y)

     TOTAL:=0

     IF X<=1

      THEN

      ELSE TOTAL:=X*Y

         END

Figure 1

通过一系列问题反映程序切片，虽然比较慢。一些在线调试排错程序允许变量有限的回溯，这种信息是动态切片。

切片时一个程序源码的翻译的过程。先前程序转化的工作重在保持源程序的正确性的同时改进程序。举一个实例，Baker（1977）、Ashcroft和Manna（1973）都考虑加入一些好结构到成血中去。Wegbreit（1976），Arsac（1979），Gerhart（1975），和Loveman（1977）使之更适应程序，改进程序的性能。

 

切片法则

这部分更正式的讨论了切片标准和规则，利用读者对机器运行的只觉得理解。已经在一个提炼操作模型里得到了所有的数据。

本论文认为切片的块结构，尤其像Pascal一类语言便携的递归的程序。所有的变量有唯一的名称，所有的程序上有单一的出口。以下的注释全文都有使用。由于种类设置的局限性方法，围绕在上标或者下表上使用方括号。标记如下表示。让A和B表示为集合，让f和g设为是变量的集合，设C(i)是有i的属性的有穷集合。那么：

A union B                           表示A和B的并集

A intersect B                         表示A和B的交集

f union g                 表示每个f(n)和g(n)的n的并集，并且没有在任何地方定义

UNION C(i)                           表示所有每个i的C(i)的并集

 

一个切片程序的分割标准决定了观察它行为的视窗。一个视窗被视为一个节点和一系列变量。视窗允许在执行特定变量的值。当程序运行时，如果程序准则的声明规定在执行了数次，那么一系列的变量值可以被观察到。

根据数字和变量的名称识别状态标识，一个切片准则是一组<i,v>，i是要观察的原有状态的序号，v是要观察的一系列不同的变量的值。

在一个切片里有两个内容让人直观上满意。首先，切片必须从原始程序里删除得到，切片的行为必须和通过切片标准视窗观察到的原始程序一致。这两个非正式内容可以有不同的理解。此处作用的理解方法可以由下面几段得到和验证。

通过语句的删除获取到一个切片的方法存在的问题便是这种方式下的源代码也许会成为不符合语法规则的。例如，如果在THEN和ELSE之间“空”语句是不允许的，从一个IF-THEN-ELSE语句中去除THEN子句就会留下一个不符合语法规则的碎片。因为他们语言的依赖，这些争议的详细考虑已经超出了这篇论文的范围。参考Arsac（1979）来获取一些方法。取而代之的是，一个流程图将会用来反应一个程序，在图中的没一个节点对应一个单独的语言表述来源。这个“节点”和“表述”将会互换。

一个流程图是这样一个结构G=<N,E,n0>,这里N代表一系列的节点，E是一系列NxN图的边，n0是最初的节点的区别。如果(n,m)是E中的一条边，n是m的一个直接原有项，m是一个n的直接原有项。一条由n到m的路径的长k就是一系列的节点p(0), p(1)….. p(k)就像p(0)=n, p(k)=m，并且（p(i),p(i+1)）是在E中的，对于所有的i，0<i<k-1。在N中，有一条从n0开始到任意其它节点的路径。如果由n到q的最短路径的长度比m 到q的最短长度还短，那么节点n就比节点m离即节点q进。如果你是在每一条由n0到m的路径中的，那么节点m是由节点n控制的。一个相反的控制者是一个控制者在流程图中通过颠倒所有变的方向并且使最终节点变为最初节点获取的。

只要删除任何一组的语句将只有一个继承物，在一个流程图里删除语句生成一个有意义的新流程图。这个限制确保了删除语句之后语句数量不会增加，语句删除后图转化如下：所有被删除的语句只有一个前项作为新的继承者。一个单独继承者伴随着很多组语句 

 

节点C，D和E由一个单独的继承者的集合而来，F，并不在集合中。这个流程图向我们展示了在移除集合前后的情况。

第二个令人满意的特性是它们复制了通过切片标准视窗可观察的行为，这意味着在同一个窗口中查看原始程序和切片的程序，而不能将它们区分开来。但是一个程序（原始程序）的切片标准怎么能用来指定另一个不同程序的视窗呢（切片的）？一个切片准则有形式<i,v>,v可以同时用在切片和程序里，然而，语句序号i可能在切片里不存在。因此，观察窗口被指定为<SUCC(i),v> SUCC(i)是同时存在于程序和切片里最近的继承者，或者有就是i自己。证明SUCC(i)是独一无二的是非常容易的。

这个程序和它的切片现在有相应的窗口用来观察它们的行为。对于一个切片，一个合理的需求可能通过切片窗口是可以观察到它的行为轨迹，它们必须和观察到的原始程序窗口中所有的输入相一致。不幸的是这种情况是太强大,因为它意味着找到切片是不可行的。考虑到以下程序的纲要：

9 BEGIN

10 READ(X)

11 IF X=0

12    THEN BEGIN

         .

         perform infinite loop

         without changing X.

         .

13   X:=1

14   END

15 ELSE X:=2

16 END

把第8行中的切割标准设为值x，一个基于所有的输入程序都相等的切片规则，必须包含第5行，除非保证第5行的输入程序永远无法完成。通过合理输入第4行和第5行，并注意第5行是否出现在切片中，这样的切片规则可以用来发现并终止一个任意的程序。但是如果一个任意的程序必须终止，不能没有规则的去判定，因此，这样的一个切片是不存在的。

要想解决这个问题，等价的计划行为可以减弱为:无论何时原始的程序终止，计划行为必须是一致的。无论何时“等价的行为”短语被使用，这个定义在本篇论文意指在剩余物中。

一个类似的问题现在出现在寻找最小可能的切片中。读者可以很容易的概括以上的例子来说明没有运算法则经常可以找到最小数量的语句的切片，因为评估两个不同的程序片段的功能的一致性是不可能的。关于一个程序数据流信息是这个类型的，而且它允许一个精确的切片运算法则。这个部分剩余物考虑了数据流信息独立的切片的估算。 

 

附录D

一、 程序切片相关知识理解与掌握：

动态程序切片根据程序的输入，从源程序删除零条或多条语句，得到对最终结果有潜在影响的源序子集 ，可用于程序调试、程序理解、软件测试和软件维护等方面。

程序切片是一种代码分析技术 ，它从语义角度对程序进行分解， 根据切片准则，识别源代码中影响已知点变量值的所有语句 ，基本程序切片可分为静态切片和动态切片，静态切片不需执行程序，即可找到影响变量值的语句；而动态切片依赖程序的特定输入 ，保留对最终结果有影响的语句 ，通过运行动态程序切片，有助于缩小错误的范围 。

基本概念：

    定义1：程序控制流图是一个有向图，用G=（N，A，s，e）表示，其中N是节点集，节点表示语句；A是边集，边表示语句间可能的控制流向；s是唯一的源结点，对应程序的开始语句；e是唯一的汇结点，对应程序的终止语句。从结点s到某结点kn的路径是语句序列T=,其中n=s，n=k且n（1i<q），（，） 。若存在输入数据使某一条路径可执行，则称该路径是可达的。；一个程序的状态迹是对某特定输入数据而实际执行的可达路径。语句X在状态迹中的位置p处可表示为（X，p），记为。

定义2：设T是程序P对输入x的状态迹，P的动态切片准则表示为一个三元组C=（x，，V），其中x是P的输入，I是状态迹T中第q个元素的状态迹符号；V是程序P的变量子集。

定义3：设C=(x,,V)是程序P的动态切片准则，T是P对输入x的状态迹，C上P的动态切片是满足如下条件的一个可执行程序：

 1、删除P中零条或者若干条语句可得到P；

2、若P对输入x可终止执行且状态迹w为T，则对输入x也可终止执行且状态迹为 ，且存在相应执行位置，使T中值与中相等。

定义4：一个变量在程序中的某处出现，使之与该变量相绑定的内容被引用，则称该出现是引用性的出现，形式定义为：。

一个变量在程序中的某处出现使数据与该变量相绑定，则称该出现是定义性出现，形式定义为：

 

算法：

1，给定一个程序p切片准则，生成其状态迹T；

2，确定 DU、TC、IR 关系；

3，定义 是在执行位置q，V中变量最后定义集，LT（）是对 有TC关系的测试控制集；

4，定义 ，其中 ，对   项中，将最后得到的最为切片  ；

5，通过反复计算产生 作为序列的极限（  ）；

6，对于 中所有的 ，切片包括语句X和切片准则中的语句I。

至此得到所需切片如Ⅰ：

 

  

 

 

 

 

         

1 read（n）

2 i=1

3 while(i<=n) do

begin

4       if(i mod 2=0) then

5           x=17

else Ⅰ

6          x=18

endif

7        i=i+1

     end

8  write(x)  

以上程序对输入n=2的执行过程状态迹T=<1,2,3,4,6,7,3,4,5,7,3,8>，如：Ⅱ

read（n）

i=1

i<=n

i mod 2=0

x=18

i=i+1 Ⅱ

i<=n

i mod 2=0

x=17

i=i+1

i<=n

write(x)  

构造DU、TC、IR关系：

1，DU关系描述一个行为为一个数据项分配一个值，其他行为引用该值，即将一个变量的引用和其最后定义联系起来，在上述第二个执行语句中： DU=

2，TC关系描述测试行为以及其影响执行的行为间的关系，即将一个逻辑表达式的最新出现和控制依赖于其上的状态迹中出现的语句联系起来。如上述第二个执行语句中  影响 的执行，但不影响的执行，影响他们的是  。在上述第二个执行语句中：

TC=

3，IR关系描述出现的相同语句。在第二个执行语句中：

IR=

在程序Ⅰ中切片准则（2，，x）为计算切片  ，首先找到对 有直接影响的所有行为集  ，因x=17对 write(x)有直接影响，所以LD（8，{x}）={}，LT（）=，从而={}， 反复计算产生作为序列 的极限（）。在语句Ⅱ中：

LD(8,{x})={},LT()=

={}, ={}

={,},=(,,)

={},={}

={},={}

=

至此停止计算，得到的切片为

={}={}

至此停止计算，得到的切片 为：

1  read（n）

2   i=1

3   while(i<=n) do

begin

4     if(I mod 2=0) then

5       x=17

endif

7      i=i+1

  end

8  write(x)

二、下步的工作计划： 

在理解了和掌握了程序切片的相关知识之后，接下来的根据任务书的要求，理解动态程序切片的方法，初步设计一个具有动态切片功能的程序分析系统， 最终采用面向对象可视化语言编程实现上述系统，进行性能测试，并分析测。

三、存在的问题：

    对算法的理解可能还不够准确，需要在后面的工作中随时加强对算法的理解，以保证系统实现，编写程序工作的顺利进行。