Verification of Data-Aware Processes via Array-Based Systems (Extended Version)

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

Technical Report, arXiv.org e-Print archive. CoRR Technical Report arXiv:1806.11459 2018. Available at http://arxiv.org/abs/1806.11459.

We study verification over a general model of data-aware processes, to assess (parameterized) safety properties irrespectively of the initial database instance. We rely on an encoding into array-based systems, which allows us to check safety by adapting backward reachability, establishing for the first time a correspondence with model checking based on Satisfiability-Modulo-Theories (SMT). To do so, 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. Our encoding pursues a twofold purpose. On the one hand, it allows us to reconstruct and generalize the essence of some of the most important decidability results obtained in the literature for artifact-centric systems, and to devise a genuinely novel class of decidable cases. On the other, it makes it possible 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.


@techreport{Corr-2018-dap,
   title = "Verification of Data-Aware Processes via Array-Based Systems
(Extended Version)",
   year = "2018",
   author = "Diego Calvanese and Silvio Ghilardi and Alessandro Gianola and
Marco Montali and Andrey Rivkin",
   institution = "arXiv.org e-Print archive",
   number = "arXiv:1806.11459",
   note = "Available at http://arxiv.org/abs/1806.11459",
}
pdf url