SMT-based Verification of Data-Aware Processes: A Model-Theoretic Approach

Diego Calvanese, Silvio Ghilardi, Alessandro Gianola, Marco Montali, and Andrey Rivkin

Mathematical Structures in Computer Science. 30(3):271--313 2020.

In recent times, Satisfiability-Modulo-Theories (SMT) techniques gained increasing attention and obtained remarkable success in model-checking infinite state systems. Still, we believe that whenever more expressivity is needed in order to specify the systems to be verified, more and more support is needed from mathematical logic and model-theory. This is the case of the applications considered in this paper: we study verification over a general model of relational, data-aware processes, to assess (parameterized) safety properties irrespectively of the initial database instance. Towards this goal, we take inspiration from array-based systems, and tackle safety algorithmically via backward reachability. To enable the adoption of this technique in our rich setting, we make use of the model-theoretic machinery of model completion, which surprisingly turns out to be an effective tool for verification of relational systems, and represents the main original contribution of this paper. In this way, we pursue a twofold purpose. On the one hand, we isolate three notable classes for which backward reachability terminates, in turn witnessing decidability. Two of such classes relate our approach to conditions singled out in the literature, whereas the third one is genuinely novel. On the other hand, we are able to exploit SMT technology in implementations, building on the well-known MCMT model checker for array-based systems, and extending it to make all our foundational results fully operational. All in all, the present contribution is deeply rooted in the long-standing tradition of the application of model theory in computer science. In particular, this paper applies these ideas in an original mathematical context and shows how these techniques can be used for the first time to empower algorithmic techniques for the verification of infinite-state systems based on arrays, so as to make such techniques applicable to the timely, challenging settings of data-aware processes.


@article{MSCS-2020,
   title = "SMT-based Verification of Data-Aware Processes:  A
Model-Theoretic Approach",
   year = "2020",
   author = "Diego Calvanese and Silvio Ghilardi and Alessandro Gianola and
Marco Montali and Andrey Rivkin",
   journal = "Mathematical Structures in Computer Science",
   pages = "271--313",
   number = "3",
   volume = "30",
   doi = "10.1017/S0960129520000067",
}
pdf