[Soot-list] FlowDroid - full set of nodes for calculating diameter of control-flow graph?

[kaunder]

Hi Steven,

Thanks for the reply! I had not considered the implications of the Android
lifecycle and the fact that there isn't a single entry point as there would
be with normal Java code. It looks like I will be able to get what I need
from the single method, extracted via iCfg.getOrCreateUnitGraph(method).

Thank you again for your help

Katie

On 19 November 2015 at 02:38, Steven Arzt <Steven.Arzt at cased.de> wrote:

> Hi Katie,
>
>
>
> If you are looking for paths, what are the start and end points of these
> paths? In a normal Java program, you could say that you take the beginning
> of the main method as the start point of all your paths and the point(s)
> where the control flow leaves the main method as the end point(s) of your
> paths. In Android, there is no such single entry point into the app that
> could serve as a natural start and end point of a path. That’s also why
> there is no easy access to “all paths” in FlowDroid: It’s totally unclear
> what such paths should look like. We do have a couple of path notations,
> though:
>
>
>
> 1.       Taint propagation paths. They start at a source and go wherever
> the respective taint goes.
>
> 2.       Source-to-sink paths: A subset of the taint propagation paths,
> namely those that end up in a sink.
>
>
>
> Unrelated to data flows, there are also other path notations one could
> think of:
>
>
>
> 1.       Control flow paths through a single method. That’s available in
> the iCfg.
>
> 2.       Control flow paths from the beginning of the dummy main method
> which emulates the Android lifecycle to the end of that dummy main method.
> You can build that from the iCfg. When using those, you however need to be
> really careful about the semantics of your results (i.e., what does such a
> path represent in the end?). This would essentially be a single trajectory
> through the app given a specific interaction of the Android OS and the user
> with the app. Usually, the set of those trajectories is of infinite size.
>
>
>
> Best regards,
>
>   Steven
>
>
>
> *Von:* soot-list-bounces at CS.McGill.CA [mailto:
> soot-list-bounces at CS.McGill.CA] *Im Auftrag von *kaunder
> *Gesendet:* Donnerstag, 19. November 2015 06:51
> *An:* soot-list at CS.McGill.CA
> *Betreff:* [Soot-list] FlowDroid - full set of nodes for calculating
> diameter of control-flow graph?
>
>
>
> Hello All,
>
>
>
> Another FlowDroid question for you. I'm interested in calculating the
> diameter (i.e. the longest path out of the set of shortest paths between
> all nodes) of the control-flow graph that FlowDroid uses for it's analysis.
> I have been working under the assumption that this graph is the variable
> iCfg of type InfoflowCFG in the class soot.jimple.infoflow.Infoflow.java.
> However, InfoflowCFG does not appear to have a way to access the set of all
> nodes in the control flow graph.
>
>
>
> The closest thing I've found appears to be the sets of Units returned by
> InfoflowCFG.getNonCallEndNodes() and InfoflowCFG.getNonCallStartNodes(),
> but clearly this is not the full set of nodes in the graph. I made an
> attempt at an approximate calculation by running the Floyd-Warshall
> algorithm on the union of these two sets, but my calculated diameter was
> significantly smaller than I would expect so I assume that I'm still
> missing a lot of nodes.
>
>
>
> Is there a way to get access the set of all nodes in the graph, so that I
> can use them in a shortest-path algorithm? Or is there another class that I
> should be looking at?
>
>
>
> Thanks and regards,
>
>
>
> Katie
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: https://mailman.CS.McGill.CA/pipermail/soot-list/attachments/20151119/d59a8c73/attachment.html