一种基于Java程序分层模型的方法内切片生成算法

程序切片作为软件理解领域的一种重要的分析技术,可以将程序分解为独立的程序线程。系统依赖图的概念及两阶段图形可达性算法的出现,则有效解决了程序切片的过程调用问题。文章介绍了程序切片的基本概念,并给出了在面向对象程序中进行静态分层切片的思想。作为分层切片思想的应用,文章给出了在一种Java程序切片工具模型JSTM(JavaSlicingToolsModel)中运用系统依赖图进行方法内切片的具体算法。     

一种面向对象程序的分层切片方法

程序切片是一种程序分析技术,广泛应用于程序的调试、测试、理解和维护等软件开发的各个阶段.在研究静态类型面向对象的程序切片时发现,利用系统依赖图计算程序切片虽然是一种有效的方法,但构造OO程序的系统依赖图是一件非常复杂的工作,而且构造过程中容易出错,这会导致切片的结果不正确,造成前功尽弃.为此,从程序逻辑分层的角度提出一种OO程序的层次模型,然后在OO程序的层次模型基础上采用逐步求精算法来分层计算OO程序的切片.     

基于逆向程序流和函数依赖集的程序切片算法

程序切片技术大多是根据程序依赖图(PDG)和系统依赖图(SDG)的图可达性算法来优化得到感兴趣的程序集合,但是构造PDG和SDG需要很大的空间开销。本文提出一种基于逆向程序流和函数依赖集的切片算法,从兴趣点开始扫描逆向程序流来计算程序切片,只计算与切片相关的数据依赖,并且考虑函数调用时切片的计算,提高计算切片的效率。通过实例表明该算法减少了计算程序切片的复杂度,具有一定的可行性和实用性。     

一种基于逆向程序流的程序切片算法*

传统的程序切片方法一般基于程序依赖图(PDG)和系统依赖图(SDG)的可达性算法,但是在建立PDG和SDG的过程中会计算一些与切片无关的数据依赖,造成时空资源的浪费及切片效率的降低。提出了一种基于程序逆向流的切片算法,它事先建立逆向程序流,再从切片点开始沿逆向程序流扫描程序以获得程序切片,只计算与切片相关的数据依赖,从而提高了切片计算的时空效率。通过实验发现该算法具有一定的可行性和实用性。本算法适用于包括Fortran、C等编程语言在内的命令式程序的切片生成。     

一个分层切片工具模型

程序切片技术在程序调试、测试、程序理解、逆向工程和软件维护等方面有着广泛的应用。程序切片是一组可能影响到在程序中某个点i的某个变量v的值的语句或谓词的集合。而(v,i)被称作切片准则。这里v也可以是一组变量。自从Mark Weiser提出切片的概念,随着程序依赖图、系统依赖图的出现,传统程序的切片技术已走向成熟。1994年以来,面向对象的程序切片逐渐成为研究的主流。A.Krishnaswamy利用一种面向对象的程序依赖图(OPDG,Object-Ori-ented Program Dependence Graph)来计算面向对象程序的语句切片,但是OPDG不能表示动态绑定等问题。D.Liang,L.D.Larsen和M.J.Harrold扩展系统依赖图来计算面向对象程序的切片,在一定程度上解决了动态绑定和对象参数的问题。这些切片方法都是基于依赖图的,而构造OO程序的依赖图是一件非常复杂的工作,而且构造过程中容易出错,这会导致切片的结果不正确,造成前功尽弃。李必信提出了分层切片的思想,利用逐步求精的方法来得到面向对象程序的切片。     

一种JAVA程序静态切片的方法

JAVA语言是目前一种主要的面向对象编程语言,由于JAVA语言复杂的结构,使得对JAVA程序进行程序切片非常困难.本文提出一种层次的构造JAVA系统依赖图的算法,基于JAVA程序本身的层次结构,自顶向下构造系统依赖图,然后基于构造的系统依赖图,用一种改进的两阶段算法得到JAVA程序切片.     

对象级粗粒度切片方法

基于面向对象程序的对象间语义级关系,提出了一种对象级粗粒度切片方法,用于解决以往传统程序切片构造过程复杂,切片结构庞大,可理解性不强等问题.该方法并非基于传统的程序依赖图或系统依赖图,而是建立在对象间的关联、组合等语义级关系的基础之上.依据对象间语义级关系构造程序的对象图,在对象图的基础上获取程序的前向对象级粗粒度切片和后向对象级粗粒度切片,并结合了对象间的组合关系使得所得后向对象级粗粒度切片更加精简.     

一种C++程序的分层切片方法

该文介绍了一种C++程序的分层切片方法。通过构造系统程序层依赖图、类层依赖图、方法层依赖图和语句层依赖图,对C++程序进行分层切片,有效地表示了C++中的单重继承、多重继承、多态和动态绑定,该方法比其它C++切片技术更清晰地描述了C++程序中类之间的各种关系和消息传递机制。     

基于简化系统依赖图的静态粗粒度切片方法

基于系统依赖图是计算面向对象程序切片的一个有效方法.但是,系统依赖图的缺点是太复杂,而且在建立系统依赖图的过程中容易出错,一旦出现错误就可能导致切片结果的不准确.通过对系统依赖图进行简化,得到了简化的系统依赖图.它省略了那些表示输入参数和输出参数的结点和概括边.同时,还定义了一种面向对象程序的粗粒度切片概念,讨论了它的性质,分析了它与细粒度切片的关系,并基于简化的系统依赖图计算面向对象程序的粗粒度切片.最后还讨论了切片技术的简单实现.     

扩展有限状态机EFSM的后向切片

切片是一种重要的约减技术，基于代码的程序切片已经得到广泛的研究和大量的应用，但基于规格和模型的切片研究不多．EFSM是一种重要的规格模型，将切片技术引入EFSM对于分析和测试基于EFSM的软件模型具有重要的作用．由于一个实际的EFSM相当复杂，导致对EFSM模型的分析和修改非常困难．EFSM的切片对于测试和分析EFSM模型具有重要意义．由于EFSM依赖关系的特殊性，依赖图的可达性问题对于EFSM依赖图中并不是一个简单的图可达性问题．而且现有的基于标志已访问节点的遍历算法不适于解决该问题．对EFSM的依赖关系的传递性进行了详细的讨论和分析，定义了一个递归的依赖传递函数来描述变迁的影响如何通过依赖关系传递，而计算后向切片则可以通过逆依赖传递函数来描述，最后给出一个基于变迁的EFSM后向切片算法．     

Dynamic slicing of concurrent AspectJ programs: An explicit context‐sensitive approach

This paper presents a context‐sensitive dynamic slicing technique for the concurrent and aspectized programs. To effectively represent the concurrent aspect‐oriented programs, we propose an intermediate graph called the multithreaded aspect‐oriented dependence graph (MAODG). The MAODG is a dynamic graph generated from the execution trace of a given program with respect to a particular set of values given as an input. Interference dependencies between the statements are shown by a distinguished edge called the interference dependence edge in the MAODG. Based on this intermediate representation, we propose a precise and accurate dynamic slicing algorithm for the concurrent aspect‐oriented programs implemented using AspectJ. The proposed dynamic slicing algorithm is implemented in a slicing tool developed using the ASM framework. Several open source programs are studied and evaluated using the proposed technique along with some existing techniques. The experimentation shows that our proposed slicing algorithm generates slices of the same or smaller size, as compared with the existing algorithms. Furthermore, we found that the slice computation time is significantly less in our proposed algorithm, as compared with the existing algorithms.     

Precise slicing of interprocedural concurrent programs

Program slicing is an effective technique for analyzing concurrent programs. However, when a conventional closure-based slicing algorithmfor sequential programs is applied to a concurrent interprocedural program, the slice is usually imprecise owing to the intransitivity of interference dependence. Interference dependence arises when a statement uses a variable defined in another statement executed concurrently. In this study, we propose a global dependence analysis approach based on a program reachability graph, and construct a novel dependence graph calledmarking-statement dependence graph (MSDG), in which each vertex is a 2-tuple of program state and statement. In contrast to the conventional program dependence graph where the vertex is a statement, the dependence relation in MSDG is transitive. When traversing MSDG, a precise slice will be obtained. To enhance the slicing efficiency without loss of precision, our slicing algorithm adopts a hybrid strategy. The procedures containing interaction statements between threads are inlined and sliced by the slicing algorithm based on program reachability graphs while allowing other procedures to be sliced as sequential programs. We have implemented our algorithm and three other representative slicing algorithms, and conducted an empirical study on concurrent Java programs. The experimental results show that our algorithm computes more precise slices than the other algorithms. Using partial-order reduction techniques, which are effective for reducing the size of a program reachability graph without loss of precision, our algorithm is optimized, thereby improving its performance to some extent.     

SymPas: Symbolic Program Slicing

Program slicing is a technique for simplifying programs by focusing on selected aspects of their behavior.Current mainstream static slicing methods operate on dependence graph PDG (program dependence graph) or SDG (system dependence graph),but these friendly graph representations may be a bit expensive for some users.In this paper we attempt to study a light-weight approach of static program slicing,called Symbolic Program Slicing (SymPas),which works as a dataflow analysis on LLVM (low-level virtual machine).In our SymPas approach,slices are stored in symbolic forms,not in procedures being re-analyzed (cf.procedure summaries).Instead of re-analyzing a procedure multiple times to find its slices for each callling context,we calculate a single symbolic slice which can be instantiated at call sites avoiding re-analysis;SymPas is implemented with LLVM to perform slicing on LLVM intermediate representation (IR).For comparison,we systematically adapt IFDS (interprocedural finite distributive subset) analysis and the SDG-based slicing method (SDG-IFDS) to statically slice IR programs.Evaluated on open-source and benchmark programs,our backward SymPas shows a factor-of-6 reduction in time cost and a factor-of-4 reduction in space cost,compared with backward SDG-IFDS,thus being more efficient.In addition,the result shows that after studying slices from 66 programs,ranging up to 336800 IR instructions in size,SymPas is highly size-scalable.     

面向方面程序的简化动态依赖图切片方法

程序切片是一种重要的程序分析技术,广泛应用于程序的调试、测试与维护等领域。面向方面程序设计作为一种新的软件开发范型,能够实现横切关注点的模块化,其特有的语言元素和功能为切片增加了难度。从静态切片和动态切片两种类型,讨论了面向方面程序切片技术。在此基础上,提出了一种基于简化动态依赖图的面向方面程序切片方法,可以减少动态依赖图中节点和边的数量,生成准确的面向方面程序的动态切片,从而有助于人们更好地对面向方面程序进行分析和理解。     

并发程序的切片模型检验方法

提出了一种对并发程序进行切片以缩减模型检验状态空间的方法，首先针对并发程序中的同步与通信定义了一组依赖关系，包括并发分支与接合．非确定性，信道，共享变量等特征，对于从要验证的时态逻辑性质中提取的关于多个程序点的切片标准，文中给出算法根据相应的依赖关系通过不动点运算得到并发程序切片，可以证明得到的切片与原程序对于该性质具有相同的可满足性。     

一种改进的并发程序静态切片算法

分析了Krinke切片算法对循环体内嵌套有线程的程序结构会产生切片不精确的现象，认为其原因是该算法对线程间数据依赖的定义过于粗糙，且对程序行为约束不够。该文提出一种新算法，在并发程序内部表示中，增加跨线程边界循环-承载数据依赖，并引入区域化执行证据约束程序行为。实例研究表明，该算法克服了Krinke算法的不精确现象。     

基于ISDG的面向对象程序分片技术研究

程序分片是一种有效的程序分析技术，它能根据给定的分片准则从源程序中提取出所需部分进行分析，如进行程序调试、测试、程序重构分析等。程序分片技术在结构化程序中已有较广泛的应用，但对于面向对象语言程序，其研究与应用还存在一些待解决的问题。针对面向对象语言程序，提出了一种改进后的系统依赖图：ISDG，用来更好地表示面向对象程序中的依赖关系，从而解决了对象类型参数和属性的表示问题。基于ISDG模型，提出了一种新的面向对象语言程序的分片准则，以度相应的分片算法。