Computer Science

Computer Science ›› 2022, Vol. 49 ›› Issue (6): 89-98.doi: 10.11896/jsjkx.210700187

• High Performance Computing • Previous Articles     Next Articles

Survey on Multithreaded Data Race Detection Techniques

ZHAO Jing-wen1, FU Yan1, WU Yan-xia1, CHEN Jun-wen2, FENG Yun2, DONG Ji-bin1, LIU Jia-qi1   

  1. 1 College of Computer Science and Technology,Harbin Engineering University,Harbin 150001,China
    2 Beijing Institute of Control and Electronic Technology,Beijing 100038,China
  • Received:2021-07-19 Revised:2021-12-11 Online:2022-06-15 Published:2022-06-08
  • About author:ZHAO Jing-wen,born in 1995,Ph.D candidate.Her main research interests include concurrent program analysis and compi-ler technology.
    FU Yan,born in 1978,master,lecturer,is a member of China Computer Federation.Her main research interests include computer architecture and compi-ler technology.

PDF (PC)

811

Abstract: Nowadays the multi-core processors and threaded parallel programs are increasingly more used.However,the uncertainty of multi-threaded program leads to concurrency problems such as data race,atomicity violation,order violation and deadlock in the process of program running.Recent researches show that data race accounts for the largest proportion of concurrency bug,and most atomicity violation and order violation are caused by data race.This paper summarizes the related detection techniques in recent years.Firstly,the related concepts,causes,and the main ideas of data race detection are introduced.Then,the existing data race detection techniques in multi-threaded program are classified into three types:static analysis,dynamic analysis and hybrid detection techniques,and their characteristics are summarized comprehensively and compared in detail.Next,the limitations of exis-ting data race detection tools are discussed.Finally,future research directions and challenges in this field are discussed.

Key words: Concurrency bug, Data race, Detection techniques, Dynamic analysis, Static analysis

CLC Number: 

  • TP311
[1] WANG C,YUAN X L,CUI Y,et al.Toward Secure Outsourced Middlebox Services:Practices,Challenges,and Beyond[J].IEEE Network,2017,32(1):166-171.
[2] LU S,PARK S,SEO E,et al.Learning from Mistakes－A Comprehensive Study on Real World Concurrency Bug Characteristics[J].Computer Architecture News,2008,36(1):329-339.
[3] JU Y,HUANG Y H,ZHENG J T,et al.Multi-thread Parallel Algorithm for Reconstructing 3D Large-Scale Porous Structures[J].Computers & Geosciences,2017,101:10-20.
[4] SEREBRYANY K,ISKHODZHANOV T.ThreadSanitizer-Data Race Detection in Practice[C]//Proceedings of the Workshop on Binary Instrumentation and Applications.New York:ACM,2009:62-71.
[5] SU X H,YU Z,WANGT T,et al.A Survey on Exposing,Detecting and Avoiding Concurrency Bugs[J].Chinese Journal of Computers,2015,38(11):2215-2233.
[6] DENG D D,ZHANG W,LU S.Efficient Concurrency-Bug Detection Across Inputs[J].ACM Sigplan Notices,2013,48(1):785-802.
[7] LAMPORT L.Time,Clocks,and the Ordering of Events in aDistributed System[J].Communications of the ACM,1978,21(7):558-565.
[8] SAVAGE S,BURROWS M,NELSON G,et al.Eraser:A Dynamic Data Race Detector for Multi-Threaded Programs[J].ACM Transactions on Computer Systems,1997,15(4):391-411.
[9] BO L L,JIANG S J,ZHANG Y M,et al.Research Progress on Techniques for Concurrency Bug Detection[J].Computers Science,2019,46(5):20-27.
[10] ENGLER D,ASHCRAFT K.RacerX:Effective,Static Detection of Race Conditions and Deadlocks[C]//Proceedings of the 19th ACM Symposium on Operating Systems Principles.New York:ACM,2003:237-252.
[11] NAIK M,AIKEN A,WHALEY J.Effective Static Race Detection for Java[J].ACM Sigplan Notices,2006,41(6):308-319.
[12] WU X G,CHEN L Q.Static Analysis of Runtime Errors in Interrupt-Driven Programs via Sequentialization[J].ACM Transactions on Embedded Computing Systems,2016,15(4):70-95.
[13] ZHANG Y,LIU H,QIAO L.Context-Sensitive Data Race Detection for Concurrent Programs[J].IEEE Access,2021,9:20861-20867.
[14] VOUNG J W,JHALA R,LERNER S.RELAY:Static Race Detection on Millions of Lines of Code[C]//Proceedings of the 6th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT International Symposium on the Foundations of Software Engineering.Dubrovnik:ACM,2007:205-214.
[15] PRATIKAKIS P,FOSTER J S,HICKS M.LOCKSMITH:Context-Sensitive Correlation Analysis for Race Detection[J].ACM SIGPLAN Notices,2006,41(6):320-331.
[16] ANDRIANOV P,MUTILIN V,KHOROSHILOV A.Predicate Abstraction Based Configurable Method for Data Race Detection in Linux Kernel[C]//Proceedings of the International Confe-rence on Tools and Methods for Program Analysis.Moscow:Springer,2018:11-23.
[17] CHOPRA N,PAI R,DSOUZA D.Data Races and Static Analysis for Interrupt-Driven Kernels[C]//Proceedings of 28th European Symposium on Programming(ESOP).Prague:Springer,2019:697-723.
[18] SHENG T W,VACHHARAJANI N,ERANIAN S,et al.RACEZ:A Lightweight and Non-Invasive Race Detection Tool for Production Applications[C]//Proceedings of the IEEE 33th International Conference on Software Engineering.Hawaii:IEEE,2011:401-410.
[19] CAI Y,ZHANG J,CAO L W,et al.A Deployable Sampling Strategy for Data Race Detection[C]//Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering.New York:ACM Press,2016:810-821.
[20] GUO Y,CAI Y,YANG Z J.AtexRace:Across Thread and Execution Sampling for In-House Race Detection[C]//Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering.New York:ACM,2017:315-325.
[21] LI S D,XU L.A Static Data Race Detecting Method for BPEL Based on Happens-Before and Lockset[J].Computer & Digital Engineering,2010,38(8):6-9.
[22] CHEN J,ZHOU K J,JIA M.Multi-thread parallel program data race static detection model[J].Computer Engineering and Design,2017,38(5):1264-1272.
[23] NAKADE R,MERCER E,ALDOUS P,et al.Model-Checking Task-Parallel Programs for Data-Race[J].Innovations in Systems and Software Engineering,2019,15(1):367-382.
[24] TAFT S T,SCHANDA F,MOY Y.High-Integrity Multitas-king in SPARK:Static Detection of Data Races and Locking Cycles[C]//Proceedings of the IEEE 17th International Sympo-sium on High Assurance Systems Engineering.Orlando:IEEE,2016:238-239.
[25] ROYUELA S,MARTORELL X,QUIÑONES E,et al.SafeParallelism:Compiler Analysis Techniques for Ada and OpenMP[C]//Proceedings of the 23rd International Conference on Reliable Software Technologies.Portugal:Springer,2018:141-157.
[26] KAHLON V,SANKARANARAYANAN S,GUPTA A.Static Analysis for Concurrent Programs with Applications to Data Race Detection[J].International Journal on Software Tools for Technology Transfer,2013,15(4):321-336.
[27] HUANG J.Stateless Model Checking Concurrent Programswith Maximal Causality Reduction[J].ACM SIGPLAN Notices,2015,50(6):165-174.
[28] BLUM B,GIBSON G.Stateless Model Checking with Data-Race Preemption Points[J].ACM SIGPLAN Notices,2016,51(10):477-493.
[29] POZNIANSKY E,SCHUSTER A.Efficient On-the-Fly DataRace Detection in Multithreaded C+＋Programs[J].Concurrency and Computation:Practice & Experience,2003,19(3):327-340.
[30] FLANAGAN C,FREUND S N.FastTrack:Efficient and Precise Dynamic Race Detection[J].Communications of the ACM,2010,53(11):93-101.
[31] LI D,SRISA W,DWYER M B.SOS:Saving Time in Dynamic Race Detection with Stationary Analysis[J].ACM SIGPLAN Notices,2011,46(10):35-50.
[32] LI M K,ZHENG Q S,WANG L.Dynamic Hybrid Data RaceDetection Algorithm Based on Sampling Technique[J].Compu-ters Science,2020,47(10):315-321.
[33] SONG Y W,LEE Y H.Efficient Data Race Detection for C/C+＋Programs Using Dynamic Granularity[C]//Proceedings of the 2014 IEEE International Parallel & Distributed Processing Symposium.Arizona:IEEE,2014:679-688.
[34] YU M,LEE J,BAE D,et al.AdaptiveLock:Efficient HybridData Race Detection Based on Real-World Locking Patterns[J].International Journal of Parallel Programming,2019,47(7):805-837.
[35] YANG J,JIANG B,CHAN W K.HistLock+:Precise Memory Access Maintenance Without Lockset Comparison for Complete Hybrid Data Race Detection[J].IEEE Transactions on Relia-bility,2018,67(3):786-801.
[36] BISWAS S,ZHANG M J,BOND M D,et al.Valor:Efficient,Software-Only Region Conflict Exceptions[C]//Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming,Systems,Languages,and Applications.New York:ACM,2015:241-259.
[37] PENG Y F,WOOD B P,DEVIETTI J.PARSNIP:Performant Architecture for Race Safety with No Impact on Precision[C]//Proceedings of the 50th Annual IEEE/ACM International Symposium.New York:ACM,2017:490-502.
[38] PENG Y F,DELOZIER C,EIZENBERG A,et al.SLIMFAST:Reducing Metadata Redundancy in Sound and Complete Dyna-mic Data Race Detection[C]//Proceedings of the 2018 IEEE International Parallel and Distributed Processing Symposium(IPDPS).New York:IEEE,2018:835-844.
[39] AHMAD A,LEE S,FONSECA P,et al.Kard:Lightweight Data Race Detection with Per-Thread Memory Protection[C]//Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems.NewYork:ACM,2021:647-660.
[40] YU M,MA Y S,BAE D H.Correction to:Efficient Noise Injection for Exposing Hidden Data Races[J].The Journal of Supercomputing,2020,76(21):1-32.
[41] XIE X W,XUE J L,ZHANG J.Acculock:Accurate and Efficient Detection of Data Races[J].Software Practice & Expe-rience,2013,43(5):543-576.
[42] ESLAMIMEHR M,PALSBERG J.Race Directed Scheduling of Concurrent Programs[J].ACM SIGPLAN Notices,2014,49(8):301-314.
[43] HUANG J,MEREDITH P O,ROSU G.Maximal Sound Predictive Race Detection with Control Flow Abstraction[C]//Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation.New York:ACM,2014:337-348.
[44] SUN J Z,YANG J W,YANG Z J.Random forest instruction level detection model for data race in multithreaded programs[J].Journal of Tsinghua University(Science and Technology),2020,60(10):804-813.
[45] CHEN Q L,BAI J J,JIANG Z M,et al.Detecting Data Races Caused by Inconsistent Lock Protection in Device Drivers[C]//Proceedings of the 2019 IEEE 26th International Conference on Software Analysis,Evolution and Reengineering(SANER).Hangzhou:IEEE,2019:366-376.
[46] NARAYANASAMY S,WANG Z H,TIGANI J,et al.Automatically Classifying Benign and Harmful Data Races Using Replay Analysis[J].ACM SIGPLAN Notices,2007,42(6):22-31.
[47] VEERARAGHAVAN K,CHEN P M,FLINN J,et al.Detecting and Surviving Data Races using Complementary Schedules[C]//Proceedings of the 23th ACM Symposium on Operating Systems Principles.New York:ACM,2011:369-384.
[48] KASIKCI B,ZAMFIR C,CANDEA G.Data Races vs.DataRace Bugs:Telling the Difference with Portend[J].ACM SIGPLAN Notices,2012,47(4):185-198.
[49] KAI L,WU Z,WANG X,et al.RaceChecker:Efficient Identification of Harmful Data Races[C]//Proceedings of the 2015 23rd Euromicro International Conference on Parallel,Distributed and Network-Based Processing(PDP).Turku:IEEE,2015:78-85.
[50] ZHU S X,WU Y N,SUN G L,et al.A Concurrent Harmful Races Identification Algorithm using Hadoop and Multiple Cloud Servers[J].International Journal of Performability Engineering,2018,14(10):2332-2342.
[51] MAJEED S,RYU M.Debugging Nondeterministic Failures in Linux Programs through Replay Analysis[J].Scientific Programming,2018(PT.1):1-11.
[52] DING Z J,ZHOU Z X.RaceTest:harmful data race detection based on testing technology in WS-BPEL[J].Service Oriented Computing and Applications,2019,13(5):141-154.
[53] CAI Y,ZHU B Y,MENG R J,et al.Detecting ConcurrencyMemory Corruption Vulnerabilities[C]//Proceedings of the 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering.NewYork:ACM,2019:706-717.
[54] KASIKCI B,ZAMFIR C,CANDEA G.RaceMob:Crowdsourced Data Race Detection[C]//Proceedings of the 24th ACM Symposium on Operating Systems Principles.Farmington:ACM,2013:406-422.
[55] KASIKCI B,ZAMFIR C,CANDEA G.Automated Classification of Data Races Under Both Strong and Weak Memory Models[J].ACM Transactions on Programming Languages and Systems,2015,37(3):1-44.
[56] YANG Z,YU Z,SU X H,et al.RaceTracker:Effective and Efficient Detection of Data Races[C]//Proceedings of the 17th IEEE/ACIS International Conference on Software Engineering.Shanghai:IEEE Computer Society,2016:293-300.
[57] ROEMER J,GEN K,BOND M D.SmartTrack:Efficient Predictive Race Detection[C]//Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation(PLDI).London:ACM,2020:747-762.
[58] LU S,PARK S,HU C,et al.MUVI:Automatically Inferring Multi-Variable Access Correlations and Detecting Related Semantic and Concurrency Bugs[J].ACM SIGOPS Operating Systems Review,2007,41(6):103-116.
[59] BEFROUEI M T,WANG C,WEISSENBACHER G.Abstraction and Mining of Traces to Explain Concurrency Bugs[J].Formal Methods in System Design,2016,49(1/2):1-32.
[60] BIAN P,LIANG B,SHI W C,et al.NAR-miner:Discovering Negative Association Rules from Code for Bug Detection[C]//Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering.New York:ACM,2018:411-422.
[61] JEONG D R,KIM K,SHIVAKUMAR B,et al.Razzer:Finding Kernel Race Bugs through Fuzzing[C]//Proceedings of the 2019 IEEE Symposium on Security and Privacy(SP).San Francisco:IEEE,2019:754-768.
[62] PADHIYAR S,SIVARAMAKRISHNAN K C.ConFuzz:Cove-rage-Guided Property Fuzzing for Event-Driven Programs[C]//Proceedings of the 23th International Symposium on Practical Aspects of Declarative Languages(PADL).Copenhagen:ACM,2021:127-144.
[63] XU M,KASHYAP S,ZHAO H Q,et al.Krace:Data Race Fuz-zing for Kernel File Systems[C]//Proceedings of the 2020 IEEE Symposium on Security and Privacy(SP).San Francisco:IEEE,2020:1643-1660.
[64] ZHENG L,LIAO X F,JIN H,et al.Towards Concurrency Race Debugging:An Integrated Approach for Constraint Solving and Dynamic Slicing[C]//Proceedings of the 27th International Conference on Parallel Architectures and Compilation Techniques.Limassol:ACM,2018:1-13.
[65] ZHANG Y,LIANG Y N,ZHANG D W.SRD:Static Data Race Detection for Concurrent Programs[J].International Journal of Performability Engineering,2018,11(14):2683-2691.
[66] GHOSH D,SINGH J.A Dynamic Slicing-Based Approach for Effective SBFL Technique[J].International Journal of Computational Science and Engineering,2021,24(1):98-107.
[67] YU H B,CHEN Z B,WANG J,et al.Symbolic Verification of Regular Properties[C]//Proceedings of the 40th International Conference on Software Engineering.New York:ACM,2018:871-881.
[68] WANG H J,LIU T,GUAN X H,et al.Dependence GuidedSymbolic Execution[J].IEEE Transactions on Software Engineering,2017,43(3):252-271.
[69] WEN C N,CHOU S H,CHEN T F,et al.NUDA:A Non-Uniform Debugging Architecture and Nonintrusive Race Detection for Many-Core Systems[J].IEEE Transactions on Computers,2012,61(2):199-212.
[70] HUANG R R,HALBERG E,FERRAIUOLO A,et al.Low-Overhead and High Coverage Run-Time Race Detection through Selective Meta-Data Management[C]//Proceeding of the 20th International Symposium on High Performance Computer Architecture(HPCA).Orlando:IEEE,2014:96-107.
[71] SONG Y W,LEE Y H.A Parallel FastTrack Data Race Detector on Multi-core Systems[C]//Proceeding of the 2017 IEEE International Parallel and Distributed Processing Symposium(IPDPS).Orlando:IEEE,2017:387-396.
[72] SAHNEH P S,SARIHI A,WARBURTON B,et al.RaceR:A Thread Mapping Algorithm for Race Reduction in Multi-Level Shared Caches[C]//Proceeding of the 2019 27th Euromicro International Conference on Parallel,Distributed and Network-Based Processing(PDP).Pavia:IEEE,2019:228-232.
[1] ZHANG Guang-hua, GAO Tian-jiao, CHEN Zhen-guo, YU Nai-wen. Study on Malware Classification Based on N-Gram Static Analysis Technology [J]. Computer Science, 2022, 49(8): 336-343.
[2] LI Ming-lei, HUANG Hui, LU Yu-liang, ZHU Kai-long. SymFuzz:Vulnerability Detection Technology Under Complex Path Conditions [J]. Computer Science, 2021, 48(5): 25-31.
[3] CHEN Chen, ZHOU Yu, WANG Yong-chao, HUANG Zhi-qiu. Context-aware Based API Personalized Recommendation [J]. Computer Science, 2021, 48(12): 100-106.
[4] CUI Kai, ZHAO Guo-liang, ZHOU Kuan-jiu, LI Ming-chu. Model of Embedded Software for Solving Concurrent Defects [J]. Computer Science, 2020, 47(6): 24-31.
[5] LI Meng-ke, ZHENG Qiu-sheng, WANG Lei. Dynamic Hybrid Data Race Detection Algorithm Based on Sampling Technique [J]. Computer Science, 2020, 47(10): 315-321.
[6] BO Li-li, JIANG Shu-juan, ZHANG Yan-mei, WANG Xing-ya, YU Qiao. Research Progress on Techniques for Concurrency Bug Detection [J]. Computer Science, 2019, 46(5): 13-20.
[7] XIE Nian-nian, ZENG Fan-ping, ZHOU Ming-song, QIN Xiao-xia, LV Cheng-cheng, CHEN Zhao. Android Malware Detection with Multi-dimensional Sensitive Features [J]. Computer Science, 2019, 46(2): 95-101.
[8] SIDIKE Pa-erhatijiang, MA Jian-feng, SUN Cong. Fine-grained Control Flow Integrity Method on Binaries [J]. Computer Science, 2019, 46(11A): 417-420.
[9] ZHU Chao-yang, CHEN Xiang-zhou, YAN Long and ZHANG Xin-ming. Research on Software Defect Prediction Based on AIRS Using PCA [J]. Computer Science, 2017, 44(Z6): 483-485.
[10] NING Zhuo, SHAO Da-cheng, CHEN Yong and SUN Zhi-xin. Android Static Analysis System Based on Signature and Data Flow Pattern Mining [J]. Computer Science, 2017, 44(Z11): 317-321.
[11] WEI Miao, WU Yi-jian, SHEN Li-wei, PENG Xin and ZHAO Wen-yun. Finding Type Mismatch Defects of JavaScript Based on Static Analysis [J]. Computer Science, 2017, 44(4): 223-228.
[12] MIAO Xu-dong, WANG Yong-chun, CAO Xing-chen and FANG Feng. Detection Approach for Security Vulnerability Based on Pattern Matching [J]. Computer Science, 2017, 44(4): 109-113.
[13] LV Zhao-jin, SHEN Li-wei and ZHAO Wen-yun. Scenario-oriented Location Method of Android Applications [J]. Computer Science, 2017, 44(2): 216-221.
[14] YANG Lu, YU Shou-wen and YAN Jian-feng. Type-2 Fuzzy Logic Based Multi-threaded Data Race Detection [J]. Computer Science, 2017, 44(12): 135-143.
[15] ZHANG Chi, HUANG Zhiqiu and DING Zewen. Research on Static Analysis Formalism Supporting Abstract Interpretation [J]. Computer Science, 2017, 44(12): 126-130.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.