From Model Checking to a Temporal Proof for Partial Models | SpringerLink
Skip to main content
Springer Nature Link
Log in

From Model Checking to a Temporal Proof for Partial Models

  • Conference paper
  • First Online:
Software Engineering and Formal Methods (SEFM 2017)

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

Included in the following conference series:

Abstract

Three-valued model checking has been proposed to support verification when some portions of the model are unspecified. Given a formal property, the model checker returns true if the property is satisfied, false and a violating behavior if it is not, maybe and a possibly violating behavior if it is possibly satisfied, i.e., its satisfaction may depend on how the unspecified parts are refined. Model checking, however, does not explain the reasons why a property holds, or possibly holds. Theorem proving can instead do it by providing a formal proof that explains why a property holds, or possibly holds in a system. Integration of theorem proving with model checking has only been studied for classical two-valued logic – hence, for fully specified models. This paper proposes a unified approach that enriches three-valued model checking with theorem proving to generate proofs which explain why true and maybe results are returned.

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

Similar content being viewed by others

Notes

  1. 1.

    In [6] the procedure is presented for PML but is valid also for LTL (see [6, 11, 13]).

References

  1. Alavi, H., Avrunin, G., Corbett, J., Dillon, L., Dwyer, M., Pasareanu, C.: Spec patterns (2017). http://patterns.projects.cs.ksu.edu/documentation/patterns/ltl.shtml

  2. Antonik, A., Huth, M.: Efficient patterns for model checking partial state spaces in CTL \(\cap \) LTL. Electron. Notes Theor. Comput. Sci. 158, 41–57 (2006)

    Article  Google Scholar 

  3. Arcaini, P., Bonfanti, S., Gargantini, A., Mashkoor, A., Riccobene, E.: Formal validation and verification of a medical software critical component. In: Formal Methods and Models for Codesign, pp. 80–89. IEEE (2015)

    Google Scholar 

  4. Bernasconi, A., Menghi, C., Spoletini, P., Zuck, L., Ghezzi, C.: From model checking to a temporal proof for partial models: preliminary example (2017). arXiv preprint arXiv:1706.02701

  5. Bruns, G., Godefroid, P.: Model checking partial state spaces with 3-valued temporal logics. In: Halbwachs, N., Peled, D. (eds.) CAV 1999. LNCS, vol. 1633, pp. 274–287. Springer, Heidelberg (1999). doi:10.1007/3-540-48683-6_25

    Chapter  Google Scholar 

  6. Bruns, G., Godefroid, P.: Generalized model checking: reasoning about partial state spaces. In: Palamidessi, C. (ed.) CONCUR 2000. LNCS, vol. 1877, pp. 168–182. Springer, Heidelberg (2000). doi:10.1007/3-540-44618-4_14

    Chapter  Google Scholar 

  7. Bruns, G., Godefroid, P.: Model checking with multi-valued logics. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 281–293. Springer, Heidelberg (2004). doi:10.1007/978-3-540-27836-8_26

    Chapter  Google Scholar 

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

    Google Scholar 

  9. Dwyer, M.B., Avrunin, G.S., Corbett, J.C.: Property specification patterns for finite-state verification. In: Proceedings of the Second Workshop on Formal Methods in Software Practice, pp. 7–15. ACM (1998)

    Google Scholar 

  10. Gerth, R., Peled, D., Vardi, M.Y., Wolper, P.: Simple on-the-fly automatic verification of linear temporal logic. In: Dembiński, P., Średniawa, M. (eds.) Protocol Specification, Testing and Verification, pp. 3–18. Springer, Boston (1996). doi:10.1007/978-0-387-34892-6_1

    Chapter  Google Scholar 

  11. Godefroid, P., Huth, M.: Model checking vs. generalized model checking: semantic minimizations for temporal logics. In: Logic in Computer Science, pp. 158–167. IEEE Computer Society (2005)

    Google Scholar 

  12. Godefroid, P., Huth, M., Jagadeesan, R.: Abstraction-based model checking using modal transition systems. In: Larsen, K.G., Nielsen, M. (eds.) CONCUR 2001. LNCS, vol. 2154, pp. 426–440. Springer, Heidelberg (2001). doi:10.1007/3-540-44685-0_29

    Chapter  Google Scholar 

  13. Godefroid, P., Piterman, N.: LTL generalized model checking revisited. Int. J. Softw. Tools Technol. Transfer 13(6), 571–584 (2011)

    Article  Google Scholar 

  14. Graf, S., Saidi, H.: Construction of abstract state graphs with PVS. In: Grumberg, O. (ed.) CAV 1997. LNCS, vol. 1254, pp. 72–83. Springer, Heidelberg (1997). doi:10.1007/3-540-63166-6_10

    Chapter  Google Scholar 

  15. Gurfinkel, A., Chechik, M.: Multi-valued model checking via classical model checking. In: Amadio, R., Lugiez, D. (eds.) CONCUR 2003. LNCS, vol. 2761, pp. 266–280. Springer, Heidelberg (2003). doi:10.1007/978-3-540-45187-7_18

    Chapter  Google Scholar 

  16. Gurfinkel, A., Chechik, M.: How thorough is thorough enough? In: Borrione, D., Paul, W. (eds.) CHARME 2005. LNCS, vol. 3725, pp. 65–80. Springer, Heidelberg (2005). doi:10.1007/11560548_8

    Chapter  Google Scholar 

  17. Larsen, K.G., Thomsen, B.: A modal process logic. In: Logic in Computer Science, pp. 203–210. IEEE (1988)

    Google Scholar 

  18. Manna, Z., Pnueli, A.: The Temporal Logic of Reactive and Concurrent Systems: Specification. Springer, New York (1992)

    Book  Google Scholar 

  19. Menghi, C., Spoletini, P., Ghezzi, C.: Dealing with incompleteness in automata-based model checking. In: Fitzgerald, J., Heitmeyer, C., Gnesi, S., Philippou, A. (eds.) FM 2016. LNCS, vol. 9995, pp. 531–550. Springer, Cham (2016). doi:10.1007/978-3-319-48989-6_32

    Chapter  Google Scholar 

  20. Namjoshi, K.S.: Certifying model checkers. In: Berry, G., Comon, H., Finkel, A. (eds.) CAV 2001. LNCS, vol. 2102, pp. 2–13. Springer, Heidelberg (2001). doi:10.1007/3-540-44585-4_2

    Chapter  Google Scholar 

  21. Peled, D., Pnueli, A., Zuck, L.: From falsification to verification. In: Hariharan, R., Vinay, V., Mukund, M. (eds.) FSTTCS 2001. LNCS, vol. 2245, pp. 292–304. Springer, Heidelberg (2001). doi:10.1007/3-540-45294-X_25

    Chapter  Google Scholar 

  22. Peled, D., Zuck, L.: From model checking to a temporal proof. In: Dwyer, M. (ed.) SPIN 2001. LNCS, vol. 2057, pp. 1–14. Springer, Heidelberg (2001). doi:10.1007/3-540-45139-0_1

    Chapter  MATH  Google Scholar 

  23. Pnueli, A.: The temporal logic of programs. In: Foundations of Computer Science, pp. 46–57. IEEE (1977)

    Google Scholar 

  24. Rajan, S., Shankar, N., Srivas, M.K.: An integration of model checking with automated proof checking. In: Wolper, P. (ed.) CAV 1995. LNCS, vol. 939, pp. 84–97. Springer, Heidelberg (1995). doi:10.1007/3-540-60045-0_42

    Chapter  Google Scholar 

  25. Tan, L., Cleaveland, R.: Evidence-based model checking. In: Brinksma, E., Larsen, K.G. (eds.) CAV 2002. LNCS, vol. 2404, pp. 455–470. Springer, Heidelberg (2002). doi:10.1007/3-540-45657-0_37

    Chapter  Google Scholar 

  26. Woodcock, J., Larsen, P.G., Bicarregui, J., Fitzgerald, J.S.: Formal methods: practice and experience. ACM Comput. Surv. 41(4) (2009)

    Article  Google Scholar 

Download references

Acknowledgments

Research partly supported from the EU H2020 Research and Innovation Programme under GA No. 731869 (Co4Robots).

Author information

Authors and Affiliations

  1. DEIB - Politecnico di Milano, Milan, Italy

    Anna Bernasconi & Carlo Ghezzi

  2. Chalmers University of Technology, Gothenburg, Sweden

    Claudio Menghi

  3. University of Gothenburg, Gothenburg, Sweden

    Claudio Menghi

  4. Kennesaw State University, Marietta, Georgia

    Paola Spoletini

  5. University of Illinois at Chicago, Chicago, USA

    Lenore D. Zuck

Authors
  1. Anna Bernasconi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Claudio Menghi
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Paola Spoletini
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Lenore D. Zuck
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Carlo Ghezzi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Anna Bernasconi or Claudio Menghi .

Editor information

Editors and Affiliations

  1. University of Trento, Trento, Italy

    Alessandro Cimatti

  2. Mälardalen University, Västerås, Sweden

    Marjan Sirjani

Rights and permissions

Reprints and permissions

Copyright information

© 2017 Springer International Publishing AG

About this paper

Cite this paper

Bernasconi, A., Menghi, C., Spoletini, P., Zuck, L.D., Ghezzi, C. (2017). From Model Checking to a Temporal Proof for Partial Models. In: Cimatti, A., Sirjani, M. (eds) Software Engineering and Formal Methods. SEFM 2017. Lecture Notes in Computer Science(), vol 10469. Springer, Cham. https://doi.org/10.1007/978-3-319-66197-1_4

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-66197-1_4

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-66196-4

  • Online ISBN: 978-3-319-66197-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation