💻 computer science

A Unified Framework for Runtime Verification and Model-Based Diagnosis in LOLA

Dieses Paper präsentiert ein einheitliches Framework, das Runtime-Verifikation und modellbasierte Diagnose innerhalb der LOLA-Stream-Spezifikationssprache integriert, um eine kontinuierliche, Online-Fehlerlokalisierung neben der Detektion zu ermöglichen, ohne dass separate Toolchains erforderlich sind.

Ursprüngliche Autoren: Raik Hipler, Martin Leucker, Patrick Rodler

Veröffentlicht 2026-06-24

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Raik Hipler, Martin Leucker, Patrick Rodler

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie sind der Chefmechaniker für ein sehr komplexes, hochtechnologisches Auto, das selbstständig fährt. Dieses Auto hat zwei Hauptaufgaben:

Das Alarmsystem (Laufzeitverifikation): Es beobachtet ständig den Tacho und die Motortemperatur. Wenn etwas merkwürdig aussieht (wie zum Beispiel, wenn der Motor zu heiß wird), ertönt sofort eine Sirene: „Etwas ist nicht in Ordnung!“
Der Detektiv (Modellbasierte Diagnose): Sobald die Sirene ertönt, tritt der Detektiv auf den Plan, um herauszufinden, was kaputt ist. Ist es der Kühler? Der Lüfter? Ein loses Kabel?

Das Problem: Normalerweise werden diese beiden Aufgaben von verschiedenen Personen mit unterschiedlichen Werkzeugen erledigt. Das Alarmsystem ist großartig darin zu sagen: „Hey, da ist ein Problem!“, aber es ist schlecht darin zu erklären, warum. Der Detektiv ist großartig darin, das defekte Teil zu finden, aber er taucht meistens erst auf, nachdem das Problem bereits bekannt ist, und er weiß vielleicht nicht, wie sich das Auto während der Fahrt verhält.

Die Lösung des Papers:
Dieses Paper stellt ein neues, vereinheitlichtes Framework namens Lola vor, das das Alarmsystem und den Detektiv in einem einzigen, super-intelligenten, kontinuierlichen Gedankenstrom kombiniert. Anstatt zwischen Werkzeugen zu wechseln, nutzt das System eine einzige Sprache, um das Auto zu beobachten, den Fehler zu erkennen und das Rätsel gleichzeitig zu lösen.

So funktioniert es, unterteilt in einfache Konzepte:

1. Der „Strom“ der Zeit

Betrachten Sie die Daten des Autos nicht als einzelne Momentaufnahme, sondern als einen Filmstreifen (einen Stream). Jede Sekunde kommen neue Videoframes an (Temperatur, Geschwindigkeit, Sensormesswerte).

Der alte Weg: Sie machen ein Foto vom Auto, prüfen, ob es kaputt ist, und machen dann später ein weiteres Foto.
Der Lola-Weg: Sie schauen den Film in Echtzeit. Das System weiß, dass das, was vor 5 Sekunden passiert ist, der Grund dafür sein kann, dass das Auto jetzt gerade seltsam reagiert.

2. Umgang mit „unscharfen“ Informationen

Manchmal sind die Sensoren etwas verrauscht. Vielleicht sagt der Temperatursensor: „Es liegt zwischen 80 und 90 Grad“, oder er liefert gar keine Werte, weil ein Kabel locker ist.

Die Magie: Lola benötigt keine perfekten Zahlen. Es kann mit „vielleicht“ und „Bereichen“ argumentieren. Es nutzt eine spezielle Logik (wie ein super-intelligenter mathematischer Rätsellöser), um zu sagen: „Selbst wenn wir die exakte Temperatur nicht kennen, wissen wir, dass der Lüfter kaputt sein muss, weil die Mathematik hier nicht aufgeht.“

3. Drei Wege, das Rätsel zu lösen

Das Paper erklärt drei verschiedene Arten, wie dieses System wie ein Detektiv agieren kann, je nach Situation:

Der „Sofort-Detektiv“ (0-Instanz-Diagnose):
Dieser Detektiv betrachtet nur den aktuellen Frame des Films. „Der Motor ist jetzt gerade heiß, also muss der Lüfter jetzt gerade kaputt sein.“ Das ist schnell, könnte aber das große Ganze übersehen.
Der „Geschichtswisser-Detektiv“ (Multi-Instanz-Diagnose):
Dieser Detektiv schaut sich die letzten Minuten des Films an. „Der Motor ist seit den letzten 3 Minuten heiß, und der Lüfter hat die ganze Zeit über seltsam reagiert.“ Das ist ideal für Dinge, die sich nicht ändern, wie eine durchgebrannte Sicherung, die dauerhaft defekt bleibt. Er kombelt Hinweise aus der Vergangenheit, um den Übeltäter zu finden.
Der „Zeitreisende-Detektiv“ (Temporale Diagnose):
Dies ist der fortschrittlichste Detektiv. Er erkennt, dass Teile kaputtgehen können und sich dann wieder selbst reparieren (oder erneut ausfallen).
- Szenario: Der Lüfter funktionierte um 1:00 Uhr gut, fiel um 1:05 Uhr aus und begann um 1:10 Uhr wieder zu funktionieren, weil der Motor abgekühlt ist.
- Das Ergebnis: Dieser Detektiv kann sagen: „Der Lüfter war um 1:05 Uhr kaputt, aber jetzt ist er wieder in Ordnung.“ Dies ist entscheidend für Dinge wie einen Router, der die Verbindung für eine Sekunde verliert und sich dann wieder verbindet.

4. Der „Annahmen“-Trick

Das System nutzt auch „Annahmen“ wie ein Detektivnotizbuch.

Beispiel: „Wir nehmen an, dass die Tür geschlossen ist.“ Wenn die Mathematik besagt, dass die Tür offen sein muss, damit die Temperatur so hoch ist, erkennt das System, dass seine Annahme falsch war oder ein Sensor lügt. Es nutzt diese Annahmen, um unmögliche Szenarien herauszufiltern und das wahre Problem zu finden.

5. Hat es funktioniert?

Die Autoren haben einen Prototyp dieses Systems gebaut und es an zwei Standard-Digitalschaltungen (wie winzigen, vereinfachten Computerchips) getestet.

Sie haben Teile dieser Schaltungen absichtlich defekt gemacht (z. B. ein Kabel so manipuliert, dass es dauerhaft auf „Aus“ steht).
Das System hat den Datenstrom erfolgreich beobachtet, den Fehler erkannt und genau das defekte Teil korrekt identifiziert, selbst als die Daten unscharf waren oder der Fehler in der Vergangenheit lag.
Es erledigte dies schnell genug, um für die Echtzeitüberwachung nutzbar zu sein.

Zusammenfassung

Dieses Paper schlägt eine neue Art vor, komplexe Maschinen zu überwachen. Anstatt ein separates Alarmsystem und ein separates Reparaturhandbuch zu haben, kombiniert es sie zu einem einzigen kontinuierlichen, stream-basierten Detektiv. Es kann mit unscharfen Daten umgehen, in die Vergangenheit zurückblicken, um die Ursache zu finden, und sogar Fehlern nachgehen, die kommen und gehen – und das alles, während die Maschine läuft. Es ist, als würde man Ihrem Auto einen Mechaniker geben, der niemals schläft, keinen Hinweis verpasst und Ihnen genau sagen kann, was wann kaputtgegangen ist, selbst wenn die Sensoren etwas unzuverlässig sind.

Technisches Resümee: Ein vereinheitlichtes Framework für Laufzeitverifikation und modellbasierte Diagnose in Lola

Problemstellung

Sicherheitskritische Systeme erfordern nicht nur die Erkennung von Fehlern, sondern auch die Lokalisierung ihrer Ursachen, um eine effektive Schadensbegrenzung zu ermöglichen. Während die Laufzeitverifikation (Runtime Verification, RV) effektiv darin ist, Abweichungen vom spezifizierten Verhalten während der Ausführung zu erkennen, und die modellbasierte Diagnose (Model-Based Diagnosis, MBD) ein fundiertes Framework zur Identifizierung fehlerhafter Komponenten darstellt, operieren diese beiden Techniken historisch gesehen isoliert voneinander. Traditionelle RV-Monitore analysieren das Systemverhalten über potenziell unbegrenzte Zustandssequenzen hinweg, um Verletzungen zu detektieren, wohingegen MBD typischerweise an einem einzelnen, unbestimmten Zeitpunkt nach der Erkennung eines Fehlers operiert. Darüber hinaus versagen bestehende Integrationen oft dabei, detektierte Fehleraktionen direkt auf abnormale Komponenten im Sinne der MBD abzubilden, oder sie verfügen nicht über die Fähigkeit, unsichere Eingaben und temporale Faltdynamiken innerhalb eines vereinheitlichten, stream-basierten Reasoning-Frameworks zu handhaben.

Methodik

Das Paper schlägt ein vereinheitlichtes Framework vor, das stream-basierte RV und MBD innerhalb von Lola, einer synchronen stream-basierten Spezifikationssprache, integriert. Die Kernmethodik besteht darin, sowohl Verifikations- als auch Diagnoseinformationen als spezialisierte Streams zu kodieren, was eine kontinuierliche Beobachtung und symbolisches Reasoning unter Unsicherheit ermöglicht.

1. Vereinheitlichte Kodierung in Lola

Die Autoren bilden ein diagnostiziertes System $S = (sd, comps)$ auf ein Lola-System $(\phi, comps)$ ab:

Systembeschreibung ($sd$): Wird in den Annahme-Stream ( $\alpha$ ) kodiert, der per Definition wahr ist. Dieser Stream enthält das Verhaltenswissen (z. B. $\neg ab(c) \to beh_c$ ) und das allgemeine Wissen über das System.
Komponenten ($comps$): Jede Komponente $c$ wird durch einen internen Booleschen Stream repräsentiert, wobei true angibt, dass die Komponente abnormal ist ($ab(c)$).
Beobachtungen: Beobachtbare Systemvariablen (Eingänge/Ausgänge) werden als Eingangs-Streams modelliert, die entweder sicher (deterministisch) oder unsicher (nicht-deterministische Intervalle oder Mengen) sein können.
Nicht-beobachtbare Variablen: Interne Systemwerte, die nicht direkt gemessen werden, werden als interne Streams modelliert.
Diagnoseproblem-Instanz (DPI): Ein Tupel $(\phi, comps, \Psi)$ , wobei $\Psi$ die Historie der Eingangsrestriktionen bis zum aktuellen Zeitpunkt darstellt.

2. Symbolisches Reasoning und Diagnoseberechnung

Das Framework nutzt einen symbolischen Monitor, der eine Constraint-Menge $[\phi]_{\Psi}^{\leq t}$ aufrechterhält, welche alle möglichen Systemverhaltensweisen darstellt, die mit den Beobachtungen bis zum Zeitpunkt $t$ konsistent sind.

Constraint-Lösung: Ein SMT-Solver (z. B. Z3) wird verwendet, um Konsistenz zu prüfen und Implikationen abzuleiten.
Ableitung der Diagnose: Eine Diagnose ist eine Annahme über den Zustand (normal/abnormal) der Komponenten, die die Systembeschreibung mit den Beobachtungen konsistent macht. Das Framework berechnet minimale Diagnosen, indem es minimale Konflikte (Mengen von Komponenten, die nicht alle normal sein können) identifiziert und deren minimale Hitting Sets berechnet.
Pruning (Beschneidung): Um eine konstante Zeit- und Platzkomplexität der Überwachung zu gewährleisten, schreiben Pruning-Strategien die Constraints um, um die Größe der Constraint-Menge zu begrenzen und nur notwendige historische Informationen zu behalten.

3. Diagnoseszenarien

Das Framework unterstützt drei verschiedene Diagnosemodi basierend auf der temporalen Natur der Komponentenfehler:

Multi-Instant-Diagnose: Nimmt an, dass die Zustände der Komponenten über ein Fenster von $k$ vergangenen Instanzen ( $t-k$ bis $t$ ) statisch sind. Eine $k$ -Instant-Diagnose erklärt alle Beobachtungen innerhalb dieses Fensters. Das Paper beweist, dass $k$ -Instant-Diagnosen für atemporale Spezifikationen äquivalent zur Aggregation von Single-Instant-Diagnosen sind, für temporale Spezifikationen (mit Nicht-Null-Offsets) jedoch fokussiertere Ergebnisse liefern.
Temporale Diagnose: Erlaubt es den Zuständen der Komponenten, sich über die Zeit zu ändern. Eine $k$ -temporale Diagnose ist eine Menge von Paaren $(c, t')$ , die angibt, dass Komponente $c$ spezifisch zum Zeitpunkt $t'$ abnormal ist. Dies ist entscheidend für die Identifizierung transienter Fehler (z. B. Überhitzung) oder Fehler, die sich erst später aufgrund von Propagation manifestieren.
Erweiterte Einstellungen: Das Framework integriert nativ Hintergrundwissen (das Komponenten zwingend als normal definiert), starke Fehlermodelle (die spezifische fehlerhafte Verhaltensweisen spezifizieren) und abstrakte Modellierung.

Zentrale Beiträge

Vereinheitlichte Kodierung: Eine Methode, die Systembeschreibungen und Diagnoseannahmen als spezialisierte Streams in Lola auszudrücken, was implizit alle gültigen Diagnosen für beobachtetes Verhalten darstellt.
Multi-Instant-Diagnosetheorie: Eine generalisierte Theorie zur Diagnose zeitinvarianter Fehler über ein gleitendes Fenster von Beobachtungen, welche die Standard-Multi-Observation-Diagnose als Spezialfall subsumiert.
Temporale Diagnose: Unterstützung für zeitvariante Abnormalität, was die Identifizierung des Zeitpunkts (wann) ermöglicht, an dem ein Fehler auftritt, nicht nur der Komponente (welche), die fehlerhaft ist.
Flexible Diagnoseszenarien: Die Fähigkeit, Hintergrundwissen, abstrakte Modellierung und verschiedene Fehlertypen (persistent vs. transient) elegant innerhalb eines einzigen stream-basierten Frameworks zu handhaben.
Implementierung und Evaluierung: Eine Prototyp-Implementierung, die den HS-Tree-Algorithmus, QuickXplain und Z3 integriert und an den Benchmarks ISCAS85 und ISCAS89 validiert wurde.

Ergebnisse

Die Autoren evaluierten das Framework an zwei Booleschen Schaltungen:

c17 (ISCAS85): Eine rein kombinatorische Schaltung mit 6 Komponenten.
s27 (ISCAS89): Eine sequentielle Schaltung mit 14 Komponenten.

Ergebnisse:

Machbarkeit: Das Framework konnte die tatsächlich injizierten Fehler (stuck-at-false) in beiden Schaltungen erfolgreich identifizieren.
Temporale Genauigkeit: Für die sequentielle Schaltung (s27) lokalisierte das Framework Fehler korrekt nur dann, wenn das Beobachtungsfenster ( $k$ ) groß genug war, um die Ursprung und die Propagationszeit des Fehlers abzudecken.
Performance:
- Die Laufzeit stieg mit größeren $k$ -Werten. Für c17 dauerte die $k$ -Instant-Diagnose bis zu 246 ms ( $k=0$ ) bzw. 775 ms ( $k=31$ ) pro Instanz.
- Die temporale Diagnose war signifikant teurer aufgrund der kombinatorischen Explosion bei der Behandlung von $(c, t')$ als distinkte Komponenten. Für c17 dauerte die temporale Diagnose bis zu 8,7 Sekunden pro Instanz für $k=5$ und 136 Sekunden für $k=12$ .
- Trotz der Rechenkosten merken die Autoren an, dass die Laufzeiten bei konstantem $k$ unabhängig von der Gesamtlänge des Traces blieben, was die Durchführbarkeit der Pruning-Strategien bestätigt.

Bedeutung und Ansprüche

Das Paper beansprucht, eine kompakte, fundierte Integration von Laufzeitverifikation und modellbasierter Diagnose bereitzustellen. Seine Bedeutung liegt in der Überbrückung der Lücke zwischen automatisierter Fehlererkennung (RV) und systematischer Fehlerlokalisierung (MBD) innerhalb eines einzigen, stream-basierten Frameworks.

Die Autoren betonen, dass dieser Ansatz:

Unsichere Eingaben und Umweltannahmen unterstützt, was eine verfeinerte Inferenz basierend auf Expertenwissen ermöglicht.
Eine Online-Diagnose ermöglicht, indem durch symbolisches Reasoning in jedem Zeitpunkt ein Urteil gefällt wird.
Eine synergetische Kombination bietet, bei der die Stärken der RV (effiziente, kontinuierliche Überwachung) und der MBD (fundierte Ursachenanalyse) vereinigt werden.
Ein soundes (korrektes) Framework darstellt, bei dem der symbolische Monitor sicherstellt, dass die abgeleiteten Werte mit allen durch die Constraints definierten Welten konsistent sind.

Die Arbeit wird als Proof-of-Concept präsentiert, der die Machbarkeit der Nutzung von Lola für komplexe diagnostische Aufgaben demonstriert und eine theoretische Grundlage für zukünftige praktische Anwendungen in sicherheitskritischen Systemen bietet.