research-article

Learning-based testing for autonomous systems using spatial and temporal requirements

Authors:

Hojat Khosrowjerdi,

Karl MeinkeAuthors Info & Claims

MASES 2018: Proceedings of the 1st International Workshop on Machine Learning and Software Engineering in Symbiosis

Pages 6 - 15

https://doi.org/10.1145/3243127.3243129

Published: 03 September 2018 Publication History

Abstract

Cooperating cyber-physical systems-of-systems (CO-CPS) such as vehicle platoons, robot teams or drone swarms usually have strict safety requirements on both spatial and temporal behavior. Learning-based testing is a combination of machine learning and model checking that has been successfully used for black-box requirements testing of cyber-physical systems-of-systems. We present an overview of research in progress to apply learning-based testing to evaluate spatio-temporal requirements on autonomous systems-of-systems through modeling and simulation.

References

[1]

K. Meinke and F. Niu, “A learning-based approach to unit testing of numerical software,” in Testing Software and Systems - 22nd IFIP WG 6.1 International Conference, ICTSS 2010, Natal, Brazil, November 8-10, 2010. Proceedings, 2010, pp. 221–235.

Digital Library

[2]

N. Walkinshaw, K. Bogdanov, J. Derrick, and J. Paris, “Increasing functional coverage by inductive testing: a case study,” in Proc. Twenty Second IFIP Int. Conf. on Testing Software and Systems (ICTSS 2010), ser. LNCS, no. 6435.

Digital Library

[3]

Springer, 2010, pp. 126–141.

[4]

L. Feng, S. Lundmark, K. Meinke, F. Niu, M. A. Sindhu, and P. Y. H. Wong, “Case studies in learning-based testing,” in Testing Software and Systems - 25th IFIP WG 6.1 International Conference, ICTSS 2013, Istanbul, Turkey, November 13-15, 2013, Proceedings, 2013, pp. 164–179. {Online}. Available:

[5]

H. Khosrowjerdi, K. Meinke, and A. Rasmusson, “Learning-based testing for safety critical automotive applications,” in Model-Based Safety and Assessment - 5th International Symposium, IMBSA 2017, Trento, Italy, September 11-13, 2017, Proceedings, 2017, pp. 197–211. {Online}. Available:

[6]

K. Meinke, “Learning-based testing of cyber-physical systems-of-systems: A platooning study,” in Computer Performance Engineering - 14th European Workshop, EPEW 2017, Berlin, Germany, September 7-8, 2017, Proceedings, 2017, pp. 135–151. {Online}. Available:

[7]

C. Bergenhem, K. Meinke, and F. Ström, “Quantitative safety analysis of a coordinated emergency brake protocol for vehicle platoons,” in 8th International Symposium On Leveraging Applications of Formal Methods, Verification and Validation, 2018, p. submitted.

[8]

J. Chen, A. G. Cohn, D. Liu, S. Wang, J. OuYang, and Q. Yu, “A survey of qualitative spatial representations,” Knowledge Eng. Review, vol. 30, no. 1, pp. 106–136, 2015. {Online}. Available:

Digital Library

[9]

M. Aiello, I. Pratt-Hartmann, and J. van Benthem, Eds., Handbook of Spatial Logics. Springer, 2007.

Digital Library

[10]

Z. Chaochen, C. A. R. Hoare, and A. P. Ravn, “A calculus of durations,” Inf. Process. Lett., vol. 40, no. 5, pp. 269–276, 1991. {Online}. Available:

[11]

B. C. Moszkowski and Z. Manna, “Reasoning in interval temporal logic,” in Logics of Programs, Workshop, Carnegie Mellon University, Pittsburgh, PA, USA, June 6-8, 1983, Proceedings, 1983, pp. 371–382. {Online}. Available:

Digital Library

[12]

R. L. Schwartz, P. M. Melliar-Smith, and F. H. Vogt, “Interval logic: A higher-level temporal logic for protocol specification,” in Protocol Specification, Testing, and Verification, 1983, pp. 3–18.

[13]

J. van Benthem and G. Bezhanishvili, “Modal logics of space,” in Handbook of Spatial Logics, 2007, pp. 217–298. {Online}. Available: 978-1-4020-5587-4_5

[14]

O. Maler and D. Nickovic, “Monitoring temporal properties of continuous signals,” in Formal Techniques, Modelling and Analysis of Timed and Fault-Tolerant Systems, Joint International Conferences on Formal Modelling and Analysis of Timed Systems, FORMATS 2004 and Formal Techniques in Real-Time and Fault-Tolerant Systems, FTRTFT 2004, Grenoble, France, September 22-24, 2004, Proceedings, 2004, pp. 152–166. {Online}. Available: MASES ’18, September 3, 2018, Montpellier, France Hojat Khosrowjerdi and Karl Meinke

[15]

I. Haghighi, A. Jones, Z. Kong, E. Bartocci, R. Grosu, and C. Belta, “Spatel: a novel spatial-temporal logic and its applications to networked systems,” in Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control, HSCC’15, Seattle, WA, USA, April 14-16, 2015, 2015, pp. 189–198. {Online}. Available:

Digital Library

[16]

E. Bartocci, L. Bortolussi, M. Loreti, and L. Nenzi, “Monitoring mobile and spatially distributed cyber-physical systems,” in Proceedings of the 15th ACM-IEEE International Conference on Formal Methods and Models for System Design, MEMOCODE 2017, Vienna, Austria, September 29 - October 02, 2017, 2017, pp. 146–155. {Online}. Available:

Digital Library

[17]

Z. Shao and J. Liu, “Spatio-temporal hybrid automata for cyber-physical systems,” in Theoretical Aspects of Computing - ICTAC 2013 - 10th International Colloquium, Shanghai, China, September 4-6, 2013. Proceedings, 2013, pp. 337–354. {Online}. Available:

[18]

A. Schäfer, “Axiomatisation and decidability of multi-dimensional duration calculus,” Inf. Comput., vol. 205, no. 1, pp. 25–64, 2007. {Online}. Available:

Digital Library

[19]

L. L. Vissat, M. Loreti, L. Nenzi, J. Hillston, and G. Marion, “Three-valued spatio-temporal logic: A further analysis on spatio-temporal properties of stochastic systems,” in Quantitative Evaluation of Systems - 14th International Conference, QEST 2017, Berlin, Germany, September 5-7, 2017, Proceedings, 2017, pp. 317–332. {Online}. Available:

[20]

B. Xu and Q. Li, “A spatial logic for modeling and verification of collision-free control of vehicles,” in 21st International Conference on Engineering of Complex Computer Systems, ICECCS 2016, Dubai, United Arab Emirates, November 6-8, 2016, 2016, pp. 33–42. {Online}. Available:

[21]

Z. Liu, B. Wu, J. Dai, and H. Lin, “Distributed communication-aware motion planning for multi-agent systems from STL and spatel specifications,” in 56th IEEE Annual Conference on Decision and Control, CDC 2017, Melbourne, Australia, December 12-15, 2017, 2017, pp. 4452–4457. {Online}. Available:

[22]

E. Bartocci, J. V. Deshmukh, A. Donzé, G. E. Fainekos, O. Maler, D. Nickovic, and S. Sankaranarayanan, “Specification-based monitoring of cyber-physical systems: A survey on theory, tools and applications,” in Lectures on Runtime Verification - Introductory and Advanced Topics, 2018, pp. 135–175. {Online}. Available:

[23]

S. E. Shladover, “PATH at 20 - history and major milestones,” IEEE Trans. Intelligent Transportation Systems, vol. 8, no. 4, pp. 584–592, 2007. {Online}. Available:

Digital Library

[24]

S. Linker and M. Hilscher, “Proof theory of a multi-lane spatial logic,” Logical Methods in Computer Science, vol. 11, no. 3, 2015. {Online}. Available:

[25]

M. Hilscher, S. Linker, E. Olderog, and A. P. Ravn, “An abstract model for proving safety of multi-lane traffic manoeuvres,” in Formal Methods and Software Engineering - 13th International Conference on Formal Engineering Methods, ICFEM 2011, Durham, UK, October 26-28, 2011. Proceedings, 2011, pp. 404–419. {Online}. Available:

Digital Library

[26]

W. Damm, H. Hungar, and E. Olderog, “On the verification of cooperating traffic agents,” in Formal Methods for Components and Objects, Second International Symposium, FMCO 2003, Leiden, The Netherlands, November 4-7, 2003, Revised Lectures, 2003, pp. 77–110. {Online}. Available:

[27]

K. G. Larsen, P. Pettersson, and W. Yi, “UPPAAL in a nutshell,” STTT, vol. 1, no. 1-2, pp. 134–152, 1997.

Digital Library

[28]

M. Kamali, S. Linker, and M. Fisher, “Modular verification of vehicle platooning with respect to decisions, space and time,” CoRR, vol. abs/1804.06647, 2018. {Online}. Available: http://arxiv.org/abs/1804.06647

[29]

K. Meinke, F. Niu, and M. Sindhu, Learning-Based Software Testing: A Tutorial. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012, pp. 200–219. {Online}. Available:

[30]

M. Broy, B. Jonsson, J.-P. Katoen, M. Leucker, and A. Pretschner, Model-Based Testing of Reactive Systems: Advanced Lectures (Lecture Notes in Computer Science). Secaucus, NJ, USA: Springer-Verlag New York, Inc., 2005.

Digital Library

[31]

C. De la Higuera, Grammatical inference: learning automata and grammars. Cambridge University Press, 2010.

Digital Library

[32]

D. Angluin, “Learning regular sets from queries and counterexamples,” Inf. Comput., vol. 75, no. 2, pp. 87–106, 1987.

Digital Library

[33]

A. Bennaceur, D. Giannakopoulou, R. Hähnle, and K. Meinke, “Machine learning for dynamic software analysis: Potentials and limits (dagstuhl seminar 16172),” Dagstuhl Reports, vol. 6, no. 4, pp. 161–173, 2016.

[34]

E. M. Clarke, O. Grumberg, and D. A. Peled, Model Checking. The MIT Press, Cambridge, MA, USA, Jan. 1999. {Online}. Available: http://www.amazon.com/ exec/obidos/redirect?tag=citeulike07-20&path=ASIN/0262032708

Digital Library

[35]

K. Meinke and M. A. Sindhu, “Lbtest: A learning-based testing tool for reactive systems,” in Proceedings of the 2013 IEEE Sixth International Conference on Software Testing, Verification and Validation, ser. ICST ’13. Washington, DC, USA: IEEE Computer Society, 2013, pp. 447–454. {Online}. Available:

Digital Library

[36]

M. Fisher, An Introduction to Practical Formal Methods Using Temporal Logic. Wiley, 2011.

Digital Library

[37]

A. Cimatti, E. M. Clarke, E. Giunchiglia, F. Giunchiglia, M. Pistore, M. Roveri, R. Sebastiani, and A. Tacchella, “Nusmv 2: An opensource tool for symbolic model checking,” in Proc. Int. Conf. on Computer-Aided Verification (CAV 2002), 2002.

Digital Library

[38]

R. Cavada, A. Cimatti, M. Dorigatti, A. Griggio, A. Mariotti, A. Micheli, S. Mover, M. Roveri, and S. Tonetta, “The nuxmv symbolic model checker,” in Computer Aided Verification - 26th International Conference, CAV 2014, Held as Part of the Vienna Summer of Logic, VSL 2014, Vienna, Austria, July 18-22, 2014. Proceedings, 2014, pp. 334–342. {Online}. Available:

Digital Library

[39]

L. Feng, S. Lundmark, K. Meinke, F. Niu, M. A. Sindhu, and P. Y. H. Wong, Case Studies in Learning-Based Testing. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013, pp. 164–179. {Online}. Available: 978-3-642-41707-8_11

[40]

L. G. Valiant, “A theory of the learnable,” Commun. ACM, vol. 27, no. 11, pp. 1134–1142, Nov. 1984.

Digital Library

[41]

K. Meinke and P. Nycander, Learning-Based Testing of Distributed Microservice Architectures: Correctness and Fault Injection. Berlin, Heidelberg: Springer Berlin Heidelberg, 2015, pp. 3–10. {Online}. Available: 978-3-662-49224-6_1

Digital Library

[42]

H. Khosrowjerdi, K. Meinke, and A. Rasmusson, “Virtualized-fault Injection Testing: a Machine Learning Approach,” in Proceedings ICST 2018.

[43]

IEEE Press, 2018.

[44]

A. Cimatti, A. Griggio, S. Mover, and S. Tonetta, “Verifying LTL properties of hybrid systems with k-liveness,” in Computer Aided Verification - 26th International Conference, CAV 2014, Held as Part of the Vienna Summer of Logic, VSL 2014, Vienna, Austria, July 18-22, 2014. Proceedings, 2014, pp. 424–440. {Online}. Available:

Digital Library

[45]

R. S. Kakade, “Automatic cruise control system,” Master’s thesis, Indian Institute of Technology, Department of Systems and Control Engineering, Mumbai, 2007.

Cited By

Wan CLiu SXie SLiu YHoffmann HMaire MLu S(2024)Keeper: Automated Testing and Fixing of Machine Learning SoftwareACM Transactions on Software Engineering and Methodology10.1145/367245133:7(1-33)Online publication date: 13-Jun-2024
https://dl.acm.org/doi/10.1145/3672451
Aichernig BTappler MWallner F(2023)Benchmarking Combinations of Learning and Testing Algorithms for Automata LearningFormal Aspects of Computing10.1145/360536036:1(1-37)Online publication date: 21-Jun-2023
https://dl.acm.org/doi/10.1145/3605360
Araujo HMousavi MVarshosaz M(2023)Testing, Validation, and Verification of Robotic and Autonomous Systems: A Systematic ReviewACM Transactions on Software Engineering and Methodology10.1145/354294532:2(1-61)Online publication date: 30-Mar-2023
https://dl.acm.org/doi/10.1145/3542945
Show More Cited By

Recommendations

Use Case Testing: A Constrained Active Machine Learning Approach
Tests and Proofs
Abstract
As a methodology for system design and testing, use cases are well-known and widely used. While current active machine learning (ML) algorithms can effectively automate unit testing, they do not scale up to use case testing of complex systems in ...
Requirements-based test case specification by using information from model construction
AST '08: Proceedings of the 3rd international workshop on Automation of software test

In model-based testing a test case specification is used to determine the set of test cases to be generated automatically. This paper introduces a requirements-based test case specification which uses information gathered by reasoning about the ...
Metamorphic model-based testing of autonomous systems
MET '17: Proceedings of the 2nd International Workshop on Metamorphic Testing

Testing becomes difficult when we cannot easily determine whether or not the system under test delivers the correct result. Autonomous systems are a case in point because it is difficult to determine whether a safety-critical autonomous system's ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MASES 2018: Proceedings of the 1st International Workshop on Machine Learning and Software Engineering in Symbiosis

September 2018

52 pages

ISBN:9781450359726

DOI:10.1145/3243127

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGAI: ACM Special Interest Group on Artificial Intelligence
CNRS: Centre National De La Rechercue Scientifique
SIGSOFT: ACM Special Interest Group on Software Engineering
IEEE-CS: Computer Society

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 September 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ASE '18

Sponsor:

SIGAI
CNRS
SIGSOFT
IEEE-CS

ASE '18: 33rd ACM/IEEE International Conference on Automated Software Engineering

September 3, 2018

Montpellier, France

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
376
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)1

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wan CLiu SXie SLiu YHoffmann HMaire MLu S(2024)Keeper: Automated Testing and Fixing of Machine Learning SoftwareACM Transactions on Software Engineering and Methodology10.1145/367245133:7(1-33)Online publication date: 13-Jun-2024
https://dl.acm.org/doi/10.1145/3672451
Aichernig BTappler MWallner F(2023)Benchmarking Combinations of Learning and Testing Algorithms for Automata LearningFormal Aspects of Computing10.1145/360536036:1(1-37)Online publication date: 21-Jun-2023
https://dl.acm.org/doi/10.1145/3605360
Araujo HMousavi MVarshosaz M(2023)Testing, Validation, and Verification of Robotic and Autonomous Systems: A Systematic ReviewACM Transactions on Software Engineering and Methodology10.1145/354294532:2(1-61)Online publication date: 30-Mar-2023
https://dl.acm.org/doi/10.1145/3542945
Haneef FSindhu M(2023)A Reinforcement Learning Based Grammatical Inference Algorithm Using Block-Based Delta Inverse StrategyIEEE Access10.1109/ACCESS.2023.324212411(12525-12535)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3242124
Haneef FSindhu M(2023) IDLIQ: An Incremental Deterministic Finite Automaton Learning Algorithm Through Inverse Queries for Regular Grammar Inference Big Data10.1089/big.2022.0158Online publication date: 18-May-2023
https://doi.org/10.1089/big.2022.0158
Fontes AGay G(2023)The integration of machine learning into automated test generation: A systematic mapping studySoftware Testing, Verification and Reliability10.1002/stvr.184533:4Online publication date: 2-May-2023
https://doi.org/10.1002/stvr.1845
Munaro TMuntean I(2022)Early Assessment of System-Level Safety Mechanisms through Co-Simulation-based Fault Injection2022 IEEE Intelligent Vehicles Symposium (IV)10.1109/IV51971.2022.9827327(1703-1708)Online publication date: 5-Jun-2022
https://doi.org/10.1109/IV51971.2022.9827327
Parveen RNandan T(2022)Developing a Testing Framework for Cyber-Physical Systems using Gazebo2022 IEEE Workshop on Design Automation for CPS and IoT (DESTION)10.1109/DESTION56136.2022.00015(50-56)Online publication date: May-2022
https://doi.org/10.1109/DESTION56136.2022.00015
Shafiq SMashkoor AMayr-Dorn CEgyed A(2021)A Literature Review of Using Machine Learning in Software Development Life Cycle StagesIEEE Access10.1109/ACCESS.2021.31197469(140896-140920)Online publication date: 2021
https://doi.org/10.1109/ACCESS.2021.3119746
Shijubo JWaga MSuenaga K(2021)Efficient Black-Box Checking via Model Checking with Strengthened SpecificationsRuntime Verification10.1007/978-3-030-88494-9_6(100-120)Online publication date: 6-Oct-2021
https://doi.org/10.1007/978-3-030-88494-9_6
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents