[cfe-dev] [analyzer] Whole Program Analysis - Full Call Graph

[Phil Camp via cfe-dev]

Hello Aleksei.

Thank you very much for the reply and details of your proof-of-concept 
approach. I will certainly look at the implementation you detailed.

My requirements may be somewhat simpler as I'm mainly concerned with 
analysis of calls to a well defined SDK API. As long as I can securely 
find those in the call-graph, it may be ok to ignore some of the more 
edge-case problems.

Thanks again.

Phil

On 01/12/2015 12:23, Aleksei Sidorin via cfe-dev wrote:
> Hello Phil,
>
> I met this problem while implementing inter-unit analysis 
> proof-of-concept for CSA. I'll describe my solution here. As I 
> understand, this problem cannot be solved inside CSA, so I used 
> multi-step approach.
>
> First, for all translation units we should collect a list of 
> 'required' and 'exported' functions. To build a list of required 
> declarations, we iterate over AST to find CallExprs that use callee 
> decl without body. To build a list of exported declarations we just 
> dump all the functions that are visible externally.
>
> I used a simple text signature of function as 
> mangled_name at target_triple_arch for dumping. I used additional arch 
> mark to distinguish between functions in multi-arch builds.
>
> Note that some function may be defined in a headers. One should not 
> merge them because they may have different bodies due to macro 
> expansion. These calls are local and the approach below should solve 
> this problem.
>
> After this, we have two lists. List of required functions is just a 
> list of signatures; list of external functions is a list of entries 
> looking like a map: function_signature::file_name at target_triple_arch. 
> Final export map contains items from exported functions whose key was 
> listed in required functions. Resulting mapping is an inter-unit call 
> graph.
>
> You may also need to use C++ mangling-style for C if you build 
> multiple projects that may contain functions with the same name. 
> However, if you need to do this, you may need more complicated approach.
>
> You can take a look at the code. This code also dumps local calls but 
> marks as local explicitly so it may be used to build a whole program 
> call graph. You can find our github repo at 
> https://github.com/haoNoQ/clang/tree/summary-ipa-draft. See 
> tools/clang-func-mapping 
> (https://github.com/haoNoQ/clang/blob/summary-ipa-draft/tools/clang-func-mapping/ClangFnMapGen.cpp) 
> and tools/scan-build/xtu-analyze.py 
> (https://github.com/haoNoQ/clang/blob/summary-ipa-draft/tools/scan-build/xtu-analyze.py) 
> for some code.
>
> Hope it will help.
>
>> Hello cfe-dev,
>>
>> I am interested in researching possible static analyzer schemes on whole
>> program states. Initially I would like to build a whole program call
>> graph. I plan to develop program wide checkers for calls to a
>> proprietary SDK. To begin with these checkers would rely on simple call
>> graph/AST based analysis rather than ‘full’ static analysis. These
>> checkers would include items like simple flow analysis of SDK calls that
>> should occur in a particular order (e.g. open()/read()/write()/close()).
>> I would be very grateful if anyone can offer any guidance as to how to
>> achieve this.
>>
>> My initial thoughts are to use the current AST call graph feature within
>> clang. I would create a checker that builds and serialises the call
>> graph to a file for each source file. I plan to add this serialisation
>> to the clang CallGraph class along the lines of the current AST
>> serialisation. The available serialised call graph files would
>> subsequently be read and a merged, creating a full program graph  (or
>> partial program graph if the whole program has not been serialised).
>>
>> I have a couple of questions regarding development style:
>>
>> a) Would the clang CallGraph class be the best place for the
>> serialisation, or would it better to place it in the checker(s)?
>>
>> b) For the read and merge process, should this be an external utility or
>> use the regular clang executable?
>>
>> Any feedback most welcome. Thank you for your time.
>