Computation of intraprocedural dynamic program slices

Dynamic slicing algorithms are used in interactive applications such as program debugging and testing. Therefore, these algorithms need to be very efficient. In this context, we propose three intraprocedural dynamic slicing algorithms which are more space and time efficient than the existing algorithms. Two of the proposed algorithms compute precise dynamic slices of structured programs using Program Dependence Graph as an intermediate representation. To compute precise dynamic slices of unstructured programs, we introduce the concepts of jump dependence and Unstructured Program Dependence Graph. The third algorithm uses Unstructured Program Dependence Graph as the intermediate program representation, and computes precise dynamic slices of unstructured programs. We show that each of our proposed algorithms is more space and time efficient than the existing algorithms.     

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.     

Granularity-Driven Dynamic Predicate Slicing Algorithms for Message Passing Systems

Program Slicing is a well-known decomposition technique that transforms a large program into a smaller one that contains only statements relevant to the computation of a selected function. In this paper, we present two novel predicate-based dynamic slicing algorithms for message passing programs. Unlike more traditional slicing criteria that focus only on parts of the program that influence a variable of interest at a specific position in the program, a predicate focuses on those parts of the program that influence the predicate. The dynamic predicate slices capture some global requirements or suspected error properties of a distributed program and computes all statements that are relevant. The presented algorithms differ from each other in their computational approaches (forward versus backward) and in the granularity of information they provide. A proof of correctness of these algorithms is provided. Through the introduction of dominant states and dominant events, critical statement executions are identified that change the value of the global predicate. Under this formulation, optimizing dynamic predicate slicing becomes a meaningful goal as well. Finally, we present how predicate slices can be applied to support comprehension tasks for analyzing and maintaining distributed programs.     

Theory and algorithms for slicing unstructured programs

Program slicing identifies parts of a program that potentially affect a chosen computation. It has many applications in software engineering, including maintenance, evolution and re-engineering of legacy systems. However, these systems typically contain programs with unstructured control-flow, produced using goto statements; thus, effective slicing of unstructured programs remains an important topic of study.This paper shows that slicing unstructured programs inherently requires making trade-offs between three slice attributes: termination behaviour, size, and syntactic structure. It is shown how different applications of slicing require different tradeoffs. The three attributes are used as the basis of a three-dimensional theoretical framework, which classifies slicing algorithms for unstructured programs. The paper proves that for two combinations of these dimensions, no algorithm exists and presents algorithms for the remaining six combinations.     

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.     

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.     

Assertion-based slicing and slice graphs

This paper revisits the idea of slicing programs based on their axiomatic semantics, rather than using criteria based on control/data dependencies. We show how the forward propagation of preconditions and the backward propagation of postconditions can be combined in a new slicing algorithm that is more precise than the existing specification-based algorithms. The algorithm is based on (a) a precise test for removable statements, and (b) the construction of a slice graph, a program control flow graph extended with semantic labels and additional edges that “short-circuit” removable commands. It improves on previous approaches in two aspects: it does not fail to identify removable commands; and it produces the smallest possible slice that can be obtained (in a sense that will be made precise). Iteration is handled through the use of loop invariants and variants to ensure termination. The paper also discusses in detail applications of these forms of slicing, including the elimination of (conditionally) unreachable and dead code, and compares them to other related notions.     

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

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

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.     

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.     

Using program slicing to simplify testing

Program slicing is a technique for automatically identifying the statements of a program which affect a selected subset of its variables. A large program can be divided into a number of smaller program (its slices), each constructed for different variable subsets. The slices are typically simpler than the original program, thereby simplifying the process of testing a property of the program which only concerns the corresponding subset of its variables. However, some aspects of a program's computation are not captured by a set of variables, rendering slicing inapplicable. To overcome this difficulty a program can be rewritten in a self-checking form by the addition of assignment statements to denote these ‘implicit’ computations. Initially this makes the program longer. However, slicing can now be applied to the introspective program, forming a slice concerned solely with the implicit computation. The simplification power of slicing is then improved using program transformation. To illustrate this approach, the implicit computation which dictates whether or not a program is robust is taken as an example. Whether or not a program is robust is not generally decidable making the approach described here particularly appealing because the slices constructed are approximate answers to the undecidable question ‘Is the program p robust?’.     

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.     

Syntax-Directed Amorphous Slicing

An amorphous slice of a program is constructed with respect to a set of variables. The amorphous slice is an executable program which preserves the behaviour of the original on the variables of interest. Unlike syntax-preserving slices, amorphous slices need not preserve a projection of the syntax of a program. This makes the task of amorphous slice construction harder, but it also often makes the result thinner and thereby preferable in applications where syntax preservation is unimportant.This paper describes an approach to the construction of amorphous slices which is based on the Abstract Syntax Tree of the program to be sliced, and does not require the construction of control flow graphs nor of program dependence graphs. The approach has some strengths and weaknesses which the paper discusses.The amorphous slicer, is part of the GUSTT slicing system, which includes syntax preserving static and conditioned slicers, a side effect removal transformation phase, slicing criterion guidance and for which much of the correctness proofs for transformation steps are mechanically verified. The system handles a subset of WSL, into which more general WSL constructs can be transformed.The paper focuses upon the way in which the GUSTT System uses dependence reduction transformation tactics. Such dependence reduction is at the heart of all approaches to amorphous slicing. The algorithms used are described and their performance is assessed with a simple empirical study of best and worst case execution times for an implementation built on top of the FermaT transformation system for maintenance and re-engineering.     

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.     

A trajectory-based strict semantics for program slicing

We define a program semantics that is preserved by dependence-based slicing algorithms. It is a natural extension, to non-terminating programs, of the semantics introduced by Weiser (which only considered terminating ones) and, as such, is an accurate characterisation of the semantic relationship between a program and the slice produced by these algorithms.Unlike other approaches, apart from Weiser’s original one, it is based on strict standard semantics which models the ‘normal’ execution of programs on a von Neumann machine and, thus, has the advantage of being intuitive. This is essential since one of the main applications of slicing is program comprehension. Although our semantics handles non-termination, it is defined wholly in terms of finite trajectories, without having to resort to complex, counter-intuitive, non-standard models of computation. As well as being simpler, unlike other approaches to this problem, our semantics is substitutive. Substitutivity is an important property because it greatly enhances the ability to reason about correctness of meaning-preserving program transformations such as slicing.     

Slice-based statistical fault localization

Recent techniques for fault localization statistically analyze coverage information of a set of test runs to measure the correlations between program entities and program failures. However, coverage information cannot identify those program entities whose execution affects the output and therefore weakens the aforementioned correlations. This paper proposes a slice-based statistical fault localization approach to address this problem. Our approach utilizes program slices of a set of test runs to capture the influence of a program entity's execution on the output, and uses statistical analysis to measure the suspiciousness of each program entity being faulty. In addition, this paper presents a new slicing approach called approximate dynamic backward slice to balance the size and accuracy of a slice, and applies this slice to our statistical approach. We use two standard benchmarks and three real-life UNIX utility programs as our subjects, and compare our approach with a sufficient number of fault localization techniques. The experimental results show that our approach can significantly improve the effectiveness of fault localization.     

Dynamic Slicing of Petri Nets Based on Structural Dependency Graph and its Application in System Analysis

Petri net models are frequently complex and difficult to understand and modify. Slicing technology is very useful in analyzing programs, and has been widely used in specification level for model reduction. So it is necessary to explore slicing methods for Petri nets. This paper proposes a dynamic slicing technique for Petri nets based on the structural dependency graph (SDG). Firstly, the SDG is constructed from the slicing criterion by a backtracking algorithm. Secondly, based on the SDG and a given marking, the dynamic slice can be acquired. As a case study, the proposed method is applied to a control system, and a simulation tool is developed for validating this method and automatically generating the slice. The algorithms can be useful in automatically identifying the parts of the model that affect a state of interest, and provide the basic technical support for alleviating the difficulty of formal verification and analysis.     

HSFal: Effective fault localization using hybrid spectrum of full slices and execution slices

Most of the existing fault localization approaches use execution coverage of test cases to isolate the suspicious codes that likely contain faults. Program slicing can extract the dependencies of program entities with respect to a specific criterion. Therefore this technique is expected to have a beneficial effect on fault localization. In this paper, we propose a novel approach using a hybrid spectrum of full slices and execution slices to improve the effectiveness of fault localization. In particular, our approach firstly computes full slices of failed test cases and execution slices of passed test cases respectively. Secondly it constructs the hybrid spectrum by intersecting full slices and execution slices. Finally it computes the suspiciousness of each statement in the hybrid slice spectrum and generates a fault location report with descending suspiciousness of each statement. We also implement our proposed approach in our prototype tool HSFal by Java programming language. To verify the effectiveness of our approach, we performed an empirical study by the prototype on several widely used open source programs. Our approach is compared with eight representative coverage-based and slice-based fault localization approaches. Final experimental results show that our proposed approach is more effective in fault localization than other compared approaches, and can reduce almost 2.98–31.79% of the average cost of examined code significantly.