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.     

一种基于规范和程序域分析的软件测试方法

虽然软件规范规定了输入变量的定义域(功能域)，但程序实现本身也定义了其定义域(运行域)．如果二者不能完全重合，那么某些软件故障就可检测出来．为此，提出了一种基于规范和程序域分析的软件测试方法，介绍了一个运行域自动确定系统ADSOD，并讨论了边界测试数据的选取原则．对特殊表达式，采用程序切片技术，构造基于表达式的可执行模块，通过执行该模块，识别其输入变量的奇异值，进而确定其输入变量的取值范围．通过分析功能域和运行域的边界测试数据集，检测二者的重合性，并根据其分析结果产生测试用例．实验表明：所提方法产生的测试用例，可以有效地提高测试效率．     

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

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

Partial Order Trace Analyzer (POTA) for Distributed Programs

Checking the correctness of software is a growing challenge. In this paper, we present a prototype implementation of Partial Order Trace Analyzer (POTA), a tool for checking execution traces of both message passing and shared memory programs using temporal logic. So far runtime verification tools have used the total order model of an execution trace, whereas POTA uses a partial order model. The partial order model enables us to capture possibly exponential number of interleavings and, in turn, this allows us to find bugs that are not found using a total order model. However, verification in partial order model suffers from the state explosion problem – the number of possible global states in a program increases exponentially with the number of processes.POTA employs an effective abstraction technique called computation slicing. A slice of a computation (execution trace) with respect to a predicate is the computation with the least number of global states that contains all global states of the original computation for which the predicate evaluates to true. The advantage of this technique is that, it mitigates the state explosion problem by reasoning only on the part of the global state space that is of interest. In POTA, we implement computing slicing algorithms for temporal logic predicates from a subset of CTL. The overall complexity of evaluating a predicate in this logic upon using computation slicing becomes polynomial in the number of processes compared to exponential without slicing.We illustrate the effectiveness of our techniques in POTA on several test cases such as the General Inter-ORB Protocol (GIOP)[18] and the primary secondary protocol[32]. POTA also contains a module that translates execution traces to Promela[16] (input language SPIN). This module enables us to compare our results on execution traces with SPIN. In some cases, we were able to verify traces with 250 processes compared to only 10 processes using SPIN.     

Dynamic slicing of lazy functional programs based on redex trails

Tracing computations is a widely used methodology for program debugging. Lazy languages, however, pose new demands on tracing techniques because following the actual trace of a computation is generally useless. Typically, tracers for lazy languages rely on the construction of a redex trail, a graph that stores the reductions performed in a computation. While tracing provides a significant help for locating bugs, the task still remains complex. A well-known debugging technique for imperative programs is based on dynamic slicing, a method for finding the program statements that influence the computation of a value for a specific program input. In this work, we introduce a novel technique for dynamic slicing in first-order lazy functional languages. Rather than starting from scratch, our technique relies on (a slight extension of) redex trails. We provide a notion of dynamic slice and introduce a method to compute it from the redex trail of a computation. We also sketch the extension of our technique to deal with a functional logic language. A clear advantage of our proposal is that one can enhance existing tracers with slicing capabilities with a modest implementation effort, since the same data structure (the redex trail) can be used for both tracing and slicing.     

An efficient dynamic program slicing technique

An important application of the dynamic program slicing technique is program debugging. In applications such as interactive debugging, the dynamic slicing algorithm needs to be efficient. In this context, we propose a new dynamic program slicing technique that is more efficient than the related algorithms reported in the literature. We use the program dependence graph as an intermediate program representation, and modify it by introducing the concepts of stable and unstable edges. Our algorithm is based on marking and unmarking the unstable edges as and when the dependences arise and cease during run-time. We call this algorithm edge-marking algorithm. After an execution of a node x, an unstable edge (x, y) is marked if the node x uses the value of the variable defined at node y. A marked unstable edge (x, y) is unmarked after an execution of a node z if the nodes y and z define the same variable var, and the value of var computed at the node y does not affect the present value of var defined at the node z. We show that our algorithm is more time and space efficient than the existing ones. The worst case space complexity of our algorithm is O(n²), where n is the number of statements in the program. We also briefly discuss an implementation of our algorithm.     

用Z形式化描述程序切片

程序切片是一种重要技术,已广泛地应用于软件工程的各个领域,如程序理解、维护、调试、测试、复用、度量等.虽然,越来越多的研究者致力于程序切片工作,然而由于缺少形式化方面的工作导致程序切片可能存在不一致性和模糊性.本文尝试着用Z语言来形式化描述程序切片,考虑了程序切片中诸如程序依赖图和程序切片算法等常用的方面.该形式化描述不仅能帮助人们正确地理解程序切片的含义,而且还能够从比较严格的意义上明确程序切片的应用领域.     

A system for debugging via online tracing and dynamic slicing

Dynamic slicing is a promising trace based technique that helps programmers in the process of debugging. In order to debug a failed run, dynamic slicing requires the dynamic dependence graph (DDG) information for that particular run. The two major challenges involved in utilizing dynamic slicing as a debugging technique are the efficient computation of the DDG and the efficient computation of the dynamic slice, given the DDG. In this paper, we present an efficient debugger, which first computes the DDG efficiently while the program is executing; dynamic slicing is later performed efficiently on the computed DDG, on demand. To minimize program slowdown during the online computation of DDG, we make the design decision of not outputting the computed dependencies to a file, instead, storing them in memory in a specially allocated fixed size circular buffer. The size of the buffer limits the length of the execution history that can be stored. To maximize the execution history that can be maintained, we introduce optimizations to eliminate the storage of most of the generated dependencies, at the same time ensuring that those that are stored are sufficient to capture the bug. Experiments conducted on CPU‐intensive programs show that our optimizations are able to reduce the trace rate from 16 to 0.8 bytes per executed instruction. This enables us to store the dependence trace history for a window of 20 million executed instructions in a 16‐MB buffer. Our debugger is also very efficient, yielding slicing times of around a second, and only slowing down the execution of the program by a factor of 19 during the online tracing step. Using recently proposed architectural support for monitoring, we are also able to handle multithreaded programs running on multicore processors. Copyright © 2011 John Wiley & Sons, Ltd.     

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

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

CONSIT: a fully automated conditioned program slicer

Conditioned slicing is a source code extraction technique. The extraction is performed with respect to a slicing criterion which contains a set of variables and conditions of interest. Conditioned slicing removes the parts of the original program which cannot affect the variables at the point of interest, when the conditions are satisfied. This produces a conditioned slice, which preserves the behaviour of the original with respect to the slicing criterion. Conditioned slicing has applications in source code comprehension, reuse, restructuring and testing. Unfortunately, implementation is not straightforward because the full exploitation of conditions requires the combination of symbolic execution, theorem proving and traditional static slicing. Hitherto, this difficultly has hindered development of fully automated conditioning slicing tools. This paper describes the first fully automated conditioned slicing system, CON SIT, detailing the theory that underlies it, its architecture and the way it combines symbolic execution, theorem proving and slicing technologies. The use of CON SIT is illustrated with respect to the applications of testing and comprehension. Copyright © 2003 John Wiley & Sons, Ltd.     

Computation of dynamic program slices for unstructured programs

A dynamic program slice is an executable part of the program whose behaviour is identical, for the same program input, to that of the original program with respect to a variable(s) of interest at some execution position. The existing algorithms of dynamic slice computation use data and control dependencies to compute dynamic slices. These algorithms are limited to structured programs because they may compute incorrect dynamic slices for unstructured programs, due to the limitations of control dependencies that are used to compute dynamic slices. In this paper, we present a novel approach to dynamic slice computation for unstructured programs. The approach employs the notion of a removable block in finding dynamic program slices. Dynamic slices are derived by identifying not only those parts of program execution that contribute to the computation of the value of a variable of interest, but also those parts of program execution that do not contribute to the computation of the variable value. Data dependencies are used to identify contributing computations, whereas removable blocks are used to identify noncontributing computations. We have proved that the presented dynamic slicing algorithms correctly compute dynamic slices. In addition, these algorithms may compute more accurate dynamic slices compared to existing algorithms that use control dependencies. The presented algorithms have been implemented in a tool that supports dynamic slicing for Pascal programs     

自动分析递归数据结构的归纳性质

本文提出了一种对递归数据结构的归纳性质进行自动化分析的框架.工作分为三个主要部分.首先,它将递归数据结构的归纳性质分为两个主要类别,并提出对应的处理模式,从而帮助简化对于程序中的递归数据结构上的相关性质的分析.其次,提出了一种称为分割与拼接的技术来发现和描述递归数据结构是如何被程序修改的：递归数据结构首先被分割为若干个互不相交的片段,然后这些片段以新的方式重新拼接在一起,形成一个新的数据结构.这个技术的重点在于如何将程序原有的性质保留下来,从而为后面的分析过程所使用.最后,提出了一种调用上下文敏感的程序摘要过程间分析方法.案例分析和实验结果表明我们的分析框架可以有效地分析递归数据结构的归纳性质,并生成对程序证明过程有用的断言.     

Linguistic reflection in Java

Reflective systems allow their own structures to be altered from within. Here we are concerned with a style of reflection, called linguistic reflection, which is the ability of a running program to generate new program fragments and to integrate these into its own execution. In particular, we describe how this kind of reflection may be provided in the compiler-based, strongly typed object-oriented programming language Java. The advantages of the programming technique include attaining high levels of genericity and accommodating system evolution. These advantages are illustrated by an example taken from persistent programming, which shows how linguistic reflection allows functionality (program code) to be generated on demand (Just-In-Time) from a generic specification and integrated into the evolving running program. The technique is evaluated against alternative implementation approaches with respect to efficiency, safety and ease of use. © 1998 John Wiley & Sons, Ltd.     

形式化语言RT-Z的合成及其应用

Z是一种确定相关数据特征的非常成功的形式化语言，却在构造动态行为方面的模型缺乏相应的功能；而Timed CSP是一种确定动态行为的功能强大的语言，但它没提供适当的结构来构造相关数据特征。文中通过形式化语言Z和过程代数Timed CSP合成一种新的形式化方法RT-Z，使得RT-Z在软件系统开发过程的需求定义和设计阶段能书写软件系统一致、简单的规格说明。     

Concurrent runtime monitoring of formally specified programs

A methodology for continuously monitoring a program for specification consistency during program execution is described. Prior development of the formal specification and program is assumed. The program is annotated with constructs from a formal specification language, and the formal specification constructs are transformed into checking code, which is then inserted into the underlying program. Calls to this checking code are inserted into underlying program wherever it can potentially become inconsistent with its specification. If an inconsistency does in fact occur, diagnostic information is provided. The implementation of such a system for Anna (annotated Ada) subtype annotations is presented     

基于锁集合的动态数据竞争检测方法

数据竞争使得共享存储程序难于调试．以前大部分针对共享存储程序的动态数据竞争检测工作都是通过维护发生序来实现．这种方法有一个重要缺点，即针对程序的一种输入，对程序的一次执行进行检测，不能检测出所有的可行数据竞争．文中利用存储一致性模型的框架模型，针对域一致性模型提出了增强发生序概念，并依此得出一种基于锁集合的动态数据竞争检测算法，克服了这个问题．在软件DSM系统JIAJIA上的实现获得了很好的性能，应用平均减速比为3．14．利用该方法，在TSP程序中找到了大量的读写数据竞争的情况．     

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

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