×

Model checking of systems with many identical timed processes. (English) Zbl 1018.68046

Summary: Over the last years there has been an increasing research effort directed towards the automatic verification of infinite state systems, such as timed automata, hybri\"d automata, data-independent systems, relational automata, Petri nets, lossy channel systems, context-free and push-down processes. We present a method for deciding reachability properties of networks of timed processes. Such a network consists of an arbitrary set of identical timed automata, each with a single real-valued clock. Using a standard reduction from safety properties to reachability properties, we can use our algorithm to decide general safety properties of timed networks. To our knowledge, this is the first decidability result concerning verification of systems that are infinite-state in “two dimensions”: they contain an arbitrary set of (identical) processes, and they use infinite data-structures, viz real-valued clocks. We illustrate our method by showing how it can be used to automatically verify Fischer’s protocol, a timer-based protocol for enforcing mutual exclusion among an arbitrary number of processes. Finally, we show undecidability of the recurrent state problem: given a state in a timed network, check whether there is a computation of the network visiting the state infinitely often. This implies undecidability of model checking for any temporal logic which is sufficiently expressive to encode the recurrent state problem, such as PTL, CTL, etc.

MSC:

68Q60 Specification and verification (program logics, model checking, etc.)

Software:

CESAR
Full Text: DOI

References:

[1] P.A. Abdulla, K. C̆erāns, B. Jonsson, T. Yih-Kuen, General decidability theorems for infinite-state systems, in: Proc. 11th IEEE Int. Symp. on Logic in Computer Science, 1996, pp. 313-321.; P.A. Abdulla, K. C̆erāns, B. Jonsson, T. Yih-Kuen, General decidability theorems for infinite-state systems, in: Proc. 11th IEEE Int. Symp. on Logic in Computer Science, 1996, pp. 313-321.
[2] Abdulla, P. A.; C̆erāns, K.; Jonsson, B.; Yih-Kuen, T., Algorithmic analysis of programs with well quasi-ordered domains, Inform. and Comput., 160, 109-127 (2000) · Zbl 1046.68567
[3] Abdulla, P. A.; Jonsson, B., Undecidable verification problems for programs with unreliable channels, Inform. and Comput., 130, 1, 71-90 (1996) · Zbl 0872.68112
[4] Abdulla, P. A.; Jonsson, B., Verifying programs with unreliable channels, Inform. and Comput., 127, 2, 91-101 (1996) · Zbl 0856.68096
[5] Abdulla, P. A.; Kindahl, M., Decidability of simulation and bisimulation between lossy channel systems and finite state systems, (Lee, I.; Smolka, S. A., Proc. CONCUR’95, 6th Internat. Conf. on Concurrency Theory. Proc. CONCUR’95, 6th Internat. Conf. on Concurrency Theory, Lecture Notes in Computer Science, Vol. 962 (1995), Springer: Springer Berlin), 333-347
[6] Abadi, M.; Lamport, L., An old-fashioned recipe for real time, (de Bakker, J.; Huizing, C.; de Roever, W. P.; Rozenberg, G., Real-Time: Theory in Practice. Real-Time: Theory in Practice, Lecture Notes in Computer Science, Vol. 600 (1992), Springer: Springer Berlin), 1-27
[7] R. Alur, C. Courcoubetis, D. Dill, Model-checking for real-time systems, in: Proc. 5th IEEE Int. Symp. on Logic in Computer Science, Philadelphia, 1990, pp. 414-425.; R. Alur, C. Courcoubetis, D. Dill, Model-checking for real-time systems, in: Proc. 5th IEEE Int. Symp. on Logic in Computer Science, Philadelphia, 1990, pp. 414-425. · Zbl 0769.68088
[8] Alur, R.; Courcoubetis, C.; Henzinger, T.; Ho, P.-H., Hybrid automataan algorithmic approach to the specification and verification of hybrid systems, (Grossman; Nerode; Ravn; Rischel, Hybrid Systems. Hybrid Systems, Lecture Notes in Computer Science, Vol. 736 (1992), Springer: Springer Berlin), 209-229
[9] R. Alur, T. Henzinger, A really temporal logic, in: Proc. 30th Annual Symp. Foundations of Computer Science, 1989, pp. 164-169.; R. Alur, T. Henzinger, A really temporal logic, in: Proc. 30th Annual Symp. Foundations of Computer Science, 1989, pp. 164-169. · Zbl 0807.68065
[10] J.M. Barzdin, J.J. Bicevskis, A.A. Kalninsh, Automatic construction of complete sample systems for program testing, Proc. IFIP Congress, 1977.; J.M. Barzdin, J.J. Bicevskis, A.A. Kalninsh, Automatic construction of complete sample systems for program testing, Proc. IFIP Congress, 1977. · Zbl 0363.68013
[11] Berthomieu, B.; Diaz, M., Modeling and verification of time dependent systems using time Petri nets, IEEE Trans. on Software Eng., 17, 3, 259-273 (1991)
[12] Burkart, O.; Steffen, B., Composition, decomposition, and model checking of pushdown processes, Nordic J. Comput., 2, 2, 89-125 (1995) · Zbl 0839.68028
[13] C̆erāns, K., Decidability of bisimulation equivalence for parallel timer processes, (Proc. Workshop on Computer Aided Verification. Proc. Workshop on Computer Aided Verification, Lecture Notes in Computer Science, Vol. 663 (1992), Springer: Springer Berlin), 302-315
[14] C̆erāns, K., Feasibility of finite and infinite paths in data dependent programs, (Proc. LFCS’92. Proc. LFCS’92, Lecture Notes in Computer Science, Vol. 620 (1992), Springer: Springer Berlin), 69-80 · Zbl 0977.68527
[15] C̆erāns, K., Deciding properties of integral relational automata, (Abiteboul, S.; Shamir, E., Proc. ICALP’94. Proc. ICALP’94, Lecture Notes in Computer Science, Vol. 820 (1994), Springer: Springer Berlin), 35-46 · Zbl 1418.68126
[16] Clarke, E. M.; Emerson, E. A.; Sistla, A. P., Automatic verification of finite-state concurrent systems using temporal logic specification, ACM Trans. on Programming Languages and Systems, 8, 2, 244-263 (1986) · Zbl 0591.68027
[17] Clarke, E. M.; Grumberg, O.; Jha, S., Verifying parameterized networks using abstraction and regular languages, (Lee, I.; Smolka, S. A., Proc. CONCUR’95, 6th Internat. Conf. on Concurrency Theory. Proc. CONCUR’95, 6th Internat. Conf. on Concurrency Theory, Lecture Notes in Computer Science, Vol. 962 (1995), Springer: Springer Berlin), 395-407
[18] Esparza, J., Petri nets, commutative context-free grammars, and basic parallel processes, (Proc. Fundamentals of Computation Theory. Proc. Fundamentals of Computation Theory, Lecture Notes in Computer Science, Vol. 965 (1995), Springer: Springer Berlin), 221-232 · Zbl 1508.68241
[19] Finkel, A., Reduction and covering of infinite reachability trees, Inform. and Comput., 89, 144-179 (1990) · Zbl 0753.68073
[20] German, S. M.; Sistla, A. P., Reasoning about systems with many processes, J. ACM, 39, 3, 675-735 (1992) · Zbl 0799.68078
[21] Ghezzi, C.; Mandrioli, D.; Morasca, S.; Pezzè, M., A unified high-level Petri net formalism for time-critical systems, IEEE Trans. Software Eng., 17, 2, 160-172 (1991)
[22] Godefroid, P.; Wolper, P., Using partial orders for the efficient verification of deadlock freedom and safety properties, Formal Methods System Design, 2, 2, 149-164 (1993) · Zbl 0772.68064
[23] J.C. Godskesen, Timed modal specifications, Ph.D. Thesis, Aalborg University, 1994.; J.C. Godskesen, Timed modal specifications, Ph.D. Thesis, Aalborg University, 1994.
[24] T.A. Henzinger, Hybrid automata with finite bisimulations, in: Proc. ICALP’95, 1995, pp. 324-335.; T.A. Henzinger, Hybrid automata with finite bisimulations, in: Proc. ICALP’95, 1995, pp. 324-335. · Zbl 1412.68130
[25] Higman, G., Ordering by divisibility in abstract algebras, Proc. London Math. Soc., 2, 326-336 (1952) · Zbl 0047.03402
[26] Janc̆ar, P., Decidability of a temporal logic problem for Petri nets, Theoret. Comput. Sci., 74, 71-93 (1990) · Zbl 0701.68081
[27] Janc̆ar, P.; Esparza, J., Deciding finiteness of Petri nets up to bisimulation, (Proc. ICALP ’96. Proc. ICALP ’96, Lecture Notes in Computer Science, Vol. 1099 (1996), Springer: Springer Berlin), 478-489 · Zbl 1046.68622
[28] Janc̆ar, P.; Moller, F., Checking regular properties of Petri nets, (Proc. CONCUR’95, 6th Internat. Conf. on Concurrency Theory. Proc. CONCUR’95, 6th Internat. Conf. on Concurrency Theory, Lecture Notes in Computer Science, Vol. 962 (1995), Springer: Springer Berlin), 348-362
[29] Jonsson, B.; Parrow, J., Deciding bisimulation equivalences for a class of non-finite-state programs, Inform. and Comput., 107, 2, 272-302 (1993) · Zbl 0799.68133
[30] M. Kindahl, Verification of infinite-state systems: decision problems and efficient algorithms, Ph.D. Thesis, Department of Computer Systems, Uppsala University, Sweden, 1999.; M. Kindahl, Verification of infinite-state systems: decision problems and efficient algorithms, Ph.D. Thesis, Department of Computer Systems, Uppsala University, Sweden, 1999.
[31] Kristoffersen, K. J.; Larroussinie, F.; Larsen, K. G.; Pettersson, P.; Yi, W., A compositional proof of a real-time mutual exclusion protocol, (Proc. TAPSOFT’97, 7th Internat. J. Confer. on the Theory and Practice of Software Development, Lille, France. Proc. TAPSOFT’97, 7th Internat. J. Confer. on the Theory and Practice of Software Development, Lille, France, Lecture Notes in Computer Science, Vol. 1214 (1997), Springer: Springer Berlin), 565-579
[32] R.P. Kurshan, K. McMillan, A structural induction theorem for processes, in: Proc. 8th ACM Symp. on Principles of Distributed Computing, Canada, Edmonton, Alberta, 1989, pp. 239-247.; R.P. Kurshan, K. McMillan, A structural induction theorem for processes, in: Proc. 8th ACM Symp. on Principles of Distributed Computing, Canada, Edmonton, Alberta, 1989, pp. 239-247. · Zbl 0828.68096
[33] K.G. Larsen, B. Steffen, C. Weise, Fischer’s protocol revisited: a simple proof using modal constraints, in: Proc. 4th DIMACS Workshop on Verification and Control of Hybrid Systems, New Brunswick, NJ, October 1995.; K.G. Larsen, B. Steffen, C. Weise, Fischer’s protocol revisited: a simple proof using modal constraints, in: Proc. 4th DIMACS Workshop on Verification and Control of Hybrid Systems, New Brunswick, NJ, October 1995.
[34] Lothaire, M., Combinatorics on Words, Encyclopedia of Mathematics and its Applications, Vol. 17 (1983), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0514.20045
[35] Merlin, P.; Farber, D. J., Recoverability of communication protocols — implications of a theoretical study, IEEE Trans. Comput., COM-24, 1036-1043 (1976) · Zbl 0362.68096
[36] Queille, J. P.; Sifakis, J., Specification and verification of concurrent systems in Cesar, (Dezani-Ciancaglini, M.; Montanari, M., Proc. Int. Symp. Programming. Proc. Int. Symp. Programming, Lecture Notes in Computer Science, Vol. 137 (1982), Springer: Springer Berlin), 337-351 · Zbl 0482.68028
[37] Schneider, F. B.; Bloom, B.; Marzullo, K., Putting time into proof outlines, (de Bakker, J. W.; Huizing, C.; de Roever, W. P.; Rozenberg, G., Real-Time: Theory in Practice. Real-Time: Theory in Practice, Lecture Notes in Computer Science, Vol. 600 (1992), Springer: Springer Berlin), 618-639
[38] Shankar, A. U., An introduction to assertional reasoning for concurrent systems, Comput. Surveys, 25, 3, 225-262 (1993)
[39] Shankar, N., Verification of real-rime systems using PVS, (Courcoubetis, Proc. 5th Int. Conf. on Computer Aided Verification. Proc. 5th Int. Conf. on Computer Aided Verification, Lecture Notes in Computer Science, Vol. 697 (1993), Springer: Springer Berlin), 280-291
[40] C. Stirling, Decidability of bisimulation equivalence for normed pushdown processes, in: Proc. CONCUR ’96, 7th Int. Conf. on Concurrency Theory, Lecture Notes in Computer Science, Vol. 1119, Springer, Berlin, 1996, pp. 217-232.; C. Stirling, Decidability of bisimulation equivalence for normed pushdown processes, in: Proc. CONCUR ’96, 7th Int. Conf. on Concurrency Theory, Lecture Notes in Computer Science, Vol. 1119, Springer, Berlin, 1996, pp. 217-232. · Zbl 1514.68183
[41] M.Y. Vardi, P. Wolper, An automata-theoretic approach to automatic program verification, in: Proc. 1st IEEE Int. Symp. on Logic in Computer Science, June 1986, pp. 332-344.; M.Y. Vardi, P. Wolper, An automata-theoretic approach to automatic program verification, in: Proc. 1st IEEE Int. Symp. on Logic in Computer Science, June 1986, pp. 332-344.
[42] P. Wolper, Expressing interesting properties of programs in propositional temporal logic (extended abstract), in: Proc. 13th ACM Symp. on Principles of Programming Languages, January 1986, pp. 184-193.; P. Wolper, Expressing interesting properties of programs in propositional temporal logic (extended abstract), in: Proc. 13th ACM Symp. on Principles of Programming Languages, January 1986, pp. 184-193.
[43] Wolper, P.; Lovinfosse, V., Verifying properties of large sets of processes with network invariants (extended abstract), (Sifakis, J., Proc. Workshop on Computer Aided Verification. Proc. Workshop on Computer Aided Verification, Lecture Notes in Computer Science, Vol. 407 (1989), Springer: Springer Berlin), 68-80
[44] Yi, W., CCS+Time=an interleaving model for real time systems, (Leach Albert, J.; Monien, B.; Rodriguez Artalejo, M., Proc. ICALP’91. Proc. ICALP’91, Lecture Notes in Computer Science, Vol. 510 (1991), Springer: Springer Berlin), 217-228 · Zbl 0769.68027
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.