Modular Heap Analysis For Higher Order Programs

We consider the problem of computing summaries for procedures that soundly capture the effect of calling a procedure on program state that includes a mutable heap. Such summaries are the basis for a compositional program analysis and key to scalability. Higher order procedures contain callbacks (indirect calls to procedures specified by callers). The use of such callbacks and higherorder features are becoming increasingly widespread and commonplace even in mainstream imperative languages such as C# and Java. Such callbacks complicate compositional analysis and the construction of procedure summaries. We present an abstract-interpretation based approach to computing summaries (of a procedure’s effect on a mutable heap) in the presence of callbacks in a simple imperative language. We present an empirical evaluation of our approach.