[cfe-dev] Checker for Context Sensitive Call Graph

[Ted Kremenek]

On Apr 25, 2011, at 6:17 PM, Tarun Sethi wrote:

> Hi,
> 
> I have been trying to write a checker using PreStmt<CallExpr> interface to get a context sensitive call graph with the SVal's of each argument at each call node (in other words with CheckerContext at that node).
> 
> To explain in detail, for example in the code below, I would like my checker to be invoked 3 times each for malloc and free calls (because they have been called thrice through alloc_mem), rather than just once for malloc and free, which is currently the case in PreStmt<CallExpr> and evalCall checkers including the MallocChecker. 

What you are describing is inter-procedural analysis.  There are a variety of options here, none of which have been really implemented:

1) ExprEngine supports "inlining" of basic function calls directly into the ExplodedGraph of the caller.  This isn't a fully general solution (intractable in general), but will work for some cases.

2) Support summary-based analysis, which possibly retains this information for callgraph construction.

There has been some work on (1).  No work has been done on (2) yet.

Incidentally, why treat all_mem() any differently than malloc()?  In your callgraph, why not just have the call graph include alloc_mem?

> 
> void* alloc_mem(int x) {
> 
>        void *p = malloc(x);
>        return p;
> }
> 
> int main() {
> 
>      void *x = alloc_mem(4);
>      free(x);
>      x = alloc_mem(8);
>      free(x);
>      x = alloc_mem(12);
>      free(x);
>      return 0;
> }
> 
> 
> And as per my understanding, I do not just want to walk/traverse the AST as I would not get the state (checkerContext, SVal) at the call expression. 

It ultimately depends on what kind of data you are trying to collect.

The SVals represent value semantics extracted from doing a path-sensitive analysis.  This allows it to resolve some control-dependencies, and possibly give you more accurate information about function pointers.  It is not, however, required to do a context-sensitive analysis for callgraph construction.  If you don't need to do any kind of flow-sensitive analysis, then your analysis is going to be far more scalable if you just walk the AST.  If all the context-sensitivity you care about is just looking at callee-caller pairs, then that's probably all you need in most case.  You can then not use the Checker interface at all (which may be analysis overkill).

> I also want to visit the calls made from within the member functions of the classes, in object oriented langs, which I could not find in any of the checkers.

ExprEngine analyses the bodies of methods just like any other function body.  There's nothing special you need to do.

Calls to C++ methods, however, require different preVisit methods to handle the different kinds of AST node kinds.  Check out the Iterator checker for some examples.



Cheers,
Ted