RacerD is a static race detector that has been proven to be effective in engineering practice: it has seen thousands of data races fixed by developers before reaching production, and has supported the migration of Facebook’s Android app from a single-threaded to a multi-threaded architecture. We prove a True Positives Theorem stating that under certain assumptions, which reflect the way that product code (but not infrastructure code) uses concurrency, an idealized theoretical version of the analysis never reports a false positive. We also provide an empirical evaluation of an implementation of this analysis, versus the original RacerD.
The theorem was motivated in the first case by the desire to understand the observation from production that RacerD was providing remarkably accurate signal to developers, and then the theorem guided further analyzer design decisions. Technically, our result can be seen as saying that the analysis computes an under-approximation of an over-approximation, which is the reverse of the more usual (over of under) situation in static analysis. We suggest that theorems of this variety might be generally useful in designing static analyses for bug catching.
Wed 16 JanDisplayed time zone: Belfast change
10:35 - 12:03
|A True Positives Theorem for a Static Race Detector|
Nikos Gorogiannis , Peter W. O'Hearn Facebook and University College London, Ilya Sergey Yale-NUS College and National University of SingaporeLink to publication DOI Pre-print Media Attached File Attached
|Decoupling Lock-Free Data Structures from Memory Reclamation for Static Analysis|
Research PapersLink to publication DOI Pre-print Media Attached File Attached
|Pretend Synchrony: Synchronous Verification of Asynchronous Distributed Programs|
Klaus v. Gleissenthall University of California at San Diego, USA, Rami Gökhan Kıcı University of California at San Diego, USA, Alexander Bakst , Deian Stefan University of California San Diego, Ranjit Jhala University of California, San DiegoLink to publication DOI Media Attached
|Weak-Consistency Specification via Visibility Relaxation|
Research PapersLink to publication DOI Media Attached File Attached