Runtime Verification for LTL and TLTL

TLDR

The article investigates runtime verification of properties expressed in linear‑time temporal logic (LTL) and timed linear‑time temporal logic (TLTL). The authors aim to introduce a three‑valued semantics that determines whether a partial observation of a running system satisfies an LTL or TLTL property. They classify runtime verification relative to model checking and testing, present an optimal deterministic monitor for LTL that is minimal in size and reports satisfaction or violation as early as possible, relate the approach to general monitorable properties, and extend the construction to TLTL with a timed monitor based on the same three‑valued semantics. The method is shown to be feasible on real‑world temporal‑logic specifications, and the set of monitorable properties is proven to be strictly larger than the safety and cosafety classes.

Abstract

This article studies runtime verification of properties expressed either in lineartime temporal logic (LTL) or timed lineartime temporal logic (TLTL). It classifies runtime verification in identifying its distinguishing features to model checking and testing, respectively. It introduces a three-valued semantics (with truth values true, false, inconclusive ) as an adequate interpretation as to whether a partial observation of a running system meets an LTL or TLTL property. For LTL, a conceptually simple monitor generation procedure is given, which is optimal in two respects: First, the size of the generated deterministic monitor is minimal , and, second, the monitor identifies a continuously monitored trace as either satisfying or falsifying a property as early as possible . The feasibility of the developed methodology is demontrated using a collection of real-world temporal logic specifications. Moreover, the presented approach is related to the properties monitorable in general and is compared to existing concepts in the literature. It is shown that the set of monitorable properties does not only encompass the safety and cosafety properties but is strictly larger. For TLTL, the same road map is followed by first defining a three-valued semantics. The corresponding construction of a timed monitor is more involved, yet, as shown, possible.