Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


dissertation_roemer.pdf (944.81 KB)

ETD Abstract Container

Abstract Header

Practical High-Coverage Sound Predictive Race Detection

Roemer, Jake
http://rave.ohiolink.edu/etdc/view?acc_num=osu1563505463237874

Abstract Details

2019, Doctor of Philosophy, Ohio State University, Computer Science and Engineering.
Data races pose a fundamental issue plaguing the reliability of parallel software. A shared-memory program has a data race if two conflicting memory accesses (accesses to the same memory location by different threads, where at least one access is a write) can execute consecutively (no interleaving events exist). Modern shared-memory programming languages including C++ and Java provide undefined or ill-defined semantics for executions with data races. So in the presence of data races, shared-memory programs are vulnerable to fatal crashes, data corruption, and other unexpected errors. Data races manifest nondeterministically creating the complex task of writing and diagnosing shared-memory programs. Existing research offers a variety of program analyses to detect and report data races to developers. Most notably, predictive dynamic analyses detect data races that can occur in executions other than the observed execution. Predictive analysis defines the set of necessary ordering between events while ensuring the same behavior as the observed execution to detect races that industry standard happens-before analysis cannot detect. The existing techniques are sound (report only true races) but often miss races because the techniques are impractical to run extensively on large programs in practice due to performing costly reasoning about reordered thread interleavings. Alternative partial-order-based predictive techniques that scale to large programs fail to detect all races knowable from the observed execution because of the conservative ordering between events that preserve a valid reordered execution for the techniques to be sound. The partial-order-based predictive techniques remain impractical compared to industry standard race detectors. A major contributing factor to predictive analyses poor performance is the metadata required to weaken the observed ordering. The metadata tracks conflicting critical sections and is a vital component of predictive analysis that industry standard happens-before race detectors do not need to manage. Thus the limitations of predictive analyses result in shared-memory programs remaining vulnerable in the presence of extremely hard-to-detect data races. The goal of this work is to detect all races knowable from the observed execution and close the performance gap between predictive analysis and industry standard detectors by designing a practical high-coverage sound predictive data race detector. This dissertation presents a body of work that advances data race coverage and run time and memory usage performance of predictive analysis. The first main focus for this dissertation is to maximize race detection capability to detect all knowable races from an observed execution. Our key insight to achieve high-coverage predictive analysis is to sacrifice soundness (may detect false races) by relinquishing conservative ordering between events. Our contributions reduce ordering between events more than prior work by showing the conservative orderings are unnecessary to ensure the same behavior as the observed execution. Our contributions detect hard-to-find races that are hidden from prior work, thus achieving high-coverage predictive analysis. To strictly improve race coverage of predictive analysis this dissertation aims to provide the same soundness guarantees as prior predictive analyses and existing industry standard detectors. Our contributions provide soundness (report only true races) by verifying if potential races detected are true races without sacrificing high-coverage predictive analysis of full program executions. The second focus for this dissertation is to improve run time and memory usage performance of predictive analysis such that predictive race detectors can compete with industry standard detectors. Our key insight to achieve practical predictive analysis is to apply similar epoch optimizations used by popular happens-before race detectors to conflicting critical section metadata and to be the first to apply the epoch optimizations directly to predictive analysis. Our contributions provide optimizations applicable to several predictive analyses that improve run time and memory usage performance to be competitive with industry standard detectors. This work tackles real, challenging issues in data race detection that directly impact system reliability. More specifically, advancing predictive analysis not only develops techniques that guarantee higher coverage with reasonable run time and memory usage than prior work but also makes a case for predictive analysis to be the prevailing approach for detecting data races. The insights of this dissertation lend itself to the development of new relations or application of partial orders to other techniques such as static analysis that broadens how an approach detects a data race.
Michael Bond (Advisor)
Atanas Rountev (Committee Member)
Paul Sivilotti (Committee Member)
194 p.
Computer Engineering; Computer Science
Data race detection; dynamic predictive analysis; dynamic analysis; software testing and debugging; software and its engineering

Recommended Citations

Citations

  • Roemer, J. (2019). Practical High-Coverage Sound Predictive Race Detection [Doctoral dissertation, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1563505463237874

    APA Style (7th edition)

  • Roemer, Jake. Practical High-Coverage Sound Predictive Race Detection. 2019. Ohio State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1563505463237874.

    MLA Style (8th edition)

  • Roemer, Jake. "Practical High-Coverage Sound Predictive Race Detection." Doctoral dissertation, Ohio State University, 2019. http://rave.ohiolink.edu/etdc/view?acc_num=osu1563505463237874

    Chicago Manual of Style (17th edition)

osu1563505463237874
337
© 2019, some rights reserved.Creative Commons License Practical High-Coverage Sound Predictive Race Detection by Jake Roemer is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License. Based on a work at etd.ohiolink.edu.
This open access ETD is published by The Ohio State University and OhioLINK.