<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"><head><meta http-equiv=Content-Type content="text/html; charset=utf-8"><meta name=Generator content="Microsoft Word 14 (filtered medium)"><style><!--
/* Font Definitions */
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Tahoma;
panose-1:2 11 6 4 3 5 4 4 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman","serif";}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
span.E-MailFormatvorlage17
{mso-style-type:personal-reply;
font-family:"Calibri","sans-serif";
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri","sans-serif";
mso-fareast-language:EN-US;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:70.85pt 70.85pt 2.0cm 70.85pt;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]--></head><body lang=DE link=blue vlink=purple><div class=WordSection1><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'>Hi John,<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span lang=EN-US style='font-size:11.0pt;font-family:"Calibri","sans-serif";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:<o:p></o:p></span></p><p class=MsoNormal><span lang=EN-US style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span lang=EN-US style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'>void foo() {<o:p></o:p></span></p><p class=MsoNormal style='text-indent:35.4pt'><span lang=EN-US style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'>Iterator it = myList.iterator();<o:p></o:p></span></p><p class=MsoNormal style='text-indent:35.4pt'><span lang=EN-US style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'>doSth(it);<o:p></o:p></span></p><p class=MsoNormal><span lang=EN-US style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'>}<o:p></o:p></span></p><p class=MsoNormal><span lang=EN-US style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span lang=EN-US style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'>void doSth(Iterator it) {<o:p></o:p></span></p><p class=MsoNormal><span lang=EN-US style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'> it.next();<o:p></o:p></span></p><p class=MsoNormal><span lang=EN-US style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'>}<o:p></o:p></span></p><p class=MsoNormal><span lang=EN-US style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span lang=EN-US style='font-size:11.0pt;font-family:"Calibri","sans-serif";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.<o:p></o:p></span></p><p class=MsoNormal><span lang=EN-US style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span lang=EN-US style='font-size:11.0pt;font-family:"Calibri","sans-serif";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.<o:p></o:p></span></p><p class=MsoNormal><span lang=EN-US style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span lang=EN-US style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'>I hope this helps a bit.<o:p></o:p></span></p><p class=MsoNormal><span lang=EN-US style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span lang=EN-US style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'>Best regards,<o:p></o:p></span></p><p class=MsoNormal><span lang=EN-US style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'> Steven<o:p></o:p></span></p><p class=MsoNormal><span lang=EN-US style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><b><span lang=EN-US style='font-size:10.0pt;font-family:"Tahoma","sans-serif"'>Von:</span></b><span lang=EN-US style='font-size:10.0pt;font-family:"Tahoma","sans-serif"'> soot-list-bounces@CS.McGill.CA [mailto:soot-list-bounces@CS.McGill.CA] <b>Im Auftrag von </b>John Ng<br><b>Gesendet:</b> Mit</span><span style='font-size:10.0pt;font-family:"Tahoma","sans-serif"'>twoch, 2. September 2015 01:30<br><b>An:</b> soot-list@CS.McGill.CA<br><b>Betreff:</b> [Soot-list] Regarding Call Graph<o:p></o:p></span></p><p class=MsoNormal><o:p> </o:p></p><div><div><p class=MsoNormal>Hello,<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>I have a class as follows:<o:p></o:p></p></div><div><p class=MsoNormal>------------------------<o:p></o:p></p></div><div><p class=MsoNormal>package testers;<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>import java.util.Iterator;<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>public class CallGraphs {<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal> Cell[] cells;<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal> class Cell {<o:p></o:p></p></div><div><p class=MsoNormal> private int cell = 0;<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal> public Cell(int cell) {<o:p></o:p></p></div><div><p class=MsoNormal> this.cell = cell;<o:p></o:p></p></div><div><p class=MsoNormal> }<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal> public int getCell() {<o:p></o:p></p></div><div><p class=MsoNormal> return cell;<o:p></o:p></p></div><div><p class=MsoNormal> }<o:p></o:p></p></div><div><p class=MsoNormal> }<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal> class CellIterator implements Iterator<Cell> {<o:p></o:p></p></div><div><p class=MsoNormal> private int idx, end;<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal> public CellIterator(int idx, int end) {<o:p></o:p></p></div><div><p class=MsoNormal> this.idx = idx;<o:p></o:p></p></div><div><p class=MsoNormal> this.end = end;<o:p></o:p></p></div><div><p class=MsoNormal> }<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal> public boolean hasNext() {<o:p></o:p></p></div><div><p class=MsoNormal> return idx < end;<o:p></o:p></p></div><div><p class=MsoNormal> }<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal> public Cell next() {<o:p></o:p></p></div><div><p class=MsoNormal> return cells[idx++];<o:p></o:p></p></div><div><p class=MsoNormal> }<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal> public void remove() {<o:p></o:p></p></div><div><p class=MsoNormal> }<o:p></o:p></p></div><div><p class=MsoNormal> }<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal> void testIterator() {<o:p></o:p></p></div><div><p class=MsoNormal> cells = new Cell[5];<o:p></o:p></p></div><div><p class=MsoNormal> Cell c0 = new Cell(0);<o:p></o:p></p></div><div><p class=MsoNormal> Cell c1 = new Cell(1);<o:p></o:p></p></div><div><p class=MsoNormal> Cell c2 = new Cell(2);<o:p></o:p></p></div><div><p class=MsoNormal> cells[0] = c0;<o:p></o:p></p></div><div><p class=MsoNormal> cells[1] = c1;<o:p></o:p></p></div><div><p class=MsoNormal> cells[2] = c2;<o:p></o:p></p></div><div><p class=MsoNormal> Iterator<Cell> iterator = new CellIterator(0, 3);<o:p></o:p></p></div><div><p class=MsoNormal> while (iterator.hasNext()) {<o:p></o:p></p></div><div><p class=MsoNormal> Cell c = iterator.next();<o:p></o:p></p></div><div><p class=MsoNormal> System.out.println(c.getCell());<o:p></o:p></p></div><div><p class=MsoNormal> }<o:p></o:p></p></div><div><p class=MsoNormal> }<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal> public static void main(String[] args) {<o:p></o:p></p></div><div><p class=MsoNormal> CallGraphs cG = new CallGraphs();<o:p></o:p></p></div><div><p class=MsoNormal> cG.testIterator();<o:p></o:p></p></div><div><p class=MsoNormal> }<o:p></o:p></p></div><div><p class=MsoNormal>}<o:p></o:p></p></div><div><p class=MsoNormal>---------------------------------<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></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: <testers.CallGraphs$CellIterator: java.lang.Object next()>. <o:p></o:p></p></div><div><p class=MsoNormal>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:<o:p></o:p></p></div><div><p class=MsoNormal><sun.security.util.DisabledAlgorithmConstraints$KeySizeConstraints: boolean disables(java.security.Key)><o:p></o:p></p></div><div><p class=MsoNormal><sun.misc.ProxyGenerator$ProxyMethod: sun.misc.ProxyGenerator$MethodInfo generateMethod()><o:p></o:p></p></div><div><p class=MsoNormal><sun.misc.ProxyGenerator$MethodInfo: void write(java.io.DataOutputStream)><o:p></o:p></p></div><div><p class=MsoNormal><sun.misc.ProxyGenerator$ConstantPool: void write(java.io.OutputStream)><o:p></o:p></p></div><div><p class=MsoNormal><sun.misc.ProxyGenerator: sun.misc.ProxyGenerator$MethodInfo generateStaticInitializer()><o:p></o:p></p></div><div><p class=MsoNormal><sun.misc.ProxyGenerator: sun.misc.ProxyGenerator$MethodInfo generateStaticInitializer()><o:p></o:p></p></div><div><p class=MsoNormal><sun.misc.ProxyGenerator: void addProxyMethod(java.lang.reflect.Method,java.lang.Class)><o:p></o:p></p></div><div><p class=MsoNormal><sun.security.x509.ExtendedKeyUsageExtension: java.util.List getExtendedKeyUsage()><o:p></o:p></p></div><div><p class=MsoNormal><java.security.KeyFactory: java.security.KeyFactorySpi nextSpi(java.security.KeyFactorySpi)><o:p></o:p></p></div><div><p class=MsoNormal><sun.misc.ProxyGenerator: void checkReturnTypes(java.util.List)><o:p></o:p></p></div><div><p class=MsoNormal><sun.misc.ProxyGenerator: byte[] generateClassFile()><o:p></o:p></p></div><div><p class=MsoNormal><sun.misc.ProxyGenerator: byte[] generateClassFile()><o:p></o:p></p></div><div><p class=MsoNormal>....<o:p></o:p></p></div><div><p class=MsoNormal> <o:p></o:p></p></div><div><p class=MsoNormal>It seems the result is not correct. Can you let me know how to deal with this case.<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>Thank you very much! <o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>Best,<o:p></o:p></p></div><div><p class=MsoNormal>John<o:p></o:p></p></div></div></div></body></html>