ConSeq: Detecting Concurrency Bugs through Sequential Errors
Wei Zhang, Junghee Lim, Ramya Olichandran, Joel Scherpelz, Guoliang Jin, Shan Lu, and Thomas Reps
Concurrency bugs are caused by non-deterministic interleavings
between shared memory accesses. Their effects propagate through
data and control dependences until they cause software to crash,
hang, produce incorrect output, etc. The lifecycle of a bug thus
consists of three phases: (1) triggering, (2) propagation, and (3)
failure.
Traditional techniques for detecting concurrency bugs mostly
focus on phase (1) -- i.e., on finding certain structural patterns of
interleavings that are common triggers of concurrency bugs, such as
data races. This paper explores a consequence-oriented approach to
improving the accuracy and coverage of state-space search and bug
detection. The proposed approach first statically identifies potential
failure sites in a program binary (i.e., it first considers a phase (3)
issue). It then uses static slicing to identify critical read instructions
that are highly likely to affect potential failure sites through control
and data dependences (phase (2)). Finally, it monitors a single (correct)
execution of a concurrent program and identifies suspicious
interleavings that could cause an incorrect state to arise at a critical
read and then lead to a software failure (phase (1)).
ConSeq's backwards approach, (3)->(2)->(1), provides advantages
in bug-detection coverage and accuracy but is challenging to
carry out. ConSeq makes it feasible by exploiting the empirical observation
that phases (2) and (3) usually are short and occur within
one thread. Our evaluation on large, real-world C/C++ applications
shows that ConSeq detects more bugs than traditional approaches
and has a much lower false-positive rate.
(Click here to access the paper:
PDF.
Copyright (c) 2011 ACM.)
University of Wisconsin