Recon: A Tool for Finding and Understanding Concurrency Bugs

Brandon Lucia, Benjamin P. Wood and Luis Ceze
University of Washington
Dept. Computer Science and Engineering

Recon is a tool for helping you understand bugs in multithreaded programs. The process starts when you get a bug report. Once you can repro the bug, you run your program a bunch of times with our tool. The tool collects information about how threads in the program communicated with one another. You (or a script) watch the program run, and after each run, you decide if the bug occurred, or didn't occur. You file output from Recon into a 'buggy' directory if the bug happened, and a 'nonbuggy' directory if the bug didn't happen.

After you have collected information from a dozen or a couple dozen executions, you can use Recon to convert that information into Reconstructions. The reconstructions Recon produces show you a short, focused snippet of the program's execution. The operations included in the reconstruction are ones that our statistical ranking algorithm determined are related to the bug. The output shows up in shiny pdf files, with one reconstruction per pdf. If the bug you are fighting was really a concurrency problem, you will probably see its cause in one of the top ranked reconstructions.

What is a Reconstruction?

A Reconsructed Execution Fragment
The example shows a reconstruction of a portion of the execution of a simple bank account toy program. The circles in the figure each correspond to a dynamic instance of a code point from an execution of the bank account program. The thick arc in the figure shows that an instruction on line 75 of the bank account program communicated with line 100 via a shared memory variable. The lighter arcs show ordering relationships between events. The weight on the light arcs indicates how frequently each ordering relationship was observed in the executions that were monitored by ReconCollect. In this example, the reconstruction shows a sequence of events that was likely to have led to the bug. Specifically, it shows that line BankAccount.c:72 was followed by BankAccount.c:75, executed by two different threads, then BankAccount.c:100, and finally, BankAccount.c:61. If you were debugging this program, you could use this reconstruction to try to understand (1)what happens when that sequence of events occurs and (2)how to prevent that sequence from occurring, if it is a bug.

Download Recon Here! The Recon download comes with full source code. Recon is available for non-commercial use. The University of Washington prefers that the download link goes through the academic use license website. When you agree, you'll be redirected to a source distribution. In the source distribution, there is documentation, including a full walk-through tutorial on how to use Recon. The source distribution also includes sample output for an included example program to give you an idea of what Recon can do.

Recon is based on our PLDI 2011 paper .

If you are interested please check out our other work on detecting and avoiding concurrency errors. Recon will be available for download for non-commercial use, including full source code. There are two parts to the tool:

ReconCollect: The context-aware communication graph collection module.

ReconCollect is a tool that can be built for C/C++ and for Java. For C/C++, ReconCollect can be built as a pintool for use with Pin. For Java, ReconCollect can be built as a tool for use with RoadRunner. ReconCollect will dynamically instrument your program to produce context-aware communication graphs in json format.

ReconRank: The reconstruction generation and ranking module.

ReconRank is a platform independent module that uses the output of ReconCollect to reconstruct fragments of your multithreaded program's execution. When you use Recon to debug an error, you use ReconCollect to collect a set of graphs from correct runs and from buggy runs. These sets of graphs are the input to ReconRank. ReconRank uses the graphs to reconstruct snippets of multithreaded execution. Then, using statistical inference, ReconRank produces a ranked list of reconstructions. Reconstructions with higher rank are more likely to point you to the root cause of your bug. ReconRank outputs a list of reconstructions, also in json format, in order of their rank. Optionally, Recon can convert these json representations into graphics, using dot.