Trace Driven Dynamic Deadlock Detection and Reproduction

Dynamic analysis techniques have been proposed to detect potential deadlocks. Analyzing and comprehending each po-tential deadlock to determine whether the deadlock is feasi-ble in a real execution requires significant programmer ef-fort. Moreover, empirical evidence shows that existing anal-yses are quite imprecise. This imprecision of the analyses further void the manual effort invested in reasoning about non-existent defects. In this paper, we address the problems of imprecision of existing analyses and the subsequent manual effort nec-essary to reason about deadlocks. We propose a novel ap-proach for deadlock detection by designing a dynamic anal-ysis that intelligently leverages execution traces. To reduce the manual effort, we replay the program by making the ex-ecution follow a schedule derived based on the observed trace. For a real deadlock, its feasibility is automatically ver-ified if the replay causes the execution to deadlock. We have implemented our approach as part of WOLF and have analyzed many large (upto 160KLoC) Java programs. Our experimental results show that we are able to identify 74 % of the reported defects as true (or false) positives au-tomatically leaving very few defects for manual analysis. The overhead of our approach is negligible making it a com-pelling tool for practical adoption