💻 computer science

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

Queste note di lezione presentano i fondamenti teorici degli automati, temporali-logici ed epistemici della verifica a runtime, trattando formalismi di specifica, diagnosi, opacità e monitorabilità per spiegare come l'analisi offline costruisca monitor per sistemi parzialmente osservabili, affrontando al contempo le sfide delle estensioni temporali in contesti real-time.

Autori originali: Benedikt Bollig

Pubblicato 2026-04-30

📖 6 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Benedikt Bollig

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina di dover capire se una macchina misteriosa funziona correttamente. Non puoi vedere all'interno della macchina (è una "scatola nera") e non puoi fermarla per smontarla. Puoi solo osservare ciò che ne esce: un flusso di luci, suoni o punti dati.

Questo è il mondo della Verifica a Runtime. Invece di cercare di prevedere ogni possibile cosa che la macchina potrebbe fare prima che inizi (il che è come cercare di mappare ogni possibile percorso in un labirinto prima di entrarci), la verifica a runtime osserva la macchina mentre funziona e lancia un allarme se rileva qualcosa di sbagliato.

Questa serie di lezioni di Benedikt Bollig esplora come farlo quando si ha incertezza. Forse la macchina nasconde alcune delle sue azioni, o forse non si sa esattamente come funziona. Gli appunti utilizzano un tipo speciale di logica (chiamata "logica epistemica") per tracciare esattamente cosa l'osservatore sa e cosa non sa in ogni dato momento.

Ecco una panoramica delle idee principali utilizzando analogie quotidiane:

1. I Tre Livelli di Conoscenza della Macchina

Il documento descrive tre modi in cui potremmo interagire con un sistema:

Scatola Bianca: Hai i progetti. Sai esattamente come gira ogni ingranaggio. È come avere il manuale e il motore aperto. Puoi verificare se la macchina funzionerà perfettamente prima ancora di accenderla (Model Checking).
Scatola Grigia: Hai un manuale approssimativo. Dice "forse succede questo, forse succede quello". Ci sono lacune. Non puoi essere sicuro al 100% di cosa accadrà, quindi devi osservarla mentre funziona per esserne certo.
Scatola Nera: Non hai alcun manuale. Vedi solo l'output. Devi indovinare cosa succede all'interno basandoti su ciò che vedi.

2. I Tre Giochi Principali: Diagnosi, Opacità e Monitoraggio

Il documento tratta tre problemi diversi come variazioni dello stesso gioco: "Cosa posso dedurre da ciò che vedo?".

Diagnosi: Il Detective

L'Obiettivo: Vuoi sapere se è accaduta una specifica cosa negativa (un "guasto").
L'Analogia: Immagina una guardia di sicurezza che sorveglia una cassaforte bancaria. La cassaforte ha un allarme silenzioso (il guasto) che nessuno sente. La guardia vede solo persone che entrano ed escono.
- Se una persona entra, la guardia non sa se ha rubato qualcosa.
- Ma se la guardia vede una persona uscire con un sacchetto d'oro, sa con certezza che il furto è avvenuto.
- La Diagnosi è la capacità di dire: "Sono sicuro al 100% che il furto sia avvenuto", anche se non hai visto il furto stesso, solo le conseguenze. Il documento chiede: La guardia può sempre capirlo alla fine?

Opacità: La Spia

L'Obiettivo: Vuoi nascondere un segreto. Vuoi assicurarti che l'osservatore non sappia mai se il segreto è accaduto.
L'Analogia: Immagina una spia che cerca di introdurre di nascosto un messaggio segreto in una stanza. L'osservatore sta guardando la porta.
- Se la spia entra, l'osservatore vede "Qualcuno è entrato".
- Se una persona normale entra, l'osservatore vede anche "Qualcuno è entrato".
- L'Opacità è l'arte di far sembrare l'ingresso della spia esattamente come l'ingresso di una persona normale. Se l'osservatore non può mai distinguere la differenza, il segreto è "opaco" (nascosto). Il documento chiede: È possibile progettare un sistema in cui il segreto della spia sia sempre nascosto?

Monitoraggio: Il Vigile Urbano

L'Obiettivo: Dare un verdetto sul comportamento del sistema mentre accade.
L'Analogia: Un vigile urbano che osserva un'auto.
- Verdetto "Vero": L'auto sta guidando perfettamente. Il vigile sa che non si schianterà mai.
- Verdetto "Falso": L'auto ha appena passato un semaforo rosso. Il vigile sa che ha infranto le regole.
- Verdetto "?": L'auto sta attualmente guidando normalmente, ma potrebbe passare un semaforo rosso tra 5 secondi. Il vigile non lo sa ancora.
- Il documento esplora quando un vigile può smettere di dire "?" e iniziare a dire "Vero" o "Falso". A volte, non importa quanto a lungo si osserva, non si può mai essere sicuri (il verdetto rimane "?").

3. Il Problema della "Conoscenza"

Il cuore del documento è che l'incertezza è il nemico principale.

Se vedi lampeggiare una luce, sai se significa "Errore" o solo "Controllo di Sistema"?
Il documento utilizza la Logica Epistemica (la logica della conoscenza) per mappare questo aspetto. Tratta la mente dell'osservatore come una mappa.
- Se la mappa mostra solo un possibile percorso, l'osservatore sa la verità.
- Se la mappa mostra due percorsi (uno con un errore, uno senza), l'osservatore è incerto.

4. La Svolta: Il Tempo Cambia Tutto

L'ultimo capitolo aggiunge il Tempo al mix. Immagina che la macchina non faccia solo cose; le faccia a velocità specifiche.

Senza Tempo: Se aspetti abbastanza a lungo, potresti capire la verità.
Con Tempo: Le cose si complicano.
- Diagnosi: Potresti aver bisogno di sapere che un errore è accaduto entro 5 secondi. Se il sistema è lento, potresti perdere la finestra temporale per essere sicuro.
- Opacità: Nascondere un segreto diventa più difficile se la tempistica degli eventi lo rivela.
- La Grande Cattiva Notizia: Il documento rivela un limite spaventoso. Nel mondo del tempo, se cerchi di combinare "controllare l'orologio" con "capire cosa sa l'osservatore", la matematica si rompe. Diventa indecidibile. Questo significa che non esiste un algoritmo che possa sempre dirti se un sistema temporizzato è sicuro o opaco. È come cercare di risolvere un puzzle in cui i pezzi cambiano forma mentre li guardi.

Riepilogo

Questo documento è una guida per costruire "osservatori intelligenti" per sistemi complessi.

Insegna come costruire Diagnosatori (detective) e Monitor (vigili urbani) che funzionano anche quando non possono vedere tutto.
Dimostra che la Diagnosi (trovare guasti) e l'Opacità (nascondere segreti) sono due facce della stessa medaglia.
Dimostra che mentre possiamo risolvere questi enigmi per sistemi semplici, aggiungere il Tempo rende alcuni di essi impossibili da risolvere perfettamente.

La conclusione fondamentale è che in un mondo di informazioni parziali, non possiamo sempre conoscere la verità immediatamente. Dobbiamo essere intelligenti riguardo a cosa possiamo sapere, quando possiamo saperlo e quando dobbiamo accettare che non lo sapremo mai.

Riepilogo Tecnico: Verifica a Runtime, Monitoraggio, Conoscenza e Incertezza

1. Enunciato del Problema

La Verifica a Runtime (RV) è una tecnica di verifica leggera progettata per analizzare le esecuzioni di un sistema mentre avvengono, piuttosto che esplorare un modello completo del sistema offline (come nel Model Checking). La sfida centrale affrontata in queste note di lezione è l'incertezza che deriva da:

Osservabilità Parziale: Gli osservatori (agenti) spesso non possono vedere tutte le azioni del sistema o gli stati interni (sistemi a scatola nera o grigia).
Esecuzioni Infinite: I sistemi sono reattivi e producono tracce infinite, ma a runtime sono disponibili solo prefissi finiti.
Limiti Epistemici: Un osservatore potrebbe non sapere se una proprietà vale, è valsa o varrà basandosi esclusivamente sulla storia osservata.

Il documento mira a fornire un quadro unificante per tre problemi di verifica distinti ma correlati—Diagnosi (rilevamento di guasti), Opacità (nascondimento di segreti) e Monitoraggio (verifica di proprietà)—utilizzando la Logica Temporale Epistemica. Inoltre, indaga come questi concetti si estendano ai sistemi Real-Time (Temporizzati), dove l'introduzione di operatori temporali e di conoscenza crea sfide algoritmiche significative.

2. Metodologia

L'autore adotta un approccio formale, basato sulla teoria degli automi, fondato sulla Logica Temporale Lineare Epistemica (LTL $\sim$ ).

2.1 Quadro Formale

Modello di Sistema: I sistemi sono modellati come Automi di Büchi (per parole infinite) o Automi di Büchi Temporizzati (per real-time).
Osservazione: Gli agenti osservano una proiezione della traccia di esecuzione globale basata su un sottoinsieme di proposizioni osservabili ( $AP_a \subseteq AP$ ). L'indistinguibilità ( $\sim_a$ ) è definita tramite il ricordo perfetto delle sequenze di osservazione.
Logica: La logica estende l'LTL standard con:
- Operatori Epistemici: $K_a \phi$ ("L'agente $a$ conosce $\phi$ ").
- Operatori Temporali: Operatori di futuro stretto ( $U^+$ ) e passato ( $S^+$ ), che permettono di ragionare su posizioni specifiche nella traccia.
- Semantica della Conoscenza: $K_a \phi$ vale in un punto se $\phi$ è vero in tutte le esecuzioni indistinguibili dall'osservazione corrente.

2.2 Meccanismi Fondamentali

Monitor della Conoscenza: Il documento costruisce Automi Finiti Deterministici (DFA) (o macchine di Moore) che tracciano l'insieme degli stati di sistema possibili (stati di credenza) coerenti con la storia delle osservazioni. Questi monitor producono verdetto basandosi sul fatto che la proprietà sia nota come vera, falsa o indeterminata.
Trasduttori: Per risolvere problemi di model checking, l'autore costruisce trasduttori (Sistema, Formula). Questi automi eseguono in parallelo con il sistema, producendo il valore di verità della formula ad ogni passo.
Costruzioni "Twin-Plant": Per la diagnosticabilità, il metodo prevede la simulazione parallela di due esecuzioni del sistema (una con guasto, una senza guasto) per verificare se rimangono indistinguibili dal punto di vista osservativo oltre un certo ritardo.

3. Contributi Chiave

3.1 Unificazione dei Problemi di Verifica

Il documento dimostra che Diagnosi, Opacità e Monitoraggio possono essere espressi uniformemente come proprietà temporali epistemiche sullo stesso modello di sistema:

Diagnosi: $G(\text{guasto} \to F K_a \text{Passato}(\text{guasto}))$ . L'agente alla fine sa che si è verificato un guasto.
Opacità: $G \neg K_a \text{Passato}(\text{segreto})$ . L'agente non sa mai che si è verificato un segreto.
Monitoraggio: Un sistema di verdetto a tre valori (Vero, Falso, ?) derivato da $K_a \hat{\phi}$ , $K_a \neg \hat{\phi}$ , o nessuno dei due.

3.2 Risultati Algoritmici (Ambiente Non Temporizzato)

Decidibilità: Il model checking per LTL $\sim$ è decidibile. La costruzione di monitor della conoscenza permette la verifica effettiva della diagnosticabilità e dell'opacità.
Complessità:
- Il model checking LTL standard è PSPACE-completo.
- L'aggiunta di operatori epistemici porta a un esplodimento di complessità non elementare dovuto alla costruzione iterata dell'insieme delle parti richiesta per gli stati di credenza sotto ricordo perfetto.
- La Diagnosticabilità (verifica se un sistema è diagnosticabile) può essere decisa in Tempo Polinomiale (P) per ritardi limitati, nonostante la logica generale sia più complessa.
- L'Opacità risulta essere PSPACE-completa.

3.3 Monitorabilità

Il documento definisce la Monitorabilità come la proprietà strutturale che garantisce che per ogni prefisso di osservazione esista una continuazione finita che porta a un verdetto definitivo.

Sicurezza e Co-sicurezza: Queste classi classiche sono dimostrate monitorabili.
LTL Generale: La monitorabilità è decidibile ma PSPACE-dura. La classe delle formule monitorabili contiene strettamente sicurezza/co-sicurezza ma è un sottoinsieme stretto di tutto l'LTL.

3.4 Sistemi Temporizzati (Real-Time)

L'ultimo capitolo estende la teoria agli Automi Temporizzati e alla Logica Temporale Temporizzata (TLTL).

Decidibilità del Model Checking Temporizzato: Decidibile per TLTL (senza conoscenza) utilizzando l'astrazione per regioni.
Indecidibilità della Logica Temporizzata Epistemica: L'aggiunta di operatori di conoscenza alla logica temporizzata ( $TLTL\sim$ ) rende il model checking indecidibile. Ciò è dimostrato tramite riduzione dal problema dell'universalità per automi temporizzati.
Opacità Temporizzata: Di conseguenza, l'opacità temporizzata è indecidibile.
Monitorabilità Temporizzata:
- Frammento Passato: La monitorabilità temporizzata per formule contenenti solo passato è decidibile.
- TLTL Completo: La monitorabilità dei linguaggi definiti da Automi Temporizzati è indecidibile.

4. Riepilogo dei Risultati Chiave

Problema	Contesto	Complessità / Stato	Insight Chiave
Model Checking	Non Temporizzato (LTL $\sim$ )	Decidibile (Non elementare)	Gli operatori di conoscenza inducono un'esplosione degli stati di credenza.
Diagnosticabilità	Non Temporizzato (Limitato)	Tempo Polinomiale	Si riduce alla raggiungibilità in un prodotto "twin-plant".
Opacità	Non Temporizzato	PSPACE-completo	Equivalente all'universalità degli NFA.
Monitorabilità	Non Temporizzato	Decidibile (PSPACE-dura)	Proprietà strutturale; sicurezza/co-sicurezza sono sufficienti ma non necessarie.
Model Checking	Temporizzato (TLTL)	Decidibile	Utilizza l'astrazione per regioni; gli operatori di passato sono più semplici di quelli di futuro.
Model Checking	Temporizzato (TLTL $\sim$ )	Indecidibile	Conoscenza + Tempo = Indecidibile (riduzione dall'Universalità Temporizzata).
Opacità	Temporizzato	Indecidibile	Conseguenza diretta dell'indecidibilità della logica temporizzata epistemica.
Monitorabilità	Temporizzato (Passato)	Decidibile	Costruibile tramite automi temporizzati deterministici.
Monitorabilità	Temporizzato (Generale)	Indecidibile	Anche per linguaggi definiti da automi temporizzati.

5. Significato e Impatto

Unificazione Teorica: Il documento colma con successo il divario tra la teoria dei sistemi a eventi discreti (diagnosi/opacità) e la verifica formale (model checking/monitoraggio) utilizzando la logica epistemica come fondamento semantico comune. Ciò chiarisce la relazione tra "rilevare guasti" e "nascondere segreti" come problemi duali della conoscenza.
Chiarificazione della Complessità: Delimita con precisione il confine tra problemi trattabili e intrattabili. Sebbene la diagnosi sia spesso efficiente nella pratica (tempo polinomiale), il problema generale del model checking epistemico è computazionalmente costoso.
La Barriera "Conoscenza + Tempo": Un contributo critico è la dimostrazione che, sebbene la verifica temporizzata sia decidibile in isolamento, la combinazione di vincoli real-time e ragionamento epistemico (conoscenza) porta all'indecidibilità. Ciò stabilisce un limite rigido su ciò che può essere verificato automaticamente nei sistemi real-time con osservabilità parziale.
Costruzione Pratica di Monitor: Le dimostrazioni costruttive forniscono algoritmi per la costruzione di monitor a runtime (macchine di Moore) e diagnosticatori (DTA). Questi non sono semplici prove di esistenza teorica, ma progetti per l'implementazione, gestendo la transizione dall'analisi offline all'esecuzione online.
Gestione dell'Incertezza: Formalizzando l'"incertezza" attraverso relazioni di indistinguibilità, le note forniscono un metodo rigoroso per ragionare su ciò che un osservatore può e non può sapere, essenziale per la sicurezza (opacità) e l'affidabilità (diagnosi) in sistemi complessi e parzialmente osservabili.

In conclusione, queste note di lezione stabiliscono un quadro teorico completo per la verifica a runtime in condizioni di incertezza, evidenziando sia il potere della logica epistemica nell'unificare compiti di verifica diversi, sia i limiti algoritmici fondamentali imposti dalla combinazione di tempo e conoscenza.