Abstract In this paper we study monitoring of real-time systems with respect to properties given by a pair of Timed Büchi Automata, one for the property and one for its complement. This includes properties expressible in temporal logics that are closed under complementation and can be translated into Timed Büchi Automata, e.g., Metric Interval Temporal Logic. We introduce efficient symbolic online monitoring algorithms in a number of settings, using difference bound matrices representing zones. Our contributions include a principled treatment of time divergence and monitoring under timing uncertainty. Our online monitoring procedure is implemented in the tool MoniTAal , and shown to effectively monitor properties over long traces.

Monitoring is an important part of the verification toolbox, in particular in situations where exhaustive verification using, e.g., model-checking is infeasible. The goal of online monitoring is to determine the satisfaction or violation of a specification during runtime, i.e., based on finite execution prefixes. However, not every specification is amenable to monitoring, e.g., properties for which no finite execution can witness satisfaction or violation. Monitorability is the question of whether a given specification is amenable to monitoring, and has been extensively studied in discrete time. Here, we study the monitorability problem for real-time properties expressed as Timed Automata. For specifications given by deterministic Timed Muller Automata, we prove decidability while we show that the problem is undecidable for specifications given by nondeterministic Timed Büchi automata. Furthermore, we refine monitorability to also determine bounds on the number of events as well as the time that must pass before monitoring the property may yield an informative verdict. We prove that for deterministic Timed Muller automata, such bounds can be effectively computed. In contrast we show that for nondeterministic Timed Büchi automata such bounds are not computable.

Nfer is a rule-based language for abstracting event streams into a hierarchy of intervals with data. Nfer has multiple implementations and has been applied in the analysis of spacecraft telemetry and autonomous vehicle logs. This work provides the first complexity analysis of nfer evaluation, i.e., the problem of deciding whether a given interval is generated by applying rules. We show that the full nfer language is undecidable and that this depends on both recursion in the rules and an infinite data domain. By restricting either or both of those capabilities, we obtain tight decidability results. We also examine the impact on complexity of exclusive rules and minimality. For the most practical case, which is minimality with finite data, we provide a polynomial-time algorithm.

Nfer is a tool that implements the eponymous language for log analysis and monitoring. Users write rules to calculate new information from an event stream such as a program log either offline or online. In addition to a command-line program, nfer exposes interfaces in Python and R and can generate monitors for embedded systems. Nfer is designed to be fast and has been repeatedly demonstrated to outperform similar tools.

Software attestation seeks to verify the authenticity of a system without the aid of trusted hardware, and has important applications in the field of security. Such attestation schemes are of particular interest in the embedded domain, where simplicity and limited resources constrain more complex security solutions. At the same time, these properties enable attestation approaches that rely on predictable side-effects. Most software attestation schemes aim to verify the integrity of memory using a combination of cryptographic schemes, internal side-effects like TLB misses, and known timing constraints. However, little attention has been paid to leveraging non-traditional side-effects, in particular, externally observable side-effects such as power consumption. In this paper we introduce a method for software attestation using power consumption as the side-effect. We show how to circumvent the undecidable nature of program execution for this purpose and present a static compiler transformation which implements the technique. Our approach is less intrusive than traditional software attestation because the system does not require interruption to compute a cryptographic checksum. It is particularly well suited to real-time systems where consistent timing is more important than speed.