Dynamic Shape Analysis of Program Heap using Graph Spectra

Muhammad Zubair Malik
University of Texas at Austin, USA
Program Analysis 2

Programs written in languages such as Java and C# maintain most of their state on the heap. The size and complexity of these programs pose a challenge in understanding and maintaining them; Heap analysis by summarizing the state of heap graphs assists programmers in these tasks. In this paper we present a novel dynamic heap analysis technique that uses spectra of the heap graphs to summarize them. These summaries capture the shape of recursive data structures as dynamic invariants or likely properties of these structures that must be preserved after any destructive update. Initial experiments show that this approach can generate meaningful summaries for a range of subject structures.