Implementing a flow and context-sensitive pointer analysis

[Machiry]

Hi @yuleisui,

Let's say I want to add context-sensitivity to the flow-analysis. Precisely, I want context-sensitive heap and stack objects.

I am thinking of the following implementation plan, Could you please let me know if this looks okay?

1) Modify MemModel.h to add context information to all the PAGNodes. Basically, build a context-sensitive PAG: This will take care of creating the correct constraint graph.

2) Add new pointer analysis to use CondPTAImpl that uses context.

Does this plan look valid? Or there is a better way to implement this?

[yuleisui]

Hi Machiry,

If you want a flow- and context-sensitive analysis. You may wish to use SVFG by parameterizing every method. Actually no need to modify MemModel.h. If you have the original SVFG, you can create a centralized the parameterize(node, method, context) to create context-sensitive SVFGNode for data-flow analysis.

Yes, CondPTAImpl is designed for context-sensitive analysis.

[Machiry]

You mean, create a new class lets say CtxSVFGNode (derived class of SVFGNode) and parameterize it with Context (one possible context would be: ContextCond) along with other SVFG node types like: CtxStmtSVFGNode etc.

And create a context-sensitive SVFG by reusing SVFGBuilder? I should also create a new MemSSA class that uses CondPTAImpl right?

[yuleisui]

ContextCond is the context condition consisting of a list of callsite ids. You can reuse SVFGBuilder and no need to change MemSSA.

You can create multiple CtxSVFGNode derived from a context-insensitive (original) SVFGNode based on the calling contexts. The previously computed incoming/outgoing value-flows on the original SVFG can be redirected to context-sensitive SVFGNodes.

A context-sensitive SVFG should be fairly easy to build using a few hundreds of lines of code.

[Machiry]

I agree. My only concern is handling/converting memory objects i.e., heap and stack objects into their context-sensitive counterparts while handling Indirect edges. Do you have any suggestions?

[yuleisui]

Every pointer should be parameterized by the context of its containing (current) method. The object should be parameterized using the context of the method who allocates this object.

You can handle indirect calls following our existing flow-sensitive analysis to build callgraph on-the-fly. https://github.com/SVF-tools/SVF/blob/31c86b143fc6796bb7f9c51645217f1c09d7e8a5/lib/WPA/FlowSensitive.cpp#L534

When you discover a new edge, you will definitely have the callsite id information there by querying the PTACallGraphEdge.

May I know what are you trying to do for implementing an FSCS pointer analysis?

[Machiry]

I guess I didn't make myself clear. I am trying to think aloud about the problem of building context-sensitive SVFG (with heap cloning) from context-insensitive SVFG.

The problem is handling the addition of IndirectVFEdge, as the edge requires points to information, but the points to information available is context-insensitive (i.e., no heap cloning). So, my concern was how can we add context sensitivity to the points to information of the indirect edges.

If your question is "why" we are doing this: We are working on a project, which requires us to be context-sensitive as we need to differentiate between objects allocated at different contexts.

[yuleisui]

I think a simple solution for your case is to build a pre-computed callgraph and SVFG using Andersen's results. Forget about the on-the-fly one. The pre-computed one will give you conservative results. But considering your purpose, I think it is already good enough and also simple enough to be implemented.

See this option to get the precomputed SVFG with all call edges resolved. https://github.com/SVF-tools/SVF/blob/31c86b143fc6796bb7f9c51645217f1c09d7e8a5/lib/MSSA/SVFGBuilder.cpp#L38