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

[Steven Arzt]

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