Stephen Magill

Instrumentation Analysis: An Automated Method for Producing Numeric Abstractions of Heap-Manipulating Programs Degree Type: Ph.D. in Computer Science
Advisor(s): Peter Lee
Graduated: December 2010

Abstract:

A number of questions regarding programs involving heap-based data structures can be phrased as questions about numeric properties of those structures. A data structure traversal might terminate if the length of some path is eventually zero or a function to remove n elements from a collection may only be safe if the collection has size at least n.

In this thesis, we develop proof methods for reasoning about the connection between heap-manipulating programs and numeric programs. In addition, we develop an automatic method for producing numeric abstractions of heap-manipulating programs. These numeric abstractions are expressed as simple imperative programs over integer variables and have the feature that if a property holds of the numeric program, then it also holds of the original, heap-manipulating program. This is true for both safety and liveness. The abstraction procedure makes use of a shape analysis based on separation logic and has support for user-defined inductive data structures.

We also discuss a number of applications of this technique. Numeric abstractions, once obtained, can be analyzed with a variety of existing verification tools. Termination provers can be used to reason about termination of the numeric abstraction, and thus termination of the original program. Safety checkers can be used to reason about assertion safety. And bound inference tools can be used to obtain bounds on the values of program variables. With small changes to the program source, bounds analysis also allows the computation of symbolic bounds on memory use and computational complexity.

Thesis Committee:
Peter Lee (Chair)
Stephen Brookes
John Reynolds
Byron Cook (Microsoft Research, Cambridge, UK)

Jeannette Wing, Head, Computer Science Department
Randy Bryant, Dean, School of Computer Science

Keywords:
Separation Logic, Instrumentation Analysis, Statis Analysis, Abstract Interpretation, Termination Proving, Hoare Logic