Points-to Analysis: A Fine-Grained Evaluation

Jonas Lundberg (Linnaeus University, Sweden)

Welf Lowe (Linnaeus University, Sweden)

Abstract: Points-to analysis is a static program analysis that extracts reference information from programs, e.g., possible targets of a call and possible objects referenced by a field. Previous works evaluating different approaches to context-sensitive Pointsto analyses use coarse-grained precision metrics focusing on references between source code entities like methods and classes. Two typical examples of such metrics are the number of nodes and edges in a call-graph. These works indicate that context-sensitive analysis with a call-depth k = 1 only provides slightly better precision than contextinsensitive analysis. Moreover, these works could not find a substantial precision improvement when using the more expensive analyses with call-depth k < 1.

The hypothesis in the present paper is that substantial differences between the contextsensitive approaches show if (and only if) the precision is measured by more fine-grained metrics focusing on individual objects (rather than methods and classes) and references between them. These metrics are justified by the many applications requiring such detailed object reference information.

In order to experimentally validate our hypothesis we make a systematic comparison of ten different variants of context-sensitive Points-to analysis using different call-depths k <= 1 for separating the contexts. For the comparison we use a metric suite containing four different metrics that all focus on individual objects and references between them.

The main results show that the differences between different context-sensitive analysis techniques are substantial, also the differences between the context-insensitive and the context-sensitive analyses with call-depth k = 1 are substantial. The major surprise was that increasing the call-depth k < 1 did not lead to any substantial precision improvements. This is a negative result since it indicates that, in practice, we cannot get a more precise Points-to analysis by increasing the call-depth. Further investigations show that substantial precision improvements can be detected for k < 1, but they occur at such a low detail level that they are unlikely to be of any practical use.

Keywords: context sensitivity, points-to analysis, static program analysis

Categories: D.2.3, D.3.4, F.3.2