💻 computer science

TREBL -- A Relative Complete Temporal Event-B Logic. Part I: Theory

Questo articolo presenta TREBL, un'estensione della logica Event-B per esprimere proprietà di tracciabilità e condizioni di vivacità tramite formule interpretate sugli stati, definendo un insieme di regole di derivazione dimostrabilmente relative-completo per macchine sufficientemente raffinate.

Autori originali: Klaus-Dieter Schewe, Flavio Ferrarotti, Peter Rivière, Neeraj Kumar Singh, Guillaume Dupont, Yamine Aït Ameur

Pubblicato 2026-04-22

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Klaus-Dieter Schewe, Flavio Ferrarotti, Peter Rivière, Neeraj Kumar Singh, Guillaume Dupont, Yamine Aït Ameur

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

Immaginate di avere un orologio meccanico molto complesso, fatto di ingranaggi, molle e leve. Questo orologio rappresenta un sistema informatico (come un software di sicurezza o un gestore di database). Il vostro compito è assicurarvi che l'orologio non si fermi mai (non si blocchi) e che, se premete un pulsante, prima o poi suoni la campanella (progresso).

Il problema è che l'orologio può avere milioni di modi diversi per funzionare. Come fate a essere sicuri che qualsiasi combinazione di ingranaggi porti alla campanella?

Questo è il cuore del problema che affrontano gli autori di questo articolo: come verificare matematicamente che un sistema software farà sempre ciò che deve fare, anche nel lungo periodo?

Ecco la spiegazione semplice, passo dopo passo, con qualche metafora.

1. Il Problema: La "Foglia di Albero" vs. Il "Sentiero"

Nella programmazione tradizionale, i metodi rigorosi (come Event-B) sono ottimi per controllare lo stato attuale. È come controllare che ogni ingranaggio sia al posto giusto in questo preciso istante.
Ma i sistemi reali hanno una vita propria: si muovono nel tempo. Possono seguire percorsi infiniti.

La vecchia idea: Per controllare il tempo, si usava una logica temporale (come LTL) che guarda l'intera storia dell'orologio (il "sentiero"). Ma questo rendeva le cose troppo complicate e spesso impossibile dimostrare matematicamente che tutto funzionava perfettamente (incompletezza).
Il nuovo approccio (TREBL): Gli autori dicono: "Aspettate! Non dobbiamo guardare l'intero sentiero. Se conosciamo la posizione attuale degli ingranaggi (lo stato), sappiamo già tutti i sentieri possibili che l'orologio può fare da lì in poi".

L'analogia della sfera di cristallo:
Immaginate che ogni stato del sistema sia una sfera di cristallo. Dentro quella sfera c'è già scritto il futuro. Non serve tracciare ogni singolo passo del futuro; basta guardare la sfera (lo stato presente) e capire cosa può succedere. Questo permette di semplificare enormemente la matematica.

2. La Soluzione: TREBL (La Logica Temporale Event-B)

Gli autori hanno creato un nuovo linguaggio chiamato TREBL. È come un "traduttore" che prende le regole complesse del tempo (come "prima o poi succederà X" o "X succederà per sempre") e le trasforma in regole semplici che guardano solo lo stato attuale.

Invece di dire: "Guarda tutta la storia futura e assicurati che X accada", TREBL dice: "Guarda lo stato attuale. Se è così, allora esiste un modo per arrivare a X".

3. Gli "Varianti": I Contatori Magici

Per dimostrare che qualcosa accadrà "prima o poi" (progresso), gli autori usano una tecnica geniale chiamata Varianti.

L'analogia della montagna:
Immaginate di dover scalare una montagna (il sistema) per arrivare in cima (l'obiettivo).

Se la montagna è infinita, non arriverete mai in cima.
Ma se avete un contatore magico (la variante) che indica la vostra altitudine, e potete dimostrare che ogni volta che fate un passo, il contatore scende, allora sapete per certo che prima o poi arriverete a zero (la cima o la fine del percorso).

Nel mondo software, questi "contatori" sono numeri o strutture matematiche che diminuiscono ad ogni azione del sistema. Se il sistema è ben progettato, questi contatori non possono scendere all'infinito (perché non esistono numeri negativi infiniti), quindi il sistema deve fermarsi o raggiungere l'obiettivo.

4. Il Trucco della "Rifinitura" (Refinement)

C'è un piccolo ostacolo: a volte, nel progetto originale dell'orologio, non abbiamo un contatore magico pronto all'uso.
Gli autori dicono: "Nessun problema! Possiamo aggiungere un contatore al nostro progetto senza cambiarne il comportamento reale".
Chiamano questo processo rifinitura conservativa. È come aggiungere un piccolo orologio da tasca al vostro orologio da polso per tenere il conto dei secondi. L'orologio da polso continua a funzionare esattamente come prima, ma ora abbiamo anche il contatore necessario per fare la prova matematica.

Hanno dimostrato che è sempre possibile aggiungere questi contatori magici a qualsiasi sistema Event-B. Questo è il segreto della loro scoperta: non importa quanto sia complesso il sistema, possiamo sempre "rifinirlo" per renderlo dimostrabile.

5. Perché è importante? (Esempi Reali)

L'articolo usa esempi di sicurezza per mostrare la potenza di questo metodo.

Non-interferenza: Immaginate un edificio con piani diversi. I dipendenti del piano 1 non devono poter vedere cosa succede al piano 5. Con la vecchia logica, dimostrare che "nessun segreto del piano 5 trapela mai al piano 1" era un incubo matematico. Con TREBL, diventa una semplice regola di stato: "Se sono al piano 1, non posso vedere le variabili del piano 5".
Fairness (Equità): Garantire che ogni processo che aspetta di essere servito, prima o poi lo sarà. Con TREBL, si dimostra che il "contatore di attesa" scende sempre, quindi nessuno viene lasciato indietro all'infinito.

In Sintesi

Questo articolo è una rivoluzione perché:

Semplifica: Trasforma il controllo del "futuro" (tempo) in un controllo del "presente" (stato).
Rende tutto dimostrabile: Mostra che, se aggiungiamo i giusti "contatori magici" (varianti) al nostro progetto, possiamo provare matematicamente che il sistema non si bloccherà mai e raggiungerà sempre i suoi obiettivi.
È universale: Funziona per qualsiasi sistema basato su stati, non solo per Event-B.

È come dire a un ingegnere: "Non devi prevedere il futuro. Devi solo costruire il tuo sistema in modo che, ogni volta che fa un passo, si avvicini un po' di più alla meta, e che non possa mai scappare all'infinito. Se fai così, la matematica ti garantisce che ce la farai".

Titolo: TREBL – Una Logica Temporale Event-B Relativamente Completa (Parte I: Teoria)

Autori: Klaus-Dieter Schewe, Flavio Ferrarotti, Peter Rivière, Neeraj Kumar Singh, Guillaume Dupont, Yamine Ait-Ameur.

1. Il Problema

La verifica delle condizioni di vivacità (liveness) è un aspetto cruciale nei metodi rigorosi basati sugli stati, come Event-B, B, TLA+ e Abstract State Machines (ASM). Mentre le condizioni di sicurezza (invarianti di stato e transizione) sono ben supportate da logiche complete, la verifica della vivacità (es. progresso, persistenza, assenza di deadlock) richiede il ragionamento su tracce complete (sequenze di stati).

I problemi principali identificati dagli autori sono:

Limitazione Espressiva delle Logiche Temporali Classiche: Logiche come LTL (Linear-Time Temporal Logic) e CTL sono complete ma di natura proposizionale. Per applicarle a metodi basati su stati come Event-B, richiedono estensioni che spesso compromettono la completezza o richiedono l'introduzione di tracce come oggetti di primo livello, complicando la logica.
Incompleteness delle Estensioni: Le estensioni di LTL per Event-B (come LTL(EB)) sono intrinsecamente incomplete perché combinano logica del primo ordine con operatori temporali.
Restrizioni nei Risultati Precedenti: Lavori precedenti (es. [FRS+24]) avevano definito un frammento relativamente completo, ma con una restrizione significativa: le macchine dovevano essere omogenee nella coda (tail-homogeneous), limitando l'uso della logica in presenza di non-determinismo intrinseco che genera rami di esecuzione diversi.
Interpretazione sulle Tracce: Nelle logiche temporali standard, le formule sono interpretate su tracce arbitrarie. Tuttavia, nei metodi basati sugli stati, uno stato iniziale determina univocamente l'insieme delle tracce possibili. Sfruttare questa proprietà per interpretare le formule temporali sugli stati invece che sulle tracce è la chiave per risolvere il problema della completezza.

2. Metodologia

Gli autori propongono un approccio che integra la logica temporale direttamente nella logica di Event-B, evitando di trattare le tracce come entità separate.

Estensione della Logica di Event-B ( $L_{ext}$ ):
- Introducono il concetto di insiemi di aggiornamento (update sets) per rendere esplicito l'effetto del firing di un evento.
- Definizione di operatori modali $[X]\phi$ , che esprimono che dopo l'applicazione di un insieme di aggiornamenti $X$ , la formula $\phi$ vale.
- Estensione a multi-step tramite la definizione induttiva di $USet^*(k, X)$ , che rappresenta l'aggregazione di aggiornamenti su $k$ passi.
Definizione degli Operatori Temporali come "Shortcut":
- Gli operatori temporali classici ( $\square$ - Always, $\diamond$ - Eventually, $U$ - Until) e le loro varianti (per una singola traccia o insiemi definibili di tracce) sono definiti come abbreviazioni sintattiche di formule complesse in $L_{ext}$ .
- Punto Chiave: Tutte le formule di TREBL sono interpretate sugli stati (in particolare sullo stato iniziale della traccia), non sulle tracce stesse. Questo riflette il fatto che in Event-B lo stato determina le tracce future.
Introduzione di Varianti (Variant Terms):
- Per dimostrare la vivacità, introducono diverse classi di varianti (termini che prendono valori in insiemi ben fondati e diminuiscono strettamente):
  - c-varianti: Per la convergenza (esistenza).
  - d-varianti: Per la divergenza (persistenza).
  - e-varianti: Per la raggiungibilità.
  - Varianti condizionali e simultanee: Per gestire formule di progresso complesse e combinazioni di operatori temporali.
Dimostrazione di Esistenza delle Varianti:
- Dimostrano che per ogni proprietà di vivacità valida, esiste sempre una rifinitura conservativa (conservative refinement) della macchina Event-B in cui i termini di variante necessari possono essere definiti esplicitamente.

3. Contributi Chiave

Definizione di TREBL (Temporal Event-B Logic): Un frammento della logica estesa di Event-B che cattura le condizioni di vivacità più importanti (invarianza, esistenza, progresso, persistenza, raggiungibilità) sia per tutte le tracce che per singole tracce o insiemi definibili di tracce.
Interpretazione sugli Stati: Spostamento dell'interpretazione delle formule temporali dalle tracce agli stati, permettendo di mantenere la logica nel dominio della logica del primo ordine con tipi (set theory), evitando l'incompletezza tipica delle logiche temporali del primo ordine.
Sistema di Regole di Derivazione: Definizione di un insieme completo di regole di derivazione (63 regole) che includono:
- Regole per invarianza, esistenza, persistenza e raggiungibilità.
- Regole per il progresso (progress), che utilizzano varianti simultanee e condizionali.
- Regole per formule temporali nidificate.
Completezza Relativa: Dimostrazione che il sistema di regole è relativamente completo. Ciò significa che per ogni formula valida $\phi$ in una macchina Event-B $M$ che soddisfa le "assunzioni di relatività" (coerenza, invarianti inclusi, e sufficientemente rifinita), esiste una derivazione formale di $\phi$ .
Rimozione della Restrizione "Tail-Homogeneous": A differenza dei lavori precedenti, TREBL non richiede che le macchine siano omogenee nella coda, rendendo la logica applicabile a sistemi con non-determinismo più complesso.
Applicazioni alla Sicurezza: Dimostrazione dell'efficacia del metodo su proprietà di sicurezza complesse, come la non-interferenza (espressa come invarianza di transizione) e la deducibilità limitata (bounded deducibility), mostrando come condizioni che sarebbero difficili da esprimere in LTL/CTL diventino gestibili in TREBL.

4. Risultati

Correttezza (Soundness): È stato dimostrato che tutte le regole di derivazione sono corrette: se una formula è derivabile, è semanticamente valida.
Completezza Relativa: È stato provato che se una formula è valida in una macchina sufficientemente rifinita, allora è derivabile. La prova si basa sulla costruzione di varianti nei modelli rifiniti.
Esistenza delle Rifiniture: È stato dimostrato che è sempre possibile costruire una macchina Event-B rifinita che contiene i termini di variante necessari per provare una data proprietà di vivacità.
Esempi Pratici: Il paper include formalizzazioni dettagliate di scenari di sicurezza (stack multi-livello, buffer produttore-consumatore) che illustrano come le proprietà di vivacità e sicurezza siano verificate tramite le nuove regole.

5. Significato e Impatto

Il lavoro rappresenta un passo avanti significativo nella verifica formale dei sistemi basati su stati:

Superamento del Dilemma Espressività/Completezza: Risolve il compromesso tra la mancanza di espressività delle logiche proposizionali e l'incompletezza delle logiche temporali del primo ordine, offrendo un sistema che è sia espressivo (grazie alla logica di Event-B) che relativamente completo.
Praticità per la Verifica: Poiché le formule sono interpretate sugli stati, la verifica può essere integrata negli strumenti esistenti per Event-B (come RODIN) senza dover gestire la complessità semantica delle tracce.
Generalizzabilità: Sebbene sviluppato per Event-B, l'approccio è applicabile ad altri metodi rigorosi basati sugli stati (ASM, TLA+, B), poiché si basa su concetti fondamentali come insiemi di aggiornamento e logica del primo ordine.
Fondamento per Strumenti Automatici: La Parte II del lavoro (in preparazione) promette di integrare queste regole nello strumento RODIN tramite la meta-teoria EB4EB, fornendo supporto meccanico per la verifica di proprietà di vivacità complesse.

In sintesi, TREBL fornisce un quadro teorico solido e pratico per verificare le proprietà di vivacità nei sistemi critici, trasformando problemi temporali complessi in problemi di ragionamento sugli stati risolvibili tramite varianti e raffinamenti.