Split Transition Power Abstraction for Unbounded Safety

Abstract:

Transition Power Abstraction (TPA) is a recent symbolic model checking approach that leverages Craig interpolation to create a sequence of symbolic abstractions for transition paths that double in length with each new element. This doubling abstraction allows the approach to find bugs that require long executions much faster than traditional approaches that unfold transitions one at a time, but its ability to prove system safety is limited. This paper proposes a novel instantiation of the TPA approach capable of proving unbounded safety efficiently while preserving the unique capability to detect deep counterexamples. The idea is to split the transition over-approximations in two complementary parts. One part focuses only on reachability in fixed number of steps, the second part complements it by summarizing all shorter paths. The resulting split abstractions are suitable for discovering safe transition invariants, making the SPLIT-TPA approach much more efficient in proving safety and even improving the counterexample detection. The approach is implemented in the constrained Horn clause solver GOLEM and our experimental comparison against state-of-the-art solvers shows it to be both competitive and complementary.

BibTeX:

@inproceedings{blicha_split_2022,
    title = {{Split Transition Power Abstraction for Unbounded Safety}},
    author = {Blicha, Martin and Fedyukovich, Grigory and Hyvärinen, Antti and Sharygina, Natasha},
    year = {2022},
    booktitle = {{Proceedings of FMCAD'22}},
    location = {Trento, Italy},
    doi = {10.34727/2022/isbn.978-3-85448-053-2_42},
    isbn = {978-3-85448-053-2},
    pages = {349--358},
    url = {https://repositum.tuwien.at/handle/20.500.12708/81371},
}

Proceedings paper