Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Introduction to Runtime Verification Kapitel lesen Erstes Kapitel lesen

2018 | OriginalPaper | Buchkapitel

Discovering Concurrency Errors

verfasst von : João M. Lourenço, Jan Fiedor, Bohuslav Křena, Tomáš Vojnar

Erschienen in: Lectures on Runtime Verification

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

Lots of concurrent software is being developed for the now ubiquitous multicore processors. And concurrent programming is difficult because it is quite easy to introduce errors that are really hard to diagnose and fix. One of the main obstacles to concurrent programming is that threads are scheduled nondeterministically and their interactions may become hard to predict and to devise. This chapter addresses the nature of concurrent programming and some classes of concurrency errors. It discusses the application of dynamic program analysis techniques to detect, locate and diagnose some common concurrency errors like data races, atomicity violations and deadlocks. This chapter also mentions some techniques that can help with quality assurance of concurrent programs, regardless of any particular class of concurrency errors, like noise injection and systematic testing, and it is closed by some prospects of concurrent software development.

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 "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

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
Vorheriges Kapitel Introduction to Runtime Verification
Nächstes Kapitel Monitoring Events that Carry Data
Fußnoten
1
In this Chapter, we concentrate on the shared memory paradigm, leaving behind the distributed memory and message passing paradigms, which are covered elsewhere in this book.
 
2
Some atomicity violations can be, actually, seen as a low-level violations of ordering expectations and deadlocks, in addition, are often caused by a wrong order of locking operations. Here, we do not consider atomicity violations and deadlocks as order violations.
 
3
Mixed errors are errors that have both finite witnesses as well as infinite ones whose any finite prefix does not suffice as a witness.
 
Literatur
1.
2.
Agarwal, R., Stoller, S.D.: Run-time detection of potential deadlocks for programs with locks, semaphores, and condition variables. In: Proceedings of PADTAD 2006, pp. 51–60. ACM, New York (2006)
3.
Agrawal, R., Imieliński, T., Swami, A.: Mining association rules between sets of items in large databases. In: Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, SIGMOD 1993, pp. 207–216. ACM, New York (1993)
4.
Artho, C., Havelund, K., Biere, A.: High-level data races. In: The First International Workshop on Verification and Validation of Enterprise Information Systems, VVEIS 2003, Angers, France (2003)
5.
Ayguade, E., Cristal, A., Unsal, O.S., Gagliardi, F., Smith, B., Valero, M., Harris, T.: Transactional memory: An overview. IEEE Micro 27, 8–29 (2007)
6.
7.
Bodden, E., Havelund, K.: Racer: Effective race detection using aspectj. In: Proceedings of the 2008 International Symposium on Software Testing and Analysis, ISSTA 2008, pp. 155–166. ACM, New York (2008)
8.
Choi, J.D., Lee, K., Loginov, A., O’Callahan, R., Sarkar, V., Sridharan, M.: Efficient and precise datarace detection for multithreaded object-oriented programs. In: Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language Design and Implementation, PLDI 2002, pp. 258–269. ACM, New York (2002)
9.
10.
Coffman, E.G., Elphick, M., Shoshani, A.: System deadlocks. ACM Comput. Surv. 3, 67–78 (1971)CrossRefMATH
11.
Deshmukh, J., Emerson, E.A., Sankaranarayanan, S.: Symbolic deadlock analysis in concurrent libraries and their clients. In: Proceedings of the 2009 IEEE/ACM International Conference on Automated Software Engineering, ASE 2009, pp. 480–491. IEEE, Washington, DC (2009)
12.
Dias, R.F., Ferreira, C., Fiedor, J., Lourenço, J.M., Smrčka, A., Sousa, D.G., Vojnar, T.: Verifying concurrent programs using contracts. In: Proceedings of ICST 2017. IEEE Computer Society, Washington, DC (2017)
13.
14.
Edelstein, O., Farchi, E., Goldin, E., Nir, Y., Ratsaby, G., Ur, S.: Framework for testing multi-threaded java programs. Concurrency Comput. Pract. Experience 15(3–5), 485–499 (2003)CrossRefMATH
15.
Elmas, T., Qadeer, S., Tasiran, S.: Goldilocks: a race and transaction-aware java runtime. In: Proceedings of PLDI 2007, pp. 245–255. ACM, New York (2007)
16.
Engler, D., Ashcraft, K.: RacerX: Effective, static detection of race conditions and deadlocks. SIGOPS Oper. Syst. Rev. 37(5), 237–252 (2003)CrossRef
17.
18.
Farchi, E., Nir, Y., Ur, S.: Concurrent bug patterns and how to test them. In: Proceedings of the 17th International Symposium on Parallel and Distributed Processing, IPDPS 2003, p. 286.2. IEEE Computer Society, Washington, DC (2003)
19.
20.
21.
Fiedor, J., Vojnar, T.: Noise-based testing and analysis of multi-threaded C/C++ programs on the binary level. In: PADTAD 2012, pp. 36–46. ACM (2012)
22.
23.
Flanagan, C., Freund, S.N.: Type-based race detection for java. In: Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation, PLDI 2000, pp. 219–232. ACM, New York (2000)
24.
Flanagan, C., Freund, S.N.: Atomizer: A dynamic atomicity checker for multithreaded programs. SIGPLAN Not. 39(1), 256–267 (2004)CrossRefMATH
25.
26.
Flanagan, C., Freund, S.N.: FastTrack: efficient and precise dynamic race detection. In: Proceedings of the 2009 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2009, pp. 121–133. ACM, New York (2009)
27.
Flanagan, C., Freund, S.N.: The roadrunner dynamic analysis framework for concurrent programs. In: Proceedings of the 9th ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, PASTE 2010, pp. 1–8. ACM, New York (2010). http://​doi.​acm.​org/​10.​1145/​1806672.​1806674
28.
Flanagan, C., Freund, S.N., Lifshin, M., Qadeer, S.: Types for atomicity: static checking and inference for java. ACM Trans. Program. Lang. Syst. 30(4), 1–53 (2008)CrossRef
29.
Flanagan, C., Freund, S.N., Yi, J.: Velodrome: A sound and complete dynamic atomicity checker for multithreaded programs. SIGPLAN Not. 43(6), 293–303 (2008)CrossRef
30.
Godefroid, P.: Software model checking: The verisoft approach. Form. Methods Syst. Des. 26(2), 77–101 (2005)CrossRef
31.
32.
Hammer, C., Dolby, J., Vaziri, M., Tip, F.: Dynamic detection of atomic-set-serializability violations. In: Proceedings of the 30th International Conference on Software Engineering, ICSE 2008, pp. 231–240. ACM, New York (2008)
33.
34.
Ho, A., Smith, S., Hand, S.: On deadlock, livelock, and forward progress. University of Cambridge, Technical report (2005)
35.
Holzmann, G.: Spin Model Checker, The: Primer and Reference Manual. Addison-Wesley Professional, Reading (2003)
36.
Hong, S., Ahn, J., Park, S., Kim, M., Harrold, M.J.: Testing concurrent programs to achieve high synchronization coverage. In: Proceedings of ISSTA 2012, pp. 210–220. ACM, New York (2012)
37.
Hovemeyer, D., Pugh, W.: Finding concurrency bugs in java. In: 23rd Annual ACM SIGACTSIGOPS Symposium on Principles of Distributed Computing (PODC 2004) Workshop on Concurrency and Programs, July 2004
38.
Joshi, P., Park, C.S., Sen, K., Naik, M.: A randomized dynamic program analysis technique for detecting real deadlocks. In: Proceedings of the 2009 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2009, pp. 110–120. ACM, New York (2009)
39.
40.
Kim, K., Yavuz-Kahveci, T., Sanders, B.A.: Precise data race detection in a relaxed memory model using heuristic-based model checking. In: ASE, pp. 495–499. IEEE (2009)
41.
Křena, B., Letko, Z., Tzoref, R., Ur, S., Vojnar, T.: Healing data races on-the-fly. In: Proceedings of PADTAD 2007, pp. 54–64. ACM, New York (2007)
42.
43.
Lamport, L.: Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21(7), 558–565 (1978)CrossRefMATH
44.
Laurenzano, M., Tikir, M., Carrington, L., Snavely, A.: PEBIL: Efficient static binary instrumentation for linux. In: ISPASS 2010, pp. 175–183 (2010)
45.
Letko, Z., Vojnar, T., Křena, B.: Atomrace: Data race and atomicity violation detector and healer. In: Proceedings of the 6th Workshop on Parallel and Distributed Systems: Testing, Analysis, and Debugging, PADTAD 2008, pp. 7:1–7:10. ACM, New York (2008). http://​doi.​acm.​org/​10.​1145/​1390841.​1390848
46.
47.
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. SIGOPS Oper. Syst. Rev. 41(6), 103–116 (2007)CrossRef
48.
Lu, S., Tucek, J., Qin, F., Zhou, Y.: AVIO: Detecting atomicity violations via access interleaving invariants. In: Proceedings of ASPLOS 2006, pp. 37–48. ACM, New York (2006)
49.
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: Proceedings of PLDI 2005. ACM (2005)
50.
Masticola, S.P., Ryder, B.G.: Non-concurrency analysis. In: Proceedings of the Fourth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP 1993, pp. 129–138. ACM, New York (1993)
51.
52.
Musuvathi, M., Qadeer, S., Ball, T.: CHESS: A Systematic Testing Tool for Concurrent Software. Technical report MSR-TR-2007-149, Microsoft Research (2007)
53.
54.
Naik, M., Aiken, A., Whaley, J.: Effective static race detection for java. SIGPLAN Not. 41(6), 308–319 (2006)CrossRef
55.
56.
57.
Nonaka, Y., Ushijima, K., Serizawa, H., Murata, S., Cheng, J.: A run-time deadlock detector for concurrent java programs. In: Proceedings of the Eighth Asia-Pacific on Software Engineering Conference, APSEC 2001, p. 45. IEEE, Washington, DC (2001)
58.
O’Callahan, R., Choi, J.D.: Hybrid dynamic data race detection. In: Proceedings of the Ninth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2003, pp. 167–178. ACM, New York (2003)
59.
60.
61.
Pozniansky, E., Schuster, A.: Efficient on-the-fly data race detection in multithreaded C++ programs. In: Proceedings of PPoPP 2003, pp. 179–190. ACM, New York (2003)
62.
Pozniansky, E., Schuster, A.: MultiRace: efficient on-the-fly data race detection in multithreaded C++ programs: research articles. Concurr. Comput. Pract. Exper. 19(3), 327–340 (2007)CrossRef
63.
von Praun, C., Gross, T.R.: Object race detection. In: Proceedings of OOPSLA 2001, pp. 70–82. ACM, New York (2001)
64.
Savage, S., Burrows, M., Nelson, G., Sobalvarro, P., Anderson, T.: Eraser: a dynamic data race detector for multi-threaded programs. In: Proceedings of SOSP 1997, pp. 27–37. ACM, New York (1997)
65.
Sousa, D.G., Dias, R.J., Ferreira, C., Lourenço, J.M.: Preventing atomicity violations with contracts, May 2015. arXiv preprint arXiv:​1505.​02951
66.
Vaziri, M., Tip, F., Dolby, J.: Associating synchronization constraints with data in an object-oriented language. In: Conference Record of the 33rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2006, pp. 334–345. ACM, New York (2006)
67.
Visser, W., Havelund, K., Brat, G., Park, S.: Model checking programs. In: Proceedings of ASE 2000, p. 3. IEEE Computer Society, Washington, DC (2000)
68.
Wang, L., Stoller, S.D.: Static analysis of atomicity for programs with non-blocking synchronization. In: Proceedings of the Tenth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2005, pp. 61–71. ACM, New York (2005)
69.
Wang, L., Stoller, S.D.: Runtime analysis of atomicity for multithreaded programs. IEEE Trans. Softw. Eng. 32(2), 93–110 (2006)CrossRef
70.
71.
Wu, J., Tang, Y., Hu, G., Cui, H., Yang, J.: Sound and precise analysis of parallel programs through schedule specialization. In: Proceedings of PLDI 2012, pp. 205–216. ACM, New York (2012)
72.
Xu, M., Bodík, R., Hill, M.D.: A serializability violation detector for shared-memory server programs. SIGPLAN Not. 40(6), 1–14 (2005)CrossRef
73.
Yang, Y., Gringauze, A., Wu, D., Rohde, H.: Detecting Data Race and Atomicity Violation via Typestate-Guided Static Analysis. Technical report MSR-TR-2008-108, Microsoft Research (2008)
74.
Yu, J., Narayanasamy, S.: A case for an interleaving constrained shared-memory multi-processor. SIGARCH Comput. Archit. News 37(3), 325–336 (2009)CrossRef
75.
Yu, J., Narayanasamy, S., Pereira, C., Pokam, G.: Maple: A coverage-driven testing tool for multithreaded programs. In: Proceedings of OOPSLA 2012, pp. 485–502. ACM, New York (2012)
76.
Yu, Y., Rodeheffer, T., Chen, W.: RaceTrack: efficient detection of data race conditions via adaptive tracking. SIGOPS Oper. Syst. Rev. 39(5), 221–234 (2005)CrossRef
77.
Zhang, W., Sun, C., Lu, S.: ConMem: detecting severe concurrency bugs through an effect-oriented approach. In: Proceedings of the Fifteenth Edition of ASPLOS on Architectural Support for Programming Languages and Operating Systems, ASPLOS 2010, pp. 179–192. ACM, New York (2010)
Metadaten
Titel
Discovering Concurrency Errors
verfasst von
João M. Lourenço
Jan Fiedor
Bohuslav Křena
Tomáš Vojnar
Copyright-Jahr
2018
Buch
Lectures on Runtime Verification

Print ISBN: 978-3-319-75631-8

Electronic ISBN: 978-3-319-75632-5

Copyright-Jahr: 2018

DOI
https://doi.org/10.1007/978-3-319-75632-5_2

Premium Partner

    Bildnachweise