💻 computer science

Runtime Verification: Monitoring, Knowledge, and Uncertainty (Lecture Notes)

These lecture notes present the automata-theoretic, temporal-logical, and epistemic foundations of runtime verification, covering specification formalisms, diagnosis, opacity, and monitorability to explain how offline analysis constructs monitors for partially observable systems, while also addressing the challenges of timed extensions in real-time settings.

Original authors: Benedikt Bollig

Published 2026-04-30

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Benedikt Bollig

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to figure out if a mysterious machine is working correctly. You can't see inside the machine (it's a "black box"), and you can't stop it to take it apart. You can only watch what comes out of it: a stream of lights, sounds, or data points.

This is the world of Runtime Verification. Instead of trying to predict every possible thing the machine could do before it starts (which is like trying to map every possible path in a maze before you enter it), runtime verification watches the machine as it runs and raises an alarm if it sees something wrong.

This lecture series by Benedikt Bollig explores how to do this when you have uncertainty. Maybe the machine hides some of its actions, or maybe you don't know exactly how it works. The notes use a special kind of logic (called "epistemic logic") to track exactly what the observer knows and what they don't know at any given moment.

Here is a breakdown of the main ideas using everyday analogies:

1. The Three Levels of Knowing the Machine

The paper describes three ways we might interact with a system:

White Box: You have the blueprints. You know exactly how every gear turns. This is like having the manual and the engine open. You can check if the machine will work perfectly before you even turn it on (Model Checking).
Gray Box: You have a sketchy manual. It says "maybe this happens, maybe that happens." There are gaps. You can't be 100% sure what will happen, so you have to watch it run to be sure.
Black Box: You have no manual at all. You only see the output. You have to guess what's happening inside based on what you see.

2. The Three Main Games: Diagnosis, Opacity, and Monitoring

The paper treats three different problems as variations of the same game: "What can I infer from what I see?"

Diagnosis: The Detective

The Goal: You want to know if a specific bad thing (a "fault") happened.
The Analogy: Imagine a security guard watching a bank vault. The vault has a silent alarm (the fault) that no one hears. The guard only sees people walking in and out.
- If a person walks in, the guard doesn't know if they stole anything.
- But if the guard sees a person walk out with a bag of gold, they know for sure the theft happened.
- Diagnosis is the ability to say, "I am 100% sure the theft happened," even if you didn't see the theft itself, just the aftermath. The paper asks: Can the guard always figure this out eventually?

Opacity: The Spy

The Goal: You want to hide a secret. You want to make sure the observer never knows if the secret happened.
The Analogy: Imagine a spy trying to sneak a secret message into a room. The observer is watching the door.
- If the spy enters, the observer sees "Someone entered."
- If a normal person enters, the observer also sees "Someone entered."
- Opacity is the art of making the spy's entry look exactly like a normal person's entry. If the observer can never tell the difference, the secret is "opaque" (hidden). The paper asks: Is it possible to design a system where the spy's secret is always hidden?

Monitoring: The Traffic Cop

The Goal: To give a verdict on the system's behavior as it happens.
The Analogy: A traffic cop watching a car.
- Verdict "True": The car is driving perfectly. The cop knows it will never crash.
- Verdict "False": The car just ran a red light. The cop knows it broke the rules.
- Verdict "?": The car is currently driving normally, but it might run a red light in 5 seconds. The cop doesn't know yet.
- The paper explores when a cop can stop saying "?" and start saying "True" or "False." Sometimes, no matter how long you watch, you can never be sure (the verdict stays "?").

3. The "Knowledge" Problem

The core of the paper is that uncertainty is the main enemy.

If you see a light flash, do you know if it means "Error" or just "System Checking"?
The paper uses Epistemic Logic (the logic of knowledge) to map this out. It treats the observer's mind like a map.
- If the map shows only one possible path, the observer knows the truth.
- If the map shows two paths (one with an error, one without), the observer is uncertain.

4. The Twist: Time Changes Everything

The final chapter adds Time to the mix. Imagine the machine doesn't just do things; it does them at specific speeds.

Without Time: If you wait long enough, you might figure out the truth.
With Time: Things get messy.
- Diagnosis: You might need to know an error happened within 5 seconds. If the system is slow, you might miss the window to be sure.
- Opacity: Hiding a secret becomes harder if the timing of events gives it away.
- The Big Bad News: The paper reveals a scary limit. In the world of time, if you try to combine "checking the clock" with "figuring out what the observer knows," the math breaks down. It becomes undecidable. This means there is no algorithm that can always tell you if a timed system is safe or opaque. It's like trying to solve a puzzle where the pieces keep changing shape while you look at them.

Summary

This paper is a guide for building "smart observers" for complex systems.

It teaches us how to build Diagnosers (detectives) and Monitors (traffic cops) that work even when they can't see everything.
It shows that Diagnosis (finding faults) and Opacity (hiding secrets) are two sides of the same coin.
It proves that while we can solve these puzzles for simple systems, adding Time makes some of them impossible to solve perfectly.

The ultimate takeaway is that in a world of partial information, we can't always know the truth immediately. We have to be smart about what we can know, when we can know it, and when we have to accept that we never will.

Technical Summary: Runtime Verification, Monitoring, Knowledge, and Uncertainty

1. Problem Statement

Runtime Verification (RV) is a lightweight verification technique designed to analyze system executions as they occur, rather than exploring a complete system model offline (as in Model Checking). The core challenge addressed in these lecture notes is uncertainty arising from:

Partial Observability: Observers (agents) often cannot see all system actions or internal states (black-box or gray-box systems).
Infinite Executions: Systems are reactive and produce infinite traces, but at runtime, only finite prefixes are available.
Epistemic Limits: An observer may not know if a property holds, has held, or will hold based solely on the observed history.

The paper aims to provide a unifying framework for three distinct but related verification problems—Diagnosis (detecting faults), Opacity (hiding secrets), and Monitoring (verifying properties)—using Epistemic Temporal Logic. It further investigates how these concepts extend to Real-Time (Timed) systems, where the introduction of time and knowledge operators creates significant algorithmic challenges.

2. Methodology

The author employs a formal, automata-theoretic approach grounded in Epistemic Linear-Time Temporal Logic (LTL $\sim$ ).

2.1 Formal Framework

System Model: Systems are modeled as Büchi Automata (for infinite words) or Timed Büchi Automata (for real-time).
Observation: Agents observe a projection of the global execution trace based on a subset of observable propositions ( $AP_a \subseteq AP$ ). Indistinguishability ( $\sim_a$ ) is defined via perfect recall of observation sequences.
Logic: The logic extends standard LTL with:
- Epistemic Operators: $K_a \phi$ ("Agent $a$ knows $\phi$ ").
- Temporal Operators: Strict future ( $U^+$ ) and past ( $S^+$ ) operators, allowing reasoning about specific positions in the trace.
- Knowledge Semantics: $K_a \phi$ holds at a point if $\phi$ is true in all executions indistinguishable from the current observation.

2.2 Core Mechanisms

Knowledge Monitors: The paper constructs Deterministic Finite Automata (DFAs) (or Moore machines) that track the set of possible system states (belief states) consistent with the observation history. These monitors output verdicts based on whether the property is known to be true, false, or undetermined.
Transducers: To solve model-checking problems, the author constructs (System, Formula)-transducers. These automata run in parallel with the system, outputting the truth value of the formula at each step.
Twin-Plant Constructions: For diagnosability, the method involves simulating two system runs in parallel (one faulty, one fault-free) to check if they remain observationally indistinguishable beyond a certain delay.

3. Key Contributions

3.1 Unification of Verification Problems

The paper demonstrates that Diagnosis, Opacity, and Monitoring can be expressed uniformly as epistemic temporal properties over the same system model:

Diagnosis: $G(\text{fault} \to F K_a \text{Past}(\text{fault}))$ . The agent eventually knows a fault occurred.
Opacity: $G \neg K_a \text{Past}(\text{secret})$ . The agent never knows a secret occurred.
Monitoring: A three-valued verdict system (True, False, ?) derived from $K_a \hat{\phi}$ , $K_a \neg \hat{\phi}$ , or neither.

3.2 Algorithmic Results (Untimed Setting)

Decidability: Model checking for LTL $\sim$ is decidable. The construction of knowledge monitors allows for the effective verification of diagnosability and opacity.
Complexity:
- Standard LTL model checking is PSPACE-complete.
- Adding epistemic operators leads to a non-elementary complexity blow-up due to the iterated powerset construction required for belief states under perfect recall.
- Diagnosability (checking if a system is diagnosable) can be decided in Polynomial Time (P) for bounded delays, despite the general logic being harder.
- Opacity is shown to be PSPACE-complete.

3.3 Monitorability

The paper defines Monitorability as the structural property ensuring that for every observation prefix, there exists a finite continuation leading to a definitive verdict.

Safety and Co-safety: These classical classes are proven to be monitorable.
General LTL: Monitorability is decidable but PSPACE-hard. The class of monitorable formulas strictly contains safety/co-safety but is a strict subset of all LTL.

3.4 Timed Systems (Real-Time)

The final chapter extends the theory to Timed Automata and Timed Temporal Logic (TLTL).

Decidability of Timed Model Checking: Decidable for TLTL (without knowledge) using region abstraction.
Undecidability of Epistemic Timed Logic: The addition of knowledge operators to timed logic ( $TLTL\sim$ ) renders model checking undecidable. This is proven via reduction from the universality problem for timed automata.
Timed Opacity: Consequently, timed opacity is undecidable.
Timed Monitorability:
- Past Fragment: Timed monitorability for past-only formulas is decidable.
- Full TLTL: The monitorability of languages defined by Timed Automata is undecidable.

4. Key Results Summary

Problem	Setting	Complexity / Status	Key Insight
Model Checking	Untimed (LTL $\sim$ )	Decidable (Non-elementary)	Knowledge operators induce belief-state explosion.
Diagnosability	Untimed (Bounded)	Polynomial Time	Reduces to reachability in a "twin-plant" product.
Opacity	Untimed	PSPACE-complete	Equivalent to universality of NFAs.
Monitorability	Untimed	Decidable (PSPACE-hard)	Structural property; safety/co-safety are sufficient but not necessary.
Model Checking	Timed (TLTL)	Decidable	Uses region abstraction; past operators are easier than future.
Model Checking	Timed (TLTL $\sim$ )	Undecidable	Knowledge + Time = Undecidable (reduction from Timed Universality).
Opacity	Timed	Undecidable	Direct consequence of undecidability of epistemic timed logic.
Monitorability	Timed (Past)	Decidable	Constructible via deterministic timed automata.
Monitorability	Timed (General)	Undecidable	Even for languages defined by timed automata.

5. Significance and Impact

Theoretical Unification: The paper successfully bridges the gap between discrete-event system theory (diagnosis/opacity) and formal verification (model checking/monitoring) by using epistemic logic as a common semantic foundation. This clarifies the relationship between "detecting faults" and "hiding secrets" as dual problems of knowledge.
Clarification of Complexity: It precisely delineates the boundary between tractable and intractable problems. While diagnosis is often efficient in practice (polynomial time), the general epistemic model checking problem is computationally expensive.
The "Knowledge + Time" Barrier: A critical contribution is the demonstration that while timed verification is decidable in isolation, the combination of real-time constraints and epistemic reasoning (knowledge) leads to undecidability. This sets a hard limit on what can be automatically verified in real-time systems with partial observability.
Practical Monitor Construction: The constructive proofs provide algorithms for building runtime monitors (Moore machines) and diagnosers (DTAs). These are not just theoretical existence proofs but blueprints for implementation, handling the transition from offline analysis to online execution.
Handling Uncertainty: By formalizing "uncertainty" through indistinguishability relations, the notes provide a rigorous method for reasoning about what an observer can and cannot know, which is essential for security (opacity) and reliability (diagnosis) in complex, partially observable systems.

In conclusion, these lecture notes establish a comprehensive theoretical framework for runtime verification under uncertainty, highlighting both the power of epistemic logic to unify diverse verification tasks and the fundamental algorithmic limits imposed by combining time and knowledge.