计算机科学 ›› 2022, Vol. 49 ›› Issue (6): 89-98.doi: 10.11896/jsjkx.210700187
赵静文1, 付岩1, 吴艳霞1, 陈俊文2, 冯云2, 董继斌1, 刘嘉琪1
ZHAO Jing-wen1, FU Yan1, WU Yan-xia1, CHEN Jun-wen2, FENG Yun2, DONG Ji-bin1, LIU Jia-qi1
摘要： 随着多核处理器在现代计算机设备中的流行,在软件中使用多线程程序的频率也随之增加。但多线程程序的不确定性会导致程序在运行过程中出现数据竞争、原子性违背、顺序违背和死锁等并发问题。研究发现,在所有并发缺陷中,数据竞争所占的比例最大,而且大多数原子性违背和顺序违背也是由数据竞争引起的。为解决这一问题,学者们先后提出了相关的检测技术,文中对近年来该领域的研究技术进行了总结。首先,介绍了数据竞争的相关概念和产生原因,以及数据竞争检测的主要思想;然后根据程序是否执行将现有的数据竞争检测技术分为静态分析、动态分析和混合检测技术三大类,归纳分析了每类技术的特点并进行了详细的比较;随后,从程序员角度阐明了现有检测技术存在的问题;最后,根据发展现状,对该领域的未来发展方向进行了分析与探讨。
中图分类号:
| [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] | 张光华, 高天娇, 陈振国, 于乃文. 基于N-Gram静态分析技术的恶意软件分类研究 Study on Malware Classification Based on N-Gram Static Analysis Technology 计算机科学, 2022, 49(8): 336-343. https://doi.org/10.11896/jsjkx.210900203 |
| [2] | 李明磊, 黄晖, 陆余良, 朱凯龙. SymFuzz:一种复杂路径条件下的漏洞检测技术 SymFuzz:Vulnerability Detection Technology Under Complex Path Conditions 计算机科学, 2021, 48(5): 25-31. https://doi.org/10.11896/jsjkx.200600128 |
| [3] | 陈晨, 周宇, 王永超, 黄志球. 基于情境感知的API个性化推荐 Context-aware Based API Personalized Recommendation 计算机科学, 2021, 48(12): 100-106. https://doi.org/10.11896/jsjkx.201000127 |
| [4] | 崔凯, 赵国亮, 周宽久, 李明楚. 一种解决嵌入式软件并发缺陷的建模方法 Model of Embedded Software for Solving Concurrent Defects 计算机科学, 2020, 47(6): 24-31. https://doi.org/10.11896/jsjkx.191100187 |
| [5] | 李梦珂, 郑秋生, 王磊. 基于采样技术的动态混合数据竞争检测算法 Dynamic Hybrid Data Race Detection Algorithm Based on Sampling Technique 计算机科学, 2020, 47(10): 315-321. https://doi.org/10.11896/jsjkx.190700079 |
| [6] | 薄莉莉, 姜淑娟, 张艳梅, 王兴亚, 于巧. 并发缺陷检测技术研究进展 Research Progress on Techniques for Concurrency Bug Detection 计算机科学, 2019, 46(5): 13-20. https://doi.org/10.11896/j.issn.1002-137X.2019.05.002 |
| [7] | 谢念念, 曾凡平, 周明松, 秦晓霞, 吕成成, 陈钊. 多维敏感特征的Android恶意应用检测 Android Malware Detection with Multi-dimensional Sensitive Features 计算机科学, 2019, 46(2): 95-101. https://doi.org/10.11896/j.issn.1002-137X.2019.02.015 |
| [8] | 帕尔哈提江·斯迪克, 马建峰, 孙聪. 一种面向二进制的细粒度控制流完整性方法 Fine-grained Control Flow Integrity Method on Binaries 计算机科学, 2019, 46(11A): 417-420. |
| [9] | 姬秀娟, 孙晓卉, 许静. 基于复杂控制流的源代码内存泄漏静态检测 Source Code Memory Leak Static Detection Based on Complex Control Flow 计算机科学, 2019, 46(11A): 517-523. |
| [10] | 朱朝阳,陈相舟,闫龙,张信明. 基于主成分分析法的人工免疫识别软件缺陷预测模型研究 Research on Software Defect Prediction Based on AIRS Using PCA 计算机科学, 2017, 44(Z6): 483-485. https://doi.org/10.11896/j.issn.1002-137X.2017.6A.107 |
| [11] | 宁卓,邵达成,陈勇,孙知信. 基于签名与数据流模式挖掘的Android恶意软件检测系统 Android Static Analysis System Based on Signature and Data Flow Pattern Mining 计算机科学, 2017, 44(Z11): 317-321. https://doi.org/10.11896/j.issn.1002-137X.2017.11A.067 |
| [12] | 缪旭东,王永春,曹星辰,方峰. 基于模式匹配的安全漏洞检测方法 Detection Approach for Security Vulnerability Based on Pattern Matching 计算机科学, 2017, 44(4): 109-113. https://doi.org/10.11896/j.issn.1002-137X.2017.04.024 |
| [13] | 魏苗,吴毅坚,沈立炜,彭鑫,赵文耘. 基于静态分析的JavaScript类型失配缺陷查找 Finding Type Mismatch Defects of JavaScript Based on Static Analysis 计算机科学, 2017, 44(4): 223-228. https://doi.org/10.11896/j.issn.1002-137X.2017.04.048 |
| [14] | 刘艳娜,陈莉,唐生林. 一个面向任务图并行程序的错误检查工具 Error Checking Tool for DAG-based Task Parallel Programs 计算机科学, 2017, 44(3): 38-41. https://doi.org/10.11896/j.issn.1002-137X.2017.03.010 |
| [15] | 吕照进,沈立炜,赵文耘. 面向场景的安卓应用代码定位方法 Scenario-oriented Location Method of Android Applications 计算机科学, 2017, 44(2): 216-221. https://doi.org/10.11896/j.issn.1002-137X.2017.02.035 |
|
||
首页