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.     

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     

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.     

Back to the Future: Omniscient Debugging

This article presents TOD (trace oriented debugger), a prototype scalable omniscient debugger for Java, which aims at making omniscient debugging practical, at last. Omniscient debuggers, also known as back-in-time or reversible debuggers, record the whole history, or execution trace, of a debugged program and let the user freely explore it. This approach combines the advantages of both log-based (past activity is never lost) and breakpoint based debugging (interactive navigation, step-by-step execution, and complete stack inspection). Omniscient debuggers simulate step-by-step execution both forward and backward, avoiding having to rerun the whole program many times to pinpoint the bug's root cause. More importantly, they make it possible to navigate through the history of a program by following causal links, so questions that would otherwise require a significant effort can be answered instantly for instance, "When was variable x assigned a null value?" or "What was the state of object o when it was passed as an argument to method foo?".     

Moped (a portable debugger)

Moped is a portable debugger that uses enhanced tracing facilities and backtracing to discover unusual or undesirable program behaviors. It is based upon two modules — Program Probes and Program History. Program Probes is a forward tracing utility which allows Moped to dynamically examine the execution of a program. Program History is a backtracing utility which allows Moped to study the executed section of a program. Together, Program Probes and Program History enable Moped to have more control over the behavior of a program than either one of them, and consequently to provide an easier path toward program debugging. Moped is written in Common LISP with no dependencies on details of the machine implementation. Therefore, it is easily portable to any Common LISP environment.     

Moped (a portable debugger)

Moped is a portable debugger that uses enhanced tracing facilities and backtracing to discover unusual or undesirable program behaviors. It is based upon two modules — Program Probes and Program History. Program Probes is a forward tracing utility which allows Moped to dynamically examine the execution of a program. Program History is a backtracing utility which allows Moped to study the executed section of a program. Together, Program Probes and Program History enable Moped to have more control over the behavior of a program than either one of them, and consequently to provide an easier path toward program debugging. Moped is written in Common LISP with no dependencies on details of the machine implementation. Therefore, it is easily portable to any Common LISP environment.This work supported in part by Hewlett-Packard Company, the National Science foundation Under Grant Number MCS81-21750 and the Defense Advanced Research Projects Agency under contract number DAAK11-84-K-0017.     

Dynamic Query-Based Debugging of Object-Oriented Programs

Program errors are hard to find because of the cause-effect gap between the instant when an error occurs and when the error becomes apparent to the programmer. Although debugging techniques such as conditional and data breakpoints help in finding errors in simple cases, they fail to effectively bridge the cause-effect gap in many situations. This paper proposes two debuggers that provide programmers with an instant error alert by continuously checking inter-object relationships while the debugged program is running. We call such tool a dynamic query-based debugger. To speed up dynamic query evaluation, our debugger implemented in portable Java uses a combination of program instrumentation, load-time code generation, query optimization, and incremental reevaluation. Experiments and a query cost model show that selection queries are efficient in most cases, while more costly join queries are practical when query evaluations are infrequent or query domains are small. To enable query-based debugging in the middle of program execution in a portable way, our debugger performs efficient Java class file instrumentation. We call such debugger an on-the-fly debugger. Though the on-the-fly debugger has a higher overhead than a dynamic query-based debugger, it offers additional interactive power and flexibility while maintaining complete portability.     

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

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

Redux: A Dynamic Dataflow Tracer

Redux is a tool that generates dynamic dataflow graphs. It generates these graphs by tracing a program's execution and recording every value-producing operation that takes place, building up a complete computational history of every value produced. For that execution, by considering the parts of the graph reachable from system call inputs, we can choose to see only the dataflow that affects the outside world. Redux works with program binaries, and thus is not restricted to programs written in any particular language.We explain how Redux works, and show how dynamic dataflow graphs give the essence of a program's computation. We show how Redux can be used for debugging and program slicing, and consider a range of other possible uses.     

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.     

Locating faulty code by multiple points slicing

Dynamic slicing has long been considered as a useful tool for debugging programs as it effectively identifies a reduced fault candidate set which captures the faulty code in the program. Traditionally, a backward dynamic slice is computed starting from an incorrect value observed by the programmer during a failed program run. This incorrect value is either an incorrect output value or an incorrect address whose dereferencing causes the program to crash. Recently we proposed two additional types of dynamic slices, a forward dynamic slice of a minimal failure inducing input difference and a bidirectional dynamic slice of a critical predicate. We have built a dynamic slicing tool that computes dynamic slices by instrumenting program binaries and executing them to build dynamic dependence graphs. In this paper, through experiments, we demonstrate that supporting three different types of dynamic slices has the following advantages. First, we observe that for each type of dynamic slice there are distinct situations in which it is not applicable. Therefore, we should support multiple types of slices to handle a wide range of situations. Second, supporting multiple types of dynamic slices enables us to compute a multiple points dynamic slice which is the intersection of different type of available slices. Our experiments show that multiple points dynamic slices are significantly smaller than any of the three kinds of individual dynamic slices. Copyright © 2006 John Wiley & Sons, Ltd.     

A debugger for distributed programs

Developing a distributed debugger is much more complex than developing a sequential debugger. This added complexity is mainly due to the non-determinism of events that communication delays introduce into distributed systems. We explore the problems that one must address when designing a distributed program debugger and then describe our design and implementation of DPD (distributed program debugger). Problems addressed include non-determinism of events, finding consistent system states, setting breakpoints, recording events, and checkpointing. Important features of DPD include dynamic roll back and replay, as well as a graphical user interface. DPD has been tested successfully in debugging distributed programs within a distributed facility called REM (remote execution manager).     

The value of slicing while debugging

The paper describes a study that explored the relationship of program slicing to (1) code understanding gained while debugging, and to (2) a debugger's ability to localize the program fault area. The study included two experiments. The first experiment compared the program understanding abilities of two classes of debuggers: those who slice while debugging and those who do not. For debugging purposes, a slice can be thought of as a minimal subprogram of the original code that contains the program faults. Those who only examine statements within a slice for correctness are considered slicers; all others are considered non-slicers. Using accuracy of subprogram construction as a measure of understanding, it was determined that slicers have a better understanding of the code after debugging. The second experiment compared debugger fault localization abilities before and after a training session on how to use slicing in debugging. Using time as a measure of ability, it was shown that slicing while debugging improves a debugger's ability to localize the program fault area.     

调试器对并行程序干扰特性的研究

机群系统中并行程序的执行具有不确定性，这种不确定性给并行程序的调试带来了困难，并行程序的不确定性是由运行环境中的各种干扰因素造成的，该文研究交互式调试行为对调试程序的干扰特性，文中给出了算法可以在调试的过程中实时地报告出本次交互式调试操作是否对调试的程序造成了干扰。     

远程调试的设计与实现

一般情况下,调试器与被调试程序（目标程序）运行在同一个计算机系统环境中,但是,在实时系统、内核调试及一些Ｃｌｉｅｎｔ／Ｓｅｒｖｅｒ系统等情况下,调试器不能运行在目标程序运行的环境中,此时有效的解决方法就是实施远程调试（Ｒｅｍｏｔｅ ｄｅｂｕｇｇｉｎｇ）。远程调试系统由本地调试器、远程调试服务器以及远程调试通讯协议组成。该文详细讨论这三部分的设计与实现,并介绍一个自行设计的基于远程调试的并行调试器。     

A Case for Compressing Traces with BDDs

Instruction-level traces are widely used for program and hardware analysis. However, program traces for just a few seconds of execution are enormous, up to several terabytes in size, uncompressed. Specialized compression can shrink traces to a few gigabytes, but trace analyzers typically stream the decompressed trace through the analysis engine. Thus, the complexity of analysis depends on the decompressed trace size (even though the decompressed trace is never stored to disk). This makes many global or interactive analyses infeasible. This paper presents a method to compress program traces using binary decision diagrams (BDDs). BDDs intrinsically support operations common to many desirable program analyses and these analyses operate directly on the BDD. Thus, they are often polynomial in the size of the compressed representation. The paper presents mechanisms to represent a variety of trace data using BDDs and shows that BDDs can store, in 1 GB of RAM, the entire data-dependence graph of traces with over 1 billion instructions. This allows rapid computation of global analyses such as heap-object liveness and dynamic slicing     

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

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

考虑实时栈信息的静态切片工具

为了提高静态切片精度,本文结合程序抛出异常时产生的堆栈追踪信息进行程序执行轨迹的推测,找出那些确定没有执行的方法或语句,设计并实现考虑实时栈信息的Java程序静态切片工具.实验结果表明,该切片工具进一步减少搜索空间,可以提高普通静态切片方法的精度和效率.     

Guard: A Relative Debugger

A significant amount of software development is evolutionary, involving the modification of already existing programs. To a large extent, the modified programs produce the same results as the original program. This similarity between the original program and the development program is utilized by relative debugging. Relative debugging is a new concept that enables the user to compare the execution of two programs by specifying the expected correspondences between their states. A relative debugger concurrently executes the programs, verifies the correspondences, and reports any differences found. We describe our novel debugger, called Guard, and its relative debugging capabilities. Guard is implemented by using our library of debugging routines, called Dynascope, which provides debugging primitives in heterogeneous networked environments. To demonstrate the capacity of Guard for debugging in heterogeneous environments, we describe an experiment in which the execution of two programs is compared across Internet. The programs are written in different programming languages and executing on different computing platforms. © 1997 by John Wiley & Sons, Ltd.     

开源跨平台的图像可视化调试器设计

目的 在调试C/C++图像处理程序时,如何以可视化的形式观察被调试程序中的图像变量,对于调试过程尤为关键。目前尚未有跨多操作系统平台的图像可视化调试器可供使用,该款开源跨平台的图像可视化调试器的设计与实现弥补了此领域的不足。方法 利用GDB(GNU debugger)调试器的Python接口,将被调试程序中的图像变量对应的内存字节序列转化成Python下的2维数组,并采用Matplotlib库加以显示,整个图像显示线程独立于GDB的文本字符交互主线程。结果 在Windows、Linux、Mac系统中分别进行实验,均可实现图像变量的显示、缩放、平移、像素数值查看、保存等多种功能,并使得GDB的命令行保持非阻塞模式运行。结论 开源跨平台的图像可视化调试器的设计,满足了不同操作系统平台下图像程序的开发调试需求,弥补了当前GDB调试图像程序功能的不足,提高了图像处理程序的开发和调试效率。