Deadlock Detection and Replay of Multi-Thread Programs Based on Refined Segmentation and Lock Graphs

Dynamic deadlock detection methods build segmentation graphs and lock graphs by extracting program behavior information from its running traces. However, existing segmentation graphs cannot model causal dependence caused by coupling of lock acquisition and thread fork operations. Lock sets in existing lock graphs cannot capture the information that a lock is held first and released soon. Both problems lead to false positives. In this work, segments in segmentation graphs are divided into fine-grained ones by identifying more causal dependence implied in a running trace. Segmentation graphs and lock graphs are extended with detailed lock acquisition and release information, based on which a deadlock detection method is proposed. To ensure authenticity of detected potential deadlocks, a deterministic scheduling scheme for deadlock replay is derived. In experiments, the proposed methods are implemented in CalFuzzer and its performance is better than PNULock and SegLock in terms of detection accuracy as well as time and memory overhead on eight Java multi-thread program examples.