[Soot-list] Paddle's BDD Escape Analysis

[Khilan Gudka]

Hey Ondrej

A quick question: would context-sensitivity affect the precision of the BDD
Escape Analysis? My inkling is that it wouldn't but i'm not sure.

Cheers

--
Khilan Gudka
PhD Student
Department of Computing
Imperial College London
http://www.doc.ic.ac.uk/~khilan/



On 19 January 2012 10:18, Khilan Gudka <khilan at doc.ic.ac.uk> wrote:

> Hey
>
> Ahh yes of course I totally forgot that Paddle can do
> context-insensitive too! I will use that.
>
> With regards to the Runnable field: the original version that finds
> all objects reachable from instances of Thread and it's subclasses
> doesn't find objects reachable from my Runnable class. I have attached
> the test cases.
>
> --
> Khilan Gudka
> PhD Student
> Department of Computing
> Imperial College London
> http://www.doc.ic.ac.uk/~khilan/
>
>
>
> On 18 January 2012 20:28, Ondrej Lhotak <olhotak at uwaterloo.ca> wrote:
> > On Wed, Jan 04, 2012 at 02:02:47PM +0000, Khilan Gudka wrote:
> >> Hi all
> >>
> >> I've been using the BDD escape analysis in paddle lately
> (src/soot/jimple/
> >> paddle/BDDEscapeAnalysis.jedd) to find objects that are thread-shared.
> However,
> >> i came across a couple of what seem to be bugs.
> >>
> >> First bug: does not consider Runnable classes
> >>
> >> The BDD escape analysis defines all objects reachable from static
> fields or the
> >> fields of classes that subclass Thread, as being thread-shared.
> However, this
> >> excludes fields of classes that only implement Runnable and whose
> instances are
> >> passed to Thread's constructor, as in:
> >>
> >> Runnable r = new MyRunnable();
> >> Thread t = new Thread(r);
> >> t.start();
> >
> > In this case, doesn't the Thread t store a copy of r in one of its
> > fields, so that it can call r.run() from t.start()? Wouldn't this
> > make all fields of r reachable from t?
> >
> >> As a result, it misses objects reachable from the fields of such
> classes.
> >>
> >> The fix for this I have found that works is to replace:
> >>
> >>         queue.add(Scene.v().getSootClass("java.lang.Thread"));
> >>
> >> with the two statements:
> >>
> >>         SootClass rc = Scene.v().getSootClass("java.lang.Runnable");
> >>         queue.addAll( fh.getAllImplementersOfInterface(rc) );
> >>
> >> Second bug: termination condition for fixed-point computation of
> thread-shared
> >> objects seems to be incorrect
> >>
> >> The analysis initialises the relation escapesThread with all Thread
> objects (or
> >> also Runnable objects if including the fix above) and then finds all
> objects
> >> that are transitively reachable. It is supposed to terminate when the
> relation
> >> stops growing. However, the termination condition does the opposite of
> looping
> >> while the relation does not grow.
> >>
> >> The loop (in propagate()) was:
> >>
> >>         while(true) {
> >>             if( escapesThread != (escapesThread |=
> escapesThread{A_objc,A_obj}
> >> <> fieldPt{A_basec,A_base}))
> >>                 break;
> >>         }
> >>
> >> Whereas i think it should be:
> >>
> >>         while(true) {
> >>             if( escapesThread == (escapesThread |=
> escapesThread{A_objc,A_obj}
> >> <> fieldPt{A_basec,A_base}))
> >>                 break;
> >>         }
> >
> > I have committed this fix to Subversion (r3639).
> >
> >> I've implemented these fixes and it gives the correct results.  Please
> find my
> >> test classes attached.
> >>
> >> Cheers
> >>
> >> --
> >> Khilan Gudka
> >> PhD Student
> >> Department of Computing
> >> Imperial College London
> >> http://www.doc.ic.ac.uk/~khilan/
> >>
> >>
> >
> >
> >> _______________________________________________
> >> Soot-list mailing list
> >> Soot-list at sable.mcgill.ca
> >> http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.mcgill.ca/pipermail/soot-list/attachments/20120120/0c854799/attachment.html