Collaborative Technique for Concurrency Bug Detection

详细信息    查看全文

• 作者：Zhendong Wu ; Kai Lu ; Xiaoping Wang…
• 关键词：Collaborative ; Concurrency bug detection ; Static program slicing ; Dynamic active tester
• 刊名：International Journal of Parallel Programming
• 出版年：2015
• 出版时间：April 2015
• 年：2015
• 卷：43
• 期：2
• 页码：260-285
• 全文大小：1,390 KB
• 参考文献：1. Securityfocus: Software bug contributed to blackout. http://www.securityfocus.com/news/8016 (2013). Accessed 1 May 2013
  2. Lu, S., Park, S., Seo, E., Zhou, Y.: Learning from mistakes: a comprehensive study on real world concurrency bug characteristics. In: Architectural Support for Programming Languages and Operating Systems (ASPLOS 2008), pp. 329-39. Seattle, Washington, USA (2008)
  3. Koskinen, E., Herlihy, M.: Dreadlocks: efficient deadlock detection. In: Proceedings of the 12th annual symposium on Parallelism in algorithms and architectures, Munich, Germany, pp. 297-03 (2008)
  4. Joshi, P., Park, C.-S., Sen, K., Naik, M.: A randomized dynamic program analysis technique for detecting real deadlocks. In: 30th annual ACMSIGPLAN conference on Programming Language Design and Implementation (PLDI 2009), Dublin, Ireland, pp. 110-20 (2009)
  5. Lu, S., Tucek, J., Qin, F., Zhou, Y.: AVIO: detecting atomicity violations via access interleaving invariants. In: Architectural Support for Programming Languages and Operating Systems (ASPLOS 2006), pp. 37-8. San Jose, CA, USA (2006)
  6. 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(FSE), pp. 135-45. Atlanta, Georgia, USA (2008)
  7. Park, S., Lu, S., Zhou, Y.: CTrigger: exposing atomicity violation bugs from their hiding places. Ctrigger: exposing atomicity violation bugs from their hiding places. In: 15th Architectural Support for Programming Languages and Operating Systems (ASPLOS 2009), pp. 25-6. Washington, DC, USA (2009)
  8. Huang, J., Zhang, C.: Persuasive prediction of concurrency access anomalies. In: Proceedings of the 2011 International Symposium on Software Testing and Analysis (ISSTA 2011), pp. 144-54. Toronto, ON, Canada (2011)
  9. 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 (PADTAD 2008). Seattle, WA, USA (2008)
  10. Zhang, W., Sun, C., Lu, S.: ConMem: detecting severe concurrency bugs through an effect-oriented approach. In: 15th Architectural Support for Programming Languages and Operating Systems (ASPLOS 2010), pp. 179-92. Pittsburgh, PA, USA (2010)
  11. Zhang, W., Lim, J., Olichandran, R., Scherpelz, J., Jin, G., Lu, S., Reps, T.: ConSeq: detecting concurrency bugs through sequential errors. In: 16th Architectural Support for Programming Languages and Operating Systems (ASPLOS 2011), pp. 251-64. Newport Beach, CA, USA (2011)
  12. Yu, J., Narayanasamy, S., Pereira, C., Pokam, G.: Maple: a coverage-driven testing tool for multithreaded programs. In: Proceedings of the ACM international conference on Object oriented programming systems languages and applications (OOPSLA 2012), pp. 485-02. Tucson, AZ, USA (2012)
  13. Brat, G., Visser, W.: Combining static analysis and model checking for software analysis. In: Proceedings of the 16th IEEE international conference on Automated software engineering (ASE 2001), pp. 262-69 (2001)
  14. Lu, S., Park, S., Hu, C., Ma, X., Jiang, W., Li, Z., Popa, R.A., Zhou, Y.: MUVI: automatically inferring multi-variable access correlations and detecting related semantic and concurrency bugs. In: Proceedings of the 21th ACM symposium on Operating systems principles (SOSP 2007), pp. 103-16. Stevenson, WA, USA (2007)
  15. S. Narayanasamy, Z.W., J. Tigani, A. Edwards, and B. Calder: Automatically classifying benign and harmful data races using replay analysis. In: 28th annual ACMSIGPLAN conference on Programming Language Design and Implementation (PLDI 2007), pp. 22-1 (2007)
  16. Pratikakis, P., Foster, J.S., Hicks, M.: Locksmith: practical static race detection for c. ACM Trans. Program. Lang. Syst. (TOPLAS) 33(3), 1-5 (2011) CrossRef
  17. Voung, J.W., Jhala, R., Lerner, S.: RELAY: static race detection on millions of lines of code. In: 15th ACM SIGSOFT International Symposium on Foundations of software engineering (FSE 2007), pp. 205-14. Cavtat near Dubrovnik, Croatia (2007)
  18. Giffhorn, D., Hammer, C.: Precise slicing of concurrent programs. J. Autom. Softw. Eng. doi:10.1007/s10515-009-0048-x pp. 197-34 (2009)
  19. X. Zhang, R.G.: Cost effective dynamic program slicing. In: 25th annual ACMSIGPLAN conference on Progr-amming Language Design and Implementation (PLDI 2004), pp. 94-06 (2004)
  20. Luk, C.-K., Cohn, R., Muth, R., Patil, H., Klauser, A., Lowney, G., Wallace, S., Reddi, V.J., Hazelwood, K.: Pin: building customized program analysis tool
• 刊物类别：Computer Science
• 刊物主题：Theory of Computation
  Processor Architectures
  Software Engineering, Programming and Operating Systems
  
• 出版者：Springer Netherlands
• ISSN：1573-7640

文摘

Concurrency bugs hidden in deployed software can cause severe failures and real-world disasters. They are notoriously difficult to detect during in-house testing due to huge and non-deterministic interleaving space. Unfortunately, the multicore technology trend worsens this problem. Unlike previous work that detects particular concurrency bugs (e.g., data races and atomicity violations), we target harmful concurrency bugs that cause program failures. In order to detect harmful concurrency bugs effectively and efficiently, we propose an innovative, collaborative approach called ColFinder. First, ColFinder statically analyzes the program to identify potential concurrency bugs. ColFinder then uses static program slicing to get smaller programs with respect to potential concurrency bugs. Finally, ColFinder dynamically controls thread scheduler to force multiple threads access the same memory location, verifying whether the potential concurrency bug will cause program failure. If a failure occurs, a harmful concurrency bug is detected. We have implemented ColFinder as a prototype tool and have experimented on a number of real-world concurrent programs. The probability of bug manifestation in these programs is only 0.64?% averagely during native execution. It is significantly raised to 90?% with ColFinder. The runtime overhead imposed by many previous approaches is always more than 10 \(\times \) . The overhead of ColFinder is more acceptable, with an average of 79?%. Additionally, to our knowledge, this is the first technique that introduces program slicing to reduce the time of bug manifestation, with an average of 33?%.