Static Analysis of Memory Models for SMT Encodings
Proceedings of the ACM on Programming Languages · 16.10.2023 · 7 (OOPSLA2) · 1618-1647
DOI: 10.1145/3622855 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Programming Languages, online erschienen am 16.10.2023. Verfasst von Thomas Haas und 3 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 89 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
The goal of this work is to improve the efficiency of bounded model checkers that are modular in the memory model. Our first contribution is a static analysis for the given memory model that is performed as a preprocessing step and helps us significantly reduce the encoding size. Memory model make use of relations to judge whether an execution is consistent. The analysis computes bounds on these relations: which pairs of events may or must be related. What is new is that the bounds are relativized to the execution of events. This makes it possible to derive, for the first time, not only upper but also meaningful lower bounds. Another important feature is that the analysis can import information about the verification instance from external sources to improve its precision. Our second contribution are new optimizations for the SMT encoding. Notably, the lower bounds allow us to simplify the encoding of acyclicity constraints. We implemented our analysis and optimizations within a bounded model checker and evaluated it on challenging benchmarks. The evaluation shows up-to 40% reduction in verification time (including the analysis) over previous encodings. Our optimizations allow us to efficiently check safety, liveness, and data race freedom in Linux kernel code.
Zitieren
APA
Haas, T., Maseli, R., Meyer, R., & León, H. P. D. (2023). Static Analysis of Memory Models for SMT Encodings. Proceedings of the ACM on Programming Languages, 7(OOPSLA2), 1618-1647. https://doi.org/10.1145/3622855
Vancouver
Haas T, Maseli R, Meyer R, León HPD. Static Analysis of Memory Models for SMT Encodings. Proceedings of the ACM on Programming Languages. 2023;7(OOPSLA2):1618-1647. doi:10.1145/3622855
BibTeX
@article{Haas2023,
author = {Haas, Thomas and Maseli, René and Meyer, Roland and León, Hernán Ponce de},
title = {Static Analysis of Memory Models for SMT Encodings},
journal = {Proceedings of the ACM on Programming Languages},
year = {2023},
volume = {7},
number = {OOPSLA2},
pages = {1618--1647},
doi = {10.1145/3622855}
}
EUVIMED