[Soot-list] pointer-analysis questions

[Ondrej Lhotak]

Hi Dan...

On Tue, Jun 06, 2006 at 04:14:06PM -0700, Dan Grossman wrote:
> 
> I have just installed Soot and spent the day reading tutorials, browsing 
> the source, glancing at mailing-list archives, etc.  So my apologies if 
> I am repeating common questions or have missed relevant documentation -- 
> specific pointers greatly appreciated.
> 
> 1. Spark "vs." Paddle?  Do I have this right:
>   * The technical differences are clear from the paper-trail: Paddle is 
> a highly-configurable context-sensitive framework built on top of BDDs, 
> whereas Spark supports 1-CFA or some object-sensitivity.
>   * Paddle is much less stable, so it's recommended only for those who 
> want to be on the bleeding-edge of pointer analysis.  It's not (yet?) 
> linked from the Soot web pages.

Almost right.

Spark does not support any context sensitivity. Any remnants of context
sensitivity that may be in Spark are incomplete and non-functional.
(The story behind this is that Paddle started out as Spark, to which
I started adding context sensitivity. People using Spark at the time
suggested I keep the old, simple Spark around before making the
complicating changes for context sensitivity. So, I spun off the
Spark I had at the time, and called the main development line Paddle.
Thus, some of the beginnings of context sensitivity are in what is
currently called Spark, but they are completed only in Paddle.)

At this point, Paddle is just about as stable as Spark, for both
meanings of "stable": I am no longer making major changes to its
design, and I have used it in enough experiments to have as much
confidence in its correctness as for Spark. I have a bit less confidence
in some of the interfaces that others have requested for post-processing
the results into their desired form, since I have not been using these
special-purpose interfaces, but the core analyses should be fine.

Paddle is more complicated than Spark, and requires Jedd to build,
although it can run in non-BDD mode. I recommend Spark for things
that don't require Paddle, just because it's simpler. But, for a
context-sensitive analysis, you probably need Paddle.

> 2. Here's a simplification of what I would like to do: Suppose there's a 
> special static method "foo" and I want a pointer-analysis that is 
> context-sensitive in the sense that it computes separate results for 
> when (one or more) "foo" calls are "on the stack" (foo has been called 
> but not yet returned) versus when no such calls are.  This is scalable 
> (it at most doubles the number of contexts), even though it supports 
> arbitrary stack depth "between foo and a program point".

This should be fairly easy to do with Paddle: you would need to write
a new StaticContextManager and VirtualContextManager to implement this
kind of context sensitivity, which shouldn't be more than a handful of
lines of code. As you say, this should be fairly scalable, and so should
run quite well even in non-BDD mode.

Ondrej

> So: Is modifying Spark's notion of "context" to support this 
> context-sensitivity (in addition to its other sensitivites) a reasonable 
> pursuit?  I think so, but thought it worth checking with the community. 
>  Would I be better off pursuing this work with Paddle instead?
> 
> Thanks in advance,
> Dan
> 
> _______________________________________________
> Soot-list mailing list
> Soot-list at sable.mcgill.ca
> http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
>