Interprocedural Functional Shape Analysis using Local Heaps
Noam Rinetzky, Mooly Sagiv, Eran Yahav · 2004
We present a framework for interprocedural shape analysis, which is contextand flow-sensitive with the ability to perform destructive pointer updates. Instances of the framework are precise enough to prove the absence of program errors such as null dereferences, memory leaks and verify conformance to API specifications. Technically, our analysis computes procedure summaries as transformers from inputs to outputs while ignoring parts of the heap not relevant to the procedure. This makes the analysis modular in the heap and thus allows reusing the effect of a procedure at different call-sites and even between different contexts occurring at the same call-site. A prototype of our framework was implemented and used to verify interesting properties of heap manipulating programs. 1