Every software engineer, regardless of their level of experience in the industry, has been faced with debugging a null-pointer dereference bug, and the experience is rarely one that engineers recall with fondness. Bugs in memory allocation are depressingly common; at the same time, they are difficult to comprehend and debug. Efforts to address these problems have spawned an entire sub-industry of tools to measure memory usage and debug memory bugs. These tools are largely focused on helping engineers identify potentially catastrophic failures in software caused by memory bugs. However, there is much to be gained just by improving the means for conveying the memory use patterns of a program to the engineer debugging it. Along with other tools, this can help engineers quickly identify a root cause for many memory bugs.
The authors of this paper bring together a number of simple algorithmic and visualization techniques to address the problem of visualizing pointer patterns in a program. The overall approach is based on instrumenting the program to capture snapshots of memory at various points of program execution. The pointer patterns in these snapshots are then summarized, taking advantage of static type information from the program. The summarization algorithms work by identifying equivalence classes of memory locations and are implemented efficiently using standard data structures. Another simple technique that is used effectively is the use of dominators to summarize complex memory graphs.
The most valuable takeaway is found in the heuristics the authors use to construct useful summaries of program heaps based on insights gained by experimenting with real-life programs. These heuristics and the insights motivating them are spread throughout the paper.