EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Static Analysis of Memory Models for SMT Encodings

Thomas Haas, René Maseli, Roland Meyer, Hernán Ponce de León

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →