Euro LLVM 17 Extended Abstract
Today Clang SA can perform (context-sensitive) inter-procedural analysis for C,C++ and Objective C files by ''inlining'' the called function into the callers context. This means that that the full calling context (assumptions about function parameters, global variables) is passed when analyzing the called function and then the assumptions about the returned value is passed back to the caller. This works well for function calls within a translation unit (TU), but when the symbolic execution reaches a function that is implemented in another TU, the analyzer engine skips the analysis of the called function definition. In particular, assumptions about references and pointers passed as function parameter get invalidated, and the return value of the function will be unknown. Loosing precision this way may lead to false positive and false negative findings.
The cross translation unit (CTU) feature would allow the analysis of called functions even if the definition of the function is external to the currently analyzed TU. This would allow detection of bugs in library functions stemming from incorrect usage (e.g. a library assumes that the user will free a memory block allocated by the library), and allows for more precise analysis in general of the caller if a TU external function is invoked (by not loosing assumptions).
We implemented (based on the prototype by A. Sidorin et al. [1]) the Cross Translation Unit analysis feature for Clang SA (4.0) and evaluated its performance on various open source projects. In our presentation we show that with the CTU feature we found many new true positive reports and eliminated some false positives in real open source projects. We show that while the total analysis time increases to 2-3 times, the execution remains scalable to the number of processors. We also point out how the analysis coverage changes that may lead to the loss of reports compared to the non-CTU baseline.
In this project we are working on a method which enables CTU analysis by inlining external function definitions using clang's existing ASTImporter (see http://clang.llvm.org/doxygen/classclang_1_1ASTImporter.html) functionality. One of our goals was to have minimal, isolated, and lightweight changes. We added less than 300 lines of code to the clang codebase (1200 lines of code including the support utilities that are separate executables and tests).
To perform the analysis we need to run clang on the whole source code two times.
2nd pass: The Clang Static Analyzer is run for all translation units. When during the analysis a TU external function is reached, the location of the definition of that function is looked up from in the function definition index and the definition is imported from the containing AST binary into the caller's context using the ASTImpoter library.
Traversal of the the control flow graph In the non-CTU analysis, functions that are not called from within the TU are analyzed first as ''top-level'' functions and all functions that are non-top-level are only analyzed in a call context (as they are called). In our CTU implementation, when analyzing a source file, we start the analysis from the same top-level functions as the original non-CTU method even if a given function is called from another TU (according to the global CFG). The reason for the choice of this strategy is that if the project contains test cases then library functions would only be analyzed with the concrete test values which would result in loss of generality of the analysis.
The source code of the prototype is available in this clang Github fork: https://github.com/dkrupp/clang/tree/ctu-master
We have analyzed many open source projects (ffmpeg, tmux, curl, vim, postgresql...) using CTU and found many new true positive reports.
In the following table we highlighted the most important findings from 3 C projects.
| Analyzed project | All Non-CTU Findings (baseline) | All CTU Findings | New CTU findings | Disappeared findings | Successfully analyzed | Failed to analyze | Analysis Time (baseline)[s] | Analysis Time XTU (1st Phase + 2nd Phase)[s] | Median of bug path length (BPL) in baseline | Median of BPL CTU | Median of BPL of new findings | Median of BPL of disappeared findings |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| FFMpeg | 339 | 399 | 101 | 41 | 1555 files | 8 files | 318 | 44+693 | 7 | 9 | 16 | 14 |
| TMux | 49 | 77 | 29 | 1 | 133 files | 0 files | 39 | 4+75 | 16 | 16 | 17 | 6 |
| Curl | 7 | 11 | 4 | 0 | 280 files | 13 files | 32 | 6.5+54 | 1 | 1 | 12 | n.a. |
The measurements were taken using clang 4.0 as the baseline and the same clang 4.0 with the CTU patch. Only the by default enabled (stable) checkers were switched on.
Quality of new results The new analysis found significant number of new results on all projects. The number of findings increased by 17% to 50%. We examined the new findings in detail and most of them are true positive. According to our evaluation the CTU analysis did not introduce any new false positives (there was no precision loss at CTU boundary).
The CTU analysis revealed many new bugs that require length symbolic analysis, such as memory leak problems (unix.Malloc), dereference of null pointers (core.NullDereference, core.NonNullParamChecker, core.CallAndMessage) and usage of uninitialized values (core.uninitialized.Assign, core.uninitialized.Branch,core.UndefinedBinaryOperatorResult).
See for example distribution of new findings for FFMPeg project:
| Checker ID | Number of new findings |
|---|---|
| core.CallAndMessage | 5 |
| core.DivideZero | 5 |
| core.NonNullParamChecker | 12 |
| core.NullDereference | 18 |
| core.UndefinedBinaryOperatorResult | 21 |
| core.uninitialized.Assign | 11 |
| core.uninitialized.Branch | 6 |
| unix.Malloc | 23 |
We expected that the bug path length of the new results will be longer than the results in the baseline, due to the long traversal of function calls into external source files. This assumption turned out to be true as the median of the bug path length of new bugs is 16 compared to the non-ctu case 7 (for ffmpeg). However in practice 16 long bug path are still manageable for programmers.
Some of the results disappeared compared to the baseline analysis. We are still investigating the reason for this, but we primarily suspect two reasons:
-
The coverage of the analysis somewhat changed for the base file analyzed, because in some cases the analysis node budget is consumed by the traversal of long CTU paths instead of paths inside the base file. It must be noted that in the Non-CTU case the paths inside the base file have inherently imprecise assumptions about external functions.
-
It is also possible that some of the findings disappeared compared the baseline because they were false positives as they were based on false assumptions about unknown external functions. However we think this is to a less extent as Clang SA checkers are written conservatively to report less false positives.
Detailed analysis of the results can be found on the following links
- FFMpeg https://github.com/dkrupp/clang/wiki/FFMpeg-XTU-Analysis
- TMUX: https://github.com/dkrupp/clang/wiki/TMUX-XTU-Analysis
- CURL https://github.com/dkrupp/clang/wiki/Curl-XTU-Analysis
Performance In general the analysis time (including both analysis passes) increased ~2 to ~2.5 times the baseline non-CTU analysis time on all analyzed projects. The increment is due to the first analysis phase and the extra effort of loading the definition of external function from the disc during the analysis. The measurements were performed on the same machine, on 16 CPU cores. The resource need of the new analysis is not dramatic and the solution is similarly scalable to multiple CPUs as the baseline, as all build actions are analyzed independently.
- The current CTU prototype is usable only for C projects. We experienced many crashes and asserts with the ASTImporter for C++ projects. ASTImporter needs to be improved to handle C++ language constructs better.
- Do we lose true positives and coverage in the base file. We plan to measure coverage and experiment with different strategies to build the exploded graph. One simple strategy might be to bound the number of file traversals.
- Flow based bug reports have a so-called uniqueing location that helps to differentiate them. This works for single TUs, but we would like to extend this to multiple TUs.
- During the analysis, we need to store the dumped ASTs temporarily. We thought of ways decrease the disc allocation by compressing or more efficiently storing the AST dumps.
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
[1] Cross-TU Analysis results on open source projects: http://cc.elte.hu/
[2] Artem Dergachev, Aleksei Sidorin Cross TU Analysis for Clang 3.4 http://lists.llvm.org/pipermail/cfe-dev/2015-October/045730.html
[3] Ericsson CTU open source repository: https://github.com/dkrupp/clang/tree/ctu-master
[4] FFMPeg project, https://github.com/FFmpeg/FFmpeg
[5] TMux project, https://github.com/tmux/tmux
[6] CUrl project, https://github.com/curl/curl
- CTU is great for finding One Definition Rule violations! We found one in ffmpeg.
- USR instead of mangled name?
- ASTImporter is hard to test. How to validate all the AST invariants? Running static analyzer on the imported AST helps with that. Lots of asserts are checked in debug builds.
- Expansion/Spelling locations are not properly imported, issues with diagnosing CTU results inside macro expansions.
- How to support incremental analysis in a cross TU setting? Check global call graph and calculate which TUs to recheck? It will no longer feel incremental that way!
- Same bug on different paths amplified
- Memory profiling