[Soot-list] Soot/IFDS (Heros) and Call Graphs

[Eric Bodden]

Hello.

> I was working on developing inter-procedural analyses with Soot and had a
> couple of questions about using the Heroes IFDS/IDE solver:
>
> In Eric Bodden's SOAP'12 paper, it is mentioned that the super-graph is
> built on-the-fly. Is this referring to the fact that not all data flow facts
> from the domain need to be enumerated at once, or that the call-graph is
> built on the fly? As far as I can tell, the "JimpleBasedInterproceduralCFG"
> class currently uses context-insensitive queries on Soot's default call
> graph (CHA/SPARK).

What I meant in this paper is that Heros only constructs the portions
of the graph that are actually reachable from the starting node(s)
(0,s_0). Unreachable portions are never constructed. That is different
from the graphical representations you find in the IFDS paper. Also
the graph is not really stored explicitly but it's rather stored as a
set of summary functions. I guess that becomes clearer when reading
the actual IFDS paper (RHS'95).

> If the answer is the former for the above point, then is it possible to
> build a call graph on-the-fly using some sort of flow-sensitive points-to
> analysis? Or is there a restriction due to the framework interface
> "heros.InterproceduralCFG"? Or is there any restriction due to the nature of
> the IFDS algorithm?

Heros simply expects some implementation of the InterproceduralCFG
interface. Usually we construct the call graph upfront. Constructing
it on the fly would mean that you'd need to compute points-to
information at the same time you compute your normal IFDS/IDE results.
This would lead to an indirect recursion, I guess: build a bit of the
CG, evaluate the flow functions, build a bit more of the CG, etc. ...
The current solver is not set up to do this but I guess it could be
extended to accommodate this.

Eric