程序动态切片技术研究

毕 业 设 计（论 文）程序动态切片技术研究专业年级： 07级计算机2班 学 号： 0706010234 姓 名： 惠军绪 指导教师： 邹 阳 评 阅 人： 2011年6月中国 南京摘 要程序切片技术是一种重要的程序分析技术，广泛应用于程序的调试、测试与维护等领域。程序切片主要通过寻找程序内部的相关特性，从而分解程序，然后对分解所得的程序切片进行分析研究，以此达到对整个程序理解和认识的目的。而动态程序切片主要是指在某个给定输入的条件下，源程序执行路径上所有对程序某条语句或兴趣点上的变量有影响的语句。面向对象技术仍是目前软件开发方法的主流，其中封装、继承、多态、并发等特征都为程序的理解与分析提出了新的问题。本文在程序的分析评测中引入使用基于依赖图的程序切片技术，实现其切片功能，解决在程序理解、程序复杂性度量、程序转换和评测中遇到的问题。本文采用一种基于依赖图的面向对象的动态程序切片方法,核心算法是以静态程序的程序依赖图为基础，先从程序依赖图里提取出对应给定执行历史的数据依赖节点和控制依赖节点，使用图可达性算法，计算得出可达语句集，从而获得所需的动态切片，对程序进行理解分析。【关键词】：数据依赖、控制依赖、程序依赖图、程序切片、动态切片AbstractProgram 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.朗读显示对应的拉丁字符的拼音朗读显示对应的拉丁字符的拼音字典翻译以下任意网站 Arte Toreo-西班牙语 Zeit Online-德语 Philadelphia Inquirer-美国 Los Angeles Times-美国 News.de-德语 The Washington Post-美国 G1 Globo-巴西 Spiegel Online-德语 OneIndia-印地语 USA Today-美国 Venezuela Tuya-西班牙语 Vogue-法国【Key words】：DD,CD,PDG,Program Slicing,Dynamic Slicing目 录摘 要IAbstractII第一章 绪 论1第一节 课题研究目的和意义1第二节 研究内容和本文结构1第二章 程序切片技术3第一节 程序切片技术的概述3第二节 切片技术的应用5第三章 动态程序切片技术7第一节 动态切片法产生的背景及现有算法7第二节 动态程序切片实现算法8第四章 动态程序切片系统设计14第一节 系统概要设计14第二节 详细设计16第三节 实例分析24第五章 系统的实现环境和运行结果的分析29第一节 开发与运行环境29第二节 系统输出29第六章 结束语32第一节 本文的主要工作32第二节 展望32致谢33参考文献34附录35附录A核心代码35附录B 英文原文41附录C英文翻译49附录D河海大学毕业设计（论文）中期进展报告56 第一章 绪 论第一节 课题研究目的和意义软件危机曾经是软件界甚至整个计算机界最热门的话题为了解决这场危机，软件从业人员、专家和学者做出了大量的努力。现在人们已经逐步认识到所谓的软件危机实际上仅是一种状况，那就是软件中存在故障，正是这些故障导致了软件开发在成本、进度和质量上的失控。故障是软件的属性，而且是无法改变的，因为软件是由人来编写的，所有由人做的工作都不会是完美无缺的。软件测试就是“为了发现故障而执行程序的过程”，其根本目的就是尽可能地消除软件中的故障，使得软件在正式投入使用之前，软件中的故障密度达到尽可能低或者可以接受的程度。软件测试是软件生命周期中的重要一环，在当前的软件开发过程中发挥着越来越重要的作用。统计表明，在典型的软件开发项目中，软件测试工作量往往占软件开发总工作量的40%以上;在软件开发的总成本中，用在测试上的开销要占到50%左右。软件测试的实质是根据软件开发各阶段的规格说明和程序的内部结构精心选取一批测试数据，形成测试用例，并用这些测试用例去驱动被测程序，观察程序的执行结果，验证实际运行结果与期望结果是否一致，然后做相应的调整。可见，测试数据生成是软件测试的核心与关键。白盒测试(结构测试)一般是根据被测程序的内部结构设计测试用例，具有很强的理论基础。这种结构测试要求对被测程序的结构特性做到一定程度的覆盖。路径覆盖是一种相对比较强的覆盖标准，要求生成足够多的测试数据，尽可能覆盖所有程序路径。但是，实际中往往会出现这样的情况：多个测试用例执行的是同一条程序路径，而有的程序路径则从未被执行过。因此，探讨一种有效的手段，以辅助基于路径的测试数据生成，有着很现实的意义。第二节 研究内容和本文结构本文在理解M.Weiser的切片算法的基础上，根据H.Agrawai等人提出的基于静态程序依赖图的算法，编写程序，最终实现切片系统。并对程序切片进行测试分析。本文的第一章简要介绍本课题研究的背景、意义以及关于切片系统的实现目标；第二章主要介绍程序切片的技术概述和应用发展；第三章则是动态程序切片的具体算法设计；第四章关于动态程序切片系统设计的介绍；第五章则是本系统的开发环境和运行结果分析；第六章则是对本文的总结以及展望。第二章 程序切片技术第一节 程序切片技术的概述程序切片技术是M.Weiser在他的1979年的博士论文中首次提出的一种程序分解技术。主要通过寻找程序内部的相关特性，从而分解程序，然后对分解所得的程序切片进行分析研究，以此达到对整个程序理解和认识的目的。后来在1981年和1984年，M.Weiser博士又发表了两篇论文对这种技术进行推广和完善。后来切片技术引起了研究者们广泛的关注，由于它起到了其他技术无可替代的作用，因此可以说是程序分解领域的一场大变革，无论在程序的分析和理解、调试还是测试和维护过程都起到了巨大的作用，另外切片技术还在硬件描述语言和其他规约语言以及形式化模型等方面的分析有至关重要的作用，因此它的研究具有极其重要的理论和实际意义。M.Weiser博士首先在1979年定义了程序切片的概念:程序中的某个输出只与这个程序的部分相关语句以及控制谓词有关系，因此如果删除其他的语句或者控制谓词将对这个输出没有任何影响。也就是说，对于一个特定的输出，源程序和对于删除不相关的语句和控制谓词后所得的程序是作用相同的。其形式化定义如下:把满足如下两个条件的切片称为M.Weiser切片:第一，一个程序切片需要对应一个切片准则，用表示，其中n指程序中的某个兴趣点，一般指一条语句，V表示在这条语句使用的变量的集合。第二，程序P的切片s可以通过在P中删除零条或者多条语句后得到，且保证程序P和所得的切片S关于切片准则的作用是相同的。当时，M.Weiser博士把只与某个输出相关联的语句和控制谓词构成的程序称之为源程序的静态切片。由此可见，一个程序的切片大多数是源程序的一个子集，这个概念准确的说其实就是程序切片的一个核心思想。后来随着研究的发展，研究者们对M.Weiser博士程序切片的概念进行了扩展，由于程序切片不一定都是可执行的，因此又包含了不可执行的切片思想，这也是一种静态切片，这样就丰富和发展了程序切片的内涵。随后，Korel和Laski又提出了动态切片的概念，它只考虑程序的某个特定执行情况，程序中的信息如数组、指针和循环依赖关系都可以在程序执行时动态确定。因此，动态切片与静态切片相比结果更加的准确。基于数据流方程的切片阶段基于依赖图的程序切片阶段面向对象的程序切片阶段程序切片变体阶段在程序切片技术二十几年的发展过程中主要经历了如图2.1所示的四个阶段：图2.1 程序切片技术的发展历程第一个阶段是基于数据流方程的切片阶段，这其实就是M.Weiser博士提出切片概念的阶段，主要使用了基于控制流图的数据流方程来计算程序切片。第二个阶段是基于依赖图的程序切片阶段，这一阶段产生了对程序切片提出了很多新的概念和算法。首先，Ottenstein等人在提出了基于程序依赖图的图可达性算法，并可以计算过程内后向程序切片，接着又提出了前向切片的概念和算法，以及基于依赖图的两步遍历图的可达性算法。最后Korel和Laski提出了动态切片的概念和算法。等人首次使用类依赖图来扩展系统依赖图，从而表示面向对象的c+程序，并通过改进的两步遍历图可达性算法来计算程序的切片。随后Christon Steindl在1999年通过对各种数据流以及控制流的计算，提出了面向对象程序切片计算的解决方法，起到了很重要的作用。最后一个阶段是程序切片变体阶段，这一阶段出现了各种程序切片的变体形式，例如砍片、削片、层次切片等等，这些都极大地促进了程序切片技术的迅速发展。通过上面程序切片的发展阶段可以看出程序切片有很多种，主要有静态切片和动态切片，前向切片和后向切片，规约切片，削片，砍片，无定型切片等等。这些种类其实本质都是一致的，也是随着发展阶段一步步演化而来的。由于本文主要使用到动态切片，因此这里主要对与之相关的静态切片和动态切片以及前向切片和后向切片作简要介绍。后文中将详细分析动态切片。如果在计算程序切片时不考虑程序的具体输入，计算对某个感兴趣点影响的语句和谓词集合，这样得到的切片就是静态切片。其切片准则为。如果在计算程序切片时考虑程序的某个具体输入，然后计算程序P在这个特定输入。的条件下所有影响V在n点的值的语句和谓词集合，这样得到的切片就是动态切片。其切片准则为。后向切片是指构造一个集合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，Entry表示子程序的入口，Exit表示子程序的出口，程序从入口节点Entry到nk的节点序列是一条执行路径，其中n1为入口Entry节点， E，1 i k。定义3:DEF:在CFG中节点n定义变量的集合，记为DEFn。定义4:USE:在CFG中节点n使用变量的集合，记为USEnl。定义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)= thenaccessible()=accessible() DDNC() CDNC() For v V do If vUse(s) thenDslice(，v)=accessible(DDNC()End forElseaccessible()=accessible() DDNC() CDNC()if Cyd()= and accessible()=accessible()then =Cyd ()else if accessible(Pre()= =accessible()then Pre()=Pre()For v V do vUse(s) thenDslice(，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 程序结构图动态切片程序系统的切片准则用一个三元组表示，其中x表示程序的输入，p表示程序中一条语句，V表示程序中的变量。切片结果包含了当前输入下所有影响p点的V变量值的语句。该系统对程序的处理大致如下：(1)对于输入的源程序进行代码格式化，以获取符合我们要求的程序；(2)对格式化后的用改造后的编译器执行，以此得到程序的执行记录；(3)对格式化后的程序进行静态分析，并利用获取的执行记录，生成动态系统依赖图；(4)在动态系统依赖图的基础上，根据切片准则，进行切片；(5)将切片的中间结果还原为程序形式。以下对于每个子系统进行简单介绍：代码格式器：由于输入的程序各式各样，很多并不符合系统的输入要求，所以要有一部分专门来处理程序的输入，使之符合系统要求并输出合格源程序，因此定制这个部分来进行系统处理，这部分主要的功能是去除源程序空格，空行，分别不规范写法等。并在下一步，程序编译处理之前做预处理动作，一方面极大的降低编译处理的复杂度，另一方面也可以使得编译处理更加规范化，方便和其他系统进行集成。程序编译处理器：程序编译处理是本功能中比较重点的子系统，因为这里的输出直接影响到一下步执行顺序的生成。而且由于编译器的复杂性，所以这里不应该承担太多的功能，因此，这里的实现原则应该为最简化处理，即：只负责源程序执行顺序的输出，不再进行任何其他功能处理。所以，本文在这里将外围功能均由第一个子系统中的代码格式器承担。程序分析处理器：这部分主要负责对源程序进行分析，包括找出类中变量定义，类定义。函数定义等，分析各语句之间的依赖关系，包括数据依赖和控制依赖，通过这些分析结果，就可以得到程序依赖图。这里也是比较重要的一部分。这里的结果将会影响到程序依赖图的生成。切片生成器：切片生成器是得到切片的核心部分，前面几个子系统都是在为这里的切片生成器做数据准备和预处理动作。它运用前一章节提到的算法，把他们用程序逻辑去实现，最后得到切片结果。它的输入包括依赖图的定义，执行历史顺序，源程序。它的输出应该是包含源程序的一种数据结构的表示。切片表示器：切片生成器得到的结果是动态系统依赖图上的一些节点的数据结构表示，所以我们需要把它还原成源程序，用直观、简洁的方式将程序切片展现出来。具体的方法是利用语句的标号和源程序之间的关系得到原来的程序。因为标号是唯一的，利用这个中间的表示，我们就可以在源程序中找到切出来的语句。系统实现难点：这个系统中有三个部分比较难于实现，分别是：程序编译处理器，程序分析处理器，和切片表示器。程序编译处理器涉及Java程序的编译处理。由于一般的优秀的商业编译处理器都无法得知源码进行改造，所以这里会尽量使用开源编译器。程序分析处理器和编译处理器一样，一般在编译处理器中都会有实现。这里要实现相应的功能，也可用开源来实现。在这里我采用JavaCC这个开源的程序编译器和分析处理器。第二节 详细设计由前几章的算法以及上面根要设计的分析可得，整个系统实现主要分为以下几个部分：第一部分：读取输入：读取输入包括源程序读取输入以及程序切片准则输入。第二部分：程序编译处理：读取源程序后，采用JavaCC进行程序编译，根据切片准则以及源程序生成程序执行历史顺序。第三部分：程序分析处理：读取源程序，进行采用JavaCC进行程序分析每个节点的数据依赖和控制依赖。1、基本语句控制依赖分析语句是程序的基本组成单位，语句间的控制依赖关系在语法分析过程中就可以确定。顺序执行语句：此类语句的执行结果不会影响程序的执行流程，如变量声明语句、赋值语句等，此类语句中无谓词出现，不存在控制依赖。if语句：如图所示，语句1执行与否，取决于if语句的执行结果，语句1控制依赖于if语句（语句1不一定是一条语句，可能是一个语句块，此情况下，语句1语句块中所有语句控制依赖于if语句）。If语句语句1是否If语句语句1图4.2 if语句的流程图和控制流图if-else语句：如图所示，语句2控制依赖于if语句，实际上语句1也是控制依赖于if语句，为了后面切片过程的方便，我们看作语句1控制依赖于else语句，else语句控制依赖于if语句。If-else语句语句1语句2假真If-else语句语句1语句2图4.3 if-else语句的流程图和控制流图while语句：如图所示，语句1控制依赖于while语句。While语句语句1真假While语句语句1语句2真假图4.4 while语句的流程图和控制流图for语句：同while语句情况相似。Switch语句语句 1语句2语句 n.case 1case ncase 2Switch语句语句 1语句2语句 n.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。从对面向对象程序类的依赖性分析，我们可以利用如下的算法得到数据依赖图：数据依赖图的建立算法：（1） 对于函数内所有的执行记录中出现的语句，分别建立语句节点；（2） 对于图中的语句节点S1、S2，如果S1数据依赖于S2，则以数据依赖边连接S1、S2。图4.6 数据依赖子图的建立算法第四部分：程序数据依赖节点集（DDNC）控制依赖节点集（CDNC）：由上述算法和程序动态数据依赖图可以得到输入程序的数据依赖节点集（DDNC）以及控制依赖节点集（CDNC）。动态程序切片的依赖图是基于程序的执行历史的，在第三部分得到了各个节点的控制依赖和数据依赖子图之后，将其根据算法建立源程序的动态语句依赖图和相应的数据依赖节点集（DDNC）/控制依赖节点集（CDNC）。动态语句依赖图的建立算法：（1） 对于函数中的所有语句，确定控制依赖关系，找到语句的控制前驱。（2） 对于数据依赖图中的所有节点，添加其控制前驱语句对应的语句节点，并以控制依赖边该语句及其控制依赖前驱节点。图4.7 动态语句依赖图的建立算法本文旨在研究动态程序切片的求解过程，程序依赖图的的求解并非重点，所以在切片系统中默认程序依赖图已经给出。所以需要一个程序引用的常量类，用来代表源程序常量数据，所有的源程序常量以及所需的输入数据（如切片准则，源程序内容等），均由此处定义。程序文件CharData用于实现这个功能。这里显示部分源码：public class CharData private static int history = null; private static ArrayList 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 TreeData = new ArrayList();TreeData 这个ArrayList定义了依赖图的数据结构，为了能更好的表示依赖图，为此定义了一个元数据结构，给出TreeChild元数据结构：ArrayList parents = new ArrayList();private Object data;private ArrayList children = new ArrayList();private ArrayList typeList = new ArrayList();parents 、children、typeList 三个ArrayList分别定义了依赖图一个节点的父级节点、子级节点、以级子级节点所对应的类型。父节点子节点子节点依赖属性.依赖属性依赖属性子节点程序运行节点的数据结构表示如下图：图4.8 程序运行节点的数据结构在图4.8中，每个运行节点都包含N个子节点，其中每个依赖子节点都有其子节点依赖属性其中对每个子节点的依赖类型都做了标注，节点的依赖类型对应该子节点顺序。这样就可以把整个依赖图表示为一个ArrayList结构，其中每个节点都为一个ArrayList，节点的数据结构为多个子结点和节点控制类型组成。源程序节点1源程序节点n源程序节点2节点1节点2节点n节点1节点n节点n子节点1子节点n子节点n子节点n子节点属性1子节点属性n子节点属性n子节点属性n图4.9 程序依赖图的数据结构整个程序依赖图的数据结构可表示为图4.9，其中每个依赖图内都包含N个源程序节点，每个源程序节点下面又包含N（n=0）个依赖子节点，其中每个依赖子节点都有其子节点属性。第五部分：程序可达语句集：由第四部分的DDNC和以及公式accessible()=accessible()+NNDC()+CNDC()可以得到程序的可达语句集。可达语句集数据结构如下图：可达语句1DNCnode元数据1nodeindexdDNCnodelistnodestepcDNCnodelistnodeindexnodeindexnodeindexnodestepnodestepnodestepdDNCnodelistdDNCnodelistdDNCnodelistcDNCnodelistcDNCnodelistcDNCnodelistDNCnode元数据nDNCnode元数据n+1DNCnode元数据2可达语句n.图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 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() - 10 - 1); accessibleChildList.add(indexNode);第六部分：程序的切片集：由第五部分的程序可达语句集和公式：Dslice(，v)=accessible(DDNC()可以得到程序的切片集合。在前面的模块中已经求出了相应的可达语句表，根据求取切片的公式进而求出程序切片。而ShowTest 是整个系统的入口，也是由这里得到具体的程序切片。这个类中只有一个主方法，用来调用程序，得到切片。 第三节 实例分析因为在算法的主要功能是在确定的源程序的的基础上，给定一个输入即某条语句的动态切片准则(，v，)以及源程序的程序依赖图，求出数据依赖节点集、控制依赖节点集，进而求出可到达语句最后输出的变量v的动态切片Dslice(，v)。而不去考虑如何去具体求出源程序的程序依赖图。所以，本文将选取一个具有代表性的程序，进行具体分析，进而通过动态切片系统求出切片。源程序如下： elseS6: x=18 endifS7: i=i+1endS8: write(x)S1: read(n)S2: i=1S3: while(i=n) do beginS4: if(i mod 2 = 0)thenS5: x=17 图4.11 源程序输入n=2；切片标准：（，v=x，n=2）；程序依赖图：S1: read(n)S2: i=1S3: while(i=n) doS4: if(i mod 2 = 0) S5: x=17 S6: x=18 S7: i=i+1S8: write(x)控制依赖边：数据依赖边： 图4.12 程序依赖图输入n=2，程序的执行历史为。由源程序、程序依赖图和执行历史可得：数据依赖节点集（DDNC）控制依赖节点集（CDNC）如下：表4.1 数据依赖/控制依赖节点集节点（）DDNC（）CDNC（）、然后由上表和公式accessible()=accessible()+NNDC()+CNDC()可得每个节点的可达语句如下：表4.2 可达语句集初始化可达语句accessible()11accessible()22accessible()31,2,3accessible()41,2,3,4accessible()61,2,3,4,6accessible()71，2,3,7accessible()31,2,3,7accessible()41,2,3,4,7accessible()51,2,3,4,5，7accessible()71,2,3,4,7accessible()31,2,3,4,7accessible()81,2,3,4,5，7，8由于本程序带有循环结构，所以选择程序第一次执行还没有出现循环前的节点作为新的切片标准（，v，），此时，n=2.此时的执行历史为。这时节点的切片Dslice(,v)=accessible(DDNC()，根据语句可达表，可知accessible(DDNC()=accessible（）=。（1） 若accessible()=accessible()，则就将，合并。由此可得，没有可以合并的节点。（2） 如果s的直接前驱节点的可到达语句与s的可到达语句相等，就把s和s的前驱节点合并，即合并s和其前驱节点的可到达语句。 、可合并 、可合并。表4.3 各个节点程序切片节点Dslice()初始化1,21,2,3、1，2，3，4，5，7由此可得到切片标准为为（，v=x，n=2）时的切片为即：S1: read(n)S2: i=1S3: while(i=n) do beginS4: if(i mod 2 = 0)thenS5: x=17 endifS7: i=i+1 End图4.13 最终生成的切片第五章 系统的实现环境和运行结果的分析第一节 开发与运行环境本系统的开发在配置为2.00GHz，2.00G RAM的PC上完成；软件环境是Windows xp，使用JDK _17、MySQL 5.1.43、JAVA语言在MyEclipse 7.5下完成。JDK、MySQL、MyEclipse的安装文件分别可以从其官方网站、 JAVA_HOME，设置为C:Program FilesJavajdk_17（JDK的安装路径）；（3）新建PATH，设置为C:Program FilesJavajdk1.6.0_17bin；（4）新建 CLASSPATH，设置为C:Program FilesJavajdk1.6.0_17lib。本系统的测试与开发在同一台PC、