Surveying concurrency bug detectors based on types of detected bugs  

作　　者：Zhendong WU Kai LU Xiaoping WANG 

机构地区：[1]Science and Technology on Parallel and Distributed Processing Laboratory, National University of Defense Technology, Changsha 410073, China [2]College of Computer, National University of Defense Technology, Changsha 410073, China

出　　处：《Science China(Information Sciences)》2017年第3期1-27,共27页中国科学（信息科学）（英文版）

基　　金：supported by National High Technology Research and Development Program of China(863 Program)(Grant Nos.2012AA01A301,2012AA010901);Program for New Century Excellent Talents in University and National Natural Science Foundation of China(Grant Nos.61402486,61402492,61272142);Moreover,it is a part of Innovation Fund Sponsor Project of Excellent Postgraduate Student(Grant No.B130608)

摘　　要：Concurrency bugs widely exist in concurrent programs and have caused severe failures in the real world. Researchers have made significant progress in detecting concurrency bugs, which improves software reliability. In this paper, we survey the most up-to-date and well-known concurrency bug detectors. We categorize the existing detectors based on the types of concurrency bugs. Consequently, we analyze data race detectors, atomicity violation detectors, order violation detectors, and deadlock detectors, respectively. We also discuss some other techniques which are mostly related to concurrency bug detection, including schedule bounding techniques, interleaving optimizing techniques, path expanding techniques, and deterministic replay techniques. Additionally, we statistically analyze the reviewed detectors and get some interesting findings, for instance, nearly 86% of previous detectors focus on data races and atomicity violations, and dynamic approaches are popular （74%）. We also discuss the limitations of previous detectors, finding that 91% of previous detectors suffer from false negatives and 64% of previous detectors suffer from runtime overhead. Based on the reviewed detectors and statistical analysis, we conclude some future research directions, including accuracy, performance, applicability, and integrality.Concurrency bugs widely exist in concurrent programs and have caused severe failures in the real world. Researchers have made significant progress in detecting concurrency bugs, which improves software reliability. In this paper, we survey the most up-to-date and well-known concurrency bug detectors. We categorize the existing detectors based on the types of concurrency bugs. Consequently, we analyze data race detectors, atomicity violation detectors, order violation detectors, and deadlock detectors, respectively. We also discuss some other techniques which are mostly related to concurrency bug detection, including schedule bounding techniques, interleaving optimizing techniques, path expanding techniques, and deterministic replay techniques. Additionally, we statistically analyze the reviewed detectors and get some interesting findings, for instance, nearly 86% of previous detectors focus on data races and atomicity violations, and dynamic approaches are popular （74%）. We also discuss the limitations of previous detectors, finding that 91% of previous detectors suffer from false negatives and 64% of previous detectors suffer from runtime overhead. Based on the reviewed detectors and statistical analysis, we conclude some future research directions, including accuracy, performance, applicability, and integrality.

关 键 词：concurrency bug detection data race atomicity violation order violation DEADLOCK 

分 类 号：TP311.53[自动化与计算机技术—计算机软件与理论]