[Soot-list] Regarding Call Graph
Steven Arzt
Steven.Arzt at cased.de
Wed Sep 2 09:21:40 EDT 2015
Hi John,
Algorithm 1 is implemented in the InfoflowProblem class. Algorithm 2 is implemented in the BackwardsInfoflowProblem class. Both classes are much more involved in the actual implementation than one might guess from the simplified description in the paper, though.
FlowDroid’s type-sensitive taint propagation is implemented inside the flow functions. The access paths store propagated type information and the flow functions propagate these types and math them when encountering a call site. This feature was not designed to be used by custom code, though. Using FlowDroid to generate a dummy main method and then creating a callgraph from that using SPARK is fairly easy, but there is no such easy way to re-use the type propagator, because it is very tightly integrated into the data flow engine.
Best regards,
Steven
Von: John Ng [mailto:john.ng162014 at gmail.com]
Gesendet: Mittwoch, 2. September 2015 15:14
An: Steven Arzt
Cc: soot-list at cs.mcgill.ca
Betreff: Re: [Soot-list] Regarding Call Graph
Hi Steven,
Thank you very much for the quick response and the wonderful explanation.
It seems Paddle hasn'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 & 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?
Best Regards,
John
On Wed, Sep 2, 2015 at 3:34 AM, Steven Arzt <Steven.Arzt at cased.de> wrote:
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/03d5b751/attachment-0001.html
More information about the Soot-list
mailing list