A theory of slicing non-deterministic programs and systems is developed. Non-deterministic programs and systems are represented as non-deterministic program graphs (NDPGs) that allow arbitrary non-deterministic branching to be expressed. Structural and semantic relationships that must exist between an NDPG and (1) its non-termination insensitive (weak) slices and (2) its non-termination sensitive (strong) slices are defined. Weak and strong commitment closure are introduced. These are the NDPG equivalents of being closed under non-termination sensitive and non-termination insensitive control dependence; properties defined on subsets of vertices of the equivalent deterministic structure: the control flow graph. It is proved that if a subset of the vertices of an NDPG is both data dependence closed and (weak/strong) commitment closed, then the resulting induced graph will, indeed, satisfy our structural and semantic requirements. O ( n 3 ) algorithms for computing minimal data and weak/strong commitment closed sets are given. The resulting induced graphs are thus guaranteed to be weak and strong slices, respectively. It is demonstrated, with examples, that programs written in Dijkstra's non-deterministic guarded command language (DNGCL) can be converted to NDPGs to which our slicing algorithms can then be applied. It is proved that the resulting slices (NDPGs) can always be converted back to valid DNGCL programs, highlighting the applicability of our approach to slicing at the source code level.

The concept of community structure arises from the analysis of social networks in sociology. Community structure can be found in many real world graphs other than social networks. Recently, efficient community detection algorithms have been developed which can cope with very large graphs with millions of nodes and potentially billions of edges. So, for the first time, there is the potential for investigating communities in real industrial-strength software at the statement level. We provide empirical evidence that dependence between statements in software does, indeed, give rise to community structure. Initial findings suggest that the separate dependence communities are far from arbitrary. They appear to decompose systems into areas of distinct functionality. This new approach to system decomposition has tremendous potential in many areas of software engineering, particularly in reverse engineering of legacy software and program comprehension.

The problem of deciding whether one point in a program is data dependent upon another is fundamental to program analysis and has been widely studied. In this article we consider this problem at the abstraction level of program schemas in which computations occur in the Herbrand domain of terms and predicate symbols, which represent arbitrary predicate functions, are allowed. Given a vertex l in the flowchart of a schema S having only equality (variable copying) assignments, and variables v , w , we show that it is PSPACE-hard to decide whether there exists an execution of a program defined by S in which v holds the initial value of w at at least one occurrence of l on the path of execution, with membership in PSPACE holding provided there is a constant upper bound on the arity of any predicate in S . We also consider the ‘dual’ problem in which v is required to hold the initial value of w at every occurrence of l , for which the analogous results hold. Additionally, the former problem for programs with nondeterministic branching (in effect, free schemas) in which assignments with functions are allowed is proved to be polynomial-time decidable provided a constant upper bound is placed upon the number of occurrences of the concurrency operator in the schemas being considered. This result is promising since many concurrent systems have a relatively small number of threads (concurrent processes), especially when compared with the number of statements they have.

Given a program, a quotient can be obtained from it by deleting zero or more statements. The field of program slicing is concerned with computing a quotient of a program that preserves part of the behaviour of the original program. All program slicing algorithms take account of the structural properties of a program, such as control dependence and data dependence, rather than the semantics of its functions and predicates, and thus work, in effect, with program schemas. The dynamic slicing criterion of Korel and Laski requires only that program behaviour is preserved in cases where the original program follows a particular path, and that the slice/quotient follows this path. In this paper we formalise Korel and Laski's definition of a dynamic slice as applied to linear schemas, and also formulate a less restrictive definition in which the path through the original program need not be preserved by the slice. The less restrictive definition has the benefit of leading to smaller slices. For both definitions, we compute complexity bounds for the problems of establishing whether a given slice of a linear schema is a dynamic slice and whether a linear schema has a non-trivial dynamic slice, and prove that the latter problem is NP-hard in both cases. We also give an example to prove that minimal dynamic slices (whether or not they preserve the original path) need not be unique.

Decompilation of Java bytecode is the act of transforming Java bytecode to Java source code. Although easier than that of decompilation of machine code, problems still arise in Java bytecode decompilation. These include type inference of local variables and exception-handling. Since the last such evaluation (2003) several new commercial, free and open-source Java decompilers have appeared and some of the older ones have been updated. In this paper, we evaluate the currently available Java bytecode decompilers using an extension of the criteria that were used in the original study. Although there has been a slight improvement since this study, it was found that none passed all the tests, each of which were designed to target different problem areas. We give reasons for this lack of success and suggest methods by which future Java bytecode decompilers could be improved.

Program comprehension of unfamiliar software is a daunting task and existing comprehension environments, although helping significantly, do not fully alleviate the information overload involved. The visual medium has been well-explored in aiding software engineers understanding of source code and other artifacts concerned with maintaining existing software systems, but the use of non-visual representations, e.g. sound, has not gone far beyond simple noises to indicate error conditions or attract attention in a running program. This paper aims to explore the program comprehension problems that could usefully be addressed using sound. There are many dimensions to this problem and this paper addresses a new area open program comprehension research, defining the problem space and beginning to populate it with possible solutions. We expect the primary focus of this session to be on software comprehension and sound although many disciplines are likely to become involved in the research that flows from it

Abstract A formal relationship between program slicing and partial evaluation is established. It is proved that for terminating programs, a residual program produced by partial evaluation is semantically equivalent to a conditioned slice.

Program slicing is an automated source code extraction technique that has been applied to a number of problems including testing, debugging, maintenance, reverse engineering, program comprehension, reuse and program integration. In all these applications the size of the slice is crucial; the smaller the better. It is known that statement minimal slices are not computable, but the question of dataflow minimal slicing has remained open since Weiser posed it in 1979. This paper proves that static slicing algorithms produce dataflow minimal end slices for programs which can be represented as schemas which are free and liberal.

Abstract 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, CONSIT, detailing the theory that underlies it, its architecture and the way it combines symbolic execution, theorem proving and slicing technologies. The use of CONSIT is illustrated with respect to the applications of testing and comprehension. Copyright © 2003 John Wiley & Sons, Ltd.

Abstract The attempt to design and integrate consistent changes to an existing system is the essence of software maintenance. Software developers also confront similar problems: there are changes during testing and the release of new system builds. Whether in development or maintenance, changes to evolving systems must be made consistently; that is, without damaging correct computations. It is difficult for the programmer to ascertain the complete effect of a code change; the programmer may make a change to a program that is syntactically and semantically legal, but which has ripples into the parts of the program that were intended to remain unchanged. Using the standard denotational semantics for procedural programming languages, this paper formalizes decomposition slicing, which identifies interferences between software components and isolates the components to be changed. We enumerate the conditions for changing one component in ways that will guarantee that changes to it will not interact inconsistently and prove that changes made under these conditions are sound. Thus, the programmer can then execute changes secure in the knowledge that the semantics of the new system are guaranteed to be consistent with the projection of the semantics of the original for which it behaved correctly. Validating that the changes do not interfere not only guarantees consistency with respect to previous unchanging behaviors, but can also be achieved with a complexity proportional to the size of the change to be made. Copyright © 2003 John Wiley & Sons, Ltd.

Evolutionary testing is a search based approach to the automated generation of systematic test data, in which the search is guided by the test data adequacy criterion. Two problems for evolutionary testing are the large size of the search space and structural impediments in the implementation of the program which inhibit the formulation of a suitable fitness function to guide the search. In this paper we claim that slicing can be used to narrow the search space and transformation can be applied to the problem of structural impediments. The paper presents examples of how these two techniques have been successfully employed to make evolutionary testing both more efficient and more effective.

Th paper shows how analysis of programs in terms of pre- and postconditions can be improved using a generalisation of conditioned program slicing called pre/post conditioned slicing. Such conditions play an important role in program comprehension, reuse, verification and reengineering. Fully automated analysis is impossible because of the inherent undecidability of pre- and post- conditions. The method presented reformulates the problem to circumvent this. The reformulation is constructed so that programs which respect the pre- and post-conditions applied to them have empty slices. For those which do not respect the conditions, the slice contains statements which could potentially break the conditions. This separates the automatable part of the analysis from the human analysis.

Conditioned slicing is a powerful generalisation of static and dynamic slicing which has applications to many problems in software maintenance and evolution, including reuse, reengineering and program comprehension. However there has been relatively little work on the implementation of conditioned slicing. Algorithms for implementing conditioned slicing necessarily involve reasoning about the values of program predicates in certain sets of states derived from the conditioned slicing criterion, making implementation particularly demanding. The paper introduces ConSIT, a conditioned slicing system which is based upon conventional static slicing, symbolic execution and theorem proving. ConSIT is the first fully automated implementation of conditioned slicing. An implementation of ConSIT is available for experimentation at http://www.mcs.gold.ac.uk//spl tilde/mas01sd/consit.html.

While mutation testing has proved to be an effective way of finding software faults, currently it is only applied to relatively small programs. One of the main reasons for this is the human analysis required in detecting equivalent mutants. Here program slicing is used to simplify this problem. Progam slicing is also used to reduce the number of equivalent mutants produced. Copyright © 1999 John Wiley & Sons, Ltd.

Problems associated with understanding, verifying and re-engineering the way in which a system allocates and releases dynamic memory present significant challenges to the software maintainer. Because the questions underlying these problems are undecidable, no system can provide a completely fail safe certification. For example, in checking for memory leaks, a system can only warn of potential problems, but cannot guarantee that no leaks remain. We present an approach to modelling the dynamic memory access properties of a program using amorphous program slicing to create a Dynamic Memory Model (DMM). The slices are constructed from a transformed version of the original program in which heap access has been made explicit using a pseudo variable to denote the top of the heap. The DMM is a simplified version of the original program which is concerned solely with the dynamic memory access behaviour of the original. We illustrate the use of DMMs in problems of comprehension, verification and re-engineering. We introduce a proof-of-concept DMM construction algorithm, showing how slicing simplification power can be dramatically improved using domain-specific transformation rules.

Program slicing is an automatic program abstraction technique whose many applications include software maintenance, re-engineering and comprehension, all of which rely crucially upon the precision of the slicing algorithm used. When slicing is applied to maintenance problems, the programs to be sliced are typically legacy systems, often written in older, ‘unstructured’ programming styles. For slicing to be a useful tool to the software maintainer it is therefore important to have precise algorithms for slicing unstructured programs. Unfortunately the standard algorithms for slicing structured programs do not extend correctly to the unstructured paradigm, and currently proposed modifications to these standard algorithms produce either unnecessarily large slices or slices which are not true subsets of the original program from which they are constructed. This paper introduces a modification of Agrawal's algorithm for slicing unstructured programs, which overcomes these difficulties. The new algorithm produces thinner slices than any previously published algorithm while respecting both the semantic and syntactic constraints of slicing. © 1998 John Wiley & Sons, Ltd.

Abstract Program slicing is a technique by which statements are deleted from a program in such a way as to preserve a projection of the original program's semantics. It is shown that slicing algorithms based upon traditional defined and referenced variable sets do not preserve a projection of strict semantics with respect to computations which cause errors. Rather, these approaches preserve a projection of the program's semantics which is lazy with respect to errors. A modified version of defined and referenced variable sets is introduced, which provides the freedom to choose the form of semantics to be preserved.

Abstract 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?’.