| dc.description.abstract | Nowadays, the number of code bases are growing explosively together with their size and complexity, where million lines of code become common to see. To guarantee the correctness and quality of software applications, program analysis techniques have been used to detect bugs and errors each time when there is a new update. However, most existing techniques are designed for whole program analysis, which become expensive and unscalable as the size of programs consistently increase. Moreover, those techniques are used during the late phase of software development, e.g., testing or production, which may be too late to fix a bug or too difficult to understand a bug.
In this dissertation, we introduce several incremental algorithms which are efficient, precise, sound and scalable for real-world, large programs. Firstly, we present IPA, an incremental context-insensitive pointer analysis for Java programs that handles both statement addition, deletion and modification efficiently. Inspired by new properties we observed, IPA avoids redundant computation and expensive graph reachability analysis from existing approaches, as well as preserves precision as the corresponding whole program analysis.
Secondly, we present SHARP, an incremental algorithm that can be generalized to the most commonly used context-sensitive pointer analysis algorithms, i.e., k-CFA and k-obj. We propose a precompute algorithm to avoid redundant computation from naively applying IPA on context-sensitive call graph and pointer assignment graph. We also discuss different parallel scenarios for incremental code changes according to GitHub commits, summarize their efficiency, redundancy and conflict, and conclude our parallel algorithm. More importantly, both IPA and SHARP can be easily extended to other programming languages.
Thirdly, we present D4, a static program analysis framework to detect concurrency bugs (i.e., data race and deadlock) during development phase. Except for IPA, D4 is powered by another three incremental algorithms of static happens-before analysis, lock-dependency analysis and static concurrency bug detection. D4 can pinpoint concurrency bugs after a code change, which is several orders of magnitude faster than the corresponding whole program detection.
Finally, we present O2, a new system for detecting data races in complex multi-threaded and event-driven applications. O2 is powered by origin, which unifies the concepts of thread and event by an entry point and its attributes. We apply origins on pointer analysis to identify objects that are shared by different origins, which concludes our origin-sharing analysis. We also leverage the result of origin-sensitive pointer analysis in static data race detection, which shows a significant improvement in both precision and scalability. | |
