[Soot-list] Stack overflow when generating call graph

Mon Jul 21 16:32:56 EDT 2008

The Buddy backend is written in C, so it matters how exactly it was
compiled. I compiled it with XP and Java 1.6.0_07. It may be that the
resulting DLL is not binary compatible with other versions of Java
and/or Windows. I do not use Windows regularly, so I do not know for
sure. If you need the Buddy backend, it is most likely to work if
you compile it from source for the version of Windows and Java that you
are running.

But if you do not insist on Buddy, it is easier to get the JavaBDD
backend working. It is slower than Buddy, but purely Java, so it
does not have these binary compatibility issues. To run Paddle
with the JavaBDD backend, use the option -p cg.paddle backend:javabdd.

If you are not doing a context-sensitive analysis, then it is unlikely
that Paddle and BDDs will reduce your memory requirements. The
context-insensitive call graph built by Paddle and Spark is small
relative to the amount of memory needed to store all the generated
Jimple, which is the same regardless of which framework you use to
build the call graph.

Can you be more specific about "the world is fairly large"? And how much
memory do you have?

Ondrej

On Mon, Jul 21, 2008 at 08:39:56AM -0700, Eric Bodden wrote:
> Hmmm, yes judging from the error I suspect some binary
> incompatibility. I don't know much about paddle. Maybe Ondrej can help
> with that?
> 
> Eric
> 
> 2008/7/21 Marc Eaddy <me133 at columbia.edu>:
> > Hi Eric,
> >
> >        Thank you so much for your advice!  I really appreciate it.
> >
> >        After spending a day trying to get paddle to work, and overcoming
> > numerous obstacles, the following exception pushed me to the brink of
> > madness:
> >
> > Exception in thread "main" java.lang.UnsatisfiedLinkError:
> > C:\APPS\Soot\jedd-0.4\runtime\lib\jeddbuddy.dll: Invalid access to memory
> > location
> >        at java.lang.ClassLoader$NativeLibrary.load(Native Method)
> >        at java.lang.ClassLoader.loadLibrary0(ClassLoader.java:1751)
> >        at java.lang.ClassLoader.loadLibrary(ClassLoader.java:1676)
> >        at java.lang.Runtime.loadLibrary0(Runtime.java:823)
> >        at java.lang.System.loadLibrary(System.java:1030)
> >        at jedd.internal.BuddyBackend.init(BuddyBackend.java:37)
> >        at jedd.internal.Backend.init(Backend.java:35)
> >        at jedd.internal.Jedd.setBackend(Jedd.java:37)
> >        at jedd.Jedd.setBackend(Jedd.java:78)
> >        at soot.jimple.paddle.PaddleScene.setupJedd(PaddleScene.java:77)
> >        at soot.jimple.paddle.PaddleScene.setup(PaddleScene.java:1272)
> >        at
> > soot.jimple.paddle.PaddleTransformer.setup(PaddleTransformer.java:84)
> >        at
> > soot.jimple.paddle.PaddleTransformer.internalTransform(PaddleTransformer.jav
> > a:45)
> >        at soot.SceneTransformer.transform(SceneTransformer.java:39)
> >        at
> > edu.columbia.concerntagger.pdgraph.SootCallGraphBuilder.getCallGraph(SootCal
> > lGraphBuilder.java:216)
> >        at
> > edu.columbia.concerntagger.pdgraph.PDGraphBuilder.buildGraph(PDGraphBuilder.
> > java:85)
> >        at
> > edu.columbia.concerntagger.PruneDependencyAnalyzer.setup(PruneDependencyAnal
> > yzer.java:53)
> >        at
> > edu.columbia.concerntagger.PruneDependencyAnalyzer.performAnalysis(PruneDepe
> > ndencyAnalyzer.java:41)
> >        at edu.columbia.concerntagger.EntryPoint.start(EntryPoint.java:33)
> >        at edu.columbia.concerntagger.Main.main(Main.java:7)
> >
> >        (BTW, I'm running on Windows Vista SP1.)
> >
> >        Having never seen this before, I suppose it could be: jeddbuddy.dll
> > not compatible with Vista, jeddbuddy.dll not playing nice with memory,
> > jeddbuddy.dll depends on missing/incompatible DLL, etc. etc.  If you have
> > any idea what the problem is or even how I can start troubleshooting, please
> > let me know!  Meanwhile, I'll keep playing around with config options and
> > install more memory. :)
> >
> >        One thing that seems odd in all of this is that I have a 4 GB page
> > file (swap file).  So how can I be running out of memory?  BTW, I used -Xss
> > but to no avail.
> >
> > Cheers,
> >
> > \\Marc
> >
> >> -----Original Message-----
> >> From: eric.bodden at googlemail.com [mailto:eric.bodden at googlemail.com] On
> >> Behalf Of Eric Bodden
> >> Sent: Friday, July 11, 2008 7:15 PM
> >> To: me133 at columbia.edu
> >> Cc: soot-list at sable.mcgill.ca
> >> Subject: Re: [Soot-list] Stack overflow when generating call graph
> >>
> >> Hi Marc.
> >>
> >> > 1. Is there any way to config cg so that it doesn't create
> >> edges/nodes for
> >> > non-application program elements (e.g., system libraries)?  Based on
> >> a
> >> > previous post, my guess is no, since doing whole program analysis
> >> always
> >> > pulls in the world for completenes.  The problem is that the world is
> >> fairly
> >> > large.
> >>
> >> No, as far as I know there isn't because that would be highly unsound:
> >> library code can call back into application classes.
> >>
> >> > 2. Is there any other way/flag/setting/option to config cg to
> >> optimize
> >> > memory usage?
> >>
> >> It's usually highly optimized as it is. You may want to try paddle,
> >> though. It uses a BDD representation instead of the explicit graph
> >> representation that spark has. That makes it more memory-efficient.
> >>
> >> > 3. Otherwise, can a Soot developer give me some suggestions on how I
> >> can
> >> > modify the cg code?  For example, if we call into a system library
> >> but there
> >> > is never a call back into the application classes, we could prune the
> >> system
> >> > library dag.
> >>
> >> I am sure that's possible somehow but I am not the right person to
> >> answer that one.
> >>
> >> However, first you should try something else: -Xms and -Xmx increase
> >> the heap size, not the stack size, so setting these will not help you
> >> avoiding a stack overflow. -Xss is what you want.
> >>
> >> 1.5GB heap is also not a lot for the kind of analysis you want to do.
> >> It might be enough with manual fine-tuning of the callgraph but maybe
> >> not without. Depends on the benchmark, really.
> >>
> >> Eric
> >>
> >>
> >>
> >> --
> >> Eric Bodden
> >> Sable Research Group
> >> McGill University, Montréal, Canada
> >
> >
> 
> 
> 
> -- 
> Eric Bodden
> Sable Research Group
> McGill University, Montréal, Canada
> _______________________________________________
> Soot-list mailing list
> Soot-list at sable.mcgill.ca
> http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
> 