Abstract
The symbolic model checker NuSMV has been used to check safety properties for railway interlockings. When the size of the models increased, the model checking efficiency decreased dramatically to a point at which the verification failed due to lack of memory. At that point the models we could check were still small in the real world of railway interlockings. Various standard options to the NuSMV model checker were tried, mostly without significant improvement. However, the analysis of our model provided information on how to optimise the variable orderings and also the ordering and clustering of the partitioned transition relation. The NuSMV code was adapted to enable user control for ordering and clustering of transitions. This replacement of the tool’s generic algorithm improved efficiency enormously, enabling the checking of safety properties for very large models. This paper discusses how the characteristics of our model are used to find the optimised parameters.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Robinson, N., Barney, D., Kearney, P., Nikandros, G., Tombs, D.: Automatic generation and verification of design specification. In: Proc. of Int. Symp. of the International Council On Systems Engineering (INCOSE) (2001)
Cimatti, A., Clarke, E., Giunchiglia, E., Giunchiglia, F., Pistore, M., Roveri, M., Sebastiani, R., Tacchella, A.: NuSMV 2: an OpenSource tool for symbolic model checking. In: Brinksma, E., Larsen, K.G. (eds.) CAV 2002. LNCS, vol. 2404, pp. 359–364. Springer, Heidelberg (2002)
Winter, K., Robinson, N.J.: Modelling large interlocking systems and model checking small ones. In: Oudshoorn, M. (ed.) Proc. of Australasian Computer Science Conference (ACSC 2003). Australian Computer Science Communications, vol. 16 (2003)
McMillan, K.: Symbolic Model Checking. Kluwer Academic Publishers, Dordrecht (1993)
Clarke, E., Grumberg, O., Peled, D.: Model Checking. MIT Press, Cambridge (2000)
Burch, J.R., Clarke, E.M., Long, D.E.: Symbolic model checking with partitioned transition relations. In: Halaas, A., Denyer, P.B. (eds.) Proc. of Int. Conference on Very Large Scale Integration, pp. 49–58. North-Holland, Amsterdam (1991)
Geist, D., Beer, I.: Efficient model checking by automated ordering of transition relation. In: Dill, D.L. (ed.) CAV 1994. LNCS, vol. 818, pp. 299–310. Springer, Heidelberg (1994)
Ranjan, R., Aziz, A., Brayton, R., Plessier, B., Pixley, C.: Efficient BDD algorithms for FSM synthesis and verification. In: Proc. of IEEE/ACM Int. Workshop on Logic Synthesis (1995)
Moon, I., Hachtel, G.D., Somenzi, F.: Border-block triangular form and conjunction schedule in image computation. In: Johnson, S.D., Hunt Jr., W.A. (eds.) FMCAD 2000. LNCS, vol. 1954, pp. 73–90. Springer, Heidelberg (2000)
Somenzi, F.: CUDD: CU Decision Diagram package — release 2.3.0. In: Department of Electrical and Computer Engineering — University of Colorado at Boulder (September 1998)
Bryant, R.E.: Graph-based algorithms for boolean function manipulation. IEEE Transactions On Computers C-35(8) (1986)
Lewis, G., Comella-Dorda, S., Gluch, D., Hudak, J., Weinstock, C.: Model-based verification: Analysis guidelines. Technical Report CMU/SEI-2001-TN-028, Carnegie Mellon Software Engineering Institute (2001)
Chan, W., Anderson, R.J., Beame, P., Burns, S., Modugno, F., Notkin, D., Reese, J.D.: Model checking large software specifications. IEEE Transactions on Software Engineering 24(7), 498–520 (1998)
Kamhi, G., Fix, L.: Adaptive variable reordering for symbolic model checking. In: Proc. of IEEE/ACM Int. Conference on Computer-aided design (ICCAD 1998), pp. 359–365. ACM Press, New York (1998)
Lu, Y., Jain, J., Clarke, E., Fujita, M.: Efficient variable ordering using a BDD based sampling. In: Proc. of Int. Conference on Design automation (DAC 2000), pp. 687–692. ACM Press, New York (2000)
Rudell, R.: Dynamic variable ordering for ordered binary decision diagrams. In: Proc. of IEEE/ACM Int. Conference on Computer-aided design (ICCAD 1993), pp. 42–47. IEEE Computer Society Press, Los Alamitos (1993)
Winter, K., Johnston, W., Robinson, P., Strooper, P., van den Berg, L.: Tool support for checking railway interlocking designs. In: Cant, T. (ed.) 10th Australian Workshop on Safety Related Programmable Systems (SCS 2005), vol. 55, Australian Computer Society, Inc. (to appear, 2005)
Cavda, R., Cimatti, A., Olivetti, E., Pistore, M., Roveri, M.: NuSMV 2.0 User Manual (2001), http://nusmv.irst.itc.it
Eisner, C.: Using symbolic model checking to verify the railway stations of hoorn-kersenboogerd and heerhugowaard. In: Pierre, L., Kropf, T. (eds.) CHARME 1999. LNCS, vol. 1703, pp. 97–109. Springer, Heidelberg (1999)
Huber, M., King, S.: Towards an integrated model checker for railway signalling data. In: Eriksson, L.-H., Lindsay, P.A. (eds.) FME 2002. LNCS, vol. 2391, pp. 204–223. Springer, Heidelberg (2002)
Wang, C., Hachtel, G.D., Somenzi, F.: The compositional far side of image computation. In: Proc. of IEEE/ACM Int. Conference on Computer-Aided Design (ICCAD 2003), pp. 334–340. IEEE Computer Society, Los Alamitos (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Johnston, W., Winter, K., van den Berg, L., Strooper, P., Robinson, P. (2006). Model-Based Variable and Transition Orderings for Efficient Symbolic Model Checking. In: Misra, J., Nipkow, T., Sekerinski, E. (eds) FM 2006: Formal Methods. FM 2006. Lecture Notes in Computer Science, vol 4085. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11813040_35
Download citation
DOI: https://doi.org/10.1007/11813040_35
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-37215-8
Online ISBN: 978-3-540-37216-5
eBook Packages: Computer ScienceComputer Science (R0)