{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/45603"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/45603","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Techniques to detect and avert advanced software concurrency bugs","abstract":"Multicore machines have become pervasive and, as a result, parallel programming has received renewed interest. Unfortunately, writing correct parallel programs is notoriously hard. One challenging problem is how to ship correct programs. Dynamic analysis tools are very useful to find errors in parallel programs by automatically analyzing the runtime information. They often capture errors from well-tested programs. However, existing dynamic analysis tools suffer from two problems: high false positive rate and high overhead. High false positive rate means lots of errors reported by the dynamic analysis tool may be benign or non-existent. For example, lots of data races detected by a race detection tool could be relatively benign data races. Also, many dynamic software analyses cause orders-ofmagnitude slowdowns, which users cannot tolerate at runtime. This dissertation contains three parts. The first two parts propose two different schemes to reduce the false positives and overhead of race detecting tools. These two schemes can detect and tolerate two different types of harmful races with low overhead: asymmetric data races and IF-condition data races. An asymmetric data race occurs when at least one of the racing threads is inside a critical section. Our proposal to detect and tolerate asymmetric data races is called Pacman. It exploits cache coherence hardware to temporarily protect the variables that a thread accesses in a critical section from other threads’s requests. An IF-condition data race is one where a memory location accessed by a thread (T1) in the control expression of an IF statement suffers a race while T1 is executing the THEN or ELSE clauses. T1 may or may not access again the location in the THEN or ELSE clauses. Our second proposal presents two techniques to handle IF-condition races dynamically. They rely on simple code transformations and, in one case, on additional hardware help. The third part proposes a general hardware framework to provide fine-grained memory monitoring with low overhead. This mechanism can be used to reduce the overhead of many dynamic software analyses. Overall, this dissertation aims at designing novel schemes to reduce the false positive rate and overhead of dynamic software analyses in order to make parallel programs more robust.","abstract_html":"Multicore machines have become pervasive and, as a result, parallel programming has received renewed interest. Unfortunately, writing correct parallel programs is notoriously hard. One challenging problem is how to ship correct programs. Dynamic analysis tools are very useful to find errors in parallel programs by automatically analyzing the runtime information. They often capture errors from well-tested programs. However, existing dynamic analysis tools suffer from two problems: high false positive rate and high overhead. High false positive rate means lots of errors reported by the dynamic analysis tool may be benign or non-existent. For example, lots of data races detected by a race detection tool could be relatively benign data races. Also, many dynamic software analyses cause orders-ofmagnitude slowdowns, which users cannot tolerate at runtime. This dissertation contains three parts. The first two parts propose two different schemes to reduce the false positives and overhead of race detecting tools. These two schemes can detect and tolerate two different types of harmful races with low overhead: asymmetric data races and IF-condition data races. An asymmetric data race occurs when at least one of the racing threads is inside a critical section. Our proposal to detect and tolerate asymmetric data races is called Pacman. It exploits cache coherence hardware to temporarily protect the variables that a thread accesses in a critical section from other threads’s requests. An IF-condition data race is one where a memory location accessed by a thread (T1) in the control expression of an IF statement suffers a race while T1 is executing the THEN or ELSE clauses. T1 may or may not access again the location in the THEN or ELSE clauses. Our second proposal presents two techniques to handle IF-condition races dynamically. They rely on simple code transformations and, in one case, on additional hardware help. The third part proposes a general hardware framework to provide fine-grained memory monitoring with low overhead. This mechanism can be used to reduce the overhead of many dynamic software analyses. Overall, this dissertation aims at designing novel schemes to reduce the false positive rate and overhead of dynamic software analyses in order to make parallel programs more robust.","abstract_has_math":false,"creators":["Qi, Shanxiang"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Torrellas, Josep","Marinov, Darko","King, Samuel T.","Lu, Shan"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2013,"date_issued":"2013-08-22T16:49:19Z","date_published":"2013-08-22T16:49:19Z","updated_at":"2026-07-22T22:25:36Z","subjects":["concurrency bugs","data race detection","dynamic analysis"],"languages":["en"],"rights":["Copyright 2013 Shanxiang Qi"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/45603","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Torrellas, Josep","Marinov, Darko","King, Samuel T.","Lu, Shan"]},{"key":"dc:creator","label":"Author","values":["Qi, Shanxiang"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2013-08-22T16:49:19Z","2015-08-22T10:00:28Z","2013-08"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"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 bugs","data race detection","dynamic analysis"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2013 Shanxiang Qi"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/45603"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Multicore machines have become pervasive and, as a result, parallel programming has received renewed interest. Unfortunately, writing correct parallel programs is notoriously hard. One challenging problem is how to ship correct programs. Dynamic analysis tools are very useful to find errors in parallel programs by automatically analyzing the runtime information. They often capture errors from well-tested programs. However, existing dynamic analysis tools suffer from two problems: high false positive rate and high overhead. High false positive rate means lots of errors reported by the dynamic analysis tool may be benign or non-existent. For example, lots of data races detected by a race detection tool could be relatively benign data races. Also, many dynamic software analyses cause orders-ofmagnitude slowdowns, which users cannot tolerate at runtime. This dissertation contains three parts. The first two parts propose two different schemes to reduce the false positives and overhead of race detecting tools. These two schemes can detect and tolerate two different types of harmful races with low overhead: asymmetric data races and IF-condition data races. An asymmetric data race occurs when at least one of the racing threads is inside a critical section. Our proposal to detect and tolerate asymmetric data races is called Pacman. It exploits cache coherence hardware to temporarily protect the variables that a thread accesses in a critical section from other threads’s requests. An IF-condition data race is one where a memory location accessed by a thread (T1) in the control expression of an IF statement suffers a race while T1 is executing the THEN or ELSE clauses. T1 may or may not access again the location in the THEN or ELSE clauses. Our second proposal presents two techniques to handle IF-condition races dynamically. They rely on simple code transformations and, in one case, on additional hardware help. The third part proposes a general hardware framework to provide fine-grained memory monitoring with low overhead. This mechanism can be used to reduce the overhead of many dynamic software analyses. Overall, this dissertation aims at designing novel schemes to reduce the false positive rate and overhead of dynamic software analyses in order to make parallel programs more robust.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2013-06-24T19:07:18Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Qi_Shanxiang.pdf: 1707722 bytes, checksum: 142cae5a25a48a1fa7200a181c6b537b (MD5)","Made available in DSpace on 2013-08-22T16:49:19Z (GMT). No. of bitstreams: 2 Shanxiang_Qi.pdf: 1707722 bytes, checksum: 142cae5a25a48a1fa7200a181c6b537b (MD5) license.txt: 4058 bytes, checksum: 9042904064fc3e107abe20bac8b3a5b3 (MD5)","Restriction data tranferred 2014-07-01T11:35:23-05:00 Original Data Group with Access UIUC Users [automated] Release Date: 2015-08-22 11:49:27 UTC Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Seth Robbins (srobbins@illinois.edu) on 2013-08-22T16:49:46Z Item is restricted until 2015-08-22T16:49:27Z","U of I Only Restriction Lifted for Item 45585 on 2015-08-22T10:00:28Z."]},{"key":"dc:title","label":"Title","values":["Techniques to detect and avert advanced software concurrency bugs"]}]}],"canonical_facts":{"dc:contributor":["Torrellas, Josep","Marinov, Darko","King, Samuel T.","Lu, Shan"],"dc:creator":["Qi, Shanxiang"],"dc:date":["2013-08-22T16:49:19Z","2015-08-22T10:00:28Z","2013-08"],"dc:description":["Multicore machines have become pervasive and, as a result, parallel programming has received renewed interest. Unfortunately, writing correct parallel programs is notoriously hard. One challenging problem is how to ship correct programs. Dynamic analysis tools are very useful to find errors in parallel programs by automatically analyzing the runtime information. They often capture errors from well-tested programs. However, existing dynamic analysis tools suffer from two problems: high false positive rate and high overhead. High false positive rate means lots of errors reported by the dynamic analysis tool may be benign or non-existent. For example, lots of data races detected by a race detection tool could be relatively benign data races. Also, many dynamic software analyses cause orders-ofmagnitude slowdowns, which users cannot tolerate at runtime. This dissertation contains three parts. The first two parts propose two different schemes to reduce the false positives and overhead of race detecting tools. These two schemes can detect and tolerate two different types of harmful races with low overhead: asymmetric data races and IF-condition data races. An asymmetric data race occurs when at least one of the racing threads is inside a critical section. Our proposal to detect and tolerate asymmetric data races is called Pacman. It exploits cache coherence hardware to temporarily protect the variables that a thread accesses in a critical section from other threads’s requests. An IF-condition data race is one where a memory location accessed by a thread (T1) in the control expression of an IF statement suffers a race while T1 is executing the THEN or ELSE clauses. T1 may or may not access again the location in the THEN or ELSE clauses. Our second proposal presents two techniques to handle IF-condition races dynamically. They rely on simple code transformations and, in one case, on additional hardware help. The third part proposes a general hardware framework to provide fine-grained memory monitoring with low overhead. This mechanism can be used to reduce the overhead of many dynamic software analyses. Overall, this dissertation aims at designing novel schemes to reduce the false positive rate and overhead of dynamic software analyses in order to make parallel programs more robust.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2013-06-24T19:07:18Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Qi_Shanxiang.pdf: 1707722 bytes, checksum: 142cae5a25a48a1fa7200a181c6b537b (MD5)","Made available in DSpace on 2013-08-22T16:49:19Z (GMT). No. of bitstreams: 2 Shanxiang_Qi.pdf: 1707722 bytes, checksum: 142cae5a25a48a1fa7200a181c6b537b (MD5) license.txt: 4058 bytes, checksum: 9042904064fc3e107abe20bac8b3a5b3 (MD5)","Restriction data tranferred 2014-07-01T11:35:23-05:00 Original Data Group with Access UIUC Users [automated] Release Date: 2015-08-22 11:49:27 UTC Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Seth Robbins (srobbins@illinois.edu) on 2013-08-22T16:49:46Z Item is restricted until 2015-08-22T16:49:27Z","U of I Only Restriction Lifted for Item 45585 on 2015-08-22T10:00:28Z."],"dc:identifier":["http://hdl.handle.net/2142/45603"],"dc:language":["en"],"dc:rights":["Copyright 2013 Shanxiang Qi"],"dc:subject":["concurrency bugs","data race detection","dynamic analysis"],"dc:title":["Techniques to detect and avert advanced software concurrency bugs"],"dc:type":["text"],"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:25:36Z"}