[Soot-list] Spark's TypeManager patch

[Eric Bodden]

Thanks a lot Hamid.

Ondrej would you be able to have a look if this patch makes sense to
you? I don't think I am qualified to judge this...

Eric

On 7 January 2012 17:16, Hamid A. Toussi <hamid2c at gmail.com> wrote:
> Hello all,
>
> This patch makes TypeManager of Spark significantly faster specially
> in cases that on-fly-cg is turned off. TypeManager is responsible for
> making type masks before doing points-to sets propagation.
>
> Below is an overview:
> Making TypeManager faster by making type masks during a
> depth-first-traversal on the class hierarchy. First, type-masks of the
> leaves of Class Hierarchy are created and then the type mask of each
> type T is obtained by ORing type maks of T’s sub-types and setting the
> bit-numbers associated with Allocation Nodes of type T. Type-mask
> of each interface is achieved by ORing type-masks of its top-level
> concrete implementers. In fact, Reference types are visited in
> reversed-topological-order.
>
> A patch is attached that can be applied to
> soot/jimple/spark/internal/TypeManager.java.
> A Java class is also attached which can be used for testing this patch
> as follows:
>
>        Date startFTM = new Date();
>        FastTypeManager ftm = new FastTypeManager(pag);
>        if (!opts.ignore_types())
>                ftm.setFastHierarchy(Scene.v().getFastHierarchy());
>        ftm.makeTypeMask();
>        Date endFTM = new Date();
>        reportTime("Fast Type masks", startFTM, endFTM);
>
>        Set<AllocNode> set = new HashSet<AllocNode>();
>        for( Iterator tIt = Scene.v().getTypeNumberer().iterator();
> tIt.hasNext(); ) {
>            final Type t = (Type) tIt.next();
>            if( !(t instanceof RefLikeType) ) continue;
>            if( t instanceof AnySubType ) continue;
>            if( FastTypeManager.isUnresolved(t) ) continue;
>            BitVector orig = pag.getTypeManager().get(t);
>            BitVector nmask = ftm.get(t);
>            if (orig.equals(nmask)) continue;
>            BitVector temp = new BitVector(nmask);
>            temp.xor(orig);
>            for (BitSetIterator it = temp.iterator(); it.hasNext(); ) {
>                int n = it.next();
>                AllocNode an = (AllocNode)pag.getAllocNodeNumberer().get(n);
>                set.add(an);
>            }
>        }
>        for (AllocNode an : set) G.v().out.println(an);
>        for( Iterator tIt = Scene.v().getTypeNumberer().iterator();
> tIt.hasNext(); ) {
>            final Type t = (Type) tIt.next();
>            if( !(t instanceof RefLikeType) ) continue;
>            if( t instanceof AnySubType ) continue;
>            if( FastTypeManager.isUnresolved(t) ) continue;
>            BitVector orig = pag.getTypeManager().get(t);
>            BitVector nmask = ftm.get(t);
>            for (AllocNode an : set) {
>                if (orig.get(an.getNumber()) && !nmask.get(an.getNumber())) {
>                        G.v().out.print(t +" mask should contain "+an+": ");
>                        if (!(t instanceof RefType)) throw new RuntimeException();
>                        SootClass sc = ((RefType)t).getSootClass();
>                        if (!sc.isInterface()) G.v().out.print(" not interface");
>                        G.v().out.println(Scene.v().getFastHierarchy().
>                                        getAllImplementersOfInterface(sc).size());
>                }
>                if (!orig.get(an.getNumber()) && nmask.get(an.getNumber())) {
>                        G.v().out.println(t +" shouldn't contain "+an);
>                }
>            }
>        }
>
> Testing should be done before applying the patch using the original TypeManager.
>
> Thanks,
> Hamid
>
> _______________________________________________
> Soot-list mailing list
> Soot-list at sable.mcgill.ca
> http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
>



-- 
Eric Bodden, Ph.D., http://bodden.de/
Head of Secure Software Engineering Group at EC SPRIDE
Principal Investigator in Secure Services at CASED
Tel: +49 6151 16-75422    Fax: +49 6151 16-72051
Room 3.2.14, Mornewegstr. 30, 64293 Darmstadt