Algorithmic advances in dynamic analysis for detecting concurrency bugs
type: CreativeWork
description: 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…
abstract: 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…
author: Mathur, Umang
language: en
keywords: Concurrency, Dynamic Analysis, Algorithms
date published: 2022-04-29T21:41:39Z
date modified: 2026-07-22T22:24:53Z
provider: University of Illinois - Urbana-Champaign
publisher: Networked Digital Library of Theses and Dissertations
type: WebPage
source organization: University of Illinois at Urbana-Champaign

PropertyValue
property ID: Handle
value: http://hdl.handle.net/2142/113938