Flow-sensitive pointer analysis promises more precise results than its flow-insensitive counterpart by respecting program control-flow. However, existing heap abstractions for C/C++ flow-sensitive pointer analysis model the heap by creating one heap object per memory allocation. Two runtime heap objects which originate from the same allocation site are imprecisely modeled using one abstract object, which makes them share the same imprecise points-to sets and thus reduces the benefit of analysing heap objects flow-sensitively. On the other hand, equipping flow-sensitive analysis with context-sensitivity where an abstract heap object is created (cloned) per calling context can yield a more precise heap modeling for flow-sensitive analysis, but at the cost of uncontrollable analysis overhead when analysing larger programs.

This paper presents TypeClone, a new type-based heap model for flow-sensitive analysis. Our key insight is to differentiate concrete heap objects lazily using the type information at their use sites (e.g., accessed via pointer dereferencing) within the program control-flow. The novelty of TypeClone lies in its lazy heap cloning: an untyped abstract heap object created at an allocation site is killed and replaced with a new (cloned) object uniquely identified by the type information at its use site for flow-sensitive points-to propagation. This yields more precise points-to relations for each program point through well-typed objects where necessary. Thus, heap cloning can be performed within a flow-sensitive analysis without the need for context-sensitivity. Moreover, we extend TypeClone to support new kinds of strong updates for heap objects to filter out imprecise points-to relations at object use sites for programs conforming to the strict aliasing rules based on the standard C/C++ specification. Our method is neither strictly superior nor inferior to context-sensitive heap cloning, but rather, represents a new dimension that achieves a sweet spot between precision and efficiency. Our experimental results also confirm that TypeClone is more precise than flow-sensitive pointer analysis by increasing the percentage of no-alias queries by 12% on average.