Politically Correct
di
Emilio Italiano
Uno strumento per la verifica di Politiche di Sicurezza su History Expressions
RELATORI
GIANLUIGIFERRARI MASSIMOBARTOLETTI
ROBERTOZUNINO
Laurea Specialistica in Informatica Universitá di Pisa
Dipartimento di Informatica Aprile 2007
Indice
1 Sommario 4
2 Introduzione 5
2.1 Il contesto . . . 5
2.2 Approccio seguito . . . 6
2.3 Sviluppo di Politically Correct . . . 8
2.4 Organizzazione del testo . . . 10
3 Preliminari 12 3.1 DFA . . . 12 3.2 NFA . . . 13 3.3 PDA . . . 14 3.4 Automa di Büchi . . . 15 3.5 CFG . . . 16 3.6 BPA . . . 17 3.7 λ-calcolo . . . 18
4 λreq: un linguaggio per servizi. 20 4.1 Sintassi e Semantica Operazionale . . . 20
4.2 History Expressions . . . 22
4.3 Il Sistema di Tipo . . . 24
5 Service Orchestration 26 6 Politically Correct: Progetto e Realizzazione. 29 6.1 Preparazione Politiche . . . 29
6.2 Preparazione History Expression . . . 32
6.4 Funzionamento del sistema . . . 41
7 Politically Correct: Architettura Software 53 7.1 Module MiscFun : Varia utilitá. . . 54
7.2 Module History : Funzioni su History Expression. . . 57
7.3 Module GrammarBase : Elementi di una CFG . . . 59
7.4 Module Grammar : Gestione delle operazioni su grammatiche. . . 60
7.5 Module Bpa : Definizione di Basic Process Algebra . . . 61
7.6 Module Automata : Definizioni e funzioni su automi. . . 63
7.7 Module HistoryChecker : File principale del progetto. . . 66
8 Formati di Input 68 8.1 Paxion . . . 69
9 Output 70 10 Uso di Politically Correct 71 11 Esempio di funzionamento 73 11.1 Descrizione dell’esempio . . . 73
11.2 Esecuzione . . . 74
11.3 Esecuzione a partire da una espressione λreq . . . 77
12 Discussione 79 12.1 SPIN . . . 79
12.2 MOPED . . . 83
1
Sommario
Viene presentato il prototipo di un Model Checker per la verifica statica di proprietá di sicurezza, in un contesto di servizi distribuiti descritti tramite espressioni λreq. Queste sono un’estensione del λ-calcolo per rappresentare reti di servizi. In questo modello, sia i servizi che i loro client possono protegger-si imponendo dei vincoli di protegger-sicurezza sul comportamento delle altre entitá tramite un meccanismo di invocazione per proprietá.
L’approccio utilizzato permette di comporre i vari servizi, garantendo che la loro esecuzione sia sicura, senza dover ricorrere a verifiche dinamiche. Questo è realizzabile in quanto, a partire dalle espressioni λreq, si possono inferire a priori le possibili sequenze di eventi critici per la sicurezza, descritte tramite History Expression.
Le proprietá di sicurezza vengono rappresentate come automi di Büchi, in accordo alle piú diffuse tecniche di Model Checking, le quali vengono prese in esame in conclusione del lavoro.
Lo strumento è stato realizzato principalmente in Ocaml, con un’interfaccia grafica Java per la definizione degli automi.
2
Introduzione
2.1 Il contesto
Negli ultimi anni ha preso sempre piú piede il paradigma del Service-Oriented Computing [21], un modello computazionale per definire applicazioni distribuite che prevede di comporre insieme varie en-titá computazionali indipendenti chiamate servizi. Un servizio è un componente autonomo distribuito in una rete, accessibile tramite standard di interazione, realizzato in maniera tale da non dipendere dall’ambiente operativo, dai client o da altri servizi da lui invocati.
In un contesto di reti di servizi, la composizione di questi é spesso il problema più complesso ed inter-essante da affrontare: questa infatti può richiedere sia di gestire complessi schemi di interazione che di garantire aspetti non funzionali del sistema, come sicurezza o service level agreement, cioè le condizioni che il fornitore del servizio è tenuto a garantire in termini di qualità dello stesso. In particolare diventa non banale capire in che modo queste proprietá - non piú solo locali, ma riferite a tutto l’insieme di client e servizi - possano essere preservate. Diventa quindi necessario stabilire delle tecniche per determinare quali servizi possano essere invocati sotto particolari condizioni e quali porterebbero a violare alcuni dei requisiti richiesti.
L’orchestrazione dei servizi consiste proprio in questa loro composizione e coordinazione, basandosi sulle informazioni pubblicate dal provider, sul metodo di scelta dei client e sullo stato a run-time del servizio stesso. L’implementazione della sicurezza rende l’orchestrazione dei servizi ancora piú com-plessa. Ad esempio i servizi possono essere forniti da vari provider, ciascuno dei quali non ha motivo di ritenere sicure le esecuzioni di altri, oppure i singoli client possono voler proteggere i propri dati sensibili dai servizi da loro invocati.
Problematiche del genere sono da sempre all’ordine del giorno in qualsiasi ambito, e rappresentano una dele maggiori sfide nel campo dello sviluppo di qualunque sistema distribuito [23].
Un approccio tipicamente utilizzato per affrontare questi problemi consiste nel dotare l’infrastuttura di rete di meccanismi di autenticazione in grado di identificare i servizi presenti, certificando il loro codice come sicuro. In ogni caso spesso le politiche di sicurezza desiderate possono essere violate anche
da servizi certificati, ad esempio per comportamenti non previsti derivanti da errori nel programma o da interazioni fra servizi.
In questo lavoro si vuole affrontare esattamente questo problema: gestire l’orchestrazione di servizi distribuiti su una rete - pianificare quindi il loro utilizzo e la loro accessibilitá - garantendo che specifiche politiche di sicurezza definibili dall’usufruitore stesso dei servizi, che sia un client od un servizio a sua volta, vengano applicate ad ogni passo dell’esecuzione.
2.2 Approccio seguito
Lo sviluppo del sistema presentato in questa dissertazione ha seguito principalmente quando presen-tato in [2].
Il problema della sicurezza su una rete di servizi viene affrontato presentando un modello linguistico in cui i servizi possono proteggere parti del loro codice da chi li invoca incapsulandoli in safety framing: ciascun framing garantisce il rispetto di una specifica politica di sicurezza, interrompendo l’esecuzione del codice non appena questo la viola. Rispetto a politiche di sicurezza monolitiche e definite glob-almente, questo modello permette una maggiore flessibilitá per il programmatore, che è in grado di controllare l’accesso a singole risorse critiche.
Dal lato di chi deve invocare il servizio è invece possibile porre dei vincoli circa il comportamento del servizio stesso, imponendo un safety framing al momento della richiesta che vada a controllare se questo sia conforme a quanto desiderato. Questo tipo di invocazione dei servizi, definito come invocazione per proprietá, verrá molto sfruttato nel corso del lavoro, non solo per garantire vincoli di sicurezza ma anche per far sí che i client possano richiedere un servizio basandosi sul tipo di funzione eseguita da questo. L’invocazione per proprietá richiede quindi che tutti i servizi forniscano un’astrazione certificata del proprio comportamento.
Il modello utilizzato per realizzare questo approccio è un’estensione del λ-calcolo [19], presentata nel corso del lavoro, denominata λreq[1, 3].
Con il meccanismo dell’invocazione per proprietá e dei safety framing, la composizione dei servizi diventa sicura, in quanto puó essere esattamente stabilito come si vuole che il servizio invocato si
com-porti. Il problema di garantire la sicurezza viene quindi spostato nel determinare la sequenza di servizi da invocare a run-time.
Un piano descrive questa sequenza, orchestrando l’esecuzione dell’applicazione e associando le richi-este di servizi a quelli in precedenza selezionati. Determinare il piano viabile, il piano che cioè seleziona dalla rete i servizi che soddisfano le richieste ed i loro vincoli di sicurezza, diventa quindi il problema da affrontare.
Infatti non si puó piú pensare esclusivamente ad una verifica locale del client sui propri vincoli di sicurezza: prendiamo ad esempio un dispositivo con una limitata capacitá computazionale in grado di scaricare programmi dalla rete e quindi delegare un terzo servizio ad eseguirli. Anche se le proprietá di sicurezza del dispositivo e del provider sono soddisfatte, il programma potrebbe violare una politica di sicurezza imposta dall’esecutore. Per determinare il piano viabile è quindi necessario verificare gli effetti di tutti i servizi disponibili contro le politiche di sicurezza di tutti gli esecutori remoti.
Una soluzione al problema di determinare il piano viabile all’interno di un framework distribuito è sta-to presentata in [1]. Questa prevede che i servizi siano descritti come unitá funzionali in λreq, assegnati esplicitamente ad una locazione all’interno della rete e con un’interfaccia pubblica nota. Quest’inter-faccia include un’astrazione del comportamento del servizio, sotto forma di tipo annotato. Per ottenere un servizio un client cerca fra le interfacce pubblicate quella che soddisfa il comportamento desidera-to e la sicurezza è implementata attraverso il meccanismo di incapsulamendesidera-to del codice presentadesidera-to in precedenza.
Per modellare l’invocazione per proprietá, viene introdotto un sistema di tipi ed effetti. Il tipo di un servizio modella il suo comportamento funzionale (quindi gli effetti che si vogliono ottenere dal servizio stesso), mentre l’effetto sono le possibili sequenze degli eventi rilevanti ai fini della sicurezza, e vengono rappresentate da una History Expression. Queste sono un’estensione delle espressioni regolari con un costrutto per indicare le selezioni di piani e gli effetti che queste possono generare.
Viene quindi presentata una tecnica per estrarre da una History Expression tutti i piani viabili, cioè tutti quelli che danno luogo ad un’esecuzione sicura di tutti i servizi. Questa avviene in due passi: in primo luogo l’espressione viene trasformata in modo che sia utilizzabile come modello in un processo di
model checking, e quindi avviene la verifica vera e propria. Il fatto che un’espressione sia riconosciuta come valida garantisce che il servizio da cui è stata estratta non fallisca mai durante la sua esecuzione.
Questa tecnica di creazione e controllo di piani agisce come un orchestratore di servizi. Fornisce cioè ai client l’elenco dei servizi di cui hanno bisogno, garantendo che questi rispetteranno le proprietá di sicurezza volute. In questo contesto l’orchestratore è l’unica entitá che deve essere certificata, nè i client nè i servizi stessi hanno bisogno di una certificazione da una terza parte. In particolare l’orchestratore inferisce i tipi e gli effetti di ogni servizio, è responsabile di certificare il codice di questi (garantendo anche che non cambi durante l’esecuzione) e provvede a pubblicare sulla rete la loro interfaccia.
Quando un’applicazione viene immessa nella rete, l’orchestratore le fornisce, se esiste, un piano viabile, costruito analizzando e componendo le interfacce dei servizi disponibili.
2.3 Sviluppo di Politically Correct
L’obiettivo che questa dissertazione si pone, partendo dai risultati fin’ora descritti, è lo sviluppo di un prototipo di un Model Checker che, a partire da una rete di servizi λreq, determini i piani viabili per un client. L’implementazione si avvalerà di quanto giá fatto in [4], si dispone cioè di un sistema di inferenza dei tipi in grado di fornire la History Expression associata ad un’espressione λreq. Nella prima fase di progettazione, quindi, le espressioni λreq non sono state prese in considerazione, partendo dalla definizione di piano viabile presente in [3].
Lo scopo principale per cui Politically Correct è stato sviluppato era fornire un’implementazione rigorosa delle tecniche di verifica delle History Expression, finora presentate unicamente in via teorica, in modo da avere una base attendibile con cui verificare in seguito i risultati derivanti da ottimizzazioni sugli algoritmi o dall’utilizzo di strumenti giá esistenti di Model Checking.
L’implementazione del sistema è stata svolta in OCaml, sia perché un linguaggio funzionale con-sente di scrivere le procedure necessarie in maniera intuitiva, sia per continuitá e compatibilitá con lo strumento di inferenza dei tipi, come mostrato nell’immagine 1.
Per far questo sono stati implementati i vari passaggi che compongono l’algoritmo di verifica della validitá, utilizzando le tecniche note in letteratura per gestire le conversioni da un formalismo ad un altro
e per le trasformazioni piú comuni [18]. Il codice è stato sviluppato in maniera modulare, partendo dalla definizione in OCaml dei vari formalismi utilizzati, per procedere quindi ad implementare le diverse operazioni necessarie all’algoritmo cercando di evitare una struttura monolitica e frammentando il piú possibile questo in numerose funzioni. Una volta che tutte le singole parti dell’algoritmo sono state implementate e verificate, si è provveduto a comporle in sequenza.
In particolare possono essere individuate tre fasi distinte, che corrispondono ai tre momenti tipici di qualsiasi processo di Model Checking ([22]): la definizione della proprietà da verificare, la definizione di un modello su cui verificare la proprietà, e l’analisi vera e propria.
Lo schema seguente mostra un’idea generale dell’architettura di Politically Correct: sono distinguibili le tre diverse fasi e l’integrazione con lo strumento di tipo.
Figura 1.
Le fasi dell’esecuzione di Politically Correct
piani, si è provveduto ad integrare Politically Correct con lo strumento di inferenza dei tipi prima citato, affinchè fosse possibile determinare i piani viabili a partire non solo da una History Expression ma anche dalla descrizione in λreq del servizio.
Una volta che lo strumento vero e proprio è stato terminato, sono stati presi in considerazione due Model Checker esistenti, SPIN e MOPED [10, 14], per cercare di ottenere una verifica della validitá piú veloce rispetto a quella risultante da Politically Correct. In questa fase è stata fondamentale la modularitá dello strumento, per poter utilizzare solo le conversioni piú opportune per integrarsi con i Model Checker.
Per una maggiore usabilitá di Politically Correct, infine, è stata sviluppata un’interfaccia grafica per definire le varie politiche di sicurezza richiamate nella History Expression da esaminare, derivandola da Paxion [5], un programma Java per la definizione di automi. Gli altri elementi coinvolti nelle analisi, come le History Expression stesse, vengono fornite in maniera testuale secondo un formato giá utilizzato come output dello strumento di inferenza dei tipi.
2.4 Organizzazione del testo
Nella parte iniziale presenteremo i formalismi necessari alla trattazione degli algoritmi utilizzati: nel capitolo 3 verranno richiamati brevemente i concetti più comuni in letteratura utilizzati nel corso del lavoro, mentre nel capitolo 4 verranno presentati i risultati su cui Politically Correct si basa, cioè il linguaggio λreqe le History Expression.
Nel capitolo 5 viene descritta la tecnica di verifica di validità di un piano, presentando le teorie su cui questa si basa. Quindi queste vengono messe in pratica nel capitolo 6, dove vengono descritti passo passo i vari algoritmi utilizzati e come siano stati composti. Oltre alla descrizione di questi viene effettuata anche un’esecuzione di esempio mostrando gli effetti che generano.
Il capitolo 7, quindi, descrive l’architettura del sistema, quali siano le funzioni implementate e le varie dipendenze fra i moduli.
dei dati in input e le modalità di utilizzo; il capitolo 11 mostra, a partire da queste informazioni, il funzionamento dello strumento, presentando un esempio di esecuzione.
Infine, nel capitolo 12, viene presentata un’analisi circa l’integrazione con due Model Checker, SPIN e MOPED, illustrando come questa sia possibile ed i benefici che si possono ottenere.
3
Preliminari
Illustriamo brevemente in questo capitolo i principali formalismi utilizzati nella trattazione delle His-tory Expression e degli algoritmi implementati in Politically Correct. Sono tutte nozioni molto note in letteratura, per una loro trattazione piú approfondita rimandiamo a [18].
3.1 DFA
Automi deterministici a stati finiti. Vengono definiti da una quintupla hΣ, Q, Q0, ρ, f i, dove:
• Σ è l’insieme dei simboli riconosciuti dall’automa;
• Q l’insieme degli stati interni;
• Q0 lo stato in cui si trova l’automa al suo avvio;
• ρ la funzione di transizione, una funzione che associa ad una coppia <stato corrente,simbolo letto>
uno stato in cui l’automa transita;
• f è l’insieme degli stati finali.
Un automa è in grado di riconoscere stringhe di simboli appartenenti ad un linguaggio regolare.
Un automa puó essere rappresentato con un grafo, dove i vari stati sono rappresentati come nodi e le transizioni come archi direzionati, etichettati con il simbolo corrispondente.
Una computazione si dice che fallisce se, in un qualsiasi momento dell’esecuzione, non esiste nessuna transizione corrispondente alla coppia <stato corrente,simbolo letto>.
L’esempio seguente è un DFA, con un alfabeto binario, che determina se la stringa in input contiene un numero pari di 0:
M = hΣ, Q, Q0, ρ, f i, dove: Σ = {0, 1};
Q = {S1, S2}; Q0 = S1; f = {S1};
ρ è definita tramite la seguente tabella di
transizione:
0 1
S1 S2 S1
S2 S1 S
3.2 NFA
Automi non deterministici a stati finiti. Vengono definiti in maniera analoga ai DFA, con la signi-ficativa differenza che in questi ρ non è una funzione ma una relazione. Ad una coppia <stato cor-rente,simbolo letto>possono quindi corrispondere piú stati in cui l’automa puó transitare. DFA e NFA sono computazionalmente equivalenti.
Un NFA puó avere -transizioni, avere cioè transizioni che abbiano la stringa vuota - ,appunto - come simbolo letto. In questo caso queste sono applicabili in ogni momento a partire dallo stato dato.
L’esempio seguente mostra un NFA, con un alfabeto binario, che determina se la stringa in input con-tiene un numero pari di 0 od un numero pari di 1.
M = hΣ, Q, Q0, ρ, f i, dove: Σ = {0, 1};
Q = {S0, S1, S2, S3, S4}; Q0 = S0;
f = {S1, S3};
ρ è definita tramite la seguente tabella di transizione:
0 1 S0 {} {} {S1, S3} S1 {S2} {S1} {} S2 {S1} {S2} {} S3 {S3} {S4} {} S4 {S4} {S3} {} 3.3 PDA
Pushdown automaton. Automi non deterministici a stati finiti dotati di uno stack interno. Sono rapp-resentati da una settupla hΣ, Γ, Q, Q0, δ, z0, f i, dove Γ rappresenta l’alfabeto utilizzato dallo stack e z0 è il simbolo che si trova sullo stack all’avvio dell’automa.
La relazione di transizione δ è definita associando alla tripla
<stato iniziale, simbolo letto,simbolo stack> la coppia hstato f inale, γi, dove γ ∈ Γ∗ rappresenta la stringa che viene sostituita al simbolo sulla cima dello stack.
Possono esistere due diverse versioni di PDA, che differiscono per condizione di accettazione: una che accetta la stringa in input quando raggiunge uno stato appartenente all’insieme f , e un’altra che l’accetta quando, in un momento dell’esecuzione, la pila viene svuotata. Nel secondo caso, generalmente, f = ∅. Un PDA è piú espressivo di DFA e NFA, potendo riconoscere stringhe di simboli appartenenti a linguaggi liberi da contesto.
Ad esempio, il linguaggio libero da contesto akbk| k ≥ 0 puó essere riconosciuto dal seguente PDA: M = hΣ, Γ, Q, Q0, δ, z0, f i, dove: Σ = {a, b}; Γ = {X, Y }; Q = {q0, q1, q2, q3}; Q0 = q0; z0 = ; f = {q0, q3};
e le transizioni sono le seguenti: δ (q0, a, ) = {(q1, Y )} δ (q1, a, ) = {(q1, X)} δ (q1, b, X) = {(q2, )} δ (q1, b, Y ) = {(q3, )} δ (q2, b, X) = {(q2, )} δ (q2, b, Y ) = {(q3, )}
Il significato delle singole transizioni puó essere spiegato esaminando la prima: δ (q0, a, ) = {(q1, Y )}
Quando q0 è lo stato corrente, a è il simbolo in input ed è il simbolo preso dalla cima della pila, lo stato cambia in q1 e Y viene inserito sulla pila.
3.4 Automa di Bchi
Gli automi di Büchi - cosí chiamati dal nome di chi li ha definiti, Julius Richard Büchi - sono un’esten-sione degli automi a stati finiti per accettare stringhe di input di dimenun’esten-sione infinita [20]. Puó es-sere deterministico o non deterministico, ed è defininito analogamente agli automi a stati finiti come A = hΣ, Q, q0, ρ, f i.
Una computazione di A su una parola infinita α in Σ∗è a sua volta una parola infinita σ in Q∗, tale che σ(0) = q0 e ∀i ≥ 0, (σ (i) , α (i) , σ (i + 1)) ∈ ρ. Una computazione ha successo se in σ trovo infinite volte stati appartenenti all’insieme degli stati finali. L’automa A accetta una parola solo se esiste una computazione di successo su questa. Il linguaggio composto dalle parole riconosciute da un automa di Büchi è detto ω-regolare.
Per esempio, consideriamo il linguaggio L che contiene tutte e sole le ω-parole su Σ = {a, b, c}, tali che tra ogni coppia di occorrenze consecutive di a (ossia, tali che tra di esse non vi è alcuna altra occorrenza di a) esiste un numero pari di occorrenze di simboli diversi da a. Il linguaggio L è ω-regolare in quanto è riconosciuto dal seguente automa di Büchi:
A = hΣ, Q, q0, ρ, f i, dove Q = {q0, q1, q2};
f = {1};
ρ è definita tramite la seguente tabella di transizione:
a b c
q0 q1 q0 q0 q1 q1 q2 q2
q2 q1 q1
3.5 CFG
Grammatica Libera da Contesto. Partendo da un alfabeto di simboli terminali T e da un alfabeto di simboli non terminali V, descrive un linguaggio tramite una serie di produzioni della forma W → w, dove W ∈ V e w ∈ {(T ∪ V )∗∪ }, con rappresentante la stringa vuota. Viene descritta come “libera dal contesto” in quanto il non-terminale W puó essere sempre rimpiazzato con la stringa w, indipenden-temente dal contesto in cui questo si presenta. Un linguaggio formale è detto libero da contesto se esiste una CFG che lo puó generare.
della gramamtica, viene indicato l’elemento S0, ovverosia il simbolo non terminale da cui iniziare nella generazione di una stringa.
Definiamo -produzioni tutte le produzioni della forma A → ; produzioni unitarie tutte le produzioni della forma A → B, dove A e B sono simboli non terminali; infine simboli non utilizzati tutti i simboli non terminali non raggiungibili a partire dal simbolo iniziale.
Inoltre una grammatica è detta vuota se non è possibile generare stringhe di soli simboli terminali a partire dal simbolo iniziale.
Qualsiasi grammatica che non genera la stringa vuota puó essere converitita in una equivalente che rispetti la Forma Normale di Greibach (GNF) o la Forma Normale di Chomsky (CNF). La prima prevede che tutte le produzioni siano scritte nella forma A → αX, dove α è un simbolo terminale e X è una stringa composta da soli siboli non-terminali o è vuota. La seconda prevede che tutte le produzioni siano scritte nella forma A → BC oppure A → α, dove A,B e C sono simboli non terminali ed α è un simbolo terminale.
Prendiamo come esempio la CFG che genera il linguaggioakbk| k ≥ 0 .
G = (V, T, P, S), dove: V = {S}
T = {a, b}
P = {S → aSb | }
3.6 BPA
Basic Process Algebra [16, 15]. Fornisce una sintassi compatta ed essenziale per rappresentare pro-cessi concorrenti. La sua sintassi è definita nella grammatica seguente:
p, p0 ::= | α | p · p0| p + p0| X
dove denota un processo terminato, α un evento, X è una variabile che si riferisce ad un altro processo, · denota la composizione sequenziale, + rappresenta la composizione non deterministica.
Un processo BPA p è detto guarded se ogni variabile invocata in p compare in una sottoespressione α · q di p.
Definiamo inoltre un insieme finito ∆ =nX def= podi definizioni guarded, tale che per ogni variabile X esiste un unico p associato a quella variabile.
La semantica operazionale dei processi BPA è fornita dal seguente sistema di transizioni SOS.
α→ α p→ pα 0 p + q → pα 0 q → qα 0 p + q → qα 0 p→ pα 0 p · q→ pα 0· q p→ pα 0 X def= p ∈ ∆ X → pα 0 3.7 λ-calcolo
Questo formalismo è un modello di calcolo proposto da Alonzo Church ed è utilizzato principalmente per analizzare formalmente le definizioni di funzioni e le loro applicazioni. Presenteremo unicamente alcuni aspetti fondamentali necessari alla trattazione del λreq, per una trattazione piú estesa si veda [19]. Una sintassi minimale del λ-calcolo, che illustra le caratteristiche rilevanti per la comprensione di questo lavoro, è la seguente:
e, e0 ::= ∗ | x | λx.e | e e0
dove ∗ rappresenta l’espressione vuota, x una variabile, λx.e l’astrazione funzionale dell’espressione e con parametro formale x, e e0 l’applicazione della funzione e, utilizzando come parametro attuale la valutazione dell’espressione e0. Dato che il λ-calcolo è un formalismo Turing-equivalente, cioè possiede la stessa espressivitá delle macchine di Turing, in accordo con la tesi di Church-Turing, secondo la quale le funzioni intuitivamente calcolabili sono tutte e sole le funzioni Turing-calcolabili, ogni procedura puó essere rappresentata in questa forma.
Richiamiamo brevemente la nozione di variabile libera: una variabile x è libera nell’espressione e se xappare in e senza essere legata ad un’astrazione funzinale. Indichiamo con fv(e) la funzione che rende le variabili libere dell’espressione e:
f v(∗) = ∅
f v(x) = {x}
f v(λx.e) = f v(e)\{x}
f v(e e0) = f v(e) ∪ f v(e0)
Diremo inoltre che e è chiusa se e solo se f v(e) = ∅. La semantica operazionale del λ-calcolo è la seguente:
e1 →1 e1e2 →2
e2 →2 ve2 →2
(λx.e)v → [v\x]e
Nel nostro sistema prendiamo in considerazione il passaggio di parametri per valore ed indichiamo con v quelle espressioni che non possono essere ulteriormente ridotte; nel nostro caso tali valori possono essere espressioni vuote, variabili o astrazioni. Con [v\x]e indichiamo un’espressione ottenuta partendo da e in cui peró abbiamo sostituito le occorrenze libere di x con v.
4
λ
req: un linguaggio per servizi.
Presentiamo qui il formalismo su cui si basa il lavoro: in primo luogo l’estensione del λ-calcolo per rappresentare servizi distribuiti, e quindi la descrizione delle History Expression, che descrivono in che modo i programmi λreq possono generare sequenze di eventi.
4.1 Sintassi e Semantica Operazionale
Prima di prendere in esame le History Expression è necessario presentare l’estensione del λ-calcolo che puó rappresentare l’utilizzo di eventi di accesso e invocazione di politiche di sicurezza. La sintassi delle espressioni del linguaggio λreqè la seguente:
e, e0 ::= x | α | if b then e else e0|zx.e | e e0| ϕ[e] | reqrρ | wait l
dove α rappresenta un evento di accesso, cioè un azione rilevante ai fini della sicurezza; il costrutto
ifla scelta condizionale; ϕ[e] l’incapsulamento di codice all’interno di un safety Frame, che impone la politica ϕ all’espressione e; infine gli ultimi due costrutti modellano rispettivamente la richiesta di un servizio, dove r rappresenta il nome associato alla richiesta e ρ il tipo del servizio richiesto, e l’attesa di una risposta dal servizio in precedenza richiesto alla location l.
Definiamo una politica di sicurezza ϕ come una proprietá regolare di una sequenza η di eventi di accesso, che chiameremo history.
La valutazione stand-alone di un servizio è molto simile alla semantica call-by-value del λ-calcolo, con l’aggiunta della verifica delle politiche di sicurezza all’interno dei rispettivi framing. Poichè i servizi sono adesso considerati isolati, le richieste e le risposte non vengono considerate. Una configurazione è una coppia (history generata, espressione), indicata con η, e. Una transizione η, e → η0, e0 significa che, partendo dalla history η il servizio e evolve in e’ ed estende ηin η0.
Indichiamo con η |= ϕ quando la history η rispetta la politica ϕ. La semantica stand-alone di un servizio è quindi la seguente:
η, e1 → η0,1 η, e1e2 → η0,1e2
η, e2 → η0,2 η, ve2 → η0, ve2
η, (λzx.e)v → η, e{v/x, λzx.e/z}
η, α → ηα, ∗ η, if b then ettelse ef f → η, eβ(b) η, e → η0, e0 η0 |= ϕ η, ϕ[e] → η0, ϕ[e0] η |= ϕ η, ϕ[v] → η, v
Le prime due regole implementano la valutazione call-by-value; la terza regola implementa la β-riduzione; la valutazione di un evento di accesso consiste nell’aggiungere l’evento stesso alla history generata fino a quel momento, e quindi produrre l’espressione vuota; la scelta condizionale si com-porta nel modo prevedibile; infine per valutare un safety framing si devono considerare due casi: se partendo dalla history corrente η e puó evolvere in η0, e0 e η0 rispetta la politica di sicurezza data, allora l’espressione puó evolvere in η0, ϕ[e0]; se invece il safety framing contiene un valore e la history rispetta la politica di sicurezza, lo scope del safety framing viene lasciato. In entrambi i casi notare che se la history non rispetta la politica data la valutazione si blocca.
Quando un servizio è introdotto in un network, viene usato un piano per risolvere le richieste al suo interno, fungendo da orchestratore. Un piano π rappresenta infatti la mappatura delle richieste nelle locazioni in cui possono essere soddisfatte, ed ha la seguente sintassi
π, π0 ::= 0 | r[l] | π|π0
dove 0 rappresenta il piano vuoto, il piano r[l] associa la richiesta r al servizio pubblicato nella lo-cazione l, mentre l’operatore | rappresenta la composizione di piú piani, ed è associativo, commutativo ed idempotente. Per brevitá consideriamo solamente i piani “semplici”, in cui cioè i piani hanno una singola scelta per ogni richiesta (r[l]|r[l0] ⇒ l = l0).
Seguendo questa sintassi vengono descritti tutti i servizi che compongono il nostro network di rifer-imento, ognuno dei quali è rappresentato da un’interfaccia τ che indica il tipo del servizio stesso. Con l he : τ i si indica quindi un servizio pubblicato nella rete, dove l rappresenta la locazione in cui si trova il servizio ed e è l’espressione λreqcorrispondente. Assumiamo che ogni locazione pubblichi un singolo servizio, e che l’interfaccia di questo sia certificata, ad esempio che sia stata prodotta con lo strumento di inferenza dei tipi descritto in [4].
Un client è un particolare servizio indicato con l he : uniti. La sua particolare interfaccia fa sí che nessun altro servizio possa invocarlo.
Lo stato di un servizio di rete pubblicato è indicato con l he : τ i : π . η, e0, dove π è il piano usato dall’istanzazione corrente del servizio, η la storia fin ora generata e e0modella il codice in esecuzione.
4.2 History Expressions
Partendo dal linguaggio λreq si vuole ottenere un linguaggio che possa descrivere una sequenza di eventi di accesso, una history, generata a run-time da un network di servizi e client. Questo ha la seguente sintassi:
H, H0 ::= h α H · H0 H + H0 ϕ [H] µh.H l : H {πi. Hi}i∈I History Vuota Variabile Evento di accesso Composizione sequenziale Scelta non deterministica Safety Framing
Ricorsione Localizzazione Selezione di piani
Gli eventi di accesso rappresentano quelle azioni del programma rilevanti ai fini della sicurezza, gli operatori · e + corrispondono alla composizione sequenziale ed alla scelta non deterministica; i safety framing modellano blocchi soggetti ad una politica di sicurezza; la ricorsione viene utilizzata per cicli e funzioni ricorsive. La localizzazione l : H serve per indicare in quale locazione venga eseguito il codice H. Ad esempio l’espressione l : α · (l0 : α0) · β denota due diverse esecuzioni: α · β, che avviene nella locazione l e α0, che avviene nella locazione l0.
La selezione di piani, infine, modella il comportamento delle richieste di servizi. Ad esempio {r [l1] . H1; ...; r [lk] . Hk} significa che una richiesta r puó essere soddisfatta da uno dei servizi forniti nelle locazioni l1; ...; lk, i
quali rispettivamente possono generare le History Expression H1; ...; Hk.
Si dice che una computazione fallisce in l quando raggiunge una configurazione il cui stato nella locazione l provoca la violazione di una politica di sicurezza. Un piano π è detto viabile per e in l quando l’evoluzione dell’espressione λreqe e all’interno di un network, sotto il piano π non fallisce in l. Quindi definiamo come π-valida una History Expression H in cui il piano π è viabile per tutte le history prodotte da H sotto π.
Ad esempio, consideriamo la History Expression H1 = αc · ϕ[αr · αw], dove ϕ richiede che non avvengano scritture (αw) dopo letture (αr). Quindi H1 non è 0-valida. Infatti, sotto il piano vuoto 0,
l’evento αw avviene all’interno di un safety framing ϕ dopo un evento αr.
4.3 Il Sistema di Tipo
Abbiamo stabilito che i servizi pubblicati nella rete hanno un’interfaccia certificata. Per ottenerla viene utizzato un sistema di tipi ed effetti descritto in [1] che puó essere usato per ottenere anche un’ap-prossimazione del suo comportamento rappresentato appunto come History Expression. Presentiamo qui brevemente questo sistema.
I tipi τ, τ0 di un servizio possono essere tipi base oppure possono avere la forma τ → τH 0, dove H rappresenta l’effetto latente associato alla funzione, il quale è la History Expression associata al servizio. Questo significa che, al momento dell’invocazione del servizio stesso, viene generata una sequenza di eventi rappresentata da H.
Una valutazione di tipo Γ, H `l e : τ significa che il servizio e nella locazione l rende un valore di tipo τ e produce una sequenza di eventi denotata dalla History Expression H. Le valutazioni di tipo sono simili a quelle del semplice λ-calcolo: per dare l’idea di come gli effetti vengono inferiti forniamo la regola relativa alla tipizzazione dell’applicazione funzionale.
Γ, H `l e : τ H00
→ τ0 Γ, H le0 : τ Γ, Hle e0 : τ0
La regola mostra che e è un’espressione la cui valutazione genera una history denotata da H e che si riduce ad un valore di tipo funzione (da τ a τ0) con un effetto latente H”. La valutazione dell’argomento e0 di tipo τ genera invece una history in H’. L’effetto complessivo di e applicato a e0 è H · H0 · H00, rispettando l’ordine di valutazione della semantica call-by-value (funzione, argomento, effetto latente). Per completezza presentiamo le altre regole di tipo dei servizi.
Γ, H `` e : τ Γ, ` : H ` e : τ if e is published at ` Γ, `` ∗ : unit Γ, α `` α : unit Γ, `` x : Γ(x) Γ; x : τ ; z : τ −H→ , H `` e : Γ, `` λzx. e : τ H −→ Γ, H ``e : τ Γ, φ[H] ``φ[e] : τ Γ, H `` e : τ Γ, H `` : τ Γ, H `` ifb then e else : τ Γ, H `` e : τ Γ, H + H0 `` e : τ τ = dρ r[`0]∅, ``0 e : ` ≺ `0e : ρ ≈ Γ, `` reqrρ : τ
5
Service Orchestration
Lo scopo delle History Expression è quello di fornire un modello da cui sia possibile determinare stati-camente quali siano i piani viabili per un client; quali siano, quindi, i servizi che è in grado di invocare rispettando le proprietá di sicurezza fornite. Questa tecnica definisce uno schema per l’orchestrazione sicura di servizi.
Una volta che, tramite l’inferenza di tipo, si è determinata una History Expression corrispondente ad un client e immesso in rete, dobbiamo procedere alla verifica vera e propria, cercando di individuare i piani viabili per l’esecuzione di e. Purtroppo non è possibile verificare semplicemente che un singolo servizio rispetti i vincoli imposti, in quanto in generale la sua esecuzione puó influire sull’intera rete. Infatti possono essere invocati a cascata altri servizi che violano la politica data.
Per la sintassi delle History Expression, l’intera rete viene descritta da una struttura ad albero di selezioni di piani, cosa che rende molto difficile stabilire sotto quale piano l’intera espressione è valida.
Come esempio di questa considerazione si prenda la seguente espressione H:
{r2[l3] . l3 : α · ϕ [{r1[l1] . φ [β] , r1[l2] . β · γ}] , r2[l4] . l4 : {r1[l1] . φ [β] , r1[l2] . β · γ}}
Si puó osservare come la selezione di piani piú esterna determini in che modo debba essere gestita la richiesta r2, e come ciascuna sottoespressione contenga a sua volta un’altra selezione di piani, che determina il comportamento in seguito alla richiesta r1.
Per affrontare questo problema esiste un’analisi statica che “linearizza” questo tipo di struttura ad albero, fornendo un’insieme di History Expression, dove ciascuna di esse non ha al suo interno selezioni di piani.
Tornando all’esempio presentato poco sopra, possiamo mostrare come H sia equivalente ad H’:
{r1[l1] | r2[l3] . l3 : α · ϕ [φ [β]] ,
r1[l2] | r2[l4] . l4 : β · γ, r1[l1] | r2[l4] . l4 : φ [β] , r1[l2] | r2[l3] . l3 : α · ϕ [β · γ]}
Ogni elemento di H’ separa il piano scelto dal comportamento astratto associato, il quale non ha nessun altra scelta di piani da selezionare al suo interno. Questo fa sí che effettuare il Model Checking della validitá è molto piú semplice.
Per verificare la validitá di una History Expression senza alcuna selezione di piani è possibile utilizzare la tecnica di verifica presentata in [3], che qui viene descritta intuitivamente.
Questa consiste nel trasformare l’espressione in un processo BPA, ed utilizzare questo come modello per la verifica contro un automa a stati finiti. La procedura standard, utilizzata in generale da tutti gli strumenti di Model Checking, per controllare se un processo BPA p soddisfi una proprietá ϕ ω-regolare consiste nel costruire il PDA corrispondente a p e l’automa di Büchi corrispondente alla negazione di ϕ. La proprietá è quindi soddisfatta se il linguaggio generato dalla congiunzione degli automi cosí creati (che a sua volta è rappresentata da un PDA), è vuoto. Questo problema è decidibile, e numerosi algoritmi hanno mostrato che questo approccio è fattibile.
Purtroppo la nozione di validitá presentata in questo contesto è non regolare, in quanto possono essere presenti invocazioni di framing di sicurezza arbitrariamente annidiate. Ad esempio, il linguaggio rap-presentato dall’espressione H = µh. (α + βhh + ϕ [h]) è libero da contesto e non regolare, in quanto contiene invocazioni di framing annidiate senza limiti (si puó osservare che è equivalente al linguaggio che genera espressioni di parentesi bilanciate). Poichè il linguaggi liberi da contesto non sono chiusi sotto l’intersezione, il problema di determinare se uno di questi sia vuoto è non decidibile. Per utiliz-zare l’algoritmo presentato poco sopra è necessario quindi manipolare la History Expression affinchè la validitá sia una proprietá regolare.
Come abbiamo mostrato, la non regolaritá è una conseguenza dei framing annidiati, ad esempio inutili invocazioni a cascata dello stesso framing di sicurezza. Ad esempio la history η = αϕ[α0ϕ0[ϕ[α00]]] ha un’invocazione ridondante di ϕ attorno ad α00. Poichè α00 è giá all’interno del frame piú esterno di ϕ, possiamo intuitivamente osservare che l’espressione η0 = αϕ[α0ϕ0[α00]] è valida se e solo se η è valida. Definamo come regolarizzazione la trasformazione in grado di eliminare i safety framing ridondanti preservando la validitá, ed indichiamo con H ↓ la regolarizzazione dell’espressione H. In particolare la regolarizzazione deve provvedere ad eliminare eventuali framing ridondanti generati anche
dalle ricorsioni. Questo viene ottenuto applicando l’algoritmo presentato in [3], che in via intuitiva -trasforma il primo ciclo di ricorsione in una nuova espressione che non invoca piú il safety framing. Ad esempio l’espressione µh.(α+β·h·h+ϕ[h]) viene regolarizzata in µh.(α+β·h·h+ϕ[µk.(α+β·k·k+k)]) . Si puó osservare come, all’interno del safety framing, sia ripetuta l’intera ricorsione, senza nuove invocazioni del safety framing stesso.
Infine, per ogni politica ϕ definiamo una formula ϕ[ ] in grado di verificare la validitá di History Expression senza framing ridondanti.
Riassumendo, la validitá di una History Expression H senza selezioni di piani puó essere verificata mostrando quindi che il BPA generato dalla regolarizzazione di H (indicato come BPA(H ↓) ) soddisfa una formula appositamente costruita.
In generale H sará 0-valida se e solo se:
kBP A(H ↓)k |=V
ϕ∈Hϕ[]
In conclusione, per trovare i piani viabili per un client, bisogna in primo luogo inferire l’effetto H del client introdotto nella rete, quindi linearizzare la History Expression cosí ottenuta - in modo da avere un insieme di espressioni senza selezioni di piani - ed infine procedere con la verifica vera e propria, utilizzando come modello il processo BPA ottenuto dalla regolarizzazione di ogni sotto espressione.
Presentiamo di seguito un’analisi approfondita degli algoritmi utilizzati nel processo di verifica della validitá.
6
Politically Correct: Progetto e Realizzazione.
Viene ora presentato il nucleo della dissertazione, ovverosia il dettaglio delle funzioni che realiz-zano la verifica statica che si vuole ottenere. Molte di queste, in particolar modo le conversioni fra formalismi diversi, seguono gli algoritmi noti in letteratura. Questi passaggi non verranno presentati nel dettaglio: per una loro trattazione approndita si veda [18]. Buona parte della complessità del sis-tema deriva dall’alto numero di algoritmi necessari alla risoluzione del problema presentato, e dalla loro composizione.
Si è scelto un approccio modulare dividendo il programma in funzioni, una per ogni algoritmo uti-lizzato, anche se molte vengono utilizzate unicamente in maniera propedeutica per altre, trasformando i dati in possesso in quel momento nel formato necessario al funzionamento dell’algoritmo successivo.
Idealmente la verifica si svolge in tre fasi: una preparatoria delle politiche di sicurezza, una prepara-toria della History Expression ed infine il model checking vero e proprio.
Si veda l’immagine 1 presente nell’Introduzione per uno schema complessivo del sistema.
Vengono descritte di seguito le tre fasi della verifica. All’interno di ciascuna vengono indicate, con questo carattere, i singoli passaggi - cioè l’applicazione di particolari funzioni.
6.1 Preparazione Politiche
In questa fase Politically Correct si occupa di trasformare le politiche di sicurezza in una versione usabile come proprietà da verificare durante il Model Checking.
Le proprietà di sicurezza vengono fornite al programma come NFA etichettati, la cui etichetta è il nome della politica stessa. Si assume che esista una corrispondenza biunivoca fra i nomi delle politiche e le loro rappresentazioni come automi. L’immagine seguente mostra uno schema riassuntivo dei vari passaggi all’interno di questa fase.
Figura 2.
Algoritmi utilizzati nella Preparazione delle Politiche di Sicurezza
L’automa fornito in ingresso è in grado di verificare se una stringa rispetti o meno la politica che egli rappresenta. A partire da questo NFA devono essere effettuati i seguenti passaggi:
1. L’automa deve essere esteso affinchè riconosca gli eventi di apertura e chiusura del pro-prio Safety Framing, in modo che possa verificare l’aderenza alla politica per qualsiasi espressione, limitatamente all’ambiente del singolo framing stesso. Infatti, ad esempio, una history che non invochi mai alcun Safety Framing deve essere riconosciuta come valida dagli automi di tutte le politiche.
Aϕ = hΣ, Q, Q0, ρ, f i, una formula ϕ[ ] definita tramite l’automa di Büchi seguente Aϕ[ ] = hΣ0, Q0, Q0, ρ0, f0i Σ0 = Σ ∪ {[ϕ, ]ϕ} Q0 = f0 = Q ∪ {q0 | q ∈ f } ρ0 = ρ ∪ {hq, [ϕ, q0i | q ∈ f } ∪ {hq0, ]ϕ, qi | q ∈ f } ∪ {hp0, α, q0i | hp, α, qi ∈ ρ ∧ p, q ∈ f }
Intuitivamente, Aϕ[ ] ha due livelli. Il primo è una copia di Aϕ , dove tutti gli stati sono finali. Questo rappresenta il fatto che ci troviamo al di fuori del safety framing, e tutte le espressioni sono quindi accettabili. Il secondo livello è raggiungibile dal primo aprendo un frame della politica in esame, mentre chiudendo il frame si ritorna allo stato corrispon-dente del primo livello. Le transizioni del secondo livello corrispondono alle transizioni fra gli stati finali di Aϕ.
Da notare che l’automa cosí generato deve verificare solamente la politica ϕ, quindi le transizioni di apertura o chiusura di politiche ϕ0 6= ϕ vengono rappresentate come transizioni nello stesso stato.
2. L’automa cosí ottenuto deve essere convertito in un DFA, per una maggiore facilità d’uso nei passaggi successivi.
3. L’automa viene negato. Il risultato di questa operazione è a sua volta un DFA che ri-conosce tutte le stringhe che facevano fallire la computazione dell’automa ottenuto al passo 2.
La negazione di un automa A = hΣ, Q, Q0, ρ, f iviene cosí definita: Aneg = hΣ, Q0, Q0, ρ0, gi
Q0 = Q ∪ g , dove g è un nuovo stato
ρ0 = ρ∪{hq, s, gi |∀q, p ∈ Q, s ∈ Σ, hq, s, pi /∈ A} ∪ {hg, s, gi |s ∈ Σ}
e solo quelle.
Questi tre passaggi (Framing, Trasformazione in DFA, Negazione) vengono applicati a tutte le politiche definite, ottenendo cosí un insieme di automi di Büchi etichettati in grado di riconoscere se una parti-colare stringa faccia fallire una specifica politica di sicurezza. A questo punto le proprietà di sicurezza sono pronte per essere usate nella verifica della validità.
6.2 Preparazione History Expression
La History Expression ha bisogno di un processo di preparazione più complesso. In primo luogo devono essere infatti individuate le sotto-espressioni relative ai singoli piani, e per ciascuna di es-sere preparare il modello da verificare corrispondente ed effettuare il checking con tutte le politiche di sicurezza. L’immagine seguente mostra i vari passaggi di questa fase.
Figura 3.
Algoritmi utilizzati nella Preparazione delle History Expression
I passaggi da compiere sono quindi i seguenti:
1. La prima trasformazione da applicare alla History Expression è la linearizzazione, definita in [1]. Lo scopo è ottenere una History Expression che abbia un’unica selezione di piani, in modo che possano essere immediatamente individuate le espressioni corrispondenti
ai singoli piani. In particolare, la linearizzazione viene effettuata utilizzando le seguenti proprietá di equivalenza fra selezioni di piani:
H ≡ {0 . H} {πi. Hi}i∈I · {j . Hj}j∈J ≡ {πi |j. Hi· Hj}i∈I,j∈J {πi . Hi}i∈I + {j . Hj}j∈J ≡ {πi |j. Hi+ Hj}i∈I,j∈J ϕ{πi. Hi}i∈I ≡ {πi. ϕ [Hi]}i∈I i∈I ≡ {πi.i}i∈I n
πi. {π0i,j . Hi,j}j∈J o
i∈I ≡ {πi i,j . Hi,j}i∈I,j∈J,
dove l’operatore è definito come:
0 π = π; r[l.π0] π = r[l.π0 π] (π0|π1) π = (π0 π)|(π1 π)
Dopo aver effettuato la linearizzazione, si ottiene un insieme di espressioni, ciascuna associata ad un piano. Si vuole scoprire quale di questi sia viabile. I passaggi seguenti si applicano a ciascuna delle sotto espressioni così ricavate, tenendo traccia di quale sia il piano corrente.
2. Vengono eliminate le locazioni. Questo puó avvenire in due modi: se si è scelto di valutare l’espressione in maniera globale le locazioni vengono semplicemente rimosse dall’espressione; altrimenti, se si è scelto di valutare l’espressione per ogni locazione questa viene scomposta in piú espressioni, una per ogni locazione utilizzata. Questo viene fatto creando in primo luogo l’elenco delle locazioni menzionate nell’espressione, quindi per ciascuna di esse viene esaminata nuovamente l’espressione, sostituendo a variabili o ad eventi eseguiti al di fuori della locazione in esame il valore ε.
3. Al termine dell’eliminazione delle localizzazione ogni espressione generata contiene nu-merose parti irrilevanti ai fini del calcolo, composte di soli ε, in quanto contenevano eventi o variabili a cui si accedeva da una locazione diversa. Quindi ciascuna di queste viene ripulita secondo le seguenti regole:
ε op ε → ε H op ε → H ε op H → H ϕ [ε] → ε µh.ε → ε, dove op ∈ {·, +}.
I passaggi seguenti si applicano a tutte le espressioni così ottenute.
4. Viene individuato l’insieme delle politiche di sicurezza utilizzate dall’espressione.
Se questo è vuoto, sia perchè l’espressione non usa safety framing, sia perchè ci tro-viamo ad un passaggio avanzato dell’analisi e sono stati verificate con successo tutte le politiche utilizzate, si passa a valutare l’espressione relativa alla locazione seguente. L’espressione relativa alla particolare locazione in esame in questo caso è valida, ma affinchè tutto il piano sia valido deve esserlo in tutte le locazioni interessate.
Se invece vengono individuate altre politiche da esaminare si procede con l’algoritmo.
5. Viene effettuata la regolarizzazione dell’espressione, definita informalmente nel capi-tolo precedente. Questa è necessaria per eliminare i framing di sicurezza ridondanti all’interno dell’espressione stessa.
applicando la funzione di traduzione h2b definita come segue: • h2b() ⇒
• h2b(h) ⇒ X, dove X è la variabile corrispondente al processo che denota la ricorsione su h.
• h2b(α) ⇒ α
• h2b(H · H0) ⇒ h2b(H) · h2b(H0)
• h2b(H + H0) ⇒ h2b(H) + h2b(H0)
• h2b(ϕ [H]) ⇒ oϕ· h2b(H) · cϕ, dove oϕe cϕ sono due nuovi eventi che indicano l’apertura
e la chiusura del safety framing ϕ
• h2b(µh.H) ⇒ X, dove X è un nuovo nome di variabile a cui viene associato il processo
h2b(H) e la variabile h.
7. Il processo BPA viene trasformato in una grammatica libera da contesto. Per la sintassi dei BPA, molto simile a quella delle CFG, la traduzione è banale.
8. Alla grammatica cosí ottenuta vengono quindi rimossi i simboli non utilizzati, le ε-produzioni e le produzioni unitarie utilizzando gli algoritmi noti in letteratura. Questo viene effettuato in quanto precondizione necessaria degli algoritmi successivi.
9. La grammatica viene riscritta prima in forma normale di Chomsky (CNF)...
10. ...e quindi in forma normale di Greibach (GNF).
Questi due passaggi vengono effettuati perché l’algoritmo utilizzato dopo richiede che la grammatica si trovi in GNF e perché una grammatica sia convertita in questa forma prima deve trovarsi in CNF.
11. La grammatica così ottenuta viene esaminata nuovamente dalla funzione descritta al pas-so 8, per eliminare eventuali produzioni superflue generate dall’algoritmo di conversione in GNF.
12. La grammatica viene trasformata in un pushdown automata (PDA) ad accettazione per pila vuota.
13. L’automa cosí ottenuto viene converito perché accetti quando raggiunge uno stato finale, e non piú quando la pila interna è vuota.
Alla fine della seconda fase abbiamo ottenuto il modello da verificare, un PDA che accetta per condizione di stato finale raggiunto, una scelta condivisa da molti strumenti di model checking ([14, 10]).
6.3 Model Checking
Una volta che abbiamo ottenuto sia il modello da verificare, il PDA rappresentante una History Ex-pression, che la proprietà contro cui effettuare il controllo, è possibile iniziare la procedura di controllo vera e propria.
Figura 4.
Algoritmi utilizzati nella fase di Model Checking
Questi vengono qui di seguito descritti nel dettaglio:
1. Per ogni politica individuata al passo 2.4 viene effettuata la congiunzione fra il PDA ot-tenuto al termine della preparazione del modello e l’automa corrispondente alla politica in esame. Questa viene effettuata secondo il seguente algoritmo:
P OL = hΣ, Q, Q0, δ, f i ; HIS = hΣ0, Γ, Q0, Q00, δ 0, z
0, f0i P OL0 = hΣ ∪ Σ0, Q, Q0, δ00, f i
δ00 = δ ∪ {hs, q, si |∀q ∈ Q, s ∈ Σ0\Σ},
dove POL è il DFA della politica di sicurezza e HIS è il PDA dell’History Expression
Questo viene effettuato per far sí che l’automa riconosca anche gli eventi non pre-visti esplicitamente dalla politica di sicurezza (in particolar modo apertura e chiusura di altri framing).
(b) Viene generata una struttura dati tale che associ un diverso numero identificativo ad ogni coppia (q, p), ∀q ∈ Q, p ∈ Q0. Questa costituirá l’insieme degli stati dell’automa congiunzione.
(c) Viene generata una tabella costituita da tutti gli elementi (q, p, symb, stack), ∀q ∈ Q, p ∈ Q0, symb ∈ Σ, stack ∈ Γ
(d) La tabella generata al punto (c) viene scansionata, e vengono mantenuti solo gli elementi
{(q, p, symb, stack) | (q, symb, p) ∈ P OL0, ∃f.(q, symb, stack, p, f ) ∈ HIS}.
(e) L’automa congiunzione è quindi definito come
CON J = hΣ ∪ Σ0, Γ, Q00, Q000, δ000, z0, f00i
dove Q00, Q000, f00 sono definiti come la traduzione secondo la struttura dati definita in (b) di tutte le coppie di stati, della coppia di stati iniziali, di tutte le coppie di stati finali. δ000è invece definito con gli elementi generati in (d)
Ottengo quindi un PDA che accetta tutte e solo le sequenze di caratteri accettate sia dal DFA che dal PDA in ingresso, cioè le history che possono essere generate dalla sottoespressione corrente e che violano la politica in esame.
2. Il PDA cosí ottenuto viene convertito in una CFG. Questo è possibile in quanto hanno la stessa capacitá espressiva. Questa conversione è il passaggio computazionalmente
più costoso dell’intero sistema. Devono essere generate un numero molto elevato di produzioni, anche se molte si riveleranno inutili.
3. La grammatica cosí ottenuta passa nuovamente attraverso il passo 2.11 per eliminare le produzioni superflue generate nella conversione.
4. Viene verificato se la CFG è vuota, cioè se a partire dal simbolo iniziale non possano essere generate stringhe di soli simboli terminali. Per determinare questo, si calcola l’in-sieme dei simboli non terminali “utili”, quelli cioè che possono generare una sequenza di soli terminali. Se il simbolo iniziale non appartiene a questo insieme, allora la CFG è vuota.
Se questa condizione è falsa l’analizzatore calcola una possibile stringa generata dalla grammatica, che è esattamente una sequenza che viola la politica in esame. Inoltre si passa a prendere in esame il piano successivo, in quanto questo è stato appena trovato non viabile, ritornando quindi al punto 2.2.
Qualora invece la condizione fosse soddisfatta si passa ad esaminare la politica succes-siva, ritornando quindi al passo 3.1.
5. Nel momento in cui non ci sono piú politiche da esaminare - e sono state quindi tutte verificate con successo - si passa ad esaminare la locazione seguente, tornando quindi al passo 2.3.
6. Nel momento in cui tutte le locazioni sono state verificate con successo il piano corrente viene aggiunto alla lista dei piani viabili, in quanto soddisfa tutte le politiche di sicurezza in ogni sua locazione, e si passa ad esaminare il piano successivo ritornando al punto 2.2.
7. Quando sono terminate le sottoespressioni relative ai piani da esaminare, il programma rende la lista di tutti i piani viabili.
Da notare che nell’algoritmo proposto c’è una differenza strutturale piuttosto significativa rispetto a quanto illustrato precedentemente nella teoria. Infatti la History Expression non viene verificata contro la congiunzione di tutte le politiche di sicurezza, bensí vengono effettuate piú iterazioni, ognuna delle quali verifica una singola politica.
Questo viene effettuato per evitare che l’algoritmo di conversione da PDA a CFG subisca un aumento spropositato del proprio tempo di esecuzione, dovuto al considerevole aumento di stati del PDA.
6.4 Funzionamento del sistema
Viene ora mostrata un’esecuzione passo passo di Politically Correct, evidenziando ad ogni passaggio come evolva l’algoritmo presentato. I dati sono estratti da un normale ciclo di esecuzione di Politically Correct, impostato per mostrare a video i passaggi rilevanti.
Per una descrizione dell’esempio utilizzato, si veda di seguito nel capitolo 11.
Vengono inizialmente mostrati gli automi relativi alle politiche di sicurezza e la History Expression da esaminare.
Initial History:
{Fail[0].Empty |> mu h.((alpha() + ((beta() ^ h) ^ h)) + rho[h]),
Work[1].Empty |> phi[(mu h.((alpha() + ((beta() ^ h) ^ h)) + h) ^ gamma())]}
Initial Policies: phi:
Q: [1; 2; 3]
Sigma: [alpha; beta; gamma] Delta (NFA): d(1, alpha) -> (1) d(1, beta) -> (2) d(1, gamma) -> (1) d(2, beta) -> (2) d(2, alpha) -> (1) d(2, gamma) -> (3) d(3, alpha) -> (3) d(3, beta) -> (3) d(3, gamma) -> (3) Q0: 1
Final set status: [1; 2] rho:
Q: [1; 2; 3]
Sigma: [alpha; beta] Delta (NFA): d(1, alpha) -> (1) d(3, alpha) -> (3) d(3, beta) -> (3) d(2, beta) -> (2) d(2, alpha) -> (3) d(1, beta) -> (2) Q0: 1
Final set status: [1; 2]
Inizia la fase 1: le due politiche vengono preparate in modo da essere utilizzate nel Model Checking. Per brevità indichiamo unicamente i passaggi di phi:
(1.1): Creazione versione “Framed”
Creating framed Buchi for Policy phi... Result:
Q: [1; 2; 3; 4; 5]
Sigma: [alpha; beta; c-phi; gamma; o-phi] Delta (NFA): d(1, o-phi) -> (4) d(4, c-phi) -> (1) d(2, o-phi) -> (5) d(5, c-phi) -> (2) d(4, alpha) -> (4) d(4, beta) -> (5) d(4, gamma) -> (4) d(5, beta) -> (5) d(5, alpha) -> (4) d(1, alpha) -> (1) d(1, beta) -> (2) d(1, gamma) -> (1) d(2, beta) -> (2) d(2, alpha) -> (1) d(2, gamma) -> (3) d(3, alpha) -> (3)
d(3, beta) -> (3) d(3, gamma) -> (3) Q0: 1
Final set status: [1; 2; 3; 4; 5] done!
(1.2): Trasformazione in DFA: Converting NFA in DFA...
Resulting DFA: Q: [1; 2; 3; 4; 5]
Sigma: [alpha; beta; c-phi; gamma; o-phi] Delta (DFA): d(1, alpha) -> (1) d(1, beta) -> (3) d(1, gamma) -> (1) d(1, o-phi) -> (2) d(3, alpha) -> (1) d(3, beta) -> (3) d(3, gamma) -> (5) d(3, o-phi) -> (4) d(5, alpha) -> (5) d(5, beta) -> (5) d(5, gamma) -> (5) d(2, alpha) -> (2) d(2, beta) -> (4) d(2, c-phi) -> (1) d(2, gamma) -> (2) d(4, alpha) -> (2) d(4, beta) -> (4) d(4, c-phi) -> (3) Q0: 1
Final set status: [1; 2; 3; 4; 5] done!
(1.3): Negazione
Applying negation to DFA... Result:
Q: [1; 2; 3; 4; 5; 6]
Sigma: [alpha; beta; c-phi; gamma; o-phi] Delta (DFA):
d(6, alpha) -> (6) d(6, beta) -> (6)
d(6, c-phi) -> (6) d(6, gamma) -> (6) d(6, o-phi) -> (6) d(1, alpha) -> (1) d(2, alpha) -> (2) d(3, alpha) -> (1) d(4, alpha) -> (2) d(5, alpha) -> (5) d(1, beta) -> (3) d(2, beta) -> (4) d(3, beta) -> (3) d(4, beta) -> (4) d(5, beta) -> (5) d(1, c-phi) -> (6) d(2, c-phi) -> (1) d(3, c-phi) -> (6) d(4, c-phi) -> (3) d(5, c-phi) -> (6) d(1, gamma) -> (1) d(2, gamma) -> (2) d(3, gamma) -> (5) d(4, gamma) -> (6) d(5, gamma) -> (5) d(1, o-phi) -> (2) d(2, o-phi) -> (6) d(3, o-phi) -> (4) d(4, o-phi) -> (6) d(5, o-phi) -> (6) Q0: 1
Final set status: [6] done!
Con la creazione dell’automa rappresentante la negazione della politica di sicurezza, la prima fase è conclusa. Come già detto, omettiamo di presentare la preparazione dell’altra politica, in quanto del tutto analoga a questa.
Passiamo adesso ad esaminare la fase di preparazione del modello da esaminare.
(2.1): History Linearization: History Linearization...
Linearized History: {Fail[0].Empty |> mu h.((alpha() + ((beta() ^ h) ^ h)) + rho[h]), Work[1].Empty |> phi[(mu h.((alpha() + ((beta() ^ h) ^ h)) + h) ^ gamma())]}
done!
(2.2): Separazione delle Locazioni. Viene selezionata la prima sottoespressione derivante da (2.1) Dividing Locations...
Resulting Histories:
Location -1: mu h.((alpha() + ((beta() ^ h) ^ h)) + rho[h]) done!
(2.3): Rimozione degli :questa fase purtroppo non è evidente nell’esempio scelto. Notare inoltre che dal passo 2.2 emerge un’unica espressione, in quanto non ci sono localizzazioni.
(2.4): L’insieme delle politiche non viene mostrato, risulterà evidente dallo svolgimento seguente. (2.5): Regolarizzazione.
Regolarizing history...
Signed History: mu h.((alpha + ((beta ^ h1) ^ h2)) + rho[h3])
Regolarized history: mu h.((alpha() + ((beta() ^ h) ^ h)) + rho[mu h.((alpha() + ((beta() ^ h) ^ h)) + h)])
done!
(2.6): Conversione in BPA:
Converting History Expression into BPA process... Resulting BPA: A
A: ((alpha + ((beta ^ A) ^ A)) + ((o-rho ^ B) ^ c-rho)) B: ((alpha + ((beta ^ B) ^ B)) + B)
done!
(2.7): Conversione in CFG:
Converting BPA process into CFG grammar (CNF)... Resulting Grammar:
NT: [A; B; C; D; E; F; G; H; I; J; K; L; M; N; O; P; Q; R; S; T; U; V; W] T: [alpha; beta; c-rho; o-rho]
PROD: A-> L A-> M B-> D B-> E C-> A D-> F
D-> G E-> B F-> alpha G-> H^I H-> J^K I-> B J-> beta K-> B L-> R L-> S M-> N^O N-> P^Q O-> c-rho P-> o-rho Q-> B R-> alpha S-> T^U T-> V^W U-> A V-> beta W-> A S :C done!
(2.8): Pulizia della Grammatica. Clearing Grammar...
NT: [H; N; O; P; Q; T; V; W] T: [alpha; beta; c-rho; o-rho] PROD: H-> V^Q N-> P^Q O-> c-rho P-> o-rho Q-> H^Q Q-> alpha T-> V^W V-> beta W-> N^O W-> T^W W-> alpha S :W
done!
(2.9): Conversione in CNF: la grammatica si trova già in CNF.
(2.10): Conversione in GNF (per brevità viene riportata la versione già ripulita dal passaggio 2.11): Converting Grammar in Greibach Normal Form...
NT: [O; Q; W]
T: [alpha; beta; c-rho; o-rho] PROD: O-> c-rho Q-> alpha Q-> beta^Q^Q W-> alpha W-> beta^W^W W-> o-rho^Q^O S :W done! (2.12): Conversione in PDA. Converting CFG into PDA... Generated PDA:
Q: [0]
Sigma: [alpha; beta; c-rho; o-rho] Stack: [O; Q; W] Delta: d(0, c-rho, O) -> (0, []) d(0, alpha, Q) -> (0, []) d(0, beta, Q) -> (0, [Q; Q]) d(0, alpha, W) -> (0, []) d(0, beta, W) -> (0, [W; W]) d(0, o-rho, W) -> (0, [Q; O]) Q0: 0 Z0: W
Final set status: []
done!
(2.13): Conversione in PDA ad accettazione per stato finale.
Converting PDA (acceptance by Empty Stack) in PDA (acceptance by Final Status)... Resulting PDA:
Sigma: [; alpha; beta; c-rho; o-rho] Stack: [!inital!; O; Q; W] Delta: d(1, , !inital!) -> (0, [W; !inital!]) d(0, c-rho, O) -> (0, []) d(0, alpha, Q) -> (0, []) d(0, beta, Q) -> (0, [Q; Q]) d(0, alpha, W) -> (0, []) d(0, beta, W) -> (0, [W; W]) d(0, o-rho, W) -> (0, [Q; O]) d(0, , !inital!) -> (2, []) Q0: 1 Z0: !inital!
Final set status: [2] done!
Con il passo 2.13 termina la preparazione del modello. Si può adesso procedere con la verifica vera e propria.
(3.1) Congiunzione: per una sua migliore comprensione viene mostrata la tabella di corrispondenza degli stati e quindi il PDA risultante dalla congiunzione dell’espressione preparata e dell’automa cor-rispondente all’unica politica che essa contiene, ϕ.
Applying conjunction between DFA and PDA... Status Table (DFA,PDA)->Conj :
(1,0)->1 (1,1)->2 (1,2)->3 (2,0)->4 (2,1)->5 (2,2)->6 (3,0)->7 (3,1)->8 (3,2)->9 (4,0)->10 (4,1)->11 (4,2)->12 (5,0)->13 (5,1)->14 (5,2)->15 (6,0)->16 (6,1)->17
(6,2)->18 Result:
Q: [1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18] Sigma: [; alpha; beta; c-rho; o-rho]
Stack: [!inital!; O; Q; W] Delta: d(1, , !inital!) -> (3, []) d(1, alpha, Q) -> (1, []) d(1, alpha, W) -> (1, []) d(1, beta, Q) -> (7, [Q; Q]) d(1, beta, W) -> (7, [W; W]) d(1, c-rho, O) -> (16, []) d(1, o-rho, W) -> (4, [Q; O]) d(2, , !inital!) -> (1, [W; !inital!]) d(4, , !inital!) -> (6, []) d(4, alpha, Q) -> (4, []) d(4, alpha, W) -> (4, []) d(4, beta, Q) -> (10, [Q; Q]) d(4, beta, W) -> (10, [W; W]) d(4, c-rho, O) -> (1, []) d(4, o-rho, W) -> (16, [Q; O]) d(5, , !inital!) -> (4, [W; !inital!]) d(7, , !inital!) -> (9, []) d(7, alpha, Q) -> (13, []) d(7, alpha, W) -> (13, []) d(7, beta, Q) -> (7, [Q; Q]) d(7, beta, W) -> (7, [W; W]) d(7, c-rho, O) -> (16, []) d(7, o-rho, W) -> (10, [Q; O]) d(8, , !inital!) -> (7, [W; !inital!]) d(10, , !inital!) -> (12, []) d(10, alpha, Q) -> (16, []) d(10, alpha, W) -> (16, []) d(10, beta, Q) -> (10, [Q; Q]) d(10, beta, W) -> (10, [W; W]) d(10, c-rho, O) -> (7, []) d(10, o-rho, W) -> (16, [Q; O]) d(11, , !inital!) -> (10, [W; !inital!]) d(13, , !inital!) -> (15, []) d(13, alpha, Q) -> (13, []) d(13, alpha, W) -> (13, []) d(13, beta, Q) -> (13, [Q; Q]) d(13, beta, W) -> (13, [W; W])
d(13, c-rho, O) -> (16, []) d(13, o-rho, W) -> (16, [Q; O]) d(14, , !inital!) -> (13, [W; !inital!]) d(16, , !inital!) -> (18, []) d(16, alpha, Q) -> (16, []) d(16, alpha, W) -> (16, []) d(16, beta, Q) -> (16, [Q; Q]) d(16, beta, W) -> (16, [W; W]) d(16, c-rho, O) -> (16, []) d(16, o-rho, W) -> (16, [Q; O]) d(17, , !inital!) -> (16, [W; !inital!]) Q0: 2 Z0: !inital!
Final set status: [18]
(3.2) La CFG risultante dalla conversione non viene qui mostrata, in quanto, come già detto, troppo lunga. L’effetto è comunque comprensibile esaminando la grammatica risultante dal passo successivo.
Converting PDA into CFG...done!
(3.3) La grammatica così ottenuta viene ripulita con la stessa funzione usata in (2.3) Clearing Grammar...
NT: [KL; L; NH; O; S; T; V; W; WO; WY; X; Y] T: [; alpha; beta; c-rho; o-rho]
PROD: KL-> beta^O^W L-> alpha L-> beta^L^T NH-> beta^L^WY NH-> beta^NH^X NH-> o-rho^O^Y O-> alpha O-> beta^O^W S-> WO^V S-> beta^L^WY S-> beta^NH^X S-> o-rho^KL^Y T-> alpha T-> beta^T^T W-> alpha W-> beta^W^W
WO-> beta^L^WY WO-> beta^NH^X WO-> o-rho^KL^Y WY-> beta^T^WY WY-> beta^WY^X WY-> o-rho^W^Y X-> alpha X-> beta^X^X X-> o-rho^W^Y Y-> c-rho S :S done!
(3.4): Si determina se la grammatica così generata è vuota: viene quindi calcolato l’insieme dei sim-boli utili.
Checking for useful symbols... Initial New V: [L; O; T; W; X; Y] Initial Old V: []
New V: [KL; L; NH; O; T; W; WY; X; Y] Old V: [L; O; T; W; X; Y]
New V: [KL; L; NH; O; S; T; W; WO; WY; X; Y] Old V: [KL; L; NH; O; T; W; WY; X; Y]
New V: [KL; L; NH; O; S; T; W; WO; WY; X; Y] Old V: [KL; L; NH; O; S; T; W; WO; WY; X; Y] Final set: [KL; L; NH; O; S; T; W; WO; WY; X; Y]
The Grammar is Empty: false
La grammatica risulta essere non vuota. Questo significa che esiste una sequenza che può essere gen-erata dalla History Expression che viola la politica. Politically Correct mostra un esempio:
Plan (Fail[0].Empty) doesn’t respect rho at location -1. A possible violation is: beta^alpha^o-rho^alpha^c-rho
Poichè ci sono altri piani da esaminare, Politically Correct torna al passo (2.1). La preparazione del-l’espressione relativa al secondo piano dà luogo al PDA seguente:
Sigma: [; alpha; beta; c-phi; gamma; o-phi] Stack: [!inital!; B; L; N; O; P] Delta: d(1, , !inital!) -> (0, [B; !inital!]) d(0, o-phi, B) -> (0, [N; L]) d(0, c-phi, L) -> (0, []) d(0, alpha, N) -> (0, [P]) d(0, beta, N) -> (0, [O; O; P])
d(0, alpha, O) -> (0, []) d(0, beta, O) -> (0, [O; O]) d(0, gamma, P) -> (0, []) d(0, , !inital!) -> (2, []) Q0: 1
Z0: !inital!
Final set status: [2]
Il PDA così ottenuto viene messo in congiunzione con l’automa relativo all’unica politica utilizzata, φ. I passaggi da 3.1 e 3.2 non vengono presentati, in quanto analoghi al caso precedente. La CFG risul-tante dal passo 3.3 è la seguente.
NT: [S]
T: [; alpha; beta; c-phi; gamma; o-phi] PROD:
S :S
E’ evidente che la grammatica così ottenuta è vuota. Poichè non ci sono nè altre politiche nè altre locazioni da esaminare, il piano corrente viene aggiunto ai piani viabili.
The Grammar is Empty: true
All Policies Respected in Location -1
All Policies Respected in All Location By Plan Work[1].Empty
Anche i piani sono terminati. Viene quindi mostrato il risultato dell’elaborazione, cioè la lista dei piani viabili (in questo caso solo uno).
7
Politically Correct: Architettura Software
Tutto il sistema è stato sviluppato in Ocaml[7, 9, 8]. E’ stato organizzato in moduli, e le relazioni di dipendenza sono riportate nello schema sottostante.
Figura 5.
Grafo delle dipendenze dei moduli.
è stato escluso dalla documentazione il modulo Memories, che contiene al suo interno una serie di classi che vengono istanziate nelle varie funzioni. Queste vengono utilizzate per avere una struttura dati indipendente dalle ricorsioni e dotata di un’interfaccia semplice sia per l’accesso ai dati che per la loro rappresentazione.
Non sono inoltre inclusi i vari compilatori, realizzati in OcamlYacc e OcamlLex, per gestire l’input di automi, History Expression ed espressioni λreq. La loro definizione, comunque, è abbastanza intuitiva a partire dalle informazioni del capitolo seguente.
La documentazione generata da Ocamldoc fornisce un’idea abbastanza completa della struttura del codice.
Lo sviluppo è stato prima effettuato con uno dei più noti ambienti OCaml, Camelia, quindi si è passati, data la complessità di gestione delle dipendenze in questo, ad utilizzare Eclipse [6] con il supporto adeguato al linguaggio.
7.1 Module MiscFun : Varia utilit.
Contiene una raccolta di funzioni generiche utilizzate in tutto il progetto. Contiene anche la definizione degli insiemi di elementi piú utilizzati dai vari algoritmi.
module NTset : sig
type elt = string
end
Insieme di simboli non terminali di CFG.
module Tset : sig
type elt = string
end
Insieme di simboli terminali di una CFG.
module Qset : sig
type elt = int
end
module Sset : sig
type elt = string
end
Insieme di simboli utilizzati da un automa, sia per rappresentare stringhe di input che per simboli nello stack di un PDA.
module QSset : sig
type elt = MiscFun.Qset.t
end
Insieme di insiemi di stati di un automa. Utilizzato per la conversione da NFA a DFA.
module QSQset : sig
type elt = MiscFun.Qset.elt
* MiscFun.Sset.elt * MiscFun.Qset.elt
end
Insieme di terne <stato, simbolo, stato>, utilizzato nella conversione da PDA a CFG.
val printstringlist : string list -> unit
Stampa a video una lista di stringhe.
val printintlist : int list -> unit
Stampa a video una lista di interi.
