[cfe-dev] Cross Translational Unit Analysis in Clang Static Analyzer

[Kareem Khazem via cfe-dev]

On 2017-03-31 15:28:49, Dániel Krupp via cfe-dev wrote:
> Would be  happy to hear your opinion and experiences with this feature
> and would appreciate your help in reviewing the patch.

Hi all,

thanks again to Dániel, Gábor, Aleksei and everyone for this work. I'm
going to brain-dump my experiences with the CTU analysis here for the
record. I'm also going to try and review patches when I get time.

At Google, we were trying to perform CTU analysis on Magenta, a
microkernel for the new Fuchsia operating system [0,1]. I wrote a
document describing these efforts; most of the document has been
published here [2]. This might help folks who want to get started
running CTU analysis, although it was last updated in December 2016.

We found several bugs that could not be caught by single-translation
unit analysis. There were both bugs at the *caller* side, where a value
set in a called function (in a different TU) caused an error in the
caller; and also bugs in the *callee* side, where a value passed in as a
parameter from a different TU caused a bug in a called function.

During EuroLLVM, it was mentioned that the analysis is truncated at a
call depth of 4. In practice, I found that the analyser read on average
between 15-20 ASTs from disk for each function that it analysed, and
never more than about 100. (Note, if every function calls 2 functions in
a different TU, then for that function we must load 2 + 4 + 8 + 16 = 30
ASTs from disk). It might be possible to find more bugs by increasing
the call depth, though I didn't experiment with this.

The main problem I ran into was incomplete implementation of
ASTImporter.cpp. In particular, whenever the analyser tries to load an
AST node from disk that does not have an implementation in the AST
Importer, the analyser crashes. So for us, most of the work involved
adding support for the AST nodes that were present in our codebase, but
which were not in the Importer. These were mostly obscure C++
constructs. Note that in some cases, support for those already exists in
Aleksei's patch but not in Gábor's; so it's always worth looking at
Aleksei's patch too.

Note, I'm no longer affiliated with Google (I was just interning there),
but I'm happy to answer whatever questions I can.

[0] https://fuchsia.googlesource.com
[1] https://lwn.net/Articles/718267
[2] https://fuchsia.googlesource.com/docs/+/411f08616d395b02e2d2861c34cace9942dee134/ctu_analysis.md

thanks!

-- 
Kareem
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 659 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20170331/b082f506/attachment.sig>