×

zbMATH — the first resource for mathematics

SMT-based verification of data-aware processes: a model-theoretic approach. (English) Zbl 07283036
Summary: 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.
MSC:
68 Computer science
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 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.
[2] 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.
[3] 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. · Zbl 1352.68141
[4] 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 Design45 (1) 63-109. · Zbl 1317.68107
[5] 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.
[6] 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 Computation8 (1/2) 29-61. · Zbl 1331.68141
[7] 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. · Zbl 1448.68284
[8] Alberti, F., Ghilardi, S. and Sharygina, N. (2017). A framework for the verification of parameterized infinite-state systems. Fundamenta Informaticae150 (1) 1-24.
[9] 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 Computation204 (10) 1413-1452. · Zbl 1098.03048
[10] Baader, F. and Nipkow, T. (1998). Term Rewriting and All That, Cambridge University Press. · Zbl 0948.68098
[11] 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.
[12] 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. · Zbl 1317.68109
[13] 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.
[14] Bradley, A. R. and Manna, Z. (2007). The Calculus of Computation - Decision Procedures with Applications to Verification, Springer. · Zbl 1126.03001
[15] 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.
[16] 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.
[17] 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.
[18] 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. · Zbl 1443.68103
[19] 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. · Zbl 1443.68103
[20] 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. · Zbl 1443.68103
[21] 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. · Zbl 1443.68103
[22] 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. · Zbl 07178974
[23] 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. · Zbl 1443.68103
[24] 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.
[25] Chang, C.-C. and Keisler, J. H. (1990). Model Theory. North-Holland Publishing Co. · Zbl 0697.03022
[26] 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.
[27] 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. · Zbl 06958097
[28] 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.
[29] 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.
[30] 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.
[31] 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.
[32] Damaggio, E., Deutsch, A. and Vianu, V. (2012). Artifact systems with data dependencies and arithmetic. ACM Transactions on Database Systems37 (3) 22:1-22:36.
[33] 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 Science7665-82.
[34] 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.
[35] 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. · Zbl 0944.68139
[36] Deutsch, A., Hull, R., Li, Y. and Vianu, V. (2018). Automatic verification of database-centric systems. SIGLOG News5 (2) 37-56.
[37] 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.
[38] 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.
[39] Deutsch, A., Li, Y. and Vianu, V. (2019). Verification of hierarchical artifact systems. ACM Transactions on Database Systems44 (3) 12:1-12:68.
[40] Dutertre, B. and De Moura, L. (2006). The YICES SMT Solver. Technical Report, SRI International.
[41] 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.
[42] Fagin, R. (1976). Probabilities on finite models. Journal of Symbolic Logic41 (1) 50-58. · Zbl 0341.02044
[43] Ghilardi, S. (2004). Model theoretic methods in combined constraint satisfiability. Journal of Automated Reasoning33 (3-4) 221-249. · Zbl 1069.03008
[44] 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. · Zbl 06821641
[45] Ghilardi, S. and Gianola, A. (2018). Modularity results for interpolation, amalgamation and superamalgamation. Annals of Pure and Applied Logic169 (8) 731-754. · Zbl 06880849
[46] 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. · Zbl 1165.68406
[47] Ghilardi, S., Nicolini, E. and Zucchelli, D. (2008b). A comprehensive framework for combined decision procedures. ACM Transactions on Computational Logic9 (2) 8:1-8:54. · Zbl 1171.03306
[48] Ghilardi, S. and Ranise, S. (2010a). Backward reachability of array-based systems by SMT solving: termination and invariant synthesis. Logical Methods in Computer Science6 (4). · Zbl 1213.68379
[49] 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. · Zbl 1291.68257
[50] 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. · Zbl 1394.03033
[51] Ghilardi, S. and Van Gool, S. J. (2017). A model-theoretic characterization of monadic second order logic on infinite words. Journal of Symbolic Logic82 (1) 62-76. · Zbl 1432.03047
[52] Higman, G. (1952). Ordering by divisibility in abstract algebras. Proceedings of the London Mathematical Society3 (2) 326-336. · Zbl 0047.03402
[53] 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. · Zbl 1273.68229
[54] 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.
[55] Kruskal, J. B. (1960). Well-quasi-ordering, the tree theorem, and Vazsonyi’s conjecture. Transactions of the American Mathematical Society95210-225. · Zbl 0158.27002
[56] Lazic, R., Newcomb, T. C., Ouaknine, J., Roscoe, A. W. and Worrell, J. (2008). Nets with tokens which carry data. Fundamenta Informaticae88 (3) 251-274. · Zbl 1154.68090
[57] Li, Y., Deutsch, A. and Vianu, V. (2017). VERIFAS: a practical verifier for artifact systems. Proceedings of the VLDB Endowment11 (3) 283-296.
[58] 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. · Zbl 0524.03021
[59] 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. · Zbl 1188.68196
[60] 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. · Zbl 1193.68090
[61] 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. · Zbl 1234.68262
[62] Nicolini, E., Ringeissen, C. and Rusinowitch, M. (2010). Combining satisfiability procedures for unions of theories with a shared counting operator. Fundamenta Informaticae105 (1-2) 163-187. · Zbl 1215.03051
[63] 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. · Zbl 0997.03012
[64] Rado, R. (1964). Universal graphs and universal functions. Acta Arithmetica9331-340. · Zbl 0139.17303
[65] Robinson, A. (1951). On the Metamathematics of Algebra, North-Holland. · Zbl 0043.24702
[66] Robinson, A. (1963). Introduction to Model Theory and to the Metamathematics of Algebra, Studies in Logic and the Foundations of Mathematics, North-Holland. · Zbl 0118.25302
[67] Rosa-Velardo, F. and De Frutos-Escrig, D. (2011). Decidability and complexity of Petri nets with unordered data. Theoretical Computer Science412 (34) 4439-4451. · Zbl 1231.68172
[68] 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. · Zbl 1390.68488
[69] Silver, B. (2011). BPMN Method and Style, 2nd edn., Cody-Cassidy.
[70] Sofronie-Stokkermans, V. (2008). Interpolation in local theory extensions. Logical Methods in Computer Science4 (4). · Zbl 1170.03018
[71] 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. · Zbl 06623267
[72] Sofronie-Stokkermans, V. (2018). On interpolation and symbol elimination in theory extensions. Logical Methods in Computer Science14 (3). · Zbl 06943960
[73] 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.
[74] Wheeler, W. H. (1976). Model-companions and definability in existentially complete structures. Israel Journal of Mathematics25 (3-4) 305-330. · Zbl 0398.03023
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.