Static Analyses for C++ in the Presence of Separate Compilation

Horváth, Gábor

Static Analyses for C++ in the Presence of Separate Compilation

Subject: Műszaki tudományok/Informatikai tudományok
C++ programming language
static analysis
bug finding
lifetime
summary
symbolic execution
abstract interpretation
testing
Informatika D. I./Az informatika alapjai és módszerei.
C++ programozási nyelv
statikus elemzés
hibakeresés
élettartam
összegzés
szimbolikus végrehajtás
absztrakt interpretáció
tesztelés

URI: http://hdl.handle.net/10831/62120

Link to Library Catalogue: https://opac.elte.hu/Record/opac-EUL01-1078408

MTMT: 32644144

DOI: 10.15476/ELTE.2020.212

Abstract:

Ez a disszertáció új elemzéseket és elemzési módszereket mutat be, melyek bizonyos programozási hibák megtalálására képesek. Az első tézis egy olyan megközelítést mutat be, ami képes megtalálni a C++ szabványkönyvtárának (STL) számos hibás használatát. Több kategóriában kerültek bevezetésre ellenőrzések: teljesítmény, hibás kód és modernizáció. Néhány ellenőrzés képes a kód automatikus javítására is. A legtöbbjük más eszközökben korábban nem volt megtalálható. Továbbá, leírtam egy módszert, amivel ezek az ellenőrzések általánosíthatóak idiomatikus nem STL kódra.
A következő tézis olyan elemzéseket definiál, amelyek bizonyos memória hibákat képesek megtalálni, úgymint felszabadítás utáni használat vagy nullpointer dereferálás. Ezek az elemzések egy Herb Sutter által definiált vezérlés érzékeny elemzésen alapulnak. Herb Sutter a C++ szabványbizottság elnöke. Bevezettem egy utasításokra lokális változatát az analízisnek, amely nem talál hamis hibákat. Ez az implementáció elég érett volt ahhoz, hogy a Clang fordítóban alapértelmezetten engedélyezésre kerüljön. Ezen felül, bemutattam számos technikát, amellyel csökkenthetőek a hamis találatok az eredeti vezérlés érzékeny algoritmusban.
A harmadik tézis a Clang Static Analyzer fordítási egységeken átívelő elemzéssel való kiegészítéséről szól. Megmértük, hogy hogyan változott a lefedettség, a teljesítmény, valamint a megtalált hibák száma. Ezen túl megvizsgáltuk a hamis hibák arányának változását. Azt találtuk, hogy az elemzés hatókörének kiterjesztésével javult a talált hibák minősége. Az eredmények nagyban függenek az analízishez választott bejárási stratégiától. A „lefedetlent-először” bejárási stratégia jól szerepelt, a módszer nem okozott nagy lefedettség romlást.
Az utolsó tézis olyan modellek (summary) bevezetését tárgyalja, amely egy középút a konzervatív kiértékelés és az inline elemzés között szimbolikus végrehajtásnál. A javasolt módszer fő alkalmazása a fordítási egységeken átívelő analízis megvalósítása. Bár a prototípus csak kézzel írt modelleket támogat, a tézisben javasoltam egy sémát ezeknek a modelleknek az automatikus generálására.
Az utolsó két tézis a szimbolikus végrehajtás hatókörének a kiterjesztéséről szól. Ez fontos a memória hibák megtalálásához, mivel számos probléma a heap használatához kapcsolható. A heap egy globális erőforrás, mely miatt kifejezetten nehéz lokálisan érvelni a helyes használatáról.
Minden bemutatott módszerhez tartozik prototípus. Sőt, néhány megoldás már olyan robusztus, hogy ipari alkalmazásai is vannak számos felhasználóval. A bemutatott elemzések közül néhány olyan hibákat is képes felfedni, ami tapasztalt fordító fejlesztőkön is kifogott. Az utasításokra lokális élettartam elemzés olyan népszerű nyílt forráskódú projektekben talált hibákat, mint OpenCV, Chromium és LLVM.

Abstract:

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.

Show full item record