Abstract. We present a framework for interprocedural shape analysis, which is contextand flow-sensitive with the ability to perform destructive pointer updates. We limit our attention to cutpoint-free programs-programs in which reasoning on a procedure call only requires consideration of context reachable from the actual parameters. For such programs, we show that our framework is able to perform an efficient modular analysis. 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. We have implemented a prototype of our framework and used it to verify interesting properties of cutpoint-free programs, including partial correctness of a recursive quicksort implementation.
Rinetzky et al. REF present an efficient shape analysis for the class of cutpoint-free programs, in which at each procedure call, the subgraph of the heap reachable in the callee can only be reached in the caller through arguments of the call.
Interprocedural shape analysis for cutpoint-free programs
In SAS’05: Static Analysis Symposium, volume 3672 of LNCS
Computer Science