Tools
Tools
Sivagurunathan, Yoga (2004) Modelling dynamic memory allocation and deallocation using amorphous slicing. Doctoral thesis, London Metropolitan University.
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.
This thesis shows how to denote implicit state components with pseudo variables, making these components explicit. This transformation of an implicit-state program into an explicit-state program is useful because it allows us to form a slicing criterion which captures the (previously implicit) state. The implicit state removal algorithm for a simple intraprocedural language (involving heap allocation using malloc) is presented as a context-free, syntax directed transformation.
Amorphous program slicing is used to create a Dynamic Memory Model (DMM). The slice is constructed from a transformed version of the original program in which heap access is 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 dynamic memory access.
The thesis presents 3 case studies to evaluate the use of slicing to construct the DMM of a real program: diff, the GNU differencing program, Word count and DVD stock analysis program. In order to measure the size of a program, the Lines of Code (LoC) metric is used.
The results from various slicing algorithms and approaches need to be comparable using LoC as a metric. This required some pre-processing to ensure that lines of code were counted in a fair and consistent manner and some post-processing to repair the ( only slightly) erroneous slices produced by Unravel. The results of the case study show:
• Syntax-preserving static slicing is applicable to the problem of dynamic memory analysis;
• Amorphous static slicing further improves the results of syntax-preserving static slicing;
• Syntax-preserving slicing performs well for Dynamic Memory Modelling.
 |
View Item |