[Soot-list] Paddle's BDD Escape Analysis

[Khilan Gudka]

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();

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'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/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.mcgill.ca/pipermail/soot-list/attachments/20120104/4752058d/attachment.html 
-------------- 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/20120104/4752058d/attachment.zip