Dipartimento di Informatica Corso di Laurea Magistrale in Informatica
Un type-system per IoT-Lysa:
un linguaggio per modellare sistemi IoT.
Relatori:
Prof. Pierpaolo Degano
Dott. Letterio Galletta
Candidato:
Federico Forte
Indice
1 Introduzione. 6
1.1 Accenni all’ Internet of Things. . . 6
1.2 Il linguaggio IoT-Lysa. . . 8
1.3 Lo scopo della tesi. . . 10
1.4 Struttura della tesi. . . 11
2 IoT-Lysa: un linguaggio per modellare sistemi IoT. 12 2.1 Il π-calcolo e IoT-Lysa. . . 12
2.2 Un breve presentazione di IoT-Lysa. . . 13
2.3 La sintassi astratta. . . 14 2.4 Un esempio di modellazione. . . 16 2.5 La sintassi concreta. . . 19 2.5.1 Le signature. . . 19 2.5.2 I nodi. . . 20 2.5.3 Sensori e attuatori. . . 21 2.5.4 I processi. . . 21
2.5.5 Specifica del range delle comunicazioni. . . 23
2.6 Implementazione del sistema condizionatore. . . 25
2.7 CFA: Control Flow Analysis. . . 27
2.8 ChorGram: un tool di supporto per IoT-Lysa. . . 29
3 Il type-system. 31 3.1 Alcuni formalismi. . . 32
3.2 La sintassi astratta utilizzata. . . 33
3.3 I domini semantici. . . 33
3.4 L’ambiente e la memoria di tipo. . . 35
3.5 La regola iniziale del sistema. . . 36
3.6 Le regole per le signature. . . 39
3.7 Le regole per i sensori e attuatori. . . 40
3.8 Le regole per i nodi. . . 42
3.9 Le regole per i componenti. . . 43
3.10 Le regole per le espressioni. . . 46
3.11 Le regole per i processi. . . 49
4 Implementazione. 55
4.1 Il modulo Domain. . . 55
4.2 Il modulo Utils. . . 57
4.2.1 L’ambiente predefinito. . . 57
4.2.2 La funzione GlobalState. . . 59
4.2.3 Riconoscimento delle keyword. . . 59
4.2.4 Gestione delle variabili generiche. . . 60
4.3 Il modulo Exceptions. . . 61
4.4 Il namespace Algorithms. . . 61
4.5 Il risultato dell’analisi e un esempio. . . 62
4.6 Altre parti significative. . . 64
4.6.1 L’inizializzazione del type-checking. . . 64
4.6.2 Il poliformismo dell’operatore di uguaglianza. . . 66
4.6.3 La receive dei processi. . . 68
4.7 Test e unit test. . . 70
5 Conclusioni. 72 5.1 Conclusioni. . . 72
5.2 Sviluppi futuri. . . 73
6 Ringraziamenti. 74
Elenco delle figure
2.1 Sintassi astratta del sistema globale e di un nodo. . . 14
2.2 Sintassi astratta di un processo. . . 15
2.3 Sintassi astratta rispettivamente di un sensore e attuatore. . . 15
2.4 Sintassi astratta delle espressioni. . . 16
2.5 Sistema condizionatore: nodo Cond. . . 17
2.6 Sistema condizionatore: nodo Th1. . . 17
2.7 Sistema condizionatore: nodo Th2. . . 18
2.8 Un albero astratto infinito. . . 28
3.1 Regola iniziale del type-system per il programma. . . 37
3.2 Regole per costruire l’ambiente di tipo del type-system. . . 38
3.3 Regole del type-system per i sensori. . . 40
3.4 Regole del type-system per gli attuatori. . . 41
3.5 Regole per type-system per il primo livello del sistema. . . 42
3.6 Regole del type-system per il singolo nodo. . . 44
3.7 Regole del type-system per le espressioni. . . 47
3.8 Regole del type-system per i processi (escluso comunicazioni). . . 50
Listings
1.1 Esempio di un modello IoT-Lysa. . . 9
2.1 Esempio di signature in IoT-Lysa. . . 20
2.2 Esempio di dichiarazione di un sensore e attuatore in IoT-Lysa. . 20
2.3 Esempio di dichiarazione di un processo in IoT-Lysa. . . 22
2.4 Implementazione signature e condizionatore del sistema. . . 24
2.5 Implementazione dei termometri del sistema condizionatore. . . . 26
2.6 Specifica della topologia per il sistema condizionatore. . . 26
3.1 Specifica in F# della sintassi astratta di IoT-Lysa. . . 34
3.2 Implementazione del dominio di tipi del type-system. . . 34
3.3 Programma di esempio per il guessing. . . 53
4.1 Codice del dominio di tipo. . . 56
4.2 Codice per la costruzione dell’ambiente predefinito. . . 58
4.3 Codice della funzione GlobalState. . . 59
4.4 Codice per il riconoscimento delle keyword. . . 60
4.5 Codice per il supporto delle variabili generiche. . . 60
4.6 Codice delle dichiarazioni di alcune eccezioni. . . 61
4.7 Signatures del namespace TypeChecker.Algorithms. . . 62
4.8 Il risultato dell’analisi. . . 63
4.9 Esempio di utilizzo della libreria. . . 63
4.10 Codice dell’inizio del type-checking. . . 65
4.11 Codice per il polimorfismo dell-operatore . . . 67
4.12 Codice della valutazione del comando receive. . . 69
Capitolo 1
Introduzione.
1.1
Accenni all’ Internet of Things.
Il termine Internet of Things [1, 2, 3, 4] (abbreviato con IoT nel seguito) indica sistemi composti di oggetti dotati di componenti software e hardware, quali sensori, attuatori e strumenti di connettività alla rete (non necessaria-mente Internet), che in maniera autonoma sono capaci di raccogliere informa-zioni, elaborarle, scambiarle con altri servizi, al fine di migliorare le proprie funzionalità.
Alcuni tipici esempi sono:
• RFID management systems, ossia sistemi di oggetti forniti di sensori RFID [35] per l’identificazione e il tracciamento della posizione. Si pensi ad esempio un sistema per una biblioteca che segnala al bibliotecario i libri fuori posto individuandoli attraverso la rilevazione dei sensori attaccati al-le copertine dei libri (vedi [39]). Un altro esempio simial-le è l’identificazione e il tracciamento di animali per l’allevamento (vedi [40]).
• Smart clothes/shoes [38], ovvero indumenti equipaggiati con sensori in grado di raccogliere costantemente dati durante l’allenamento: come il numero di passi, stima delle calorie consumate ma anche dati più signifi-cativi come la correttezza della postura, il battito cardiaco, ecc. Gli oggetti permettono di ricevere raccomandazioni in tempo reale per modificare l’al-lenamento e in seguito recuperare i risultati di analisi in considerazione degli obbiettivi.
• Driverless cars, cioè macchine capaci di muoversi autonomamente verso una destinazione. Tali macchine richiedono una vasta serie di tecnologie a partire da sensori per controllare lo stato della macchina (software e meccanico), dispositivi GPS per la posizione, Radar per rilevare le velocità di corpi, sensori e software per riconoscimenti di diversi tipi di ostacoli, ma anche poter comunicare con le automobili o altri oggetti circostanti.
• IoT healthcare solutions [41], vale a dire sistemi o strumentazioni a fini medici. Ad esempio macchinari che costantemente monitorizzano un pa-ziente e autonomamente valutano se intervenire in caso di emergenza, op-pure strumenti per supportare un chirurgo in sala operatoria in interventi di estrema precisione o particolarmente invasivi per il paziente.
Le nuove tecnologie hanno permesso agli oggetti di smettere di assumere il ruolo classicamente passivo. La metafora che rappresenta bene l’idea è vedere gli oggetti “arricchiti” di sensori e attuatori in maniera che i sensori siano i loro occhi per osservare l’ambiente e gli attuatori le loro braccia e gambe per compiere azioni o muoversi nello spazio. Inoltre, la capacità di computazione e l’accesso ai servizi in rete rende gli oggetti capaci di pensare e prendere decisioni autonomamente [5].
La caratteristica chiave di un sistema IoT maturo è l’attenzione riservata alle informazioni e alla qualità dei servizi che determinano il comportamento degli oggetti. Se prima le informazioni erano fortemente connesse all’attività umana come la pressione di un bottone, lo scatto di una foto, la scansione di un bar-code ecc., i sistemi IoT tendono a ridurre l’operato umano permettendo di raccogliere una maggiore mole di dati, con più accuratezza e con più responsività. Per migliorare la qualità del servizio del sistema è vitale l’apertura verso servizi esterni, insieme di servizi che spesso differiscono sia per le informazioni trattate che delle politiche governative di appartenenza.
Per investire con successo in un sistema IoT di medie o grandi dimensioni è fondamentale come punto di partenza il consenso generale della società [6]. Infatti, il fenomeno si sta rivelando sempre più invasivo e coinvolge tutti gli aspetti dell’uomo e della società. La maggiore preoccupazione riguarda la pri-vacy delle informazioni coinvolte, che pongono in discussione la libertà stessa del singolo individuo. La gravità dei rischi dipende dalla natura delle informazioni. I rischi non sono solo causati dall’attività maliziosa da parte di attaccanti, ma sono anche dovuti ad errori di sistema. Un errore causa innanzitutto un danno economico: ad esempio come spese di risarcimento, spese legali, spese promozio-nali, i costi di correzione dell’errore nel sistema, senza considerare il danno alla reputazione dell’azienda stessa con la diminuizione dell’interessamento e della fiducia degli utenti verso l’azienda.
La diffusione dei sistemi IoT è stata resa possibile dal miglioramento delle tecniche di miniaturizzazione dei chip elettronici e dei loro costi di produzione minore. La proliferazione delle tecnologie quali ad esempio RFID, NFC [36], codici QR [37] hanno reso possibile a oggetti tradizionalmente non digitali di essere identificati univocamente. Il continuo perfezionamento delle tecnologie di rilevazione (indicato con sensor technology in letteratura) ha incrementato l’efficienza di tali sistemi. Ha inciso la crescente disponibilità generale di ac-cesso a Internet e diffusione di smart-phone almeno per quanto riguarda i paesi più sviluppati. Infine i progressi ottenuti per i linguaggi di programmazione, algoritmi e strutture dati hanno reso possibile la gestione di software complessi sempre più efficiente e sicura.
1.2
Il linguaggio IoT-Lysa.
Un sistema IoT richiede una attenta fase di specifica e progettazione. In tal senso è utile costruire un modello del sistema e con tecniche formali verificare proprietà e individuare punti deboli o errori. Il linguaggio IoT-Lysa si propone come strumento di specifica di modelli di sistemi IoT. I modelli costruiti descrivono sistemi che sono tipicamente statici ovvero in cui gli oggetti intelligenti hanno una posizione fissa e la topologia delle comunicazioni non cambia. Il sistema è rappresentato da un’insieme di nodi (ovvero gli oggetti intelligenti) composti da 3 tipi di componenti:
sensori: sono i componenti con il compito di rilevare dati dall’ambiente; attuatori: sono i componenti capaci di modificare l’ambiente con azioni
pre-stabilite;
processi controllori: sono i componenti cui è affidata la logica del nodo, tra cui comunicare con gli altri nodi e indicare azioni per gli attuatori.
Ogni nodo possiede una memoria condivisa tra tutti i suoi processi. Per ogni sensore del nodo è riservata una cella per contenere le rilevazioni dall’ambiente e può essere acceduta in sola lettura da parte dei processi. È previsto un unico canale di comunicazione asincrono per la comunicazione tra i nodi. I costrutti di invio trattano messaggi formati da tuple, e i destinatari di ogni messaggio sono indicati esplicitamente. Invece per la ricezione è presente la possibilità di accettare messaggi attraverso un pattern-matching su un numero arbitrario di componenti iniziali del messaggio.
Come esempio di uso di IoT-Lysa si consideri un sistema per il controllo della porta di un garage che potrebbe essere un sottosistema di un sistema di domotica più complesso. Supponiamo che la porta possiede le seguenti caratteristiche:
• sia possibile comandare la porta in remoto;
• la porta si chiuda autonomamente se rimane aperto oltre un lasso di tempo.
Il listato 1.1 mostra il programma IoT-Lysa che descrive il sistema. Il program-ma è suddiviso in due sezioni: una priprogram-ma in cui sono dichiarate nuove definizioni che aumentano la leggibilità del modello, e a seguire, la specifica dei nodi.
Il listato mostra soltato il nodo del garage omettendo la controparte del Server. Il garage contiene 2 componenti sensori: Sdoorper l’osservazione dello stato della porta modellato dal tipostatus_t, eStimerper la rilevazione dell’ora modellata dal tipotimestamp. Entrambi i sensori rilevano i dati dall’ambiente, rilevazione modellata dall’istruzione probe. Il nodo contiene anche un’attuato-re Adoor di tipoadoor_t per manipolare la porta. L’attuatore ricorsivamente attende con il comandowait_foruna tra le azioniopene close.
Il nodo contiene anche la dichiarazione di due processi controllori. Il primo ha il compito di comunicare con il nodo server per ricevere le richieste dei comandi.
Listing 1.1: Esempio di un modello IoT-Lysa. 1 type s t a t u s _ t
2 type timestamp 3
4 func i s E x p i r e d T i m e ( timestamp , timestamp ) : b o o l 5 func OPEN : s t a t u s _ t
6 func CLOSE : s t a t u s _ t 7 func REQ : number 8 func ACK : number 9
10 actuator_type adoor_t { c l o s e , open } 11
12 node Garage =
13 sensor Sdoor : s t a t u s _ t = rec h . t a u ; p r o b e ; h 14 sensor S t i m e r : timestamp = rec h . t a u ; p r o b e ; h
15 actuator Adoor : adoor_t = rec h . w a i t _ f o r ( c l o s e , open ) ; h 16 17 process = 18 rec h . 19 r e c v (REQ; r e q _ f o r _ d o o r ) ; 20 i f n o t ( Sdoor = r e q _ f o r _ d o o r ) then 21 i f r e q _ f o r _ d o o r = OPEN then 22 @Adoor . open ; 23 snd (ACK, OPEN) to [ S e r v e r ] 24 h 25 e l s e 26 @Adoor . c l o s e ; 27 snd (ACK, CLOSE) to [ S e r v e r ] 28 h 29 e l s e 30 h 31 32 process = 33 l a s t S t a t u s := Sdoor ; 34 l a s t T i m e := S t i m e r ; 35 rec h .
36 i f Sdoor = OPEN then
37 i f l a s t S t a t u s = OPEN then 38 i f i s E x p i r e d T i m e ( l a s t T i m e , S t i m e r ) then 39 @Adoor . c l o s e ; 40 l a s t S t a t u s := CLOSE ; 41 h 42 e l s e 43 h 44 e l s e 45 l a s t S t a t u s := OPEN; 46 l a s t T i m e := S t i m e r ; 47 h 48 e l s e 49 l a s t S t a t u s := CLOSE ; 50 h 51 52 node S e r v e r = 53 . . .
Alla riga 19 viene ricevuta la richiesta di comando riconosciuta dal successo del pattern-matching del primo campo con la costante REQ. Il comando è invece assegnato alla variabilereq_for_door. Il test alla riga 20 coinvolge la variabile
Sdoorin lettura per modellare la lettura dello stato della porta. Alle righe 22 e 26 sono modellate le richieste all’attuatore di interazione con la porta. Il secondo processo controlla se la porta è rimasta aperta per il tempo prestabilito. La funzioneisExpiredTime modella il test se la durata di un arco di tempo impone la chiusura della porta.
1.3
Lo scopo della tesi.
Tra gli strumenti a disposizione per il linguaggio IoT-Lysa è presente un compi-latore il cui sorgente è accedibile a [13]. Il compicompi-latore genera a partire da un modello IoT-Lysa il corrispondente modello ChorGram che riproduce le comunicazioni del sistema.
Un modello ChorGram è composto di automi denominati Communicating Finite State Machines (abbreviati anche con CFSMs) che descrivono le intera-zioni di componenti comunicanti, come i nodi in un sistema nel caso di IoT-Lysa. Il modello CFSM astrae il comportamento del sistema costruendo un grafo in cui gli stati considerano l’avanzamento in parallelo dei singoli automi, e gli archi sono etichettati con le operazioni di invio o ricezione sul canale. Gli strumenti di analisi per ChorGram permettono la ricerca di stati non desiderati nel grafo generato, come lo stato di deadlock ovvero uno stato in cui nessuno degli automi (associati ai nodi) può avanzare ulteriormente.
Il progetto del compilatore è ancora in fase di implementazione e prima della scrittura di questa tesi, non era presente un type-system per il compilatore. Un type-system è una collezione di regole per validare la consistenza di un program-ma in rispetto alla seprogram-mantica del linguaggio. Il type-checker è il componente che implementa le regole e durante la compilazione valida semanticamente il programma sorgente.
Lo scopo di questa tesi è duplice:
1. specificare un type-system per il linguaggio IoT-Lysa;
2. implementare un type-checker che si integri con il compilatore presente.
La specifica del type-system prevede la costruzione di un sistema di deduzio-ne logica indipendente dall’implementaziodeduzio-ne per la dimostraziodeduzio-ne di validità di enunciati. Gli enunciati coinvolgono i componenti sintattici del linguaggio stesso e oggetti del dominio semantico. Il compito del type-checker è verificare l’esi-stenza di una dimostrazione degli enunciati per ogni componente sintattico del programma.
1.4
Struttura della tesi.
Il seguito della tesi è organizzata come segue:
• il capitolo 2 fornisce una panoramica approfondita del linguaggio IoT-Lysa. Formalizza le proprietà dei sistemi che IoT-Lysa intende modellare e pre-senta sia la sintassi astratta che concreta. Esso conclude accennando gli strumenti di analisi statiche previste per il linguaggio.
• il capitolo 3 descrive il processo che ha portato alla specifica del type-system. Inizia introducendo i formalismi matematici utilizzati per la specifica delle regole, i domini semantici e le strutture dati che coinvolgono gli enunciati. Infine espone tutte le regole del type-system con esempi di costruzione di dimostrazioni completi.
• il capitolo 4 presenta la libreria F# che implementa il typechecker. La libreria è divisa in 4 parti principali. Per ogni parte è mostrato il codice più significativo e commenta le scelte implementative in maniera esaustiva. • il capitolo 5 conclude riepilogando il contributo di questa tesi e presentando
Capitolo 2
IoT-Lysa: un linguaggio per
modellare sistemi IoT.
Progettare, implementare, testare un sistema IoT non è semplice, perché il pro-gettista deve tenere in considerazione diversi aspetti tra loro interlacciati, come le esigue risorse hardware a disposizione, i protocolli di rete da usare, e gli aspetti algoritmici per l’acquisizione e la manipolazione dei dati. È dunque fondamen-tale valutare un sistema fin dalle specifiche, ancora prima di implementarlo, ovvero ragionare su un modello del sistema che riassume le caratteristiche es-senziali di un sistema IoT. È qui che entra in gioco IoT-Lysa, linguaggio per modellare un sistema IoT.
Il capitolo inizia con una introduzione sul linguaggio IoT-Lysa descrivendone le caratteristiche che lo contraddistinguono. Viene presentata la sintassi astratta e concreta del linguaggio esemplificati attraverso la descrizione di esempi. Infine vengono introdotti gli strumenti per l’analisi statica dei modelli IoT-Lysa.
Le regole per la semantica del linguaggio e per la specifica della CFA ( intro-dotta nella sezione 2.7) sono state omesse e sono consultabili ai riferimenti [8, 9, 10, 11].
2.1
Il π-calcolo e IoT-Lysa.
Il linguaggio IoT-Lysa [8, 9, 10, 11, 13] prende ispirazione dal linguaggio LySa [12, 17], il quale a sua volta è una estensione del π-calcolo [19, 20] da cui eredita gran parte della sua sintassi. Il π-calcolo è un linguaggio di modellazione di processi concorrenti capaci di comunicare attraverso canali denotati da nomi. Tali nomi sono valori che possono essere scambiati tra i processi, cambiando in questo modo chi può accedere ad un canale e come le informazioni possono muoversi tra i processi.
Esistono molte estensioni del π-calcolo che aggiungono costrutti per spe-cializzarsi in un determinato contesto. Ad esempio, lo Spi-calcolo [21] è un’e-stensione del π-calcolo con lo scopo di modellare protocolli di rete. Per questo motivo aggiunge alla sintassi del π-calcolo costrutti di criptaggio dei messag-gi. Inoltre, lo Spi-calcolo fornisce strumenti per analizzare come le informazioni confidenziali si spostano tra i partecipanti. A sua volta, LySa eredità molto dal Spi-calcolo ma si differenzia scegliendo di rappresentare le comunicazioni con un unico canale per tutti i processi. Questa scelta si rileva più accurata per i protocolli di autenticazione nelle reti ethernet e wireless in cui tutti i nodi possono leggere i messaggi.
IoT-Lysa cerca di riadattare il π-calcolo e LySa per applicazioni IoT. Il ria-dattamento è in realtà corposo, perché il π-calcolo modella i processi in maniera troppo astratta. IoT-Lysa, invece, cattura la struttura tipica di un’applicazione IoT considerando un sistema composto da un insieme di nodi i quali possono avere sensori e attuatori per interagire con l’ambiente. Il vantaggio di tale sforzo è quello di ereditare o riadattare per l’IoT le tecniche di analisi già consolidate e presenti per LySa, come gli algoritmi per la control flow analysis (detta CFA). IoT-Lysa non è l’unico linguaggio di modellazione. Un esempio di un altro approccio è IoT-calculus [7] in cui viene modellata la dinamicità delle connes-sioni tra gli oggetti. Gli scenari in cui si specializza IoT-Lysa sono caratterizzati dal fatto che tutti gli oggetti hanno una loro posizione determinata e la topologia tra gli oggetti è statica.
2.2
Un breve presentazione di IoT-Lysa.
I punti chiave nelle scelte di modello IoT-Lysa sono i seguenti:
• un sistema è un insieme di nodi. I nodi sono formati da 3 diversi compo-nenti: sensori, attuatori e processi controllori. I primi sono entità attive capaci di rilevare eventi dall’ambiente con una propria frequenza. Le ri-levazioni sono a disposizione dei processi in sola lettura in variabili di una memoria condivisa del nodo. Gli attuatori sono invece entità passive pronti a intraprendere richieste di azioni per interagire con l’ambiente. Ai processi controllori è affidata la logica del nodo, compresa la manipolazio-ne dei dati letti dai sensori. Tutti i processi dello stesso nodo condividono il medesimo spazio di memorizzazione con cui è possibile simulare una comunicazione tra essi.
• è presente un unico canale di comunicazione asincrono per comunicazioni 1-molti . Sono dati esplicitamente i nodi destinatari di ogni messaggio. La topologia della rete è decisa con regole definite staticamente per modellare la nozione di prossimità. I messaggi inviati sono tuple di arietà libera. È presente la possibilità di accettare i messaggi attraverso pattern matching su un numero arbitrario di componenti iniziali.
N 3 N ::=
0 sistema vuoto
l : [B] singolo nodo etichettato da l N1 || N2 composizione parallela di nodi
B 3 B ::=
Σl memoria del nodo
S sensore unicamente identificato da i ∈ Il
A attuatore unicamente identificato da i ∈ Il
P processo controllore
B | B composizione parallela di componenti
Figura 2.1: Sintassi astratta del sistema globale e di un nodo.
Un esempio tipico dell’uso di IoT-Lysa è quello dei sistemi IoT denominati smart cities, ovvero in cui è presente una gestione intelligente delle risorse (come il con-sumo della corrente) per i servizi come l’illuminazione delle strade. Ad esempio, in questi sistemi gli oggetti intelligenti principali sono i lampioni dotati di sen-sori e attuatori. I sensen-sori servono per la rilevazione di dati come: ricoscimento di auto, targhe o persone, per il livello di batteria del lampione, per il livello dell’illuminazione circostante, ecc. Gli attuatori potrebbero permettere di ac-cendere o spegnare un lampione, agire sull’intensità dell’illuminazione, o poter avvertire una stazione centrale in caso di guasti.
2.3
La sintassi astratta.
La figura 2.1 mostra la sintassi astratta di un sistema IoT-Lysa. Il sistema possiede una struttura a due livelli: un primo livello per la definizione di un nodo e della loro composizione parallela. La definizione di un singolo nodo può assumere due forme: un nodo identificato da una etichetta l ∈ L, dove L è l’insieme delle etichette, o il sistema vuoto.
Ogni nodo è la composizione in parallelo di vari componenti. Un componen-te dei nodi (sempre in figura 2.1) può essere una memoria incomponen-terna al nodo, un sensore, un attuatore o un processo controllore. Viene assunto per semplicità che nella definizione di un nodo è presente al più un solo componente memoria Σl: XS Il→ V, dove X e V sono la categoria sintattica per definire
rispettiva-mente i nomi delle variabili e i valori costanti. La memoria viene intesa come un array con spazio di indirizzi che comprende oltre ai nomi delle variabili dei pro-cessi anche gli indirizzi identificativi dei sensori e attuatori. Gli indirizzi riservati ai sensori possono essere acceduti solo in lettura dai processi per modellare la lettura dei valori rilevati dall’ambiente. Poichè la memoria è unica in un dato nodo, si modella implicitamente una condivisione tra i processi. Si assume che le operazioni in memoria siano atomiche e che i processi non modifichino le celle destinate ai sensori e attuatori.
Le regole di costruzione dei processi sono mostrate in figura 2.2. Un processo può essere il processo inattivo che non compie alcuna operazione, un prefisso per
P 3 P, Q ::=
0 processo inattivo
x := E. P assegnamento a x ∈ X
E?P : Q costrutto condizionale
< j, γ > . P azione γ all’attuatore j
P + Q scelta non deterministica
µh. P definizione ricorsiva
h variabile di ricorsione
E1, · · · , Ek to [L]. P invio multiplo asincrono
( E1, · · · , Ej; xj+1· · · , xk). P ricezione con pattern matching
Figura 2.2: Sintassi astratta di un processo.
S 3 S ::=
0 sensore inattivo
τ.S azione interna
i := v.S azione di rilevamento del sensore µh.S definizione ricorsiva
h variabile di ricorsione
A 3 A ::=
0 attuatore inattivo
τ.A azione interna
(|j, Γ|).A j indice attuatore, Γ azioni attese γ.A azione dell’attuatore
µh.A definizione ricorsiva h variabile di ricorsione
Figura 2.3: Sintassi astratta rispettivamente di un sensore e attuatore.
un assegnamento, un prefisso condizionale, un prefisso per indicare ad un attua-tore di intraprendere una specifica azione, scelta non deterministica per simulare un costruttto switch, una definizione ricorsiva, ricorsione su una variabile di de-finizione ricorsiva. Inoltre è presente un prefisso di invio asincrono di messaggi. I messaggi sono formati da due parti: una tupla di valori per contenuto e la lista dei destinari indicati dalle loro etichette. I destinatari sono verificati se “rag-giungibili” nel sistema al momento della valutazione della semantica attraverso un insieme di regole che determinano i range delle trasmissioni dei nodi. Dal lato di ricezione invece si ha un prefisso che permette la selezione dei messaggi attraverso pattern matching. La forma è (E1, · · · , Ej; xj+1, · · · , xk): la prima
parte della lista fino a ’;’ contiene i pattern che saranno valutati al momento della ricezione di un messaggio. La loro semantica richiede che ci dovrà essere corrispondenza esatta tra il valore rappresentato dal pattern e quello contenuto nella tupla ricevuta. La seconda parte consiste in assegnamenti alle variabili nella memoria del processo. Si assume che le variabili indicate non siano indi-rizzi di sensori o attuatori. Infine si ha il prefisso < j, γ > con cui si modella la richiesta di eseguire l’azione γ sull’attuatore all’indirizzo j che interagirà con l’ambiente.
E 3 E ::=
v valore costante v ∈ V
i identificatore di un sensore i ∈ Il
x indirizzo di una variabile x ∈ X f (E1, · · · , Ek) funzione di aggregazione f ∈ F
Figura 2.4: Sintassi astratta delle espressioni.
Le strutture dei sensori e attuatori mostrate in figura 2.3 sono più semplici perché IoT-Lysa affida tutta la logica dei nodi ai processi controllori. La defini-zione di un sensore può assumere la forma di un sensore inattivo, compiere una azione interna τ , eseguire operazioni di rilevamento dei dati modellate come un assegnamento ad un indirizzo (riservato al sensore), e i costrutti per la defini-zione ricorsiva come per i processi. L’attuatore è analogo al sensore ma invece della rilevazione ha la possibilità di intraprendere una determinata azione per interagire con l’ambiente o di rimanere in attesa della richiesta di compiere una tra un insieme di azioni previste.
In figura 2.4 è mostrata la sintassi astratta delle espressioni. Un’espressione può essere un simbolo di un valore costante appartente all’insieme V, oppure un indice della memoria appartenente a I o X , rispettivamente per indicare un dato di sensore o una variabile dei processi. Può anche assumere la forma di una funzione di aggregazione per altri termini di espressioni.
2.4
Un esempio di modellazione.
In questa sezione viene presentato un esempio che modella un sistema di un condizionatore per raffreddare la temperatura in una stanza. Gli oggetti in-telligenti del sistema sono un condizionatore e due termometri. I termometri si scambiano le misurazioni delle temperature per una maggiore precisione e le comunicano al condizionatore (in realtà solo un termometro avrà questo ruo-lo). Il condizionatore rimarrà in attesa delle rilevazioni e se la temperatura è sotto una determinata soglia accenderà o spegnerà il processo di raffredamento agendo su un attuatore e notificando l’azione intrapresa al termometro. Inoltre supponiamo che uno dei due termometri possieda una propria batteria, il cui li-vello di carica è reperibile da un sensore. Quando il termometro rileva un lili-vello insufficiente notifica al condizionatore che intende spegnersi.
In figura 2.5 è mostrata la definizione del nodo Cond del condizionatore. Possiede due componenti: l’attuatore ACond per agire sul raffreddamento e il
processo controllore PCond. L’attuatore è un’entità che passivamente attende di
intraprendere una delle due azioni possibili.
Il processo controllore viene modellato come la scelta non deterministica di due processi. Il primo processo (Ponoff) rimane in attesa di ricevere le
tem-perature dai termometri per verificare se la temperatura ha superato la soglia threshold. In risposta, esso agisce sull’attuatore per il raffreddamento e notifica il termometro. Il secondo processo (Pquit) rimane in attesa della richiesta di
ACond def = µh. (|1, {turnon, turnoff}|). h Pquit def = (quit; i ). 0 Ponoff def = µh. (temp; x). threshold < x ?
< 1, turnon > . ack, on to [locT h1 ]. h :
< 1, turnoff > . ack, off to [locT h1 ]. h PCond
def
= Ponoff + Pquit
Conddef= locCond : [ ΣCond | ACond | PCond ]
Figura 2.5: Sistema condizionatore: nodo Cond.
ST emp def = µh. τ. 1 := v1. h SBattery def = µh. τ. 2 := v2. h Plistener def = µh. (temp; s). mt := s. h Pmain def = µh. battery := 2. bthreshold < battery ? t := 1. tp := t+mt. mt := tp/2. i := i+1. ( i = 10 ) ?
temp,mt to [locCond, locT h2]. (ack; j). i := 0. h
:
temp,mt to [locT h2 ]. h :
quit,0 to [locCond]. h
Th1 def
= locTh1 : [ ΣTh1 | ST emp | SBattery | Pmain| Plistener ]
Figura 2.6: Sistema condizionatore: nodo Th1.
terminazione di uso del condizionatore e permette la terminazione del processo PCond. Per garantire che i due processi non usino i messaggi destinati
all’al-tro viene utilizzata la ricezione con pattern matching: l’etichetta temp per i messaggi che trasportano temperature, la costante 0 per terminare.
Il nodo Cond è la composizione parallela di ΣCond come memoria locale del
nodo, l’attuatore ACond e il processo PCond. La memoria ΣCond è tale che la
locazione 1 è riservata per l’attuatore e possiede due locazioni per le variabili x e i.
Segue la modellazione del primo termometro Th1 in figura 2.6. Il nodo Th1
è il termemotro che possiede una propria batteria. I sensori ST emp e SBattery
sono rispettivamente le definizioni dei sensori per la temperatura e il livello di batteria. Essi continuamente compiono operazioni interne (rappresentate dal
ST emp def = µh. τ. 1 := v1. h PTh2 def = mt := 0. µh. temp,mt to [ locT h1 ]. (temp; x). t := 1. tp := t. mt := tp/2. h Th2 def = locTh2 : [ ΣPTh2 | ST emp| PTh2 ]
Figura 2.7: Sistema condizionatore: nodo Th2.
prefisso τ ) e rilevano i dati dal sensore. Le rilevazioni sono assegnate alle loca-zioni 1 per la temperatura e 2 per la carica di batteria. Queste stesse localoca-zioni sono usate dai processi del nodo per leggere le rilevazioni. Gli assegnamenti alle variabili battery e t sono evidenziate per ricordare che le costanti indicano un indirizzo di memoria piuttosto che le costanti numeriche.
Riguardo alla logica del nodo dividiamo i compiti in due processi controllo-ri. Il processo (Plistener) riceve le temperature dell’altro termometro e aggiorna
la variabile mt per condividerla con Pmain. Il secondo processo (Pmain) è più
complesso. Finchè la carica della batteria è sufficiente rileva la temperatura e aggiorna la variabile media mt. Dopo comunica la propria temperatura etichet-tando il messaggio con temp. Ogni 10 iterazioni la temperatura è inviata anche al condizionatore.
Alla composizione complessiva del nodo è presente anche il componente memoria ΣTh1 con gli indirizzi 1 e 2 riservati per i sensori.
Il secondo termometro (Th2) è mostrato in figura 2.7. È presente un
senso-re per la temperatura specificato già da ST emp il quale è ripetuto per maggior
chiarezza. Il processo controllore PTh2 rimane in ascolto sul canale delle tem-perature (riconosciute dalle etichette temp) così da contribuire ad una migliore valutazione della temperatura e condividerla con l’altro termometro.
Nella modellazione di PTh2 è presente un errore di modellazione nell’asseg-mamento alla variabile mt. Infatti, la variabile dovrebbe modellare la tempe-ratura media della stanza ma dopo la ricezione viene aggiornata con un valore solo in funzione del sensore Temp. Questo errore sarà poi catturato dalla CFA (vedi sezione 2.7). Per la memoria del nodo di nuovo l’indirizzo 1 è riservato al sensore.
Il sistema globale è modellato con la parallelizzazione dei 3 nodi:
2.5
La sintassi concreta.
Attraverso esempi segue la descrizione della sintassi concreta di IoT-Lysa im-plementata per il compilatore che genera modelli ChorGram. Il progetto del compilatore è introdotto nella sezione 2.8.
Il compilatore richiede due file in ingresso. Il primo per la descrizione del modello nel linguaggio IoT-Lysa con estensione .lysa. Il secondo è un file di configurazione con estensione .comp che contiene le regole per impostare il range delle communicazione dei nodi.
2.5.1
Le signature.
In un programma IoT-Lysa è riconoscibile una sezione iniziale per specificare le signature utilizzabili nella modellazione del sistema. Le dichiarazioni delle signature si vanno ad aggiungere a quelle predefinite del linguaggio per formare ciò che viene indicato come l’ambiente del programma. Le signature possono introdurre 3 possibili entità nel sistema:
• un tipo di valore. Ad esempio si può dichiarare un tipo image_t per dellare un’immagine. I tipi predefiniti del linguaggio sono number per mo-dellare sia i numeri interi che in virgola mobile, il tipo bool per momo-dellare i valori booleani e il tipo void per indicare nessun tipo.
• una funzione di aggregazione. Una funzione di aggregazione è utilizzata per rappresentare un nuovo valore, ed è specificata da un nome, una lista finita dei tipi dei parametri formali e il tipo del valore restituito. Sono predefinite funzioni classiche come gli operatori aritmetici e booleani. Ad esempio è presente la somma con il simbolo + di due valori number o la negazione di un valore bool con l’operatore not.
• un tipo di attuatore. Un tipo di attuatore è caratterizzato da un nome e da un insieme di azioni distinte. Non ci sono attuatori predefiniti nel linguaggio.
Al momento, il linguaggio non permette di definire tipi strutturati. I tipi so-no usati principalmente per aumentare la leggibilità del modello e per cercare di limitare errori di modellazione. Analogamente le funzioni non necessitano implementazioni perché sono utilizzate solo per esprimere nuovi valori a dispo-sizione. Un caso particolare sono le funzioni che non ricevono argomenti, che sono intese dal linguaggio come valori costanti. Esso è l’unico modo per definire nuovi valori appartenenti ad un tipo. I valori costanti hanno anche un ruolo particolare nell’identificazione dei messaggi.
Non è permesso dichiarare funzioni poliforme, ovvero multiple funzioni omo-nime con liste di parametri diverse o tipi restituiti. L’unica eccezione è l’ope-ratore predefinito = per testare l’uguaglianza di due valori. Nell’ambiente è
Listing 2.1: Esempio di signature in IoT-Lysa. 1 type image_t
2 type song_t
3 func f i n d S o n g ( image_t ) : song_t 4 func w a l l p a p e r : image_t
5 actuator_type s p e a k e r _ t { s t o p , pause , p l a y }
Listing 2.2: Esempio di dichiarazione di un sensore e attuatore in IoT-Lysa. 1 node PSpeaker =
2 sensor Scamera : image_t = rec h . t a u ; p r o b e ; h 3 actuator A s p e a k e r : s p e a k e r _ t = rec h . 4 t a u ; 5 w a i t _ f o r ( s t o p , p l a y ) ; 6 h 7 process = . . . 8 9 node . . .
presente una dichiarazione dell’operatore per confrontare coppie di ogni tipo a disposizione nell’ambiente.
Nel listato 2.1 sono esemplificate alcune signature. Le prime due dichiarano i tipi di valori image_t e song_t come suggeriscono i nomi per delle immagini e tracce audio. La terza mette a disposizione una funzione findSong che richiede un’immagine come parametro e restituisce una traccia. È dichiarato un valore costante immagine wallpaper (equivalentemente si può anche dichiarare una funzione con una lista vuota di argomenti). L’ultima riga introduce un tipo di attuatore di nome speaker_t capace di intraprendere le azioni stop, pause e play.
Anche se non sono definite le strutture dei tipi, sono disponibili dei valori per i tipi image_t e song_t. Infatti, con wallpaper denotiamo una costante immagine e con findSong(wallpaper) rappresentiamo un valore di tipo song_t. Per i tipi predefiniti, tutti i numeri interi e in virgola mobile sono riconosciute dal compilatore come costanti predefinite di number (come le costanti -1, 42 o 3.14); mentre le costanti false e true hanno tipo bool. Non c’è nessuna costante predefinita per il tipo void.
2.5.2
I nodi.
Ogni nodo possiede un identificatore id unico (detto anche etichetta del no-do) scelto dal progettista. Gli id saranno utilizzati per indicare i destinatari nelle comunicazioni. Il nodo è definito da una lista di definizioni di sensori, attuatori e processi controllori. L’ordine dei componenti non è rilevante, ad esempio un processo può utilizzare un sensore che è dichiarato dopo il processo nel programma.
2.5.3
Sensori e attuatori.
La dichiarazione di un sensore è formata da due parti. La prima introduce una variabile associata al sensore, e la seconda il comportamento del sensore (detto anche corpo). La variabile sarà aggiunta nella memoria condivisa del nodo, ma ai processi è permesso utilizzare la variabile solo in lettura. Il tipo associato modella il tipo dei valori che vengono rilevati. Il corpo di un sensore può essere definito ricorsivamente, attraverso l’uso dei costruttirech.ehrispettivamente per la definizione ricorsiva è l’uso della variabile di ricorsione (dove h indica un qualunque nome di variabile). I nomi delle variabili di ricorsione sono locali al sensore, ma non devono collidere con i nomi delle variabili dei sensori o attua-tori, cioè possono essere riutilizzate in altri componenti anche con scopi diversi. Sono presenti operazioni interne modellate con l’operazione tau e rilevazioni dall’ambiente con probe. Il comando probe astrae le operazioni di rilevamento dall’ambiente del sensore. L’astrazione è molto forte al punto che il valore ri-levato è implicitamente accedibile nella memoria condivisa con la variabile che introduce il sensore.
Anche gli attuatori introducono una variabile in memoria con associato un tipo di attuatore. La variabile può essere utilizzata dai processi per denotare l’attuatore su cui compiere un’azione. Essa non è utilizzabile in espressioni o de-stinazioni di assegnamenti. I comandi per gli attuatori sono gli stessi dei sensori ma invece di catturare rilevazioni possono rimanere in attesa di intraprendere un’azione tra quelle indicate con il comando wait_for(azione_1, ..., azione_t). Le azioni indicate devono appartenenere alle azioni per il tipo dell’attuatore.
Nel listato 2.2 si riporta un esempio di dichiarazione di un sensore e attua-tore utilizzando le signature definite precedentemente. Il listato inizia con la dichiarazione di un nodo identificato con PSpeaker. Il nodo ha 3 componenti: un sensore, un attuatore e un processo controllore (al momento omesso). Il sen-sore rileva dall’ambiente un’immagine e che è disposibile nella variabileScamera. Esso continuamente compie un’azione interna e effettua rilevazioni. L’attuato-re è associato alla variabile Aspeaker di tipo speaker_t. Il corpo dell’attuatore ricorsivamente compie un’azione interna e rimane in attesa della richiesta di un’azione trastop oplay.
2.5.4
I processi.
Nel listato 2.3 è mostrata la struttura tipica di un processo. Il costruttorech.
introduce una definizione ricorsiva del processo dovehè la variabile nella memo-ria per denotare la ricorsione. I comandi nil etaurappresentano le operazioni standard per modellare rispettivamente l’operazione nulla e l’operazione interna. Il comando nil può essere usato come alternativa alla variabile di ricorsione per terminare la definizione di un processo. Il comando@Aspeaker.play è una nota-zione specifica per richiedere all’attuatore assegnato aAspeakerdi intraprendere l’azione play. L’azione deve essere una azione valida per il tipo dell’attuatore presente nell’ambiente.
Listing 2.3: Esempio di dichiarazione di un processo in IoT-Lysa. 1 process = 2 rec h . 3 switch{ 4 r e c v ( w a l l p a p e r ; that_song ) ; 5 c o v e r := f i n d S o n g ( w a l l p a p e r ) ; 6 i f c o v e r = that_song then 7 @Aspeaker . p l a y ; 8 snd ( w a l l p a p e r , t r u e ) to [ C l i e n t ] ; 9 h 10 e l s e 11 snd ( w a l l p a p e r , f a l s e ) to [ C l i e n t ] 12 h 13 | 14 r e c e i v e ( 0 ; x ) ; 15 t a u ; 16 @Aspeaker . s t o p ; 17 n i l
Il costrutto switch definisce più rami di esecuzione possibile. I rami sono supposti essere mutualmente esclusivi e la semantica prevede che il processo rimanga bloccato in attesa finchè l’esecuzione non possa continuare per uno dei rami. Tipicamente le condizioni sono delle ricezioni sul canale con pattern mat-ching che devono avere successo. Esiste anche il classico comando condizionale
if−then−else la cui espressione di guardia deve essere valutata nel tipo bool predefinito dal linguaggio.
Il comando recv(c ; var1, ... , varM) permette di selezionare dei messaggi etichettati ovvero il cui primo campo corrisponde alla costante indicatac. L’eti-chetta è singola e deve essere un valore costante dichiarato nell’ambiente. Dopo il simbolo “;” a ogni variabile è assegnato un campo del messaggio con il vincolo che deve essere indicata almeno una variabile. Esiste anche una receive più ge-nerale con la sintassi receive (exp1, ..., expN; var1, ..., varM )la cui semantica è accettare messaggi i cui i primi N campi corrispondono con le valutazioni delle N espressioni e i rimanenti campi sono assegnati alle variabili. Per le espressioni sono accettate anche funzioni di aggregazione i cui argomenti devono rispettare la firma della signatura. Il comando receive è una forma più generale direcv, ma quest’ultimo mette maggiore enfasi sul significato del messaggio e aiuta l’espressività.
Per l’invio dei messaggi esiste la controparte delle due forme di ricezione vi-ste. Per l’invio etichettato la sintassi èsnd(c, expr1, ..., exprN)to[Dest1, ..., DestN]
dove un messaggio composto dall’etichetta c e N campi formati dalle valutazioni delle espressioni, è inviato ai destinatari che devono essere nodi esistenti nel si-stema. Per la semantica, in realtà la lista degli effettivi destinatari sarà ristretta ai nodi che le regole di prossimità consentono. Il comando di invio più generale è invecesend(expr1, ..., exprN)to[Dest1, ..., DestN]con una semantica analoga. Il comando assegnamentocover := findSong(wallpaper);valuta l’espressione e
assegna il valore risultante alla variabile cover nella memoria condivisa. I tipi della variabile e dell’espressione devono corrispondere, e se la variabile è alla sua prima apparizione allora l’assegnamento crea anche il binding in memoria. Non si può utilizzare la variabile in una espressione se prima non è stata inizializzata nel processo o in uno dei processi precedenti.
La memoria condivisa richiede un accorgimento da parte del modellatore di usare le variabili in maniera consistente. Ad esempio non è lecito usare una variabile in un processo per valori numerici e in un altro processo per valori booleani. Un altro classico errore è utilizzare una variabile per la ricorsione in un processo e con uno scopo diverso in un altro processo dello stesso nodo. Il type-system tra i vari errori da verificare ha proprio l’uso consistente delle variabili.
È possibile avere delle variabili con un tipo variabile nel programma. Ad esempio nel listato 2.3 alla riga 5 è presente un assegnamento alla variabile cover. La variabile è alla prima apparizione e il tipo è inferito dall’espressione assegnata individuabile come il tipo song_t dalla firma della funzione findSong. Diverso è il caso alla riga 14 per la variabile x. Non è possibile inferire staticamente il tipo del valore che sarà assegnato poichè non ci sono strutture ai messaggi. La variabile non è usata ulteriormente nel programma e quindi il tipo della variabile può essere qualunque. Se ad esempio in seguito nel nodo fosse coinvolta in una somma, allora si potrebbe inferire che la variabile sia numerica poichè l’unica dichiarazione della somma nell’ambiente è per valori numerici. Il type-system si occupa anche di cercare di inferire i tipi alle variabili.
2.5.5
Specifica del range delle comunicazioni.
Il file presenta una riga per ogni comunicazione abilitata tra due nodi. La sintassi di una regola è:
Mitt − Dest,
doveMitt eDestsono due id di nodi.
Essa dichiara che il nodo Mitt può comunicare con il nodo Dest. La comu-nicazione non è abilitata in entrambe le direzioni a meno che non ci sia anche la regola opposta nel file: Dest − Mitt. Questo modella la situazione reale dei sistemi IoT dove la comunicazione tra due oggetti è possibile sia in una sola direzione, per una differenza di distanza massima di trasmissione.
Un esempio di file con più regole è il listato 2.6 a pagina 26 dove tutti i nodi del sistema sono raggiungibili poichè è ipotizzato che gli oggetti siano ravvicinati in una stanza o appartamento.
Listing 2.4: Implementazione signature e condizionatore del sistema. 1 type c o n d _ a c t i o n 2 3 func t u r n e d o n : c o n d _ a c t i o n 4 func t u r n e d o f f : c o n d _ a c t i o n 5 6 func q u i t : number 7 func temp : number 8 func ack : number 9 10 func t h r e s h o l d : number 11 func b t h r e s h o l d : number 12 13 actuator_type s w i t c h _ t { t u r n o f f , t u r n o n } 14 15 node Cond = 16 actuator ACond : s w i t c h _ t = 17 rec h . t a u ; w a i t _ f o r ( turnon , t u r n o f f ) ; h 18 19 process = 20 rec h .switch { 21 r e c v ( temp ; x ) ; 22 i f t h r e s h o l d < x then 23 @ACond . t u r n o n ; 24 snd ( ack , t u r n e d o n ) to [ Th1 ] ; 25 h 26 e l s e 27 @ACond . t u r n o f f ; 28 snd ( ack , t u r n e d o f f ) to [ Th1 ] ; 29 h 30 | 31 r e c v ( q u i t ; i ) ; 32 n i l 33 }
2.6
Implementazione del sistema condizionatore.
Le signature del sistema del condizionatore sono mostrate nel listato 2.4. Il tipo action rappresenta azioni che il condizionatore conferma di aver intrapreso al termometro e turnedon e turnedoff sono due azioni possibili. Le signature dalle linee 6–8 sono costanti usate come etichette per i messaggi: sono dichia-rate le soglie per modellare la temperatura desiderata, e il livello di batteria di sicurezza a cui spegnersi autonomamente. Infine è presente l’attuatoreswitch_t
con due azioni possibili turnoff e turnon.
Il listato continua con la modellazione del condizionatore. Il nodo Cond de-nota con ACond l’attuatore per agire sul condizionatore nella stanza. Il processo controllore inizia rimanendo in attesa sul comando switch. Alla riga 21 procede se riceve una nuova rilevazione della temperatura. Il messaggio è riconosciuto dall’etichetta temp e nella variabile x è depositato la temperatura ricevuta. La temperatura viene confrontata con una soglia threshold che modella la tem-peratura massima desiderata. Se la soglia è superata chiede all’attuatore di accendere il condizionatore (riga 23) per poter raffreddare l’ambiente, altrimen-ti chiede l’azione per spegnere il condizionatore (riga 27). Inoltre alle righe 10 e 14 invia al termometro le notifiche dell’azione intrapresa con i valori costanti turnedon o turnedoff per indicare rispettivamente che il condizionatore è stato accesso o spento. Dopo la notifica, il processo ritorna ad attendere sulle scelte dello switch. Se invece il processo riceve un messaggio con etichetta quit (riga 17) allora termina la ricorsione con il comando nil.
L’implementazione dei termometri è invece data nel listato 2.5. Entrambi i termometri sono dotati di un sensore STemp per rilevare la temperatura della stanza. Il termometro Th1possiede anche il sensore SBattery per il livello della
batteria. Entrambe le rilevazioni sono modellate con valori numerici. Il primo processo di Th1 si occupa della rilevazione e condivisione della temperatura
media. Il calcolo della temperatura media della stanza è modellata alla riga 9. In particolare con l’espressione mt+STemp si aggregano insieme per mezzo dell’operatore somma l’ultima media calcolata e la rilevazione del sensore. Ogni 10 iterazioni (linee 11–13) il processo comunica la nuova media sia al condizio-natore che al termometro e rimane in attesa di un messaggio di conferma dal condizionatore etichettato con l’etichetta ack. Il secondo processo invece rimane in attesa di messaggi etichettati con temp per conoscere le nuove rilevazioni. La temperatura viene salvata in mt e così resa disponibile anche al primo proces-so. Il termometro Th2ha solo un processo con la funzionalità di condividere la
temperatura della stanza.
La specifica della topologia è mostrata nel listato 2.6. Poichè il sistema è ipotizzato in un ambiente ristretto come una stanza o un paio di stanze la topologia proposta prevede che tutti i nodi del sistema siano ad una distanza tale da poter comunicare.
Listing 2.5: Implementazione dei termometri del sistema condizionatore. 1 node Th1 =
2 sensor STemp : number = rec h . t a u ; p r o b e ; h 3 sensor S B a t t e r y : number = rec h . t a u ; p r o b e ; h 4 5 process = 6 mt := 0 ; 7 i := 0 ; 8 rec h .i f b t h r e s h o l d < S B a t t e r y then 9 tp := mt+STemp ; mt := tp / 2 ; i := i +1; 10 i f i = 10 then 11 snd ( temp , mt ) to [ Cond , Th2 ] ; 12 r e c v ( ack ; j ) ; 13 i := 0 ; h 14 e l s e 15 snd ( temp , mt ) to [ Th2 ] ; h 16 e l s e 17 snd ( q u i t , 0 ) to [ Cond ] ; h 18 19 process = 20 rec h . r e c v ( temp ; s ) ; mt := s ; h 21 22 node Th2 =
23 sensor STemp : number = rec h . t a u ; p r o b e ; h 24 25 process = 26 mt := 0 ; 27 rec h . snd ( temp , mt ) to [ Th1 ] ; 28 r e c v ( temp ; x ) ; 29 tp := x+STemp ; mt := tp / 2 ; 30 h
Listing 2.6: Specifica della topologia per il sistema condizionatore. 1 Cond − Th1 2 Cond − Th2 3 Th1 − Cond 4 Th1 − Th2 5 Th2 − Cond 6 Th2 − Th1
2.7
CFA: Control Flow Analysis.
La CFA presentata per IoT-Lysa riprende il lavoro fatto per LySa [18]. Sono reperibili in [11] maggiori approfondimenti come ad esempio le regole per la specifica dell’analisi.
L’analisi fornisce una sovra-approssimazione sicura del comportamento del sistema. Lo scopo è tenere traccia di come i dati ( in particolare i più sensibili dei sensori) vengono diffusi attraverso i nodi del sistema e le manipolazioni su di esse rappresentate dalle funzioni di aggregazione che ne fanno uso.
I valori del sistema sono rappresentati dagli alberi sintattici dei termini stessi, come descritto nel listato 2.4. Le foglie rappresentano o dati rilevati dai sensori o valori costanti. I nodi interni sono rappresentati dalle funzioni di aggregazione e ogni i-esimo figlio corrisponde all’i-esimo argomento.
Siccome i sistemi IoT sono specificati per essere attivi continuamente è possi-bile avere dei cicli che portano ad alberi con profondità non limitata. Nell’analisi per garantire una rappresentazione finita i valori astratti vengono rappresentati con grammatiche regolari per alberi [34]. Una grammatica regolare per alberi è una quadrupla ˆG =< N, T, Z, R > dove:
• N è un insieme di non-terminali.
• T è un alfabeto di simboli terminali etichettati con propria arità. • Z ∈ N è il non-terminale iniziale.
• R è l’insieme delle produzioni della forma A → t, dove t è un albero composto dai simboli dall’unione NS
T in rispetto della loro arità.
Dato un sistema di nodi possiamo costruire una grammatica per alberi regolari che definisce i valori astratti dell’analisi. L’alfabeto T sarà costituito dai simboli etichettati:
• il (di arità 0), per ogni sensore indicizzato con i ∈ I l
• vl (di arità 0), per ogni valore costante e l ∈ L
• fl (di arità r), per ogni funzione f in F con r argomenti e l ∈ L
L’insieme N dei non-terminali include un simbolo per ogni terminale che produce solo quel termine:
• Per ogni il∈ T è presente Il∈ N e una produzione Il→ il∈ R.
• Per ogni vl∈ T è presente Vl∈ N e una produzione Vl→ vl∈ R.
• Per ogni fl∈ T è presente Fl∈ N e una produzione Fl→ fl(t
1, . . . , tr) ∈ R
fl0 il0 hl1
il1 fl0 il0 hl1
il1 · · ·
Figura 2.8: Un albero astratto infinito.
Nel momento in cui sia fissato il sistema è utile abbreviare con ˆv = (Z, R) per indicare la grammatica ˆG =< N, T, Z, R > senza indicare gli insiemi dei non-terminali e terminali.
Riprendendo l’esempio del sistema del condizionatore presentato nella sezio-ne 2.4 i valori astratti rilevati dei sensori dei due termometri sono rappresentati come:
(sensore temperatura di Th1) = (ST empTh1, {ST empTh1 → 1Th1})
(sensore batteria di Th1) = (SBatteryTh1, {SBatteryTh1 → 2Th1})
(sensore temperatura di Th2) = (ST empTh2, {ST empTh2 → 1Th2})
dove in questo caso i nomi ST empTh1, SBatteryTh1,ST empTh2indicano le categorie
sintattiche per generare gli indirizzi 1Th1, 2Th1 e 1Th2 riservati in memoria ai sensori.
Come esempio più significativo di rappresentazione di alberi non limitati è utile l’esempio utilizzato in [11]. Supponiamo di avere un sistema con due nodi Nl0 e Nl1 e due funzioni di aggregazione f e he che il nodo Nl0 applichi f ad un dato del sensore e a un valore ricevuto da Nl1 e che il nodo Nl1 si comporti nella stessa maniera ma che aggreghi con la funzione h. Infine supponiamo che il sistema possa ripetere in maniera indefinita questi scambi di messaggi. Allora la valutazione è un albero binario infinito come in figura 2.8 in cui nelle foglie risiedono i sensori dei due nodi e nei nodi interni si alternano le due funzioni. Il valore astratto che rappresenta tutti i possibili valori è dunque la seguente grammatica: (Fl0, {Fl0 → fl0(Il0 0, Hl1), I l0 0 → il0, Hl1 → hl1(I l1 1 , Fl0), I l1 1 → il1}) .
Fissato un sistema di nodi l’insieme dei termini astratti può essere introdotto come l’insieme ˆV = 2N×R, ossia un sottoinsieme delle grammatiche possibili.
Allora il risultato della CFA di un programma è inteso da una tripla ( ˆΣ, κ, Θ) tale che:
• ˆΣ =S
l∈LΣˆl: XS Il→ 2 ˆ
V, dove ogni memoria astratta locale ˆΣ
l
• κ : L → L ×Sk
i=1Vˆ
i, (dove con ˆVi indichiamo il prodotto cartesiano di
arità i, e con k l’arità maggiore tra tutti i messaggi inviati sul canale) per una approssimazione dei messaggi e mittenti ricevuti sul canale per ogni nodo.
• Θ : L → 2Vˆ, è una funzione che fornisce una approsimazione dei valori che
ogni nodo usa e aggrega insieme.
L’analisi per la sua natura statica fornisce una sovra-approssimazione sicura dei valori ottenibili cioè potrebbe individuare casistiche che in realtà non si presenterebbero mai in esecuzione. L’analisi può aiutare in fase di progettazione del sistema per individuare subito alcuni errori di progettazione, o le questioni più critiche del sistema. Osservando la tripla ( ˆΣ, κ, Θ), risultato della CFA come formalizzato precedentemente è possibile indagare proprietà del tipo seguente:
• individuare la ridondanza di messaggi;
• tenere traccia dei nodi raggiunti da dati (ad esempio i dati dei sensori) e verificare che nessun nodo sia indesiderato;
• similmente al punto precedente, tenere traccia di come vengono aggregati i dati;
• osservare di quali valori è funzione una variabile.
Riprendendo il modello della sezione 2.4, nel codice di PTh2 era presente un errore nel modellare l’aggiornamento della variabile mt. Infatti, la sovra-prossimazione per la variabile mt che si otterrebbe è:
ˆ ΣTh2(mt) ⊆ (DivTh2, {DivTh2 → /Th2(ITh2 1 , T woTh2), I Th2 1 → 1Th2, T woTh2 → 2Th2}),
dove non bisogna confondere le due costanti intere le quali indicano oggetti differenti: la costante 1 indica la locazione 1 riservata al sensore in memoria invece la costante 2 indica esattamente il valore costante numerico 2.
Osservando le etichette dei valori astratti è possibile scoprire un errore: la media è in funzione esclusivamente di dati del nodo Th2 stesso.
2.8
ChorGram: un tool di supporto per IoT-Lysa.
Uno dei vantaggi di possedere un modello è trasformarlo in un altro modello dove sono disponibili strumenti per analisi e verifiche diverse. In tal senso, un esempio di analisi per IoT-Lysa è proprio il progetto del compilatore open-source per IoT-Lysa [13, 10], dove questo lavoro di tesi intende inserirsi. Il progetto consiste in un compilatore per il linguaggio IoT-Lysa per generare modelli per
CFSMs [16] che descrivono la comunicazione tra i nodi di un sistema. A loro volta i modelli CFSMs sono interpretabili con il tool di ChorGram [14, 15] per validare le comunicazioni del sistema. Il type-system a cui è dedicato questo lavoro di tesi è un modulo che è destinato ad integrarsi con il compilatore.
Il CFSM è un modello per analisi delle comunicazioni composto da macchine a stati finiti, in cui gli archi sono etichettati con azioni di send o receive su canali bidirezionali, asincroni, con buffer di capienza illimitata. Ad esempio un etichetta di un arco può essere AB!“foo” indicando che il nodo A invia un messaggio “foo” al nodo B. In particolare il sistema può essere osservato a due livelli: un livello locale e un livello globale. Il livello locale descrive un singolo nodo con una macchina a stati finiti. Il livello globale è un grafo il quale considera l’avanzamento delle singole macchine in parallelo e lo stato dei buffer di tutte le comunicazioni.
Le analisi consistono in una ricerca di stati non desiderati nel grafo. Ad esempio uno stati di deadlock, cioè stati da cui nessuna macchina può avan-zare ulteriormente. Oppure rilevazioni di casi di message-oblivion, in cui un messaggio depositato in un buffer non è mai preso in consegna.
L’analisi per IoT-Lysa consiste dunque di tre fasi:
1. descrizione del sistema in programma IoT-Lysa;
2. compilazione del sorgente IoT-Lysa in un modello CFSMs per mezzo del compilatore [13];
3. utilizzo dello stumento ChorGram [15] per la verifica di stati di deadlock o casi di message-oblivion.
Capitolo 3
Il type-system.
Lo scopo principale di un type-checker è individuare a tempo di compilazione possibili esecuzioni che causerebbero un errore. Esso è uno strumento impre-scindibile per il supporto di un linguaggio senza quale il processo di sviluppo sarebbe molto frustrante anche per programmi giocattolo. Il type-checker fa in modo di associare un tipo a ogni oggetto definito (ad esempio una variabi-le, una funzione o un’espressione), e ottenere che tutti gli oggetti siano usati correttamente in accordo con i tipi assegnati. Ad esempio che una funzione sia utilizzata rispettando la firma dichiarata. Spesso verifica anche errori che non coinvolgono strettamente tipi, come collissioni di nomi o uso di nomi non dichiarati. La tipologia degli errori che può individuare dipende dal linguaggio. Approfondimenti sono reperibili in [33].
Durante una fase di compilazione (in questo caso il testo di riferimento de facto è [32]), il codice sorgente che supera il parsing dell’analizzatore sintattico del linguaggio viene trasformato nell’albero della sintassi astratta, il quale deve essere validato attraverso il type-checker. Se la validazione ha successo, allora il codice può passare alle fasi successive di back-end.
Nel repository di IoT-Lysa [13] introdotto nella sezione 2.8 è presente il com-pilatore che genera modelli ChorGram delle comunicazioni di modelli IoT-Lysa. Il type-system oggetto di questa tesi si inserisce nel front-end del compilatore a seguito della fase di parsing supportando i modellatori con il linguaggio.
Questo capitolo presenta la specifica logica del type-system di IoT-Lysa e invece l’implementazione del type-checker che ne deriva è presentato nel capito-lo 4. Sono introdotti i formalismi utilizzati, descritti più ampiamente in [31, 33]. Il type-system viene rappresentato come un sistema di deduzione logica indipen-dente da qualunque algoritmo o linguaggio di programmazione. Astrarre dagli aspetti implementativi aiuta nel focalizzarsi sulle specifiche. Rende più facile fare delle modifiche e sopratutto delle dimostrazioni sul sistema.
3.1
Alcuni formalismi.
Il type-system ha l’obbiettivo di dimostrare la validità di enunciati (in lette-rattura inglese “judgment”) che rappresentano relazioni tra insiemi di interesse. Nel caso del type-system si intende validare costrutti sintattici (esempio termini, espressioni, ecc.) insieme a valori del dominio semantico per associarli tra loro. Ad esempio, enunciati per espressioni sono relazioni della forma:
` ⊆ TEnv ∗ Expr ∗ (IntS Bool) ,
dove TEnv è l’insieme degli ambienti di tipo, Expr la categoria sintattica delle espressioni e Int e Bool l’insieme dei valori di tipo interi e booleani rispettiva-mente. Un’istanza possibile di un enunciato potrebbe essere
[int/x] ` x + 1 : int ,
per rappresentare che nell’ambiente di tipo in cui x è una variabile intera, x + 1 è un’espressione intera. Diversamente non sarebbe valido l’enunciato
[bool/x] 6` x + 1 : int ,
ipotizzando che interi e booleani non si possano sommare.
Gli enunciati si dimostrano attraverso delle deduzioni che usano degli insieme di regole. Una regola è composta da due parti: un insieme finito di premesse e l’enunciato da dimostrare detto conclusione. La regola afferma che se sono valide tutte le premesse, allora vale la conclusione. Le premesse possono eventualmente essere un insieme vuoto e in tal caso la regola è si definisce un assioma. La rappresentazione grafica di una regola è la seguente:
[name] prem1· · · premn conclusione .
Le regole del sistema di tipo esemplificato per le espressioni sono:
(Int):
Γ ` n : int (Bool): Γ ` true | false : bool
(var): Γ(x) : t
Γ ` x : t (sum):
Γ ` e1: int Γ ` e2: int
Γ ` e1+ e2: int
.
I due assioni dimostrano le costanti intere e booleane con il tipo opportuno. La regola var afferma che l’espressione formata da una variabile possiede un tipo solo se la variabile è definita nell’ambiente di tipo in cui è valutata. La regola sum riconosce che una somma restituisce un valore di tipo intero se le due sotto-espressioni sono a loro volta espressioni intere.
Per dimostrare la veridicità di un enunciato è necessario poter costruire una dimostrazione che ne sia conclusione. Ad esempio, l’enunciato per l’espressione x + 1 è dimostrabile per l’esistenza della seguente istanza valida delle regole:
[int/x](x) = int
[int/x] ` x : int [int/x] ` 1 : int
[int/x] ` x + 1 : int .
Il type-checker implementa l’algoritmo di ricerca di esistenza di una dimostra-zione per ogni costrutto sintattico del programma.
3.2
La sintassi astratta utilizzata.
La grammatica da validare nelle regole è mostrata nel listing 3.1, scritto con codice F# [25]. Il type-system del linguaggio F# si rivela ideale per modellare la struttura ad albero tipica delle grammatiche libere dal contesto. Lo stesso compilatore di IoT-Lysa [13] usa la medesima grammatica per definire la sintassi astratta. Ad ogni categoria sintattica del linguaggio è associato un tipo e ad ogni produzione una possibile definizione riconoscibile con un costruttore del type-system di F#.
Ad esempio, il tipo SigDelaration modella la categoria sintattica per le signature, e sono presenti tre possibili produzioni:
• TypeDecl, per l’albero astratto di una dichiarazione di un tipo con un unico figlio per il nome.
• FuncDecl, per l’albero astratto di una dichiarazione di una funzione con 3 figli: il nome della funzione, una lista dei tipi come argomenti e il tipo restituito.
• ActuatorDecl, per l’albero astratto di una dichiarazione di un attuatore con 2 figli: il nome della funzione e la lista delle azioni che può intraprendere.
Il tipo Symbol utilizzato per rappresentare la frontiera degli alberi sintattici è un riferimento alla symbol table creata e inizializzata durante la fase di ana-lisi sintattica. Il type-system è syntax-directed, ovvero le regole rispecchiano la struttura della grammatica definendo una regola per ogni produzione della grammatica.
3.3
I domini semantici.
Listing 3.1: Specifica in F# della sintassi astratta di IoT-Lysa. 1 type S i g D e l a r a t i o n =
2 | TypeDecl o f Symbol
3 | FuncDecl o f Symbol ∗ Symbol l i s t ∗ Symbol 4 | A c t u a t o r D e c l o f Symbol ∗ Symbol l i s t 5 6 type S e n s o r P a r s e T r e e = 7 | STau o f S e n s o r P a r s e T r e e 8 | SProbe o f S e n s o r P a r s e T r e e 9 | SRec o f Symbol ∗ S e n s o r P a r s e T r e e 10 | SId o f Symbol 11 | S N i l 12 13 type A c t u a t o r P a r s e T r e e = 14 | ATau o f A c t u a t o r P a r s e T r e e 15 | AId o f Symbol 16 | AWaitFor o f Symbol l i s t ∗ A c t u a t o r P a r s e T r e e 17 | ARec o f Symbol ∗ A c t u a t o r P a r s e T r e e 18 | ANil 19
20 type E x p r e s s i o n = App o f Symbol ∗ ( E x p r e s s i o n l i s t ) 21 22 type P r o c e s s P a r s e T r e e = 23 | PNil 24 | PTau o f P r o c e s s P a r s e T r e e 25 | PAssign o f Symbol ∗ E x p r e s s i o n ∗ P r o c e s s P a r s e T r e e 26 | PRec o f Symbol ∗ P r o c e s s P a r s e T r e e 27 | PId o f Symbol 28 | PSwitch o f P r o c e s s P a r s e T r e e l i s t 29 | PCmd o f Symbol ∗ Symbol ∗ P r o c e s s P a r s e T r e e 30 | PSend o f E x p r e s s i o n l i s t ∗ Symbol l i s t ∗ P r o c e s s P a r s e T r e e 31 | PSnd o f Symbol ∗ E x p r e s s i o n l i s t ∗ Symbol l i s t ∗ P r o c e s s P a r s e T r e e 32 | PCond o f E x p r e s s i o n ∗ P r o c e s s P a r s e T r e e ∗ P r o c e s s P a r s e T r e e 33 | P R e c e i v e o f E x p r e s s i o n l i s t ∗ Symbol l i s t ∗ P r o c e s s P a r s e T r e e 34 | PRecv o f Symbol ∗ Symbol l i s t ∗ P r o c e s s P a r s e T r e e
35 36
37 type NodeBody =
38 | SDecl o f Symbol ∗ Symbol ∗ S e n s o r P a r s e T r e e 39 | ADecl o f Symbol ∗ Symbol ∗ A c t u a t o r P a r s e T r e e 40 | PDecl o f P r o c e s s P a r s e T r e e
41
42 type NodeDecl = NDecl o f Symbol ∗ NodeBody l i s t
Listing 3.2: Implementazione del dominio di tipi del type-system. 1 type Type = Type o f s t r i n g ; ;
2 type Func = Func o f s t r i n g ∗ Type l i s t ∗ Type ; ; 3 type A c t u a t o r = A c t u a t o r o f s t r i n g ∗ Set<s t r i n g > ; ; 4 type S e n s o r = S e n s o r o f Type ; ;
Type: ogni valore di Type astrae tutti i valori ottenibili durante l’esecuzio-ne del tipo che denota. Esempi di valori di tipo sono Type(number), Type(bool), o Type(image_t) per astrarre rispettivamente tutti i valori numerici, booleani o immagini.
Func: modella le funzioni di aggregazione. Un esempio di valore di funzione è Func(resizeImage, [image], image) dove image = Type(image_t) per una funzione di ridimensionamento di una immagine. Un esempio di valore costante è Func(wallpaper, [ ], image) che modella una costante di nome wallpaper di tipo image_t.
Actuator: modella un tipo di attuatore. Ad esempio un attuatore che può agire sulla potenza di un dispositivo è Actuator(pwr, set [turnoff, turnon]). Sensor: un suo valore astrae il comportamento di un sensore capace di rilevare
dall’ambiente valori del tipo che incapsula.
In seguito i valori v1, v2 appartenent al dominio semantico rappresentano il
medesimo tipo se, e solo se, indicano il medesimo valore immutabile secondo il type-checker di F# espresso con la notazione v1= v2. Ad esempio, supponendo
che valga imm = Type(image_t) allora valgono le seguenti affermazioni:
imm = Type(image_t) imm 6= Type(number)
Func(resizeImage, [imm], imm) = Func(resizeImage, [imm], imm) Func(resizeImage, [imm], imm) 6= Func(resizeImage, [ ], imm)
Sensor(imm) = Sensor(Type(image_t)) Sensor(imm) 6= Sensor(Type(number))
imm 6= Sensor(Type(image_t))
Actuator(pwr, set[turnoff, turnon]) = Actuator(pwr, set[turnon, turnoff])
Nel seguito per non appensantire i formalismi delle regole le stringhe non saran-no rappresentate nella forma classica "text" ma semplicemente con text. Nelle regole sarà chiaro dal contesto quando un nome denota una variabile o una strin-ga se non diversamente indicato. Ad esempio sarà scritto Type(number) invece che Type("number"), sfruttando la specifica del costruttore Type che richiede una stringa come argomento.
3.4
L’ambiente e la memoria di tipo.
Un ambiente di tipo (da ora in avanti anche indicato semplicemente ambiente) è una astrazione che colleziona le dichiarazioni delle signature a disposizione. Tale collezione è statica durante l’analisi dei nodi, cioè determinabile a tempo di compilazione e comprende sia le signature predefinite che tutte quelle di-chiarate dal progettista. Le signature nel programma devono essere validate dal
