Exposing and Detecting Concurrency Bugs in Large-Scale Software

to software reliability. As hardware becomes more parallel, concurrent
programming will become increasingly pervasive. However, correct
concurrent programming is known to be extremely challenging for
developers and a source of concurrency bugs. In this work we propose
to develop mechanisms to help developers to expose and detect
concurrency bugs.

We conducted a real-world concurrency bug study to better understand
the external and internal effects of real-world concurrency bugs. In
this study we found that a significant fraction of concurrency bugs
qualify as semantic or latent bugs, which are two particularly
challenging classes of concurrency bugs. Based on the insights from
our study, we propose a concurrency bug detector that analyzes the
behavior of program executions to infer whether concurrency bugs have
been triggered during a concurrent execution. Our bug detector
analyzes the external behavior (i.e., output produced) and the
internal behavior (i.e., state changes) of a program execution to
detect these particularly challenging classes of concurrency bugs. It
compares the program output of different executions to detect
concurrency bugs that manifest themselves by providing wrong results
to the user (i.e., semantic concurrency bugs). In addition, it also
compares the internal state of different executions to detect
concurrency bugs that do not immediately manifest themselves to the
user when they are triggered (i.e., latent concurrency bugs). We
applied our bug detector to MySQL and we were able to find various
instances of concurrency bugs of both of these classes.

In addition, we propose a testing tool to allow developers to test
operating system kernels for concurrency bugs. The goal of our tool is
to bridge the gap between user-mode testing and kernel-mode testing by
enabling systematic exploration of the kernel thread interleaving
space. We will achieve this systematic exploration through
fine-grained control over the execution of individual threads. Unlike
similar tools for the user-mode context, achieving fine-grained
control over the execution of kernel threads is hard because the
kernel is, itself, the software layer that implements the thread
abstraction, the scheduler and the synchronization primitives. This
process is further complicated by the existence in the kernel of
additional concurrency mechanisms (i.e., interrupts) and
synchronization mechanisms. Our proposed system will allow developers
to efficiently expose concurrency bugs by combining the fine-grained
control mechanism with smart heuristics that determine which thread
interleavings to explore first. In addition, our approach does not
require modifications to the kernel, which is an important
characteristic to make the tool practical. The key idea of our
approach is to use a modified virtual machine, implementing a custom
scheduling algorithm, to control the thread interleavings. In turn,
this virtual machine is combined with existing concurrency bug
detectors to flag the executions that trigger concurrency bugs.