An Oracle for Tolerating and Detecting Asymmetric Races

MSR-TR-2007-122 |

Because races represent a hard-to-manage class of errors in concurrent programs, numerous approaches to detect them have been proposed and evaluated. We consider specifically asymmetric races, a subclass of race conditions, where a programmer’s thread correctly acquires and releases a lock for a specific variable, while another thread causes a race by improperly accessing this variable. We introduce ToleRace, an oracle that allows programs to either tolerate or detect asymmetric races based on local replication of shared state. ToleRace provides an approximation of atomicity in critical sections by creating local copies of shared variables when a critical section is entered and propagating the appropriate copy when the critical section is exited. We characterize the possible interleavings that can cause races and precisely describe the effect of ToleRace in each of these cases. We evaluate the theoretical aspects of the oracle and note that it could be implemented in hardware and/or software within a favorable range of overhead-to-benefit scenarios.