Static Analyses for C++ in the Presence of Separate Compilation
Gábor Horváth · Eötvös Loránd Tudományegyetem · 2021
This dissertation presents novel analyses and analysis methods to find certain programming errors. The first thesis describes a method to find misuses of the C++ Standard Template Library (STL). The checks cover a wide range of categories including performance, error prone code, and modernization. Some of them also capable of transforming the code to fix errors automatically. The most of introduced checks were not available in other tools before. Moreover, I also described how some of those checks could be generalized for idiomatic non-STL code. The next thesis describes a set of analyses that can find common memory errors such as use-after-free or null pointer dereference. The analyses are based on a flow-sensitive method proposed by Herb Sutter, the chairman of the C++ Standards Committee. I defined a statement-local variant that has virtually no false positives and it was mature enough to be enabled by default in the open-source Clang compiler. Furthermore, I introduced various improvements to reduce the false-positive findings in the original algorithm. The third thesis discusses how we extended the Clang Static Analyzer to reason about multiple translation units at once. We measured how the coverage patterns, performance, and the number of discovered bugs change with the increased analysis scope. Moreover, we manually investigated the false-positive ratio of the bugs and found that the cross translation unit analysis slightly improved the quality of the results. These findings are dependent on the exploration strategy used by the analyzers. We verified that the unexplored-first strategy is resilient to the increase in analysis scope. The final thesis proposes a special kind of summaries that are a middle ground between conservative evaluation and inline substitution for symbolic execution. The proposed method's main applicability is to implement reasoning across translation units. While the implemented prototype only works with hand-written summaries, I also proposed a method to automatically synthesize them from the implementations. The last two theses are related to extending the scope of symbolic execution. This is important, as memory errors are often related to how the heap is handled in C++. The heap is a global resource which makes it extremely tricky to locally reason about it. All of the results are backed by prototypes, some of them even have mature implementations and a large user base. The demonstrated methods could uncover issues that eluded some seasoned compiler developers. The statement-local lifetime analysis found errors in many popular open-source projects including OpenCV, Chromium, and LLVM.