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

[Rohan Padhye]

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