Anzeige
Erschienen in:
2016 | OriginalPaper | Buchkapitel
Efficient Verification of Program Fragments: Eager POR
verfasst von : Patrick Metzler, Habib Saissi, Péter Bokor, Robin Hesse, Neeraj Suri
Erschienen in: Automated Technology for Verification and Analysis
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
Software verification of concurrent programs is hampered by an exponentially growing state space due to non-deterministic process scheduling. Partial order reduction (POR)-based verification has proven to be a powerful technique to handle large state spaces.
In this paper, we propose a novel dynamic POR algorithm, called \(\textit{Eager POR}\) (\(\textsc {epor}\)), that requires considerably less overhead during state space exploration than existing algorithms. \(\textsc {epor}\) is based on a formal characterization of program fragments for which exploration can be scheduled in advance and dependency checks can be avoided. We show the correctness of this characterization and evaluate the performance of \(\textsc {epor}\) in comparison to existing state-of-the-art dynamic POR algorithms. Our evaluation shows substantial improvement in the runtime performance by up to 91 %.