Anzeige
Erschienen in:
2016 | OriginalPaper | Buchkapitel
A Bounded Model Checker for Three-Valued Abstractions of Concurrent Software Systems
verfasst von : Nils Timm, Stefan Gruner, Matthias Harvey
Erschienen in: Formal Methods: Foundations and Applications
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
We present a technique for verifying concurrent software systems via SAT-based bounded model checking. It is based on a direct transfer of the system and an LTL property into a formula that encodes the corresponding model checking problem. In our approach we first employ three-valued abstraction. The state space of the resulting abstract system is then logically encoded, which saves us the expensive construction of an explicit state space model. The verification result can be obtained via two SAT checks. Our work includes the definition of the encoding and a theorem which states that the SAT result for an encoded verification task is equivalent to the result of the corresponding model checking problem. We also introduce an extension of the encoding by fairness constraints, which facilitates the verification of liveness properties. We have implemented our technique in an automatic verification tool that supports bounded LTL model checking under fairness.