Efficient Algorithms for Context Sensitive Points-to Analysis

PhD Thesis Proposal Defence


Title: "Efficient Algorithms for Context Sensitive Points-to Analysis"

by

Mr. Xiao XIAO


Abstract:

Context sensitive points-to analysis, while significantly benefiting many 
static analysis techniques, is known to be difficult to scale to large 
programs. To make context sensitive points-to analysis practical to routine 
usages, we implement an efficient points-to engine GeomPTA, based on a novel 
technique, geometric encoding, to effectively capture the redundancy in 
representing a large number of contexts. Geometric encoding is capable of 
evaluating contexts of points-to constraints in the compressed form, but 
incurring much less space and time requirements compared to other compressing 
techniques such as BDD. GeomPTA can analyze large Java programs with JDK 1.6 
library 7.1X -- 81.9X faster than the worklist based 1-object-sensitive 
analysis in Paddle, and meanwhile its precision is comparable or better than 
1-object-sensitive analysis. This work has been published in ISSTA 2011 and our 
implementation of GeomPTA is now a part of the official distribution of Soot, 
which is a widely used framework for analyzing Java programs.

Although GeomPTA is much faster than other points-to algorithms, analyzing 
large programs still need tens of minutes and sometimes the memory usage 
exceeds the capacity of a commodity machine. Moreover, some queries, especially 
those require aliasing information, cannot be answered efficiently merely with 
the points-to information. Therefore, we develop a technique, Pestrie, to 
compress and persist the points-to and aliasing information, making pointer 
information easily reusable. Also, the compressed information is structured for 
fast querying. Empirically, Pestrie is 2.9X -- 123.6X faster than the 
demand-driven approaches based on points-to information. Our work of Pestrie 
has been accepted to PLDI 2014.


Date:			Friday, 30 May 2014

Time:                   9:30am - 11:30am

Venue:                  Room 3584
                         lifts 27/28

Committee Members:	Dr. Charles Zhang (Supervisor)
 			Prof. Fangzhen Lin (Chairperson)
 			Prof. Shing-Chi Cheung
 			Prof. Frederick Lochovsky


**** ALL are Welcome ****