《程序动态切片技术研究》由会员分享，可在线阅读，更多相关《程序动态切片技术研究（64页珍藏版）》请在金锄头文库上搜索。
1、毕 业 设 计（论 文）程序动态切片技术研究专业年级： 07级计算机2班 学 号： 0706010234 姓 名： 惠军绪 指导教师： 邹 阳 评 阅 人： 2011年6月中国 南京 / 摘 要程序切片技术是一种重要的程序分析技术，广泛应用于程序的调试、测试与维护等领域。程序切片主要通过寻找程序内部的相关特性，从而分解程序，然后对分解所得的程序切片进行分析研究，以此达到对整个程序理解和认识的目的。而动态程序切片主要是指在某个给定输入的条件下，源程序执行路径上所有对程序某条语句或兴趣点上的变量有影响的语句。面向对象技术仍是目前软件开发方法的主流，其中封装、继承、多态、并发等特征都为程序的理解与分
2、析提出了新的问题。本文在程序的分析评测中引入使用基于依赖图的程序切片技术，实现其切片功能，解决在程序理解、程序复杂性度量、程序转换和评测中遇到的问题。本文采用一种基于依赖图的面向对象的动态程序切片方法,核心算法是以静态程序的程序依赖图为基础，先从程序依赖图里提取出对应给定执行历史的数据依赖节点和控制依赖节点，使用图可达性算法，计算得出可达语句集，从而获得所需的动态切片，对程序进行理解分析。【关键词】：数据依赖、控制依赖、程序依赖图、程序切片、动态切片AbstractProgram slicing is an important program analysis techniques, wide
3、ly 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 aw
4、areness 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, inherit
5、ance, 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
6、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 prog
7、ram 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.朗读显示对应
8、的拉丁字符的拼音朗读显示对应的拉丁字符的拼音字典翻译以下任意网站 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第一
9、章 绪 论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河海大学毕业设计（论文）中期
10、进展报告56 第一章 绪 论第一节 课题研究目的和意义软件危机曾经是软件界甚至整个计算机界最热门的话题为了解决这场危机，软件从业人员、专家和学者做出了大量的努力。现在人们已经逐步认识到所谓的软件危机实际上仅是一种状况，那就是软件中存在故障，正是这些故障导致了软件开发在成本、进度和质量上的失控。故障是软件的属性，而且是无法改变的，因为软件是由人来编写的，所有由人做的工作都不会是完美无缺的。软件测试就是“为了发现故障而执行程序的过程”，其根本目的就是尽可能地消除软件中的故障，使得软件在正式投入使用之前，软件中的故障密度达到尽可能低或者可以接受的程度。软件测试是软件生命周期中的重要一环，在当前的软件
11、开发过程中发挥着越来越重要的作用。统计表明，在典型的软件开发项目中，软件测试工作量往往占软件开发总工作量的40%以上;在软件开发的总成本中，用在测试上的开销要占到50%左右。软件测试的实质是根据软件开发各阶段的规格说明和程序的内部结构精心选取一批测试数据，形成测试用例，并用这些测试用例去驱动被测程序，观察程序的执行结果，验证实际运行结果与期望结果是否一致，然后做相应的调整。可见，测试数据生成是软件测试的核心与关键。白盒测试(结构测试)一般是根据被测程序的内部结构设计测试用例，具有很强的理论基础。这种结构测试要求对被测程序的结构特性做到一定程度的覆盖。路径覆盖是一种相对比较强的覆盖标准，要求生成
12、足够多的测试数据，尽可能覆盖所有程序路径。但是，实际中往往会出现这样的情况：多个测试用例执行的是同一条程序路径，而有的程序路径则从未被执行过。因此，探讨一种有效的手段，以辅助基于路径的测试数据生成，有着很现实的意义。第二节 研究内容和本文结构本文在理解M.Weiser的切片算法的基础上，根据H.Agrawai等人提出的基于静态程序依赖图的算法，编写程序，最终实现切片系统。并对程序切片进行测试分析。本文的第一章简要介绍本课题研究的背景、意义以及关于切片系统的实现目标；第二章主要介绍程序切片的技术概述和应用发展；第三章则是动态程序切片的具体算法设计；第四章关于动态程序切片系统设计的介绍；第五章则是
13、本系统的开发环境和运行结果分析；第六章则是对本文的总结以及展望。第二章 程序切片技术第一节 程序切片技术的概述程序切片技术是M.Weiser在他的1979年的博士论文中首次提出的一种程序分解技术。主要通过寻找程序内部的相关特性，从而分解程序，然后对分解所得的程序切片进行分析研究，以此达到对整个程序理解和认识的目的。后来在1981年和1984年，M.Weiser博士又发表了两篇论文对这种技术进行推广和完善。后来切片技术引起了研究者们广泛的关注，由于它起到了其他技术无可替代的作用，因此可以说是程序分解领域的一场大变革，无论在程序的分析和理解、调试还是测试和维护过程都起到了巨大的作用，另外切片技术还
14、在硬件描述语言和其他规约语言以及形式化模型等方面的分析有至关重要的作用，因此它的研究具有极其重要的理论和实际意义。M.Weiser博士首先在1979年定义了程序切片的概念:程序中的某个输出只与这个程序的部分相关语句以及控制谓词有关系，因此如果删除其他的语句或者控制谓词将对这个输出没有任何影响。也就是说，对于一个特定的输出，源程序和对于删除不相关的语句和控制谓词后所得的程序是作用相同的。其形式化定义如下:把满足如下两个条件的切片称为M.Weiser切片:第一，一个程序切片需要对应一个切片准则，用表示，其中n指程序中的某个兴趣点，一般指一条语句，V表示在这条语句使用的变量的集合。第二，程序P的切片
15、s可以通过在P中删除零条或者多条语句后得到，且保证程序P和所得的切片S关于切片准则的作用是相同的。当时，M.Weiser博士把只与某个输出相关联的语句和控制谓词构成的程序称之为源程序的静态切片。由此可见，一个程序的切片大多数是源程序的一个子集，这个概念准确的说其实就是程序切片的一个核心思想。后来随着研究的发展，研究者们对M.Weiser博士程序切片的概念进行了扩展，由于程序切片不一定都是可执行的，因此又包含了不可执行的切片思想，这也是一种静态切片，这样就丰富和发展了程序切片的内涵。随后，Korel和Laski又提出了动态切片的概念，它只考虑程序的某个特定执行情况，程序中的信息如数组、指针和循环依赖关系都可以在程序执行时动态确定。因此，动态切片与静态切片相比结果更加的准确。基于数据流方程的
