Document Open Access Logo

Notions of Conformance Testing for Cyber-Physical Systems: Overview and Roadmap (Invited Paper)

Authors Narges Khakpour, Mohammad Reza Mousavi

PDF
Thumbnail PDF

File

LIPIcs.CONCUR.2015.18.pdf
  • Filesize: 0.57 MB
  • 23 pages

Document Identifiers

Author Details

Narges Khakpour
Mohammad Reza Mousavi

Cite As Get BibTex

Narges Khakpour and Mohammad Reza Mousavi. Notions of Conformance Testing for Cyber-Physical Systems: Overview and Roadmap (Invited Paper). In 26th International Conference on Concurrency Theory (CONCUR 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 42, pp. 18-40, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.CONCUR.2015.18

Abstract

We review and compare three notions of conformance testing for cyber-physical systems. We begin with a review of their underlying semantic models and present conformance-preserving translations between them. We identify the differences in the underlying semantic models and the various design decisions that lead to these substantially different notions of conformance testing. Learning from this exercise, we reflect upon the challenges in designing an "ideal" notion of conformance for cyber-physical systems and sketch a roadmap of future research in this domain.

Subject Classification

Keywords
  • Cyber-physical systems
  • hybrid systems
  • conformance testing
  • model-based testing
  • behavioral pre-orders
  • hybrid input-output conformance testing
  • (tau

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Fides Aarts, Bengt Jonsson, Johan Uijen, and Frits W. Vaandrager. Generating models of infinite-state communication protocols using regular inference with abstraction. Formal Methods in System Design, 46(1):1-41, 2015. Google Scholar
  2. Fides Aarts and Frits W. Vaandrager. Learning I/O automata. In Proceedings of the 21th International Conference on Concurrency Theory (CONCUR 2010), volume 6269 of Lecture Notes in Computer Science, pages 71-85. Springer, 2010. Google Scholar
  3. Houssam Abbas, Bardh Hoxha, Georgios E. Fainekos, J. V. Deshmukh, James Kapinski, and Koichi Ueda. WiP abstract: Conformance testing as falsification for cyber-physical systems. In Proceedings of the ACM/IEEE 5th International Conference on Cyber-Physical Systems (ICCPS 2014), page 211. IEEE CS, 2014. Available online: http://arxiv.org/abs/1401.5200. Google Scholar
  4. Houssam Abbas, Hans Mittelmann, and Georgios E. Fainekos. Formal property verification in a conformance testing framework. In 12th ACM-IEEE International Conference on Formal Methods and Models for System Design (MEMOCODE 2014), pages 155-164. IEEE, 2014. Google Scholar
  5. Samson Abramsky. Observation equivalence as a testing equivalence. Theoretical Computer Science, 53(2-3):225-241, 1987. Google Scholar
  6. Bernhard K. Aichernig, Harald Brandl, Elisabeth Jöbstl, and Willibald Krenn. Model-based mutation testing of hybrid systems. In Revised Selected Papers from the 8th International Symposium on Formal Methods for Components and Objects (FMCO 2009), volume 6286 of Lecture Notes in Computer Science, pages 228-249. Springer, 2010. Google Scholar
  7. Bernhard K. Aichernig, Harald Brandl, and Franz Wotawa. Conformance testing of hybrid systems with qualitative reasoning models. Electronic Notes in Theoretical Computer Science, 253(2):53-69, 2009. Proceedings of Fifth Workshop on Model Based Testing (MBT 2009). Google Scholar
  8. Rajeev Alur. Formal verification of hybrid systems. In Proceedings of the 11th International Conference on Embedded Software (EMSOFT 2011), pages 273-278. ACM, 2011. Google Scholar
  9. Rajeev Alur, Costas Courcoubetis, Nicolas Halbwachs, Thomas A. Henzinger, Pei-Hsin Ho, Xavier Nicollin, Alfredo Olivero, Joseph Sifakis, and Sergio Yovine. The algorithmic analysis of hybrid systems. Theoretical Computer Science, 138(1):3-34, 1995. Google Scholar
  10. Jos C. M. Baeten. A brief history of process algebra. Theoretical Computer Science, 335(2-3):131-146, 2005. Google Scholar
  11. Klaus Bender, Manfred Broy, István Péter, Alexander Pretschner, and Thomas Stauner. Model based development of hybrid systems: Specification, simulation, test case generation. In Modelling, Analysis, and Design of Hybrid Systems, volume 279 of Lecture Notes in Control and Information Sciences, pages 37-51. Springer, 2002. Google Scholar
  12. Nikola Benes, Przemyslaw Daca, Thomas A. Henzinger, Jan Kretínský, and Dejan Nickovic. Complete composition operators for IOCO-testing theory. In Proceedings of the 18th International ACM SIGSOFT Symposium on Component-Based Software Engineering (CBSE 2015), pages 101-110. ACM, 2015. Google Scholar
  13. Harsh Beohar and Mohammad Reza Mousavi. A pre-congruence format for XY-simulation. In Proceedings of the 6th International Conference on Fundamentals of Software Engineering (FSEN 2015), Lecture Notes in Computer Science, 2015. Google Scholar
  14. Harald Brandl, Martin Weiglhofer, and Bernhard K. Aichernig. Automated conformance verification of hybrid systems. In Proceedings of the 10th International Conference on Quality Software (QSIC 2010), pages 3-12. IEEE CS, 2010. Google Scholar
  15. Cécile Braunstein, Anne Elisabeth Haxthausen, Wen-ling Huang, Felix Hübner, Jan Peleska, Uwe Schulze, and Linh Vu Hong. Complete model-based equivalence class testing for the ETCS ceiling speed monitor. In Proceedings of the 16th International Conference on Formal Engineering Methods on Formal Methods and Software Engineering (ICFEM 2014), volume 8829 of Lecture Notes in Computer Science, pages 380-395. Springer, 2014. Google Scholar
  16. Manfred Broy, Bengt Jonsson, Joost-Pieter Katoen, Martin Leucker, and Alexander Pretschner. Model-Based Testing of Reactive Systems: Advanced Lectures, volume 3472 of Lecture Notes in Computer Science. Springer, 2005. Google Scholar
  17. Ana Cavalcanti and Marie-Claude Gaudel. Data flow coverage for circus-based testing. In Proceedings 17th International Conference of the Fundamental Approaches to Software Engineering (FASE 2014), volume 8411 of Lecture Notes in Computer Science, pages 415-429. Springer, 2014. Google Scholar
  18. Pieter Cuijpers. Hybrid Process Algebra. PhD thesis, Department of Computer Science, Eindhoven University of Technology, 2004. Google Scholar
  19. Pieter Cuijpers, Michel Reniers, and Maurice Heemels. Hybrid transition systems. Technical Report CSR-02-12, Department of Computer Science, Eindhoven University of Technology, 2002. Google Scholar
  20. Pieter J. L. Cuijpers and Michel A. Reniers. Lost in translation: Hybrid-time flows vs. real-time transitions. In Proceedings of the 11th International Workshop on Hybrid Systems: Computation and Control (HSCC 2008), volume 4981 of Lecture Notes in Computer Science, pages 116-129. Springer, 2008. Google Scholar
  21. Przemyslaw Daca, Thomas A. Henzinger, Willibald Krenn, and Dejan Nickovic. Compositional specifications for ioco testing. In Proceedings of the 7th IEEE International Conference on Software Testing, Verification and Validation (ICST 2014), pages 373-382. IEEE CS, 2014. Google Scholar
  22. Thao Dang. Model-based testing of hybrid systems. In Justyna Zander, Ina Schieferdecker, and Pieter J. Mosterman, editors, Model-based Testing for Embedded Systems, pages 383-424. CRC Press, 2011. Google Scholar
  23. Thao Dang and Tarik Nahhal. Coverage-guided test generation for continuous and hybrid systems. Formal Methods in System Design, 34(2):183-213, 2009. Google Scholar
  24. Jennifer M. Davoren. On hybrid systems and the modal μ-calculus. In Hybrid Systems V, volume 1567 of Lecture Notes in Computer Science, pages 38-69. Springer, 1999. Google Scholar
  25. Jennifer M. Davoren, Vaughan Coulthard, Nicolas Markey, and Thomas Moor. Non-deterministic temporal logics for general flow systems. In Proceedings of the 7th International Workshop on Hybrid Systems: Computation and Control (HSCC 2004), volume 2993 of Lecture Notes in Computer Science, pages 280-295. Springer, 2004. Google Scholar
  26. Rocco De Nicola and Matthew Hennessy. Testing equivalences for processes. Theoretical Computer Science, 34:83-133, 1984. Google Scholar
  27. Tommaso Dreossi, Thao Dang, Alexandre Donzé, James Kapinski, Xiaoqing Jin, and Jyotirmoy V. Deshmukh. Efficient guiding strategies for testing of temporal properties of hybrid systems. In Proceedings of the 7th International NASA Formal Methods Symposium (NFM 2015), volume 9058 of Lecture Notes in Computer Science, pages 127-142. Springer, 2015. Google Scholar
  28. Georgios E. Fainekos and George J. Pappas. Robustness of temporal logic specifications for continuous-time signals. Theoretical Computer Science, 410(42):4262-4291, 2009. Google Scholar
  29. Carlo A. Furia and Matteo Rossi. On the expressiveness of MTL variants over dense time. In Proceedings of the 5th International Conference on Formal Modeling and Analysis of Timed Systems (FORMATS 2007), volume 4763 of Lecture Notes in Computer Science, pages 163-178. Springer, 2007. Google Scholar
  30. Marie-Claude Gaudel. Testing can be formal, too. In Proceedings of the 6th International Joint Conference on Theory and Practice of Software Development (TAPSOFT 1995), volume 915 of Lecture Notes in Computer Science, pages 82-96. Springer, 1995. Google Scholar
  31. Alessandro Giacalone, Chi-Chang Jou, and Scott A Smolka. Algebraic reasoning for probabilistic concurrent systems. In Proceedings of the IFIP TC2 Working Conference on Programming Concepts and Methods (PROCOMET 1990), pages 443-458. North-Holland, 1990. Google Scholar
  32. Antoine Girard, A. Agung Julius, and George J. Pappas. Approximate simulation relations for hybrid systems. Discrete Event Dynamic Systems, 18(2):163-179, 2008. Google Scholar
  33. Antoine Girard and George J. Pappas. Approximation metrics for discrete and continuous systems. Technical Report MS-CIS-05-10, Dept. of CIS, University of Pennsylvania, 2005. Google Scholar
  34. Antoine Girard and George J. Pappas. Approximate bisimulation: A bridge between computer science and control theory. European Journal of Control, 17(5-6):568-578, 2011. Google Scholar
  35. Antoine Girard and George J. Pappas. A tool prototype for model-based testing of cyber-physical systems. Technical Report CST 2015.090, Contol Systems Group, Dept. of Mechanical Engineering, Eindhoven University of Technology, 2015. Google Scholar
  36. Rafal Goebel, Ricardo G. Sanfelice, and Andrew R. Teel. Hybrid dynamical systems. IEEE Control Systems, 29(2):28-93, 2009. Google Scholar
  37. Robert M. Hierons. Generating complete controllable test suites for distributed testing. IEEE Trans. Software Eng., 41(3):279-293, 2015. Google Scholar
  38. Robert M. Hierons, Kirill Bogdanov, Jonathan P. Bowen, Rance Cleaveland, John Derrick, Jeremy Dick, Marian Gheorghe, Mark Harman, Kalpesh Kapoor, Paul J. Krause, Gerald Lüttgen, Anthony J. H. Simons, Sergiy A. Vilkomir, Martin R. Woodward, and Hussein Zedan. Using formal specifications to support testing. ACM Computing Surveys, 41(2):9:1-9:76, 2009. Google Scholar
  39. Bardh Hoxha, Houssam Abbas, and Georgios E. Fainekos. Using S-TaLiRo on industrial size automotive models. In Proceedings of the Applied Verification for Continuous and Hybrid Systems (ARCH 2014), 2014. Google Scholar
  40. Wen-ling Huang and Jan Peleska. Exhaustive model-based equivalence class testing. In Proceedings of the 25th IFIP WG 6.1 International Conference of Testing Software and Systems (ICTSS 2013), volume 8254 of Lecture Notes in Computer Science, pages 49-64. Springer, 2013. Google Scholar
  41. A. Agung Julius, Georgios E. Fainekos, Madhukar Anand, Insup Lee, and George J. Pappas. Robust test generation and coverage for hybrid systems. In Proceedings of the 10th International Workshop on Hybrid Systems: Computation and Control (HSCC 2007), volume 4416 of Lecture Notes in Computer Science, pages 329-342. Springer, 2007. Google Scholar
  42. Daniel Liberzon. Switching in Systems and Control. Systems & Control: Foundations and Application. Birkhäuser, 2003. Google Scholar
  43. Nancy Lynch, Roberto Segala, and Frits Vaandrager. Hybrid I/O automata. Information and Computation, 185(1):105-157, 2003. Google Scholar
  44. Oded Maler, Zohar Manna, and Amir Pnueli. From timed to hybrid systems. In Proceedings of the REX Workshop on Real-Time: Theory in Practice, volume 600 of Lecture Notes in Computer Science, pages 447-484. Springer, 1992. Google Scholar
  45. Karl Meinke, Fei Niu, and Muddassar A. Sindhu. Learning-based software testing: A tutorial. In International Workshops on Leveraging Applications of Formal Methods, Verification, and Validation, volume 336 of Communications in Computer and Information Science, pages 200-219. Springer, 2012. Google Scholar
  46. Morteza Mohaqeqi, Mohammad Reza Mousavi, and Walid Taha. Conformance testing of cyber-physical systems: A comparative study. In Proceedings of the 14th International Workshop on Automated Verification of Critical Systems (AVOCS 2014), volume 70 of Electronic Communications of the EASST, 2014. Google Scholar
  47. Neda Noroozi. Improving Theories of Input Output Conformance Testing. PhD thesis, Eindhoven University of Technology, The Netherlands, 2015. Google Scholar
  48. Neda Noroozi, Ramtin Khosravi, Mohammad Reza Mousavi, and Tim A. C. Willemse. Synchrony and asynchrony in conformance testing. Software and System Modeling, 14(1):149-172, 2015. Google Scholar
  49. Neda Noroozi, Mohammad Reza Mousavi, and Tim A. C. Willemse. Decomposability in input output conformance testing. In Proceedings of the 8th Workshop on Model-Based Testing (MBT 2013), volume 111 of Electronic Proceedings in Theoretical Computer Science, pages 51-66, 2013. Google Scholar
  50. Jan Willem Polderman and Jan C. Willems. Introduction to Mathematical Systems Theory: A Behavioral Approach, volume 26 of Texts in Applied Mathematics. Springer, 1998. Google Scholar
  51. Adenilso Simao and Alexandre Petrenko. From test purposes to asynchronous test cases. In Third International Conference on Software Testing, Verification, and Validation Workshops (ICSTW 2010), pages 1-10. IEEE CS, 2010. Google Scholar
  52. Paulo Tabuada. Approximate simulation relations and finite abstractions of quantized control systems. In Proceedings of the 10th International Workshop on Hybrid Systems: Computation and Control (HSCC 2007), volume 4416 of Lecture Notes in Computer Science, pages 529-542. Springer, 2007. Google Scholar
  53. Jan Tretmans. A formal Approach to conformance testing. PhD thesis, University of Twente, The Netherlands, 1992. Google Scholar
  54. Jan Tretmans. Model-based testing and some steps towards test-based modelling. In Advanced Lectures of the 11th International School on Formal Methods for the Design of Computer, Communication and Software Systems (SFM 2011), volume 6659 of Lecture Notes in Computer Science, pages 297-326. Springer, 2011. Google Scholar
  55. Jan Tretmans and Louis Verhaard. A queue model relating synchronous and asynchronous communication. In Proceedings of the IFIP Symposium on Protocol Specification, Testing and Verification XII, pages 131-145, Amsterdam, The Netherlands, The Netherlands, 1992. North-Holland Publishing Co. Google Scholar
  56. Franck van Breugel, Claudio Hermida, Michael Makkai, and James Worrell. An accessible approach to behavioural pseudometrics. In Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP 2005), volume 3580 of Lecture Notes in Computer Science, pages 1018-1030. Springer, 2005. Google Scholar
  57. Machiel van der Bijl, Arend Rensink, and Jan Tretmans. Compositional testing with IOCO. In Proceedings of the 3rd International Workshop on Formal Approaches to Testing of Software (FATES 2003), volume 2931 of Lecture Notes in Computer Science, pages 86-100. Springer, 2004. Google Scholar
  58. Arjan van der Schaft and Hans Schumacher. An Introduction to Hybrid Dynamical Systems, volume 251 of Lecture Notes in Control and Information Sciences. Springer, 2000. Google Scholar
  59. Michiel van Osch. Hybrid input-output conformance and test generation. In Formal Approaches to Software Testing and Runtime Verification, volume 4262 of Lecture Notes in Computer Science, pages 70-84. Springer, 2006. Google Scholar
  60. Michiel van Osch. Automated Model-based Testing of Hybrid Systems. PhD thesis, Eindhoven University of Technology, The Netherlands, 2009. Google Scholar
  61. Louis Verhaard, Jan Tretmans, Pim Pars, and Ed Brinksma. On asynchronous testign. In Protocol Test Systems, volume C-11 of IFIP Transaction, pages 55-66, 1992. Google Scholar
  62. Martin Weiglhofer. Automated Software Conformance Testing. PhD thesis, Graz University of Technology, Austria, 2009. Google Scholar
  63. Matthias Woehrle, Kai Lampka, and Lothar Thiele. Segmented state space traversal for conformance testing of cyber-physical systems. In Proceedings of the 9th International Conference on Formal Modeling and Analysis of Timed Systems (FORMATS 2011), volume 6919 of Lecture Notes in Computer Science, pages 193-208. Springer, 2011. Google Scholar
  64. Matthias Woehrle, Kai Lampka, and Lothar Thiele. Conformance testing for cyber-physical systems. ACM Transactions on Embedded Computing Systems, 11(4):84:1-84:23, 2013. Google Scholar
  65. Jun Zhang, Karl Henrik Johansson, John Lygeros, and Shankar Sastry. Zeno hybrid systems. International Journal of Robust and Nonlinear Control, 11(5):435-451, 2001. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact