Re: Limiting whole-program analysis

[Helge Jensen <jensen@slog.dk>]

(uups... forgot to reply-all, so the list didn't get the mail)

Ondrej Lhotak wrote:

> On Thu, Jun 03, 2004 at 09:51:45AM +0200, Helge Jensen wrote:

First of all, thanks for you elaborate explanation and your interest. It
is valued.

> For debugging, I use an even smaller class library, from JDK 1.1.8. With
> that one, your example runs in 11 seconds. That should be acceptable.
> Other people working on points-to (not with Spark) use GNU Classpath,
> which is even smaller. I haven't tried analyzing it with Spark.

This still shows that the user is unable to convey known limitations of
the analysed code to soot in whole-program mode. I realize that there is
no canonical way of doing this and think that the workarounds you have
shown are reasonable. And, of course, I can still just hack at the
framework when i need to ignore stuff, for the time being.

> In Java, there is no such thing as a small program with just a few
> classes. If you run a Hello World program and use the JVM's profiler
> interface to see what's going on, you will see that about 500 distinct
> methods are actually executed. Of course, at least all of these must
> appear in any conservative static call graph.

Of course. But for what i'm planning to do it's reasonable to impose
restrictions on the behaviour of the input. For starters, I am not
allowing catch'es of exceptions, threads, ...

Especially in partial evalution it's widely accepted to simulate calls
"external" to the partial-evaluation by substituting implementations
that (in a very simple way) just models the expected alias and
binding-time behaviours of the real code that can be used at runtime.

You are actually doing the same by switching JRE implementations.

The "implicit"-hack is doing it somewhat more agressively, but things
should works as long as the input is just plain JAVA without any
callbacks and side-effects through the non-analysed parts.

> If you want the analysis to still be conservative, simple things break
> down.

That's OK. if I can just state which behaviour will result in breakdown.

When I have the simple things working, I can begin considering what to
do about the advanced things (like exceptions, threads, ...). Untill
then I really just want the analysis to complete fast, even if that
limits the set of valid inputs, so I can actually get some work done :)

For figuring out which options I needed to pass to soot to generate the
right amount of points-to information for my purposes, what the
different output-formats looked like, what dava was and so on, I must
have run soot >50 times on a small example program. Then it makes a
_lot_ of difference if it completes in 2 seconds or 2 minutes :)

> For example, consider a program with a GUI containing a button.
[...snip...]

Fortunatly, the programs i'll be analysing will not do this kind of
stuff (atleast for now).

> There is some published work on analyzing programs and making
> conservative assumptions about the library, particularly by Atanas
> Rountev. I have some ideas about this as well, but none of them have
> been implemented.

Thats a nice topic, and I would like to do some work on that... when my
thesis is complete :)

--
Helge