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

[Rohan Padhye]

Hi Eric,

To answer your questions:

1. Yes, definitely, although it might be better to let the project 
evolve independently until a stable point is reached - as there is still 
scope in order to change the API depending on public feedback. Once it 
is in the Soot code base I would assume the API would need to be more 
rigid as Soot users would expect compatibility across versions.

2. I haven't thought of this but will try to see if this fits. I guess 
the main difference is that Heros uses flow functions D -> Set<D> while 
Vasco uses A -> A, (where A corresponds to Set<D> in set problems) 
because non-distributive functions cannot be decomposed.

In any case, I was planning to add Soot-specific template classes that 
contain boilerplate code such as instantiating the correct types and 
using the default call graph to resolve invocations.

Thanks for your feedback, and let me know if you have any more suggestions.

Regards,
Rohan


On Wednesday 24 April 2013 11:30 PM, Bodden, Eric wrote:
> Hi Rohan.
>
> This sounds very interesting - thanks for the message!
>
> I wonder about two things…
>
> 1.) Would you be interested in integrating this into the Soot code base into the near future?
> 2.) Do you think it could be possible to define a common interface for flow functions that would work with Heros as well as with Vasco? I understand that your merge functions would be different but the transfer functions could probably implemented the same way (just guessing, though)…
>
> Cheers,
> Eric
>
>
>
>
> On 24.04.2013, at 19:38, Rohan Padhye <rohanpadhye at cse.iitb.ac.in>
>   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
>>
> --
> Eric Bodden, Ph.D., http://sse.ec-spride.de/ http://bodden.de/
> Head of Secure Software Engineering Group at EC SPRIDE
> Tel: +49 6151 16-75422    Fax: +49 6151 16-72051
> Room 3.2.14, Mornewegstr. 30, 64293 Darmstadt
>

-- 
Regards,
Rohan Padhye