[Soot-list] Regarding Call Graph

[John Ng]

Hi Steven,

Got it! Thank you again for your help.

Best Regards,
John

On Wed, Sep 2, 2015 at 9:21 AM, Steven Arzt <Steven.Arzt at cased.de> wrote:

> 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/6efca57d/attachment.html