Concurrency Reasoning for Weak Memory

Teilnehmer:

Heike Wehrheim, Simon Doherty, Brijesh Dongol, Sadegh Dalvandi, Lara Bargmann

Förderung:

Deutsche Forschungsgemeinschaft (DFG), 2021 - 2024

Concurrency Reasoning for Weak Memory

Programmverifikation für parallele Programme auf schwachen Speichermodellen

Das Gebiet der Programmverifikation beschäftigt sich mit Beweisverfahren zum formalen Nachweis der Korrektheit von Programmen bezüglich spezifizierten Eigenschaften. Ausschlaggebend für die Korrektheit ist bei parallelen Programmen aber nicht nur das Programm selber, sondern auch das der ausführenden Hardware zugrundeliegende Speichermodell. Many- und Multi-core Architekturen besitzen sogenannte schwache Speichermodelle, die die Semantik von parallelen Programmen signifikant beinflussen. Bisher sind vor allem Beweisverfahren entwickelt worden, die spezifisch für ein solches Speichermodell sind.

Das Ziel des Projektes ist Entwicklung einer generischen Verifikationstechnik, die Korrektheitsbeweise für Programme unabhängig von einem Speichermodell entwickeln kann, und Beweise dann auf Speichermodelle transferiert. Dazu soll die Verifikation auf eine axiomatische Basis gesetzt werden, die das verschiedenen Speichermodellen gemeinsame operationelle Verhalten von parallelen Programmen beschreibt und von den technischen Unterschieden abstrahiert. Auf dieser Basis soll (a) eine Sprache zur Eigenschaftsspezifikation sowie (b) ein Beweiskalkül entwickelt werden. Durch den exemplarischen Nachweis der Gültigkeit dieser Axiome für drei Speichermodelle und die Durchführung einer Reihe von Beweis-Fallstudien wollen wir die Generizität der Verifikationstechnik demonstrieren.

Veröffentlichungen

  • [inproceedings] bibtex | Dokument aufrufen Dokument aufrufen
    S. Bodenmüller, J. Derrick, B. Dongol, G. Schellhorn, und H. Wehrheim, "A Fully Verified Persistency Library" in Proc. Verification, Model Checking, and Abstract Interpretation - 25th International Conference, VMCAI 2024, London, United Kingdom, January 15-16, 2024, Proceedings, Part II, 2024.
    doi: 10.1007/978-3-031-50521-8_2
  • L. Bargmann und H. Wehrheim, "View-Based Axiomatic Reasoning for PSO (Extended Version)" CoRR, vol. abs/2301.07967.
    doi: 10.48550/ARXIV.2301.07967
  • O. Lahav, B. Dongol, und H. Wehrheim, "Rely-Guarantee Reasoning for Causally Consistent Shared Memory (Extended Version)" CoRR, vol. abs/2305.08486.
    doi: 10.48550/ARXIV.2305.08486
  • L. Bargmann und H. Wehrheim, "Lifting the Reasoning Level in Generic Weak Memory Verification (Extended Version)" CoRR, vol. abs/2309.01433.
    doi: 10.48550/ARXIV.2309.01433
  • [inproceedings] bibtex | Dokument aufrufen Dokument aufrufen
    O. Lahav, B. Dongol, und H. Wehrheim, "Rely-Guarantee Reasoning for Causally Consistent Shared Memory" in Proc. Computer Aided Verification - 35th International Conference, CAV 2023, Paris, France, July 17-22, 2023, Proceedings, Part I, 2023.
    doi: 10.1007/978-3-031-37706-8_11
  • [inproceedings] bibtex | Dokument aufrufen Dokument aufrufen
    H. Wehrheim, L. Bargmann, und B. Dongol, "Reasoning About Promises in Weak Memory Models with Event Structures" in Proc. Formal Methods - 25th International Symposium, FM 2023, Lübeck, Germany, March 6-10, 2023, Proceedings, 2023.
    doi: 10.1007/978-3-031-27481-7_17
  • [inproceedings] bibtex | Dokument aufrufen Dokument aufrufen
    L. Bargmann und H. Wehrheim, "Lifting the Reasoning Level in Generic Weak Memory Verification" in Proc. iFM 2023 - 18th International Conference, iFM 2023, Leiden, The Netherlands, November 13-15, 2023, Proceedings, 2023.
    doi: 10.1007/978-3-031-47705-8_10
  • [inproceedings] bibtex | Dokument aufrufen Dokument aufrufen
    L. Bargmann und H. Wehrheim, "View-Based Axiomatic Reasoning for PSO" in Proc. Theoretical Aspects of Software Engineering - 17th International Symposium, TASE 2023, Bristol, UK, July 4-6, 2023, Proceedings, 2023.
    doi: 10.1007/978-3-031-35257-7_17
  • H. Wehrheim, L. Bargmann, und B. Dongol, "Reasoning about Promises in Weak Memory Models with Event Structures (Extended Version)" CoRR, vol. abs/2211.16330.
    doi: 10.48550/ARXIV.2211.16330
  • S. Dalvandi, B. Dongol, S. Doherty, und H. Wehrheim, "Integrating Owicki-Gries for C11-Style Memory Models into Isabelle/HOL" J. Autom. Reason. vol. 66, iss. 1.
    doi: 10.1007/S10817-021-09610-2
  • S. Doherty, S. Dalvandi, B. Dongol, und H. Wehrheim, "Unifying Operational Weak Memory Verification: An Axiomatic Approach" ACM Trans. Comput. Logic, vol. 23, iss. 4.
    doi: 10.1145/3545117
(Stand: 12.07.2024)  | 
Zum Seitananfang scrollen Scroll to the top of the page