SDA SE Wiki

For sufficient precision, points-to-analysis (PTA) must be based on a realistic heap-abstraction, that is, a sufficiently precise representation of objects and fields.

This talk will introduce the distinction between field-based and field-sensitive PTA approaches. In particular, it will present the context-insensitive, field-sensitive approach of Sridharan and its efficient implementation as a demand-driven and refinement-based algorithm. Here a few main keywords:

• Challenge: Field-based versus field-sensitive
• Approach overview: Field accesses as balanced parantheses
• Graph representation
• Formalism: PTA as a grammar
• Algorithm
• Examples
• Benchmark results
• Open issues (questions to discuss in the lab)

This variant of Sridharan's algorithms represents the minimal degree of precision and efficiency that we aim to implement and evaluate in the lab phase. Much of it has already been implemented in a previous diploma thesis. We shall start by making ourselves familiar with the existing implementation, evaluating its performance on relevant benchmarks and then refining it towards the more precise context-sensitive and on-the-fly algorithms.

A summary of the entire approach of Sridharan is contained in his PLDI 2006 article [ Sridharan & Bodik 2006 ].

The details are in his PhD thesis [ Sridharan 2007 ]:

• Chapter 3 is an overview of all the three PTA variants (field-sensitive, context-sensitive, on-the-fly)
  • In particular, Section 3.1 and 3.2 (page 42-53) introduces the basic (field-sensitive) approach
• Chapter 4 is an in-depth discussion of the field-sensitive, refinement-based variant
  • In particular, Section 4 (page 139-176) elaborates the context-insensitive, field-senstive approach.

The first complete version of the talk will be presented (to GK) on Thursday, Sept 30, 2010 at 13:00. We will then discuss open issues and once these are resolve, fine-tuning of the contents and presentation.