Movatterモバイル変換


[0]ホーム

URL:


Skip to main content

Advertisement

Springer Nature Link
Log in

Direct Support for Model Checking Abstract State Machines by Utilizing Simulation

  • Conference paper

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

Included in the following conference series:

Abstract

This paper presents an approach to model checking abstract state machines (ASMs) without the need for translation of the ASM specification into the modeling language of an existing model checker. Instead, our model checker[mc]square uses the simulation capabilities ofCoreASM to build the state space, thereby directly supporting ASMs and circumventing a possible loss of expressiveness in a translation process. This enables our approach to present counterexamples and witnesses directly as sequences of ASM states and at the same time supports the major features ofCoreASM like distributed ASMs, n-ary functions or extended rule forms. We show the applicability of this approach in a case study that also reveals possible improvements desirable for minimizing the duration needed for building the state space and its memory consumption.

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

Access this chapter

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Börger, E., Päppinghaus, P., Schmid, J.: Report on a Practical Application of ASMs in Software Design. In: Gurevich, Y., Kutter, P., Odersky, M., Thiele, L. (eds.) ASM 2000. LNCS, vol. 1912, pp. 361–366. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  2. Börger, E., Stärk, R.: Abstract State Machines. A Method for High-Level System Design and Analysis. Springer, Heidelberg (2003)

    Google Scholar 

  3. Farahbod, R., Gervasi, V., Glässer, U.: Coreasm: an extensible asm execution engine. Fundamenta Informaticae 77, 71–103 (2007)

    MATH MathSciNet  Google Scholar 

  4. Castillo, G.D.: Towards comprehensive tool support for abstract state machines. In: Hutter, D., Stephan, W., Traverso, P., Ullmann, M. (eds.) FM-Trends 1998. LNCS, vol. 1641, pp. 311–325. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

  5. Winter, K.: Model Checking Abstract State Machines. PhD thesis, Technical University of Berlin, Germany (2001)

    Google Scholar 

  6. Castillo, G.D., Winter, K.: Model checking support for the asm high-level language. In: Graf, S., Schwartzbach, M. (eds.) TACAS 2000. LNCS, vol. 1785, pp. 331–346. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  7. Gargantini, A., Riccobene, E.: ASM-based Testing: coverage criteria and automatic tests generation. In: Moreno-Díaz, R., Quesada-Arencibia, A. (eds.) Formal Methods and Tools for Computer Science (Proceedings of Eurocast 2001), Canary Islands, Spain, Universidad de Las Palmas de Gran Canaria, February 2001, pp. 262–265 (2001)

    Google Scholar 

  8. Tang, C.K.F., Ternovska, E.: Model checking abstract state machines with answer set programming. In: Sutcliffe, G., Voronkov, A. (eds.) LPAR 2005. LNCS (LNAI), vol. 3835, pp. 443–458. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  9. Kardos, M.: An approach to model checking asml specifications. In: Proceedings of the 12th International Workshop on Abstract State Machines, pp. 289–304 (2005)

    Google Scholar 

  10. Ouimet, M., Lundqvist, K.: The timed abstract state machine language: Abstract state machines for real-time system engineering. In: Proceedings ASM 2007 (2007)

    Google Scholar 

  11. Farahbod, R., Glässer, U., Ma, G.: Model checking coreasm specifications. In: Proceedings ASM 2007 (2007)

    Google Scholar 

  12. Ma, G.Z.: Model checking support for coreasm: Model checking distributed abstract state machines using spin. Master’s thesis, Simon Fraser University, Burnaby, Canada (2007)

    Google Scholar 

  13. Schlich, B., Kowalewski, S.: [MC]SQUARE: A model checker for microcontroller code. In: Margaria, T., Philippou, A., Steffen, B. (eds.) Proc. 2nd Int. Symp. Leveraging Applications of Formal Methods, Verification and Validation (IEEE-ISoLA). IEEE Computer Society, Los Alamitos (to appear, 2006)

    Google Scholar 

  14. Schlich, B., Salewski, F., Kowalewski, S.: Applying model checking to an automotive microcontroller application. In: Proc. IEEE 2nd Int. Symp. Industrial Embedded Systems (SIES), pp. 209–216. IEEE, Los Alamitos (2007)

    Chapter  Google Scholar 

  15. Vergauwen, B., Lewi, J.: A linear local model checking algorithm for ctl. In: Best, E. (ed.) CONCUR 1993. LNCS, vol. 715, pp. 447–461. Springer, Heidelberg (1993)

    Google Scholar 

  16. Heljanko, K.: Model checking the branching time temporal logic ctl. Research Report A45, Helsinki University of Technology, Digital Systems Laboratory, Espoo, Finland (May 1997)

    Google Scholar 

  17. Schlich, B., Kowalewski, S.: An extendable architecture for model checking hardware-specific automotive microcontroller code. In: Schnieder, E., Tarnai, G. (eds.) Proc. 6th Symp. Formal Methods for Automation and Safety in Railway and Automotive Systems (FORMS/FORMAT), GZVB, Braunschweig, Germany, pp. 201–212 (2007)

    Google Scholar 

  18. Dijkstra, E., Feijen, W., Gasteren, A.: Derivation of a Termination Detection Algorithm for Distributed Computations. Information Processing Letters 16(5), 217–219 (1983)

    Article MathSciNet  Google Scholar 

  19. Kuskin, J., Ofelt, D., Heinrich, M., Heinlein, J., Simoni, R., Gharachorloo, K., Chapin, J., Nakahira, D., Baxter, J., Horowitz, M., et al.: The Stanford FLASH multiprocessor. In: Kuskin, J., Ofelt, D., Heinrich, M., Heinlein, J., Simoni, R., Gharachorloo, K., Chapin, J., Nakahira, D., Baxter, J., Horowitz, M., et al. (eds.) Proceedings the 21st Annual International Symposium on Computer Architecture, pp. 302–313 (1994)

    Google Scholar 

  20. Eschbach, R.: A Termination Detection Algorithm: Specification and Verification. In: Wing, J., Woodcock, J., Davies, J. (eds.) FM 1999. LNCS, vol. 1709, pp. 1720–1737. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Embedded Software Laboratory, RWTH Aachen, Ahornstr. 55, 52074, Aachen, Germany

    Jörg Beckers, Daniel Klünder, Stefan Kowalewski & Bastian Schlich

Authors
  1. Jörg Beckers

    You can also search for this author inPubMed Google Scholar

  2. Daniel Klünder

    You can also search for this author inPubMed Google Scholar

  3. Stefan Kowalewski

    You can also search for this author inPubMed Google Scholar

  4. Bastian Schlich

    You can also search for this author inPubMed Google Scholar

Editor information

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

Rights and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Beckers, J., Klünder, D., Kowalewski, S., Schlich, B. (2008). Direct Support for Model Checking Abstract State Machines by Utilizing Simulation. 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_10

Download citation

Publish with us


[8]ページ先頭

©2009-2025 Movatter.jp