[Soot-list] Paddle's BDD Escape Analysis

[Ondrej Lhotak]

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