<div dir="ltr">Hi Steven,<div><br></div><div>Thank you very much for the quick response and the wonderful explanation. </div><div><br></div><div>It seems Paddle hasn&#39;t been supported for a while so I prefer to stick with SPARK. I actually am using FlowDroid to perform analyses. Can you let me know which classes in the source implement the Algorithm 1 &amp; 2 in your FlowDroid paper? It seems that  you applied the technique which maintains context sensitivity to the IFDS algorithm. However, I also need a context-sensitive call graph, can you please let me know which is the most efficient way to implement a layer context-sensitive on top of SPARK or there is any existing implementation that I am not aware of?</div><div><br></div><div>Best Regards,</div><div>John</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Sep 2, 2015 at 3:34 AM, Steven Arzt <span dir="ltr">&lt;<a href="mailto:Steven.Arzt@cased.de" target="_blank">Steven.Arzt@cased.de</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div lang="DE" link="blue" vlink="purple"><div><p class="MsoNormal"><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d">Hi John,<u></u><u></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d"><u></u> <u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d">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:<u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d"><u></u> <u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d">void foo()  {<u></u><u></u></span></p><p class="MsoNormal" style="text-indent:35.4pt"><span lang="EN-US" style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d">Iterator it = myList.iterator();<u></u><u></u></span></p><p class="MsoNormal" style="text-indent:35.4pt"><span lang="EN-US" style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d">doSth(it);<u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d">}<u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d"><u></u> <u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d">void doSth(Iterator it) {<u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d">                it.next();<u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d">}<u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d"><u></u> <u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d">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.<u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d"><u></u> <u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d">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.<u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d"><u></u> <u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d">I hope this helps a bit.<u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d"><u></u> <u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d">Best regards,<u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d">  Steven<u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d"><u></u> <u></u></span></p><p class="MsoNormal"><b><span lang="EN-US" style="font-size:10.0pt;font-family:&quot;Tahoma&quot;,&quot;sans-serif&quot;">Von:</span></b><span lang="EN-US" style="font-size:10.0pt;font-family:&quot;Tahoma&quot;,&quot;sans-serif&quot;"> <a href="mailto:soot-list-bounces@CS.McGill.CA" target="_blank">soot-list-bounces@CS.McGill.CA</a> [mailto:<a href="mailto:soot-list-bounces@CS.McGill.CA" target="_blank">soot-list-bounces@CS.McGill.CA</a>] <b>Im Auftrag von </b>John Ng<br><b>Gesendet:</b> Mit</span><span style="font-size:10.0pt;font-family:&quot;Tahoma&quot;,&quot;sans-serif&quot;">twoch, 2. September 2015 01:30<br><b>An:</b> <a href="mailto:soot-list@CS.McGill.CA" target="_blank">soot-list@CS.McGill.CA</a><br><b>Betreff:</b> [Soot-list] Regarding Call Graph<u></u><u></u></span></p><div><div class="h5"><p class="MsoNormal"><u></u> <u></u></p><div><div><p class="MsoNormal">Hello,<u></u><u></u></p></div><div><p class="MsoNormal"><u></u> <u></u></p></div><div><p class="MsoNormal">I have a class as follows:<u></u><u></u></p></div><div><p class="MsoNormal">------------------------<u></u><u></u></p></div><div><p class="MsoNormal">package testers;<u></u><u></u></p></div><div><p class="MsoNormal"><u></u> <u></u></p></div><div><p class="MsoNormal">import java.util.Iterator;<u></u><u></u></p></div><div><p class="MsoNormal"><u></u> <u></u></p></div><div><p class="MsoNormal">public class CallGraphs {<u></u><u></u></p></div><div><p class="MsoNormal"><u></u> <u></u></p></div><div><p class="MsoNormal">  Cell[] cells;<u></u><u></u></p></div><div><p class="MsoNormal"><u></u> <u></u></p></div><div><p class="MsoNormal">  class Cell {<u></u><u></u></p></div><div><p class="MsoNormal">    private int cell = 0;<u></u><u></u></p></div><div><p class="MsoNormal"><u></u> <u></u></p></div><div><p class="MsoNormal">    public Cell(int cell) {<u></u><u></u></p></div><div><p class="MsoNormal">      this.cell = cell;<u></u><u></u></p></div><div><p class="MsoNormal">    }<u></u><u></u></p></div><div><p class="MsoNormal"><u></u> <u></u></p></div><div><p class="MsoNormal">    public int getCell() {<u></u><u></u></p></div><div><p class="MsoNormal">      return cell;<u></u><u></u></p></div><div><p class="MsoNormal">    }<u></u><u></u></p></div><div><p class="MsoNormal">  }<u></u><u></u></p></div><div><p class="MsoNormal"><u></u> <u></u></p></div><div><p class="MsoNormal">  class CellIterator implements Iterator&lt;Cell&gt; {<u></u><u></u></p></div><div><p class="MsoNormal">    private int idx, end;<u></u><u></u></p></div><div><p class="MsoNormal"><u></u> <u></u></p></div><div><p class="MsoNormal">    public CellIterator(int idx, int end) {<u></u><u></u></p></div><div><p class="MsoNormal">      this.idx = idx;<u></u><u></u></p></div><div><p class="MsoNormal">      this.end = end;<u></u><u></u></p></div><div><p class="MsoNormal">    }<u></u><u></u></p></div><div><p class="MsoNormal"><u></u> <u></u></p></div><div><p class="MsoNormal">    public boolean hasNext() {<u></u><u></u></p></div><div><p class="MsoNormal">      return idx &lt; end;<u></u><u></u></p></div><div><p class="MsoNormal">    }<u></u><u></u></p></div><div><p class="MsoNormal"><u></u> <u></u></p></div><div><p class="MsoNormal">    public Cell next() {<u></u><u></u></p></div><div><p class="MsoNormal">      return cells[idx++];<u></u><u></u></p></div><div><p class="MsoNormal">    }<u></u><u></u></p></div><div><p class="MsoNormal"><u></u> <u></u></p></div><div><p class="MsoNormal">    public void remove() {<u></u><u></u></p></div><div><p class="MsoNormal">    }<u></u><u></u></p></div><div><p class="MsoNormal">  }<u></u><u></u></p></div><div><p class="MsoNormal"><u></u> <u></u></p></div><div><p class="MsoNormal">  void testIterator() {<u></u><u></u></p></div><div><p class="MsoNormal">    cells = new Cell[5];<u></u><u></u></p></div><div><p class="MsoNormal">    Cell c0 = new Cell(0);<u></u><u></u></p></div><div><p class="MsoNormal">    Cell c1 = new Cell(1);<u></u><u></u></p></div><div><p class="MsoNormal">    Cell c2 = new Cell(2);<u></u><u></u></p></div><div><p class="MsoNormal">    cells[0] = c0;<u></u><u></u></p></div><div><p class="MsoNormal">    cells[1] = c1;<u></u><u></u></p></div><div><p class="MsoNormal">    cells[2] = c2;<u></u><u></u></p></div><div><p class="MsoNormal">    Iterator&lt;Cell&gt; iterator = new CellIterator(0, 3);<u></u><u></u></p></div><div><p class="MsoNormal">    while (iterator.hasNext()) {<u></u><u></u></p></div><div><p class="MsoNormal">      Cell c = iterator.next();<u></u><u></u></p></div><div><p class="MsoNormal">      System.out.println(c.getCell());<u></u><u></u></p></div><div><p class="MsoNormal">    }<u></u><u></u></p></div><div><p class="MsoNormal">  }<u></u><u></u></p></div><div><p class="MsoNormal"><u></u> <u></u></p></div><div><p class="MsoNormal">  public static void main(String[] args) {<u></u><u></u></p></div><div><p class="MsoNormal">    CallGraphs cG = new CallGraphs();<u></u><u></u></p></div><div><p class="MsoNormal">    cG.testIterator();<u></u><u></u></p></div><div><p class="MsoNormal">  }<u></u><u></u></p></div><div><p class="MsoNormal">}<u></u><u></u></p></div><div><p class="MsoNormal">---------------------------------<u></u><u></u></p></div><div><p class="MsoNormal"><u></u> <u></u></p></div><div><p class="MsoNormal">I used Soot to build a call graph for the class. The call graph is exploded because of the method: &lt;testers.CallGraphs$CellIterator: java.lang.Object next()&gt;. <u></u><u></u></p></div><div><p class="MsoNormal">The method  &lt;testers.CallGraphs$CellIterator: java.lang.Object next()&gt; is the target method of &lt;testers.CallGraphs$CellIterator: testers.CallGraphs$Cell next()&gt;. The tool reported that this method is called by many other methods such as:<u></u><u></u></p></div><div><p class="MsoNormal">&lt;sun.security.util.DisabledAlgorithmConstraints$KeySizeConstraints: boolean disables(java.security.Key)&gt;<u></u><u></u></p></div><div><p class="MsoNormal">&lt;sun.misc.ProxyGenerator$ProxyMethod: sun.misc.ProxyGenerator$MethodInfo generateMethod()&gt;<u></u><u></u></p></div><div><p class="MsoNormal">&lt;sun.misc.ProxyGenerator$MethodInfo: void write(java.io.DataOutputStream)&gt;<u></u><u></u></p></div><div><p class="MsoNormal">&lt;sun.misc.ProxyGenerator$ConstantPool: void write(java.io.OutputStream)&gt;<u></u><u></u></p></div><div><p class="MsoNormal">&lt;sun.misc.ProxyGenerator: sun.misc.ProxyGenerator$MethodInfo generateStaticInitializer()&gt;<u></u><u></u></p></div><div><p class="MsoNormal">&lt;sun.misc.ProxyGenerator: sun.misc.ProxyGenerator$MethodInfo generateStaticInitializer()&gt;<u></u><u></u></p></div><div><p class="MsoNormal">&lt;sun.misc.ProxyGenerator: void addProxyMethod(java.lang.reflect.Method,java.lang.Class)&gt;<u></u><u></u></p></div><div><p class="MsoNormal">&lt;sun.security.x509.ExtendedKeyUsageExtension: java.util.List getExtendedKeyUsage()&gt;<u></u><u></u></p></div><div><p class="MsoNormal">&lt;java.security.KeyFactory: java.security.KeyFactorySpi nextSpi(java.security.KeyFactorySpi)&gt;<u></u><u></u></p></div><div><p class="MsoNormal">&lt;sun.misc.ProxyGenerator: void checkReturnTypes(java.util.List)&gt;<u></u><u></u></p></div><div><p class="MsoNormal">&lt;sun.misc.ProxyGenerator: byte[] generateClassFile()&gt;<u></u><u></u></p></div><div><p class="MsoNormal">&lt;sun.misc.ProxyGenerator: byte[] generateClassFile()&gt;<u></u><u></u></p></div><div><p class="MsoNormal">....<u></u><u></u></p></div><div><p class="MsoNormal">            <u></u><u></u></p></div><div><p class="MsoNormal">It seems the result is not correct. Can you let me know how to deal with this case.<u></u><u></u></p></div><div><p class="MsoNormal"><u></u> <u></u></p></div><div><p class="MsoNormal">Thank you very much! <u></u><u></u></p></div><div><p class="MsoNormal"><u></u> <u></u></p></div><div><p class="MsoNormal">Best,<u></u><u></u></p></div><div><p class="MsoNormal">John<u></u><u></u></p></div></div></div></div></div></div></blockquote></div><br></div>