logo

SCIENCE CHINA Information Sciences, Volume 60, Issue 3: 031101(2017) https://doi.org/10.1007/s11432-015-0203-2

Surveying concurrency bug detectors based on types of detected bugs

More info
  • ReceivedOct 10, 2015
  • AcceptedFeb 3, 2016
  • PublishedOct 13, 2016

Abstract

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.


Funded by

. Moreover it is a part of Innovation Fund Sponsor Project of Excellent Postgraduate Student(B130608)

Program for New Century Excellent Talents in University and National Natural Science Foundation of China(61402492)

"source" : null , "contract" : "2012AA010901"

Program for New Century Excellent Talents in University and National Natural Science Foundation of China(61402486)

National High Technology Research and Development Program of China(863 Program)

Program for New Century Excellent Talents in University and National Natural Science Foundation of China(61272142)

"source" : null , "contract" : "2012AA01A301"


Acknowledgment

Acknowledgments

This work was supported by National High Technology Research and Development Program of China (863 Program) (Grant Nos. 2012AA01A301, 2012AA010901) and 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).


References

[1] Leveson N G, Turner C S. An investigation of the therac-25 accidents. Computer, 1993, 26: 18-41 Google Scholar

[2] Godefroid P, Nagappan N. Concurrency at Microsoft an Exploratory Survey. Technical Report, Microsoft Research, MSR-TR-2008-75. 2008. Google Scholar

[3] Abdelqawy D, Kamel A, Omara F. A survey on testing concurrent and multi-threaded applications tools and methodologies. In: Proceedings of the International Conference on Informatics and Applications, Kuala Terengganu, 2012. 458--470. Google Scholar

[4] Raza A. A review of race detection mechanisms. In: Proceedings of the 1st International Conference on Computer Science Theory and Applications. Berlin: Springer, 2006. 534--543. Google Scholar

[5] Voung J W, Jhala R, Lerner S. RELAY: static race detection on millions of lines of code. In: Proceedings of the 15th ACM SIGSOFT International Symposium on Foundations of Software Engineering. New York: ACM, 2007. 205--214. Google Scholar

[6] Engler D, Ashcraft K. RacerX: effective, static detection of race conditions and deadlocks. In: Proceedings of the 19th ACM Symposium on Operating Systems Principles. New York: ACM, 2003. 237--252. Google Scholar

[7] Qadeer S, Wu D. KISS: keep it simple and sequential. In: Proceedings of the 25th Annual ACMSIGPLAN Conference on Programming Language Design and Implementation. New York: ACM, 2004. 14--24. Google Scholar

[8] Flanagan C, Freund S N. Type-based race detection for Java. In: Proceedings of the 21st Annual ACMSIGPLAN Conference on Programming Language Design and Implementation. New York: ACM, 2000. 219--232. Google Scholar

[9] Grossman D. Type-safe multithreading in cyclone. In: Proceedings of ACM SIGPLAN Workshop on Types in Language Design and Implementation. New York: ACM, 2003. 13--25. Google Scholar

[10] Pratikakis P, Foster J S, Hicks M. Locksmith: practical static race detection for C. ACM Trans Program Lang Syst, 2011, 33: 1-55 Google Scholar

[11] Sterling N. WARLOCK-A static data race analysis tool. In: Proceedings of USENIx Winter, San Diego, 1993. 97--106. Google Scholar

[12] Park S, Lu S, Zhou Y Y. CTrigger: exposing atomicity violation bugs from their hiding places. In: Proceedings of the 14th Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2009. 25--36. Google Scholar

[13] Sen K. Race directed random testing of concurrent programs. In: Proceedings of the 29th Annual ACMSIGPLAN Conference on Programming Language Design and Implementation. New York: ACM, 2008. 11--21. Google Scholar

[14] Park C S, Sen K. Randomized active atomicity violation detection in concurrent programs. In: Proceedings of the 16th ACM SIGSOFT International Symposium on Foundations of Software Engineering. New York: ACM, 2008. 135--145. Google Scholar

[15] Yu J, Narayanasamy S, Pereira C, et al. Maple: a coverage-driven testing tool for multithreaded programs. In: Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications. New York: ACM, 2012. 485--502. Google Scholar

[16] Lai Z, Cheung S C, Chan W K. Detecting atomic-set serializability violations in multithreaded programs through active randomized testing. In: Proceedings of the 32nd ACM/IEEE International Conference on Software Engineering. New York: ACM, 2010. 235--244. Google Scholar

[17] Huang J, Zhang C. Persuasive prediction of concurrency access anomalies. In: Proceedings of the International Symposium on Software Testing and Analysis. New York: ACM, 2011. 144--154. Google Scholar

[18] Park S, Vuduc R W, Harrold M J. Falcon: fault localization in concurrent programs. In: Proceedings of the 32nd ACM/IEEE International Conference on Software Engineering. New York: ACM, 2010. 245--254. Google Scholar

[19] Park S, Vuduc R, Harrold M J. A unified approach for localizing non-deadlock concurrency bugs. In: Proceedings of IEEE 5th International Conference on Software Testing, Verification and Validation, Montreal, 2012. 51--60. Google Scholar

[20] Shi Y, Park S, Yin Z, et al. Do I use the wrong definition? DefUse: definition-use invariants for detecting concurrency and sequential bugs. In: Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications. New York: ACM, 2010. 160--174. Google Scholar

[21] Savage S, Burrows M, Nelson G, et al. Eraser: a dynamic data race detector for multithreaded programs. ACM Trans Comput Syst, 1997, 15: 391-411 CrossRef Google Scholar

[22] Hammer C, Dolby J, Vaziri M, et al. Dynamic detection of atomic-set-serializability violations. In: Proceedings of the 30th ACM/IEEE International Conference on Software Engineering. New York: ACM, 2008. 231--240. Google Scholar

[23] Brat G, Visser W. Combining static analysis and model checking for software analysis. In: Proceedings of the 16th Annual International Conference on Automated Software Engineering, San Diego, 2001. 262--269. Google Scholar

[24] Chen J, MacDonald S. Towards a better collaboration of static and dynamic analyses for testing concurrent programs. In: Proceedings of the 6th Workshop on Parallel and Distributed Systems: Testing, Analysis, and Debugging. New York: ACM, 2008. 8. Google Scholar

[25] Kasikci B, Zamfir C, Candea G. RaceMob: crowdsourced data race detection. In: Proceedings of the 23rd ACM Symposium on Operating Systems Principles. New York: ACM, 2013. 406--422. Google Scholar

[26] Wu Z D, Lu K, Wang X P, et al. Collaborative technique for concurrency bug detection. Int J Parall Program, 2015, 43: 260-285 CrossRef Google Scholar

[27] Fiedor J, Krena B, Letko Z, et al. A Uniform Classification of Common Concurrency Errors. Technical Report, Brno University of Technology, FIT-TR-2010-03. 2010. Google Scholar

[28] Lu S, Park S, Seo E, et al. Learning from mistakes: a comprehensive study on real world concurrency bug characteristics. In: Proceedings of Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2008. 329--339. Google Scholar

[29] Joshi P, Park C S, Sen K, et al. A randomized dynamic program analysis technique for detecting real deadlocks. In: Proceedings of the 30th Annual ACMSIGPLAN Conference on Programming Language Design and Implementation. New York: ACM, 2009. 110--120. Google Scholar

[30] Jin G, Thakur A, Liblit B, et al. Instrumentation and sampling strategies for cooperative concurrency bug isolation. In: Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications. New York: ACM, 2010. 241--255. Google Scholar

[31] Corp I. Parallel Inspector. http://software.intel.com/en-us/articles/intel-parallel-inspector. 2012. Google Scholar

[32] Sadowski C, Yi J. How developers use data race detection tools. In: Proceedings of the 5th Workshop on Evaluation and Usability of Programming Languages and Tools. New York: ACM, 2014. 43--51. Google Scholar

[33] Bessey A, Block K, Chelf B, et al. A few billion lines of code later: using static analysis to find bugs in the real world. Commun ACM, 2010, 53: 66-75 Google Scholar

[34] Erickson J, Musuvathi M, Burckhardt S, et al. Effective data-race detection for the kernel. In: Proceedings of the 9th USENIX Symposium on Operating Systems Design and Implementation, Berkeley, 2010. 1--16. Google Scholar

[35] Naik M, Aiken A, Whaley J. Effective static race detection for Java. In: Proceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and Implementation. New York: ACM, 2006. 308--319. Google Scholar

[36] Agarwal R, Sasturkar A, Wang L, et al. Optimized run-time race detection and atomicity checking using partial discovered types. In: Proceedings of the 20th IEEE/ACM International Conference on Automated Software Engineering. New York: ACM, 2005. 233--242. Google Scholar

[37] Flanagan C, Freund S. Detecting race conditions in large programs. In: Proceedings of the ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering. New York: ACM, 2001. 90--96. Google Scholar

[38] Abadi M, Flanagan C, Freund S N. Types for safe locking: static race detection for Java. ACM Trans Program Lang Syst, 2006, 28: 207-255 CrossRef Google Scholar

[39] Kahlon V, Sinha N, Kruus E, et al. Static data race detection for concurrent programs with asynchronous calls. In: Proceedings of the 7th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering. New York: ACM, 2009. 13--22. Google Scholar

[40] Flanagan C, Freund S N. Type inference against races. In: Static Analysis. Berlin: Springer, 2004. 116--132. Google Scholar

[41] Kidd N, Lammich P, Touilli T, et al. A static technique for checking for multiple-variable data races. Softw Tools Tech Transfer, 2010. Google Scholar

[42] Kasikci B, Zamfir C, Candea G. Data races vs. data race bugs: telling the difference with portend. In: Proceedings of the 17th Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2012. 185--198. Google Scholar

[43] Wester B, Devecsery D, Chen P M, et al. Parallelizing data race detection. In: Proceedings of the 18th Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2013. 27--38. Google Scholar

[44] Effinger-Dean L, Lucia B, Ceze L, et al. IFRit: interference-free regions for dynamic data-race detection. In: Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications. New York: ACM, 2012. 467--484. Google Scholar

[45] Flanagan C, Freund S N. FastTrack: efficient and precise dynamic race detection. In: Proceedings of the 30th Annual ACMSIGPLAN Conference on Programming Language Design and Implementation. New York: ACM, 2009. 121--133. Google Scholar

[46] Marino D, Musuvathi M, Narayanasamy S. LiteRace: effective sampling for lightweight data-race detection. In: Proceedings of the 30th Annual ACMSIGPLAN Conference on Programming Language Design and Implementation. New York: ACM, 2009. 134--143. Google Scholar

[47] Callahan R, Choi J D. Hybrid dynamic data race detection. In: Proceedings of the 8th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. New York: ACM, 2003. 167--178. Google Scholar

[48] Choi J D. Efficient and precise data race detection for multithreaded object-oriented programs. In: Proceedings of the 23rd Annual ACMSIGPLAN Conference on Programming Language Design and Implementation. New York: ACM, 2002. 258--269. Google Scholar

[49] Helmbold D P, McDowell C E. A Taxonomy of Race Detection Algorithms. Technical Report UCSC-CRL-94-35. 1994. Google Scholar

[50] Ronsse M, de Bosschere K. RecPlay: a fully integrated practical record/replay system. ACM Trans Comput Syst, 1999, 17: 133-152 CrossRef Google Scholar

[51] Huang J, Meredith P O, Rosu G. Maximal sound predictive race detection with control flow abstraction. In: Proceedings of the 35th Annual ACMSIGPLAN Conference on Programming Language Design and Implementation. New York: ACM, 2014. 337--348. Google Scholar

[52] Eslamimehr M, Palsberg J. Race directed scheduling of concurrent programs. In: Proceedings of the 19th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. New York: ACM, 2014. 301--314. Google Scholar

[53] Wood B P, Ceze L, Grossman D. Low-level detection of language-level data races with LARD. In: Proceedings of the 19th International Conference on Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2014. 671--686. Google Scholar

[54] Sen K, Rosu G, Agha G. Detecting errors in multithreaded programs by generalized predictive analysis of executions. In: Formal Methods for Open Object-Based Distributed Systems. Berlin: Springer, 2005. 211--226. Google Scholar

[55] Yu T, Srisa-an W, Rothermel G. SimRT: an automated framework to support regression testing for data races. In: Proceedings of the ACM/IEEE 36th International Conference on Software Engineering. New York: ACM, 2014. 48--59. Google Scholar

[56] Wood B P, Ceze L, Grossman D. Low-level detection of language-level data races with LARD. In: Proceedings of the 19th Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2014. 671--686. Google Scholar

[57] Serebryany K, Potapenko A, Iskhodzhanov T, et al. Dynamic race detection with LLVM compiler. In: Runtime Verification. Berlin: Springer, 2011. 110--114. Google Scholar

[58] Lu K, Wu Z, Wang X, et al. RaceChecker: efficient identification of harmful data races. In: Proceedings of the 23rd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing, Turku, 2015. 78--85. Google Scholar

[59] Narayanasamy S, Tigani J, Edwards A, et al. Automatically classifying benign and harmful data races using replay analysis. In: Proceedings of the 28th Annual ACMSIGPLAN Conference on Programming Language Design and Implementation. New York: ACM, 2007. 22--31. Google Scholar

[60] Maiya P, Kanade A, Majumdar R. Race detection for android applications. In: Proceedings of the 35th Annual ACMSIGPLAN Conference on Programming Language Design and Implementation. New York: ACM, 2014. 316--325. Google Scholar

[61] Hsiao C H, Yu J, Narayanasamy S, et al. Race detection for event-driven mobile applications. In: Proceedings of the 35th Annual ACMSIGPLAN Conference on Programming Language Design and Implementation. New York: ACM, 2014. 326--336. Google Scholar

[62] Mao X G, Lei Y, Dai Z Y, et al. Slice-based statistical fault localization. J Syst Softw, 2014, 89: 51-62 CrossRef Google Scholar

[63] Park C S, Sen K, Iancu C. Scaling data race detection for partitioned global address space programs. In: Proceedings of the 27th International ACM Conference on Supercomputing. New York: ACM, 2013. 47--58. Google Scholar

[64] Jannesari A, Tichy W F. Identifying ad-hoc synchronization for enhanced race detection. In: Proceedings of IEEE International Symposium on Parallel and Distributed Processing, Atlanta, 2010. 1--10. Google Scholar

[65] Xiong W, Park S, Zhang J, et al. Ad hoc synchronization considered harmful. In: Proceedings of the 9th USENIX Symposium on Operating Systems Design and Implementation, Vancouver, 2010. 163--176. Google Scholar

[66] Tian C, Nagarajan V, Gupta R, et al. Dynamic recognition of synchronization operations for improved data race detection. In: Proceedings of the International Symposium on Software Testing and Analysis. New York: ACM, 2008. 143--154. Google Scholar

[67] Lu S, Park S, Hu C, et al. MUVI: automatically inferring multi-variable access correlations and detecting related semantic and concurrency bugs. In: Proceedings of the 21st ACM Symposium on Operating Systems Principles. New York: ACM, 2007. 103--116. Google Scholar

[68] Liu P, Dolby J, Zhang C. Finding incorrect compositions of atomicity. In: Proceedings of the 9th Joint Meeting on Foundations of Software Engineering. New York: ACM, 2013. 158--168. Google Scholar

[69] Lu S, Tucek J, Qin F, et al. AVIO: detecting atomicity violations via access interleaving invariants. In: Proceedings of Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2006. 37--48. Google Scholar

[70] Muzahid A, Otsuki N, Torrellas J. AtomTracker: a comprehensive approach to atomic region inference and violation detection. In: Proceedings of the 43rd Annual IEEE/ACM International Symposium on Microarchitecture. New York: ACM, 2010. 287--297. Google Scholar

[71] Flanagan C, Freund S N. Atomizer: a dynamic atomicity checker for multithreaded programs. In: Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. New York: ACM, 2004. 256--267. Google Scholar

[72] Kidd N, Reps T, Dolby J, et al. Static Detection of Atomic-Set-Serializability Violations. Technical Report \#1623. University of Wisconsin-Madison, 2007. Google Scholar

[73] Chen Q, Wang L, Yang Z, et al. HAVE: detecting atomicity violations via integrated dynamic and static analysis. In: Fundamental Approaches to Software Engineering. Berlin: Springer, 2009. 425--439. Google Scholar

[74] Ye C, Cheung S, Chan W, et al. Detection and resolution of atomicity violation in service composition. In: Proceedings of the 6th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering. New York: ACM, 2007. 235--244. Google Scholar

[75] Chew L, Lie D. Kivati: fast detection and prevention of atomicity violations. In: Proceedings of the 5th European Conference on Computer Systems. New York: ACM, 2010. 307--320. Google Scholar

[76] Lucia B, Devietti J, Strauss K, et al. Atom-aid: detecting and surviving atomicity violations. In: Proceedings of the 35th Annual International Symposium on Computer Architecture, Beijing, 2008. 277--288. Google Scholar

[77] Liblit B, Naik M, Zheng A X, et al. Public deployment of cooperative bug isolation. In: Proceedings of the 2nd International Workshop on Remote Analysis and Measurement of Software Systems, 2004. 1: 57--62. Google Scholar

[78] Liblit B, Naik M, Zheng A X, et al. Scalable statistical bug isolation. In: Proceedings of the 26th Annual ACMSIGPLAN Conference on Programming Language Design and Implementation. New York: ACM, 2005. 15--26. Google Scholar

[79] Lu S, Zhou P, Liu W, et al. PathExpander: architectural support for increasing the path coverage of dynamic bug detection. In: Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture. New York: ACM, 2006. 38--52. Google Scholar

[80] Okur S, Dig D. How do developers use parallel libraries? In: Proceedings of the ACM SIGSOFT 20th International Symposium on the Foundations of Software Engineering. New York: ACM, 2012. 54. Google Scholar

[81] Liblit B, Aiken A, Zheng A X, et al. Bug isolation via remote program sampling. In: Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. New York: ACM, 2003. 141--154. Google Scholar

[82] Sorrentino F, Farzan A, Madhusudan P. PENELOPE: weaving threads to expose atomicity violations. In: Proceedings of the 18th ACM SIGSOFT International Symposium on Foundations of Software Engineering. New York: ACM, 2010. 37--46. Google Scholar

[83] Lucia B, Ceze L. Finding concurrency bugs with context-aware communication graphs. In: Proceedings of the 42th Annual IEEE/ACM International Symposium on Microarchitecture. New York: ACM, 2009. 553--563. Google Scholar

[84] Zhang W, Sun C, Lu S. ConMem: detecting severe concurrency bugs through an effect-oriented approach. In: Proceedings of the 15th Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2010. 179--192. Google Scholar

[85] Zhang W, Lim J, Olichandran R, et al. ConSeq: detecting concurrency bugs through sequential errors. In: Proceedings of the 16th Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2011. 251--264. Google Scholar

[86] Gao Q, Zhang W, Chen Z, et al. 2ndStrike: toward manifesting hidden concurrency typestate bugs. In: Proceedings of the 16th International Conference on Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2012. 239--250. Google Scholar

[87] Yu J, Narayanasamy S. A case for an interleaving constrained shared-memory multi-processor. In: Proceedings of the 36th Annual International Symposium on Computer Architecture. New York: ACM, 2009. 325--336. Google Scholar

[88] Sangmin P, Mary J H, Richard V. Griffin: grouping suspicious memory-access patterns to improve understanding of concurrency bugs. In: Proceedings of the International Symposium on Software Testing and Analysis. New York: ACM, 2013. 134--144. Google Scholar

[89] Burckhardt S, Kothari P, Musuvathi M, et al. A randomized scheduler with probabilistic guarantees of finding bugs. ACM Sigplan Notices, 2010, 45: 167-178 Google Scholar

[90] Joshi P, Naik M, Sen K, et al. An effective dynamic analysis for detecting generalized deadlocks. In: Proceedings of the 18th ACM SIGSOFT International Symposium on Foundations of Software Engineering. New York: ACM, 2010. 327--336. Google Scholar

[91] Marino D, Hammer C, Dolby J, et al. Detecting deadlock in programs with data-centric synchronization. In: Proceedings of the 35th International Conference on Software Engineering, San Francisco, 2013. 322--331. Google Scholar

[92] Koskinen E, Herlihy M. Dreadlocks: efficient deadlock detection. In: Proceedings of the 20th Annual Symposium on Parallelism in Algorithms and Architectures. New York: ACM, 2008. 297--303. Google Scholar

[93] Jula H, Tralamazza D, Zamfir C, et al. Deadlock immunity: enabling systems to defend against deadlocks. In: Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation. Berkeley: USENIX Association, 2008. 295--308. Google Scholar

[94] Cai Y, Chan W. MagicFuzzer: scalable deadlock detection for large-scale applications. In: Proceedings of the 34th International Conference on Software Engineering, Zurich, 2012. 606--616. Google Scholar

[95] Li T, Ellis C S, Lebeck A R, et al. Pulse: a dynamic deadlock detection mechanism using speculative execution. In: Proceedings of the Annual Conference on USENIX Annual Technical Conference. Berkeley: USENIX Association, 2005. 31--44. Google Scholar

[96] Naik M, Park C S, Sen K, et al. Effective static deadlock detection. In: Proceedings of the 31st International Conference on Software Engineering, Vancouver, 2009. 386--396. Google Scholar

[97] Samak M, Ramanathan M K. Trace driven dynamic deadlock detection and reproduction. In: Proceedings of the 19th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. New York: ACM, 2014. 29--42. Google Scholar

[98] Nistor A, Luo Q, Pradel M, et al. Ballerina: automatic generation and clustering of efficient random unit tests for multithreaded code. In: Proceedings of the 34th International Conference on Software Engineering, Zurich, 2012. 727--737. Google Scholar

[99] Cai Y, Wu S, Chan W K. ConLock: a constraint-based approach to dynamic checking on deadlocks in multithreaded programs. In: Proceedings of the ACM/IEEE 36th International Conference on Software Engineering. New York: ACM, 2014. 491--502. Google Scholar

[100] Farzan A, Holzer A, Razavi N, et al. Con2colic testing. In: Proceedings of the 9th Joint Meeting on Foundations of Software Engineering. New York: ACM, 2013. 37--47. Google Scholar

[101] Musuvathi M, Qadeer S, Ball T, et al. Finding and reproducing heisenbugs in concurrent programs. In: Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation. New York: ACM, 2008. 267--280. Google Scholar

[102] Wang C, Said M, Gupta A. Coverage guided systematic concurrency testing. In: Proceedings of the 33rd International Conference on Software Engineering, Honolulu, 2011. 221--230. Google Scholar

[103] Yang Y, Chen X, Gopalakrishnan G. Inspect: a Runtime Model Checker for Multithreaded C Programs. University of Utah, Technology Report UUCS-08-004. 2008. Google Scholar

[104] Emmi M, Qadeer S, Rakamari Z. Delay-bounded scheduling. In: Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. New York: ACM, 2011. 411--422. Google Scholar

[105] Godefroid P. Model checking for programming languages using VeriSoft. In: Proceedings of the 24th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. New York: ACM, 1997. 174--186. Google Scholar

[106] Sandeep B, Sorav B, Akash L. Variable and thread bounding for systematic testing of multithreaded programs. In: Proceedings of the International Symposium on Software Testing and Analysis. New York: ACM, 2013. 145--155. Google Scholar

[107] Musuvathi M, Qadeer S. Iterative context bounding for systematic testing of multithreaded programs. In: Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. New York: ACM, 2007. 446--455. Google Scholar

[108] Thomson P, Donaldson A F, Betts A. Concurrency testing using schedule bounding: an empirical study. In: Proceedings of the 19th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. New York: ACM, 2014. 15--28. Google Scholar

[109] Bergan T, Ceze L, Grossman D. Input-covering schedules for multithreaded programs. In: Proceedings of the ACM SIGPLAN International Conference on Object Oriented Programming Systems Languages and Applications. New York: ACM, 2013. 677--692. Google Scholar

[110] Deng D, Zhang W, Wang B, et al. Understanding the interleaving-space overlap across inputs and software versions. In: Proceedings of the 4th USENIX Conference on Hot Topics in Parallelism. Berkeley: USENIX Association, 2012. 17. Google Scholar

[111] Deng D, Zhang W, Lu S. Efficient concurrency-bug detection across inputs. In: Proceedings of the ACM SIGPLAN International Conference on Object Oriented Programming Systems Languages and Applications. New York: ACM, 2013. 785--802. Google Scholar

[112] Radoi C, Dig D. Practical static race detection for Java parallel loops. In: Proceedings of the International Symposium on Software Testing and Analysis. New York: ACM, 2013. 178--190. Google Scholar

[113] Dimitrov D, Raychev V, Vechev M, et al. Commutativity race detection. In: Proceedings of the 35th Annual ACMSIGPLAN Conference on Programming Language Design and Implementation. New York: ACM, 2014. 305--315. Google Scholar

[114] Sen K, Agha G. A race-detection and flipping algorithm for automated testing of multi-threaded programs. In: Hardware and Software, Verification and Testing. Berlin: Springer, 2007. 166--182. Google Scholar

[115] Jagannath V, Gligoric M, Jin D, et al. Improved multithreaded unit testing. In: Proceedings of the 19th ACM SIGSOFT International Symposium on Foundations of Software Engineering. New York: ACM, 2011. 223--233. Google Scholar

[116] Yu Y, Rodeheffer T, Chen W. Racetrack: efficient detection of data race conditions via adaptive tracking. ACM SIGOPS Oper Syst Rev, 2005, 39: 221-234 CrossRef Google Scholar

[117] Bond M D, Coons K E, McKinley K S. PACER: proportional detection of data races. In: Proceedings of the 31st Annual ACMSIGPLAN Conference on Programming Language Design and Implementation. New York: ACM, 2010. 255--268. Google Scholar

[118] Pozniansky E, Schuster A. MultiRace: efficient on-the-fly data race detection in multithreaded C++ programs. Concurr Comput Pract Exper, 2007, 19: 327-340 CrossRef Google Scholar

[119] Biswas S, Huang J, Sengupta A, et al. DoubleChecker: efficient sound and precise atomicity checking. In: Proceedings of the 35th Annual ACMSIGPLAN Conference on Programming Language Design and Implementation. New York: ACM, 2014. 28--39. Google Scholar

[120] Cadar C, Sen K. Symbolic execution for software testing: three decades later. Commun ACM, 2013, 56: 82-90 Google Scholar

[121] Cadar C, Dunbar D, Engler D R. KLEE: unassisted and automatic generation of high-coverage tests for complex systems programs. In: Proceedings of the 8th USENIX Symposium on Operating Systems Design and Implementation. Berkeley: USENIX Association, 2008. 209--224. Google Scholar

[122] Ciortea L, Zamfir C, Bucur S, et al. Cloud9: a software testing service. ACM SIGOPS Oper Syst Rev, 2010, 43: 5-10 CrossRef Google Scholar

[123] Cadar C, Ganesh V, Pawlowski P M, et al. EXE: automatically generating inputs of death. ACM Trans Inf Syst Secur, 2008, 12: 322-335 Google Scholar

[124] Liu W W, Wang J, Chen H W, et al. Symbolic model checking APSL. Front Comput Sci China, 2009, 3: 130-141 CrossRef Google Scholar

[125] Altekar G, Stoica I. ODR: output-deterministic replay for multicore debugging. In: Proceedings of the ACM SIGOPS 22nd Symposium on Operating Systems Principles. New York: ACM, 2009. 193--206. Google Scholar

[126] Huang J, Zhang C. LEAN: simplifying concurrency bug reproduction via replay-supported execution reduction. In: Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications. New York: ACM, 2012. 451--466. Google Scholar

[127] Huang J, Liu P, Zhang C. LEAP: lightweight deterministic multi-processor replay of concurrent java programs. In: Proceedings of the 18th ACM SIGSOFT International Symposium on Foundations of Software Engineering. New York: ACM, 2010. 207--216. Google Scholar

[128] Veeraraghavan K, Lee D, Wester B, et al. DoublePlay: parallelizing sequential logging and replay. ACM Trans Comput Syst, 2012, 30: 3-141 Google Scholar

[129] Weiss Z, Harter T, Arpaci-Dusseau A C, et al. ROOT: replaying multithreaded traces with resource-oriented ordering. In: Proceedings of the 24th ACM Symposium on Operating Systems Principles. New York: ACM, 2013. 373--387. Google Scholar

[130] Huang J, Zhang C, Dolby J. CLAP: recording local executions to reproduce concurrency failures. In: Proceedings of the 34th Annual ACMSIGPLAN Conference on Programming Language Design and Implementation. New York: ACM, 2013. 141--152. Google Scholar

[131] Devietti J, Lucia B, Ceze L, et al. DMP: deterministic shared memory multiprocessing. In: Proceedings of the 14th Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2009. 85--96. Google Scholar

[132] Zhou X, Lu K, Wang X, et al. Exploiting parallelism in deterministic shared memory multiprocessing. J Parall Distrib Comput, 2012, 72: 716-727 CrossRef Google Scholar

[133] Burnim J, Sen K. Asserting and checking determinism for multithreaded programs. In: Proceedings of the 7th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering. New York: ACM, 2009. 3--12. Google Scholar

[134] Yin Z, Yuan D, Zhou Y, et al. How do fixes become bugs? In: Proceedings of the 19th ACM SIGSOFT International Symposium on Foundations of Software Engineering. New York: ACM, 2011. 26--36. Google Scholar

[135] Sidiroglou S, Ioannidis S, Keromytis A D. Band-aid patching. In: Proceedings of the 3rd Workshop on Hot Topics in System Dependability. Berkeley: USENIX Association, 2007. 102--106. Google Scholar

[136] Gu Z, Barr E T, Hamilton D J, et al. Has the bug really been fixed? In: Proceedings of ACM/IEEE 32nd International Conference on Software Engineering, Cape Town, 2010. 55--64. Google Scholar

[137] Jin G, Song L, Zhang W, et al. Automated atomicity-violation fixing. In: Proceedings of the 32th Annual ACMSIGPLAN Conference on Programming Language Design and Implementation. New York: ACM, 2011. 389--400. Google Scholar

[138] Jin G, Zhang W, Deng D, et al. Automated concurrency-bug fixing. In: Proceedings of the 10th USENIX Symposium on Operating Systems Design and Implementation. Berkeley: USENIX Association, 2012. 221--246. Google Scholar

[139] Liu P, Zhang C. Axis: automatically fixing atomicity violations through solving control constraints. In: Proceedings of the International Conference on Software Engineering, Zurich, 2012. 299--309. Google Scholar

[140] Deng D D, Jin G L, de Kruijf M, et al. Fixing, preventing, and recovering from concurrency bugs. Sci China Inf Sci, 2015, 58: 052105-727 Google Scholar

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1