Software Engineering for Smart Data Analytics & Smart Data Analytics for Software Engineering
Computing precise points-to information needs a precise call-graph and computing a precise call graph needs points-to information.
One way to deal with this mutual dependency is to compute a context-insensitive call graph upfront with a fast, linear algorithm (e.g. Bacon's rapid type analysis), and use it during the points-to analysis. The drawback of this approach is that the graph will probably be much bigger than required because, lacking points-to information, too many methods will be included as potential targets for dynamically bound invocations. Thus the subsequent points-to analysis will waste time on analysing effectively unreachable code and its precision will degrade because it includes points-to information from such code.
A better alternative is to construct a context-sensitive call-graph on-the-fly, during computation of points-to relations. This talk will present an extension of Sridharan's field- and context-sensitive, refinement-based points-to analysis. This extension allows construction of a context-sensitive call-graph on-the-fly:
This variant of Sridharan's algorithms represents the maximum degree of precision and efficiency that we aim to implement and evaluate in the lab phase.
A summary of the entire approach of Sridharan is contained in his PLDI 2006 article [ Sridharan & Bodik 2006 ]. You can use it as a relatively concise overview of what your colleagues will present before your talk.
The details are in his PhD thesis [ Sridharan 2007 ]:
CFL-Reachability as a solution to the “unrealizable path” problem is introduced by Reps: PDF, Citation
The “unrealizable paths” problem that arises if context-sensitive analysis is viewed as graph reachability is described in an earlier paper of Reps & Horowitz & Sagiv: PDF, Citation.
The first complete version of the talk will be presented (to GK) on Friday, Oct 01, 2010 at 14:30. We will then discuss open issues and once these are resolve, fine-tuning of the contents and presentation.