Quantitative monitoring of STL with edit distance
Open Access
- 27 March 2018
- journal article
- research article
- Published by Springer Nature in Formal Methods in System Design
- Vol. 53 (1) , 83-112
Abstract
In cyber-physical systems (CPS), physical behaviors are typically controlled by digital hardware. As a consequence, continuous behaviors are discretized by sampling and quantization prior to their processing. Quantifying the similarity between CPS behaviors and their specification is an important ingredient in evaluating correctness and quality of such systems. We propose a novel procedure for measuring robustness between digitized CPS signals and signal temporal logic (STL) specifications. We first equip STL with quantitative semantics based on the weighted edit distance, a metric that quantifies both space and time mismatches between digitized CPS behaviors. We then develop a dynamic programming algorithm for computing the robustness degree between digitized signals and STL specifications. In order to promote hardware-based monitors we implemented our approach in FPGA. We evaluated it on automotive benchmarks defined by research community, and also on realistic data obtained from magnetic sensor used in modern cars.Keywords
Funding Information
- Österreichische Forschungsförderungsgesellschaft (845631)
- ICT COST Action ARVI (IC1402)
- Austrian Science Fund (11405-N23, S 11412-N23)
- Austrian Science Fund (Doctoral Program Logical Methods in Computer Science)
This publication has 32 references indexed in Scilit:
- Computer Aided Verification2017
- Quantitative Monitoring of STL with Edit Distance2016
- Computer Aided VerificationLecture Notes in Computer Science, 2015
- Data-Driven Statistical Learning of Temporal Logic Properties2014
- On-Line Monitoring for Temporal Logic Robustness2014
- Formal Methods for Industrial Critical Systems2014
- Robustness Analysis of String TransducersLecture Notes in Computer Science, 2013
- 25 Years of Model Checking2008
- Reasoning with Temporal Logic on Truncated Paths2003
- Simple On-the-fly Automatic Verification of Linear Temporal Logic1996