A Cooperative Parallelization Approach for Property-Directed k-Induction

Abstract:

Recently presented, IC3-inspired symbolic model checking algorithms strengthen the procedure for showing inductiveness of lemmas expressing reachability of states. These approaches show an impressive performance gain in comparison to previous state-of-the-art, but also present new challenges to portfolio-based, lemma sharing parallelization as the solvers now store lemmas that serve different purposes. In this work we formalize this recent algorithm class for lemma sharing parallel portfolios using two central engines, one for checking inductiveness and the other for checking bounded reachability, and show when the respective engines can share their information. In our implementation based on the PD-KIND algorithm, the approach provides a consistent speed-up already in a multi-core environment, and surpasses in performance the winners of a recent solver competition by a comfortable margin.

BibTeX:

@inproceedings{blicha_cooperative_2020,
    title = {{A Cooperative Parallelization Approach for Property-Directed k-Induction}},
    author = {Blicha, Martin and Hyvärinen, Antti E. J. and Marescotti, Matteo and Sharygina, Natasha},
    year = {2020},
    booktitle = {{Verification, Model Checking, and Abstract Interpretation}},
    editor = {Beyer, Dirk and Zufferey, Damien},
    publisher = {Springer International Publishing},
    series = {{Lecture Notes in Computer Science}},
    location = {Cham},
    doi = {10.1007/978-3-030-39322-9_13},
    isbn = {978-3-030-39322-9},
    pages = {270--292},
}

Proceedings paper