Martino Angela

1

Seminario di “Sicurezza”

Martino Angela

a.a. 2007-2008

Prof. S.Bistarelli

2

Cosa sono

Sono dei linguaggi che vengono usati per la rappresentazione del comportamento e la descrizione di sistemi informatici.

- Sintassi ben definita.

- Semantica di base.

- Sistema logico-matematico come struttura sottostante.

Approccio induttivo vs Model checking technique

Utilizzo, grado di automazione, completezza, dominio, pre/post sviluppo

Premesse  Proprietà Logica temporale; tabella di verità

Venire incontro alle esigenze.

3

Inductive verification tecnique

- Usate per problematiche poco complesse.

- Forniscono tecniche per provare teoremi.

- Mostrano come una specifica di sistema incontra un insieme di proprietà.

- Più step.

- Theorem prover (trova prove intermedie).

- Interazione con l’utilizzatore (lemmi).

- Fase di progettazione del prodotto.

Model checking technique

Ammette stati transitori - Fatto su misura per lo strumento che lo utilizza - Poche interazioni - Equivalenza modello e proprietà desiderata - Test sui prodotti -

4

Specifiche formali

E’ la descrizione dettagliata delle caratteristiche di un sistema o di un programma.

E’ una specifica scritta in un linguaggio formale con una sintassi ristretta e ben definita basata su concetti matematici fondamentali.

- E’ un linguaggio di primo livello basato sulla logica e sviluppato da SRI international.

- Linguaggio non procedurale.

- Ricchezza espressiva (Union, Diff, End, Or, forAll, Ε, If-Then-Else…) - Moduli (Predefiniti, funzioni, parametri, asserzioni, tipi di dato)

> manipolazione Designator,

Boolean..

Costruiti intorno al modulo, usati per la dimostrazione di teoremi.

Globali o interne, informazioni sullo stato del sistema.

Special

5

Le prime tecniche di verifica formale

I primi metodi cercavano di meccanizzare e formalizzare le fasi di sviluppo di alcuni processi, portando ai moderni modelli di controllo e all’analisi di protocolli di

comunicazione.

Tra i primi

The Enhanced Hierarchical Development Methodology (EHDM)

Forniva modelli di progettazione per l’implementazione di specifiche e verifiche usando il concetto di successivi miglioramenti delle stesse. Si creava una gerarchia di macchine

astratte ed il passaggio delle informazioni in essa accresceva il livello di dettaglio.

La macchina astratta(AM) era dotata di un insieme di moduli di specifiche scritte in Special, strumenti di supporto, controlli sintattici, mappe tra coppie di macchine

6

The Hierarchical Development Methodology (EHDM)

Hdm of sri international

E’ una metodologia pensata come una Struttura gerarchica di base che doveva essere di supporto alle fasi di progettazione e implementazione di programmi generici

Supporta la descrizione di un sistema a vari livelli di astrazione usando uno specifico linguaggio,tecniche di verifica per dimostrare che i successivi livelli di astrazione fossero consistenti Multilevel Security Tool: MLS tool il primo model checking

L’input fornito era una specifica formale in SPECIAL

Strumento completamente automatico per verificare le proprietà del sistema,le violazioni

delle specifiche descrittive

MLS generator per generare formule per raffinare le

specifiche (Vc)

Theorem prover processava le formule del programma e forniva una lista di quelle che fallivano/superavano il test

7

I livelli di astrazione di HDM

Requirements

Model

External interfaces AM1

Abstract machine AM2

Primitive machine AMn

Il più basso livello è rappresentato dalla macchina primitiva, vista come una combinazione di hw e sw, che

verificava il processo in esecuzione.

La gerarchia inizia con l’analisi e l’accettazione di alcuni requisiti

che venivano estesi in un modello coerente che veniva testato e rappresentava la base delle

verifiche degli altri livelli

La prima A.M. era generalmente un’interfaccia per specifiche fornite dall’esterno. Attraverso le funzioni implementate in termini di chiamate al livello più basso, i programmi venivano scritti in un

linguaggio comprensibile al livello successivo (linguaggio intermedio).

8

In ogni macchina astratta venivano implementate delle funzioni in termini di chiamate al livello più basso che erano riunite in un programma..

Il programma risultante veniva mandato ad un traduttore che lo indirizzava nel Common Internal Form (CIF), che lo rendeva comprensibile agli strumenti del sistema il quale usando la traccia i due livelli di specifiche erano tradotte in un linguaggio intermedio.

Questo linguaggio insieme al CIF generava condizioni di verifica al dispositivo Boyer- Moore theorem prover. L’esattezza del CIF (corrispondenza con il programma) implicava

la correttezza della reale implementazione AMk

AMk+1

Mapping specification

Linguaggio intermedio CIF

Verification condition generator

Theorem prover

Proof results

Translator

Specifica del modello

verifica

Il funzionamento

9

.

The Boyer-Moore Theorem Prover

L’utente deve fornire assiomi,teoremi,lemmata, necessari durante il processo dimostrativo (rispetto di proprietà

transitiva/riflessiva/simmetria).

VCs: Verification Condition, condizioni che dovevano essere verificate provenienti dal Generator.

Conoscenze dell’utente

Traccia delle vecchie dimostrazioni Eseguiva la formula in una serie di passi

- Semplificare la formula (uso costrutti logici,lemmi).

- Riformulare la dichiarazione scambiando termini con altri più facili.

- Eguaglianze sostitutive: sostituire i vincoli con altri equivalenti.

- Generalizzare la formula: variabili al posto delle regole già dimostrate.

- Eliminazione dei termini irrilevanti.

- [Induzione per provare teoremi quando necessario]

Usciva appena ritornava una soluzione altrimenti andava al passo successivo.

10

Prototipe Verification System

Fu costruito come un prototipo da utilizzare per la verifica di modelli quali EHDM e HDM Mette a disposizione specifiche di controllo, dimostrazioni in un linguaggio leggibile ma non forniva una dettagliata metodologia di sviluppo  serve per spiegare dimostrazioni e teoremi in passi successivi

Si serve di un dispositivo di dimostrazione di teoremi molto interattivo: Theorem

prover. Proof checker: Strumento di controllo (grammaticale e sintattico).

Strumenti

Declaration: Dichiarazioni per la teoria.

Costrutti: Sottotipi, record, tipi di dato.

Libreria interna: Preludes.

11

1. Fase esplorativa: La specifica viene ripulita.

2. Fase di sviluppo: Si lavora sull’efficienza della dimostrazione.

3. Fase di presentazione: La prova viene ulteriormente raffinata e controllata.

4. Generalizzazione: Si analizza la dimostrazione per apprendere.

Il proof checker analizza la conclusione, progressivamente ricava deduzioni, scopre dei sottobiettivi e le fasi vengono ripetute fino al raggiungimento del sottobiettivo più banale, controllando che i vincoli vengano rispettati.

Deduzioni primitive:

- Regole proposizionali: Tagliare il problema in parti più piccole.

- Regole per quantificare: Variabili di tipo non numerico.

- Regole di eguaglianza: Come il rimpiazzo di una parte di eguaglianza premessa da un’altra.

- Lemmi, assiomi, procedure decisionali…

Il processo dimostrativo si divide in 4 fasi:

12

Symbolic Model Verifier (SMV)

A= inevitabile’per tutti i percorsi’, E = possibilita ’per almeno un percorso’

x= prox stato

f=qualche stato futuro g= tutti gli stati u = finchè

Questi programmi usano la logica CTL per esprimere le loro proprietà.

Le loro capacità sono:

- Verità della specifica in tutti gli stati

- Traccia delle operazioni svolte in esecuzione

Sono formati da diversi moduli (Main identifica la radice)

Può avere diversi tipi di espressioni: VAR, ASSIGN,INVAR, DEFINE,SPEC..

1°) 2°)

E’ basato sulla logica degli alberi logici (CTL) alle connessioni è attribuito un peso temporale.

La connessione è rappresentata da 2 lettere:

AX=in tutto il prossimo cammino EX= c’è almeno un prossimo cammino

13

p¹, p³ s⁰

p¹

s¹ p², p³ s²

stato iniziale

s⁰

s¹ s²

s²

s⁰ s²

s²

s²

s²

Sistema M con 3 stati possibili: s0 s1 s2 Modello rappresentativo del sistema…

Passaggio da uno stato all’altro p Atomo del sistema che si trova in

quello stato

Stati di transizione possibili:

s0s1 s0s2 s1s0 s1s2 s2s2

p1 è vero in s1 (p1 e p2) veri in s0 (p2 p3) in s2

Grafico districato:

percorsi computazionali iniziando da uno stato

14

(n¹,n²) (t¹,n²)

(c¹,n²) (t¹,t²)

(c¹,t²)

(t¹,t²)

(n¹,t²)

(n¹,c²)

(t¹,c²) s¹

s⁰

s² s³

s⁵

s⁶ s⁸

s⁴ s⁷

Stato iniziale del sistema

Il programma deve tradurre le proprietà di un sistema in elementi grafici

2 sistemi concorrenti che dividono una risorsa e non hanno accesso ad essa insieme Si dota un sistema di proprietà che

ne ‘anticipino’ la conclusione

- Quale processo (p¹ / p²) può entrare nella zona critica a quel tempo?

3 stati possibili:

Nⁱ il processo i non tenta di entrare Tⁱ il processo i tenta di entrare

Cⁱ il pocesso i si trova nella zona critica

N T C

Stati possibili del sistema: (n¹,n²), (n¹,t²), (n¹,c²), (t¹,n²), (t¹,t²), (t¹,c²), (c¹,n²), (c¹,t²) (c1,c2).

Un altro esempio

15

(n¹,n²) (t¹,n²)

(c¹,n²) (t¹,t²)

(c¹,t²)

(t¹,t²)

(n¹,t²)

(n¹,c²)

(t¹,c²) s¹

s⁰

s² s³

s⁵

s⁶ s⁸

s⁴ s⁷

Stato iniziale del sistema

Il grafico rappresenta le seguenti proprietà:

Liveness: Un processo tenta di entrare ed eventualmente ce la fa:

 Per tutti i cammini se tⁱ è vero nei passi futuri ci sarà cⁱ.  AG (tⁱ → AFcⁱ)

Safety: Solo un processo può accedere alla risorsa ad un determinato tempo:

 In tutti i cammini c¹ e c² non possono apparire simultaneamente.

 AG ¬(c¹ Λ c²)

Nonblocking: Un processo può sempre chiedere di entrare:

 Per ogni cammino ha un successore tⁱ.  AG (nⁱ → EXtⁱ)

16

Analizzatore di protocolli per i laboratori di ricerca navale

Serve per crittografare protocolli, la loro autenticazione e i protocolli di distribuzione di chiavi.

Usa il Prolog

Presupposto: Intrusi alla scoperta di informazioni per accedere ai messaggi

scambiati

L’utente specifica gli stati

‘nonsicuro’ e ne prova la raggiungibilità

NPA Temporal Requirements Language:Esprime generici requisiti di distribuzione delle chiavi in base alle esigenze

Contribuisce allo sviluppo di CAPSL (Common Autentication Protocol Specification Language):

Specifiche sul protocollo d’origine  Traduttore  Linguaggio supportato dal sistema

Protocol specification – types spec. – environment