- Tengfei Li ORCID:orcid.org/0000-0002-9531-71281,2,
- Jing Liu1,
- Haiying Sun1,
- Xiaohong Chen1,
- Ling Yin3,
- Xia Mao1 &
- …
- Junfeng Sun2
410Accesses
Abstract
Combining spatial and temporal primitives together is quite useful to specify dynamic behaviors of cyber-physical systems. The ability to represent spatio-temporal properties by means of formulas in spatio-temporal logics has recently found important applications in various fields, such as runtime verification, parameter synthesis, and falsification. In this paper, we present a spatio-temporal specification language,STSL, by combining signal temporal logic (STL) with a spatial logic\(\mathcal {S}4_{u}\) to characterize spatio-temporal dynamic behaviors of cyber-physical systems. This language is highly expressive: it allows the description of quantitative signals, by expressing spatio-temporal traces over real-valued signals in dense time, and Boolean signals, by constraining values of spatial objects across threshold predicates.STSL combines the power of temporal modalities and spatial operators and enjoys important properties such as safety and liveness. We provide the falsification problem through extending Lemire’s algorithm and a parameter synthesis procedure by calling the simulated annealing algorithm. We demonstrate the proposed approach on the adaptive cruise control system and path planning of quadrotors.
This is a preview of subscription content,log in via an institution to check access.
Access this article
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
Price includes VAT (Japan)
Instant access to the full article PDF.








Similar content being viewed by others
References
Lee EA (2008) Cyber physical systems: Design challenges. In: 2008 11th IEEE international symposium on object oriented real-time distributed computing (ISORC). IEEE
Gabbay DM, Kurucz A, Wolter F, Zakharyaschev M (2003) Many-dimensional modal logics: theory and applications. Amsterdam; Boston: Elsevier. North Holland
Konur S, Fisher M, Schewe S (2013) Combined model checking for temporal, probabilistic, and real-time logics. Theor Comput Sci 503:61–88
Gabelaia D, Kontchakov R, Kurucz A, Wolter F, Zakharyaschev M (2005) Combining spatial and temporal logics: expressiveness vs. complexity. J Artif Intell Res 23:167–243
Wolter F, Zakharyaschev M (2000) Spatio-temporal representation and reasoning based on RCC-8. In: 7Th international conference on principles of knowledge representation and reasoning. Morgan kaufmann, pp 3–14
Bennett B (1994) Spatial reasoning with propositional logics. In: 4Th international conference on principles of knowledge representation and reasoning (KR). Morgan kaufmann, pp 51–62
Randell DA, Cui Z, Cohn AG (1992) A spatial logic based on regions and connection. In: 3Th international conference on principles of knowledge representation and reasoning. Morgan kaufmann, pp 165–176
Kontchakov R, Kurucz A, Wolter F, Zakharyaschev M (2007) Spatial logic+ temporal logic=?. In: Handbook of spatial logics. Springer, pp 497–564
Shao Z, Liu J, Ding Z, Chen M, Jiang N (2013) Spatio-temporal properties analysis for cyberphysical systems. In: 18Th international conference on engineering of complex computer systems (ICECCS). IEEE, pp 101–110
Sun H, Liu J, Chen X, Du D (2015) Specifying cyber physical system safety properties with metric temporal spatial logic. In: 22nd asia-pacific software engineering conference (APSEC). IEEE, pp 254–260
Alur R, Feder T, Henzinger TA (1996) The benefits of relaxing punctuality. J ACM (JACM) 43(1):116–146
Maler O, Nickovic D (2004) Monitoring temporal properties of continuous signals. In: Formal techniques, modelling and analysis of timed and fault-tolerant systems. Springer, pp 152–166
Donzé A., Ferrere T, Maler O (2013) Efficient robust monitoring for STL. In: International conference on computer aided verification. Springer, pp 264–279
Raman V, Donzé A, Sadigh D, Murray RM, Seshia SA (2015) Reactive synthesis from signal temporal logic specifications. In: Proceedings of the 18th international conference on hybrid systems: Computation and control. ACM, pp 239–248
Haghighi I, Jones A, Kong Z, Bartocci E, Gros R, Belta C (2015) Spatel: a novel spatialtemporal logic and its applications to networked systems. In: Proceedings of the 18th international conference on hybrid systems: computation and control. ACM, pp 189–198
Li T., Liu J., Kang J., Sun H., Yin W., Chen X., Wang H. (2020) STSL: A novel spatio-temporal specification language for cyber-physical systems. In: The 20th IEEE international conference on software quality, reliability and security. pp. 309–319. IEEE
Li T, Liu J, An D, Sun H (2019) A sound and complete axiomatisation for spatio-temporal specification language. In: The 31st international conference on software engineering & knowledge engineering. KSI, pp 153–204
Lemire D (2007) Streaming maximum-minimum filter using no more than three comparisons per element. Nordic J Comput 13(4):328–339
Van Laarhoven PJ, Aarts EH (1987) Simulated annealing. In: Simulated annealing: theory and applications. Springer, pp 7–15
Ladner RE (1977) The computational complexity of provability in systems of modal propositional logic. SIAM J Comput 6(3):467–480
Wolter F, Zakharyaschev M (2005) A logic for metric and topology. J Symb Log 70(3):795–828
Gao H, Huang W, Yang X, Duan Y, Yin Y (2018) Toward service selection for workflow reconfiguration: an interface-based computing solution. Futur Gener Comput Syst 87:298–311
Nenzi L, Bortolussi L, Ciancia V, Loreti M, Massink M (2015) Qualitative and quantitative monitoring of spatio-temporal properties. In: Runtime verification. Springer, pp 21–37
Deshmukh JV, Donzé A, Ghosh S, Jin X, Juniwal G, Seshia SA (2017) Robust online monitoring of signal temporal logic. Form Methods Syst Des 51(1):5–30
Sankaranarayanan S, Fainekos G (2012) Falsification of temporal properties of hybrid systems using the cross-entropy method. In: Proceedings of the 15th ACM international conference on hybrid systems: computation and control. ACM, pp 125–134
Nghiem T, Sankaranarayanan S, Fainekos G, Ivancic F, Gupta A, Pappas GJ (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. ACM, pp 211–220
Jin X, Donzé A, Deshmukh JV, Seshia SA (2015) Mining requirements from closed-loop control models. IEEE Trans Comput-Aid Des Integr Circ Syst 34(11):1704–1717
Zhang Z, Hasuo I, Arcaini P (2019) Multi-armed bandits for boolean connectives in hybrid system falsification. In: International conference on computer aided verification. Springer, pp 401–420
Metropolis N, Rosenbluth AW, Rosenbluth MN, Teller AH, Teller E (1953) Equation of state calculations by fast computing machines. J Chem Phys 21(6):1087–1092
Yang X, Zhou S, Cao M (2019) An approach to alleviate the sparsity problem of hybrid collaborative filtering based recommendations: the productattribute perspective from user reviews. Mob Netw Appl :1–15
Takahama T, Akasaka D (2018) Model predictive control approach to design practical adaptive cruise control for traffic jam. Int J Autom Eng 9(3):99–104
Kavraki LE, Svestka P, Latombe JC, Overmars MH (1996) Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans Robot Autom 12(4):566–580
Knapp A, Merz S, Wirsing M, Zappe J (2006) Specification and refinement of mobile systems in MTLA and mobile uml. Theor Comput Sci 351(2):184–202
Bresolin D, Sala P, Della Monica D, Montanari A, Sciavicco G (2010) A decidable spatial generalization of metric interval temporal logic. In: 2010 17Th international symposium on temporal representation and reasoning. IEEE, pp 95–102
Balbiani P, Fernández-Duque D., Lorini E (2017) Exploring the bidimensional space: a dynamic logic point of view. In: Proceedings of the 16th conference on autonomous agents and multiagent systems. International Foundation for Autonomous Agents and Multiagent Systems, pp 132–140
Bennett B, Cohn AG, Wolter F, Zakharyaschev M (2002) Multi-dimensional modal logic as a framework for spatio-temporal reasoning. Appl Intell 17(3):239–251
Ciancia V, Gilmore S, Grilletti G, Latella D, Loreti M, Massink M (2018) Spatio-temporal model checking of vehicular movement in public transport systems. Int J Softw Tools Technol Transfer :1–23
Nenzi L, Bortolussi L, Ciancia V, Loreti M, Massink M (2017) Qualitative and quantitative monitoring of spatio-temporal properties with SSTL. Log Methods Comput Sci 14:1–38
Bartocci E, Bortolussi L, Loreti M, Nenzi L (2017) Monitoring mobile and spatially distributed cyberphysical systems. In: Proceedings of the 15th ACMIEEE international conference on formal methods and models for system design. ACM, pp 146–155
Talcott C (2008) Cyber-physical systems and events. In: Software-intensive systems and new computing paradigms. Springer, pp 101–115
Tan Y, Vuran MC, Goddard S (2009) Spatiotemporal event model for cyber-physical systems. In: 2009 29th IEEE international conference on distributed computing systems workshops. IEEE pp. 44–50
Gao H, Huang W, Yang X (2019) Applying probabilistic model checking to path planning in an intelligent transportation system using mobility trajectories and their statistical data. Intell Automat Soft Comput 25(3):547–559
Gao H, Liu C, Li Y, Yang X (2020) V2vr: reliable hybrid-network-oriented v2v data transmission and routing considering rsus and connectivity probability. IEEE Trans Intell Transp Syst :1–14.https://doi.org/10.1109/TITS.2020.2983835
Acknowledgements
We would like to thank the anonymous reviewers for their valuable comments and suggestions, which helped improve the quality of this paper. This paper is funded by the National Key Research and Development Project 2017YFB1001800, NSFC 61802251, NSFC 61972150, and Shanghai Knowledge Service Platform Project ZF1213.
Author information
Authors and Affiliations
Shanghai Key Laboratory of Trustworthy Computing, East China Normal University, Shanghai, China
Tengfei Li, Jing Liu, Haiying Sun, Xiaohong Chen & Xia Mao
CASCO SIGNAL LTD., Shanghai, China
Tengfei Li & Junfeng Sun
Shanghai University Of Engineering Science, Shanghai, China
Ling Yin
- Tengfei Li
You can also search for this author inPubMed Google Scholar
- Jing Liu
You can also search for this author inPubMed Google Scholar
- Haiying Sun
You can also search for this author inPubMed Google Scholar
- Xiaohong Chen
You can also search for this author inPubMed Google Scholar
- Ling Yin
You can also search for this author inPubMed Google Scholar
- Xia Mao
You can also search for this author inPubMed Google Scholar
- Junfeng Sun
You can also search for this author inPubMed Google Scholar
Corresponding author
Correspondence toTengfei Li.
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Li, T., Liu, J., Sun, H.et al. Runtime Verification of Spatio-Temporal Specification Language.Mobile Netw Appl26, 2392–2406 (2021). https://doi.org/10.1007/s11036-021-01779-5
Accepted:
Published:
Issue Date:
Share this article
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative