Demand-driven Flow-sensitive Points-to Analysis

Points-to analysis is a static analysis technique to infer the variable references at runtime.Many demand-driven points-to analysis techniques are proposed to suit some environments bounded by strict limits of time and memory usage,such as just-in-time compilers and interactive development environments.Additionally,how to perform the demanddriven points-to analysis in a flow-sensitive manner,which helps achieve precise points-to relations for some variables of interest,still remains a challenge so far in practice due to the existence of strong flow and data dependencies in the large-scale software systems bringing about the difficulty in identifying all the program statements contributing to the points-to relations of the objective variables by static analysis.This paper proposes a demand-driven flow-sensitive points-to analysis,Seeker,to resolve the points-to relations of the objective variables of interest.Seeker adopts a novel flow-sensitive program representation approach by storing a points-to set for each variable at each program point along the control flow and preserving constraints between the points-to sets.Then according to a definition of context-free language reachability,Seeker could perform the demand-driven points-to analysis by exploring all the points-to paths accepted by the context-free language for all the points-to relations satisfying the constraints with respect to the objective variables.Seeker supports a demand-driven flow-sensitive context-sensitive points-to analysis as well.The analysis maintains a call stack in the process of exploring the points-to paths.The call stack could be used to infer the context of the currently traversed variables and the context validity could avoid some infeasible points-to paths.In order to support the field-sensitive points-to analysis,Seeker defines five conditions of alias checks for matching the load and store of the object instance fields.Each alias check depends on a points-to analysis with an independent degree of precision.Seeker combines the two points-to analyses and five alias check conditions to achieve different degrees of efficiency and precision of points-to analyses.Five points-to analyses are evaluated in two experiments.The experimental results show that Seeker improves the precision of the demand-driven points-to analysis as well as the efficiency of the flow-sensitive points-to analysis.