Interpretazione Astratta per il pi-calcolo

(1)

A Vittorio Anna

A Marco Valentina

(2)

(3)

In questa tesi presentiamo un’applicazione dell’interpretazione astratta al π-calcolo. In particolare, introduciamo un framework generale, basato su una nuova semantica, detta semantica normale, che consente di derivare ana-lisi che forniscono informazioni approssimate sull’evoluzione dei processi a run-time. Più precisamente, lo scopo è di derivare, per ogni processo rag-giungibile, informazioni che permettono di osservare una classe di proprietà sulle possibili comunicazioni. Definiamo inoltre un’opportuna astrazione del-la semantica normale, allo scopo di ricostruire l’analisi presentata da Bodei in [3, 2, 5]. L’informazione calcolata dall’analisi può essere successivamente usata per verificare interessanti proprietà di sicurezza.

(4)

(5)

1 Introduzione 1

2 Nozioni generali 7

2.1 Il π-calcolo . . . . 7

2.1.1 Semantica a Riduzioni . . . 10

2.2 Interpretazione Astratta . . . 13

3 Un framework di intepretazione astratta per il π-calcolo 17 3.1 Sintassi e semantica del π-calcolo per processi etichettati . . . 18

3.2 Semantica Normale . . . 22

3.2.1 Stati . . . 22

3.2.2 Funzione di normalizzazione . . . 29

3.2.3 Regole di transizione . . . 32

3.3 Relazione tra semantica normale e semantica a riduzioni . . . 35

3.3.1 Semantica a riduzioni decorata . . . 36

3.3.2 Equivalenza tra stati concreti . . . 40

3.3.3 Relazione tra semantica normale e semantica a ridu-zioni decorata . . . 41

3.4 Semantica Collecting . . . 42

4 Astrazione della semantica normale 45 4.1 Dominio astratto . . . 46

4.1.1 Stati astratti . . . 46

4.2 Connessione di Galois . . . 50 v

(6)

4.3 Semantica astratta . . . 53 4.3.1 Funzione di normalizzazione astratta . . . 53 4.3.2 Regole di transizione astratte . . . 55 4.3.3 Definizione e correttezza della semantica astratta . . . 56 4.3.4 Esempi . . . 58

5 Conclusioni e lavori correlati 65

A Dimostrazioni del Capitolo 3 69

(7)

2.1 Congruenza Strutturale . . . 11

2.2 Regole di riduzione del π−calcolo . . . . 12

3.1 Funzione di normalizzazione δ . . . . 30

3.2 Transizioni 7→ . . . . 33

3.3 Regole di riduzione decorate per processi ben-etichettati . . . 36

4.1 Funzione di Normalizzazione δ◦ _{. . . .} ₅₄

4.2 Transizioni astratte 7→◦ _{. . . .} ₅₅

(8)

(9)

Introduzione

La grande diffusione di reti di calcolatori e di sistemi distribuiti ha introdot-to nuovi scenari in cui la sicurezza, e in particolare i prointrodot-tocolli di sicurezza, giocano un ruolo fondamentale. Questi sistemi permettono la condivisione di risorse e dati tra pi`u utenti e sono generalmente caratterizzati dalla mobilit`a di codice e/o agenti.

I protocolli di sicurezza sono programmi distribuiti progettati per garantire su reti di calcolatori alcune proprietà fondamentali come segretezza, auten-ticazione e integrità. Tali protocolli sono basati sull’utilizzo di tecniche di crittografia e particolari regole per lo scambio di messaggi. La segretezza ri-guarda la protezione di informazioni segrete, per esempio si vuole assicurare che un messaggio inviato sia compreso solo dal mittente e dal destinatario. Lo scopo dell’autenticazione è invece quello di garantire che gli agenti non mentano sulla propria identità. Infine, l’integrità assicura che l’informazio-ne non venga manipolata da agenti non autorizzati. Un’altra proprietà di sicurezza è la non-interferenza, che mira ad impedire che un agente esterno derivi informazioni critiche anche non direttamente.

In questo contesto, l’utilizzo di metodi formali si `e rivelato fondamentale sia per la specifica dei protocolli di sicurezza, sia per sviluppare tecniche di ve-rifica e di analisi che ne garantiscono le propriet`a.

Le algebre di processi sono uno degli approcci per la specifica sia di sistemi 1

(10)

concorrenti e distribuiti che di sistemi mobili, che hanno avuto pi`u succes-so. Tali sistemi sono formati da differenti componenti attive, dette processi o agenti, che possono agire indipendentemente oppure interagire attraverso azioni atomiche, per esempio azioni di input/output. Le azioni insieme agli operatori sono gli elementi di base di un’algebra. Gli operatori permettono di costruire espressioni che rappresentano la struttura del sistema che si vuole modellare e ne descrivono il comportamento. Esempi di operatori sono: la composizione parallela, la scelta non deterministica, il prefisso e operatori di scope come la restrizione.

Tra le algebre di processi classiche troviamo il CCS (Calculus of Commu-nicating Systems) [22, 23], proposto da Milner, e il CSP (CommuCommu-nicating Sequential Processes), descritto da Hoare [17]. Questi due formalismi sono stati progettati attorno al 1980 per modellare sistemi concorrenti. Successi-vamente, alla fine degli anni 80, Milner ha introdotto un’estensione del CCS, il π-calcolo [25, 24], adatto a descrivere sistemi mobili, ovvero sistemi in cui la topologia dei canali di comunicazione cambia dinamicamente. Le entit`a base del π-calcolo sono i nomi, che rappresentano i canali di comunicazione e che possono essere trasmessi.

Pi`u recentemente varie algebre di processi sono state proposte per modellare concetti di locazione, mobilit`a di processi e computazioni mobili. Tra queste troviamo l’ambient calculus [7], il distributed π-calculus [16] e il join calculus [13].

La verifica della sicurezza di un sistema è un problema molto difficile. Infatti, tipicamente è necessario considerare tutte le possibili esecuzioni ed osservare che un determinato evento non si possa verificare mai. Di conseguenza, il problema può essere indecidibile.

Per questo motivo sono state progettate molte tecniche formali per lo studio e la verifica di propriet`a di sicurezza. In tale contesto, un approccio ben noto consiste nell’applicazione di tecniche di analisi statica [27], che forniscono ap-prossimazioni corrette del comportamento run-time di un programma, senza eseguirlo.

(11)

L’analisi statica di programmi tradizionalmente `e stata usata per l’ottimiz-zazione dei compilatori. Gli approcci principali per l’analisi statica sono: Interpretazione Astratta [10, 11], Data Flow Analysis [18], Control Flow Analysis (CFA) [26] e Sistemi di Tipi [15].

Nel contesto delle algebre di processi, la verifica di protocolli di sicurezza richiede generalmente di controllare tutti gli stati raggiungibili. Quindi, le tecniche di analisi statica calcolano tipicamente informazioni su tutte le possi-bili esecuzioni, fornendo informazioni approssimate sulla struttura topologica di tutti gli stati raggiungibili. Queste informazioni sono adeguate per provare propriet`a di invarianza, che valgono in ogni stato raggiungibile. In genere, garantiscono che un certo evento non si verificher`a mai in alcun stato del sistema.

Diverse tecniche di analisi statica sono state proposte per le algebre di proces-si. In particolare, tra i lavori che riguardano il π-calcolo, troviamo le analisi control flow (CFA) [3, 4, 2, 5, 6, 8] e l’analisi statica [12], realizzata tramite l’Interpretazione Astratta.

In questa tesi presentiamo un’applicazione dell’interpretazione astratta al π-calcolo. Questa tecnica fornisce una teoria per derivare in modo sistematico analisi di programmi a partire dalla semantica del linguaggio. L’approccio tipico dell’interpretazione astratta, una volta scelta la proprietà di interesse, consiste nel: rimpiazzare il dominio concreto delle computazioni con un do-minio astratto, che modella la proprietà che si vuole analizzare; stabilire una relazione tra il dominio concreto e quello astratto, attraverso una connessio-ne di Galois; e derivare una semantica approssimata sul dominio astratto. La semantica approssimata, ottenuta in un modo sistematico, è corretta per costruzione rispetto alla proprietà scelta.

In questo lavoro presentiamo un framework generale per derivare analisi che calcolano informazioni sulla possibile evoluzione dei processi. Più precisa-mente, lo scopo è di derivare, per ogni processo raggiungibile, informazioni che permettono di osservare una classe di proprietà sulle possibili comunica-zioni.

(12)

Tale framework è basato sulla definizione di una nuova semantica per il π-calcolo, detta semantica normale, nello stile di [19, 20]. La semantica nor-male, che è equivalente alla semantica a riduzioni standard, semplifica lo sviluppo di analisi attraverso l’interpretazione astratta. Essa utilizza una diversa rappresentazione di un processo, detta stato. Tale rappresentazione elimina le complicazioni legate alla congruenza strutturale e permette di os-servare in modo esplicito le proprietà sulle comunicazioni.

Successivamente, definiamo un’opportuna astrazione della semantica norma-le per ricostruire la CFA di [3, 2, 5], basata su Flow Logic. Tanorma-le analisi calcola un’approssimazione corretta della seguente proprietà: quali nomi di canali possono essere inviati su un dato canale di comunicazione, e a quali nomi di canali un dato nome può essere legato. La principale differenza tra l’analisi presentata in [3, 2, 5] e la nostra, è che quest’ultima risulta più precisa, in quanto considera l’effetto delle continuazioni di un’azione di input/output, solo nei casi in cui la semantica astratta riporta la sincronizzazione come possibile.

L’informazione calcolata dall’analisi può essere usata per garantire ben note proprietà di sicurezza. In particolare, mostriamo un’applicazione della nostra analisi per verificare staticamente la proprietà di segretezza di confinement, discussa in [3, 2, 5]. Considerando una classificazione dei canali in pubblici e privati, la proprietà di confinement garantisce che un’informazione segreta possa essere comunicata solo su canali privati.

Organizzazione della tesi

Nel Capitolo 2 introduciamo la sintassi e la semantica del π-calcolo e i con-cetti base dell’Interpretazione Astratta.

Nel Capitolo 3 proponiamo un framework di interpretazione astratta per il π-calcolo, basato su una nuova semantica, detta semantica normale, equiva-lente a quella a riduzioni.

(13)

rico-struisce l’analisi di [2, 5].

Infine, nel Capitolo 5 presentiamo le nostre conclusioni, commentando anche alcuni lavori correlati a quello proposto in questa tesi.

(14)

(15)

Nozioni generali

In questo capitolo introduciamo alcune nozioni necessarie per la comprensio-ne del lavoro presentato comprensio-nei successivi capitoli.

In particolare, descriveremo brevemente il π-calcolo [25, 24] e i concetti base dell’interpretazione astratta [10, 11].

2.1 Il π-calcolo

In questo paragrafo introduciamo il π-calcolo, un modello di comunicazione concorrente a processi, in cui la topologia dei canali pu`o cambiare dinamica-mente.

Le entità base del π-calcolo sono i nomi, che rappresentano canali di comu-nicazione. I nomi possono essere trasmessi durante una comunicazione; ciò permette di simulare la loro mobilità.

Di seguito consideriamo una variante del π-calcolo [28, 29], la cui sintassi dif-ferisce da quella standard per la forma della somma e per il fatto che non `e presente il τ -prefix. Successivamente spiegheremo brevemente i motivi di tali limitazioni introdotte nella sintassi dei processi e riporteremo la semantica a riduzioni.

Definizione 2.1 (Sintassi dei processi) Sia eN un insieme infinito di no-mi tale che u, w, x, y, · · · ∈ eN . I processi P, Q, R, · · · ∈ P sono definiti

(16)

x(y) input pref ix | ¯xy output pref ix

Commentiamo di seguito la sintassi dei processi della Definizione 2.1, descri-vendo dettagliatamente le diverse forme che un processo pu`o assumere. La Somma P pu`o essere:

• 0 che indica il processo che non pu`o fare alcuna azione.

• π.P che rappresenta la somma composta da un solo agente prefisso.

• P+P che indica la somma di due o pi`u agenti, ognuno dei quali pu`o avere una delle due forme descritte nei punti precedenti. Un processo di questo tipo intuitivamente si comporta come uno degli agenti che lo compongono.

Ogni processo π.P presente in una somma pu`o essere un Input Prefix oppure un Output Prefix.

(17)

Un Input Prefix, della forma x(y).P , intuitivamente modella la ricezione di un nome sul canale x. Dopo l’esecuzione dell’azione di input il processo con-tinua come P , in cui il nome y è sostituito con il nome ricevuto. Quindi x può essere visto come una porta di input e y come una variabile a cui verrà associato il valore ricevuto su x.

Un Output Prefix, della forma ¯xy.P , intuitivamente modella la spedizione di y sul canale x. Successivamente l’agente continua come P . Quindi x pu`o essere visto come una porta di output e y come un dato spedito su quella porta.

In un processo π.P diciamo che P `e guardato da π, poich´e le azioni rappre-sentate da π devono essere eseguite prima che P diventi attivo.

La Restrizione (νx)P si comporta come P in cui il nome x `e locale. In altre parole, x pu`o essere usato per la comunicazione tra i componenti di P , ma non per le comunicazioni tra P e l’ambiente esterno.

La Composizione Parallela P |Q rappresenta il comportamento combinato di P e Q che sono eseguiti in parallelo. I componenti P e Q possono agire indipendentemente e possono comunicare se uno esegue un output e l’altro un input sullo stesso canale.

Il Match [x = y]P si comporta come P se i nomi x e y sono identici, come l’agente 0 altrimenti.

Infine, la Replicazione !P permette di creare qualsiasi numero di copie di P in parallelo.

`

E da notare che nella Definizione 2.1 abbiamo considerato una sintassi parti-colare per la somma. Infatti, consideriamo somme composte solo da processi di tipoPe abbiamo assunto che non ci siano τ -prefix. Tali limitazioni, come spiegato in [28], non limitano il potere espressivo e rendono pi`u semplici le regole della semantica a riduzioni.

Di seguito adottiamo la convenzione sintattica di omettere 0 dopo un’azione, scrivendo π al posto di π.0. Consideriamo inoltre la precedenza degli opera-tori unari su quelli binari e della composizione parallela sulla somma. L’operatore di restrizione (νy) e l’azione di input x(y) legano entrambi il

(18)

no-me y; no-mentre il nono-me y `e libero nell’azione di output ¯xy. Indichiamo pertanto con bn(P ) i nomi che occorrono legati in P ; con f n(P ) i nomi liberi di P , ov-vero quelli che occorrono in P non legati; ed infine con n(P ) = bn(P )∪f n(P ) l’insieme di tutti i nomi di P .

Inoltre, nei prefissi x(y) e ¯xy diciamo che il nome x `e il soggetto, mentre y `e l’oggetto.

Adottiamo la nozione standard di α-conversione, per sostituire un nome le-gato con un nome nuovo. Diciamo che due processi sono α-convertibili se possono essere resi sintatticamente identici attraverso il renaming dei nomi legati.

Una sostituzione `e una funzione σ : eN → eN . Di seguito scriviamo [x/y] per indicare la sostituzione che mappa y ad x e tutti gli altri nomi a se stessi. Inoltre, usiamo P [m/n] per indicare il processo ottenuto sostituendo in P ogni occorrenza libera di n con m (assumendo che i nomi legati di P sia-no α-convertiti per evitare conflitti con m). Analogamente, usiamo P σ per indicare il processo ottenuto applicando la funzione di sostituzione σ a P .

2.1.1 Semantica a Riduzioni

Nel presente paragrafo presentiamo la semantica a riduzioni, definendo la relazione di congruenza strutturale e le regole di riduzione.

Congruenza Strutturale. In Tabella 2.1 definiamo la relazione di con-gruenza strutturale ≡, che permette di identificare processi che sono seman-ticamente equivalenti. La definizione contiene regole standard per commutare i processi nella composizione parallela e nelle somme, per spostare o togliere le restrizioni, e per α-convertire i processi.

Regole di Riduzione. Descriviamo di seguito come i diversi componenti concorrenti di un processo possono interagire l’uno con l’altro. Scriviamo P → P0 _{per indicare che P si riduce a P}0_{, ovvero che P pu`o eseguire un}

(19)

Tabella 2.1: Congruenza Strutturale P ≡ P (Rifl≡) P ≡ Q ⇒ Q ≡ P (Simm≡) P ≡ Q, Q ≡ R ⇒ P ≡ R (Tran≡) P ≡ Q ⇒ π.P +P≡ π.Q +P (Somma≡) P ≡ Q ⇒ (νx)P ≡ (νx)Q (Res≡) P ≡ Q ⇒ P |R ≡ Q|R (Par≡) P ≡ Q ⇒!P ≡!Q (Copia≡)

P ≡ Q ⇒ [x = y]P ≡ [x = y]Q (Match≡)

0|P ≡ P (Nil-Par≡) P |Q ≡ Q|P (Par-Com≡) P |(Q|R) ≡ (P |Q)|R (Par-Ass≡) 0 +P≡P (Nil-Somma≡) P 1+ P 2 ≡ P 2+ P 1 (Somma-Com≡) P 1+( P 2+ P 3) ≡ ( P 1+ P 2) + P 3 (Somma-Ass≡)

(νx)(νy)P ≡ (νy)(νx)P se x 6= y (Res-Com≡)

(νx)(P |Q) ≡ (νx)P |Q se x /∈ f n(Q) (Res-Par≡)

(νx)0 ≡ 0 (Nil-Res≡)

Se P e Q sono α-equivalenti allora P ≡ Q; cio`e

(νx)P ≡ (νy)(P [y/x]) se y /∈ f n((νx)P ) e (α−Res≡)

x(y).P ≡ x(z).(P [z/y]) se z /∈ f n(x(y).P ) (α−In≡)

La relazione di riduzione → `e definita come la minima relazione chiusa sotto un insieme di regole di riduzione. Le regole della semantica a riduzioni sono definite in Tabella 2.2.

La regola Com evidenzia come la comunicazione avviene tra due processi della forma π.P complementari; dopo la comunicazione gli eventuali altri

(20)

Tabella 2.2: Regole di riduzione del π−calcolo

(P₁+¯az.P )|(P₂+a(y).Q) → P |Q[z/y] (Com)

P → Q implica P |R → Q|R (Par)

P → Q implica (νx)P → (νx)Q (Res)

(P0 _{→ Q}0_{, P ≡ P}0_{, Q ≡ Q}0_{) implica P → Q} _(Struct)

!P →!P |P (Copia)

[x = x]P → P (Match)

processi che compongono la somma vengono eliminati.

Le regole Res e Par indicano che la riduzione pu`o avvenire anche all’interno di una restrizione e una composizione parallela rispettivamente.

La regola Struct mostra che processi strutturalmente congruenti hanno le stesse riduzioni. La regola Copia consente di creare una copia di un processo replicato. Infine, la regola Match mostra che un processo della forma [x = x]P pu`o continuare come P .

`

E da notare che modelliamo la replicazione e il match tramite delle regole di riduzione invece che tramite degli assiomi della congruenza strutturale. Questa modifica permette di semplificare l’astrazione come in [21].

Di seguito presentiamo un esempio che mostra la capacit`a del π-calcolo di modellare la mobilit`a dei nomi di canali.

Esempio 2.1 Supponiamo di voler modellare un sistema in cui `e presente un server, che gestisce i diritti di accesso ad una stampante, e un client, che ne richiede l’uso. Inizialmente, solo il server ha accesso alla stampante, attraverso un canale di comunicazione privato.

Il sistema descritto pu`o essere modellato dal seguente processo (νa)(¯ba.S|a(y).R)|b(x).¯xc.P .

(21)

Per consentire l’uso della stampante, il server deve inviare il canale privato a al client, sul canale condiviso b. Dopo la comunicazione il client pu`o in-viare i suoi dati alla stampante. Tali interazioni sono descritte dalle seguenti transizioni

(νa)(¯ba.S|a(y).R)|b(x).¯xc.P → (νa)(S|a(y).R|¯ac.P0_{) → (νa)(S|R}0_|P0_).

dove P0 _{= P [a/x] e R}0 _{= R[c/y].}

`

E da notare che in questo esempio il nome a ha due differenti ruoli. Nel-l’interazione tra il server e il client, `e un oggetto che viene trasmesso da un processo all’altro, invece nell’interazione tra il client e la stampante esso

rappresenta un canale di comunicazione. 2

2.2 Interpretazione Astratta

L’interpretazione astratta è una teoria generale per approssimare la seman-tica di sistemi dinamici [10, 11, 9]. Originariamente è stata sviluppata da Patrick e Radhia Cousot come framework per descrivere e derivare in modo sistematico analisi statiche di programmi e dimostrarne correttezza e preci-sione. In anni recenti è stata applicata con successo in molte aree dell’infor-matica (per esempio model checking, type inference, sicurezza e constraint solving) per descrivere e formalizzare computazioni approssimate.

L’idea dell’interpretazione astratta è che l’analisi di un sistema, per esem-pio un programma, può essere ottenuta come un’approssimazione della sua semantica formale. La semantica (concreta) di un linguaggio di program-mazione è tradizionalmente descritta attraverso un dominio concreto ed una funzione che associa ad ogni programma un significato sul dominio concreto. L’approccio tipico dell’interpretazione astratta consiste nel:

• rimpiazzare il dominio concreto delle computazioni con un dominio astratto, che modella le propriet`a che si vogliono analizzare;

(22)

• stabilire una relazione tra il dominio concreto e quello astratto, at-traverso una connessione di Galois, che formalizza la correttezza e la precisione dell’approssimazione;

• derivare una semantica approssimata, detta astratta, eseguendo il pro-gramma sul dominio astratto. L’analisi definisce un’approssimazione della propriet`a di interesse.

La semantica approssimata `e ottenuta in un modo sistematico che ne garan-tisce la correttezza per costruzione.

Supponiamo di volere approssimare una semantica S, che è calcolata come il minimo punto fisso di una funzione di valutazione semantica concreta F , de-finita sul dominio concreto hC, 6i. Il punto cruciale è la scelta di un dominio astratto hA, 6α_{i, che modella la proprietà che vogliamo analizzare}

statica-mente. Assumiamo che il dominio concreto e quello astratto siano entrambi reticoli completi. L’ordinamento sul dominio concreto e quello sul dominio astratto descrivono la precisione dei valori appartenenti ai rispettivi domini. Dati due elementi del dominio concreto, c1 6 c2 significa che c1 `e pi`u preciso

di c2, ovvero c2ha meno informazione di c1. Analogamente, dati due elementi

del dominio astratto, a1 6α a2 significa che a1 `e pi`u preciso di a2. Inoltre,

gli elementi top dei due domini rappresentano l’assenza di informazione. La relazione tra il dominio concreto e quello astratto `e formalizzata dalla nozione di connessione di Galois, ovvero da una coppia di funzioni monotone α : C → A e γ : A → C. La funzione α, detta funzione di astrazione, associa ad ogni elemento del dominio concreto la sua migliore approssimazione nel dominio astratto. La funzione γ, detta funzione di concretizzazione, definisce il significato dei valori astratti, ovvero associa ad ogni elemento del dominio astratto l’insieme dei valori concreti che esso descrive.

La seguente definizione formalizza la nozione di connessione di Galois. Definizione 2.2 (Connessione di Galois) Siano hC, 6i e hA, 6α_{i due}

re-ticoli completi. Una coppia di funzioni monotone (α, γ), tale che α : C → A è la funzione di astrazione e γ : A → C è la funzione di concretizzazione, è

(23)

una connessione di Galois tra hC, 6i e hA, 6α_{i se e solo se per ogni c ∈ C e}

a ∈ A

1. c 6 γ(α(c));

2. α(γ(a)) 6α _a.

Se α(γ(a)) = a allora (α, γ) `e detta inserzione di Galois.

La funzione di valutazione semantica concreta F `e definita in termini di ope-ratori semantici primitivi fi. Per ottenere la funzione di valutazione

seman-tica astratta `e sufficiente rimpiazzare in F ogni operatore semantico concreto con un corrispondente operatore astratto. Pertanto, per ogni operatore fi,

definito su C, `e necessario fornire un corrispondente operatore fα

i , definito

su A, che sia localmente corretto, ovvero

∀c1, . . . , cn ∈ C.α(fi(c1, . . . , cn)) 6α fiα(α(c1), . . . , α(cn)).

Intuitivamente questo significa che, se c1, . . . , cn sono valori concreti

appros-simati da a1, . . . , an, allora un passo di calcolo concreto, ovvero fi(c1, . . . , cn),

`e approssimato da un passo di calcolo astratto, ovvero fα

i (a1, . . . , an).

Se per qualche c1, . . . , cn∈ C si ha che

α(fi(c1, . . . , cn)) <α fiα(α(c1), . . . , α(cn))

significa che c’`e una perdita di informazione durante la simulazione del com-portamento dell’operazione concreta fi da parte dell’operazione astratta fiα.

Invece, se per ogni c1, . . . , cn ∈ C si ha che

α(fi(c1, . . . , cn)) = fiα(α(c1), . . . , α(cn))

significa che non c’è perdita di informazione, ovvero l’astrazione del passo di calcolo concreto è esattamente il risultato del corrispondente passo di calcolo astratto. In tal caso l’operatore è detto completo.

Il risultato fondamentale `e che la funzione di valutazione semantica astratta Fα_{, ottenuta rimpiazzando in F ogni operatore semantico concreto con un}

corrispondente operatore astratto localmente corretto, `e localmente corretta. Pi`u formalmente

(24)

∀c ∈ C.α(F (c)) 6α _Fα_(α(c)).

Inoltre, la correttezza viene preservata anche dal calcolo del punto fisso. Teorema 2.3 (Correttezza) Sia la coppia di funzioni (α, γ) una connes-sione di Galois tra hC, 6i e hA, 6α_{i e siano F : C → C e F}α _{: A → A}

funzioni monotone. Se α(F (c)) 6α _Fα_{(α(c)) per ogni c ∈ C, allora α(lf p}

(25)

Un framework di intepretazione

astratta per il π-calcolo

In questo capitolo presentiamo un framework di interpretazione astratta per il π-calcolo, mirato alla definizione di analisi che calcolano informazioni su ogni processo raggiungibile. Più precisamente, lo scopo è di derivare informa-zioni che permettono di osservare una classe di proprietà sulle comunicainforma-zioni che potrebbero avvenire a run-time.

Un esempio di proprietà appartenente a tale classe è la seguente: quali no-mi di canali possono essere inviati su un dato canale di comunicazione e a quali nomi di canali un dato nome può essere legato. Supponiamo di volere osservare tale proprietà sul processo presentato nell’ Esempio 2.1

(νa)(¯ba.S|a(y).R)|b(x).¯xc.P .

L’informazione che vogliamo approssimare `e che sul canale b viene trasmesso il nome a, sul canale a `e trasmesso il nome c, e i nomi x e y sono legati rispettivamente ai nomi di canali a e c.

Il framework che presentiamo si basa su un’estensione della sintassi del π-calcolo presentata nella Definizione 2.1, per la quale `e immediato adattare la semantica a riduzioni del Paragrafo 2.1.1.

Inoltre, per semplificare il calcolo della classe di informazioni a cui siamo in-17

(26)

teressati, introduciamo una nuova semantica per il π-calcolo, detta semantica normale, che `e equivalente alla semantica a riduzioni.

3.1 Sintassi e semantica del π-calcolo per

pro-cessi etichettati

In questo paragrafo presentiamo un’estensione della sintassi del π-calcolo, che prevede l’assegnamento di etichette ai nomi di canali introdotti dagli operatori di restrizione e ai nomi oggetto degli input prefix.

Indichiamo con LabR_{l’insieme delle etichette che possono essere assegnate ai}

nomi di canali introdotti da un operatore di restrizione e con LabI _l’insieme

delle etichette che possono essere assegnate alle variabili introdotte da un input prefix. Assumiamo che LabR_{∩ Lab}I _{= ∅.}

Inoltre assumiamo una partizione dei nomi eN = N ]V, dove N = U_χ∈LabRNχ

`e un insieme di nomi di canali e V = U_β∈LabIVβ `e un insieme di variabili.

L’operatore U rappresenta l’unione disgiunta tra insiemi, mentre Nχ e Vβ

sono insiemi infiniti rispettivamente di nomi di canali e di variabili.

Definizione 3.1 (Sintassi dei processi etichettati) I processi etichetta-ti sono definietichetta-ti sui nomi eN = N ] V secondo la seguente sintassi

P ::= processi

| P somma

| (νxχ_)P _restrizione _{con χ ∈ Lab}R_{e x ∈ N} χ

| P |P parallelo

| [x = y]P matching con x, y ∈ eN

| !P replicazione P ::= 0 nil | π.P pref isso | P+P somma

(27)

π ::=

x(yβ₎ _{input pref ix} _{con β ∈ Lab}I_{, y ∈ V}

β e x ∈ eN

| ¯xy output pref ix con x, y ∈ eN

Come specificato nella Definizione 3.1, in un processo i nomi di canali in-trodotti da un operatore di restrizione devono appartenere alla partizione dei nomi associata all’etichetta. Analogamente, le variabili introdotte da un input prefix devono appartenere alla partizione di variabili associata all’eti-chetta.

Assumiamo che tutte le nozioni presentate nel Paragrafo 2.1 siano adattate nel modo ovvio ai processi etichettati.

Inoltre, indichiamo con var(P ) ⊆ V l’insieme delle variabili introdotte dagli operatori di input prefix presenti nel processo P ; e con nr(P ) ⊆ N , l’insieme dei nomi di canali introdotti in P da un operatore di restrizione. `E impor-tante notare che: n(P ) ⊆ N ] V, f n(P ) ⊆ N ] V e bn(P ) = nr(P )∪var(P ). Al fine di semplificare l’analisi, di seguito consideriamo processi ben-etichettati. Definizione 3.2 (Processi ben-etichettati) Un processo P `e ben-etichettato se e solo se:

(i) le variabili legate di P sono diverse sia da tutte le altre variabili legate del processo sia dalle variabili libere;

(ii) i nomi ristretti di P sono diversi sia da tutti gli altri nomi ristretti del processo sia dai nomi liberi .

`

E da notare che la semantica a riduzioni pu`o essere adattata banalmente ai processi ben-etichettati. `E sufficiente assumere che l’α-conversione e l’unfol-ding della replicazione preservino la ben-etichettatura dei processi.

In particolare, per l’α-conversione assumiamo che un nome di canale ristretto n ∈ Nχpossa essere sostituito solo da un nome m ∈ Nχ, se m non appartiene

(28)

sostituita solo da y ∈ Vβ, se y non appartiene alle variabili del processo.

Per quanto riguarda la regola (Copia), che modella l’unfolding della replica-zione, assumiamo che essa generi una copia fresh α-equivalente al processo replicato. Formalmente, la regola (Copia) usata per i processi ben-etichettati `e la seguente !P → P |newP(P ), dove newP(P ) restituisce un processo

ben-etichettato Q α-equivalente a P .

Inoltre, data la struttura dei processi ben-etichettati, che prevede l’uso di variabili e nomi legati tutti diversi, `e evidente che durante l’esecuzione di un processo non si ha mai la necessit`a di applicare l’α-conversione. Pertanto, as-sumiamo che le regole della congruenza strutturale (α-In≡) e (α-Res≡) non

siano presenti nella semantica a riduzioni adattata ai processi ben-etichettati. Di seguito presentiamo un esempio che mostra l’applicazione di alcune regole della semantica a riduzioni adattata ai processi ben-etichettati.

Esempio 3.1 Consideriamo il processo ben-etichettato P =!(νaχ_)(νnγ_{)(¯an | a(x}β_).¯_xb).

`

E da notare che `e possibile applicare infinite volte la regola (Copia), pertanto durante l’esecuzione di P si pu`o generare un numero non limitato di nomi appartenenti alla partizione Nχ e un numero non limitato di nomi della

par-tizione Nγ. Inoltre, pu`o essere generato anche un numero non limitato di

variabili appartenenti alla partizione Vβ.

Di seguito mostriamo solo alcuni passi dell’esecuzione di P . Applicando la regola (Copia), P pu`o transire in

P1 =!(νaχ)(νnγ)(¯an | a(xβ).¯xb) | (νaχ1)(νn1γ)(¯a1n1 | a1(xβ1).¯x1b).

Da P1 si pu`o transire in due processi differenti. Se applichiamo nuovamente

la regola (Copia), otteniamo

P2 =!(νaχ)(νnγ)(¯an | a(xβ).¯xb) | (νaχ1)(νn1γ)(¯a1n1 | a1(xβ1).¯x1b)

| (νaχ₂)(νnγ₂)(¯a2n2 | a2(xβ2).¯x2b).

(29)

P3 =!(νaχ)(νnγ)(¯an | a(xβ).¯xb) | (νaχ1)(νnγ1)(0 | ¯n1b).

2 Di seguito usiamo PE per indicare l’insieme dei processi ben-etichettati e consideriamo solo processi appartenenti a tale insieme. Inoltre, dato un pro-cesso P ben-etichettato, indichiamo con E(P ) il propro-cesso ottenuto eliminando le etichette.

Introduciamo adesso due teoremi che mostrano la relazione tra la semantica a riduzioni dei processi ben-etichettati e quella dei processi standard.

Teorema 3.3 (Correttezza) Siano P e Q due processi ben-etichettati.

1. Se P ≡ Q allora E(P ) ≡ E(Q).

2. Se P → Q allora E(P ) → E(Q).

Teorema 3.4 (Completezza) Siano P e Q due processi.

1. Se P ≡ Q allora esistono due processi ben-etichettati Pe _{e Q}e_{, tale che}

Pe_{≡ Q}e_{, E(P}e_{) `e α−equivalente a P e E(Q}e_{) `e α−equivalente a Q.}

2. Se P → Q allora esistono due processi ben-etichettati Pe _{e Q}e_{, tale che}

Pe_{→ Q}e_{, E(P}e_{) `e α−equivalente a P e E(Q}e_{) `e α−equivalente a Q.}

Adesso descriviamo brevemente l’uso delle etichette nei processi.

Etichettatura E da notare che l’etichettatura non ha effetto sulla seman-` tica e pu`o essere fatta in maniera meccanica.

L’etichettatura dei processi `e tipica delle tecniche statiche, in particolare del-l’approccio Flow Logic [27], e permette di identificare i “punti di programma” in cui si vuole raccogliere informazione.

Le etichette delle restrizioni sono necessarie per trattare l’α-conversione, men-tre le etichette degli input prefix sono state introdotte per identificare i punti in cui vogliamo raccogliere informazione.

(30)

3.2 Semantica Normale

La semantica normale `e progettata, nello stile di [19, 20], per semplificare l’applicazione dell’interpretazione astratta. Infatti, la semantica a riduzioni ha due limiti fondamentali:

1. le regole di congruenza strutturale e l’α-conversione complicano l’astra-zione;

2. non permette di osservare in maniera esplicita le propriet`a sulle comu-nicazioni.

3.2.1 Stati

Nella semantica normale usiamo una diversa rappresentazione di un proces-so, detta stato. La definizione di stato si basa sull’idea di rappresentare un processo come un multi-insieme di processi di base, ovvero somme, replica-zioni e match.

Per esempio il processo ben-etichettato P =!¯xn|¯xn|¯xn|x(yβ₎

pu`o essere rappresentato con il multi-insieme {(!¯xn, 1), (¯xn, 2), (x(yβ_{), 1)}.}

`

E da notare che i multi-insiemi sono necessari per mantenere l’informazione sul numero di occorrenze dei processi di base.

Tra i processi base non consideriamo le restrizioni, poich´e queste possono essere eliminate. Infatti, dato che consideriamo solo processi ben-etichettati, il nome ristretto `e certamente un nome fresh.

Per esempio nel processo Q = (νnχ_)(¯_na|n(yβ_).¯_yb)

il nome ristretto n `e nuovo, quindi nella rappresentazione in stato pu`o essere eliminato ottenendo

(31)

{(¯na, 1), (n(yβ_).¯_{yb, 1)}.}

Tuttavia la rappresentazione di un processo esclusivamente tramite un multi-insieme di processi di base non `e abbastanza informativa.

Tale rappresentazione infatti non permette di distinguere i nomi ristretti da quelli liberi.

Consideriamo per esempio i processi Q = (νnχ_)(¯_na|n(yβ_).¯_yb)

Q0 _{= ¯}_na|n(yβ_).¯_yb.

`

E immediato notare che i due processi sono diversi, in quanto nel processo Q il nome n è ristretto, mentre nel processo Q0 _{n è libero. Di conseguenza, è}

ovvio che anche gli stati che li rappresentano devono essere diversi. La rap-presentazione tramite multi-insieme invece non ci permette di distinguerli, dato che Q e Q0 _{hanno gli stessi processi di base. Per risolvere questo}

pro-blema introduciamo nello stato una nuova componente, ovvero la funzione R, che mantiene l’associazione tra le etichette delle restrizioni e gli insiemi contenenti i relativi nomi. Pertanto, abbiamo che i processi Q e Q0 _sono

rappresentati rispettivamente dai seguenti stati ({(¯na, 1), (n(yβ_).¯_{yb, 1)}, R}

1)

({(¯na, 1), (n(yβ_).¯_{yb, 1)}, R}

2)

dove R1(χ) = {n} e R2(χ) = ∅.

Inoltre, per predire staticamente le propriet`a a cui siamo interessati `e ne-cessario catturare in modo semplice quali nomi verranno legati alle variabili durante l’esecuzione di un processo.

Per esempio, consideriamo il seguente processo Q0 _{= ¯}_na|n(yβ_).¯_yb.

che con un passo di computazione pu`o transire in Q00_{= ab.}

(32)

Abbiamo bisogno di mantenere l’informazione del legame tra l’etichetta β e la variabile y e tra y e il nome a, di conseguenza introduciamo nello stato le seguenti componenti:

• B, che mantiene l’associazione tra le etichette e le variabili oggetto degli input prefix, che sono stati coinvolti in una comunicazione;

• env, che mantiene l’associazione tra variabili e nomi.

In questo modo possiamo rappresentare il processo Q00 _{con lo stato}

({(¯yb, 1)}, B, env, R)

dove le funzioni B ed env sono tali che B(β) = {y} e env(y) = a.

Di seguito consideriamo la funzione env come l’ambiente dei nomi in cui so-no valutati le variabili e i so-nomi liberi dei processi base presenti nello stato. Pertanto, env mantiene le associazioni, non solo per le variabili oggetto degli input prefix che sono stati coinvolti in una comunicazione, ma anche per ogni variabile e nome libero dei processi base dello stato.

Presentiamo adesso la definizione di stato e definiamo le operazioni di inclu-sione e unione tra stati.

Indichiamo con PB l’insieme dei processi base ben-etichettati, ovvero quelli della forma P = π.Q, P =P+P, P =!Q e P = [x = y]Q.

Consideriamo inoltre un’estensione dell’insieme dei nomi che indichiamo con e

N⊥,>, ottenuta aggiungendo gli elementi ⊥ e > all’insieme eN .

Definizione 3.5 (Stati) Uno stato S ∈ S `e una quadrupla (P roc, B, env, R) dove

• P roc ∈ PROC `e un multi-insieme di processi base ben-etichettati;

• B : LabI _{→ ℘(V), con B ∈ B, `e una funzione totale tale che ∀β ∈}

LabI _{: B(β) ⊆ V} β;

• env : eN → eN⊥,>, con env ∈ EN V, `e una funzione totale tale che

(33)

• R : LabR _{→ ℘(N ), con R ∈ R, `e una funzione totale tale che ∀χ ∈}

LabR _{: R(χ) ⊆ N} χ.

In uno stato le funzioni B ed env forniscono l’informazione sui canali a cui una data variabile `e legata. Analizzando il multi-insieme P roc e la funzione env inoltre `e possibile determinare i canali che vengono inviati su un dato canale. Infine, la funzione R consente di individuare i nomi legati da un operatore di restrizione.

Introduciamo adesso alcune notazioni usate di seguito.

Notazioni

• Sia f : A → B una funzione e siano a ∈ A e b ∈ B. Scriviamo f [a 7→ b] per indicare che f `e aggiornata con la nuova associazione tra a e b, sovrascrivendo l’associazione gi`a presente.

• Sia env ∈ EN V una funzione. Indichiamo con dom(env) l’insieme degli elementi del dominio di env associati ad un elemento diverso da ⊥, ovvero dom(env) = {y|env(y) 6=⊥}.

• Sia S = (P roc, B, env, R) uno stato. Indichiamo con hP roc, envi il multi-insieme dei processi dello stato S valutati nell’ambiente env, ov-vero

hP roc, envi = {(Q, n)|Q = hP, envi ∧ (P, n) ∈ P roc} dove

hP, envi = P [env(n1)/n1, . . . , env(ni)/ni] con {n1, . . . , ni} = f n(P )

Introduciamo di seguito le nozioni di nomi liberi e nomi legati di uno stato. Definizione 3.6 (Nomi liberi e nomi legati di uno stato) Sia S ∈ S uno stato tale che S = (P roc, B, env, R). Indichiamo con:

• f n(S) i nomi liberi di S tale che f n(S) = [

P ∈hP roc,envi

f n(P ) \ [

χ∈LabR

(34)

• nr(S) i nomi ristretti di S tale che nr(S) = [ P ∈P roc nr(P ) ∪ [ χ∈LabR R(χ)

• var(S) le variabili legate di S tale che var(S) = [

P ∈P roc

var(P )

• bn(S) i nomi legati di S tale che

bn(S) = var(S) ∪ nr(S)

Ordinamento e unione tra stati. Prima di dare le definizione di ordi-namento e di unione tra stati ricordiamo l’ordiordi-namento punto a punto delle funzioni e definiamo il minimo dei maggioranti e il massimo dei minoranti di un insieme di funzioni.

Definizione 3.7 (Ordinamento puntuale delle funzioni) Sia (B, vB) un

ordinamento parziale e siano f, g : A → B due funzioni totali. Si ha che f vF g se e solo se ∀x ∈ A : f (x) vB g(x).

Definizione 3.8 (Lub di un insieme di funzioni) Siano F = {f1, f2, . . .}

un insieme di funzioni fi : A → B e (B, vB) un ordinamento parziale tale

che ogni suo sottoinsieme ha lub. Il minimo maggiorante dell’insieme F `e definito in modo puntuale, ovvero

( G i F fi)(x) = G i B fi(x).

Definizione 3.9 (Glb di un insieme di funzioni) Siano F = {f1, f2, . . .}

un insieme di funzioni fi : A → B e (B, vB) un ordinamento parziale tale

che ogni suo sottoinsieme ha glb. Il massimo minorante dell’insieme F `e definito in modo puntuale, ovvero

( \ i F fi)(x) = \ i B fi(x).

(35)

Le Definizioni 3.7 e 3.8 sono usate rispettivamente per l’ordinamento e l’u-nione degli stati, definite entrambi componente per componente.

Definiamo di seguito gli ordinamenti dei codomini delle funzioni che com-pongono lo stato.

I codomini delle funzioni appartenenti a B e di quelle appartenenti ad R sono ordinati secondo la relazione di inclusione tra insiemi ⊆, mentre il codomi-nio delle funzioni appartenenti ad EN V, ovvero eN⊥,>, `e ordinato secondo la

seguente relazione: ∀n ∈ eN⊥,> : ⊥v n ∧ n v n ∧ n v >.

Poichè (℘(V), ⊆) è un ordinamento parziale è possibile usare la Definizione 3.7 per ordinare due funzioni B1, B2 ∈ B. `E facile verificare che la stessa

defini-zione pu`o essere applicata anche per ordinare due funzioni env1, env2 ∈ EN V

e due funzioni R1, R2 ∈ R, dato che anche ( eN⊥,>, v) e (℘(N ), ⊆) sono

ordi-namenti parziali.

Di seguito usiamo la seguente notazione:

• B∅ per indicare la minima funzione B ∈ B, che mappa ogni etichetta a

∅, ovvero ∀β ∈ LabI _{: B}

∅(β) = ∅.

• env⊥ per indicare la minima funzione env ∈ EN V, che mappa ogni

nome a ⊥, ovvero ∀n ∈ eN : env⊥(n) =⊥.

• R∅ per indicare la minima funzione R ∈ R, che mappa ogni etichetta

a ∅, ovvero ∀χ ∈ LabR _{: R}

∅(χ) = ∅.

Inoltre, `e facile verificare che per ognuno degli ordinamenti parziali (℘(V), ⊆), ( eN⊥,>, v) e (℘(N ), ⊆), vale che ogni loro sottoinsieme ammette lub.

Pertan-to, secondo la Definizione 3.8, `e sempre possibile calcolare il minimo dei maggioranti rispettivamente di un insieme di funzioni {Bi|Bi ∈ B}, un

insie-me di funzioni {envi|envi ∈ EN V} e un insieme di funzioni {Ri|Ri ∈ R}.

Sulla base di queste propriet`a definiamo l’inclusione e l’unione tra stati. Definizione 3.10 (Ordinamento sugli stati) Siano (P roc, B, env, R) e (P roc0_{, B}0_{, env}0_{, R}0_{) due stati. Diciamo che}

(36)

se e solo se

• P roc ⊆ P roc0

• B vF B0

• env vF env0

• R vF R0

dove per le funzioni si considera l’ordinamento punto a punto e per l’elemento P roc si considera l’ordinamento tra multi-insiemi, definito in modo standard. Di seguito diamo la definizione di unione tra stati.

Definizione 3.11 (Unione tra stati) Siano (P roc1, B1, env1, R1) e

(P roc2, B2, env2, R2) due stati. Abbiamo

(P roc1, B1, env1, R1) ∪s(P roc2, B2, env2, R2) = (P roc, B, env, R)

dove

• P roc = P roc1∪ P roc2

• B = B1tF B2

• env = env1tF env2

• R = R1tF R2

Per l’elemento P roc consideriamo l’unione tra multi-insiemi, definito in modo standard.

Stati ben-etichettati. Poich´e siamo interessati solo a stati che rappresen-tano processi ben-etichettati, introduciamo la nozione di stato ben-etichettato. Definizione 3.12 (Stato ben-etichettato) Uno stato S = (P roc, B, env, R) `e ben-etichettato se e solo se:

(37)

1. le variabili legate di S sono diverse:

(a) da tutte le altre variabili legate dello stato

(b) dalle variabili appartenenti ai nomi liberi dello stato

(c) dalle variabili libere non valutate dei processi presenti nella com-ponente P roc di S

2. i nomi ristretti di S sono diversi:

(a) da tutti gli altri nomi ristretti dello stato S

(b) dai nomi liberi di S

3. la funzione env dello stato S `e tale che

(a) ∀n ∈ N : env(n) =⊥ ∨ env(n) = n

(b) ∀x ∈ eN : env(x) 6= >

(c) ∀x ∈ dom(env) : env(x) ∈ dom(env).

Di seguito usiamo SE per indicare l’insieme degli stati ben-etichettati.

3.2.2 Funzione di normalizzazione

Allo scopo di trasformare un processo ben-etichettato in uno stato introdu-ciamo una funzione, δ : PE × EN V → S, detta funzione di normalizzazione. Intuitivamente, δ(P, env) rappresenta lo stato corrispondente al processo P rispetto all’ambiente dei nomi env.

Presentiamo la definizione della funzione di normalizzazione in Tabella 3.1. La regola DCopia restituisce uno stato in cui P roc contiene solo il processo che si vuole tradurre, le funzioni B ed R sono quelle minime e l’ambiente env rimane invariato.

La regola DSomma prevede due casi. In entrambi i casi essa è analoga alla regola DCopia. È da notare che nel caso in cui il processo da tradurre sia 0 il multi-insieme P roc è vuoto.

(38)

Tabella 3.1: Funzione di normalizzazione δ DSomma δ(P, env) = ( (∅, B∅, env, R∅) se P = 0 ({(P, 1)}, B∅, env, R∅) altrimenti DMatch

δ([x = y]P, env) = ({([x = y]P, 1)}, B∅, env, R∅)

DCopia δ(!P, env) = ({(!P, 1)}, B∅, env, R∅) DRes δ((νnχ_{)P, env) =} ( δ(P, env) se n 6∈ f n(P ) δ(P, env[n 7→ n]) ∪s_{(∅, B} ∅, env⊥, R∅[χ 7→ {n}]) altr. DPar

δ(P |Q, env) = δ(P, env) ∪s_{δ(Q, env)}

La regola DPar restituisce uno stato che `e il risultato dell’unione degli stati relativi ai due processi in parallelo.

Infine, la regola DRes prevede due casi. Se il nome introdotto dall’operatore di restrizione non è presente tra i nomi di P , la regola traduce in stato il pro-cesso P . Altrimenti traduce in stato il propro-cesso P considerando l’ambiente env aggiornato con l’associazione tra il nome legato n e se stesso, e aggiorna la funzione R aggiungendo all’insieme dei nomi associati all’etichetta χ il no-me ristretto. Intuitivano-mente, questa regola elimina la restrizione al top-level del processo che si vuole tradurre. Ciò è possibile grazie alla definizione di processo ben-etichettato, che assicura che n sia un nome nuovo in P .

La funzione δ `e utilizzata sia per ottenere lo stato che rappresenta il processo iniziale, sia per ottenere lo stato dei processi che diventano eseguibili dopo

(39)

un passo di computazione.

Lo stato iniziale corrispondente ad un processo P `e δ(P, envP), dove ∀n ∈

f n(P ) : envP(n) = n ∧ ∀m ∈ eN \ f n(P ) : envP(m) =⊥.

In particolare, le componenti dello stato iniziale di un processo P hanno le seguenti caratteristiche:

• P roc contiene i processi di base relativi ai processi in parallelo che compongono P ;

• la funzione B mappa ogni etichetta all’insieme vuoto;

• la funzione env associa ai nomi liberi e ai nomi delle restrizioni al top-level di P i nomi stessi, e agli altri nomi l’elemento ⊥;

• la funzione R mappa le etichette delle restrizioni al top-level di P al-l’insieme dei nomi ai quali le etichette sono associate, ed ogni altra etichetta all’insieme vuoto.

Proposizione 3.13 Sia P ∈ PE. Abbiamo che δ(P, envP) ∈ SE.

La dimostrazione della Proposizione 3.13 `e mostrata in Appendice A. Esempio 3.2 In questo esempio mostriamo l’applicazione della funzione di normalizzazione δ. A tale scopo usiamo i processi dell’Esempio 3.1. Lo stato iniziale corrispondente al processo

P =!(νaχ_)(νnγ_{)(¯an | a(x}β_).¯_xb).

`e il seguente

δ(P, envP) = ({(!(νaχ)(νnγ)(¯an|a(xβ).¯xb), 1)}, B∅, envP, R∅)

dove ∀m ∈ eN ∧ m 6= b : envP(m) =⊥ ∧ envP(b) = b.

Applicando la funzione δ al processo

(40)

| (νaχ₂)(νnγ₂)(¯a2n2 | a2(xβ2).¯x2b).

invece otteniamo rispettivamente lo stato δ(P1, envP1) = ({(P, 1), (¯a1n1, 1), (a1(x

β

1).¯x1b, 1)}, B∅,

envP[n1 7→ n1, a1 7→ a1], R∅[χ 7→ {n1}, γ 7→ {a1}])

dove ∀m ∈ eN ∧ m 6= b : envP1(m) =⊥ ∧ envP1(b) = b,

e lo stato δ(P2, envP2) = ({(P, 1), (¯a1n1, 1), (a1(x β 1).¯x1b, 1), (¯a2n2, 1), (a2(xβ2).¯x2b, 1)}, B∅, envP[n1 7→ n1, n2 7→ n2, a1 7→ a1, a2 7→ a2], R∅[χ 7→ {n1, n2}, γ 7→ {a1, a2}])

dove ∀m ∈ eN ∧ m 6= b : envP2(m) =⊥ ∧ envP2(b) = b.

2

3.2.3 Regole di transizione

In questo paragrafo presentiamo le regole di transizione tra stati, che simu-lano le regole della semantica a riduzioni. Le regole sono definite in Tabella 3.2, dove l’operatore \ indica la differenza tra multi-insiemi, definita in modo standard.

La regola Match `e applicabile quando i nomi presenti nella condizione del match rappresentano lo stesso canale. La regola aggiunge allo stato la tra-duzione del processo che segue la condizione del match ed elimina da P roc un’occorrenza del processo [x = y]P .

La regola Copia consente di creare copie fresh di un processo P replicato. La nuova copia di P ha i nomi legati diversi dai nomi e dalle variabili presenti nei processi dello stato. Per creare copie fresh usiamo new(P roc,B,env,R)(P )

che definiamo di seguito.

(41)

Tabella 3.2: Transizioni 7→

Match

[x = y]P ∈ P roc env(x) = env(y)

(P roc, B, env, R) 7→ (P roc \ {[x = y]P }, B, env, R) ∪s_{δ(P, env)}

Copia

!P ∈ P roc

(P roc, B, env, R) 7→ (P roc, B, env, R) ∪s_δ(new

(P roc,B,env,R)(P ), env) Com P0 ₌P 1+¯xy.P + P 2 Q0 = P 3+w(zβ).Q + P 4 P0, Q0 ∈ P roc P0 6= Q0

env(x) = env(w) B1 = B[β 7→ {z} ∪ B(β)] env1 = env[z 7→ env(y)]

(P roc, B, env, R) 7→ (P roc \ {P0_{, Q}0_{}, B}

1, env1, R) ∪sδ(P, env1) ∪sδ(Q, env1)

• Q `e α−equivalente a P

• Q `e un processo ben-etichettato

• ∀n ∈ bn(Q) : n /∈ nc(S)

dove con nc(S) =S_{P ∈P roc}n(P ) ∪S_β∈LabIB(β) ∪ dom(env) ∪

S

χ∈LabRR(χ)

indichiamo i nomi presenti in tutte le componenti dello stato S.

La regola Com1 _{realizza la comunicazione tra due processi che inviano e}

ricevono sullo stesso canale. La regola modifica lo stato aggiungendo la tra-duzioni delle continuazioni dei due processi coinvolti nella comunicazione ed eliminando da P roc l’azione consumata. Inoltre aggiunge in env l’associazio-ne tra la variabile dell’input prefix e il canale inviato, e in B l’associaziol’associazio-ne tra

1_{Nei processi P}0 _{e Q}0 _{della regola Com ogni processo somma indicato dai simboli} P

(42)

l’etichetta dell’input prefix e la relativa variabile. `E da notare che la regola Com richiede che i due processi coinvolti nella comunicazione debbano essere diversi per evitare che un processo base si sincronizzi con se stesso. Inoltre, dato che applichiamo le regole di transizione solo a stati ben-etichettati, non pu`o mai accadere che un processo base si sincronizzi con un’altra occorrenza dello stesso processo. Infatti, la presenza di due occorrenze di un processo base che contiene un input prefix renderebbe lo stato non ben-etichettato. Nell’esempio che segue mostriamo l’applicazione delle regole di transizione descritte in precedenza.

Esempio 3.3 In questo esempio mostriamo alcune delle possibili transizioni eseguibili dallo stato iniziale corrispondente al processo P dell’Esempio 3.2. Ricordiamo che il processo P ha la seguente forma

P =!(νaχ_)(νnγ_{)(¯an | a(x}β_).¯_xb).

e che lo stato iniziale `e

S0 = δ(P, envP) = ({(!(νaχ)(νnγ)(¯an|a(xβ).¯xb), 1)}, B∅, envP, R∅).

Dallo stato iniziale applicando la regola Copia si transisce in S1 = ({(P, 1), (¯a1n1, 1), (a1(xβ1).¯x1b, 1)}, B∅, envP[n1 7→ n1, a1 7→ a1],

R∅[χ 7→ {n1}, γ 7→ {a1}])

Da S1 con la regola Com si ottiene lo stato

S2 = ({(P, 1), (¯x1b, 1)}, B∅[β 7→ {x1}], envP[n1 7→ n1, a1 7→ a1, x1 7→ n1],

R∅[χ 7→ {n1}, γ 7→ {a1}])

e applicando nuovamente la regola Copia da S2 si transisce in

S3 = ({(P, 1), (¯x1b, 1), (¯a2n2, 1), (a2(xβ2).¯x2b, 1)}, B∅[β 7→ {x1}],

envP[n1 7→ n1, n2 7→ n2, a1 7→ a1, a2 7→ a2, x1 7→ n1],

R∅[χ 7→ {n1, n2}, γ 7→ {a1, a2}])

(43)

S4 = ({(P, 1), (¯x1b, 1), (¯x2b, 1)}, B∅[β 7→ {x1, x2}],

envP[n1 7→ n1, n2 7→ n2, a1 7→ a1, a2 7→ a2, x1 7→ n1, x2 7→ n2],

R∅[χ 7→ {n1, n2}, γ 7→ {a1, a2}])

La funzione env dello stato S4 ci dice che le variabili x1 e x2 sono legate

ri-spettivamente ai canali n1 e n2. Dalla funzione R possiamo dedurre che n1 e

n2 sono identificati dalla stessa etichetta χ; e analogamente che a1 e a2 sono

identificati dalla stessa etichetta γ; essi infatti derivano dalla duplicazione dello stesso processo.

Osservando l’insieme P roc e la funzione env di ogni stato è possibile indivi-duare quali canali sono trasmessi su ogni canale del processo P . In partico-lare, possiamo dire che sul canale a1 è inviato il canale n1 e sul canale a2 è

inviato il canale n2. 2

La seguente proposizione mostra che la ben-etichettatura degli stati `e man-tenuta dalle regole di transizione.

Proposizione 3.14 Sia S1 uno stato ben-etichettato. Se S1 7→ S2 allora S2

`e uno stato ben-etichettato.

La dimostrazione della Proposizione 3.14 `e mostrata in Appendice A.

3.3 Relazione tra semantica normale e

seman-tica a riduzioni

In questo paragrafo mostriamo la relazione tra la semantica a riduzioni stan-dard adattata ai processi ben-etichettati, come descritto nel Paragrafo 3.1, e le regole di transizione della semantica normale presentate in Tabella 3.2. Formalizzare tale relazione `e piuttosto complesso, in quanto la semantica a riduzioni non tiene traccia delle comunicazioni avvenute in precedenza. Per semplificare la dimostrazione, introduciamo una semantica a riduzioni de-corata per i processi ben-etichettati. Tale semantica `e equivalente a quella presentata nel Paragrafo 3.1, ma mantiene informazioni aggiuntive simili a quelle della semantica normale.

(44)

3.3.1 Semantica a riduzioni decorata

La semantica a riduzioni decorata differisce da quella adottata per i processi ben-etichettati solo per il fatto che la relazione → `e decorata con una coppia di funzioni φ = (Bφ, envφ), dove B ∈ B e env ∈ EN V. Queste funzioni

mantengono informazioni sulla possibile comunicazione avvenuta nel passo di computazione. In particolare, la funzione Bφ mantiene l’associazione tra

l’etichetta della variabile oggetto dell’input prefix coinvolto nella comunica-zione e la variabile stessa; mentre la funcomunica-zione envφ mantiene l’associazione

tra la variabile dell’input prefix e il nome di canale comunicato. Le regole di riduzione decorate con l’informazione φ sono presentate in Tabella 3.3.

Tabella 3.3: Regole di riduzione decorate per processi ben-etichettati

(P₁+¯az.P )|(P₂+a(yβ_).Q)(B∅[β7→{y}],env⊥[y7→z])

−→ P |Q[z/y] (Com) !P (B∅,env⊥) −→ !P |newP(P ) (Copia) [x = x]P (B∅,env⊥) −→ P (Match) P → Q implica P |Rφ → Q|Rφ (Par) P → Q implica (νxφ χ_)P _{→ (νx}φ χ_)Q _(Res) (P0 φ_{→ Q}0_{, P ≡ P}0_{, Q ≡ Q}0_{) implica P} _{→ Q}φ _(Struct)

Le regole di riduzione decorate sono analoghe a quelle della semantica a ri-duzioni per i processi ben-etichettati. `E da notare che la regola (Com) `e l’unica regola che aggiorna la coppia di funzioni (B∅, env⊥), per memorizzare

l’informazione relativa alla comunicazione avvenuta. Inoltre, per ogni coppia φ = (Bφ, envφ) esiste al pi`u un’etichetta β ∈ LabI tale che B(β) 6= ∅, ed

esiste al pi`u un nome n ∈ eN tale che env(n) 6=⊥.

Di seguito usiamo −→φ ∗ per indicare la chiusura riflessiva e transitiva della relazione −→, e scriviamo Pφ −→φe nQ, con eφ = (φ1, . . . , φn), per indicare una

(45)

computazione lunga n passi. Notiamo che se n = 0, allora la computazione `e vuota. Inoltre, indichiamo con C l’insieme delle computazioni.

Storia di una computazione. La sequenza delle coppie (φ1, . . . , φn)

rela-tive ad una computazione P −→nQ, ci permette di ricostruire a

posterio-ri la stoposterio-ria di tale computazione. In particolare, `e possibile mettere in-sieme le informazioni relative a tutte le comunicazioni eseguite durante la computazione.

Definizione 3.15 (Storia) Una storia H ∈ H `e una tripla (B, env, R), tale che B ∈ B, env ∈ EN V e R ∈ R, e valgono le seguenti condizioni:

• ∀β ∈ LabI _{: B(β) ⊆ V} β;

• ∀x ∈ V : x ∈S_β∈LabIB(β) ⇔ ∃n ∈ eN : env(x) = n ∧ n 6= x;

• ∀n ∈ eN : n 6∈S_β∈LabIB(β) ⇒ env(n) =⊥ ∨ env(n) = n ∨

env(n) = >;

• ∀x ∈ dom(env) : env(x) 6= > ⇒ env(x) ∈ dom(env);

• ∀χ ∈ LabR _{: R(χ) ⊆ N} χ;

• ∀n ∈ N : n ∈S_χ∈LabRR(χ) ⇒ env(n) = n.

Assumiamo che l’inclusione e l’unione sulle storie, ovvero vH _{e t}H_{, siano}

definite componente per componente.

Introduciamo adesso alcune notazioni che useremo di seguito.

Notazioni

• Siano env1, env2 ∈ EN V. Abbiamo che env1 4 env2 se e solo se ∀x ∈

dom(env1) si ha che env1(x) = env2(x).

• Sia H = (B, env, R) una storia. Indichiamo con n(H) i nomi di H, ovvero n(H) =S_β∈LabIB(β) ∪ dom(env) ∪

S

(46)

• Sia R ∈ R una funzione. Indichiamo con envidR ∈ EN V la funzione

tale che per ogni nome n ∈ S_χ∈LabRR(χ) : env_idR(n) = n e per ogni

n ∈ ( eN \S_χ∈LabRR(χ)) : env_idR(n) =⊥.

Prima di definire la funzione che permette di ottenere la storia di una compu-tazione, introduciamo la funzione Res : P → R usata nella Definizione 3.16. La funzione Res associa ad un processo P la funzione R ∈ R, che mappa ogni etichetta all’insieme dei nomi ristretti al top-level di P . Tale funzione `e definita nel seguente modo:

Res(P) = R∅ Res(!P ) = R∅ Res([x = y]P ) = R∅ Res((νχ_{)P ) =} ( Res(P ) t R∅[χ 7→ {n}] se n ∈ f n(P ) Res(P ) altrimenti

Res(P1|P2) = Res(P1) t Res(P2)

La funzione che consente di ottenere la storia di una computazione `e definita come segue.

Definizione 3.16 Sia C = P0

(B1,env1)

−→ P1

(B2,env2)

−→ . . .(Bn,envn−→ ) Pn una

com-putazione. La storia di C `e ottenuta attraverso una funzione History : C → H definita come segue:

History(C) = (B, env, R) dove

• B =Fn_i=1Bit B∅

• env =Fn_i=1envit envP0 t envidR • R =Fn_i=0Res(Pi).

Introduciamo adesso la nozione di storia consistente per un processo P . Definizione 3.17 (Storia consistente) Sia P un processo ben-etichettato e sia H = (B, env, R) una storia. Diciamo che H `e una storia consistente per P se valgono le seguenti condizioni:

(47)

1. envP 4 env;

2. Res(P ) v R;

3. ∀x ∈ var(P ) : env(x) =⊥;

4. ∀x ∈ eN : env(x) 6= >;

5. i nomi ristretti non al top-level di P sono diversi dai nomi presenti in S

χ∈LabRR(χ).

Da qui in poi consideriamo solo computazioni P0

φ1 → P1 φ2 → . . . → Pφn n, dove ad ogni passo Pi φi+1

→ Pi+1, se consideriamo la storia Hi consistente per Pi,

abbiamo che (bn(Pi+1) \ bn(Pi)) ∩ n(Hi) = ∅.

`

E da notare che bn(Pi+1) \ bn(Pi) sono i nuovi nomi legati introdotti

dal-l’esecuzione di un passo di replicazione e i nuovi nomi ristretti introdotti dall’applicazione delle regole di congruenza.

Di seguito usiamo new(P → Q) per indicare l’insieme dei nomi legati intro-φ dotti da un’applicazione di newP, ovvero quelli introdotti dall’esecuzione di

un passo di replicazione.

Definiamo formalmente l’operazione new per ogni regola di transizione della Tabella 3.3:

new((P₁+¯az.P )|(P₂+a(yβ_).Q))_{−→ P |Q[z/y]) = ∅}φ _{Reg. (Com)}

new(!P −→!P |newφ P(P )) = bn(newP(P )) Reg. (Copia)

new([x = x]P −→ P ) = ∅φ Reg. (Match)

new(P |R→ Q|R) = new(Pφ → Q)φ Reg. (Par)

new((νxχ_)P _{→ (νx}φ χ_{)Q) = new(P} _{→ Q)}φ _{Reg. (Res)}

new(P → Q) = new(Pφ 0 φ_{→ Q}0₎ _{Reg. (Struct).}

Introduciamo adesso due teoremi che mostrano la relazione tra la semantica a riduzioni decorata e la semantica a riduzioni dei processi ben-etichettati. Teorema 3.18 (Correttezza) Siano P e Q due processi ben-etichettati e sia H una storia consistente per P .

(48)

1. Se P ≡ Q considerando la storia H, ovvero (bn(Q)\bn(P ))∩n(H) = ∅, allora P ≡ Q.

2. Se P → Q considerando la storia H, ovvero (bn(Q)\bn(P ))∩n(H) = ∅,φ allora P → Q.

Teorema 3.19 (Completezza) Siano P e Q due processi ben-etichettati e sia H una storia consistente per P .

1. Se P ≡ Q, allora esiste un processo ben-etichettato Q0 _{tale che Q}0 _`e

α−equivalente a Q e P ≡ Q0 _{considerando la storia H, ovvero (bn(Q}0_)\

bn(P )) ∩ n(H) = ∅.

2. Se P → Q, allora esiste un processo ben-etichettato Q0 _{tale che Q}0 _`e

α−equivalente a Q e P → Qφ 0 _{considerando la storia H, ovvero (bn(Q}0_)\

bn(P )) ∩ n(H) = ∅.

3.3.2 Equivalenza tra stati concreti

Nel presente paragrafo introduciamo una nozione di equivalenza tra stati ben-etichettati. Intuitivamente, la relazione identifica stati a meno di α-conversione delle componenti e a meno di congruenza dei processi base. Tale equivalenza `e usata per mostrare la relazione tra la semantica a riduzioni decorata e la semantica normale.

Per semplificare la notazione, di seguito useremo:

• IMBS =

S

β∈LabIB(β) per indicare l’insieme delle variabili presenti

nell’immagine della funzione B di uno stato S;

• IMRS =

S

χ∈LabRR(χ) per indicare l’insieme dei nomi ristretti presenti

nell’immagine della funzione R di uno stato S.

Definizione 3.20 (Equivalenza tra stati concreti) Siano S1, S2 ∈ SE.

Diciamo che S1 ∼ S2 se e solo se |P rocS1| = |P rocS2| ed esiste una funzione