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

[Rohan Padhye]

Hello,

Thanks for your reply. That answers my question.

On 03/29/2013 01:32 PM, Eric Bodden wrote:
> 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