Home

Clang Cross Translational Unit (CTU) Static Analysis

The goal of this project is to improve the Clang Static Analyzer to be able to detect bugs that span multiple translation units (TUs). CTU analysis has been presented at EuroLLVM '17 (see the submitted Extended abstract for a more in-depth overview.)

Usage

To use CTU static analysis, you need to build a version of Clang which supports this feature. (See in Compilation.) Invoking the analyzer requires some special arguments (for an in-depth explanation, see Approach), we suggest using CodeChecker to invoke the analyzer. (See Cross Translation Unit analysis with CodeChecker.) scan-build-py is currently in the process of supporting CTU.

To analyze your project in strict mode (error on import failures) pass this parameter to clang:

-Werror=odr

Compilation

You can build a version of Clang by checking out our repository. The commits below tell you which LLVM and clang-tools-extra Git commit to use. To build clang, use the same procedure as usual, but with the commits described below.

Branches

The ctu-os branch collects commits and changes that are currently undergoing review by the community.

ctu-master and ctu-clang5 contain extra functionality that are continuously aimed to make CTU more viable, especially for C++ projects. -master follows the master version of Clang, while -clang5 is branched from the (currently release-candidated) Clang 5.0 version. We suggest using ctu-clang5 to build your Clang binaries from.

Which LLVM commit to use?

Branch ctu-clang5 -> LLVM commit 1368f4044e62cad4316da638d919a93fd3ac3fe6

Branch ctu-master -> LLVM commit 8a2fcfe5bef82d0c9249af74990ab54612f0dfc4

Branch ctu-os -> LLVM commit 9901953429f6e4519760d62761d5555cbafbd24f

If you want to use clang-tools-extra (e.g. clang-tidy):

Branch ctu-clang5 -> CTE commit bf75b14aaf1c50decb69deaa9cd0b46c2b3dddc6

Branch ctu-master -> CTE commit e790a95e604b660264b68d74af6d891e576fa42a

Branch ctu-os -> CTE commit b958885f42c75678a1eb8021301612935caf4fa1

#How to debug ASTImporter This CTU implementation heavily relies on the ASTImporter library as it imports the implementation of functions from foreign Translation Units.

It is essential that we get a valid AST after importing. It is a common fault that after import, the resulting merged AST gets corrupt which prevents Clang Static Analyzer to work properly on the AST.

Let's say that we want to verify how myclass.cpp and main.cpp is merged.

#Create the binary dump of the to-be-merged cpp file
clang -cc1 -emit-pch -o myclass.ast ./myclass.cpp
#Call Clang to merge create a textual dump of the ast
clang -cc1 -ast-merge ./myclass.ast -ast-dump main.cpp > merged_ast.txt

#create dump of the single file AST
cat myclass.cpp main.cpp > main_all.cpp
clang -cc1 -ast-dump main_all.cpp > single_file_ast.txt

#compare the ASTs using meld
meld ./single_file_ast.txt merged_ast.txt

any structural deviation in the `merged_ast.txt` is a potential fault in merge.

---

Approach

Today, Clang SA can perform (context-sensitive) inter-procedural analysis by "inlining" the called function into the callers context. This means that function parameters (including all constraints) are passed to the called function and the return value of the function is passed back to the caller. This works well for function calls within a translation unit, but when the symbolic execution reaches a function that is implemented in another TU, the analyzer engine handles it as "unknown".

In this project we are working on a method which enables CTU analysis by inlining external function definitions using Clang's existing ASTImporter functionality.

The EuroLLVM '17 Extended abstract contains a more in-depth description in white paper style.

Two-pass analysis

To perform the analysis we need to run Clang on the whole source code two times.

1st pass

We generate a binary AST dump (using Clang's -cc1 -emit-pch feature) of each TU into a temporary directory called preanalyze-dir. We collect the Unified Symbol Resolution (USR) of all externally linkable functions into a text file (externalFnMap.txt).

2nd pass

We run the Clang Static Analysis for all translation units, and if during inlining an externally defined function is reached, we look up the definition of that function in the corresponding AST file (based on the info in externalFnMap.txt) and import the function definition into the caller's context using the ASTImpoter library.

Results

We have run comparative analysis on several open source projects, such as openssl, FFMpeg, Git, Xerces, tmux, etc. We found several additional bugs compared to the normal (non cross-translation-unit capable) analysis.

See the results on cc.elte.hu/, with memory usage and result comparison.

Credits

This work is based on earlier work of Aleksei Sidorin, Artem Dergachev, et al. See http://lists.llvm.org/pipermail/cfe-dev/2015-October/045730.html.