Deterministic Reproduction of Concurrency Bugs for Bug Diagnostics

PhD Thesis Proposal Defence


Title: "Deterministic Reproduction of Concurrency Bugs for Bug Diagnostics"

by

Mr. Jinguo ZHOU


Abstract:

Concurrency bug is a major stumbling block to writing multi-threaded programs. 
The capability of reproducing a concurrency bug is key to comprehending and 
nally xing the bug. Unlike sequential programs, concurrent programs may behave 
erently even given the same input, making replay techniques for concurrent 
programs much harder than the counterpart for sequential programs. In this 
thesis proposal, we target on deterministic reproducing concurrency bugs 
together with the bug diagnostics given the capability of reproducing the bug.

This thesis proposal contains three parts. In the rst part, we provide Stride, 
a search based deterministic replay technique that improves the e ciency of 
recording of the program execution information. Unlike exiting techniques that 
either maintain the exact shared read-write linkages with a large runtime 
overhead -line algorithms to search for a feasible interleaved execution, 
Stride records the bounded shared memory access linkages at runtime and infers 
an equivalent interleaving in polynomial time, under the sequential 
consistency(SC) assumption. The recording scheme eliminates the need for 
synchronizing the shared read operations, which results in a signicant overhead 
reduction. Comparing to the previous state-of-the-art approach of deterministic 
replay, Stride reduces, on average, 2.5 times of runtime overhead and produces, 
on average, 3.88 times smaller logs.

The second part aims at enabling deterministic replay under relaxed memory 
models(RMMs), which dominate today's multicore chips. The main obstacle ap- 
ects caused by the code instrumentation required by replay techniques: The code 
instrumentation may prevent certain hardware optimizations, such as code 
reordering and thus, disables the RMM-specic behaviors, leading to poor 
coverage of RMM-specic behaviors. By leveraging the insight that sequential 
consistency (SC) instrumentation is free ects, we reduce RMM instrumentation to 
SC instrumenta- tion via auxiliary threads that simulate RMM behaviors. This 
leads to a novel code transformation, namely SC-Transformation, which is the 
rst to enable safe instrumentation under RMMs with the provable guarantee of 
full coverage, i.e., it does not prevent any execution witnesses permitted by 
the target RMM. We provide a formal characterization of our transformation, and 
prove its soundness and completeness w.r.t. TSO and PSO. Our experiments show 
that the overhead ective, in that it successfully captures the buggy execution 
traces of all the 71 RMM-specic bugs we tested for, none of which could be 
captured atop naive instrumentation due to ects.

Finally, we provide a method to pinpoint the root cause of a concurrency bug, 
which is key to xing the bug. Given the capability of bug reproduction, the 
localization of a concurrency bug is still challenging because of the hundreds 
of context-switches and thousands of race pairs in the execution trace. 
Existing localization techniques report many false positives or redundancies, 
leaving the onus to the programmer to determine whether each report is 
responsible for the triggered bug, which is a laborious and error-prone task. 
In this thesis proposal, we develop a technique that deterministically 
pinpoints the root cause of concurrency bugs. The high ects of the 
context-switches within the buggy execution. The method is general, accepting 
order violation bugs and latent bugs, and reports no false positives even given 
a non-concurrency bug. Experiments on real world concurrency bugs show that the 
method can localize a concurrency bug to one context-switch, from 10 to 
6,377,256 context-switches and up to one billion high level race pairs in the 
execution trace.


Date:			Monday, 22 June 2015

Time:                   10:00am - 12:00noon

Venue:                  Room 2132C
                         lift 19

Committee Members:	Dr. Charles Zhang (Supervisor)
  			Dr. Lin Gu (Chairperson)
 			Prof. Shing-Chi Cheung
  			Prof. Fangzhen Lin


**** ALL are Welcome ****