Bounded Verification of Multi-threaded Programs via Lazy Sequentialization
ACM Transactions on Programming Languages and Systems · 31.03.2022 · 44 (1) · 1-50
DOI: 10.1145/3478536 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Programming Languages and Systems, online erschienen am 09.12.2021. Verfasst von Omar Inverso und 4 weiteren Autor:innen. Die Arbeit wurde bisher 17-mal zitiert (Crossref) und nennt 97 Literaturangaben. Gefördert von: EPSRC, Università degli Studi di Salerno, University of Southampton Scholarship Schemes.
Abstract (Originalsprache)
Bounded verification techniques such as bounded model checking (BMC) have successfully been used for many practical program analysis problems, but concurrency still poses a challenge. Here, we describe a new approach to BMC of sequentially consistent imperative programs that use POSIX threads. We first translate the multi-threaded program into a nondeterministic sequential program that preserves reachability for all round-robin schedules with a given bound on the number of rounds. We then reuse existing high-performance BMC tools as backends for the sequential verification problem. Our translation is carefully designed to introduce very small memory overheads and very few sources of nondeterminism, so it produces tight SAT/SMT formulae, and is thus very effective in practice: Our Lazy-CSeq tool implementing this translation for the C programming language won several gold and silver medals in the concurrency category of the Software Verification Competitions (SV-COMP) 2014–2021 and was able to find errors in programs where all other techniques (including testing) failed. In this article, we give a detailed description of our translation and prove its correctness, sketch its implementation using the CSeq framework, and report on a detailed evaluation and comparison of our approach.
Förderung
- EPSRC
- Università degli Studi di Salerno
- University of Southampton Scholarship Schemes
- Amazon Research Awards
Zitieren
APA
Inverso, O., Tomasco, E., Fischer, B., Torre, S. L., & Parlato, G. (2022). Bounded Verification of Multi-threaded Programs via Lazy Sequentialization. ACM Transactions on Programming Languages and Systems, 44(1), 1-50. https://doi.org/10.1145/3478536
Vancouver
Inverso O, Tomasco E, Fischer B, Torre SL, Parlato G. Bounded Verification of Multi-threaded Programs via Lazy Sequentialization. ACM Transactions on Programming Languages and Systems. 2022;44(1):1-50. doi:10.1145/3478536
BibTeX
@article{Inverso2022,
author = {Inverso, Omar and Tomasco, Ermenegildo and Fischer, Bernd and Torre, Salvatore La and Parlato, Gennaro},
title = {Bounded Verification of Multi-threaded Programs via Lazy Sequentialization},
journal = {ACM Transactions on Programming Languages and Systems},
year = {2022},
volume = {44},
number = {1},
pages = {1--50},
doi = {10.1145/3478536}
}
EUVIMED