{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/113938"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/113938","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Algorithmic advances in dynamic analysis for detecting concurrency bugs","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 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.","abstract_html":"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.","abstract_has_math":false,"creators":["Mathur, Umang"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Viswanathan, Mahesh","Parthasarathy, Madhusudan","Rosu, Grigore","Sarkar, Vivek"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022-04-29T21:41:39Z","date_published":"2022-04-29T21:41:39Z","updated_at":"2026-07-22T22:24:53Z","subjects":["Concurrency","Dynamic Analysis","Algorithms"],"languages":["en"],"rights":["Copyright 2021 Umang Mathur"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/113938","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Viswanathan, Mahesh","Parthasarathy, Madhusudan","Rosu, Grigore","Sarkar, Vivek"]},{"key":"dc:creator","label":"Author","values":["Mathur, Umang"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2022-04-29T21:41:39Z","2024-04-29T21:47:53Z","2021-07-19","2021-12"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Concurrency","Dynamic Analysis","Algorithms"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2021 Umang Mathur"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/113938"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2023-12-01","The student, Umang Mathur, accepted the attached license on 2021-07-16 at 17:21.","The student, Umang Mathur, submitted this Dissertation for approval on 2021-07-16 at 17:26.","This Dissertation was approved for publication on 2021-07-19 at 11:23.","DSpace SAF Submission Ingestion Package generated from Vireo submission #16995 on 2022-04-06 at 17:16:10","Made available in DSpace on 2022-04-29T21:41:39Z (GMT). No. of bitstreams: 2 MATHUR-DISSERTATION-2021.pdf: 1409268 bytes, checksum: 38100bbe811f8c0e68527926131094c6 (MD5) LICENSE.txt: 4209 bytes, checksum: 1fcc77be006b05f4869e0be361ec7fcc (MD5) Previous issue date: 2021-07-19","Embargo set by: Seth Robbins for item 123299 Lift date: 2024-04-29T21:41:44Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Embargo set by: Seth Robbins for item 123299 Lift date: 2024-04-29T21:42:24Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Embargo set by: Seth Robbins for item 123299 Lift date: 2024-04-29T21:43:01Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Embargo set by: Seth Robbins for item 123299 Lift date: 2024-04-29T21:44:44Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Embargo set by: Seth Robbins for item 123299 Lift date: 2024-04-29T21:46:25Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Embargo set by: Seth Robbins for item 123299 Lift date: 2024-04-29T21:47:53Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Algorithmic advances in dynamic analysis for detecting concurrency bugs"]}]}],"canonical_facts":{"dc:contributor":["Viswanathan, Mahesh","Parthasarathy, Madhusudan","Rosu, Grigore","Sarkar, Vivek"],"dc:creator":["Mathur, Umang"],"dc:date":["2022-04-29T21:41:39Z","2024-04-29T21:47:53Z","2021-07-19","2021-12"],"dc: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 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.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2023-12-01","The student, Umang Mathur, accepted the attached license on 2021-07-16 at 17:21.","The student, Umang Mathur, submitted this Dissertation for approval on 2021-07-16 at 17:26.","This Dissertation was approved for publication on 2021-07-19 at 11:23.","DSpace SAF Submission Ingestion Package generated from Vireo submission #16995 on 2022-04-06 at 17:16:10","Made available in DSpace on 2022-04-29T21:41:39Z (GMT). No. of bitstreams: 2 MATHUR-DISSERTATION-2021.pdf: 1409268 bytes, checksum: 38100bbe811f8c0e68527926131094c6 (MD5) LICENSE.txt: 4209 bytes, checksum: 1fcc77be006b05f4869e0be361ec7fcc (MD5) Previous issue date: 2021-07-19","Embargo set by: Seth Robbins for item 123299 Lift date: 2024-04-29T21:41:44Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Embargo set by: Seth Robbins for item 123299 Lift date: 2024-04-29T21:42:24Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Embargo set by: Seth Robbins for item 123299 Lift date: 2024-04-29T21:43:01Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Embargo set by: Seth Robbins for item 123299 Lift date: 2024-04-29T21:44:44Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Embargo set by: Seth Robbins for item 123299 Lift date: 2024-04-29T21:46:25Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Embargo set by: Seth Robbins for item 123299 Lift date: 2024-04-29T21:47:53Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/113938"],"dc:language":["en"],"dc:rights":["Copyright 2021 Umang Mathur"],"dc:subject":["Concurrency","Dynamic Analysis","Algorithms"],"dc:title":["Algorithmic advances in dynamic analysis for detecting concurrency bugs"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:53Z"}