Metodi formali per la verifica dell’affidabilit` a di sistemi software (e hardware)

Metodi formali per la verifica dell’affidabilit` a di sistemi software (e hardware)

(Peled, Software Reliability Methods, cap. 1)

Importanza della verifica di sistemi (safety-critical, commercially critical, mission critical) Il baco del 2000: gli US spesero pi`u di 100.000 milioni di dollari per combattere il Y2K-bug. Non successe niente.

Sistemi SW controllano gran parte della nostra vita (telefoni, banche, aerei,...) Lo sviluppo del SW `e cambiato

coinvolge decine o centinaia di programmatori su uno stesso progetto migliaia/milioni di linee di codice

persone dislocate

Difficolt`a di controllare il processo di sviluppo del SW

⇒ metodologie di progettazione

⇒ metodi formali per identificare errori

Problema della validazione di un progetto: assicurare la correttezza del progetto fin dai primi stadi dello sviluppo:

• simulazione e test

• verifica formale

Metodi Formali per la verifica di sistemi Collezione di notazioni e tecniche per descrivere a analizzare sistemi

Formali: basati su qualche teoria matematica (logica, automi, teoria dei grafi)

Verifica: applicazione di una tecnica manuale o automatica che possa aiutare a stabilire se un sistema soddisfa una data propriet`a o si comporta in accordo a una specifica data.

Una tecnica di verifica formale include:

1. Una metodologia per modellare sistemi:

rappresentare un sistema in termini di oggetti matematici, astraendo e semplificandone la descrizione

2. Un linguaggio di specifica, per descrivere le propriet` a del sistema mo- dellato. Si utilizzano formalismi logici, in genere una logica temporale.

3. Un metodo di verifica: tecniche di analisi formale per verificare se un sistema soddisfa la sua specifica.

Quindi escludiamo i metodi di test, che agiscono sul sistema reale (e non coprono comunque tutte le esecuzioni possibili).

Limiti intrinseci dei metodi formali:

• non garantiscono la correttezza del sistema, ma di qualche suo modello astratto (co- struito manualmente)

• la formulazione della specifica `e eseguita manualmente, pu`o essere incompleta

Approcci fondamentali alla verifica di sistemi Verifica deduttiva.

Inizialmente con lo scopo di assicurare la correttezza di un programma.

Il sistema `e descritto da un insieme di formule S (in una logica adatta allo scopo), la specifica `e una formula A. Il metodo di verifica consiste nel dimostrare che S ⊢ A.

Normalmente non sono metodi completamente automatizzabili.

Influenza sullo sviluppo del SW: nozione di invariante.

Verifica basata su model checking.

Il sistema `e rappresentato da una struttura matematica M, rappresentabile in modo finito, che corrisponde a un’interpretazione o un insieme di interpretazioni di una logica (adatta allo scopo). La specifica `e una formula A. Il metodo di verifica consiste nel dimostrare che M |= A.

Il metodo di verifica `e generalmente automatizzabile.

Applicabile a sistemi a stati finiti (dove l’insieme di valori che pu`o assumere ciascuna variabile `e finito).

Metodi adatti a verificare protocolli di comunicazione, sistemi concorrenti, o rappresen- tazioni astratte di algoritmi.

L’applicazione di metodi formali di verifica `e oggi spesso integrata nel processo di sviluppo

del SW (piuttosto che eseguita a posteriori): metodologia di sviluppo per raffinamenti

(specifica e test), conservando la correttezza da uno stadio dello sviluppo al successivo.

Verifica automatica

Restrizione teorica: la verifica completamente automatica di tutti i programmi `e impossibile (indecidibilit`a del problema della fermata).

• restringere la classe di programmi (programmi a stati finiti)

• verificare soltanto le parti cruciali del programma

• semplificare il programma mediante astrazione (manualmente)

• usare metodi di verifica semi-automatica

Verifica di programmi a stati finiti: lo spazio degli stati si pu`o visitare come un grafo a partire da I, ad esempio per verificare le invarianti.

Programmi a stati finiti rappresentabili mediante sistemi di transizioni basati su un linguag- gio proposizionale.

Rappresentazione degli stati: importante non distinguere stati che sono essenzialmen-

te lo stesso. Spesso sono mantenuti in una tabella hash e si usano tecniche di compressione.

Logica del primo ordine (Peled, Cap. 3)

Notazioni e terminologia del libro:

Segnatura (linguaggio) G = (V, F, R) contiene un insieme di variabili V , un insieme di simboli funzionali F e un insieme di simboli di relazione R.

terms(G): insieme dei termini f orms(G): insieme delle formule

Struttura del primo ordine (linguaggio + interpretazione) S = (G, D, F, R, f ) dove:

• G `e una segnatura (V, F, R)

• D un insieme (il dominio)

• F un insieme di funzioni su D

• R un insieme di relazioni su D

• f la funzione di interpretazione semantica

f : F ∪ R → F ∪ R

associa una funzione a ogni simbolo funzionale e una relazione a ogni simbolo di relazione, conservando la arit`a

Noi utilizzeremo il simbolo M (eventualmente con indici) per indicare una interpreta- zione (D, F , R, f ) – o semplicemente (D, f ) – di una segnatura.

Assegnazione a : V → D

a[d/v]: variante di a che assegna d a v

Interpretazione di termini e formule

Interpretazione semantica dei termini: T

: terms(G) → D

Interpretazione delle formule: M

: f orms(G) → {T RU E, F ALSE}

a |=

ϕ : (S, a) |= ϕ cio`e M

(ϕ) = T RU E

|=

ϕ : S |= ϕ (per ogni a, a |=

ϕ) 3.8: presenta PVS

Riferimenti a mechanized thorem provers