search

SVF-tools / SVF

Static Value-Flow Analysis Framework for Source Code
http://svf-tools.github.io/SVF/
Other
1.39k stars 436 forks source link

What is the best way to build a context-sensitive flow-insensitive analysis on top of SVF? #677

Open maemre opened 2 years ago

maemre commented 2 years ago

Hi @yuleisui ,

I want to build a context-sensitive and flow-insensitive analysis on SVF. Specifically, I want to make an Andersen-style analysis context sensitive by making objects on the stack, and on the heap context sensitive. I am interested in this combination to model potential effects of some program transformations (inlining, function duplication) on Andersen-style analysis. Does any of the approaches below (or another approach) sound good to you? Are there any gotchas I should be aware of?

As far as I can see, there are two possibilities:

  1. Effectively make a copy of the Andersen class that inherits from CondPTAImpl<ContextCond> (instead of BVDataPTAImpl and be careful about the assumptions Andersen makes about the backing set data structure. Issue #80 seems a bit relevant here, but I am not sure if/how I can parameterize SVFG to generate a call graph that would correspond to what would be built alongside the PTA I am trying to build. Edit: @mbarbar also noted that CondPTAImpl supports only mutable points-to data, which may prohibit some optimized variants of Andersen-style analysis.
  2. Another option is to clone objects as I go and adding them to the pool of objects to process, similar to how type-based heap cloning works (thanks to @mbarbar for suggesting this, as well as pointing out the potential performance advantage over the first option!). I think this would require generating/duplicating the constraints for the new object as I create it, or to maintain a map from the object to the associated constraints similar to the metadata maps in TypeBasedHeapCloning.
yuleisui commented 2 years ago

This is a very good question. I would suggest going for the first option.

In fact, SVF has a demand-driven context-sensitive pointer analysis using CondPTAImpl in the DDA folder (https://github.com/SVF-tools/SVF/blob/master/include/DDA/ContextDDA.h). You can have a look to get started with a similar data structure for whole-program context-sensitive analysis on top of a constraint graph rather than SVFG.

I don't think the optimization at this stage matters, but you can always map a CxtVar to a single ID to leverage the bit-vector-based points-to structure optimization from @mbarbar

mbarbar commented 2 years ago

To clarify some terminology, #80 mentions the SVFG only because he wanted a flow-sensitive analysis. The SVFG corresponds to the DUG in other literature.

maemre commented 2 years ago

Thank you for the hints, and keeping me from worrying about the SVFG! The analogy with the def-use graph really helps. I am looking into whether I can fit the flow-sensitive demand-driven analysis to my use case, and if it doesn't work then I'll go with the first option.