[Soot-list] Paddle's BDD Escape Analysis

[Ondrej Lhotak]

On Fri, Jan 20, 2012 at 05:03:35PM +0000, Khilan Gudka wrote:
> 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.

It could improve precision indirectly by improving precision of the
points-to analysis results. I would not expect any huge improvements
in typical cases.

Ondrej

> 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
>     >
> 
>