[Soot-list] VASCO: An Interprocedural Data Flow Analysis Framework using Value Contexts

[Marc-André Laverdière-Papineau]

Wow. This looks awesome!

Thanks a lot for sharing with everybody.

Marc-André Laverdière-Papineau
Doctorant - PhD Candidate

On 04/24/2013 01:38 PM, Rohan Padhye wrote:
> Hello all,
>
> There seemed to be one or two people who recently asked for data flow
> results of an inter-procedural analysis which are parametrized by
> contexts. For those who are interested, I would like to share with you
> the code of an inter-procedural framework for Soot that we have been
> working on that uses value-sensitive contexts.
>
> Source code: https://github.com/rohanpadhye/vasco
> API docs: http://rohanpadhye.github.io/vasco/apidocs
> Paper (submitted to SOAP '13): http://arxiv.org/pdf/1304.6274v1.pdf
>
> Why did we need to develop a new framework when a nice tool like Heros
> exists already? Well, the difficulties we faced were not with Heros but
> with the underlying approach of graph-reachability based solutions which
> depend on distributive flow functions (IFDS/IDE).
>
> Specifically, we wanted an inter-procedural framework for performing
> heap analyses (e.g. points-to analysis, heap reference analysis using
> access graphs, various types of shape analysis, etc). Most of these
> analyses have non-distributive flow functions and hence cannot be
> directly encoded as IFDS/IDE problems.
>
> Also, one of our requirements was that the data flow solution should be
> context-sensitive, whereas graph-reachability based methods give a
> meet-over-valid-paths solution by default. Handling results differently
> for different contexts opens up many new opportunities for optimization
> and performing precise secondary analyses that depend on results of a
> primary analysis (e.g. heap liveness analysis that requires alias
> analysis).
>
> Thus, our framework is built around the concept of using data flow
> values themselves as contexts, which provides a fully context-sensitive
> solution even in the presence of recursion (i.e. no k-limited bounding),
> provided the lattice is finite, and has found to be efficient in
> practice. The algorithm used is mainly an adaptation of Sharir and
> Pnueli's tabulation method of the functional approach as well as Khedker
> and Karkare's CC '08 paper on a modified call strings approach.
>
> Although the second requirement may be (partially) addressed in Heros by
> tweaking the "domain" of the IFDS/IDE problem, this loses the
> intuitiveness and clarity of the data flow problem model, and the
> resulting solution complexity also increases as a cubic factor of the
> domain extensions.
>
> We've aimed to ensure intuitiveness by designing the classes on the
> lines of Soot's intra-procedural data flow framework, which makes it
> easy to lift an existing intra-procedural analysis to an
> inter-procedural scope.
>
> The source code also includes an implementation of a Flow and Context
> Sensitive Pointer Analysis (FCPA) using this framework, which we used
> for constructing a context-sensitive call graph, resulting in phenomenal
> reductions in inter-procedural paths (call chains) that would directly
> affect the precision and efficiency of any inter-procedural analysis,
> whether using our framework or otherwise.
>
> Suggestions and comments are welcome.
>
> Regards,
>
> Rohan Padhye
>