Slice-based dynamic memory modelling - a case study

Program slicing is a source-code extraction technique that identifies parts of a program which have no effect upon a chosen set of variables at a point of interest. Slices can be constructed statically (with respect to no input information) or conditionally (with respect to partial input information). They can also be constructed in either a purely syntax-preserving or amorphous way. Amorphous slices tend to be smaller than their syntax-preserving counterparts but they may not be syntactically related to the original. This paper presents the results of a case study which assesses the value of static and conditioned slicing (in both syntax-preserving and amorphous formulations) upon the problem of dynamic memory analysis. The results confirmed our belief that slicing is helpful for dynamic memory analysis: syntax-preserving static slicing produced an order-of-magnitude reduction in the size of the program to be analysed. Amorphous static slicing produced a further reduction in slice size. Finally, conditioned slicing (both syntax-preserving and amorphous) produced the smallest slices (12 to 35 lines of code).

1 Introduction

The dynamic memory allocation properties of a program are often hard to understand and problems associated with dynamic memory are notoriously difficult to model, predict and verify. However, the problems which can arise as a result of a failure to correctly understand dynamic memory allocation can be severe. For instance, the report on London Ambulance Service System failure attributed the second disastrous crash of November 1992 to the accidental insertion of a simple memory leak in the vehicle mobilisation routine [6] (section 4039).