[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

The High Road to Formal Validation:

Model Checking High-Level Versus Low-Level Specifications

  • Conference paper
Abstract State Machines, B and Z (ABZ 2008)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5238))

Included in the following conference series:

Abstract

In this paper we examine the difference between model checking high-level and low-level models. In particular, we compare the ProB model checker for the B-method and the Spin model checker for Promela. While Spin has a dramatically more efficient model checking engine, we show that in practice the performance can be disappointing compared to model checking high-level specifications with ProB. We investigate the reasons for this behaviour, examining expressivity, granularity and Spin’s search algorithms. We also show that certain types of information (such as symmetry) can be more easily inferred and exploited in high-level models, leading to a considerable reduction in model checking time.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Abrial, J.-R.: The B-Book. Cambridge University Press, Cambridge (1996)

    MATH  Google Scholar 

  2. Arvind, N.D., Katelman, M.: Getting formal verification into design flow. In: Cuéllar, J., Maibaum, T.S.E., Sere, K. (eds.) FM 2008. LNCS, vol. 5014, pp. 12–32. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  3. Basin, D.A., Friedrich, S., Gawkowski, M., Posegga, J.: Bytecode model checking: An experimental analysis. In: Bosnacki and Leue [8], pp. 42–59

    Google Scholar 

  4. Ben-Ari, M.: Principles of Concurrent and Distributed Programming, 2nd edn. Addison-Wesley, Reading (2006)

    Google Scholar 

  5. Ben-Ari, M.: Principles of the Spin Model Checker. Springer, Heidelberg (2008)

    MATH  Google Scholar 

  6. Bosnacki, D., Dams, D., Holenderski, L.: Symmetric Spin. STTT 4(1), 92–106 (2002)

    Article  Google Scholar 

  7. Bosnacki, D., Dams, D., Holenderski, L., Sidorova, N.: Model checking SDL with Spin. In: Graf, S., Schwartzbach, M.I. (eds.) TACAS 2000. LNCS, vol. 1785, pp. 363–377. Springer, Heidelberg (2000)

    Google Scholar 

  8. Bošnački, D., Leue, S. (eds.): SPIN 2002. LNCS, vol. 2318. Springer, Heidelberg (2002)

    MATH  Google Scholar 

  9. Burch, J.R., Clarke, E.M., McMillan, K.L., Dill, D.L., Hwang, L.J.: Symbolic model checking: 1020 states and beyond. Information and Computation 98(2), 142–170 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  10. Chen, J., Cui, H.: Translation from adapted uml to promela for corba-based applications. In: Graf, S., Mounier, L. (eds.) SPIN 2004. LNCS, vol. 2989, pp. 234–251. Springer, Heidelberg (2004)

    Google Scholar 

  11. Clarke, E.M., Grumberg, O., Peled, D.: Model Checking. MIT Press, Cambridge (1999)

    Google Scholar 

  12. Donaldson, A.F., Miller, A.: Automatic symmetry detection for model checking using computational group theory. In: Fitzgerald, J.S., Hayes, I.J., Tarlecki, A. (eds.) FM 2005. LNCS, vol. 3582, pp. 481–496. Springer, Heidelberg (2005)

    Google Scholar 

  13. Donaldson, A.F., Miller, A.: Exact and approximate strategies for symmetry reduction in model checking. In: Misra, J., Nipkow, T., Sekerinski, E. (eds.) FM 2006. LNCS, vol. 4085, pp. 541–556. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  14. Edelkamp, S., Leue, S., Lluch-Lafuente, A.: Partial-order reduction and trail improvement in directed model checking. STTT 6(4), 277–301 (2004)

    Article  Google Scholar 

  15. Edelkamp, S., Lluch-Lafuente, A., Leue, S.: Directed explicit model checking with hsf-spin. In: Dwyer, M.B. (ed.) SPIN 2001. LNCS, vol. 2057, pp. 57–79. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  16. Formal Systems (Europe) Ltd. Failures-Divergence Refinement — FDR2 User Manual (version 2.8.2)

    Google Scholar 

  17. Godefroid, P. (ed.): SPIN 2005. LNCS, vol. 3639. Springer, Heidelberg (2005)

    MATH  Google Scholar 

  18. Guelfi, N., Mammar, A.: A formal semantics of timed activity diagrams and its promela translation. In: APSEC, pp. 283–290. IEEE Computer Society, Los Alamitos (2005)

    Google Scholar 

  19. Holzmann, G.J.: The model checker Spin. IEEE Trans. Software Eng. 23(5), 279–295 (1997)

    Article  MathSciNet  Google Scholar 

  20. Holzmann, G.J.: An analysis of bitstate hashing. Formal Methods in System Design 13(3), 289–307 (1998)

    Article  MathSciNet  Google Scholar 

  21. Holzmann, G.J.: The Spin Model Checker: Primer and Reference Manual. Addison-Wesley, Reading (2004)

    Google Scholar 

  22. Holzmann, G.J., Peled, D.: An improvement in formal verification. In: Hogrefe, D., Leue, S. (eds.) FORTE. IFIP Conference Proceedings, vol. 6, pp. 197–211. Chapman & Hall, Boca Raton (1994)

    Google Scholar 

  23. Jackson, D.: Alloy: A lightweight object modelling notation. ACM Transactions on Software Engineering and Methodology 11, 256–290 (2002)

    Article  Google Scholar 

  24. Leuschel, M., Butler, M.: ProB: A model checker for B. In: Araki, K., Gnesi, S., Mandrioli, D. (eds.) FME 2003. LNCS, vol. 2805, pp. 855–874. Springer, Heidelberg (2003)

    Google Scholar 

  25. Leuschel, M., Butler, M.: Automatic refinement checking for B. In: Lau, K.-K., Banach, R. (eds.) ICFEM 2005. LNCS, vol. 3785, pp. 345–359. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  26. Leuschel, M., Butler, M., Spermann, C., Turner, E.: Symmetry reduction for B by permutation flooding. In: Julliand, J., Kouchnarenko, O. (eds.) B 2007. LNCS, vol. 4355, pp. 79–93. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  27. Leuschel, M., Butler, M.J.: ProB: an automated analysis toolset for the B method. STTT 10(2), 185–203 (2008)

    Article  Google Scholar 

  28. Leuschel, M., Massart, T.: Efficient approximate verification of B via symmetry markers. In: Proceedings International Symmetry Conference, pp. 71–85 (January 2007)

    Google Scholar 

  29. McMillan, K.L.: Symbolic Model Checking. PhD thesis, Boston (1993)

    Google Scholar 

  30. Peled, D.: Combining partial order reductions with on-the-fly model-checking. In: Dill, D.L. (ed.) CAV 1994. LNCS, vol. 818, pp. 377–390. Springer, Heidelberg (1994)

    Google Scholar 

  31. Prigent, A., Cassez, F., Dhaussy, P., Roux, O.: Extending the translation from sdl to promela. In: Bosnacki and Leue [8], pp. 79–94

    Google Scholar 

  32. Rothmaier, G., Kneiphoff, T., Krumm, H.: Using Spin and Eclipse for optimized high-level modeling and analysis of computer network attack models. In: Godefroid [17], pp. 236–250

    Google Scholar 

  33. Spermann, C., Leuschel, M.: ProB gets nauty: Effective symmetry reduction for B and Z models. In: Proceedings Symposium TASE 2008, Nanjing, China, June 2008, pp. 15–22. IEEE, Los Alamitos (2008)

    Google Scholar 

  34. Turner, E., Leuschel, M., Spermann, C., Butler, M.: Symmetry reduced model checking for B. In: Proceedings Symposium TASE 2007, Shanghai, China, June 2007, pp. 25–34. IEEE, Los Alamitos (2007)

    Google Scholar 

  35. Wachter, B.D., Genon, A., Massart, T., Meuter, C.: The formal design of distributed controllers with \(_{\mbox{d}}\)sl and Spin. Formal Asp. Comput. 17(2), 177–200 (2005)

    Article  MATH  Google Scholar 

  36. Wiegard, H.: A comparison of the model checker ProB with Spin. Master’s thesis, Institut für Informatik, Universität Düsseldorf (to appear, 2008)

    Google Scholar 

  37. Yang, C.H., Dill, D.L.: Validation with guided search of the state space. In: DAC, pp. 599–604 (1998)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut für Informatik, Universität Düsseldorf, Universitätsstr. 1, D-40225, Düsseldorf,  

    Michael Leuschel

Authors
  1. Michael Leuschel
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Egon Börger Michael Butler Jonathan P. Bowen Paul Boca

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Leuschel, M. (2008). The High Road to Formal Validation:. In: Börger, E., Butler, M., Bowen, J.P., Boca, P. (eds) Abstract State Machines, B and Z. ABZ 2008. Lecture Notes in Computer Science, vol 5238. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-87603-8_2

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-87603-8_2

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-87602-1

  • Online ISBN: 978-3-540-87603-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation