计算机科学 ›› 2019, Vol. 46 ›› Issue (5): 13-20.doi: 10.11896/j.issn.1002-137X.2019.05.002
薄莉莉1, 姜淑娟1, 张艳梅1, 王兴亚2, 于巧3
BO Li-li1, JIANG Shu-juan1, ZHANG Yan-mei1, WANG Xing-ya2, YU Qiao3
摘要: 多核时代的到来使得并发程序的设计备受人们关注。然而,并发程序的并发性和不确定性容易引发并发缺陷。因此,快速且有效地检测出这些并发缺陷尤为重要。首先,将目前常见的并发缺陷分为五大类(并发类型状态缺陷、死锁、数据竞争、原子性违背和顺序违背);随后,从软件运行的角度,将现有的并发缺陷检测技术分为静态分析、动态分析和动静结合分析,并对每一类进行详细的分析、比较和总结;接着,对并发缺陷检测技术的通用性进行分析和总结;最后,从通用准确的并发缺陷检测、软硬件相结合的并发缺陷检测、并发缺陷检测修复一体化、适用于松散内存模型的并发缺陷检测、安卓等其他应用平台的并发缺陷检测和分布式系统非确定性并发缺陷研究等方面,对并发缺陷检测技术的未来研究进行了探讨。
中图分类号:
[1]PINTO G,TORRES W,FERNANDES B,et al.A large-scalestudy on the usage of Java’s concurrent programming constructs [J].Journal of Systems & Software,2015,106(C):59-81. [2]LEVESON N G,TURNER C S.An investigation of the Therac-25 accidents [J].Computer,1993,26(7):18-41. [3]POULSEN K.Software bug contributed to blackout [EB/OL].http://www.securityfocus.com/news/8016. [4]TAYLOR R N.A general-purpose algorithm for analyzing concurrent programs [J].Communications of the ACM,1983,26(5):361-376. [5]TAYLOR R N,LEVINE D L,KELLY C D.Structural Testing of Concurrent Programs [J].IEEE Transactions on Software Engineering,1992,18(3):206-215. [6]SU X H,YU Z,WANG T T,et al.An Survey on Exposing,Detecting and Avoiding Concurrency Bug [J].Chinese Journal of Computers,2015,38(11):2215-2233.(in Chinese)苏小红,禹振,王甜甜,等.并发缺陷暴露、检测与规避研究综述[J].计算机学报,2015,38(11):2215-2233. [7]JIANG Y Y,XU C,MA X X,et al.Approaches to ObtainingShared Memory Dependences for Dynamic Analysis of Concurrent Programs:A Survey [J].Ruan Journal of Software,2017,28(4):747-763.(in Chinese)蒋炎岩,许畅,马晓星,等.获取访存依赖:并发程序动态分析基础技术综述 [J].软件学报,2017,28(4):747-763. [8]LU S,PARK S,SEO E,et al.Learning from Mistakes:A Comprehensive Study on Real World concurrency bug characteristics[C]∥Proceedings of the 13th International Conference on Architectural Support for Programming Languages and Operating Systems.New York:ACM,2008:329-339. [9]WU Z D,LU K,WANG X P.Surveying concurrency bug detectors based on types of detected bugs [J].Science China Information Sciences,2017(3):5-31. [10]BIANCHI F A,MARGARA A,PEZZ`E M.A Survey of Recent Trends in Testing Concurrent Software Systems [J].IEEE Transactions on Software Engineering,2017,PP(99):1-40. [11]Jlint1[EB/OL].http://www.ispras.ru/~knizhnik/jlint. [12]ARTHO C,BIERE A.Applying Static Analysis to Large-Scale,Multi-Threaded Java Programs[C]∥Proceedings of the 13th Australian Conference on Software Engineering.Washington:IEEE,2001:68. [13]NAIK M,PARK C S,SEN K,et al.Effective Static Deadlock Detection[C]∥Proceedings of the 31st International Conference on Software Engineering.Washington:IEEE,2009:386-396. [14]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. [15]NAIK M,AIKEN A,WHALEY J.Effective static race detection for Java [J].Acm Sigplan Notices,2006,41(6):308-319. [16]LU S,PARK S,HU C,et al.MUVI:Automatically Inferring Multi-variable Access Correlations and Detecting Related Semantic and Concurrency Bugs[C]∥Proceedings of the 21st ACM SIGOPS Symposium on Operating Systems Principles.New York:ACM,2007:103-116. [17]HUANG J.Scalable Thread Sharing Analysis[C]∥Proceedings of the International Conference on Software Engineering.New York:ACM,2016:1097-1108. [18]STERLING N.Warlock-A Static Data Race Analysis Tool[C]∥Proceedings of the USENlx Winter.San Diego,1993:97-106. [19]SASTURKAR A,AGARWAL R,WANG L,et al.Automated Type-Based Analysis of Data Races and Atomicity[C]∥Proceedings of the 10th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming.New York:ACM,2005:83-94. [20]FLANAGAN C,FREUND S N,LIFSHIN M,et al.Types for atomicity:Static checking and inference for Java [J].ACM Trans on Programming Languages & Systems,2008,30(4):1-53. [21]HOVEMEYER D,PUGH W.Finding bugs is easy [J].AcmSigplan Notices,2004,39(12):132-136. [22]HOVEMEYER D,PUGH W.Finding Concurrency Bugs In Java[C]∥Proceedings of the PODC Workshop on Concurrency & Synchronization in Java Programs.2004:1-10. [23]VAZIRI M,TIP F,DOLBY J.Associating synchronization constraints with data in an object-oriented language[C]∥Procee-dings of the 33rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages.New York:ACM,2006:334-345. [24]KING J C.Symbolic execution and program testing [J].Communications of the ACM,1976,19(7):385-394. [25]SEN K.Concolic Testing[C]∥Proceedings of the 22nd IEEE/ACM International Conference on Automated Software Engineering.New York:ACM,2007:571-572. [26]WANG X Y,SUN J,CHEN Z B,et al.Towards optimal concolic testing[C]∥Proceedings of the 40th International Conference on Software Engineering.New York:ACM,2018:291-302. [27]SEN K.Scalable automated methods for dynamic program analysis[D].Illinois:University of Illinois at Urbana-Champaign,2006. [28]FARZAN A,HOLZER A,RAZAVI N,et al.Con2colic Testing [C]∥Proceedings of the 9th Joint Meeting on Foundations of Software Engineering.New York:ACM,2013:37-47. [29]YU T T,ZAMAN T S,WANG C.DESCRY:reproducing system-level concurrency failures[C]∥Proceedings of the 11th Joint Meeting on Foundations of Software Engineering.New York:ACM,2017:694-704. [30]QADEER S,RAJAMANI S K,REHOF J.Summarizing Procedures in Concurrent Programs[C]∥Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of programming languages.New York:ACM,2004:245-255. [31]KUZNETSOV V,KINDER J,BUCUR S,et al.Efficient statemerging in symbolic execution [J].Acm Sigplan Notices,2012,47(6):193-204. [32]GUO S,KUSANO M,WANG C,et al.Assertion guided symbolic execution of multithreaded programs[C]∥Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering.New York:ACM,2015:854-865. [33]GODEFROID P.Model Checking for Programming Languages using VeriSoft[C]∥Proceedings of the 24th ACM SIGPLAN-SIGACT Symposium on Principles of programming languages.New York:ACM,1997:174-186. [34]BRAT G,HAVELUND K,VISSER W.Java PathFinder-Second Generation of a Java Model Checker[C]∥Proceedings of the Workshop on Advances in Verification.2000:1-6. [35]HOLZMANN G J.The Model Checker SPIN [J].IEEE Transa-ctions on Software Engineering,2002,23(5):279-295. [36]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. [37]SERBANUTA T F,CHEN F,ROSU G.Maximal Causal Mo-dels for Sequentially Consistent Systems[C]∥Proceedings of the International Conference on Runtime Verification.Berlin:Springer,2012:136-150. [38]HUANG J,MEREDITH P O N,ROSU G.Maximal Sound Predictive Race Detection with Control Flow Abstraction[C]∥Proceedings of the ACM SIGPLAN 2014 International Conference on Programming Language Design and Implementation.New York:ACM,2014:337-348. [39]HUANG J.Stateless model checking concurrent programs with maximal causality reduction [J].Acm Sigplan Notices,2015,50(6):165-174. [40]WU X,WEN Y,CHEN L,et al.Data Race Detection for Interrupt-Driven Programs via Bounded Model Checking[C]∥Proceedings of the IEEE 7th International Conference on Software Security and Reliability-Companion.Washington:IEEE,2013:204-210. [41]KHOSHNOOD S,KUSANO M,WANG C.ConcBugAssist:Constraint Solving for Diagnosis and Repair of Concurrency Bugs[C]∥Proceedings of the International Symposium on Software Testing and Analysis.New York:ACM,2015:165-176. [42]PATRICK C,RADHIA C.Abstract Interpretation Frameworks [J].Journal of Logic & Computation,1992,2(4):511-547. [43]MCMILLAN K L.Lazy Abstraction With Interpolants[C]∥Proceedings of the International Conference on Computer Aided Verification.Berlin:Springer,2006:123-136. [44]LIBLIT B.Cooperative Bug Isolation [M].Berlin:Springer,2004:255-264. [45]SHI Y,PARK S,YIN Z,et al.Do I Use the Wrong Definition? DeFuse:Definition-Use Invariants for Detecting Concurrency and Sequential Bugs[C]∥Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications.New York:ACM,2010:160-174. [46]ZHANG M,WU Y,LU S,et al.A Lightweight System for Detecting and Tolerating Concurrency Bugs [J].IEEE Trans on Software Engineering,2016,42(10):899-917. [47]FLANAGAN C,FREUND S N,YI J.Velodrome:a sound and complete dynamic atomicity checker for multithreaded programs[C]∥Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation.New York:ACM,2008:293-303. [48]SORRENTINO F,FARZAN A,MADHUSUDAN P.PENELOPE:Weaving Threads to Expose Atomicity Violations[C]∥Proceedings of the ACM SIGSOFT International Symposium on Foundations of Software Engineering.New York:ACM,2010:37-46. [49]PARK S,VUDUC R W,HARROLD M J.Falcon:Fault Localization in Concurrent Programs[C]∥Proceedings of the 32nd International Conference of Software Engineering.New York:ACM,2010:245-254. [50]PARK S,VUDUC R,HARROLD M J.UNICORN:a unified approach for localizing non-deadlock concurrency bugs [J].Software Testing,Verification & Reliability,2015,25(3):167-190. [51]WANG L,STOLLER S D.Accurate and Efficient Runtime Detection of Atomicity Errors in Concurrent Programs[C]∥Proceedings of the 11th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming.New York:ACM,2006:137-146. [52]HUANG J,ZHANG C.Persuasive Prediction of ConcurrencyAccess Anomalies[C]∥Proceedings of the 2011 International Symposium on Software Testing and Analysis.New York:ACM,2011:144-154. [53]HUANG J,RAJAGOPALAN A K.Precise and maximal race detection from incomplete traces [J].Acm Sigplan Notices,2016,51(10):462-476. [54]HUANG J,LUO Q Z,ROSU G.GPredict:Generic Predictive Concurrency Analysis[C]∥Proceedings of the 37th Internatio-nal Conference on Software Engineering.NJ:IEEE Press,2015:847-857. [55]HUANG J.UFO:predictive concurrency use-after-free detection[C]∥Proceedings of the 40th International Conference on Software Engineering.New York:ACM,2018:609-619. [56]BISWAS S,HUANG J,SENGUPTA A,et al.DoubleChecker:Efficient Sound and Precise Atomicity Checking[C]∥Procee-dings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation.New York:ACM,2014:28-39. [57]EDELSTEIN O,FARCHI E,NIR Y,et al.Multithreaded Java program test generation [J].Ibm Systems Journal,2002,41(1):111-125. [58]LEE S,HWANG S,RYU S.All about activity injection:Threats,semantics,and detection[C]∥Proceedings of the IEEE/ACM International Conference on Automated Software Engineering.New York:ACM,2017:252-262. [59]SEN K.Race directed random testing of concurrent programs [J].Acm Sigplan Notices,2008,43(6):11-21. [60]PARK S,LU S,ZHOU Y Y.CTrigger:exposing atomicity violation bugs from their hiding places [J].ACM SIGARCH Computer Architecture News,2009,37(1):25-36. [61]SAVAGE S,BURROWS M,NELSON G,et al.Eraser:a dynamic data race detector for multithreaded programs [J].ACM Trans on Computer Systems,1997,15(4):391-411. [62]FLANAGAN C,FREUND S N.Atomizer:a dynamic atomicity checker for multithreaded programs [J].Science of Computer Programming,2008,71(2):89-109. [63]ELMAS T,QADEER S,TASIRAN S.Goldilocks:a race andtransaction-aware java runtime[C]∥Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation.New York:ACM,2007:245-255. [64]LAMPORT L.Time,clocks,and the ordering of events in a distributed system [J].Communications of the Acm,1978,21(7):558-565. [65]POZNIANSKY E,SCHUSTER A.MultiRace:efficient on-the-fly data race detection in multithreaded C++ programs [J].Concurrency & Computation Practice & Experience,2007,19(3):327-340. [66]FLANAGAN C,FREUND S N.FastTrack:Efficient and Precise Dynamic Race Detection[C]∥Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design & Implementation.New York:ACM,2009:121-133. [67]CAI Y,ZHANG J,CAO L W,et al.A deployable samplingstrategy for data race detection[C]∥Proceedings of the 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering.New York:ACM,2016:810-821. [68]LAI Z,CHEUNG S C,CHAN W K.Detecting Atomic-Set Seria-lizability Violations in Multithreaded Programs through Active Randomized Testing[C]∥Proceedings of the 32nd ACM/IEEE International Conference on Software Engineering.New York:ACM,2010:235-244. [69]ZHANG W,LIM J,OLICHANDRAN R,et al.ConSeq:detecting concurrency bugs through sequential errors[C]∥Procee-dings of the International Conference on Architectural Support for Programming Languages and Operating Systems.New York:ACM,2011:251-264. [70]CAI Y,LU Q.Dynamic Testing for Deadlocks via Constraints [J].IEEE Transactions on Software Engineering,2016,42(9):825-842. [71]CHOI J D,LEE K,LOGINOV A,et al.Efficient and Precise Datarace Detection for Multithreaded Object-Oriented Programs[C]∥Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language Design and Implementation.New York:ACM,2002:258-269. [72]YOGA A,NAGARAKATTE S,GUPTA A.Parallel Data Race Detection for Task Parallel Programs with Locks[C]∥Procee-dings of the 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering.New York:ACM,2016:833-845. [73]HAMMER C,DOLBY J,VAZIRI M,et al.Dynamic Detection of Atomic-Set-Serializability Violations[C]∥Proceedings of the 30th International Conference on Software Engineering.New York:ACM,2008:231-240. [74]LUCIA B,CEZE L,STRAUSS K.ColorSafe:Architectural Support for Debugging and Dynamically Avoiding Multi-Variable Atomicity Violations[C]∥Proceedings of the 37th Annual International Symposium on Computer architecture.Saint-Malo,New York:ACM,2010:222-233. [75]LETKO Z,VOJNAR T,KRENA B.AtomRace:Data Race and Atomicity Violation Detector and Healer[C]∥Proceedings of the 6th workshop on Parallel and distributed systems:testing,analysis,and debugging.New York:ACM,2008:1-10. [76]CAI Y,CAO L W,ZHAO J.Adaptively Generating High Quality Fixes for Atomicity Violations[C]∥Proceedings of the 11th Joint Meeting on Foundations of Software Engineering.New York:ACM,2017:303-314. [77]HUANG A.Maximally Stateless Model Checking for Concur-rent Bugs under Relaxed Memory Models[C]∥Proceedings of the IEEE/ACM 38th International Conference on Software Engineering Companion.New York:ACM,2016:686-688. [78]KARTIK N,SURESH J.Automated Detection of Serializability Violations Under Weak Consistency[C]∥Proceedings of the 29th International Conference on Concurrency Theory.Schloss Dagstuhl,2018:1-18. [79]WANG J,JIANG Y Y,XU C,et al.AATT+:Effectively manifesting concurrency bugs in Android apps [J].Science of Computer Programming,2018,163:1-18. [80]ZHOU J,SILVESTRO S,LIU H,et al.UNDEAD:Detectingand preventing deadlocks in production software[C]∥Proceedings of the IEEE/ACM International Conference on Automated Software Engineering.New York:ACM,2017:729-740. [81]SUN Q.Detecting and Replaying Data Races in Android Applications [D].Nanjing:Nanjing University,2017.(in Chinese)孙全.安卓应用数据竞争的检测与再现 [D].南京:南京大学,2017. [82]WIN T Y,TIANFIELD H,MAIR Q.Big Data Based Security Analytics for Protecting Virtualized Infrastructures in Cloud Computing [J].IEEE Transactions on Big Data,2018,4(1):11-25. [83]LIU Y,SUN X H.CaL:Extending Data Locality to ConsiderConcurrency for Performance Optimization [J].IEEE Transactions on Big Data,2018,5(2):273-288. |
[1] | 赵静文, 付岩, 吴艳霞, 陈俊文, 冯云, 董继斌, 刘嘉琪. 多线程数据竞争检测技术研究综述 Survey on Multithreaded Data Race Detection Techniques 计算机科学, 2022, 49(6): 89-98. https://doi.org/10.11896/jsjkx.210700187 |
[2] | 李发光, 伊力哈木·亚尔买买提. 基于改进CenterNet的航拍绝缘子缺陷实时检测模型 Real-time Detection Model of Insulator Defect Based on Improved CenterNet 计算机科学, 2022, 49(5): 84-91. https://doi.org/10.11896/jsjkx.210400142 |
[3] | 滕俊元, 高猛, 郑小萌, 江云松. 噪声可容忍的软件缺陷预测特征选择方法 Noise Tolerable Feature Selection Method for Software Defect Prediction 计算机科学, 2021, 48(12): 131-139. https://doi.org/10.11896/jsjkx.201000168 |
[4] | 文进, 张星宇, 沙朝锋, 刘艳君. 基于次模函数最大化的测试用例集约简 Test Suite Reduction via Submodular Function Maximization 计算机科学, 2021, 48(12): 75-84. https://doi.org/10.11896/jsjkx.210300086 |
[5] | 刘鑫, 黄沁元, 李强, 冉茂霞, 周颖, 杨天. 基于卷积神经网络和声振图像的磁瓦内部缺陷检测 Fault Detection for Arc Magnet Based on Convolutional Neural Network and Acoustic VibrationImage 计算机科学, 2021, 48(11A): 648-654. https://doi.org/10.11896/jsjkx.210100161 |
[6] | 彭磊, 张辉. 基于U-net的道路缺陷检测 U-net for Pavement Crack Detection 计算机科学, 2021, 48(11A): 616-619. https://doi.org/10.11896/jsjkx.201200059 |
[7] | 孙昌爱, 张守峰, 朱维忠. 一种基于变异分析的BPEL程序故障定位技术 Mutation Based Fault Localization Technique for BPEL Programs 计算机科学, 2021, 48(1): 301-307. https://doi.org/10.11896/jsjkx.200900051 |
[8] | 谢源, 苗玉彬, 许凤麟, 张铭. 基于半监督深度卷积生成对抗网络的注塑瓶表面缺陷检测模型 Injection-molded Bottle Defect Detection Using Semi-supervised Deep Convolutional Generative Adversarial Network 计算机科学, 2020, 47(7): 92-96. https://doi.org/10.11896/jsjkx.190700093 |
[9] | 杨志伟, 戴铭, 周智恒. 基于直方图差异的工业产品表面缺陷检测方法 Surface Defect Detection Method of Industrial Products Based on Histogram Difference 计算机科学, 2020, 47(6A): 247-249. https://doi.org/10.11896/JsJkx.191000049 |
[10] | 夏春艳, 王兴亚, 张岩. 基于多目标优化的测试用例优先级排序方法 Test Case Prioritization Based on Multi-objective Optimization 计算机科学, 2020, 47(6): 38-43. https://doi.org/10.11896/jsjkx.191100113 |
[11] | 罗月,童卞,景帅,张蒙,饶永明,闫峰. 基于卷积去噪自编码器的芯片表面弱缺陷检测方法 Detection Method of Chip Surface Weak Defect Based on Convolution Denoising Auto-encoders 计算机科学, 2020, 47(2): 118-125. https://doi.org/10.11896/jsjkx.190100141 |
[12] | 李志博,李清宝,于磊,侯雪梅. 基于划分的自适应随机测试综述 Survey on Adaptive Random Testing by Partitioning 计算机科学, 2019, 46(3): 19-29. https://doi.org/10.11896/j.issn.1002-137X.2019.03.003 |
[13] | 胡海兵, 徐挺, 张波, 徐东建, 金施群, 卢荣胜. OpenMP与环形缓冲技术在TFT-LCD缺陷检测中的应用 Application of Open MP and Ring Buffer Technology in Defects Detection of Glass Substrate 计算机科学, 2019, 46(11A): 562-566. |
[14] | 王蓁蓁, 刘嘉. 基于校正因子的随机TBFL方法 Stochastic TBFL Approach Based on Calibration Factor 计算机科学, 2019, 46(11): 161-167. https://doi.org/10.11896/jsjkx.191100503C |
[15] | 包晓安, 熊子健, 张唯, 吴彪, 张娜. 一种基于改进遗传算法的路径测试用例生成方法 Approach for Path-oriented Test Cases Generation Based on Improved Genetic Algorithm 计算机科学, 2018, 45(8): 174-178. https://doi.org/10.11896/j.issn.1002-137X.2018.08.031 |
|