Abstract
The formal verification of cyber-physical systems is a challenging task mainly because of the involvement of various factors of continuous nature, such as the analog components or the surrounding environment. Traditional verification methods, such as model checking or automated theorem proving, usually deal with these continuous aspects by using abstracted discrete models. This fact makes cyber-physical system designs error prone, which may lead to disastrous consequences given the safety and financial critical nature of their applications. Leveraging upon the high expressiveness of higher-order logic, we propose to use higher-order-logic theorem proving to analyze continuous models of cyber-physical systems. To facilitate this process, this paper presents the formalization of the solutions of second-order homogeneous linear differential equations. To illustrate the usefulness of our foundational cyber-physical system analysis formalization, we present the formal analysis of a damped harmonic oscillator and a second-order op-amp circuit using the HOL4 theorem prover.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Akella, R., McMillin, B.M.: Model-Checking BNDC Properties in Cyber-Physical Systems. In: Computer Software and Applications Conference, pp. 660–663 (2009)
Baier, C., Katoen, J.: Principles of Model Checking. MIT Press (2008)
Boca, P.P., Bowen, J.P., Siddiqi, J.I.: Formal Methods: State of the Art and New Directions. Springer (2009)
Broman, D., Lee, E.A., Tripakis, S., Toerngren, M.: Viewpoints, Formalisms, Languages, and Tools for Cyber-Physical Systems. In: 6th International Workshop on Multi-Paradigm Modeling (2012)
Brown, C.E.: Automated Reasoning in Higher-order Logic. College Publications (2007)
Bu, L., Wang, Q., Chen, X., Wang, L., Zhang, T., Zhao, J., Li, X.: Towards Online Hybrid Systems Model Checking of Cyber-Physical Systems’ Time-Bounded Short-Run Behavior. SIGBED (2), 7–10 (2011)
Butler, R.W.: Formalization of the Integral Calculus in the PVS Theorem Prover. Journal of Formalized Reasoning 2(1), 1–26 (2009)
Church, A.: A Formulation of the Simple Theory of Types. Journal of Symbolic Logic 5, 56–68 (1940)
Clarke, E.M., Zuliani, P.: Statistical model checking for cyber-physical systems. In: Bultan, T., Hsiung, P.-A. (eds.) ATVA 2011. LNCS, vol. 6996, pp. 1–12. Springer, Heidelberg (2011)
Cruz-Filipe, L.: Constructive Real Analysis: a Type-Theoretical Formalization and Applications. PhD thesis, University of Nijmegen (April 2004)
Daneshbod, Y., Latulippe, J.: A Look at Damped Harmonic Oscillators through the Phase Plane. Teaching Mathematics and its Applications 30(2)
Fitting, M.: First-Order Logic and Automated Theorem Proving. Springer (1996)
Gordon, M.J.C.: Mechanizing Programming Logics in Higher-0rder Logic. In: Current Trends in Hardware Verification and Automated Theorem Proving, pp. 387–439. Springer (1989)
Strang, G.: Calculus, 2nd edn. Wellesley College (2009)
Harrison, J.: Formalized Mathematics. Technical Report 36, Turku Centre for Computer Science (1996)
Harrison, J.: Theorem Proving with the Real Numbers. Springer (1998)
Harrison, J.: A HOL theory of Euclidean space. In: Hurd, J., Melham, T. (eds.) TPHOLs 2005. LNCS, vol. 3603, pp. 114–129. Springer, Heidelberg (2005)
Harrison, J.: Handbook of Practical Logic and Automated Reasoning. Cambridge University Press (2009)
Alexander, K., Sadiku, M.N.O.: Fundamentals of Electric Circuits. McGraw-Hill (2008)
Liu, J., Zhang, L.: QoS Modeling for Cyber-Physical Systems using Aspect-Oriented Approach. In: 2011 Second International Conference on Networking and Distributed Computing (ICNDC), pp. 154–158 (2011)
Zhang, L., Hu, J., Yu, W.: Generating Test Cases for Cyber Physical Systems from Formal Specification, pp. 97–103. Springer (2011)
Mashkoor, A., Hasan, O.: Formal Probabilistic Analysis of Cyber-Physical Transportation Systems. In: Murgante, B., Gervasi, O., Misra, S., Nedjah, N., Rocha, A.M.A.C., Taniar, D., Apduhan, B.O. (eds.) ICCSA 2012, Part III. LNCS, vol. 7335, pp. 419–434. Springer, Heidelberg (2012)
Milner, R.: A Theory of Type Polymorphism in Programming. Journal of Computer and System Sciences 17, 348–375 (1977)
Paulson, L.C.: ML for the Working Programmer. Cambridge University Press (1996)
Rajkumar, R., Lee, I., Sha, L., Stankovic, J.J.: Cyber-Physical Systems: The next Computing Revolution. In: 2010 47th ACM/IEEE Design Automation Conference (DAC), pp. 731–736 (2010)
Shi, J., Wan, J., Yan, H., Suo, H.: A survey of Cyber-Physical Systems. In: Wireless Communications and Signal Processing (WCSP), pp. 1–6 (2011)
Slind, K., Norrish, M.: A Brief Overview of HOL4. In: Mohamed, O.A., Muñoz, C., Tahar, S. (eds.) TPHOLs 2008. LNCS, vol. 5170, pp. 28–32. Springer, Heidelberg (2008)
Thacker, R.A., Jones, K.R., Myers, C.J., Zheng, H.: Automatic Abstraction for Verification of Cyber-Physical Systems. In: Proceedings of the 1st ACM/IEEE International Conference on Cyber-Physical Systems, pp. 12–21. ACM (2010)
Jung, W.: Op Amp Applications Handbook. Newnes (2004)
Zhang, L.: Aspect Oriented Formal Techniques for Cyber Physical Systems. Journal of Software 7(4), 823–834 (2012)
Zill, D.G., Wright, W.S., Cullen, M.R.: Advanced Engineering Mathematics, 4th edn. Jones and Bartlett Learning (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sanwal, M.U., Hasan, O. (2013). Formal Verification of Cyber-Physical Systems: Coping with Continuous Elements. In: Murgante, B., et al. Computational Science and Its Applications – ICCSA 2013. ICCSA 2013. Lecture Notes in Computer Science, vol 7971. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-39637-3_29
Download citation
DOI: https://doi.org/10.1007/978-3-642-39637-3_29
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-39636-6
Online ISBN: 978-3-642-39637-3
eBook Packages: Computer ScienceComputer Science (R0)