Introduzione al Model Checking
PROSSIMO
Progettazione, sviluppo e ottimizzazione di sistemi intelligenti multi-oggetto
Azioni Cluster “Top Down”
Progetto finanziato con fondi POR FESR 2014/2020
ASSE PRIORITARIO I “RICERCA SCIENTIFICA, SVILUPPO TECNOLOGICO E INNOVAZIONE”
1 / 106
Intro alla Verifica Formale.
Per alcuni sistemi (di computazione) è cruciale verificare la loro corret- tezza prima che vengano utilizzati.
Sistema di computazione:
Circuiti, unità aritmetiche, CPU, programmi, compilatori ...
Proprietà dei sistemi
Availability: la probabilità che un sistema sia funzionante e in grado di fornire i servizi nel tempo
Reliability: la probabilità, in un dato intervallo di tempo, che un sistema fornisca correttamente i servizi come atteso dagli utenti
Safety: è una valutazione di quanto sia verosimile che il sistema causi danni a persone o all’ambiente.
Security: è una valutazione di quanto sia verosimile che il sistema possa resistere ad intrusioni accidentali o premeditate.
3 / 106
Tipi di sistemi critici
Safety-critical: sistemi il cui fallimento (failure) può causare ferimenti, perdite di vita, o seri danni ambientali (e.g. sistema di controllo per un impianto chimico).
Mission-critical: sistemi il cui fallimento (failure) può causare il falli- mento di attività guidate da obiettivo. (e.g. sistema di navigazione di una navetta spaziale)
Business-critical: sistemi il cui fallimento (failure) può causare ingenti perdite di denaro (e.g. sistema di gestione dei conti correnti in una banca).
Il caso Therac-25
Il fatto: Canada-USA 1985-1987. 3 persone uccise e 3 gravemente ferite (di cui una paralizzata) per i malfunzionamenti di una macchina per l’irradiazione dei tumori, il Therac-25.
Il problema: “overdose” di radiazioni.
Le cause: errori nel sistema SW, e di interfacciamento SW/HW (erronea integrazione di componenti SW preesistenti nel Therac-20).
5 / 106
Il caso di Denver
Aeroporto di Denver - Progettato per essere un aeroporto all’avan- guardia, provvisto di un complesso sistema di gestione bagagli compu- terizzato e 5.300 miglia di cablaggio in fibre ottiche.
Sfortunatamente, errori nel sistema gestione bagagli causavano lo schiacciamento delle valige e guidavano i carrelli automatici contro i muri.
L’aeroporto inaugurò con 16 mesi di ritardo, con una perdita di 3.2 miliardi di dollari, e con un sistema bagagli essenzialmente manuale.
Il Pentium 5
Il baco del Pentium- Il Professor Thomas Nicely del Lynchburg Col- lege in Virginia scoprì che il chip Pentium dava risposte scorrette per certe complesse equazioni (1994).
L’errore era dovuto a un difetto di progettazione dell’algoritmo di divi- sione in floating point (FDIV) del processore.
Intel fu costretta a ritirare il chip e a sostituirlo. Il tutto costò alla Intel 450 milioniudi dollari.
Dal 1994 Intel usa le Tecniche di Verifica Formale!
7 / 106
Il caso AT&T
AT&T - errori nel software dei computer che gestivano le chiamate telefoniche, causarono uno scollegamento di 9 ore per tutte le reti a lunga distanza della compagnia.
Fu il peggior black-out, tra i tanti subiti nella storia del sistema. Coin- volse centinaia di servizi.
Alla fine la causa venne individuata in una singola linea di codice errata.
L’Ariane 5
Il fatto: 4 giugno 1996, il volo di prova dell’Ariane 5 risultò un fal- limento. Dopo solo 40 secondi dall’inizio della sequenza di volo, ad un’altitudine di 3700 m, il razzo deviò dalla rotta, si separò ed esplose (500M$).
La causa: gli Inertial Reference Systems cessarono di funzionare si- multaneamente dopo circa 36.7 secondi. L’eccezione del software SRI si verificò durante la conversione di dati da floating point a 64-bit a signed integer a 16-bit. Il numero floating point da convertire aveva un valore superiore a quello rappresentabile con un signed integer di 16-bit.
Il risultato fu una eccezione di “Operand Error”...
9 / 106
L’Ariane 5 (continua)
... il pacchetto di navigazione era stato ereditato dall’Ariane 4 senza eseguire un testing accurato. Il nuovo razzo volava più velocemente, fornendo al il software di navigazione valori maggiori per alcune variabili.
La sfortuna fu che il codice che generò l’eccezione forniva informa- zioni utili solo nella fase precedente alla partenza; se fosse stato disabilitato al momento del lancio, non ci sarebbero stati problemi.
Verifica di correttezza
È una pratica ingegneristica fondamentale.
Gli errori possono essere molto costosi il “baco” del Pentium.
il Razzo Ariane 5
Ci sono molti sistemi la cui correttezza è critica, ad esempio i sistemi
“safety-critical”.
11 / 106
Necessità di correttezza
Sistemi safety-critical:
Medici
Controllo di reattori Controllo ferroviario Controllo aereo ...
Società che usano i Metodi Formali
Intel Siemens AT&T Lucent AMD
IBM Motorola Nasa
British Telecom (BT) etc...
13 / 106
Verifica a posteriori
Errori: introduzione, individuazione e costi
15 / 106
Tecniche correnti
Simulazione Testing
Sempre più frequente e diffusa:
Verifica formale
In pratica le più utilizzate sono però la simulazione e il testing.
Simulazione e testing
Simulazione : Un modello astratto del sistema viene simulato inclu- dendo:
Dati di input Eventi esterni
Testing: Il sistema implementato viene eseguito su insiemi selezionati di input e eventi esterni, e verificato.
17 / 106
Svantaggi
La simulazione non può essere eseguita per sempre.
La simulazione è molte volte più lenta del sistema reale.
Può essere motlo costosa.
Nessuna garanzia che tutte le esecuzioni possibili vengano simulate.
Svantaggi
Anche il testing soffre di svantaggi simili.
In pratica, non tutte le configurazioni di input possono essere presentate al sistema.
Gli insiemi di input devono essere generati automaticamente.
Nessuna garanzia che gli input “cattivi” vengano mai presentati.
Molto difficile soprattutto per sistemi concorrenti Sistemi multi-componente.
19 / 106
Svantaggi
La simulazione e il testing possono rivelare la presenza di bachi ma non possono mai stabilire l’assenza di bachi (Dijkstra negli anni ’70).
Questa è una limitazione fondamentale nel caso di sistemi “safety- critical”.
Ma in pratica ...
Metodi Formali
I Metodi Formali hanno come obiettivo fornire:
la capacità di esprimere specifiche in maniera precisa, e
la capacità di definire in modo chiaro quando un’implementazione sod- disfa le specifiche (“correttezza”)
21 / 106
La Verifica Automatica
La Verifica Automatica:
l’applicazione del ragionamento logico allo sviluppo di sistemi com- puterizzati (software, hardware, applicazioni web distribuite,...)
l’uso di tools informatici per aiutare questo ragionamento logico
Ragionamento logico e verifica
Il ragionamento logico permette di dedurre proprietà dei sistemi dandoci un modo di “verificare” il nostro lavoro, e fornisce un punto di vista diverso sul sistema.
Nella verifica formale le proprietà vengono controllate per “tutti” i pos- sibili comportamenti del sistema. L’analisi è esaustiva ma eseguita su un modello formale del sistema, non sul sistema reale.
Il ragionamento simbolico rende possibile l’analisi esaustiva.
23 / 106
Ragionamento logico e verifica
La verifica corrisponde a decidere la relazione di soddisfacimento tra un modello e una formula:
M |= ϕ
M è un modello che descrive i possibili comportamenti del sistema ϕ è la proprietà o specifica che il sistema deve soddisfare
|= è una relazione che deve sussistere tra M e ϕ.
Il ragionamento logico ci permette di decidere se la relazione vale o meno tra il modello e la proprietà.
Verifica Formale
La verifica è:
formale: la proprietà di correttezza è una proposizione matematica precisa - sia il modello che la proprietà sono non ambigue
definitiva: la verifica o dimostra oppure rifuta la proprietà di correttezza opposta a
testingdel sistema reale su input selezionati simulazione di un modello su input selezionati ispezione manuale del codice o di un modello
25 / 106
Approcci alla Verifica Formale
Verifica deduttiva e/o Model Checking.
Verifica deduttiva (o Theorem proving):
Usa assiomi e regole di dimostrazione per modellare il sistema (sistema formale).
La proprieta da verificare viene espressa da un teorema del sistema formale.
Derivare il teorema con l’aiuto di un dimostratore automatico (Theorem- prover)
Svantaggi
Molto difficile da automatizzare (spesso impossibile in teoria).
Richiede l’intervento dell’utente.
Derivare il sistema formale può essere piuttosto scomodo.
Raramente effettiva (fattibile).
Richiede un esperto per usare il theorem-prover.
27 / 106
Model checking
Usa sistemi a transizioni (LTS)per modellare i sistemi.
Usa logica temporale per specificare le proprietà.
Il problema della verifica viene spesso ridotto a problemi di ricerca su grafi.
Può essere completamente automatizzato.
Se la proprietà non è verificata viene generato un controesempio.
È relativamente facile da usare.
Filosofia di progettazione
Rendere la verifica una parte significativa del processo di sviluppo.
Progettazione, verifica, riprogettazione.
Model checking (come il testing) funziona al meglio quando ci sono
“bachi”!
Le verifiche di basso livello vengono sempre svolte tramite testing ...
... ma forse meccanismi di sintesi automatica potrbbero essere di aiuto
29 / 106
Il processo di Model Checking
Il processo di Model Checking
Modellazione:
descrivere il comportamento del sistema usando il linguaggio di descri- zione fornito dal Model Checker (costruzione del modello).
(opzionale) eseguire alcune simulazioni per controllare il comportamento del modello
formalizzare la proprietàda verificare usando il linguaggio di specifica fornito dal Model Checker
31 / 106
Il processo di Model Checking
Esecuzione:
esegue la verifica sul modello e sulla proprietà Analisi:
proprietà soddisfatta — passare alla prossima proprietà violata—
analizzare il contro-esempio fornito tramite simulazione raffinare il modello, il progetto o la proprietà
ripetere il procedimento
out of memory — tentare di ridurre il modello e riprovare
Svantaggi
Funziona (bene) prevalentemente per sistemi a stati finiti.
L’esplosione dello spazio degli stati è un problema serio:
Al crescere del numero di componenti interagenti le dimensioni del siste- ma crescono esponenzialmente.
Trovare il giusto livello di astrazione per la modellizzazione non è facile (Eliminare i giusti dettagli).
Gli informatici non sono sempre a loro agio con le logiche temporali.
33 / 106
Stato dell’arte
Di grande successo nella verifica di : hardware “isolato” di media dimensione.
Protocolli di comunicazione/sicurezza Sempre più popolare in ambito industriale
Sono disponibili tool robusti come SPIN, SMV (NuSMV), COSPAN, etc.
I principi sottostanti sono ben compresi.
Tendenze della ricerca
Integrazione con il theorem-proving (PVS, Abstraction-Refinement per verifica SW).
Verifica parametrica.
Verificare sistemi ad n-componenti per ogni n.
Pipelines con n stadi.
Protocolli di cache con n unità di memoria.
...
Sistemi a stati infiniti (ricorsione, parallelismo) Sistemi temporizzati (real-time).
Sistemi ibridi.
35 / 106
La verifica nella pratica:
Definire il modello di un sistema usando il formalismo dei sistemi di transizioni : TS
Esprimere prorpietà interessanti del sistema usando una logica tempo- rale : Ψ
Verificareche il sistema soddisfa la proprietà desiderata tramite model checking:
TS |= Ψ
Sistemi a transizioni
Come modellare sistemi ? Uso di sistemi a transizioni.
37 / 106
Sistemi a transizioni
TS = (S , Sin, −→) S è un insieme di stati
Sin è un iinsieme di stati iniziali (un sottoinsieme di S)
−→⊆ S × S è la relazione di transizione (s, s0) ⊆−→ s −→ s0
Varianti
S deve essere finito.
Ci deve essere un solo stato iniziale.
Act — un insieme di azioni a, b, ...
−→⊆ S × Act × S s −→ sa 0 (s, a, s0) ∈−→
39 / 106
Sistemi a transizioni
Modello molto generale.
Programmi, hardware, protocolli, Macchine di Turing ...
Programmi possono essere modellati tramite:
Stato
(locazione del controllo, valori correnti delle variabili) Le transizioni producono nuovi stati :
(nuove locazioni del controllo, nuovi valori delle variabili)
Logiche temporali
Nascono nella filosofia greca antica.
Sviluppate dai filosofi per lo studio dei costrutti linguistici che coinvol- gono il flusso del tempo.
Riprese nei tempi moderni da Prior.
Importata in ambito informatico (per la verifica formale) nel 1977 da Amir Pnueli.
41 / 106
Logiche temporali
Due principali famiglie:
Logiche Temporali Lineari
(Linear-time Temporal Logics) es. LTL Logiche Temporali Ramificate
(Branching-time Temporal Logics) es. CTL
Framework di base
TS = (S , s0, −→)
s0 → s1 → s2 → s3→ s4...
Una computazione come quella sopra è l’oggetto di base del ragiona- mento.
In linear time ci interessano le computazioni individuali che hanno origine da s0.
In branching time ci interessa l’albero delle computazioni che hanno origine da s0.
43 / 106
Model Checking
Partiamo daTS = (S, s0, →), il modello del sistema Da un insieme finito di proposizioni abbiamo P = {p1, p2, ....pn}.
p1 = “lo stato del controllo è “begin” ”
Fissiamo una valutazione V che assegna un sottoinsieme di P ad ogni stato s;
V (s0) = {p1, p2, p5}...
Model Checking
(TS , V ) — Kripke Structure
Costruiamo una formula in logica temporale Ψ (specifica, specification) a partire da
P = {p1, p2, ....pn}.
Determiniamo se (TS, V ) soddisfa (meets) la specifica Ψ.
(TS , V ) |= Ψ
45 / 106
Tecniche basate sulla teoria degli automi
Linear time Temporal Logic (LTL).
Si associa un automa a K e uno alla specifica.
K = (TS , V ) − − − − − − − −AK Ψ − − − − − − − − − − − − − AΨ
“K meets the specification Ψ00iff L(AK) ⊆ L(AΨ).
Questo di riduce ad un problema algoritmico su grafi!
Tecnica di etichettatura degli stati
Branching time K = (TS , V ) Ψ
Partiamo da P = {p1, p2, ....pn} ed etichettiamo induttivamente gli stati di TS con le sottoformule di Ψ.
Il passo base è fornito dalla valutazione V !
“K meets Ψ iff, alla fine, s0 è risulta essere etichettato con Ψ.
47 / 106
Esplosione dello spazio degli stati
Sistemi concorrenti.
TS = TS1||TS2||...||TSm
m processi sequenziali comunicanti (communicating sequential proces- ses).
Lo spazio degli stati di TS è esponenziale (2m).
m = 50...!
Esplosione dello spazio degli stati
Trovare modi succinti per descrivere gli stati e le transizioni di TS.
Usare questa rappresentazione nella computazione di punto fisso guidata dalla procedura di model checking.
Vengono utilizzati gli OBDD (Ordered Boolean Decision Diagrams);
Randy Bryant, Ken McMillan...
49 / 106
Altre tecniche di riduzione
Partial order reductions Simmetria
Astrazione ....
Sistemi real-time
Le logiche temporali permettono di esprimere solo asserzioni qualitative sul tempo.
A volte è necessario fare asserzioni quantitative sul tempo.
Dopo al più 5.5 unità di tempodal verificarsi dell’evento
“gas-pressure-level = danger”
deveverificarsi l’evento
“safety-valve = open”
51 / 106
Sistemi real-time
Uso degli automi temporizzati (timed automata) e sistemi a tran- sizioni temporizzati (timed transition systems)
Sistemi a transizioni + Variabili di clock.
Una variabile di clock evolve col tempo a tasso unitario.
Una transizione può essere guarded (condizionata) da predicati che coinvolgono variabili di clock:
x < 6.1 e y > 3
Una variabile di clock può essere resettata a 0 da una transizione.
Molto espressivi.
Verifica formale
Le logiche temporali sono uno strumento fondamentale in Informatica.
Strumenti molto potenti e interessanti di specifica di proprietà di sistemi reatrivi.
Verifica formale basata su model checking è un “must” per sistemi safety-critical.
.... ma c’è ancora molto da fare!
53 / 106
Richiami sulle Logiche Temporali
Consideriamo la seguente st ruttura di Kripke:
La sua esecuzione può essere vista come:
un insieme infinito di percorsi di computazione
un albero infinito di computa- zioni
Logiche Temporali
Proprietà dei “Sistemi Reattivi”
comportamenti non terminanti, senza riferimento esplicito del tempo.
Linear Temporal Logic (LTL)
interpretato su ogni percorso della struttura di Kripke modello lineare del tempo
operatori temporali
Computation Tree Logic (CTL)
interpretato sull’albero delle computazioni del modello di Kripke modello del tempo ramificato
operatori temporali più quantificatori di percorso
55 / 106
Linear Time Temporal Logic (LTL): Sintassi
Una proposizione atomica è una formula LTL;
se ϕ1 e ϕ2 sono formule LTL, allora ¬ϕ1, ϕ1∧ ϕ2, ϕ1∨ ϕ2, ϕ1→ ϕ2, ϕ1↔ ϕ2 sono formule LTL;
se ϕ1e ϕ2sono formule LTL, then X ϕ1, ϕ1Uϕ2, G ϕ1, F ϕ1sono formule LTL, dove X , G , F , U sono gli operatori temporali “next”, “globally”,
“eventually” e “until”.
N.B: LTL può essere solo definita nei termini di ∧, ¬, X , U:
Linear Temporal Logic (LTL)
Le proprietà LTL vengono valutate su percorsi, cioè, su sequenze lineari infinite di stati:π = s0 → s1 → ... → st → st+1→ ...
Given an infinite sequence:π = s0, s1, s2, ...
π, si |= ϕ se ϕ è vera nello stato si di π.
π |= ϕ se ϕ è vera nello stato iniziale s0di π.
Il problema di Model Checking LTL M |= ϕ
verifica se π |= ϕ per ogni percorso π della struttura di Kripke M(ad esempio, ϕ = Fdone)
57 / 106
Semantica LTL: intuizione
LTL è dato dalla logica booleana standard migliorata con i seguenti operatori temporali:
“Next” X : Xϕ è vera in st se e solo se ϕ è vera in st+1
“Future” (o “eventually”) F : Fϕ è vera in st se e solo se ϕ è vera in alcuni st0 con t0 ≥ t
“Globally” (o “henceforth”) G : Gϕ è vera in st se e solo se ϕ è vera in tutti i st0 con t0 ≥ t
“Until” U : ϕUψ è vera in st se e solo se ψ è vera in alcuni stati st0 con t0≥ t ϕ è vera in tutti gli stati s con t ≤ t00< t0
Semantica LTL: intuizione
59 / 106
Semantica Formale LTL
LTL regola del tableaux
Siano ϕ1 e ϕ2 formule LTL:
Definizioni ricorsive di F, G, U.
Se applicate ricorsivamente, riscrivono una formula LTL in termini di formule atomiche e formule precedute dall’operatore X:
61 / 106
LTL: Alcuni esempi degni di nota
Safety: “non succede mai che arrivi un treno e che la sbarra sia alzata”
G(¬(train_arriving ∧ bar _up))
Liveness: “se input, quindi eventualmente output”
G(input → Foutput)
Fairness: “inviato infinitamente spesso ” GFsend
Strong fairness: “inviato infinitamente spesso implica ricevuto infini- tamente spesso”
GFsend → GFrecv
Esempio 1: mutua esclusione (safety)
63 / 106
Esempio 1: mutua esclusione (safety)[continua]
Esempio 2: liveness
65 / 106
Esempio 2: liveness [continua]
Esempio 3: liveness
67 / 106
Esempio 3: liveness [continua]
Esempio 4: fairness
69 / 106
Esempio 4: fairness [continua]
Esempio 5: strong fairness
71 / 106
Esempio 5: strong fairness
Computational Tree Logic (CTL): Sintassi
Una proposizione atomica è una formula CTL;
se ϕ1 e ϕ2 sono formule CTL, allora ¬ϕ1, ϕ1∧ ϕ2, ϕ1∨ ϕ2, ϕ1→ ϕ2, ϕ1↔ ϕ2 sono formule CTL;
se ϕ1 e ϕ2 sono formule CTL, allora AXϕ1, A(ϕ1Uϕ2), AGϕ1, AFϕ1, EXϕ1, E(ϕ1Uϕ2), EGϕ1, EFϕ1 , sono formule CTL.
N.B: CTL può essere definito solo in termini di ∧, ¬, EX, EG, EU:
73 / 106
Computation Tree Logic (CTL)
Le proprietà CTL (ad es.AFdone) sono valutate lungo gli alberi.
Ogni operatore temporale (F, G, X, U) è preceduto da un quantifica- tore del percorso (A o E).
Modalità universali (AF, AG, AX, AU): la formula temporale è vera in tutti i percorsi che iniziano nello stato corrente.
Semantica CTL: intuizioni
CTL è dato dalla logica booleana standard migliorata con gli operatori AX, AG, AF, AU, EX, EG, EF, EU:
“Necessarily Next” AX: AXϕ è vera in st se e solo se ϕ è vera in ogni stato successore st + 1
“Possibly Next” EX: EXϕ è vera in st se e solo se ϕ è vera in uno stato successore st+1
“Necessarily in the future” (o “Inevitably”) AF: AFϕ è vera in st se e solo se ϕ è inetabilmente vera in alcuni st0 con t0 ≥ t
“Possibly in the future” (o “Possibly”) EF: EF ϕ è vera in st se e solo se ϕ può essere vera in alcuni st0con t0≥ t
75 / 106
Semantica CTL: intuizioni[continua]
“Globally” (o “always”) AG: AGϕ è vera in st se e solo se ϕ è vera in tutti gli st0 con t0≥ t
“Possibly henceforth” EG: EGϕ è vera in st se e solo se ϕ è possibil- mente vera d’ora in poi
“Necessarily Until” AU: A(ϕUψ) è vera in st se e solo se necessaria- mente ϕ è verificata fino a che ψ viene verificata.
“Possibly Until” EU: E(ϕUψ) è vera in st se e solo se possibilmente ϕ viene verificata fino a che ψ viene verificata.
Semantica CTL: intuizioni[continua]
77 / 106
CTL Semantica Formale
Sia (si, si +1, ...) un percorso in uscita dallo stato si in M
Il problema del Model Checking CTL M |= φ
Verifica se M, s |= φ per ogni stato iniziale s ∈ I della struttura di Kripke
79 / 106
CTL Regola del tableaux
Siano ϕ1 e ϕ2 formule CTL
Definizioni ricorsive di AF, AG, AU, EF, EG, EU.
Se applicate ricorsivamente, riscrivono una formula CTL in termini di formule atomiche, formule Necessarily Next e formule Possibly Next:
Esempio 1: mutua esclusione(safety)
81 / 106
Esempio 1: mutua esclusione(safety)[continua]
Esempio 2:liveness
83 / 106
Esempio 2:liveness [continua]
SÌ: ogni percorso che inizia da ogni stato in cui è presente T1 passa
Esempio 3: fairness
85 / 106
Esempio 3: fairness [continua]
Esempio 4: blocking
87 / 106
Esempio 4: blocking [continua]
SI: da ogni stato in cui N è vero, c’è un percorso che porta a uno stato
LTL vs. CTL: espressività
molte formule CTL non possono essere espresse in LTL
(ad esempio, quelli contenenti sottoformule quantificate esistenzialmen- te)
Esempio, AG(N1→ EFT1), AF AG ϕ
molte formule LTL non possono essere espresse in CTL (ad esempio, formule LTL di fairness)
Esempio, GFT1→ GFC1, FG ϕ
alcune formule possono essere espresse sia in LTL che in CTL (in genere formule LTL con operatori annidati di profondità 1, e / o con operatori che si verificano in maniera positiva)
Esempio, G¬(C1∧ C2), FC1, G(T1 → FC1), GFC1
89 / 106
Introduzione a NuSMV
Originariamente, SMV di Ken McMillan, Symbolic Model Checking: An Approach to the State Explosion Problem, 1993.
NuSMV: Re-implementato alla Fondazione Bruno Kessler (FBK) di Trento.
Sistemi a stati finiti specificati in un linguaggio specializzato Specifiche date come formules LTL or CTL + Fairness Rappresentazione interna usando BDD.
Controlla automaticamente le specifiche o fornisce un controesempio
Caratteristiche del linguaggio
Consente la descrizione di sistemi sincroni e asincroni Descrizioni modulari e gerarchiche
Tipi di dati finiti: valori booleani, numeri interi limitati, scalari (enume- razioni), array.
Gestisce il nondeterminismo
91 / 106
Un esempio di programma NuSMV
Assegnazione delle variabili
Assegnazione allo stato iniziale:
init(value) := 0;
Assegnazione allo stato successivo (relazione di transizione) next(value) := value + carry _in mod 2;
Assegnazione allo stato corrente (invariante) carry _out := value & carry _in;
Usare le keyword init-next oppure le invarianti - mai entrambi SMV è un linguaggio di assegnazione parallelo
93 / 106
L’espressione “Case”
caseè un’espressione, non una dichiarazione Le guardie vengono valutate in sequenza.
La prima che viene valutata a TRUE determina il valore risultante Se nessuna delle guardie ha valore TRUE, viene restituito un valore arbitrario valido
Usa sempre una guardia else!
Nondeterminismo
Una variabile completamente non assegnata può modellare input non vincolati.
{val_1, ..., val_n} è un’espressione che assume uno qualsiasi dei valori dati in modo non deterministico.
Usare union quando si hanno espressioni anziché valori Una scelta non deterministica si può usare per:
Modellare un’implementazione che non è stata ancora raffinata Comportamento astratto
95 / 106
Tipi di dato
Booleani
1 è vero e 0 è falso Interi
Gli interi in genere vanno da (−223+ 1) a (223− 1) Enumerativi
Tipi di dato[continua]
Bit-vector
word[] es., bv : word [4] dichiara un vettore di 4 bit.
Operatori di selezione di bit su tipi word [] :
es., 0b6_011001[4 : 1] restituisce la costante 0b4_1100 Operatori di shift sul tipo word [] :
es. 0b6011001 2 restituisce la costante 0b6_100101
È possibile applicare operatori logici, relazionali e aritmetici al tipo word []
Array
a: array 0..3 di booleani;
b: array 10..20 di {OK , y , z};
c: array 1..8 di array −1..2 di word [4];
Uso limitato nelle espressioni, es.: c[3][−1] & 0b4_1100 .
97 / 106
ASSIGN e DEFINE
VAR a: boolean;
ASSIGN a := b | c;
dichiara una nuova variabile di stato a diventa parte della relazione invariante DEFINE d := b | c;
è effettivamente una definizione di macro, ogni occorrenza di d è sosti- tuita da b | c
non viene generata nessuna variabile BDD aggiuntiva per d ilo BDD per b | c diventa parte di ogni espressione che utilizza d
Next (relazione di transizione)
Le espressioni possono fare riferimento al valore di una variabile nello stato successivo (next state)
Examples:
(a è la negazione di b, ad eccezione dello stato iniziale)
99 / 106
Definizioni circolari
....NON SONO PERMESSE!!!
questo è illegale:
Questo è OK:
Moduli e Gerarchia
I moduli possono essere istanziati più volte, ogni istanza crea una copia delle variabili locali
Ogni programma ha un modulo main Scoping
Le variabili dichiarate all’esterno di un modulo possono essere passate come parametri
Le variabili interne di un modulo possono essere utilizzate nei moduli racchiusi (indicati con l’identificatore complesso submodel.varname).
L’identificatore completo è l’identificatore complesso della variabile di un modulo visto dal modulo MAIN
I parametri sono passati per riferimento.
101 / 106
Scoping
Scoping [continua]
103 / 106
Composizione dei moduli
Composizione sincrona
Tutte le assegnazioni vengono eseguite in parallelo e in modo sincrono.
Un singolo step del modello risultante corrisponde a uno step in ciascuno dei componenti.
Composizione asincrona (interleaving)
Uno step della composizione è esattamente uno step di un processo.
Le variabili, non assegnate in tale processo, rimangono invariate.
Composizione asincrona
105 / 106
