Runtime verification in uncertain environment based on probabilistic model learning

Abstract

Runtime verification (RV) is a lightweight approach to detecting temporal errors of system at runtime. It confines the verification on observed trajectory which avoids state explosion problem. To predict the future violation, some work proposed the predictive RV which uses the information from models or static analysis. But for software whose models and codes cannot be obtained, or systems running under uncertain environment, these predictive methods cannot take effect. Meanwhile, RV in general takes multi-valued logic as the specification languages, for example the true, false and inconclusive in three-valued semantics. They cannot give accurate quantitative description of correctness when inconclusive is encountered. We in this paper present a RV method which learns probabilistic model of system and environment from history traces and then generates probabilistic runtime monitor to quantitatively predict the satisfaction of temporal property at each runtime state. In this approach, Hidden Markov Model (HMM) is firstly learned and then transformed to Discrete Time Markov Chain (DTMC). To construct incremental monitor, the monitored LTL property is translated into Deterministic Rabin Automaton (DRA). The final probabilistic monitor is obtained by generating the product of DTMC and DRA, and computing the probabilities for each state. With such a method, one can give early warning once the probability of correctness is lower than a pre-defined threshold, and have the chance to do adjustment in advance. The method has been implemented and experimented on real UAS (Unmanned Aerial Vehicle) simulation platform.

Keywords

• runtime verification
• probabilistic monitor
• markov chain
• ω-automata