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

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

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

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

一种面向对象程序的过程间切片算法

程序切片是一种程序分析技术，它通过把程序减少到只包含与某个特定计算相关的那些语句来分析程序，过程间切片作为图形可达性问题时，需要扩展过程内切片所用的程序依赖图（PDG）成系统依赖图（SDG），然后利用两阶段图形可达性算法计算比较精确的切片，目前程序切片技术的研究以面向对象程序切片为主，文中讨论了一种合适面向对象程序的分层切片方法，并综合分层切片方法和两阶段图形可达性算法提出了一种简化的计算面向对象程序过程间切片的算法。     

快速自动程序流分析方法研究

介绍一种自动程序流信息分析方法,使用静态单赋值简化程序切片中的数据依赖关系,利用简单快速程序切片算法删除对循环控制无影响的语句和控制谓词,利用抽象解释自动精确获得程序流信息。实验结果表明,在不失精度的情况下,该方法的分析速度较普通方法快了近25%,且未假定任何程序格式,适用于任何程序格式的流分析过程。     

基于程序切片的测试用例生成系统研究与实现

介绍了一种基于程序行为切片的测试用例生成系统的实现方案,系统在不扫描全部程序路径的情况下,生成可以覆盖全部程序行为的测试用例集。系统分为静态分析、动态符号执行以及测试用例生成3个模块。在静态分析模块中根据输入的程序代码分析程序的控制流和信息流,提取程序的控制依赖和数据依赖,并计算程序的潜在依赖;动态符号执行模块求解约束条件、生成测试用例和分析代码执行过程;测试用例生成模块根据执行路径和依赖关系计算被路径覆盖的程序行为切片和未被覆盖的程序行为切片,然后根据未被覆盖的程序行为切片,引导符号执行生成能覆盖新的程序行为切片的测试用例。实验证明,本系统生成的测试用例集可以保证覆盖所有的程序行为,同时能显著减少生成的测试用例数量。     

一种包含异常传播的类间数据依赖分析方法

类间数据依赖分析是类间数据流测试的基础。本文通过分析类簇级测试中的异常传播对程序数据依赖的影响,提出一种包括异常结构在内的类间C++程序数据依赖分析方法,根据类间关系增量式地构造类间数据依赖图,并给出类间数据依赖图的构造算法。最后,在程序切片中应用了该数据依赖分析方法。结果证明,该方法通过分析异常传播对数据依赖的影响能够带来切片精度的提高。     

用于程序开发的改进的有条件切片算法

为了加速软件开发,提高软件质量,本文针对开发过程提出了一种改进的有条件切片算法.该算法改造了程序控制流程图,扩充了程序数据依赖定义,按照条件切片的一阶逻辑谓词缩减目标程序,并用扩充后的数据依赖计算有务件程序切片.在程序编码阶段,该算法能够抽取需要关注的代码段给开发人员,并能利用边的信息计算出程序的路径数目.从而为开发人员发现软件缺陷、冗余提供了有利的支撑.     

Slithice:一个基于系统依赖图的Java程序切片工具

当前程序切片的相关理论已经较为成熟,但针对Java程序的静态切片工具却非常少见。为便于展开切片应用研究,设计并实现了一个基于系统依赖图的Eclipse切片插件——Slithice。该插件支持不同粒度的底层分析和系统依赖图构建,从而可以使切片算法能够在精度和性能之间进行权衡,适应各种规模程序的分析需要。     

基于关键谓词的程序错误定位方法

将程序切片技术应用于程序错误定位可以大量减少需要测试的语句数。提出一种基于关键谓词的程序错误定位方法,从程序中找出能影响输出结果的关键谓词,对该谓词和错误输出语句进行数据切片,并引入代码优先技术。该方法考虑了数据依赖和控制依赖,能实现准确快速的错误定位。     

基于抽象解释理论的循环边界计算方法

在实时系统的应用中常常需要对系统的执行时间,尤其是最坏执行时间进行分析。而程序中的循环结构的迭代次数对程序执行时间的分析结果具有重要的影响。程序的循环边界分析目的在于给出较为接近程序真实运行情况下的循环结构迭代的上界和下界。提出了一种基于抽象解释理论的程序循环边界计算方法,该方法对原有的循环边界分析方法进行了改进。首先在程序切片阶段对原程序建立程序依赖图,并提出了对程序依赖图的约简方法。由约简后的依赖关系可以对变量的取值进行约束,得到更小的取值范围,因此基于该方法的循环边界分析结果更加接近程序的实际执行边界,对获取精确的程序执行时间具有重要意义。     

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.     

Dynamic slicing of concurrent specification languages

Dynamic slicing is a technique to extract the part of the program (called slice) that influences or is influenced, in a particular execution, by a given point of interest in the source code (called slicing criterion). Since a single execution is considered, the technique often uses a trace of this execution to analyze data and control dependencies. In this work we present the first formulation and implementation of dynamic slicing in the context of CSP. Most of the ideas presented can be directly applied to other concurrent specification languages such as Promela or CCS, but we center the discussion and the implementation on CSP. We base our technique on a new data structure to represent CSP computations called track. A track is a data structure which represents the sequence of expressions that have been evaluated during the computation, and moreover, it is labeled with the location of these expressions in the specification. The implementation of a dynamic slicer for CSP is useful for debugging, program comprehension, and program specialization, and it is also interesting from a theoretical perspective because CSP introduces difficulties such as heavy concurrency and non-determinism, synchronizations, frequent absence of data dependence, etc.     

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.     

并发程序切片原型系统的设计与实现

并发程序切片是并发程序分析的一种重要手段。针对多线程共享变量通信机制,在通过程序分析工具CodeSurfer获取程序基本信息的基础上构造程序可达图,生成以程序状态和语句二元组为节点的并发程序依赖图,实现了基于程序可达图的并发程序切片原型系统。初步实验结果表明,与传统的切片方法相比,采用基于程序可达图的并发程序切片方法,可有效地解决依赖关系不可传递问题,获得高精度的并发程序切片。     

Compiler Techniques for the Superthreaded Architectures1, 2

Several useful compiler and program transformation techniques for the superthreaded architectures are presented in this paper. The superthreaded architecture adopts a thread pipelining execution model to facilitate runtime data dependence checking between threads, and to maximize thread overlap to enhance concurrency. In this paper, we present some important program transformation techniques to facilitate concurrent execution among threads, and to manage critical system resources such as the memory buffers effectively. We evaluate the effectiveness of those program transformation techniques by applying them manually on several benchmark programs, and using a trace-driven, cycle-by-cycle superthreaded processor simulator. The simulation results show that a superthreaded processor can achieve promising speedup for most of the benchmark programs.     

一种基于模块单子语义的动态程序切片方法

提出一种基于程序模块单子语义的新动态切片方法--模块单子动态切片.首先通过单子转换器,将切片这一类计算抽象成独立于具体语言的实体：切片单子转换器.然后,将该切片转换器作为模块加载到实际程序中,并给出相应的模块单子动态切片算法.据此,可直接在抽象语法结构上计算动态切片,不必记录程序执行历史;相应单子切片器也无需显式地构造诸如依赖图的中间结构.这种模块化抽象机制使得文中的动态切片算法具有很强的可扩展性和重用性.     

Characterizing minimal semantics-preserving slices of function-linear, free, liberal program schemas

A program schema defines a class of programs, all of which have identical statement structure, but whose functions and predicates may differ. A schema thus defines an entire class of programs according to how its symbols are interpreted. As defined in this paper, a slice of a schema is obtained from a schema by deleting some of its statements. We prove that given a schema S which is function-linear, free and liberal, and a slicing criterion defined by the final value of a given variable after execution of any program defined by S, the minimal slice of S which respects this slicing criterion contains only the symbols ‘needed’ by the variable according to the data dependence and control dependence relations used in program slicing, which is the symbol set given by Weiser’s static slicing algorithm. Thus this algorithm gives minimal slices for programs representable by function-linear, free, liberal schemas. We also prove a similar result with termination behaviour used as a slicing criterion. This strengthens a recent result, in which S was required to be linear, free and liberal, and termination behaviour as a slicing criterion was not considered.     

热路径结合程序切片思想在错误定位中的应用

回归测试指对修改后的软件进行测试.为提高回归测试错误分析效率,基于目前热路径思想在程序分析里的应用,结合程序切片方法,提出一种高效的回归测试方法.首先找出在程序执行过程中方法级的执行路径频率,结合应用Dslice切片算法应用用于回归测试,对已知的错误的程序进行调试,比较准确地进行了方法级的错误定位.实验结果表明通过热路...     

Program Slicing:Its Improved Algorithm and Application in Verification

Program slicing is a method for automatical program decomposition.This paper presents an improvedslicing algorithm on the basis of static analysis of the control structure of loop statements.The slice obtainedby the new algorithm is guaranteed to be no larger than that obtained by the previous slicing algorithmdeveloped by Mark Weiser.Moreover,the former will be much smaller than the latter for certain kinds ofprograms.In addition,a brief discussion of using slicing in program verification has been given for the sakeof extending the application area of program slicing.