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[0]: path to the JDK classes (rt.jar, jce.jar,
jsse.jar, etc)
- args[1]: the directory containing the class files of
the program you want to analyze
- args[2]: 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.
5) Example:
java -Xmx2G -DMayAlias=spa -classpath MayAlias/bin
client.datarace.DataraceMain /path/to/rt.jar:/path/to/jce.jar:/path/to/jsse.jar
/path/to/target_program/bin target.Main
Since the analysis is based on a symbolic points-to graph, here are the
detailed steps to construct such a graph:
1) Setup
* 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();
m.buildSPG();
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.
You can contribute to this
project by sending bug reports, code patches, and suggestions. Please send your
inquiries to yan@cse.ohio-state.edu
or harry.g.xu@uci.edu.
We thank all of
the developers of the Soot program
analysis framework, without whom the research would not happen.
Last updated: July 24, 2013