Syntax-directed amorphous slicing

TY - JOUR

T1 - Syntax-directed amorphous slicing

AU - Harman, M

AU - Hu, L

AU - Munro, M

AU - Zhang, X

AU - Binkley, D

AU - Danicic, S

AU - Daoudi, M

AU - Ouarbya, L

PY - 2004/1

Y1 - 2004/1

N2 - 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. We describe 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 is discussed. 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. We focus 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. (82 References).

AB - 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. We describe 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 is discussed. 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. We focus 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. (82 References).

M3 - Article

VL - ol.11

SP - 27

EP - 61

JO - Automated Software Engineering

JF - Automated Software Engineering

IS - .1

ER -