Algorithmic advances in dynamic analysis for detecting concurrency bugs

Concurrency is an indispensable programming paradigm and multi-threaded programs form the bedrock of most modern software applications. Multi-threaded programs, however, are also the most tricky to get right. Despite rigorous in-house testing, concurrency issues like data races, race conditions, deadlocks and atomicity violations incessantly find there way into production-level software. In the past, errors arising due to complex concurrency bugs in software have led to catastrophic loss of human lives and money. Tackling concurrency bugs, and in particular, efficiently detecting such bugs, has, therefore, been the center of attention in computer science research for several decades now. Dynamic analysis techniques, in particular, have emerged as the de facto standard for detecting concurrency bugs. Such techniques, examine execution traces of programs, with an aim to detect concurrency bugs at runtime. This thesis advances the state-of-the art in dynamic analysis for detecting concurrency bugs. We propose several algorithms for improving the precision, recall and efficiency of existing techniques for dynamically detecting concurrency bugs like data races and atomicity violations. We also investigate several complexity-theoretic questions establishing precise complexity bounds on several questions arising in dynamic concurrency bug detection. We first consider the problem of detecting data races dynamically. Most popular techniques for dynamic race detection are either based on a principle of lockset violations, or on the happens-before partial order. While these techniques are usually employed at runtime, for detecting data races on-the-fly, there are many scenarios when executions can be, or need to be analyzed for concurrency bugs in an offline setting. Since executions can be extremely large, they are often stored in a compressed format to ease their warehousing. In this thesis, we study the problem of detecting data races when the analysis needs to be performed over an execution that has been compressed using a grammar-based compression scheme. We show how to detect data races efficiently in such a setting, without needing to decompress the (potentially) exponentially succinct compressed format. We next study the problem of dynamic race prediction, which asks if one can infer the presence of data races beyond those present in a single trace observed by monitoring a program while it is executing. Existing race detectors report false alarms, miss a lot of real races, or do not scale beyond small execution traces. We propose several algorithms that offer a good balance of scalability and predictive power, while being sound (no false positives). We also study the problem from a complexity-theoretic point of view and identify upper and lower bounds, both in the general setting and in settings when the observed execution trace satisfies special properties. Next, we consider the problem of dynamically detecting atomicity violations. This thesis proposes a linear time vector-clock algorithm for a well-studied notion of atomicity, called conflict serializability, for which the only known algorithms ran in cubic time. The algorithms proposed in this thesis have been implemented and evaluated against large benchmark suites to evaluate their effectiveness. The techniques developed in this thesis are backed by strong theoretical foundations that ensure that our algorithms are scalable, sound and have high predictive power, making them applicable for analyzing modern software systems.U of I OnlyAuthor requested U of Illinois access only (OA after 2yrs) in Vireo ETD syste