Techniques to detect and avert advanced software concurrency bugs

Qi, Shanxiang

Permalink

https://hdl.handle.net/2142/45603 Copy

Description

Title

Techniques to detect and avert advanced software concurrency bugs

Author(s)

Qi, Shanxiang

Issue Date

2013-08-22T16:49:19Z

Director of Research (if dissertation) or Advisor (if thesis)

Torrellas, Josep

Doctoral Committee Chair(s)

Torrellas, Josep

Committee Member(s)

• Marinov, Darko
• King, Samuel T.
• Lu, Shan

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• concurrency bugs
• data race detection
• dynamic analysis

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.

Graduation Semester

2013-08

Permalink

http://hdl.handle.net/2142/45603

Copyright and License Information

Copyright 2013 Shanxiang Qi

Owning Collections