[Soot-list] Paddle's BDD Escape Analysis

[Khilan Gudka]

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 --------------
A non-text attachment was scrubbed...
Name: bddescapetests.zip
Type: application/zip
Size: 2065 bytes
Desc: not available
Url : http://mailman.cs.mcgill.ca/pipermail/soot-list/attachments/20120119/bc380ff9/attachment-0001.zip