Techniques to detect and avert advanced software concurrency bugs

concurrency bugs;data race detection;dynamic analysis

Qi, Shanxiang

关键词: concurrency bugs;    data race detection;    dynamic analysis;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/45603/Shanxiang_Qi.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

Multicore machines have become pervasive and, as a result, parallel programming has receivedrenewed interest. Unfortunately, writing correct parallel programs is notoriously hard. One challengingproblem is how to ship correct programs. Dynamic analysis tools are very useful to finderrors in parallel programs by automatically analyzing the runtime information. They often captureerrors from well-tested programs.However, existing dynamic analysis tools suffer from two problems: high false positive rateand high overhead. High false positive rate means lots of errors reported by the dynamic analysistool may be benign or non-existent. For example, lots of data races detected by a race detectiontool could be relatively benign data races. Also, many dynamic software analyses cause orders-ofmagnitudeslowdowns, which users cannot tolerate at runtime.This dissertation contains three parts. The first two parts propose two different schemes toreduce the false positives and overhead of race detecting tools. These two schemes can detectand tolerate two different types of harmful races with low overhead: asymmetric data races andIF-condition data races.An asymmetric data race occurs when at least one of the racing threads is inside a criticalsection. Our proposal to detect and tolerate asymmetric data races is called Pacman. It exploitscache coherence hardware to temporarily protect the variables that a thread accesses in a criticalsection from other threads’s requests.An IF-condition data race is one where a memory location accessed by a thread (T1) in thecontrol expression of an IF statement suffers a race while T1 is executing the THEN or ELSEclauses. 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 simplecode transformations and, in one case, on additional hardware help.The third part proposes a general hardware framework to provide fine-grained memory monitoringwith low overhead. This mechanism can be used to reduce the overhead of many dynamicsoftware analyses.Overall, this dissertation aims at designing novel schemes to reduce the false positive rate andoverhead of dynamic software analyses in order to make parallel programs more robust.