[Soot-list] Context sensitive analysis introduction?

[Ondrej Lhotak]

On Sun, Mar 06, 2005 at 11:34:22AM +0100, Helge Jensen wrote:
> I am doing binding-time analysis in soot, and am about to extend it to
> be context-sensitive.
> 
> For this I need some pointers to where i can read about how the
> context-sensitivity in soot works, some slides, a small sample analysis
> maybe?
> 
> Specificly I need:
>    - a context-sensitive reads/writes analysis
>    - to understand how to obtain the context main runs in
>    - given the current context: a set of (Method,Context) that a Units
> method-invocation could possibly dispatch to.
> 
> I can see that at least some of that functionality is available, but it
> would really help with a small example and maybe some docs on the
> architecture/design for context sensitivity in soot, for the big picture
> to fall into place.

Soot doesn't really have much of a big picture design for context
sensitivity.

That said, at one point, I extended the callgraph in
soot.jimple.toolkits.callgraph.CallGraph to be able to deal with
context-sensitive call edges by just substituting a (method, context)
pair for each method. So, for example, you can get all edges out of a
specific (method, context) pair using the edgesOutOf method.

soot.jimple.toolkits.callgraph.CallGraph is a structure designed for
querying call graphs, but it doesn't build them itself. The cg.cha and
cg.spark phases put the context-insensitive call graph that they create
into a soot.jimple.toolkits.callgraph.CallGraph in the Scene for use by
other analyses.

At one point, I thought I would make Paddle just put its
context-sensitive edges into the call graph in the Scene, but that
messes up existing analyses that expect a context-insensitive call
graph. Also, I don't think the s.j.t.c.CallGraph structure is
necessarily appropriate for context-sensitive call graphs, because they
may be huge, so some more space-efficient implicit representation may be
better.

Paddle has an internal call graph interface
(soot.jimple.paddle.AbsCallGraph) which supports only the functionality
specifically needed inside Paddle. After Paddle runs, you can get the
AbsCallGraph it built from soot.jimple.paddle.Results.v().callGraph().
One of the things you can get from that is an iterator over all the
context-sensitive call edges from the csEdges() method. You can then
index and query the edges in whatever specific way your application
requires.

If the s.j.t.c.CallGraph interface is appealing to people wanting to
query context-sensitive call graphs, perhaps at some point, it would be
worthwhile to make an adapter over the Paddle AbsCallGraph implementing
the same interface.

Ondrej

> Anyone got any references to something?
> 
> -- 
> Helge
> 
> _______________________________________________
> Soot-list mailing list
> Soot-list at sable.mcgill.ca
> http://www.sable.mcgill.ca/mailman/listinfo/soot-list
>