Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/3365365.3382193acmconferencesArticle/Chapter ViewAbstractPublication PagescpsweekConference Proceedingsconference-collections
research-article
Public Access

Falsification of cyber-physical systems with robustness-guided black-box checking

Published: 22 April 2020 Publication History

Abstract

For exhaustive formal verification, industrial-scale cyber-physical systems (CPSs) are often too large and complex, and lightweight alternatives (e.g., monitoring and testing) have attracted the attention of both industrial practitioners and academic researchers. Falsification is one popular testing method of CPSs utilizing stochastic optimization. In state-of-the-art falsification methods, the result of the previous falsification trials is discarded, and we always try to falsify without any prior knowledge. To concisely memorize such prior information on the CPS model and exploit it, we employ Black-box checking (BBC), which is a combination of automata learning and model checking. Moreover, we enhance BBC using the robust semantics of STL formulas, which is the essential gadget in falsification. Our experiment results suggest that our robustness-guided BBC outperforms a state-of-the-art falsification tool.

References

[1]
Fides Aarts, Bengt Jonsson, Johan Uijen, and Frits W. Vaandrager. 2015. Generating models of infinite-state communication protocols using regular inference with abstraction. Formal Methods in System Design 46, 1 (2015), 1--41.
[2]
Takumi Akazaki and Ichiro Hasuo. 2015. Time Robustness in MTL and Expressivity in Hybrid System Falsification. In Computer Aided Verification - 27th International Conference, CAV 2015, San Francisco, CA, USA, July 18--24, 2015, Proceedings, Part II (Lecture Notes in Computer Science), Daniel Kroening and Corina S. Pasareanu (Eds.), Vol. 9207. Springer, 356--374.
[3]
Takumi Akazaki, Shuang Liu, Yoriyuki Yamagata, Yihai Duan, and Jianye Hao. 2018. Falsification of Cyber-Physical Systems Using Deep Reinforcement Learning. In Formal Methods - 22nd International Symposium, FM 2018, Held as Part of the Federated Logic Conference, FloC 2018, Oxford, UK, July 15--17, 2018, Proceedings (Lecture Notes in Computer Science), Klaus Havelund, Jan Peleska, Bill Roscoe, and Erik P. de Vink (Eds.), Vol. 10951. Springer, 456--465.
[4]
Dana Angluin. 1987. Learning Regular Sets from Queries and Counterexamples. Inf. Comput. 75, 2 (1987), 87--106.
[5]
Yashwanth Annpureddy, Che Liu, Georgios E. Fainekos, and Sriram Sankaranarayanan. 2011. S-TaLiRo: A Tool for Temporal Logic Falsification for Hybrid Systems. In Tools and Algorithms for the Construction and Analysis of Systems - 17th International Conference, TACAS 2011, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2011, Saarbrücken, Germany, March 26-April 3, 2011. Proceedings (Lecture Notes in Computer Science), Parosh Aziz Abdulla and K. Rustan M. Leino (Eds.), Vol. 6605. Springer, 254--257.
[6]
Anne Auger and Nikolaus Hansen. 2005. A restart CMA evolution strategy with increasing population size. In Proceedings of the IEEE Congress on Evolutionary Computation, CEC 2005, 2--4 September 2005, Edinburgh, UK. IEEE, 1769--1776.
[7]
Christel Baier and Joost-Pieter Katoen. 2008. Principles of model checking. MIT Press.
[8]
Amel Bennaceur, Reiner Hähnle, and Karl Meinke (Eds.). 2018. Machine Learning for Dynamic Software Analysis: Potentials and Limits - International Dagstuhl Seminar 16172, Dagstuhl Castle, Germany, April 24--27, 2016, Revised Papers. Lecture Notes in Computer Science, Vol. 11026. Springer.
[9]
Marco Bernardo and Valérie Issarny (Eds.). 2011. Formal Methods for Eternal Networked Software Systems - 11th International School on Formal Methods for the Design of Computer, Communication and Software Systems, SFM 2011, Bertinoro, Italy, June 13--18, 2011. Advanced Lectures. Lecture Notes in Computer Science, Vol. 6659. Springer.
[10]
Eric Brochu, Vlad M. Cora, and Nando de Freitas. 2010. A Tutorial on Bayesian Optimization of Expensive Cost Functions, with Application to Active User Modeling and Hierarchical Reinforcement Learning. CoRR abs/1012.2599 (2010). arXiv:1012.2599 http://arxiv.org/abs/1012.2599
[11]
Tsun S. Chow. 1978. Testing Software Design Modeled by Finite-State Machines. IEEE Trans. Software Eng. 4, 3 (1978), 178--187.
[12]
Marcelo d'Amorim and Grigore Rosu. 2005. Efficient Monitoring of omega-Languages. In Computer Aided Verification, 17th International Conference, CAV 2005, Edinburgh, Scotland, UK, July 6--10, 2005, Proceedings (Lecture Notes in Computer Science), Kousha Etessami and Sriram K. Rajamani (Eds.), Vol. 3576. Springer, 364--378.
[13]
Jyotirmoy V. Deshmukh, Alexandre Donzé, Shromona Ghosh, Xiaoqing Jin, Garvit Juniwal, and Sanjit A. Seshia. 2017. Robust online monitoring of signal temporal logic. Formal Methods in System Design 51, 1 (2017), 5--30.
[14]
Jyotirmoy V. Deshmukh, Marko Horvat, Xiaoqing Jin, Rupak Majumdar, and Vinayak S. Prabhu. 2017. Testing Cyber-Physical Systems through Bayesian Optimization. ACM Trans. Embedded Comput. Syst. 16, 5 (2017), 170:1--170:18.
[15]
Adel Dokhanchi, Shakiba Yaghoubi, Bardh Hoxha, and Georgios E. Fainekos. 2017. Vacuity aware falsification for MTL request-response specifications. In 13th IEEE Conference on Automation Science and Engineering, CASE 2017, Xi'an, China, August 20--23, 2017. IEEE, 1332--1337.
[16]
Alexandre Donzé. 2010. Breach, A Toolbox for Verification and Parameter Synthesis of Hybrid Systems. In Computer Aided Verification, 22nd International Conference, CAV 2010, Edinburgh, UK, July 15--19, 2010. Proceedings (Lecture Notes in Computer Science), Tayssir Touili, Byron Cook, and Paul B. Jackson (Eds.), Vol. 6174. Springer, 167--170.
[17]
Alexandre Donzé and Oded Maler. 2010. Robust Satisfaction of Temporal Logic over Real-Valued Signals. In Formal Modeling and Analysis of Timed Systems - 8th International Conference, FORMATS 2010, Klosterneuburg, Austria, September 8--10, 2010. Proceedings (Lecture Notes in Computer Science), Krishnendu Chatterjee and Thomas A. Henzinger (Eds.), Vol. 6246. Springer, 92--106.
[18]
Tommaso Dreossi, Alexandre Donzé, and Sanjit A. Seshia. 2017. Compositional Falsification of Cyber-Physical Systems with Machine Learning Components. In NASA Formal Methods - 9th International Symposium, NFM 2017, Moffett Field, CA, USA, May 16--18, 2017, Proceedings (Lecture Notes in Computer Science), Clark W. Barrett, Misty Davies, and Temesghen Kahsai (Eds.), Vol. 10227. 357--372.
[19]
Juan José Durillo and Antonio J. Nebro. 2011. jMetal: A Java framework for multi-objective optimization. Advances in Engineering Software 42, 10 (2011), 760--771.
[20]
Gidon Ernst, Paolo Arcaini, Alexandre Donzé, Georgios Fainekos, Logan Mathesen, Giulia Pedrielli, Shakiba Yaghoubi, Yoriyuki Yamagata, and Zhenya Zhang. 2019. ARCH-COMP 2019 Category Report: Falsification, See [22], 129--140. http://www.easychair.org/publications/paper/5VWq
[21]
Georgios E. Fainekos and George J. Pappas. 2009. Robustness of temporal logic specifications for continuous-time signals. Theor. Comput. Sci. 410, 42 (2009), 4262--4291.
[22]
Goran Frehse and Matthias Althoff (Eds.). 2019. ARCH19. 6th International Workshop on Applied Verification of Continuous and Hybrid Systemsi, part of CPS-IoT Week 2019, Montreal, QC, Canada, April 15, 2019. EPiC Series in Computing, Vol. 61. EasyChair. http://www.easychair.org/publications/volume/ARCH19
[23]
Susumu Fujiwara, Gregor von Bochmann, Ferhat Khendek, Mokhtar Amalou, and Abderrazak Ghedamsi. 1991. Test Selection Based on Finite State Models. IEEE Trans. Software Eng. 17, 6 (1991), 591--603.
[24]
Alex Groce, Doron A. Peled, and Mihalis Yannakakis. 2006. Adaptive Model Checking. Logic Journal of the IGPL 14, 5 (2006), 729--744.
[25]
Falk Howar and Bernhard Steffen. 2018. Active Automata Learning in Practice - An Annotated Bibliography of the Years 2011 to 2016, See [8], 123--148.
[26]
Bardh Hoxha, Houssam Abbas, and Georgios E. Fainekos. 2014. Benchmarks for Temporal Logic Requirements for Automotive Systems. In 1st and 2nd International Workshop on Applied veRification for Continuous and Hybrid Systems, ARCH@CPSWeek 2014, Berlin, Germany, April 14, 2014 / ARCH@CPSWeek 2015, Seattle, WA, USA, April 13, 2015. (EPiC Series in Computing), Goran Frehse and Matthias Althoff (Eds.), Vol. 34. EasyChair, 25--30. http://www.easychair.org/publications/paper/Benchmarks_for_Temporal_Logic_Requirements_for_Automotive_Systems
[27]
Malte Isberner, Falk Howar, and Bernhard Steffen. 2014. The TTT Algorithm: A Redundancy-Free Approach to Active Automata Learning. In Runtime Verification - 5th International Conference, RV 2014, Toronto, ON, Canada, September 22--25, 2014. Proceedings (Lecture Notes in Computer Science), Borzoo Bonakdarpour and Scott A. Smolka (Eds.), Vol. 8734. Springer, 307--322.
[28]
Malte Isberner, Falk Howar, and Bernhard Steffen. 2015. The Open-Source LearnLib - A Framework for Active Automata Learning. In Computer Aided Verification - 27th International Conference, CAV 2015, San Francisco, CA, USA, July 18--24, 2015, Proceedings, Part I (Lecture Notes in Computer Science), Daniel Kroening and Corina S. Pasareanu (Eds.), Vol. 9206. Springer, 487--495.
[29]
Gijs Kant, Alfons Laarman, Jeroen Meijer, Jaco van de Pol, Stefan Blom, and Tom van Dijk. 2015. LTSmin: High-Performance Language-Independent Model Checking. In Tools and Algorithms for the Construction and Analysis of Systems - 21st International Conference, TACAS 2015, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2015, London, UK, April 11--18, 2015. Proceedings (Lecture Notes in Computer Science), Christel Baier and Cesare Tinelli (Eds.), Vol. 9035. Springer, 692--707.
[30]
Koki Kato, Fuyuki Ishikawa, and Shinichi Honiden. 2018. Falsification of Cyber-Physical Systems with Reinforcement Learning. In 3rd Workshop on Monitoring and Testing of Cyber-Physical Systems, MT@CPSWeek 2018, Porto, Portugal, April 10, 2018. IEEE, 5--6.
[31]
Hojat Khosrowjerdi and Karl Meinke. 2018. Learning-based testing for autonomous systems using spatial and temporal requirements. In Proceedings of the 1st International Workshop on Machine Learning and Software Engineering in Symbiosis, MASES@ASE 2018, Montpellier, France, September 3, 2018, Gilles Perrouin, Mathieu Acher, Maxime Cordy, and Xavier Devroey (Eds.). ACM, 6--15.
[32]
Hojat Khosrowjerdi, Karl Meinke, and Andreas Rasmusson. 2017. 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 (Lecture Notes in Computer Science), Marco Bozzano and Yiannis Papadopoulos (Eds.), Vol. 10437. Springer, 197--211.
[33]
Scott Kirkpatrick, C Daniel Gelatt, and Mario P Vecchi. 1983. Optimization by simulated annealing. science 220, 4598 (1983), 671--680.
[34]
John R. Koza. 1993. Genetic programming - on the programming of computers by means of natural selection. MIT Press.
[35]
Orna Kupferman and Moshe Y. Vardi. 2001. Model Checking of Safety Properties. Formal Methods in System Design 19, 3 (2001), 291--314.
[36]
Marco A Luersen and Rodolphe Le Riche. 2004. Globalized Nelder-Mead method for engineering optimization. Computers & structures 82, 23-26 (2004), 2251--2260.
[37]
Oded Maler and Dejan Nickovic. 2004. 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 (Lecture Notes in Computer Science), Yassine Lakhnech and Sergio Yovine (Eds.), Vol. 3253. Springer, 152--166.
[38]
Jeroen Meijer and Jaco van de Pol. 2019. Sound black-box checking in the LearnLib. ISSE 15, 3-4 (2019), 267--287.
[39]
Karl Meinke. 2017. 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 (Lecture Notes in Computer Science), Philipp Reinecke and Antinisca Di Marco (Eds.), Vol. 10497. Springer, 135--151.
[40]
Karl Meinke. 2018. Learning-Based Testing: Recent Progress and Future Prospects, See [8], 53--73.
[41]
Karl Meinke and Muddassar A. Sindhu. 2013. LBTest: A Learning-Based Testing Tool for Reactive Systems. In Sixth IEEE International Conference on Software Testing, Verification and Validation, ICST 2013, Luxembourg, Luxembourg, March 18--22, 2013. IEEE Computer Society, 447--454.
[42]
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin A. Riedmiller, Andreas Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. 2015. Human-level control through deep reinforcement learning. Nature 518, 7540 (2015), 529--533.
[43]
Truong Nghiem, Sriram Sankaranarayanan, Georgios E. Fainekos, Franjo Ivancic, Aarti Gupta, and George J. Pappas. 2010. Monte-carlo techniques for falsification of temporal properties of non-linear hybrid systems. In Proceedings of the 13th ACM International Conference on Hybrid Systems: Computation and Control, HSCC 2010, Stockholm, Sweden, April 12--15, 2010, Karl Henrik Johansson and Wang Yi (Eds.). ACM, 211--220.
[44]
Doron A. Peled, Moshe Y. Vardi, and Mihalis Yannakakis. 2002. Black Box Checking. Journal of Automata, Languages and Combinatorics 7, 2 (2002), 225--246.
[45]
Amir Pnueli. 1977. The Temporal Logic of Programs. In 18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October - 1 November 1977. IEEE Computer Society, 46--57.
[46]
Hendrik Roehm, Jens Oehlerking, Matthias Woehrle, and Matthias Althoff. 2019. Model Conformance for Cyber-Physical Systems: A Survey. TCPS 3, 3 (2019), 30:1--30:26.
[47]
Bernhard Steffen, Falk Howar, and Maik Merten. 2011. Introduction to Active Automata Learning from a Practical Perspective, See [9], 256--296.
[48]
M. P. Vasilevskii. 1973. Failure diagnosis of automata. Cybernetics 9, 4 (01 Jul 1973), 653--665.
[49]
Shakiba Yaghoubi and Georgios Fainekos. 2018. Falsification of Temporal Logic Requirements Using Gradient Based Local Search in Space and Time. In 6th IFAC Conference on Analysis and Design of Hybrid Systems, ADHS 2018, Oxford, UK, July 11--13, 2018 (IFAC-PapersOnLine), Alessandro Abate, Antoine Girard, and Maurice Heemels (Eds.), Vol. 51. Elsevier, 103--108.
[50]
Zhenya Zhang, Gidon Ernst, Sean Sedwards, Paolo Arcaini, and Ichiro Hasuo. 2018. Two-Layered Falsification of Hybrid Systems Guided by Monte Carlo Tree Search. IEEE Trans. on CAD of Integrated Circuits and Systems 37, 11 (2018), 2894--2905.
[51]
Zhenya Zhang, Ichiro Hasuo, and Paolo Arcaini. 2019. Multi-armed Bandits for Boolean Connectives in Hybrid System Falsification. In Computer Aided Verification - 31st International Conference, CAV 2019, New York City, NY, USA, July 15--18, 2019, Proceedings, Part I (Lecture Notes in Computer Science), Isil Dillig and Serdar Tasiran (Eds.), Vol. 11561. Springer, 401--420.

Cited By

View all
  • (2024)Falsification using Reachability of Surrogate Koopman ModelsProceedings of the 27th ACM International Conference on Hybrid Systems: Computation and Control10.1145/3641513.3650141(1-13)Online publication date: 14-May-2024
  • (2024)Data-Driven Falsification of Cyber-Physical SystemsProceedings of the 17th Innovations in Software Engineering Conference10.1145/3641399.3641401(1-5)Online publication date: 22-Feb-2024
  • (2024)Simulation-Based Testing of Simulink Models With Test Sequence and Test Assessment BlocksIEEE Transactions on Software Engineering10.1109/TSE.2023.334375350:2(239-257)Online publication date: Feb-2024
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
HSCC '20: Proceedings of the 23rd International Conference on Hybrid Systems: Computation and Control
April 2020
324 pages
ISBN:9781450370189
DOI:10.1145/3365365
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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication Notes

Badge change: Article originally badged under Version 1.0 guidelines https://www.acm.org/publications/policies/artifact-review-badging

Publication History

Published: 22 April 2020

Permissions

Request permissions for this article.

Check for updates

Badges

Author Tags

  1. automata learning
  2. black-box checking
  3. cyber-physical systems
  4. falsification
  5. model checking
  6. robust semantics
  7. signal temporal logic

Qualifiers

  • Research-article

Funding Sources

Conference

HSCC '20
Sponsor:

Acceptance Rates

Overall Acceptance Rate 153 of 373 submissions, 41%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)183
  • Downloads (Last 6 weeks)22
Reflects downloads up to 19 Nov 2024

Other Metrics

Citations

Cited By

View all
  • (2024)Falsification using Reachability of Surrogate Koopman ModelsProceedings of the 27th ACM International Conference on Hybrid Systems: Computation and Control10.1145/3641513.3650141(1-13)Online publication date: 14-May-2024
  • (2024)Data-Driven Falsification of Cyber-Physical SystemsProceedings of the 17th Innovations in Software Engineering Conference10.1145/3641399.3641401(1-5)Online publication date: 22-Feb-2024
  • (2024)Simulation-Based Testing of Simulink Models With Test Sequence and Test Assessment BlocksIEEE Transactions on Software Engineering10.1109/TSE.2023.334375350:2(239-257)Online publication date: Feb-2024
  • (2024)Part-X: A Family of Stochastic Algorithms for Search-Based Test Generation With Probabilistic GuaranteesIEEE Transactions on Automation Science and Engineering10.1109/TASE.2023.329798421:3(4504-4525)Online publication date: Jul-2024
  • (2024)Dynamic, Multi-objective Specification and Falsification of Autonomous CPSRuntime Verification10.1007/978-3-031-74234-7_3(40-58)Online publication date: 12-Oct-2024
  • (2024)The ARCH-COMP Friendly Verification Competition for Continuous and Hybrid SystemsTOOLympics Challenge 202310.1007/978-3-031-67695-6_1(1-37)Online publication date: 26-Apr-2024
  • (2024)Scenario-Based Flexible Modeling and Scalable Falsification for Reconfigurable CPSsComputer Aided Verification10.1007/978-3-031-65633-0_15(329-355)Online publication date: 26-Jul-2024
  • (2023)Search-Based Software Testing Driven by Automatically Generated and Manually Defined Fitness FunctionsACM Transactions on Software Engineering and Methodology10.1145/362474533:2(1-37)Online publication date: 23-Dec-2023
  • (2023)Stealthy attacks formalized as STL formulas for Falsification of CPS SecurityProceedings of the 26th ACM International Conference on Hybrid Systems: Computation and Control10.1145/3575870.3587122(1-8)Online publication date: 9-May-2023
  • (2023)Quantitative Robustness for Signal Temporal Logic With Time-Freeze QuantifiersIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.328329642:12(4436-4449)Online publication date: Dec-2023
  • Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media