一种JAVA语言的程序分片技术

论文分类号：TP31单位代码10183密级：内部研究生学号2001532091吉林大学硕士学位论文一种JAVA语言的程序分片技术ATechniqueofProgramSlicingBasedonJAVA作者姓名：潘海燕专业：计算机应用技术导师姓名张长海及职称教授论文起止年月：2002年10月至2004年4月提要程序分片是一种程序抽取技术，它对于程序理解、程序分析和软件工程等领域有很重要的作用。自从程序分片被提出以后，一直是人们研究的重点，针对它的方法也有很多。目前程序分片的重点已经转移到针对不同的语言的分片技术，以及程序分片形式的多样化中。但是由于各种语言的机制不同，分片的技术也不相同。针对面向对象语言的分片还没有很完整的方法，工具更少。同时条件分片是新提出地概念，它的技术还不是很成熟，特别是国内对这方面的研究还很少。我们研究了针对JAVA语言的静态分片技术以及条件分片技术。静态分片技术是在已有的方法基础上进行了改进，基本实现了面向对象语言的特殊机制。条件分片技术是我们下一步研究的重点，在本文中我们提出了类似于部分求值技术的方法，并给出了形式化的描述。两种分片技术通过结合，可以得到条件分片的结果。本文提出了JAVA语言的静态分片和条件分片算法，实践表明这些技术是可行的，它为进一步研究JAVA语言的异常和多线程以及条件分片奠定了基础。目录-1-目录第一章前言..............................................................11．1程序分片.............................................................11．2程序分片技术的发展史.......................................11．3程序分片的分类..................................................11．4程序分片的应用..................................................41．5研究的现状.........................................................41．6预备知识.............................................................61．7本文完成的工作...................................................7第二章程序分片方法.........................................................92．1数据流等式方法..................................................92．2图的可达性方法................................................102．3面向对象的分片................................................10第三章条件分片..............................................................113．1条件分片的概念................................................113．2条件分片的应用................................................113．3条件分片的方法................................................12第四章JAVA语言的静态分片系统实现方法..................134．1JAVA语言的静态分片准则................................134．2系统采用的方法................................................13第五章条件分片算法.......................................................285．1JAVA语言的条件分片分析方法.......................28目录-2-5．2预备知识.........................................................285．3采用的技术.......................................................315．4具体处理...........................................................335．5条件方法的实现................................................34第六章JAVA语言的分片实现........................................366．1处理的语言........................................................366．2实现环境............................................................366．3数据结构............................................................366．4分片算法...........................................................416．5依赖图到分片后程序的转换..............................466．6今后的工作.......................................................47结束语...........................................................................48附录............................................................................49参考文献...........................................................................52致谢中文摘要Abstract前言前-1-第一章前言1．1程序分片程序分片技术（programslicing）是很重要的技术，它的应用很广泛，主要应用到软件维护、程序调试、测试、代码理解以及逆向工程等领域。程序分片技术最早应用到程序调试中，在调试的时候，当错误特征出现时，我们希望能够通过一种手段，找到可能产生该错误的源代码部分。我们或许不能对这样的源代码准确定位，但我们可以做到通过剔除程序中不可能产生该错误的部分，而把错误限定在一个较小的范围中。程序分片就是一种有效实现上述目的的技术。1．2程序分片技术的发展史程序分片（programslicing）这一概念最早是由MarkWeiser[11]在1979年提出，此后出现了许多略有不同的定义以及用于计算分片的算法。大体上说，程序分片技术的发展经历了从静态到动态、从前向到后向、从单一过程到多个过程、从非分布程序到分布式程序等几个阶段。SHorwitz[2]等人给出的程序分片定义是：“一个程序分片是由程序中的一些语句和判定表达式组成的集合。这些语句和判定表达式可能会影响在程序的某个位置（常用行号标识）p上所定义的或所使用的变量v的值。（p，v）称为分片准则（slicingcriterion）”1．3程序分片的分类静态分片技术（staticslicing）静态分片技术是指在计算程序分片时使用的是静态的数据流和控制流分析方法。该技术对程序的输入不做任何假设，所做的分析完全以程序的静态信息为依据。使用该技术的工作量较大，因为要分析程序所有可能的执行轨迹，所以相对于动态分片技术，静态分片技术一般用于程序理解与软件维护方面。Weiser最初提出的程序分片概念就属于静态分片范畴。图1是一段决定前言前-2-三边长的代码，准则为r的静态分片请参见图1（a），静态分片结果即是程序本身。动态分片技术（dynamicslicing）动态分片技术使用的是动态的数据流和控制流分析方法，因此分片的计算过程依赖于程序的具体输入。采用这一技术，每一次的计算工作量较小，但每一次的计算都不尽相同，因此动态分片技术多用于程序调试、测试方面。请参见图1（b）。条件分片（conditionedslicing）目前对程序的理解主要有两种方法：静态分析或者是动态分析。但这两种方法都有些过于极端，前者对程序的理解只局限于对程序源代码的分析，获得的是静态信息，过于片面；后者对程序的理解则以程序多次运行的测试结果为基础，这些测试结果随着触发程序运转的外界输入的不同而不同，又过于复杂。CanforaCimile和Lucia于1998年提出的条件分片技术避免了上述两个极端。Canfora等人提出的条件分片技术通过增加一个条件扩展了传统的静态分片准则。在进行条件分片算法时，只有满足该分片条件的那些输入才会被分析。这个条件对应着程序的某个或某些初始状态。可以看出，条件分片是一种施加了一定条件的动态分片。如果存在从满足分片条件的任一个初始状态出发都不可能被执行的语句，那么把这些语句去除掉后，就得到了在这个分片条件下的程序分片，即条件分片。请参见图１中（c）。前言前-3-图1静态分片，动态分片和条件分片的比较左图（a）为静态分片示例，中图（b）为动态分片，右图（c）为条件分片示例Canfora等人提出的条件是一种正向的条件，而2001年CbrisFox等人提出的条件则是一种逆向的条件。在生成逆向条件分片时，去除的是那些执行不可能导致一个满足分片条件的程序状态的语句。CbrisFox等人结合正向和逆向条件这两个概念，进一步提出了前提/后继条件分片技术（pre/postconditionedslicing）。该技术在去除语句时采用如下的标准：当程序从一个满足前提条件的初始状态出发，遇到一些语句，这些语句的执行不可能导致后继条件的否命题为真，那么这些语句应该被去除。如果一个程序正确的满足分片的前提和后继条件，那么使用该技术就能去除影响程序行为的语句，而留下那些错误或者是无关的语句，后者往往是使用传统分片技术无法检测到的。无定型切片技术（amorphousslicing）如果在程序调试领域应用程序分片技术，为了使得到的程序分片包含那些可能引起错误的语句，在去除语句时就必须施加一定的约束。显然，这些约束是必要的，因为它们剔除了那些执行不影响p处所切变量v的值的语句，从而使调试者都能够在一个较小的范围内有效地发现并且修改错误现在的问题是:这种约束if(a==b)If(a==c)r=’equilateral’;elseif(a=c)r=’isosceles’;elseif(b==c)r=’isosceles’;elser=’scalene’;if(a==b)if(a==c)r=’equilateral’;if(a==b)if(a==c)r=’equilateral’;elseif(a=c)r=’isosceles’;elseif(b==c)r=’isosceles’;原始动态分片：a=b=c=1条件分片：a=b∨a=c∨b=c前言前-4-在程序理解领域是否过于苛刻？MHarman和SDanicic发现了程序理解领域，这些约束可以被适当放宽。他们于1997年提出了无定型分片的概念。这种分片技术继承了传统分片技术在简化源程序的过程中保留源程序语义的功能，唯一不同