Re: Limiting whole-program analysis

[Venkatesh Prasad Ranganath <vranganath@sbcglobal.net>]

Helge Jensen wrote:

> (uups... forgot to reply-all, so the list didn't get the mail)
>
> Ondrej Lhotak wrote:
>
>>> With this disabled, which programs would yield inconsistent
>>> analysis results? can it be summed up as programs that uses
>>> specific features of the java language/runtime-system?
>>
>>
>>
>> Well, even for Hello World, you'll get a call graph which
>> excludes things that are executed at run-time.
>
>
> That's OK, If these things have side-effects/callbacks to the
> analysed code, I consider it an invalid input program.
>
>> However, particularly for debugging, I'd guess most of your
>> results would be close enough to conservative.
>
>
> They are spot-on for my purposes.
>
>> The things I can think of that you'd be ignoring are
>
>> class loading altogether, privileged actions, finalization,
>> reflection, threads.
>
>
> I figured somthing along those lines.
>
>> Out of curiosity, how many methods are reachable if you remove
>> the implicit()?
>
>
> Few, 5 to be exact, in the attached test program program: A.main,
> X.<init>, java.lang.Object.<init>, java.lang.Object.finalize,
> X.toString
>
[I did not use reply-all when I mailed Lhotak and Jensen.]

Shouldn't the class initializers be included?

I get the following call graph on for the attached program through OFA
(home grown points-to analysis/call graph constructor).

<A: void main(java.lang.String[])
<java.lang.Object: void <clinit>()>
<java.lang.Object: void registerNatives()>
<java.lang.String: void <clinit>()>
<java.lang.String$CaseInsensitiveComparator: void
<init>(java.lang.String$1)>
<java.lang.String$CaseInsensitiveComparator: void <init>()>
<java.lang.Object: void <init>()>
<X: void <init>(X)>
<X: void <init>()>
<X: java.lang.String toString()>

Note that Implicit calls from native code (methods such as finalize())
or based on values returned from native code are not captured as the
analysis does not (yet) try to complete the system.
However,  all of this (program start to end in flow-sensitive,
field-sensitive, and context-insensitive mode) happens in 7 seconds on
a Linux box running on 1.4GHz Athlon XP Processor with 512MB RAM.

So, I was wondering if the soot developers had some numbers from
benchmarks that can be used to compare SPARK and OFA?

>> It would useful to see which specific methods in implicit() cause
>> your call graph to become unbearably large.
>
>
> Perhaps, it's really quite easy to try. Maybe you could get
> more/better quality info from just uncommenting those lines
> yourself and running soot with "-f grimp -app A -w -p cg
> verbose:true;context:1cfa -p cg.spark
> on,dump-solution:true,add-tags:true -p jap.pat on -p bb.lp
> unsplit-original-locals:true" as I do.
>
> Note, that if I do NOT implement X.ToString, the call-graph
> explodes again... probably because of the implementation of
> object.toString?
>
>> Anyway, for some of our applications, it was necessary to have a
>> call graph that is absolutely complete, so there was a lot of
>> effort put into ensuring that in Spark. Completeness was a higher
>> priority than having a very small call graph by ignoring unlikely
>> but possible things.
>
>
> I can see the reasons why you did what you did, and I acknowledge
> them. I just need things to work faster, and I'm satisfied with the
> situation I'm in now, without implict().
>
>
> ----------------------------------------------------------------------
>
>
> class X { X x; public X() {} public X(X x) { this.x = x; } public
> String toString() { return "X"; } } public class A extends Object {
>  public static void main(String[] args) { X x1 = new X(null); X x2
> = new X(); x2.x = x2; X x_x1 = x1; X x_x1_x = x1.x; X x_x2_x =
> x2.x; X x_dyn; if ( args.length > 0 ) x_dyn = x1.x; else x_dyn =
> x2; x_dyn.toString(); } }



--

Venkatesh Prasad Ranganath,
Dept. Computing and Information Science,
Kansas State University, US.
web: http://www.cis.ksu.edu/~rvprasad