Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-23T15:47:53.019Z Has data issue: false hasContentIssue false
  • English
  • Français

SMT-based verification of data-aware processes: a model-theoretic approach

Published online by Cambridge University Press:  03 April 2020

Diego Calvanese ,
Silvio Ghilardi Open the ORCID record for Silvio Ghilardi [Opens in a new window] ,
Alessandro Gianola Open the ORCID record for Alessandro Gianola [Opens in a new window] ,
Marco Montali  and
Andrey Rivkin
Diego Calvanese
Affiliation:
Free University of Bozen-Bolzano
Silvio Ghilardi
Affiliation:
Università degli Studi di Milano
Alessandro Gianola*
Affiliation:
Free University of Bozen-Bolzano
Marco Montali
Affiliation:
Free University of Bozen-Bolzano
Andrey Rivkin
Affiliation:
Free University of Bozen-Bolzano
*
*Corresponding author. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

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 (DB) instance. Toward 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 Modulo Theories) 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.

Keywords

Verification of data-aware processessatisfiability modulo theoriesmodel completenesswell-quasi-ordersdatabase theory
Type
Paper
Information
Mathematical Structures in Computer Science , Volume 30 , Issue 3 , March 2020 , pp. 271 - 313
Copyright
© The Author(s) 2020. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Abdulla, P. A., Cerans, K., Jonsson, B. and Tsay, Y.-K. (1996). General decidability theorems for infinite-state systems. In: Proceedings of the 11th Annual IEEE Symposium on Logic in Computer Science (LICS), 313–321.CrossRefGoogle Scholar
Alberti, F., Armando, A. and Ranise, S. (2011). ASASP: automated symbolic analysis of security policies. In: Proceedings of the 23rd International Conference on Automated Deduction (CADE), LNCS (LNAI), vol. 6803, Springer, 26–33.CrossRefGoogle Scholar
Alberti, F., Bruttomesso, R., Ghilardi, S., Ranise, S. and Sharygina, N. (2012a). SAFARI: SMT-based abstraction for arrays with interpolants. In: Proceedings of the 24th International Conference on Computer Aided Verification (CAV), LNCS, vol. 7358, Springer, 679–685.Google Scholar
Alberti, F., Bruttomesso, R., Ghilardi, S., Ranise, S. and Sharygina, N. (2014a). An extension of lazy abstraction with interpolation for programs with arrays. Formal Methods in System Design 45 (1) 63–109.CrossRefGoogle Scholar
Alberti, F., Ghilardi, S., Pagani, E., Ranise, S. and Rossi, G. P. (2010). Brief announcement: automated support for the design and validation of fault tolerant parameterized systems - A case study. In: Proceeding of 24th International Symposium on Distributed Computing DISC, LNCS, vol. 6343, Springer, 392–394.CrossRefGoogle Scholar
Alberti, F., Ghilardi, S., Pagani, E., Ranise, S. and Rossi, G. P. (2012b). Universal guards, relativization of quantifiers, and failure models in Model Checking Modulo Theories. Journal on Satisfiability, Boolean Modeling and Computation 8 (1/2) 29–61.CrossRefGoogle Scholar
Alberti, F., Ghilardi, S. and Sharygina, N. (2014b). Booster: an acceleration-based verification framework for array programs. In: Proceedings of the 12th International Symposium on Automated Technology for Verification and Analysis (ATVA), LNCS, vol. 8837, Springer, 18–23.Google Scholar
Alberti, F., Ghilardi, S. and Sharygina, N. (2017). A framework for the verification of parameterized infinite-state systems. Fundamenta Informaticae 150 (1) 1–24.CrossRefGoogle Scholar
Baader, F., Ghilardi, S. and Tinelli, C. (2006). A new combination procedure for the word problem that generalizes fusion decidability results in modal logics. Information and Computation 204 (10) 1413–1452.CrossRefGoogle Scholar
Baader, F. and Nipkow, T. (1998). Term Rewriting and All That, Cambridge University Press.CrossRefGoogle Scholar
Bojańczyk, M., Segoufin, L. and Toruńczyk, S. (2013). Verification of database-driven systems via amalgamation. In: Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), 63–74.CrossRefGoogle Scholar
Bradley, A. R. (2011). SAT-based model checking without unrolling. In: Proceedings of the 12th International Conference on Verification, Model Checking, and Abstract Interpretation VMCAI, LNCS, vol. 6538, Springer, 70–87.CrossRefGoogle Scholar
Bradley, A. R. (2012). IC3 and beyond: incremental, inductive verification. In: Proceedings of the 24th International Conference on Computer Aided Verification (CAV), LNCS, vol. 7358, Springer, 4.Google Scholar
Bradley, A. R. and Manna, Z. (2007). The Calculus of Computation - Decision Procedures with Applications to Verification, Springer.Google Scholar
Bruschi, D., Di Pasquale, A., Ghilardi, S., Lanzi, A. and Pagani, E. (2017). Formal verification of ARP (address resolution protocol) through SMT-based model checking - A case study. In: Proceedings of the 13th International Conference on Integrated Formal Methods (IFM), LNCS, vol. 10510, Springer, 391–406.CrossRefGoogle Scholar
Bruttomesso, R., Carioni, A., Ghilardi, S. and Ranise, S. (2012). Automated analysis of parametric timing-based mutual exclusion algorithms. In: Proceedings of the 4th International Symposium on NASA Formal Methods (NFM), LNCS, vol. 7226, Springer, 279–294.CrossRefGoogle Scholar
Calvanese, D., De Giacomo, G. and Montali, M. (2013). Foundations of data-aware process analysis: a database theory perspective. In: Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), 1–12.CrossRefGoogle Scholar
Calvanese, D., Ghilardi, S., Gianola, A., Montali, M. and Rivkin, A. (2018a). Quantifier Elimination for Database Driven Verification. Technical Report arXiv:1806.09686, arXiv.org.Google Scholar
Calvanese, D., Ghilardi, S., Gianola, A., Montali, M. and Rivkin, A. (2018b). Verification of Data-Aware Processes via Array-Based Systems (Extended Version). Technical Report arXiv:1806.11459, arXiv.org.Google Scholar
Calvanese, D., Ghilardi, S., Gianola, A., Montali, M. and Rivkin, A. (2019a). Formal modeling and SMT-based parameterized verification of data-aware BPMN. In: Proceeding of the 17th International Conference on Business Process Management (BPM), LNCS, vol. 11675, Springer, 157–175.Google Scholar
Calvanese, D., Ghilardi, S., Gianola, A., Montali, M. and Rivkin, A. (2019b). From model completeness to verification of data aware processes. In: Lutz, C., Sattler, U., Tinelli, C., Turhan, A.-Y., and Wolter, F. (eds.) Description Logic, Theory Combination, and All That, LNCS, vol. 11560, Springer, 212–239.Google Scholar
Calvanese, D., Ghilardi, S., Gianola, A., Montali, M. and Rivkin, A. (2019c). Model completeness, covers and superposition. In: Proceedings of 27th International Conference on Automated Deduction (CADE), LNCS (LNAI), vol. 11716, Springer, 142–160.Google Scholar
Calvanese, D., Ghilardi, S., Gianola, A., Montali, M. and Rivkin, A. (2019d). Verification of data-aware processes: challenges and opportunities for automated reasoning. In: Proceedings of the 2nd International Workshop on Automated Reasoning: Challenges, Applications, Directions, Exemplary Achievements (ARCADE), EPTCS, vol. 311.CrossRefGoogle Scholar
Carioni, A., Ghilardi, S. and Ranise, S. (2010). MCMT in the land of parametrized timed automata. In: Proceedings of the 6th International Verification Workshop (VERIFY), 47–64.Google Scholar
Chang, C.-C. and Keisler, J. H. (1990). Model Theory. North-Holland Publishing Co.Google Scholar
Cimatti, A., Stojic, I. and Tonetta, S. (2018). Formal specification and verification of dynamic parametrized architectures. In: Proceedings of the 22nd International Symposium on Formal Methods (FM), LNCS, vol. 10951, Springer, 625–644.CrossRefGoogle Scholar
Conchon, S., Declerck, D. and Zaidi, F. (2018a). Cubicle-W: parameterized model checking on weak memory. In: Proceedings of the 9th International Joint Conference on Automated Reasoning (IJCAR), LNCS (LNAI), vol. 10900, Springer, 152–160.Google Scholar
Conchon, S., Delzanno, G. and Ferrando, A. (2018b). Declarative parameterized verification of topology-sensitive distributed protocols. In: Proceedings of the 6th International Conference on Networked Systems (NETYS), LNCS, vol. 11028, Springer, 209–224.Google Scholar
Conchon, S., Goel, A., Krstic, S., Mebsout, A. and ZaÏdi, F. (2012). Cubicle: a parallel SMT-based model checker for parameterized systems - Tool paper. In: Proceedings of the 24th International Conference on Computer Aided Verification (CAV), LNCS, vol. 7358, Springer, 718–724.CrossRefGoogle Scholar
Conchon, S., Goel, A., Krstic, S., Mebsout, A. and ZaÏdi, F. (2013). Invariants for finite instances and beyond. In: Proceedings of the International Conference on Formal Methods in Computer-Aided Design (FMCAD), 61–68.CrossRefGoogle Scholar
Conchon, S., Mebsout, A. and Zadi, F. (2015). Certificates for parameterized model checking. In: Proceeding of the 20th International Symposium on Formal Methods (FM), LNCS, vol. 9109, Springer, 126–142.CrossRefGoogle Scholar
Damaggio, E., Deutsch, A. and Vianu, V. (2012). Artifact systems with data dependencies and arithmetic. ACM Transactions on Database Systems 37 (3) 22:1–22:36.CrossRefGoogle Scholar
Delzanno, G. (2002). An overview of MSR(C): a CLP-based framework for the symbolic verification of parameterized concurrent systems. Electronic Notes in Theoretical Computer Science 76 65–82.CrossRefGoogle Scholar
Delzanno, G. (2018). Parameterized verification of publish/subcribe protocols via infinite-state model checking. In: Proceedings of the 33rd Italian Conference on Computational Logic (CILC), 97–111.Google Scholar
Delzanno, G., Esparza, J. and Podelski, A. (1999). Constraint-based analysis of broadcast protocols. In: Proceeding of 13th International Workshop on Computer Science Logic (CSL), LNCS, vol. 1683, Springer, 50–66.CrossRefGoogle Scholar
Deutsch, A., Hull, R., Li, Y. and Vianu, V. (2018). Automatic verification of database-centric systems. SIGLOG News 5 (2) 37–56.CrossRefGoogle Scholar
Deutsch, A., Hull, R., Patrizi, F. and Vianu, V. (2009). Automatic verification of data-centric business processes. In: Proceedings of the 12th International Conference on Database Theory (ICDT), 252–267.CrossRefGoogle Scholar
Deutsch, A., Li, Y. and Vianu, V. (2016). Verification of hierarchical artifact systems. In: Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), 179–194.CrossRefGoogle Scholar
Deutsch, A., Li, Y. and Vianu, V. (2019). Verification of hierarchical artifact systems. ACM Transactions on Database Systems 44 (3) 12:1–12:68.CrossRefGoogle Scholar
Dutertre, B. and De Moura, L. (2006). The YICES SMT Solver. Technical Report, SRI International.Google Scholar
Esparza, J., Finkel, A. and Mayr, R. (1999). On the verification of broadcast protocols. In: Proceedings of the 14th Annual IEEE Symposium on Logic in Computer Science (LICS), 352–359.CrossRefGoogle Scholar
Fagin, R. (1976). Probabilities on finite models. Journal of Symbolic Logic 41 (1) 50–58.CrossRefGoogle Scholar
Ghilardi, S. (2004). Model theoretic methods in combined constraint satisfiability. Journal of Automated Reasoning 33 (3–4) 221–249.CrossRefGoogle Scholar
Ghilardi, S. and Gianola, A. (2017). Interpolation, amalgamation and combination (the non-disjoint signatures case). In: Proceedings of the 11th International Symposium on Frontiers of Combining Systems (FroCoS), LNCS (LNAI), vol. 10483, Springer, 316–332.CrossRefGoogle Scholar
Ghilardi, S. and Gianola, A. (2018). Modularity results for interpolation, amalgamation and superamalgamation. Annals of Pure and Applied Logic 169 (8) 731–754.CrossRefGoogle Scholar
Ghilardi, S., Nicolini, E., Ranise, S. and Zucchelli, D. (2008a). Towards SMT model checking of array-based systems. In: Proceedings of the 4th International Joint Conference on Automated Reasoning (IJCAR), LNCS (LNAI), vol. 5195, Springer, 67–82.Google Scholar
Ghilardi, S., Nicolini, E. and Zucchelli, D. (2008b). A comprehensive framework for combined decision procedures. ACM Transactions on Computational Logic 9 (2) 8:1–8:54.CrossRefGoogle Scholar
Ghilardi, S. and Ranise, S. (2010a). Backward reachability of array-based systems by SMT solving: termination and invariant synthesis. Logical Methods in Computer Science 6 (4).CrossRefGoogle Scholar
Ghilardi, S. and Ranise, S. (2010b). MCMT: a model checker modulo theories. In: Proceedings of the 5th International Joint Conference on Automated Reasoning (IJCAR), LNCS (LNAI), vol. 6173, Springer, 22–29.Google Scholar
Ghilardi, S. and van Gool, S. J. (2016). Monadic second order logic as the model companion of temporal logic. In: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 417–426.CrossRefGoogle Scholar
Ghilardi, S. and van Gool, S. J. (2017). A model-theoretic characterization of monadic second order logic on infinite words. Journal of Symbolic Logic 82 (1) 62–76.CrossRefGoogle Scholar
Higman, G. (1952). Ordering by divisibility in abstract algebras. Proceedings of the London Mathematical Society 3 (2) 326–336.CrossRefGoogle Scholar
Hoder, K. and Bjørner, N. (2012). Generalized property directed reachability. In: Proceedings of the 15th International Conference on Theory and Applications of Satisfiability Testing (SAT), LNCS, vol. 7317, Springer, 157–171.CrossRefGoogle Scholar
Hull, R. (2008). Artifact-centric business process models: brief survey of research results and challenges. In: Proceedings of the OTM Confederated International Conferences, LNCS, vol. 5332, Springer, 1152–1163.Google Scholar
Kruskal, J. B. (1960). Well-quasi-ordering, the tree theorem, and Vazsonyi’s conjecture. Transactions of the American Mathematical Society 95 210–225.Google Scholar
Lazic, R., Newcomb, T. C., Ouaknine, J., Roscoe, A. W. and Worrell, J. (2008). Nets with tokens which carry data. Fundamenta Informaticae 88 (3) 251–274.Google Scholar
Li, Y., Deutsch, A. and Vianu, V. (2017). VERIFAS: a practical verifier for artifact systems. Proceedings of the VLDB Endowment 11 (3) 283–296.Google Scholar
Lipparini, P. (1982). Locally finite theories with model companion. In: Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti, Serie 8, vol. 72, Accademia Nazionale dei Lincei.Google Scholar
McMillan, K. L. (2006). Lazy abstraction with interpolants. In: Proceedings of the 18th International Conference on Computer Aided Verification (CAV), LNCS, vol. 4144, Springer, 123–136.CrossRefGoogle Scholar
Nicolini, E., Ringeissen, C. and Rusinowitch, M. (2009a). Data structures with arithmetic constraints: a non-disjoint combination. In: Proceedings of the 7th International Symposium on Frontiers of Combining Systems (FroCoS), LNCS (LNAI), vol. 5749, Springer, 319–334.Google Scholar
Nicolini, E., Ringeissen, C. and Rusinowitch, M. (2009b). Satisfiability procedures for combination of theories sharing integer offsets. In: Proceedings of the 15th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), LNCS, vol. 5505, Springer, 428–442.Google Scholar
Nicolini, E., Ringeissen, C. and Rusinowitch, M. (2010). Combining satisfiability procedures for unions of theories with a shared counting operator. Fundamenta Informaticae 105 (1–2) 163–187.CrossRefGoogle Scholar
Nieuwenhuis, R. and Rubio, A. (2001). Paramodulation-based theorem proving. In: Robinson, J. A., and Voronkov, A. (eds.) Handbook of Automated Reasoning (in 2 Volumes), MIT Press, 371–443.CrossRefGoogle Scholar
Rado, R. (1964). Universal graphs and universal functions. Acta Arithmetica 9 331–340.CrossRefGoogle Scholar
Robinson, A. (1951). On the Metamathematics of Algebra, North-Holland.Google Scholar
Robinson, A. (1963). Introduction to Model Theory and to the Metamathematics of Algebra, Studies in Logic and the Foundations of Mathematics, North-Holland.Google Scholar
Rosa-Velardo, F. and de Frutos-Escrig, D. (2011). Decidability and complexity of Petri nets with unordered data. Theoretical Computer Science 412 (34) 4439–4451.CrossRefGoogle Scholar
Schmitz, S. and Schnoebelen, P. (2013). The power of well-structured systems. In: Proceedings of the 24th International Conference on Concurrency Theory (CONCUR), LNCS, vol. 8052, Springer, 5–24.Google Scholar
Silver, B. (2011). BPMN Method and Style, 2nd edn., Cody-Cassidy.Google Scholar
Sofronie-Stokkermans, V. (2008). Interpolation in local theory extensions. Logical Methods in Computer Science 4 (4).CrossRefGoogle Scholar
Sofronie-Stokkermans, V. (2016). On interpolation and symbol elimination in theory extensions. In: Proceedings of the 8th International Joint Conference on Automated Reasoning (IJCAR), LNCS (LNAI), vol. 9706, Springer, 273–289.CrossRefGoogle Scholar
Sofronie-Stokkermans, V. (2018). On interpolation and symbol elimination in theory extensions. Logical Methods in Computer Science 14 (3).Google Scholar
Vianu, V. (2009). Automatic verification of database-driven systems: a new frontier. In: Proceedings of the 12th International Conference on Database Theory (ICDT), 1–13.CrossRefGoogle Scholar
Wheeler, W. H. (1976). Model-companions and definability in existentially complete structures. Israel Journal of Mathematics 25 (3–4) 305–330.CrossRefGoogle Scholar