Error invariants for concurrent traces

Andreas Holzer, Daniel Schwartz-Narbonne, Mitra Tabaei Befrouei, Georg Weissenbacher, Thomas Wies

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Error invariants are assertions that over-approximate the reachable program states at a given position in an error trace while only capturing states that will still lead to failure if execution of the trace is continued from that position. Such assertions reflect the effect of statements that are involved in the root cause of an error and its propagation, enabling slicing of statements that do not contribute to the error. Previous work on error invariants focused on sequential programs. We generalize error invariants to concurrent traces by augmenting them with additional information about hazards such as write-after-write events, which are often involved in race conditions and atomicity violations. By providing the option to include varying levels of details in error invariants—such as hazards and branching information—our approach allows the programmer to systematically analyze individual aspects of an error trace. We have implemented a hazard-sensitive slicing tool for concurrent traces based on error invariants and evaluated it on benchmarks covering a broad range of real-world concurrency bugs. Hazard-sensitive slicing significantly reduced the length of the considered traces and still maintained the root causes of the concurrency bugs.

Original languageEnglish (US)
Title of host publicationFM 2016
Subtitle of host publicationFormal Methods - 21st International Symposium, Proceedings
EditorsConstance Heitmeyer, Anna Philippou, Stefania Gnesi, John Fitzgerald
PublisherSpringer Verlag
Pages370-387
Number of pages18
ISBN (Print)9783319489889
DOIs
StatePublished - 2016
Event21st International Symposium on Formal Methods, FM 2016 - Limassol, Cyprus
Duration: Nov 9 2016Nov 11 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9995 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other21st International Symposium on Formal Methods, FM 2016
CountryCyprus
CityLimassol
Period11/9/1611/11/16

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Error invariants for concurrent traces'. Together they form a unique fingerprint.

  • Cite this

    Holzer, A., Schwartz-Narbonne, D., Befrouei, M. T., Weissenbacher, G., & Wies, T. (2016). Error invariants for concurrent traces. In C. Heitmeyer, A. Philippou, S. Gnesi, & J. Fitzgerald (Eds.), FM 2016: Formal Methods - 21st International Symposium, Proceedings (pp. 370-387). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9995 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-48989-6_23