[Soot-list] Regarding Call Graph

[Steven Arzt]

Hi John,

 

This happens because the SPARK callgraph builder is context-insensitive. In other words, it does not distinguish the different calling contexts. If the type of a variable x is java.lang.Iterator, a call to x.next() can go out to every implementation of the Iterator interface. If SPARK knows the type of the base variable, it can reduce the number of possible callees – but this is not always the case. Take the following example:

 

void foo()  {

Iterator it = myList.iterator();

doSth(it);

}

 

void doSth(Iterator it) {

                it.next();

}

 

The variable “it” does not have a single specialized type in “doSth” since “doSth” can be called from a variety of places with different actual types for the first argument (and we assume that we’re actually in a larger code base where this happens, so a simple reduction wouldn’t work). The only way to get a more precise call graph would be to track the context: If we came from the call site at line 2 in “foo”, we know that for this call to “doSth” (and only this call), the type of “it” is whatever list iterator we got back in line 1 of “foo”. For some other call to “doSth”, we may have a different actual type.

 

In general, there are two ways to solve the issue: Firstly, you can switch to such a context-sensitive callgraph algorithm. Soot supports Paddle which should do the job. Have a look at the command-line reference and the paper on Paddle for the details. Secondly, you can also stay with SPARK and layer context-sensitivity on top. This is what we did in FlowDroid, but which has its own advantages and drawbacks.

 

I hope this helps a bit.

 

Best regards,

  Steven

 

Von: soot-list-bounces at CS.McGill.CA [mailto:soot-list-bounces at CS.McGill.CA] Im Auftrag von John Ng
Gesendet: Mittwoch, 2. September 2015 01:30
An: soot-list at CS.McGill.CA
Betreff: [Soot-list] Regarding Call Graph

 

Hello,

 

I have a class as follows:

------------------------

package testers;

 

import java.util.Iterator;

 

public class CallGraphs {

 

  Cell[] cells;

 

  class Cell {

    private int cell = 0;

 

    public Cell(int cell) {

      this.cell = cell;

    }

 

    public int getCell() {

      return cell;

    }

  }

 

  class CellIterator implements Iterator<Cell> {

    private int idx, end;

 

    public CellIterator(int idx, int end) {

      this.idx = idx;

      this.end = end;

    }

 

    public boolean hasNext() {

      return idx < end;

    }

 

    public Cell next() {

      return cells[idx++];

    }

 

    public void remove() {

    }

  }

 

  void testIterator() {

    cells = new Cell[5];

    Cell c0 = new Cell(0);

    Cell c1 = new Cell(1);

    Cell c2 = new Cell(2);

    cells[0] = c0;

    cells[1] = c1;

    cells[2] = c2;

    Iterator<Cell> iterator = new CellIterator(0, 3);

    while (iterator.hasNext()) {

      Cell c = iterator.next();

      System.out.println(c.getCell());

    }

  }

 

  public static void main(String[] args) {

    CallGraphs cG = new CallGraphs();

    cG.testIterator();

  }

}

---------------------------------

 

I used Soot to build a call graph for the class. The call graph is exploded because of the method: <testers.CallGraphs$CellIterator: java.lang.Object next()>. 

The method  <testers.CallGraphs$CellIterator: java.lang.Object next()> is the target method of <testers.CallGraphs$CellIterator: testers.CallGraphs$Cell next()>. The tool reported that this method is called by many other methods such as:

<sun.security.util.DisabledAlgorithmConstraints$KeySizeConstraints: boolean disables(java.security.Key)>

<sun.misc.ProxyGenerator$ProxyMethod: sun.misc.ProxyGenerator$MethodInfo generateMethod()>

<sun.misc.ProxyGenerator$MethodInfo: void write(java.io.DataOutputStream)>

<sun.misc.ProxyGenerator$ConstantPool: void write(java.io.OutputStream)>

<sun.misc.ProxyGenerator: sun.misc.ProxyGenerator$MethodInfo generateStaticInitializer()>

<sun.misc.ProxyGenerator: sun.misc.ProxyGenerator$MethodInfo generateStaticInitializer()>

<sun.misc.ProxyGenerator: void addProxyMethod(java.lang.reflect.Method,java.lang.Class)>

<sun.security.x509.ExtendedKeyUsageExtension: java.util.List getExtendedKeyUsage()>

<java.security.KeyFactory: java.security.KeyFactorySpi nextSpi(java.security.KeyFactorySpi)>

<sun.misc.ProxyGenerator: void checkReturnTypes(java.util.List)>

<sun.misc.ProxyGenerator: byte[] generateClassFile()>

<sun.misc.ProxyGenerator: byte[] generateClassFile()>

....

            

It seems the result is not correct. Can you let me know how to deal with this case.

 

Thank you very much! 

 

Best,

John

-------------- next part --------------
An HTML attachment was scrubbed...
URL: https://mailman.CS.McGill.CA/pipermail/soot-list/attachments/20150902/368254f9/attachment-0001.html