Seminar - Giga-Scale Exhaustive Points-To Analysis for Java in Under a Minute
School of Engineering and Computer Science Seminar
Speaker: A/Prof Jens Dietrich
Time:
Friday 9th October 2015 at 12:00 PM -
01:00 PM
Location:
Cotton Club,
Cotton 350
Abstract
Computing a precise points-to analysis for very large Java programs remains challenging despite the large body of re- search on points-to analysis. Any approach must solve an underlying dynamic graph reachability problem, for which the best algorithms have near-cubic worst-case runtime complexity, and, hence, previous work does not scale to programs with millions of lines of code.
In this work, we present a novel approach for solving the field-sensitive points-to problem for Java with the means of (1) a transitive-closure data-structure, and (2) a pre-computed set of potentially matching load/store pairs to accelerate the fix-point calculation. Experimentation on Java benchmarks validates the superior performance of our approach over the standard context-free language reachability implementations. Our approach computes a points-to index for the OpenJDK with over 1.5 billion tuples in under a minute.
This is work done in collaboration with Nicholas Hollingum from the University of Sydney and Bernhard Scholz from Oracle Labs Brisbane.