Software tools for program understanding, transformation, verification, and testing often require an efficient yet highly-precise alias analysis. Typically this is done by computing points-to information, from which alias queries can be answered. This paper presents a novel context-sensitive, demand-driven alias analysis for Java that achieves efficiencyby answering alias queries directly, instead of relying on an underlying points-to analysis. The analysis is formulated as a context-free-language (CFL) reachability problem over a language that models calling context sensitivity, and over another language that models field sensitivity (i.e., flow of reference values through fields of heap objects).
To improve analysis scalability, we propose to compute procedural reachability summaries online, during the CFL-reachability computation. This cannot be done indiscriminately, as the benefits of using the summary information do not necessarily outweigh the cost of computing it. Our approach selects for summarization only a subset of heavily-used methods (i.e., methods having a large number of incoming edges in the static call graph). We have performed a variety of studies on the proposed analysis. The experimental results show that, within the same time budget, the precision of the analysis is higher than that of a state-of-the-art highly-precise points-to analysis. In addition, the use of method summaries canlead to significant improvements in analysis performance.
This section shows how to use the demand-driven alias analysis.
1) Install soot...
2) See compile.sh for an example of how to compile the source code.
3) The main entrance of the tool is client.datarace.DataraceMain. It queries our analysis for the aliasing relationship between the base objects of each pair of heap load and store (e.g., x and y in "x.f = ...; ... =y.f") to simulate the first step of a data race detector.
Arguments to its main() method are:
- args: path to the JDK classes (rt.jar, jce.jar, jsse.jar, etc)
- args: the directory containing the class files of the program you want to analyze
- args: the main class of the program you want to analyze
4) The parameters of the analysis are defined by a set of properties set using the "-D" VM options. Details can be found in alias.Util.
The key property is MayAlias. When it is set to spa, it runs our alias analysis for the "data race" client. When it is set to spark, it runs an alias analysis by first performing a points-to analysis using Spark.
java -Xmx2G -DMayAlias=spa -classpath MayAlias/bin client.datarace.DataraceMain /path/to/rt.jar:/path/to/jce.jar:/path/to/jsse.jar
Since the analysis is based on a symbolic points-to graph, here are the detailed steps to construct such a graph:
* Configure soot to run spark. See an example in client.slicing.SlicerMain.main().
* When you run it, remember to put the bin directory before soot.jar in the classpath, e.g., "-classpath MayAlias/bin:soot.jar:jasmin.jar:polyglot.jar".
2) SPG construction
edu.osu.cse.pa.Main m = edu.osu.cse.pa.Main.v();
3) Use SPG
The following statement should be used to obtain an Intra-procedural SPG for method mtd:
SymbolicPointerGraph spg = SymbolicPointerGraph.v(mtd);
Inter-procedural SPG: it's simply intra-procedural SPGs connected by entry/exit edges, so there's no explicit representation for it. See an example in the method at edu.osu.cse.pa.Main:1025.
We thank all of the developers of the Soot program analysis framework, without whom the research would not happen. This material is based upon work supported by an IBM Ph.D. Fellowship and the National Science Foundation under Grants Number CCF-0546040 and CCF-1017204. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
Last updated: July 24, 2013