@inproceedings{c90e187a10cc4a42abebe3ba961859ee,
title = "SAW: A Tool for Safety Analysis of Weakly-Hard Systems",
abstract = "We introduce SAW, a tool for safety analysis of weakly-hard systems, in which traditional hard timing constraints are relaxed to allow bounded deadline misses for improving design flexibility and runtime resiliency. Safety verification is a key issue for weakly-hard systems, as it ensures system safety under allowed deadline misses. Previous works are either for linear systems only, or limited to a certain type of nonlinear systems (e.g., systems that satisfy exponential stability and Lipschitz continuity of the system dynamics). In this work, we propose a new technique for infinite-time safety verification of general nonlinear weakly-hard systems. Our approach first discretizes the safe state set into grids and constructs a directed graph, where nodes represent the grids and edges represent the reachability relation. Based on graph theory and dynamic programming, our approach can effectively find the safe initial set (consisting of a set of grids), from which the system can be proven safe under given weakly-hard constraints. Experimental results demonstrate the effectiveness of our approach, when compared with the state-of-the-art. An open source implementation of our tool is available at https://github.com/551100kk/SAW. The virtual machine where the tool is ready to run can be found at https://www.csie.ntu.edu.tw/~r08922054/SAW.ova.",
keywords = "Graph theory, Safety verification, Weakly-hard systems",
author = "Chao Huang and Chang, {Kai Chieh} and Lin, {Chung Wei} and Qi Zhu",
note = "Funding Information: This work is supported by the National Science Foundation awards 1834701, 1834324, 1839511, 1724341, and the Office of Naval Research grant N00014-19-1-2496. It is also supported by the Asian Office of Aerospace Research and Development (AOARD), jointly with the Office of Naval Research Global (ONRG), award FA2386-19-1-4037, the Taiwan Ministry of Education (MOE) grants NTU-107V0901 and NTU-108V0901, the Taiwan Ministry of Science and Technology (MOST) grants MOST-108-2636-E-002-011 and MOST-109-2636-E-002-022. Publisher Copyright: {\textcopyright} 2020, The Author(s).; 32nd International Conference on Computer Aided Verification, CAV 2020 ; Conference date: 21-07-2020 Through 24-07-2020",
year = "2020",
doi = "10.1007/978-3-030-53288-8_26",
language = "English (US)",
isbn = "9783030532871",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "543--555",
editor = "Lahiri, {Shuvendu K.} and Chao Wang",
booktitle = "Computer Aided Verification - 32nd International Conference, CAV 2020, Proceedings",
}