💻 computer science

mstlo: Efficient Online Monitoring of Signal Temporal Logic

Dieser Beitrag stellt mstlo vor, eine leistungsstarke Rust-Bibliothek mit Python-Bindings, die eine effiziente Online-Überwachung von Signal-Temporal-Logik über eine einheitliche Schnittstelle, einen inkrementellen dynamischen Programmieralgorithmus mit Caching und eine eingebettete domänenspezifische Sprache ermöglicht und damit signifikante Skalierbarkeitsverbesserungen gegenüber bestehenden Werkzeugen demonstriert.

Ursprüngliche Autoren: Andreas Kaag Thomsen, Niels Viggo Stark Madsen, Valdemar Tang Evans, Thomas David Wright, Lukas Esterle, Peter Gorm Larsen

Veröffentlicht 2026-05-27

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Andreas Kaag Thomsen, Niels Viggo Stark Madsen, Valdemar Tang Evans, Thomas David Wright, Lukas Esterle, Peter Gorm Larsen

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 Sicherheitsinspektor für einen Hochgeschwindigkeitszug. Ihre Aufgabe besteht darin, das Tachometer, die Temperaturanzeigen und die Druckventile in Echtzeit zu überwachen. Sie verfügen über ein Regelbuch (die „Signal Temporal Logic" oder STL), das Aussagen wie folgende enthält: „Wenn die Temperatur über 100 Grad steigt, muss sie innerhalb von 5 Minuten wieder unter 90 fallen."

Das Problem mit herkömmlichen Sicherheitsinspektoren besteht darin, dass sie oft warten, bis die gesamten 5 Minuten vergangen sind, bevor sie sagen können: „Okay, diese Regel wurde eingehalten" oder „Oh nein, sie wurde verletzt!" Bis sie sprechen, könnte der Zug bereits abgestürzt sein.

Hier kommt mstlo (ausgesprochen „Mistelzweig") ins Spiel.

Stellen Sie sich mstlo als einen superschnellen, superscharfsinnigen digitalen Inspektor vor, der mit der Programmiersprache Rust (bekannt für ihre extreme Geschwindigkeit und Sicherheit) entwickelt und in eine freundliche Python-Hülle gehüllt wurde, damit jeder ihn nutzen kann. So funktioniert es, unter Verwendung einfacher Analogien:

1. Die Superkraft des „frühen Urteils"

Die meisten Inspektoren warten darauf, dass sich die gesamte Geschichte entfaltet. mstlo ist anders. Es verwendet einen Trick namens „Kurzschluss" (short-circuiting).

Die Analogie: Stellen Sie sich eine Regel vor, die besagt: „Sie dürfen das Feuer nicht berühren." Wenn Sie sehen, wie jemand die Hand ausstreckt und das Feuer berührt, warten Sie nicht ab, ob er seine Hand innerhalb von 5 Sekunden wieder zurückzieht. Sie schreien sofort „VERLETZUNG!" aus.
Im Papier: Dies wird als Eager Qualitative-Semantik bezeichnet. Wenn eine Regel verletzt wird, hört mstlo auf zu warten und liefert Ihnen sofort die Antwort, wodurch wertvolle Zeit gespart wird.

2. Die Kristallkugel des „unscharfen Intervalls"

Manchmal kennen Sie die endgültige Antwort noch nicht, aber Sie möchten wissen, wie nah Sie am Desaster sind.

Die Analogie: Anstatt eines einfachen „Bestanden/Nicht bestanden" liefert mstlo Ihnen einen Bereich, ähnlich wie eine Wettervorhersage, die sagt: „Die Temperatur wird zwischen 80 und 120 Grad liegen."
- Wenn die niedrigste mögliche Zahl in diesem Bereich noch sicher ist, wissen Sie, dass alles in Ordnung ist.
- Wenn die höchste mögliche Zahl gefährlich ist, wissen Sie, dass Sie in Schwierigkeiten stecken.
- Wenn der Bereich gemischt ist, beobachtet es weiter.
Im Papier: Dies wird als RoSI (Robust Satisfaction Intervals) bezeichnet. Es berechnet einen „Sicherheitspuffer", der schrumpft, je mehr Daten eintreffen, und bietet Ihnen eine differenzierte Sicht darauf, wie gut das System funktioniert, ohne auf den finalen Moment warten zu müssen.

3. Der Trick des „gleitenden Fensters" (Das Geheimrezept)

Um Regeln wie „Bleiben Sie für die nächsten 10 Minuten unter der Geschwindigkeitsbegrenzung" zu überprüfen, muss ein langsamer Computer jede einzelne Sekunde auf die letzten 10 Minuten Daten zurückblicken. Das ist so, als würde man jedes Mal, wenn man eine neue Seite umblättert, die letzten 10 Seiten eines Buches erneut lesen.

Die Analogie: mstlo verwendet einen cleveren mathematischen Trick (Lemire-Algorithmus), der wie ein gleitendes Fenster funktioniert. Anstatt alles erneut zu lesen, aktualisiert es einfach die „höchsten" und „niedrigsten" Werte, während neue Daten hereinschieben und alte Daten herausschieben. Es ist wie ein Förderband, auf dem Sie nur den neu ankommenden Artikel prüfen, nicht den gesamten Stapel.
Im Papier: Dies macht das Werkzeug unglaublich schnell, insbesondere für Regeln, die weit in die Zukunft blicken (große „temporale Tiefe").

4. Der „magische Zauber" (Die DSL)

Das Schreiben komplexer Logikregeln im Code kann unübersichtlich sein und anfällig für Tippfehler.

Die Analogie: mstlo bietet Ihnen eine domainspezifische Sprache (DSL). Stellen Sie sich dies als eine spezielle Syntax für „magische Zauber" vor. Sie können eine Regel wie G[0, 5] (temp < $MAX_TEMP) schreiben (was bedeutet: „Immer, für 5 Sekunden, muss die Temperatur unter MAX_TEMP liegen").
Der Vorteil: Wenn Sie einen Tippfehler in Ihrem Zauber machen, fängt der Computer ihn bevor Sie den Zug überhaupt starten (statische Prüfung). Es ermöglicht Ihnen auch, Variablen auszutauschen (wie das Ändern der Temperaturgrenze), ohne den gesamten Zauber neu schreiben zu müssen.

5. Wie schnell ist es?

Die Autoren haben mstlo gegen die besten bestehenden Tools getestet (wie ein Tool namens RTAMT).

Das Ergebnis: mstlo ist deutlich schneller. Bei einfachen Regeln ist es etwa 10 bis 13 Mal schneller. Bei komplexen Regeln mit tiefen Zeitfenstern kann es 39 Mal schneller sein.
Warum? Weil es in Rust geschrieben ist (eine sehr effiziente Sprache) und die oben genannten intelligenten mathematischen Tricks des „gleitenden Fensters" verwendet, während ältere Tools oft alles von Grund auf neu berechnen oder auf langsamere Sprachen angewiesen sind.

Zusammenfassung

mstlo ist ein neues, hochleistungsfähiges Werkzeug, das Ingenieuren ermöglicht, komplexe Systeme in Echtzeit zu überwachen. Es wartet nicht nur auf das Ende der Geschichte, um Ihnen zu sagen, ob Sie versagt haben; es erkennt Probleme im Moment ihres Auftretens, liefert Ihnen während des Wartens einen „Sicherheitswert" und tut all dies mit Blitzgeschwindigkeit unter Verwendung intelligenter mathematischer Tricks. Es ist sowohl für Rust-Entwickler als auch für Python-Nutzer verfügbar, was es einfach macht, es in moderne Ingenieursprojekte einzubinden.

Technische Zusammenfassung: mstlo – Effizientes Online-Monitoring von Signal-Temporal-Logik

1. Problemstellung

Die zunehmende Verbreitung von Cyber-Physical Systems (CPS) erfordert robuste Methoden zur Sicherstellung der Korrektheit während des Betriebs. Die Laufzeitverifikation (Runtime Verification, RV) adressiert dies durch die Überwachung des Systemverhaltens in Echtzeit gegen formal definierte Eigenschaften. Signal-Temporal-Logik (STL) ist eine Standardsprache zur Spezifikation von Zeitbeschränkungen und Sicherheitsanforderungen über reellwertige kontinuierliche Signale.

Herkömmliche Online-Monitoring-Tools stehen jedoch vor erheblichen Herausforderungen:

Leistungsbeschränkungen: Monitore müssen hocheffizient sein, um Latenzen zu minimieren und sicherzustellen, dass der Verifikationsprozess nicht hinter dem System zurückbleibt. Naive Ansätze, die Formeln zu jedem Zeitpunkt neu von Grund auf auswerten, skalieren schlecht mit der Komplexität der Formel und der Signallänge.
Semantische Einschränkungen: Die meisten Tools beschränken Benutzer auf eine einzige Auswertungsstrategie (z. B. nur verzögerte quantitative Semantik), was die Fähigkeit einschränkt, Kompromisse zwischen der Ausdruckskraft der Urteile, der Latenz und der Leistung zu finden.
Benutzerfreundlichkeit und Integration: Es fehlt an Tools, die eine einheitliche Schnittstelle für mehrere STL-Semantiken bieten und gleichzeitig eine eingebettete domänenspezifische Sprache (DSL) für statische Syntaxprüfungen und eine einfache Integration in moderne Ökosysteme wie Rust und Python bereitstellen.

2. Methodik

Die Autoren stellen mstlo (mistletoe) vor, eine hochleistungsfähige Bibliothek, die in Rust implementiert und mit Python-Bindings versehen ist, entwickelt für effizientes Online-Monitoring von STL.

Kernalgorithmischer Ansatz

Inkrementelles Monitoring: Anstatt die gesamte Formel zu jedem Zeitpunkt neu auszuwerten, verwendet mstlo einen Bottom-up-Dynamischen-Programmierungs-Ansatz. Die Spezifikation wird als Abstrakter Syntaxbaum (AST) dargestellt, wobei jeder Operator einen Cache für Zwischenergebnisse seiner Kindoperatoren verwaltet.
Optimierte Temporaloperatoren: Für die Operatoren „globally" ( $\square$ ) und „eventually" ( $\diamond$ ), die als gleitende Fenster-Minimum- und Maximum-Berechnungen fungieren, integriert die Implementierung eine Version des Lemire-Algorithmus. Diese Optimierung reduziert den Speicherbedarf und die Rechenzeit für nicht-RoSI-Semantiken erheblich.
Einheitliche Semantik-Schnittstelle: Die Bibliothek unterstützt vier verschiedene semantische Definitionen über einen einzigen generischen Monitoring-Kern, der Rust-Traits für Zero-Cost-statische Dispatch verwendet:
1. Verzögert Qualitativ: Standard-Boolesche Erfüllungsprüfung, die eine vollständige Signalauflösung bis zur temporalen Tiefe erfordert.
2. Verzögert Quantitativ: Standard-Robustheitsssemantik, die einen reellwertigen Score berechnet.
3. Eager Qualitativ: Nutzt Monotonie, um frühe boolesche Urteile (Short-Circuiting) über partielle Spuren auszugeben (z. B. sofortiges Zurückgeben von „falsch" bei der ersten Verletzung einer $\square$ -Eigenschaft).
4. Robust Satisfaction Intervals (RoSI): Berechnet ein Intervall $[\rho_{min}, \rho_{max}]$ , das alle möglichen zukünftigen Robustheitswerte für partielle Spuren einschließt und sich zu einem einzigen Wert konvergiert, sobald der vollständige Horizont beobachtet wurde.

Implementierungsfunktionen

Eingebettete DSL: mstlo bietet eine DSL, die als Compile-time-prozedurales Makro (stl!) für Rust und als Laufzeitparser verfügbar ist. Dies unterstützt statische Syntaxprüfungen, parametrisierte Formeln (über mit $ präfixierte symbolische Variablen) und syntaktischen Zucker für gängige Muster.
Builder-Muster: Monitore werden unter Verwendung des Builder-Musters instanziiert, um Formeln, Semantiken, algorithmische Modi (Naiv vs. Inkrementell), Variablenkontexte und Synchronisationsstrategien (z. B. Behandlung asynchroner Signalinterpolation) zu konfigurieren.
Sprachübergreifende Unterstützung: Die Kernengine ist in Rust geschrieben, wobei Python-Bindings (mstlo-python) die Engine kapseln, um die Adoption im Python-Ökosystem und in interaktiven Workflows (z. B. Jupyter Notebooks) zu erleichtern.

3. Hauptbeiträge

Einheitliches Framework: Das erste dedizierte Tool für Online-Monitoring, das mehrere STL-Semantiken (Verzögert Qualitativ/Quantitativ, Eager Qualitativ und RoSI) innerhalb einer einzigen Architektur unterstützt.
Hochleistungs-Algorithmus: Ein inkrementeller Monitoring-Algorithmus, der pro-Operator-Caching und die gleitende Fenster-Optimierung nach Lemire nutzt und Skalierbarkeit für Formeln mit großen temporalen Tiefen erreicht.
Entwicklererfahrung: Eine eingebettete DSL mit statischer Syntaxprüfung in Rust und einem Laufzeitparser sowie Python-Bindings für breitere Zugänglichkeit.
Reproduzierbare Benchmarking: Eine umfassende Benchmark-Suite zur Bewertung der Leistung über verschiedene Semantiken, Formelstrukturen und Eingangssignale hinweg.

4. Experimentelle Ergebnisse

Die Benchmarks wurden auf einem Apple MacBook M4 Pro mit einem Chirp-Wave-Signal durchgeführt, das mit 1 Hz über 20.000 Samples abgetastet wurde. Drei Formeln ( $\phi_1, \phi_2, \phi_3$ ) mit variierenden temporalen Tiefen und Verschachtelungen wurden evaluiert.

Skalierbarkeit:
- Für verzögerte und eager qualitative Semantiken blieb die Ausführungszeit für den $\square$ -Operator unabhängig von der temporalen oberen Schranke $b$ konstant, dank der Lemire-Optimierung.
- Die Ausführungszeit für den $U$ -Operator (Until) skalierte linear mit $b$ , da er nicht von derselben Optimierung profitiert.
- Die RoSI-Semantik zeigte eine lineare Skalierung für $\square$ und eine quadratische Skalierung für $U$ , was die höheren Rechenkosten der Intervallverwaltung widerspiegelt.
Leistungsvergleich:
- mstlo (Rust) zeigte deutlich niedrigere Ausführungszeiten im Vergleich zu RTAMT (ein führendes Python-basiertes Tool mit C++-Backend).
- Für einfache Formeln ( $\phi_1$ ) war mstlo-python 10–13-mal schneller als RTAMT.
- Für komplexe verschachtelte Formeln ( $\phi_3$ ) war mstlo-python etwa 39-mal schneller.
- Die Leistungslücke wird auf die algorithmischen Optimierungen von mstlo (Caching) und die flachen Python-Bindings im Vergleich zur stärkeren Abhängigkeit von Python bei RTAMT zurückgeführt.
Overhead: Die Python-Bindings führten nur einen geringen Overhead (1–1,7 $\times$ ) im Vergleich zur nativen Rust-Implementierung ein.

5. Bedeutung und Behauptungen

Die Autoren behaupten, dass mstlo den Stand der Technik im STL-Monitoring durch folgende Punkte voranbringt:

Überbrückung der Lücke: Bereitstellung eines einfach zu bedienenden, dedizierten Online-Frameworks für sowohl Rust als auch Python, das mehrere Auswertungssemantiken unterstützt und die Knappheit an Tools adressiert, die für Online-STL-Monitoring optimiert sind.
Architektonischer Fortschritt: Einführung architektonischer Verbesserungen, die speziell für hochleistungsfähiges Online-Monitoring entwickelt wurden, insbesondere die Kombination von inkrementellen Algorithmen mit der Lemire-Optimierung.
Benutzerfreundlichkeit: Verbesserung der Benutzerfreundlichkeit durch eine eingebettete DSL, die statische Syntaxprüfungen und Parametrisierung bietet und so die Einstiegshürde für die Spezifikation komplexer temporaler Eigenschaften senkt.
Praktische Anwendung: Das Tool wurde bereits erfolgreich in einem Bildungskontext („Engineering Digital Twins"-Kurs) eingesetzt, um Laufzeitverifikation in praktischen Szenarien zu lehren.

Die Autoren weisen darauf hin, dass zukünftige Arbeiten die Erweiterung der Implementierung auf Plattformen für eingebettete Systeme umfassen, wo Speicher- und Rechenbeschränkungen zusätzliche Anforderungen stellen.