[Soot-list] Creating an abstracted call graph

[Eric Bodden]

Hello.

In order to speed up analysis I want to create an abstracted call graph,
i.e. this graph "A" should hold only certain nodes that satisfy a given
predicate. An edge between two such nodes in "A" shall exist whenever
there is a path between those nodes in the original call graph "G" and
in between there is no other node satisfying this predicate. (So
basically all nodes and edges not satisfying the predicate are collapsed
in a conservative way.)

Consider the following example, where [Mi] methods satisfy the
predicate:

[M1] -----> M2 ----> [M3]
  |                   ^|
  |                   ||
  |                   |v
  ------------------> M4 ---->[M5]

This would be abstracted to:

[M1] --------------> [M3]
  |                   |
  |                   |
  |                   v
  ------------------>[M5]

Note that a marked node [Mi] is connected to a marked node [Mj] iff it
is reachable over a path p in the original graph and no other marked
node is on p.

This could certainly be solved by first building the usual call graph
and then using Filter and TransitiveTargets. However, this would
probably be quite slow.

So I was wondering if it would be a better idea to modify/subclass
OnFlyCallGraphBuilder in such a way that it creates this abstracttion
right away. Basically, it would have modified in such a way that it only
adds edges between nodes that satisfy the predicate. If one was about to
add an edge ([M1],M2), then one would not add this edge (since M2 is not
marked) but rather store [M1] (hence deleting M2) and at the next time
one encounters a marked method (here [M3]) would add the edge
([M1},[M3]). At this time one would also have to adjust all incoming
edges which went to M2 to now point to M3.

This of course all only works if the call graph builder builds the graph
in a depth first order. Would it be safe to make such an assumption? Or
does anyone have a better idea of how to achive this?

Thanks a lot,

Eric

--
Eric Bodden
Sable Research Group, McGill University
Montreal, Canada