nach oben

International Journal of Parallel Programming

Erschienen in:

01.04.2015

Collaborative Technique for Concurrency Bug Detection

verfasst von: Zhendong Wu, Kai Lu, Xiaoping Wang, Xu Zhou

Erschienen in: International Journal of Parallel Programming | Ausgabe 2/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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 %.

Vorheriger Artikel A Parallel Implementation for the Negative Cost Girth Problem

Nächster Artikel Multi-Threaded Parallel I/O for OpenMP Applications

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Securityfocus: Software bug contributed to blackout. http://www.securityfocus.com/news/8016 (2013). Accessed 1 May 2013

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–339. Seattle, Washington, USA (2008)

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–303 (2008)

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–120 (2009)

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–48. San Jose, CA, USA (2006)

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–145. Atlanta, Georgia, USA (2008)

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–36. Washington, DC, USA (2009)

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–154. Toronto, ON, Canada (2011)

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–192. 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–264. 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–502. 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–269 (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–116. 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–31 (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–55 (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–214. 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–234 (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–106 (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 tools with dynamic instrumentation. In: 26th annual ACMSIGPLAN conference on Programming Language Design and Implementation (PLDI 2005), pp. 190–200. Chicago, Illinois, USA (2005)

21.

Engler, D., Ashcraft, K.: RacerX: effective, static detection of race conditions and deadlocks. In: Proceedings of the 19th ACM symposium on Operating systems principles (SOSP 2003), pp. 237–252 (2003)

22.

Balakrishnan, G., Gruian, R., Reps, T., Teitelbaum, T.: CodeSurfer/x86 - A platform for analyzing x86 executables. In: Proceedings of the 14th International Conference on Compiler Construction (CC 2005), pp. 250–254 (2005)

23.

Balakrishnan, G., Reps, T.: Analyzing memory accesses in x86 executables. In: Proceedings of the 13th international conference on Compiler Construction (CC 2004), pp. 5–23 (2004)

24.

Lyle, J.R., Wallace, D.R.: Using the unravel program slicing tool to evaluate high integrity software. In: Proceedings of 10th International Software Quality Week, vol. 301, pp. 975–3270 (1997)

25.

Sen, K.: Race directed random testing of concurrent programs. In: 29th annual ACMSIGPLAN conference on Program-ming Language Design and Implementation (PLDI 2008), pp. 11–21. Tucson, Arizona, USA (2008)

26.

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 (ICSE 2010), pp. 235–244. Cape Town, South, Africa (2010)

27.

Chew, L., Lie, D.: Kivati: fast detection and prevention of atomicity violations. In: Proceedings of the 5th European conference on Computer systems (Eurosys 2010), pp. 307–320. Paris, France (2010)

28.

Apache-2.0.48, https://issues.apache.org/bugzilla/show_bug.cgi?id=25520. Accessed 1 May 2013 (2013)

29.

Narayanasamy, S., Wang, Z., Tigani, J., Edwards, A., Calder, B.: 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–31 (2007)

30.

Lucia, B., Devietti, J., Strauss, K., Ceze, L.: Atom-aid: Detecting and surviving atomicity violations. In: Proceedings of the 35th Annual International Symposium on Computer Architecture (ISCA 2008), pp. 277–288 (2008)

31.

Woo, S.C., Ohara, M., Torrie, E., Singh, J.P., Gupta, A.: The SPLASH-2 programs: characterization and methodological considerations. In: Proceedings of the 22th Annual Interna-tional Symposium on Computer Architecture (ISCA 1995), pp. 24–36 (1995)

32.

Xu, Z., Kai L., Xiaoping W., Xu L.: Exploiting parallelism in deterministic shared memory multiprocessing. J. Parallel Distrib. Comput. (JPDC), pp. 716–727 (2012)

33.

Kai L., Xu, Z., Tom B., Xiaoping W.: Efficient Deterministic Multithreading Without Global Barriers. In PPoPP (2014)

34.

Zhendong W., Kai L., Xiaoping W., Xu Z.: ColFinder: Collaborative Concurrency Bug Detection. The 13th International Conference on Quality Software (QSIC 2013), pp. 208–211 (2013)

35.

Benjamin, W., David D., Peter M. C., Jason F. and Satish N.: Parallelizing Data Race Detection. In: 18th Architectural Support for Programming Languages and Operating Systems (ASPLOS 2013), pp. 27–38 (2013)

36.

Sangmin, P., Mary J. H., Richard V.: Griffin: Grouping Suspicious Memory-Access Patterns to Improve Understanding of Concurrency Bugs. In: Proceedings of the 2013 International Symposium on Software Testing and Analysis (ISSTA 2013), pp. 134–144 (2013)

37.

Madanlal, M., Shaz, Q., Thomas, B., Gerard, B., Piramanayagam, A. N., Iulian, N.: Finding and Reproducing Heisenbugs in Concurrent Programs. In: 8th USENIX symposium on Operating Systems Design and Implementation (OSDI 2008), pp. 267–280 (2008)

38.

Sandeep, B., Sorav, B., Akash, L.: Variable and Thread Bounding for Systematic Testing of Multithreaded Programs. In: Proceedings of the 2013 International Symposium on Software Testing and Analysis (ISSTA 2013)

39.

Jeff, H., Charles, Z., Julian, D.: CLAP: Recording Local Executions to Reproduce Concurrency Failures. In: 34th annual ACMSIGPLAN conference on Program-ming Language Design and Implementation (PLDI 2013), Seattle, WA, USA (2013)

40.

Baris, K., Cristian Z., George C.: RaceMob: Crowdsourced Data Race Detection. In: Proceedings of the 23th ACM symposium on Operating systems principles (SOSP 2013)

Titel: Collaborative Technique for Concurrency Bug Detection
verfasst von: Zhendong Wu
Kai Lu
Xiaoping Wang
Xu Zhou
Publikationsdatum: 01.04.2015
Verlag: Springer US
Erschienen in: International Journal of Parallel Programming / Ausgabe 2/2015
Print ISSN: 0885-7458
Elektronische ISSN: 1573-7640
DOI: https://doi.org/10.1007/s10766-014-0304-y

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2015

Multi-Threaded Parallel I/O for OpenMP Applications

Finite Element Algorithms and Data Structures on Graphical Processing Units

Helper Thread Prefetching Control Framework on Chip Multi-processor

A Parallel Implementation for the Negative Cost Girth Problem

User-Guided Dynamic Data Race Detection

Premium Partner