💻 computer science

mstlo: Efficient Online Monitoring of Signal Temporal Logic

Dit artikel introduceert mstlo, een hoogpresterende Rust-bibliotheek met Python-bindingen die efficiënt online monitoring van Signal Temporal Logic mogelijk maakt via een uniforme interface, een incrementeel dynamisch programmeringsalgoritme met caching en een ingebouwde domeinspecifieke taal, waarmee aanzienlijke schaalbaarheidsverbeteringen ten opzichte van bestaande hulpmiddelen worden aangetoond.

Oorspronkelijke auteurs: Andreas Kaag Thomsen, Niels Viggo Stark Madsen, Valdemar Tang Evans, Thomas David Wright, Lukas Esterle, Peter Gorm Larsen

Gepubliceerd 2026-05-27

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Andreas Kaag Thomsen, Niels Viggo Stark Madsen, Valdemar Tang Evans, Thomas David Wright, Lukas Esterle, Peter Gorm Larsen

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je de veiligheidsinspecteur bent voor een hogesnelheidstrein. Je taak is om in real-time de snelheidsmeter, temperatuurmeters en drukkleppen te bewaken. Je hebt een regelboek (de "Signal Temporal Logic" of STL) met voorschriften zoals: "Als de temperatuur boven de 100 graden komt, moet deze binnen 5 minuten weer onder de 90 graden dalen."

Het probleem met traditionele veiligheidsinspecteurs is dat ze vaak wachten tot de hele 5 minuten voorbij zijn voordat ze kunnen zeggen: "Oké, die regel is gevolgd," of "Oh nee, het is mislukt!" Tegen de tijd dat ze spreken, kan de trein al zijn gecrasht.

Maak kennis met mstlo (uitgesproken als "mistletoe").

Beschouw mstlo als een supersnelle, super slimme digitale inspecteur, gebouwd met de programmeertaal Rust (bekend om zijn uitzonderlijke snelheid en veiligheid) en verpakt in een vriendelijke Python-mantel zodat iedereen het kan gebruiken. Hieronder wordt uitgelegd hoe het werkt, met eenvoudige analogieën:

1. De superkracht van het "Vroegtijdige Vonnis"

De meeste inspecteurs wachten tot het hele verhaal zich heeft ontvouwen. mstlo is anders. Het maakt gebruik van een truc genaamd "short-circuiting".

De Analogie: Stel je een regel voor die zegt: "Je mag het vuur niet aanraken." Als je ziet dat iemand de hand uitstrekt en het vuur aanraakt, wacht je niet om te zien of ze hun hand binnen 5 seconden terugtrekken. Je schreeuwt direct "SCHENDING!"
In het Paper: Dit wordt Eager Qualitative semantiek genoemd. Als een regel wordt overtreden, stopt mstlo met wachten en geeft het je direct het antwoord, waardoor kostbare tijd wordt bespaard.

2. De kristallen bol met "Vage Intervallen"

Soms weet je het definitieve antwoord nog niet, maar wil je weten hoe dicht je bij een ramp zit.

De Analogie: In plaats van een simpele "Goed/Goedgekeurd" of "Slecht/Verworpen", geeft mstlo je een bereik, zoals een weersvoorspelling die zegt: "De temperatuur zal liggen tussen 80 en 120 graden."
- Als het laagste mogelijke getal in dat bereik nog veilig is, weet je dat je goed zit.
- Als het hoogste mogelijke getal gevaarlijk is, weet je dat je in de problemen zit.
- Als het bereik gemengd is, blijft het toezicht houden.
In het Paper: Dit wordt RoSI (Robust Satisfaction Intervals) genoemd. Het berekent een "veiligheidsmarge" die krimpt naarmate er meer data binnenkomt, waardoor je een genuanceerd beeld krijgt van hoe goed het systeem presteert zonder te wachten op het definitieve moment.

3. De truc met het "Schuivende Venster" (Het geheime ingrediënt)

Om regels te controleren zoals "Blijf de komende 10 minuten onder de snelheidslimiet", moet een trage computer elke seconde terugkijken naar de laatste 10 minuten aan data. Dat is alsof je elke keer dat je een nieuwe pagina draait, de laatste 10 pagina's van een boek opnieuw leest.

De Analogie: mstlo gebruikt een slimme wiskundige truc (het algoritme van Lemire) die fungeert als een schuivend venster. In plaats van alles opnieuw te lezen, update het alleen de "hoogste" en "laagste" waarden terwijl nieuwe data binnenkomt en oude data wegschuift. Het is als een transportband waarbij je alleen het nieuwe item dat binnenkomt controleert, niet de hele stapel.
In het Paper: Dit maakt het gereedschap ongelooflijk snel, vooral voor regels die ver in de toekomst kijken (grote "temporale diepte").

4. De "Magische Spreuk" (De DSL)

Het schrijven van complexe logische regels in code kan rommelig zijn en vatbaar voor typefouten.

De Analogie: mstlo biedt je een Domain-Specific Language (DSL). Denk hierbij aan een speciale syntaxis voor "magische spreuken". Je kunt een regel schrijven als G[0, 5] (temp < $MAX_TEMP) (wat betekent: "Altijd, gedurende 5 seconden, moet de temperatuur lager zijn dan MAX_TEMP").
Het Voordeel: Als je een typefout maakt in je spreuk, vangt de computer deze op voordat je de trein zelfs maar laat rijden (statische controle). Het stelt je ook in staat variabelen te vervangen (zoals het wijzigen van de temperatuurlimiet) zonder de hele spreuk opnieuw te hoeven schrijven.

5. Hoe snel is het?

De auteurs hebben mstlo getest tegen de beste bestaande tools (zoals een tool genaamd RTAMT).

Het Resultaat: mstlo is aanzienlijk sneller. Voor simpele regels is het ongeveer 10 tot 13 keer sneller. Voor complexe regels met diepe tijdsvensters kan het 39 keer sneller zijn.
Waarom? Omdat het is geschreven in Rust (een zeer efficiënte taal) en gebruikmaakt van de slimme "schuivende venster"-wiskundige trucs die hierboven werden genoemd, terwijl oudere tools vaak alles vanaf nul opnieuw berekenen of vertrouwen op langzamere talen.

Samenvatting

mstlo is een nieuw, hoogpresterend hulpmiddel dat engineers in staat stelt complexe systemen in real-time te bewaken. Het wacht niet tot het einde van het verhaal om je te vertellen of je gefaald hebt; het signaleert problemen het moment dat ze ontstaan, geeft je een "veiligheidsscore" terwijl je wacht, en doet dit alles met bliksemsnelheid dankzij slimme wiskundige trucs. Het is beschikbaar voor zowel Rust-ontwikkelaars als Python-gebruikers, waardoor het eenvoudig in moderne engineeringprojecten te integreren is.

Technische Samenvatting: mstlo – Efficiënte Online Monitoring van Signaal-temporele Logica

1. Probleemstelling

De toenemende implementatie van Cyber-Fysieke Systemen (CPS) vereist robuuste methoden om de correctheid tijdens de operatie te waarborgen. Runtime Verification (RV) adresseert dit door systeemgedrag in real-time te monitoren tegen formeel gespecificeerde eigenschappen. Signaal-temporele logica (STL) is een standaardtaal voor het specificeren van timingbeperkingen en veiligheidsvereisten over reëelwaardige continue-tijdsignalen.

Echter, bestaande online monitoringtools staan voor aanzienlijke uitdagingen:

Prestatiebeperkingen: Monitoren moeten zeer efficiënt zijn om latentie te minimaliseren en ervoor te zorgen dat het verificatieproces niet achterblijft bij het systeem. Naïeve benaderingen die formules bij elke tijdstap vanaf nul opnieuw evalueren, schalen slecht met formulecomplexiteit en signaallengte.
Semantische beperkingen: De meeste tools beperken gebruikers tot één evaluatiestrategie (bijvoorbeeld alleen vertraagde kwantitatieve semantiek), wat de mogelijkheid beperkt om af te wegen tussen uitspraakexpressiviteit, latentie en prestaties.
Gebruiksvriendelijkheid en Integratie: Er is een gebrek aan tools die een uniforme interface bieden voor meerdere STL-semantiek, terwijl ze tegelijkertijd een ingebouwde Domeinspecifieke Taal (DSL) bieden voor statische syntaxiscontrole en eenvoudige integratie in moderne ecosystemen zoals Rust en Python.

2. Methodologie

De auteurs presenteren mstlo (mistletoe), een hoogpresterende bibliotheek geïmplementeerd in Rust met Python-bindingen, ontworpen voor efficiënte online monitoring van STL.

Kernalgoritmische Aanpak

Incrementele Monitoring: In plaats van de volledige formule bij elke tijdstap opnieuw te evalueren, hanteert mstlo een bottom-up dynamisch programmeringsbenadering. De specificatie wordt weergegeven als een Abstracte Syntaxboom (AST) waarbij elke operator een cache van tussenresultaten van zijn kind-operatoren bijhoudt.
Geoptimaliseerde Temporele Operatoren: Voor globaal ( $\square$ ) en uiteindelijk ( $\diamond$ ) operatoren, die fungeren als schuifvenster-minimum- en maximumberekeningen, implementeert de uitvoering een versie van Lemire's algoritme. Deze optimalisatie vermindert aanzienlijk het geheugengebruik en de rekentijd voor niet-RoSI-semantiek.
Unificatie van Semantische Interface: De bibliotheek ondersteunt vier verschillende semantische definities via één generieke monitoringkern met behulp van Rust-traits voor zero-cost statische dispatch:
1. Vertraagde Kwalitatieve: Standaard Booleaanse voldoening die volledige signaalresolutie vereist tot aan de temporele diepte.
2. Vertraagde Kwantitatieve: Standaard robuustheidsemantiek die een reëelwaardige score berekent.
3. Dringende Kwalitatieve: Maakt gebruik van monotonie om vroege Booleaanse uitspraken te genereren (short-circuiting) over gedeeltelijke sporen (bijvoorbeeld direct false retourneren bij de eerste schending van een $\square$ -eigenschap).
4. Robuuste Voldoening Intervallen (RoSI): Berekent een interval $[\rho_{min}, \rho_{max}]$ dat alle mogelijke toekomstige robuustheidswaarden voor gedeeltelijke sporen omvat, en convergeert naar één enkele waarde zodra het volledige horizon is waargenomen.

Implementatiekenmerken

Ingebouwde DSL: mstlo biedt een DSL beschikbaar als een compile-time procedurele macro (stl!) voor Rust en een runtime-parser. Dit ondersteunt statische syntaxiscontrole, geparametriseerde formules (via symbolische variabelen voorafgegaan door $) en syntactisch suiker voor veelvoorkomende patronen.
Builder-patroon: Monitoren worden geïnstantieerd met behulp van een builder-patroon om formules, semantiek, algoritmische modi (Naïef vs. Incrementeel), variabele contexten en synchronisatiestrategieën te configureren (bijvoorbeeld het afhandelen van asynchrone signaalinterpolatie).
Cross-taal Ondersteuning: De kernengine is geschreven in Rust, met Python-bindingen (mstlo-python) die de engine omhullen om adoptie in het Python-ecosysteem en interactieve workflows (bijvoorbeeld Jupyter Notebooks) te faciliteren.

3. Belangrijkste Bijdragen

Unificatie van Kader: Het eerste specifieke hulpmiddel voor online monitoring dat meerdere STL-semantiek (Vertraagde Kwalitatieve/Kwantitatieve, Dringende Kwalitatieve en RoSI) ondersteunt binnen één architectuur.
Hoogpresterend Algoritme: Een incrementeel monitoringalgoritme dat gebruikmaakt van per-operator caching en Lemire's schuifvenster-optimalisatie, waardoor schaalbaarheid wordt bereikt voor formules met grote temporele diepten.
Ontwikkelaarservaring: Een ingebouwde DSL met statische syntaxiscontrole in Rust en een runtime-parser, naast Python-bindingen voor bredere toegankelijkheid.
Reproduceerbare Benchmarking: Een uitgebreide benchmark-suite die prestaties evalueert over verschillende semantiek, formulestructuren en invoersignalen.

4. Experimentele Resultaten

Benchmarks werden uitgevoerd op een Apple MacBook M4 Pro met behulp van een chirp-golf signaal bemonsterd op 1 Hz over 20.000 samples. Drie formules ( $\phi_1, \phi_2, \phi_3$ ) met variërende temporele diepten en nesting werden geëvalueerd.

Schaalbaarheid:
- Voor Vertraagde en Dringende Kwalitatieve semantiek bleef de uitvoeringstijd voor de $\square$ -operator constant, ongeacht de temporele bovengrens $b$ , dankzij Lemire's optimalisatie.
- De uitvoeringstijd voor de $U$ (Tot) operator schaalde lineair met $b$ , aangezien deze niet profiteert van dezelfde optimalisatie.
- RoSI-semantiek toonde lineaire schaalbaarheid voor $\square$ en kwadratische schaalbaarheid voor $U$ , wat de hogere rekentijd weerspiegelt voor het onderhouden van intervallen.
Prestatievergelijking:
- mstlo (Rust) vertoonde aanzienlijk lagere uitvoeringstijden in vergelijking met RTAMT (een toonaangevend Python-gebaseerd hulpmiddel met een C++-backend).
- Voor eenvoudige formules ( $\phi_1$ ) was mstlo-python 10–13 keer sneller dan RTAMT.
- Voor complexe geneste formules ( $\phi_3$ ) was mstlo-python ongeveer 39 keer sneller.
- Het prestatieverschil wordt toegeschreven aan mstlo's algoritmische optimalisaties (caching) en ondiepe Python-bindingen in vergelijking met RTAMT's zwaardere afhankelijkheid van Python.
Overhead: De Python-bindingen introduceerden slechts een kleine overhead (1–1,7 $\times$ ) in vergelijking met de native Rust-implementatie.

5. Betekenis en Claims

Het artikel beweert dat mstlo de staat van de kunst in STL-monitoring vooruitbrengt door:

Het Kruis te Overbruggen: Het bieden van een gebruiksvriendelijk, specifiek online kader voor zowel Rust als Python dat meerdere evaluatiesemantiek ondersteunt, en zo het gebrek aan hulpmiddelen die geoptimaliseerd zijn voor online STL-monitoring aanpakt.
Architecturale Vooruitgang: Het introduceren van architecturale verbeteringen die op maat zijn gemaakt voor hoogpresterende online monitoring, specifiek de combinatie van incrementele algoritmen met Lemire's optimalisatie.
Gebruiksvriendelijkheid: Het verbeteren van de gebruiksvriendelijkheid door een ingebouwde DSL die statische syntaxiscontrole en parametrisatie biedt, waardoor de instapdrempel voor het specificeren van complexe temporele eigenschappen wordt verlaagd.
Praktische Toepassing: Het hulpmiddel is al met succes gebruikt in een educatieve context ("Engineering Digital Twins"-cursus) om Runtime Verification in praktische situaties te onderwijzen.

De auteurs merken op dat toekomstig werk onder meer bestaat uit het uitbreiden van de implementatie naar platformen voor ingebouwde systemen, waar geheugen- en rekentijdbeperkingen aanvullende eisen opleggen.