Home » Laurea Magistrale » Archivio Tesi

Laurea Magistrale

Jump second level menu

Thesis

July 2017

Propagazione rapida di messaggi in scenario veicolare urbano - Marco Barichello - 1084564 - Relatore: Claudio Enrico Palazzi

Oggi sono in sviluppo un numero sempre maggiore di tecnologie per le automobili. Tali tecnologie potrebbero portare allo sviluppo di moltissime applicazioni di sicurezza e di intrattenimento. La presenza di scenari sempre più affollati, sempre più grandi e molto variabili rappresenta però una grossa difficoltà nello sviluppo di tali applicazioni. In particolare, la presenza di una grande quantità di mezzi porta alla necessità di inviare il minor numero possibile di messaggi, raggiungendo al tempo stesso il maggior numero possibile di mezzi. Si stanno dunque studiando nuove tecniche che possano essere efficaci ed al tempo stesso il più efficiente possibile. Una di queste consentirebbe di ottenere un buon risultato con un numero molto limitato di messaggi, il tutto dopo una fase iniziale nella quale ogni mezzo stimerà il proprio range trasmissivo. Si andrà quindi a studiare il comportamento di questa tecnica in un ambiente differente.

Architettura di un sistema di raccomandazione per il job searching. - Matteo Del Pioluogo - 1084106 - Relatore: Fabio Aiolli

Il progetto affrontato prevede la creazione di una piattaforma web denominata pySurvey. Il suo scopo è quello di creare un portale web per studenti e aziende. Gli studenti potranno cercare ed essere consigliati sulle offerte di lavoro. Le aziende avranno modo di trovare il candidato ideale per una certa posizione lavorativa. Il risultato finale sarà un sistema di raccomandazione per il mondodel lavoro. Il primo obbiettivo sarà quello di raccogliere dati, in modo da poter attingere a contenuti sui quali poter basare la raccomandazione. Il portale dovrà essere in grado di salvare le informazione sugli utenti (che siano di aziende o studenti), e permettere la modifica delle scelte effettuate. Infine l'applicativo web dovrà fornire una raccomandazione all'utente. Il documento di tesi prosegue con i requisiti del programma sviluppato, la scelta del linguaggio e dei vari strumenti software. Lo schema Entità Relazione e la sue evoluzioni per necessità nate da scoperte fatte sul campo. Successivamente verrà presentata la struttura del programma, il design pattern utilizzato e le funzioni principali. Poi verrà spiegato il problema Cold Start e verrà presentato un semplice algoritmo per affrontarlo. Verranno anche proposti futuri miglioramenti teorizzati durante il progetto, ma non ancora implementati.

Un'applicazione di supporto della terapia logopedia della disfonia - Nicola Favaro - 1085256 - Relatore: Ombretta Gaggi

La tecnologia pervade ormai da molti anni la quotidianità delle persone, mutandone i normali comportamenti e gli stili di vita. Sicuramente è cambiato il modo di comunicare e di rapportarsi con gli altri, il modo di lavorare, di reperire le informazioni, di acquistare beni e servizi e così via… Lo scopo di questa tesi è quello di apportare alcuni cambiamenti anche in ambito medico. Nel campo della logopedia esistono alcune terapie che prevedono lo svolgimento, autonomo, di determinati esercizi nell’arco della giornata. Spesso i pazienti non svolgono buona parte delle attività per dimenticanza e perché poco stimolati a farlo. 
L’obiettivo è quello di sfruttare lo smartphone come strumento di supporto alla terapia e allo stesso tempo di migliorarne i risultati sfruttando le regole della gamification.

Implementation and evaluation of a container-based software architecture - Alberto Simioni - 1106663 - Supervisor: Tullio Vardanega

Recent advances in fields such as Cloud Computing, Web Systems, Internet of Things and Distributed NoSQL DBMS are enabling the development of innovative enterprise information systems that significantly increase the productivity of end users and developers. The aim of this thesis is to explore the new opportunities that these new technologies are bringing to the enterprise world. The new opportunities are explored by investigating the scenario of a medium-sized worldwide-trading company, Fiorital S.p.A. The thesis presents the design of a software architecture for the future information system of the company. The architecture is based on the usage of the Container technology and of the Microservice architectural style. Containers have empowered the usage of Microservices architectures by being lightweight, providing fast start-up times, and having low overhead. Candidate technologies for the implementation of the proposed software architecture are singled out, and the selection rationale is presented. This thesis provides an evaluation of both the candidate architecture and the technologies through the implementation of a prototype and the application of synthetic workloads that mimic stressful use scenarios. The results show that, in spite of the relative immaturity of some of the candidate technologies, the information system's candidate architecture is appropriate and that a company like Fiorital would considerably benefit from it.

April 2017

Ravenscar-EDF: Comparative Benchmarking of an EDF Variant of the Ravenscar Runtime - Paolo Carletto - 622276 - Supervisor: Tullio Vardanega

Subsequent to the seminal work of Liu and Layland in 1973, researchers and practitioners alike discussed which online scheduling algorithm was to be preferred between EDF and FPS. In the past decades FPS collected much more approvals for two main reasons: it was easier to implement and then there were many algorithms developed to optimally manage protected resources. So Fixed Priority (FPS) is actually the most common algorithm used by the largest number of RTOS and Immediate Priority Ceiling Protocol (IPCP) is its counterpart dedicated to manage protected resources. Unfortunately there was not so far an easy way to manage protected objects under EDF scheduling: the only functional approach was Stack Resource Policy (SRP) proposed by Baker (1990), which had a more complex implementation than IPCP for priority based scheduling. But recently Alan Burns and Andy Wellings (2016) theorized a new protocol which is easier to implement than SRP and guarantees exactly the same behavior than IPCP: it is represented by Deadline Floor Protocol (DFP). Furthermore recent results published by Buttazzo (2005) sustained the superiority of EDF, already proven in theory, also from an implementation perspective. In this work, we aim at digging deeper into the roots of those results. To this end, we took the Ravenscar runtime based on GNAT-2012-LEON-ELF-BIN developed by AdaCore, which includes a lean, fast and efficient implementation of an FPS scheduler, combined with its IPCP locking policy companion, and produced a variant of it that implements EDF scheduling coupled with DFP locking. In this manner, we were able to transparently attach those two runtime variants to a vast suite of application benchmarks, which we used to perform an extensive quantitative comparison between those two runtimes, achieving the goal of digging deeper into where one prevails on the other both in scheduling as in managing protected resources.

Analisi di algoritmi per il data mining relazionale - Giovanni Calore - 1081959 - Relatore: Fabio Aiolli

E' sempre più semplice reperire grandi quantità di dati, ma risulta spesso difficile estrarre conoscenza da essi in modo efficace, soprattutto quando l'informazione è divisa su più tabelle. Il data mining relazionale è un campo del machine learning che consente di analizzare informazioni contenute in database relazionali, sfruttando l'espressività fornita dalle relazioni logiche, per migliorare il processo di apprendimento. Il documento analizza il problema e descrive i possibili approcci esistenti per l'apprendimento. E' successivamente riportato il confronto tra gli algoritmi che rappresentano lo stato dell'arte per la risoluzione del problema, valutandone efficacia e prestazioni su diversi esempi.

Confronto tra strumenti per l'analisi di grandi quantita' di dati - Enrico Bottaro - 1081293 - Relatore: Silvia Crafa

Questo elaborato presenta un confronto tra una versione sequenziale e due parallelizzate di un algoritmo utilizzato per la realizzazione di un sistema di raccomandazione di brani musicali. Per la versione sequenziale è stato utilizzato il linguaggio Python, mentre per le versioni parallelizzate è stato utilizzato Scala, in combinazione con Spark e Flink. Il sistema di raccomandazione fa riferimento alla MSD Challenge: una sfida di apprendimento automatico.

February 2017

Evoluzione temporale ed analisi del successo di siti web - Giulio Rigoni - 1057725 - Relatore: Massimo Marchiori

Quali sono gli aspetti che rendono un sito internet più popolare? Il lavoro svolto cerca di rispondere in parte a tale domanda, offrendo allo stesso tempo una visione temporale dell’evoluzione del Web, sotto alcuni aspetti come il testo, la semplici- tà dei contenuti, alcune tecnologie usate ecc. Tramite l’ausilio di Memento project e Alexa sono state ricavate le precedenti versioni di Homepage relative ai siti più popolari del Web, suddivisi per categorie di contenuti e nazionalità. Dai risulta- ti emerge che la quantità di codice, testo, script e complessità delle Homepage è aumentata nel tempo e sebbene anche la quantità di link presenti nelle pagine sia anche essa aumentata, la più recente tendenza sembra essere quella di mantenere i link all’interno del proprio dominio. Stesso ragionamento si applica anche alla tecnologia Flash; sempre meno usata negli anni con un leggero cambio di tendenza per il 2015. In alcuni casi si denotano possibili ritardi nelle tendenze Italiane rispet- to al resto delle nazioni studiate. Sono presenti correlazioni negative con l’utilizzo di immagini, escludendo categorie di contenuti che si basano su di esse (come quel- li per un pubblico adulto) e positive per quanto riguarda l’utilizzo di script. Dallo studio delle immagini risulta che il formato jpeg è il più usato, svg il meno usato (principalmente nei file CSS e in crescita recente) mentre bmp è quasi inesistente. Inoltre c’è un aumento annuo nel numero e nella dimensione delle immagini. Ri- guardo al colore è emerso che è molto influenzato dalla categoria dei contenuti, e che non ci sono forti differenze tra i siti di nazionalità Italiana, Inglese e Statu- nitense. I toni di rosso sono generalmente i più usati mentre il magenta il meno usato.

The bad vibrations of tip-tap: Inferring keystrokes on mobile devices from microphone and motion sensors - Stefano Sandonà - 1108215 - Supervisor: Mauro Conti

Modern mobile devices are equipped with various sensors that measure data related to their state, such as data about motion, location and environment. These sensors brought intelligence and awareness to the device, improving the usage experience. Unfortunately, they also opened some backdoors exploitable for malicious intentions. One of the main related threats, as demonstrated in prior works, is the possibility to perform keylogging on smartphones exploiting the inner sensors. Most of existing keyloggers on mobile devices rely on accelerometer and gyroscope as data source. However, such keyloggers suffer from the high sensitivity of sensors, that can detect any slight device movement. State-of-the-art attacks neglect this aspect, ignoring practical real-world settings, which contemplate a non-perfectly stable position maintained during typing. In this thesis we propose an innovative way to increase smartphone keylogging performance on realistic contexts. We present BADVIT (BAD VIbrations of Tip-tap), a framework that addresses a complete keylogging attack. Thanks to its modularity, BADVIT can be used by existing sensor-based keyloggers to increase their performance. In particular, we prove that it is possible to rely on acoustic emanations of the vibration, emitted as feedback by soft-keyboards (a.k.a. Haptic Feedback), to build more robust keyloggers in terms of keystroke detection. Indeed, the sound produced by the vibrating motor have spectral and temporal properties, which allow to detect when the user is typing. Knowing the exact keystrokes timing allows keylog attacks to focus the sensor-based keylogging on effective soft-keyboard usage, avoiding false detection due to other activities. In addition to that, we present a way to strengthen keyloggers based on motion data. Instead of capturing the specific key pressed by the user, it is possible to limit to detect its keyboard portion (i.e., left/right) and refine at the end the results using Natural Language Processing (NLP) techniques. To assess the feasibility and effectiveness of our proposal, we first designed and fully implemented a prototype, and then we run a thorough evaluation on such prototype. With our analysis, we were able to distinguish with an accuracy of 98.66% keystrokes from noise, and with an accuracy of 98.21% character keys from the spacebar. Analyzing gyroscope data, we could understand in which part of the soft-keyboard the key relies on (i.e., left or right) with a 90% accuracy. Performing a complete attack, we were able to detect trigrams typed by the user on 76\% of the cases.

Robustness in TSO-Architectures: an Unfolding-based Approach - gino rech - 624414 - Supervisor: Paolo Baldan

Sequential Consistency is the memory model commonly adopted by programmers and verification tools when dealing with multithreaded programs. Assuming sequential consistency, instructions of each thread are guaranteed to be executed atomically and in program order. Modern CPUs implement memory models that relax SC guarantees: conceptually, threads can execute instructions out of order and stores to the memory can be observed by different threads in different order. As a result, multithreaded programs may show unexpected, potentially undesired behaviors when run on real hardware. In this setting, a central role is played by the so-called “robustness problem”, asking whether a program has the same behaviors under SC and under some relaxed memory model of interest. In this thesis we propose an approach for statically checking the robustness of a concurrent program against the Total Store Order memory model, that, roughly speaking, allows writes to be delayed over reads of different threads. We focus on a simple imperative multithreaded program with shared memory concurrency. The approach we propose is based on the definition of a partial order true concurrent semantics of a program which explicitly describes the possibly concurrent computation steps and their mutual dependecies. Concretely, we define an encoding of the language into contextual Petri nets, an extension of the classical Petri Nets with the possibility of properly encoding concurrent read accesses to resources. The standard unfolding construction for the Petri net encoding of a program is shown to properly represent the behaviour of the program in the sequential consistency model. We then define a so-called TSO unfolding semantics which relies on a more generous notion of concurrency, where the dependencies between events (occurrences of computation steps) are relaxed. Finally, we demonstrate that if a program determines a violation of sequential consistency under a TSO architecture, then we can find a witness of such undesired behaviour in the form of an event or configuration which are in the TSO but not in the standard unfolding.

December 2016

Sviluppo di un algoritmo genetico per l’allineamento dei loci genomici - Riccardo Cesarotto - 1084448 - Relatore: Valle Giorgio

L'analisi del genoma è importante per capire l'evoluzione e il funzionamento di un organismo. Il suo studio consiste nello scoprire la funzionalità di ciascun gene ma anche di capire quali sono le malattie che nascono dalle sue alterazioni. Lo svolgimento di queste operazioni ha inizio con il sequenziamento del genoma, ovvero con l'identificazione della sua sequenza nucleotidica. Le tecnologie di oggi permettono però di leggere solamente brevi frammenti di DNA e non un intero genoma: per questo motivo, il sequenziamento genomico consiste di varie fasi. Innanzitutto da un individuo si preleva un insieme di cellule, ognuna delle quali contiene lo stesso genoma. Tutti questi genomi uguali tra loro verranno quindi estratti dalle cellule e spezzettati casualmente in tantissimi brevi frammenti che verranno a loro volta sequenziati e successivamente assemblati in base alle loro sovrapposizioni. Nel migliore dei casi si otterrà una sequenza nucleotidica che corrisponderà a quella del genoma di partenza, in altri invece si otterrà una serie di frammenti disordinati (denominati loci) interrotti probabilmente da regioni genomiche ripetute. La presente Tesi di Laurea Magistrale ha lo scopo di descrivere il progetto bioinformatico svolto a Padova presso il Dipartimento di Biologia. L'obiettivo dell'attività è stato quello di sviluppare un algoritmo che servisse a disporre questi frammenti nello stesso ordine in cui appaiono all'interno del genoma. In base al metodo illustrato in questa Tesi, è stata calcolata la probabilità che due frammenti siano vicini nel genoma. Utilizzando questa informazione, l'algoritmo provvederà quindi a ordinare adeguatamente questi frammenti.

Mirage: Toward a Stealthier and Modular Malware Analysis Sandbox for Android - Lorenzo Bordoni - 1104878 - Supervisor: Mauro Conti

Nowadays, malware is affecting not only PCs but also mobile devices, which became pervasive in everyday life. Mobile devices can access and store personal information (e.g., location, photos, and messages) and thus are appealing to malware authors. One of the most promising approach to analyze malware is by monitoring its execution in a sandbox (i.e., via dynamic analysis). In particular, most malware sandboxing solutions for Android rely on an emulator, rather than a real device. This motivates malware authors to include runtime checks in order to detect whether the malware is running in a virtualized environment. In that case, the malicious app does not trigger the malicious payload. The presence of differences between real devices and Android emulators started an arms race between security researchers and malware authors, where the former want to hide these differences and the latter try to seek them out. In this thesis we present Mirage, a malware sandbox architecture for Android focused on dynamic analysis evasion attacks. We designed the components of Mirage to be extensible via software modules, in order to build specific countermeasures against such attacks. To the best of our knowledge, Mirage is the first modular sandbox architecture that is robust against sandbox detection techniques. As a representative case study, we present a proof of concept implementation of Mirage with a module that tackles evasion attacks based on sensors API return values.

TimePlanner: Gestione dello scheduling temporale con preferenze - Claudio Carbone - 528851 - Relatore: Massimo Marchiori

Il progetto TimePlanner nasce con lo scopo di offrire un servizio per gestire la pianificazione di attività, utilizzando tecnologie e design pattern moderni. Il programma permette di gestire sia problemi di aggregazione, nei quali gli utenti devono concordare periodi di tempo condivisi in cui svolgere delle attività, sia problemi di schedulazione, in cui le attività degli utenti devono essere svolte senza sovrapposizioni in base alle risorse disponibili. Il programma tiene anche conto delle preferenze temporali espresse dagli utenti. Il problema è ricondotto ad un sistema con vincoli hard e soft, la cui ricerca della soluzione avviene tramite l'utilizzo della libreria ''Iterative Forward Search''. Il progetto è realizzato con un architettura client-server; il dialogo tra il frontend (sviluppato con Angularjs) e il backend (sviluppato con Spring) avviene tramite web service REST.

A Network Analysis of the Most Popular Remote Play Streaming Services - Giacomo Quadrio - 1061566 - Supervisor: Claudio Enrico Palazzi

One of the new trends in the video game industry is the possibility to play titles thanks to the streaming technology. Currently, the services that provide the best experience only operate if the two involved devices, the remote and client machines, are in the same LAN or WLAN. In the past, some companies like OnLive and Gaikai tried to offer such a service through an Internet connection but they failed due to the high infrastructure costs. This analysis attempts to answer to some questions about the video game streaming services like how much bandwidth they use or what is the network behavior with different games and different quality settings. The results show that to obtain a visual experience that is near the one of a dedicated video game machine a connection that delivers around 40 Mbit/s of bandwidth is required. It follows that, for the moment, the game streaming services could not be a sustainable solution that can substitute the dedicated game devices as consoles and PCs.

Machine Learning e NeuroImaging: ricerca di biomarcatori cerebrali in patologie neurologiche. - Luca Demo - 1081298 - Relatore: Fabio Aiolli

Questo elaborato presenta alcuni metodi di integrazione tra apprendimento automatico e studio di neuroimmagini. Molte patologie neurologiche sono correlate ad alterazioni nella struttura cerebrale dei pazienti. Alcuni algoritmi di apprendimento come le Support Vector Machine sono in grado non solo di raggiungere un buon potere di classificazione tra cervelli sani e affetti dalla patologia, ma anche di fornire dati utili per il riconoscimento di biomarcatori discriminanti. Si propone l'uso di Support Vector Machine e Random Forest, in modo esclusivo e congiunto, per condurre una verifica dello stato dell'arte, insieme ad alcuni approfondimenti al fine di evidenziare possibili punti critici. Particolare attenzione verrà posta al problema della classificazione tra individui sani e pazienti schizofrenici, che presenta le maggiori difficoltà. I primi capitoli introducono il problema, gli strumenti di Machine Learning e i dati a disposizione. Successivamente vengono descritte le metodologie di studio, quindi i test effettuati seguiti infine dai risultati.

We’re not on the same Wavelength: Automatic Deauthentication using Wireless Signal - Giulio Lovisotto - 1084847 - Supervisor: Mauro Conti

Authentication and deauthentication are key security mechanisms to prevent unauthorized access to computer and data assets. While the motivation for a user to go through the authentication mechanism is strong (otherwise, simply he might not have access to a system), convincing a user to perform the deauthentication procedure is less trivial. Unfortunately, if a victim user leaves his workstation unattended (e.g., to go out for lunch) without deauthenticating himself, the machine is exposed to the “lunchtime attack”: a malicious adversary could get access to the machine and act on the behalf of the victim user. In this thesis, we present, to the best of our knowledge, the first system that provides automatic user deauthentication without using behavioral-based techniques (e.g., keystroke dynamics), and without requiring the user to carry any device. We leverage physical properties of the wireless signals, and the effect of human bodies on its propagation. Our solution is easy to deploy and transparent to the user, while still being secure and efficient (deauthenticating users in a matter of seconds). To show the feasibility and performance of the proposed solution, we realized a real-world implementation, and we and run a thorough evaluation experiment. We show that our solution is able to learn and understand the behavior of the wireless signals, and to correlate them with the movement of users. Our results show that with only nine economic wireless sensors deployed in a shared office environment (i.e., with several people working at their desk at the same time), we are able to correctly deauthenticate 100% of the users within six seconds (already 90% within four seconds) since they left the proximity of their workstation. We evaluate two realistic scenarios where an adversary attempts to perform a lunchtime attack, and we show that such attack becomes unfeasible in practical settings.

Watch your step! Percorsi pedonali e Accessibilità a portata di smartwatch - Serena Pattaro - 1081476 - Relatore: Ombretta Gaggi

Lo sviluppo tecnologico ha permesso di dotare la maggior parte dei dispositivi che quotidianamente utilizziamo, in particolare smartphone e smartwatch, di vari sensori. Il loro utilizzo dà la possibilità di recuperare una grande mole di informazioni sull'ambiente che ci crirconda: queste informazioni cambiano nel tempo, ad esempio l’intensità di luce di una giornata, o il rumore del traffico di una strada. Tutti questi dati se raccolti ed elaborati possono essere utilizzati per fornire soluzioni ad-hoc per ogni singolo utente. Per fare un esempio supponiamo che un manager e una mamma con passeggino, debbano recarsi, camminando, nello stesso luogo: creare soluzioni ad-hoc significa dare al manager la possibilità di scegliere un percorso principalmente all’ombra, mentre alla mamma proporre un percorso privo di barriere architettoniche che le impediscano di compiere grandi sforzi per giungere a destinazione con il passeggino. StepbyWatch è un'applicazione pensata e sviluppata per smartwatch, al fine di recuperare informazioni sull'ambiente circostante e di utilizzarle per fornire all'utente dei percorsi pedonali caratterizzati da informazioni dinamiche differenti tra loro, minimizzando l'interazione tra utilizzatore e dispositivo.

The Dark Side of Smartphones and Tablets: A Survey on Mobile Network Traffic Analysis - Alberto Maragno - 1081068 - Supervisor: Mauro Conti

In recent years mobile devices, defined as smartphones and tablets, have met an increasing commercial success, as well as a widespread adoption among people, becoming an important, if not fundamental, element of the everyday life of millions of people all around the world. Many recent studies have highlighted this trend: mobile devices are used not only for traditional communication activities (e.g., voice calls, SMSes), but also for more advanced tasks (e.g., gaming, shopping), thanks to the enormous amount of mobile applications available on the marketplaces of the most popular mobile platforms (e.g., Android, iOS). Moreover, the traffic generated by mobile devices has become a consistent part of the overall Internet traffic. This scenario has led to an increasing interest by researchers in how it is possible to ensure security and privacy on mobile devices, and the traffic analysis is one of the research fields that have naturally moved into the mobile domain. In this thesis, we review the papers that contribute traffic analysis methods targeting mobile devices. In particular, we consider the ones in which the network traffic is: (i) sniffed at one or more access points of a Wi-Fi network; (ii) logged on one or more mobile devices; (iii) captured from the exterior of one or more mobile emulators; (iv) eavesdropped by one or more Wi-Fi monitors; (v) generated by a software simulator; and (vi) extracted from wired network traces. We believe the survey and classification done in this thesis will be a reference work for researchers and practitioners that want to study or contribute novel solutions in this area.

Algoritmi basati su programmazione matematica per la configurazione di reti ad-hoc di droni - Filippo Gamberoni - 1081445 - Relatore: Luigi De Giovanni

In questi ultimi anni i droni sono diventati un argomento di notevole interesse sia di ricerca, sia in ambito applicativo,ed emergono continuamente nuove opportunità di impiego. Uno dei settori in cui stanno acquisendo maggior importanza è quello che li vede impiegati come unità di supporto alle squadre di primo soccorso, in seguito al verificarsi di calamità naturali. Oltre ad utilizzarli per individuare i dispersi o ispezionare infrastrutture pericolanti, i droni possono venire equipaggiati con Access Points wireless e dislocati nell'area per configurare una Recovery Ad-hoc Flying Network, con lo scopo di instaurare velocemente un sistema di comunicazione d'emergenza e interconnettere gli utenti (come civili o membri delle squadre di soccorso) presenti nell'area. Ciascun utente nel range di un drone potrà quindi comunicare con esso e, tramite multi-hop relaying, con tutti gli altri nodi interconnessi alla rete. Da questa tipologia di impiego, in continuo sviluppo, emerge un interessante problema di ottimizzazione, che riguarda la determinazione della posizione del minor numero possibile di droni per garantire che tutti i canali di comunicazione tra gli utenti richiesti vengano stabiliti. Visto l'impiego di canali wireless, la soluzione del problema impone di considerare l'impatto dell'interferenza radio sulle comunicazioni. In questa tesi, definiamo il risultante problema Interference-aware (I-DARNC) e proponiamo degli algoritmi di soluzione basati su programmazione matematica. In particolare, proponiamo una formulazione di I-DARNC con un modello di Programmazione Lineare Intera Mista (Mixed Integer Linear Programming - MILP). Al fine di integrare il modello con la rappresentazione degli effetti dell'interferenza, si sviluppa un modello di interferenza basato su misure statistiche degli effetti dell'interferenza stessa sui ricevitori, seguendo uno degli approcci proposti nella letteratura del settore. Per il modello si considerano diverse varianti, in base ai tipi di interferenza che si considerano rilevanti (interferenza tra droni e/o utenti), e alla eventuale necessità di ottimizzare i flussi di traffico, oltre al numero di droni. I modelli proposti sono stati implementati in C++. utilizzando le librerie messe a disposizione da CPLEX, uno dei risolutori MILP allo stato dell'arte. I test effettuati su alcune istanze di prova di I-DARNC fanno vedere come solo istanze di piccole dimensioni possano essere risolte in modo ottimo, a causa dell'aumentare delle dimensioni del modello. Al fine di trovare delle buone soluzioni per istanze di dimensioni elevate, la tesi propone una procedura euristica. La procedura si basa sull'osservazione che, una volta fissate alcune delle variabili, il modello può essere risolto in tempi estremamente ridotti. Pertanto, l'algoritmo proposto nella tesi fissa alcune delle variabili legate alla posizione dei droni e risolve il modello iterativamente. Ad ogni iterazione, le variabili vengono fissate in modo da ridurre il numero di droni utilizzati. I risultati computazionali discussi nella tesi mostrano come le istanze di prova possano essere risolte in tempi ragionevoli, con valori della funzione obiettivo molto vicini alle soluzioni ottime, quando disponibili.

October 2016

Synthesis of Numerical Abstract Domains by Invertible Affine Transformations - Marco Zanella - 1079762 - Supervisor: Francesco Ranzato

Abstract domains play a fundamental role in program analysis based on abstract interpretation, as they encode which program properties are subject to the analysis, as well as how approximation of program properties works. The systematic design and transformation of abstract domains has been extensively studied since the beginning of abstract interpretation. This thesis focuses on transformations of a single numerical abstract domain, that is, domains representing properties of numeric program variables, offering a novel methodology for systematically transform a numerical abstract domain through affine geometric transformations, in particular invertible ones. This work shows how well-known numerical abstract domains, in particular relational domains like zones and octagons, can be systematically obtained from some basic numerical domains by applying these affine transformations and combining the results.

A Small Step Abstract Interpreter for (desugared) Python - Federico Poli - 1109576 - Supervisor: Francesco Ranzato

Static analysis tools help developers to construct and review secure, fast, maintainable and correct code. Concerning error detection, sound analysis tools can formally guarantee the absence of certain types of bugs and never raise false positives. Unsound tools, by the contrary, focus only on providing ''useful'' warnings, but are affected by both false positives and false negatives. Python is currently one of the most popular programming languages, and it has several third-party tools for static analysis. Unlike other popular languages (C, Java, .Net, JavaScript), however, Python has no sound tools. Our work is based on Lambda-py: a formal semantics for Python that provides a core language covering a large segment of Python, and a tool for the translation of Python programs to Lambda-py. We identify a common structure shared by almost all the Lambda-py rules. The few exceptions are individually inspected and modified, producing an equivalent semantics Lambda'-py. We then define a small step semantics for the static analysis of Lambda'-py, using the technique of abstract interpretation: a generic framework in which multiple types of static analysis can be implemented. Finally, the soundness of the static analysis is proved.

Analisi e sviluppo di un sistema di misurazione di processi ITSM - Marco Pezzutti - 108441 - Relatore: Tullio Vardanega

Il controllo di gestione è quel sistema volto a guidare la gestione di un azienda verso il conseguimento degli obiettivi stabiliti in sede di pianificazione operativa. Viene attuato rilevando, attraverso la misurazione di appositi indicatori, lo scostamento tra obiettivi pianificati e risultati conseguiti; informando infine di tali scostamenti gli organi responsabili, affinché possano decidere e attuare le opportune azioni correttive. Ogni azienda che sia di piccole o grandi dimensioni ha la necessità di attuare un controllo sulle attività che svolge, sui dipartimenti che la compongono e sui dipendenti che ne fanno parte. Sia che l'azienda sia manifatturiera, piuttosto che farmaceutica o che operi nel terziario, ha nel suo organigramma un dipartimento \ac{IT} che coordina e gestisce l'infrastruttura informatica aziendale. Di conseguenza anche il dipartimento \ac{IT} deve sottostare al sistema di controllo. A questo scopo esistono alcuni standard internazionali che fungono da guide per le imprese. Tra questi troviamo \ac{COBIT}, \ac{ITIL}, ISO/IEC 20000 e anche \ac{CMMI}. Il mio contributo, facente parte di un intervento più ampio svolto da Netcom srl presso Vimar SpA, è stato quello di realizzare un sistema di misurazione dati non intrusivo per l'operatività aziendale che consenta in prima battuta di valutare i miglioramenti a breve termine avuti con l'introduzione dei nuovi processi e in un secondo momento di avere uno strumento di controllo funzionale del dipartimento \ac{IT}.

Sviluppo di un framework per l’analisi di database per il relational data mining - Stefano Cecconello - 1082325 - Relatore: Fabio Aiolli

Il presente documento descrive il lavoro di tesi compiuto dal laureando Stefano Cec- conello nel corso della sua Laurea Magistrale in informatica all’Università di Padova. Il progetto affrontato prevede la creazione di un programma applicativo denominato PythonMining. Il suo scopo è quello di fornire un framework per lo sviluppo di funzioni per l’analisi di database relazionali nel campo del data mining. A partire da queste informazioni, gli utenti del programma potranno quindi essere in grado di dedurre le tecniche di apprendimento migliori per la specifica natura della base di dati. Sempre tra gli obiettivi principali, vi è anche quello di dotare il programma di un set di funzioni iniziali, in modo da fornire così un prodotto finito all’utente. L’attività di tesi fa inoltre parte di un più grande progetto di dipartimento. Quest’ultimo, tra le altre cose, prevede una parte teorica per la definizione dei modelli che poi questa tesi (in quanto parte pratica) ha il compito di implementare come funzioni eseguibili. La relazione prosegue quindi esponendo i requisiti del programma sviluppato: tra i più importanti troviamo quelli che definiscono la necessità di scrivere una struttura delle classi facilmente estendibile. Sono inoltre elencati gli use case del programma sviluppato. Si introduce quindi la progettazione definita. Viene esposta l’architettura a tre livelli, che costituisce la base del sistema di funzionamento del software. I tre strati (accesso ai dati, business logic e GUI) sono quindi descritti nel loro funziona- mento interno: sono esposte le gerarchie delle classi che garantiscono l’estendibilità del programma e la funzioni delle singole classi all’interno del sistema. Per finire sono descritte le comunicazioni che avvengo tra i livelli adiacenti e i possibili errori che si possono scatenare in questi scambi di informazioni. Si passa quindi alla descrizione delle caratteristiche implementative del programma. Le classi concrete, che implementano gli elementi grafici e le operazioni supportate dal programma, sono quindi descritte nel loro modus operandi. Nello specifico per ogni operazione sono descritti i dettagli implementativi che ne definiscono: il significato del risultato e le precondizioni per eseguirle. Compaiono poi le descrizioni di altre funzioni minori e dei test. Il capitolo conclusivo riporta la descrizione del risultato ottenuto rispetto agli obiettivi prefissati. Il prodotto è risultato soddisfare le aspettative iniziali: l’aggiunta di funzioni risulta agevole e il tool base è stato sviluppato. Vengono inoltre elencate tutte le possibilità di miglioramento ed estensione vagliate durante lo sviluppo del progetto, ma non implementate perchè solo qualitative o comunque ancora non necessarie per l’utilizzo del programma.

September 2016

Solving Signaling Storms in LTE Networks: a Software-Defined Cellular Architecture - Matteo Pozza - 1106664 - Supervisor: Claudio Enrico Palazzi

The LTE network infrastructure is composed by monolithic devices that carry out a convoluted set of tasks in a vendor-specific manner. Therefore, LTE networks are largely inflexible, and consequently unable to adapt to a constantly increasing number of mobile subscribers and the changeable usage pattern of the Internet service. In fact, current LTE networks are affected by signaling storms, which come from the inability to reduce the number of signals exchanged among the infrastructural elements of the network when the number of subscribers’ requests grows. In this work, we propose a software-defined cellular architecture, whose logical entities can be mapped to an arbitrary number of physical devices, allowing different implementations depending on the specific use case. In particular, we show that the proposed model actually mitigates the impact of signaling storms, as it can be tailored to reduce significantly the number of signals flowing in the network during the occurrences of the most frequent network events.

WiFi offload with NDN over vehicular networks - Andrea Tosatto - 1065549 - Supervisor: Claudio Enrico Palazzi

The number of vehicles connected to the Internet through cellular networks is increasing at an outstanding rate. As a result, the current mobile operators' infrastructure will progressively suffer of performance degradation, mainly caused by the high number of users. We developed a new solution to offload part of network data requested and generated by the vehicles itself or its occupants. To lower our solution's cost and time to deploy, we exploited the WiFi networks made available by the mobile networks operators. A peculiarity of our approach is the use of Named Data Network (NDN), a novel network architecture that aims to solve most of the IP's architecture problems, e.g., consumer mobility support. In this work we give an introduction and the necessary background knowledge to the problem; later we introduce and motivate our novel solution and we provide and implementation of it, and finally we proved the feasibility of our approach in real world scenario, using the existing infrastructure deployed in the city of Paris.

Learning Dot-Product Polynomials with MKLpy, a scikit compliant framework for Multiple Kernel Learning - Ivano Lauriola - 1111377 - Supervisor: Fabio Aiolli

In machine learning, Kernel Learning (KL) is a recent paradigm that consists on learning the kernel matrix from the training data directly, reducing the problems related to the arbitrary user’s choice of the kernel. Recently, the goal of KL is to provide a deep representation as is the case for neural networks. In this context, we propose a framework for Multiple Kernel Learning (MKL) scikit-compliant. Furthermore, a depth analysis over deep kernels learned in the space of Dot-Product Polynomials (DPP) in multiclass context is presented.

July 2016

Bio-Nanomachines: There’s Plenty of Weakness at the Bottom - Alberto Giaretta - 1062583 - Supervisor: Mauro Conti

Nanotechnology is growing faster than ever, and the advancements in the field of molecular communication, along with the outstanding discoveries in synthetic biology, make possible to build futuristic biologic nanonetworks. Even though deep investigations about bio-nanonetworks have been (and still are) done, very little attention has been paid to the related security issues: this lack of investigations could lead to serious problems, such as new forms of bioterrorism. In this thesis we first provide an overview of nanomachines and molecular communication technologies, as well as a summary of the state of the art in nanonetworks security and privacy issues. Then, we propose two new types of attacks, specific to bio-nanonetworks, which aim to the signalling sub-layer of the physical layer. Moreover, we propose two different kinds of countermeasures that rely on a threshold-based decision process and a Bayes’ rule decision process, respectively. We ran a thorough set of simulations, in order to asses the feasibility of our countermeasures and evaluate their potential collateral disruptiveness. Results show that our attacks are feasible and that the countermeasures are capable to effectively mitigate the danger.

PhotoTripGame: gamification per la classificazione di immagini in percorsi turistici - Dario De Giovanni - 1062713 - Relatore: Ombretta Gaggi

Gli utenti delle applicazioni sono una grande risorsa. La tendenza, legata anche alla diffusione del web 2.0 e dei social, è sempre più quella di coinvolgerli nell’esecuzione di compiti tesi a migliorare il servizio offerto. Gli utenti però in genere sono passivi e non collaborano facilmente, tendono solo a utilizzare il servizio senza svolgere il compito che ci si aspetterebbe da loro. Le tecniche di gamification cercano di dare agli utenti una motivazione per svolgere il loro compito, rendendolo divertente e/o premiando in qualche modo il lavoro svolto. PhotoTrip è un’applicazione che permette di cercare un percorso tra due località e propone i punti di interesse turistico da visitare con una breve deviazione dalla strada più diretta. Per trovare i punti di interesse PhotoTrip usa le foto geolocalizzate presenti in Flickr. Le foto restituite non sempre sono attinenti ai parametri inseriti; gli utenti possono segnalare tali foto influendo sui risultati futuri restituiti dal sistema. Per spingere più utenti a collaborare al miglioramento di PhotoTrip, aumentando il loro desiderio di interazione, si è deciso di applicare tecniche di gamification.

Analisi e sviluppo di un sistema di sblocco smartphone basato su giochi cognitivi - Marco Baesso - 1082306 - Relatore: Mauro Conti

I sistemi di sblocco per smartphone basati su pattern segreto sono soggetti ad attacchi come smudge attacks e shoulder surfing attacks; il nostro sistema crea una soluzione contro queste tipologie di attacco, utilizzando un sistema fondato su segreto permettendo il riconoscimento di un utente attraverso l'utilizzo di un gioco; abbiamo creato un sistema in cui per un utente sono necessarie poche e semplici informazioni da ricordare, garantendo affidabilità nel riconoscimento utente, introducendo quindi oltre al segreto di autenticazione, un processo di verifica non intrusiva basato sulle caratteristiche di interazione con il gioco. Molte pubblicazioni scientifiche hanno dimostrato empiricamente che il modo con cui un utente interagisce con il proprio smartphone è unico; per interazione si intende l'esecuzione di operazioni con il device, come ad esempio l'autenticazione con segno o gesture, operazioni di scrolling, operazioni touch con la tastiera virtuale ecc. Questo principio si è verificato anche nel nostro sistema e dall'analisi dei risultati sugli esperimenti eseguiti abbiamo raggiunto su uno dei giochi proposti un EER di circa 1,38%. Data l'innovatività del campo in cui si vogliono utilizzare i giochi, abbiamo optato per analizzare la fattibilità e le performance per un sistema di riconoscimento utente basato su giochi, monitorando caratteristiche comportamentali degli utenti, sfruttando touch features, dati campionati da sensori smartphone e time features.

Remaining Time Prediction of Running Business Processes Instances - Marco Pegoraro - 1057882 - Supervisor: Alessandro Sperduti

Today, more and more information related to business processes is created and made available in form of event logs. Event logs are datasets that contain information about events that are part of a process instance, together with additional information like event attributes and process instance attributes. In this thesis we examine some state-of-the-art approaches that combine Process Mining concepts with regression and classification techniques (SVR and Naive Bayes) from Machine Learning to tackle the necessity to calculate an accurate remaining time in business process running instances. These approaches does not consider the control-flow perspective (i.e. the sequence of activities) by itself, but predict the remaining time taking into account the values of the additional event attributes; that is, they perform a data-aware prediction. The final goal of the practical part of the thesis' work was to inspect the capability and enhanceability of these preexisting algorithms, mainly in terms of accuracy and reliability of the prediction; to laid out some hypotheses on how to improve the accuracy of the prediction paradigms; and to implement and test the new prediction approaches. Overall, the experimental results indicate that the baseline methods are reliable, solid and hard to improve without normative information about the process to effectively customize the algorithms; furthermore, it is shown that the predictor can be exploited to predict the amount of work needed to complete a running business process instance. The methods presented in this thesis are general and can adapt to various event logs: nonetheless, they are solid enough to constitute a possible base for a specialized operational support tool, given the necessary adjustments in the operational viewpoint; additional normative information given by a business user can aid the prediction or allow to further widen the capabilities of the predictor.

Algoritmi di programmazione matematica per problemi di Distributed- Flexible Job Shop Scheduling - Andrea Nasari - 1059500 - Relatore: Luigi De Giovanni

Negli ultimi anni i sistemi di produzione si sono evoluti dal classico ambiente centralizzato ad una configurazione più dinamica e distribuita, permettendo di creare strategie volte a ottenere contemporaneamente la riduzione dei costi con una elevata flessibilità produttiva. Un aspetto importante nell'utilizzo di questi ambienti distribuiti o con molteplici celle flessibili di produzione è la schedulazione delle operazioni di produzione. In questa tesi viene studiato il problema del Distributed-Flexible Job Shop Scheduling (DFJS) che riguarda la schedulazione di compiti (job) in un ambiente di produzione distribuito, sotto l'assunzione che ogni fabbrica/cella di produzione permetta l'esecuzione di compiti di diverso tipo. Basati sull'attuale stato dell'arte per problemi di schedulazione della famiglia Flexible Job Shop (FJS), vengono proposti tre modelli di programmazione lineare intera mista, ottenendo risultati soddisfacenti. In seguito sono state analizzate e applicate tecniche basate sulla decomposizione di Benders. L'idea alla base di queste tecniche è quella di ottenere modelli più piccoli e di conseguenza più facili da risolvere, fissando un sottoinsieme di variabili. Durate la ricerca, tramite le procedure di separazione, vengono generati e aggiunti tagli di natura combinatoria al fine di escludere soluzioni non ammissibili e subottimali. Viene introdotto un nuovo metodo di separazione efficace basato sull'analogia tra schedulazione e grafo disgiuntivo, e sull'individuazione ed eliminazione dei cammini critici. Questa procedura ha permesso di ottenere soluzioni per istanze medio-semplici del DFJS molto velocemente rispetto ai modelli lineari. Viene infine proposto un risolutore esatto e scalabile, basato su un approccio a due fasi. Questo risolutore alterna fasi di ricerca intensificata, dove la ricerca è concentrata su sulle singole fabbriche, a fasi di ricerca diversificata, dove si cercano nuove soluzioni esplorando zone sempre più distanti dalla soluzione attuale, secondo lo spirito della Variable Neighborhood Search. In entrambe le fasi, la ricerca avviene utilizzando un risolutore lineare dove gli spazi di ricerca sono definiti tramite dei tagli combinatori, come effettuato nel Local Branching. Questo approccio si è dimostrato efficace e molto efficiente rispetto ai precedenti risolutori implementati.

Allineamento del flusso di lavoro su modelli BPMN per l’analisi di conformità - Beatrice Vincenzi - 1081702 - Relatore: Alessandro Sperduti

In questo lavoro di tesi, ci si è focalizzati su una tecnica dell'area di ricerca del process mining: il conformance checking. Il suo compito è quello di confrontare il comportamento osservato nel log degli eventi con quello atteso dal modello di processi per rilevare deviazioni, localizzarle e spiegare perché esse accadono. Esistono diversi approcci di conformance checking che sono stati studiati e costruiti per rispondere a questo bisogno. Tuttavia il prcess mining nasce studiando e implementando tecniche su modelli espressi sotto forma di reti di Petri. Lo scopo di questo lavoro consiste di applicare un approccio di conformance checking su modelli BPMN, in quanto il mondo aziendali utilizza e manipola questo linguaggio di processo. La tecnica ci conformance checking che andremo a utilizzare è l’allineamento.

Don't Skype & Type: Keyboard Acoustic Eavesdropping Through Voice Over IP Applications - Daniele Lain - 1082329 - Supervisor: Mauro Conti

The acoustic emanations of keyboards represent a serious privacy issue. It is possible to understand with high accuracy what the user is typing on his keyboard, using spectral or geometrical properties of the sound of keypresses. However, previous work in the topic of keyboard acoustic eavesdropping have strong assumptions that limit their real-world feasibility. In this Thesis, we propose the novel use of Voice-over-IP (VoIP) software as a means to acquire acoustic emanations of the keyboard of the victim. We consider a number of realistic scenarios, with the goal of password cracking, and design our attack accordingly. We then carefully evaluate the accuracy of the attack on a number of users and laptops, with the realistic Touch typing style, on Skype, one of the most popular VoIP software. We show that our attack has high accuracy both when the victim is profiled by the attacker, and when the victim is completely unknown to the attacker. We then calculate the speedup that our attack can give to bruteforce techniques, and find that our attack reduces by several orders of magnitude the average number of trials required to successfully crack truly random passwords. We study VoIP related aspects of the problem of keyboard acoustic eavesdropping: the impact of audible bandwidth reduction on networks with limited network bandwidth, and the impact of voice and keypress overlapping. We find that our attack is still able to operate successfully with real-world bandwidth requirements, and when the victim talks while typing keys on the keyboard. We finally show that, even if countermeasures are possible, the best defense is prevention, by ultimately avoiding to Skype and type sensitive information.

April 2016

SLK: implementazione di SAP-LAW in Kernel Space - Giacomo Pandini - 1085320 - Relatore: Claudio Enrico Palazzi

SAP-LAW, Smart Access Point with Limited Advertised Window, è una soluzione software basata sulla modifica del comportamento di un access point riprogrammabile adattato per comunicazioni interattive in WLAN domestiche. Il suo scopo è quello di rendere migliore la fruizione contemporanea di contenuti dalla rete Internet, che siano essi provenienti da un contesto real-time o meno. Considerando il normale contesto domestico, in cui vi sono tipologie eterogenee di flussi di dati, con diverse caratteristiche e che utilizzano diversi protocolli per la loro trasmissione, SAP-LAW cerca di gestire i flussi di dati in modo che tutti i servizi legati ad essi ottengano una qualità migliore della trasmissione grazie ad un utilizzo più equilibrato della banda disponibile rispetto a quello che si otterrebbe nel caso di funzionamento normale. SAP-LAW basa il suo funzionamento sulla modifica della finestra di ricezione nei flussi TCP, in modo da limitare il ritardo di coda da essi generato ed ottenere così un’influenza minore sulle performance dei flussi interattivi basati su UDP(e.g VoIP, giochi on-line). In questo documento si prosegue il lavoro precedentemente svolto su SAP-LAW, ampliando la sua implementazione in user space e creando una nuova implementazione kernel space basata sull’utilizzo di un modulo Kernel.

Studio comparativo di efficienza e scalabilità su diverse implementazioni di un sistema di raccomandazione - Michela Bonasoro - 1057755 - Relatore: Silvia Crafa

La tesi analizza come alcune scelte di design e implementazione all'interno dei linguaggi di programmazione possano influire in termini di efficienza e prestazioni condizionando la decisione di utilizzare un certo linguaggio per l'implementazione di un algoritmo. I linguaggi presi in considerazione sono Python, Scala, Java e C++. Vengono prese in esame diverse ipotesi che possano giustificare le differenze di prestazioni messe in evidenza. Infine vengono considerati e confrontati gli strumenti messi a disposizione per la concorrenza da ogni linguaggio e come questi influenzino la scalabilità per una versione concorrente dell'algoritmo studiato.

Una procedura per il rafforzamento di tagli di ottimalità per Programmazione Lineare Intera Mista - Riccardo Zanella - 1084502 - Relatore: Luigi De Giovanni

In questa tesi tratteremo la risoluzione di un generico problema di programmazione lineare intera. Proporremo un algoritmo che si basa sull'inserimento di piani di taglio. I problemi di programmazione lineare intera sono molto più complessi rispetto alla risoluzione di problemi lineari continui. Per risolvere un problema lineare continuo esistono tecniche quali il simplesso che ci permettono di trovare la soluzione ottima. Per i problemi di programmazione lineare intera invece la tecnica del simplesso non è in generale sufficiente. Supponiamo di risolvere un problema continuo con tecniche come il simplesso. La soluzione ottima calcolata potrà avere variabili di valore frazionario. Un problema di programmazione lineare intera, invece, pone il vincolo di interezza sulle variabili del problema. Risolvere un problema di programmazione intera attraverso il suo rilassamento lineare con tecniche quali il simplesso impone di gestire la complessità della ricerca della soluzione intera. Immaginiamo infatti di procedere con la tecnica del simplesso, avremo uno spazio di ricerca in cui cercare la soluzione intera. All'interno di questo spazio di ricerca solo le soluzioni intere sono ammissibili. Le soluzioni intere sono definite solo come alcuni punti all'interno di uno spazio di ricerca. Risulta più semplice individuare un punto qualsiasi all'interno dello spazio di ricerca piuttosto di un punto particolare corrispondente alla soluzione intera. Il simplesso genera una soluzione a un problema continuo dunque non necessariamente intera. Dovremmo valutarne ognuna all'interno del reticolo sperando di trovare il prima possibile la soluzione intera. Questo approccio, ovviamente, impone notevoli costi in termini computazionali e temporali. Per rendere possibile, in termini di tempo e costo computazionale, avvicinarsi al punto ricercato, una possibile soluzione è applicare tecniche di riduzione della regione ammissibile, in modo che la ricerca dell’ottimo sia sempre più semplice grazie ad una regione ammissibile sempre più piccola. L’algoritmo che abbiamo sviluppato utilizza diverse tecniche di riduzione della regione ammissibile per permettere all'algoritmo del simplesso di trovare una soluzione che sempre più si avvicina alla soluzione ottima intera, con l’accortezza di non eliminare la soluzione ottima intera in fase di riduzione. I problemi di programmazione intera vengono risolti in genere con due tipi di metodologie, la prima è basata sul restringimento progressivo del dominio delle soluzioni attraverso l’introduzione di piani di taglio (cutting plane), la seconda si basa sulla partizione e valutazione progressiva dell’insieme delle soluzioni e prende il nome di Branch and Bound. Il nostro algoritmo risolve il problema continuo con la tecnica del simplesso combinata a una tecnica di generazione di piani di taglio. Il risultato ottenuto da queste tecniche combinate, unite alla generazione di tagli ammissibili, permettono all'algoritmo iterativo di convergere verso la soluzione intera ottima, se essa esiste. L’algoritmo inizia la sua esecuzione generando un taglio di ottimalità che successivamente si scompone in un insieme di tagli più stringenti. Questi ultimi ci permettono di ridurre la regione ammissibile in modo più efficace rispetto al taglio di ottimalità iniziale, come confermato dall'implementazione delle procedure proposte e dagli esperimenti computazionali condotti su diverse classi di programmazione lineare intera generati casualmente.

Tamper with the flow: Modern Control-Flow Integrity Implementations and their Weaknesses - Marco Negro - 1066878 - Supervisor: Mauro Conti

Protecting the runtime behaviour of an application is a critical task that is threatened by the large amount of bugs found in software. Development errors can lead to vulnerabilities exploitable by malicious users, who in turns can hijack the program and reuse the code for malicious purposes. Throughout the history of the runtime attacks, the types of vulnerabilities exploited by the attackers changed greatly, while the common feature is still the memory corruption. Many types of mechanisms has been proposed to prevent the misuse of applications. The most recent type aims to protect the control-flow of the application and it is called Control-Flow Integrity. A significant amount of work has been done in this file up until now. However, it is still difficult to find a sound solution, and performance and efficiency are the most debated aspects of these schemes. In this thesis we study a number of proposed solution which we deemed the most important and we assessed their usability and actual efficiency. We then focus on one particular scheme, selected for its possible actual usage on commercial applications and for the security it grants, showing that the problem of runtime attacks is still not solved. We present an attack, described on a trivial application, and we apply it to a modern complex application. Finally, we propose a solution to patch the studied method and we asses again its performance.

Public Warning System su Reti Cellulari - Carlo Carraro - 625432 - Relatore: Claudio Enrico Palazzi

In questo documento di tesi vengono analizzate quali sono le tecniche odierne e dell’imminente futuro per informare i cittadini di situazioni di pericolo imminente o d’emergenza come terremoti, tsunami, etc.; il tutto in ambito di reti cellulari, con particolare attenzione alle reti UMTS e LTE. Si tratta del lavoro svolto presso Athonet Srl per implementare un Cell Broadcast Center da integrare in un core network di una rete cellulare; vengono analizzati i requisiti del servizio e i protocolli proposti dal 3GPP. I documenti del 3GPP sono innumerevoli e molto tecnici; in particolare quelli a cui fare riferimento o coinvolti in qualche modo nel servizio di broadcast sono a decine. Questa tesi può essere una buona introduzione per chi voglia avere una panoramica generale del funzionamento del Cell Broadcast Service.

Modeling Elastic and Multi-Tenant Applications Deployable in the Cloud - Andrea Meneghinello - 1082342 - Supervisor: Tullio Vardanega

The attention for cloud computing and the take up of its offering have risen swiftly over the last decade. The cloud computing stack, also known as SPI, spans three conceptual layers with associated service models: SaaS on the top (at user end), PaaS in the middle (at developers end) and finally IaaS on the bottom (at sysadmin end) where physical resources reside. Owing to more immediate perception of value added, the cloud landscape has shown marked progress in the development of the SaaS and IaaS offerings. Interest in PaaS solutions have taken longer to ignite instead, so much so that the PaaS world is still largely unexplored. The purpose of this thesis is to explore the PaaS layer in order to understand how it is different from the IaaS layer and how we are able to build elastic applications upon it. We analyse in deep, through the evaluation of infrastructural costs, two units of deployment for the PaaS (VMs and containerization) in order to choose the better one to host our service. Finally, we want to propose a possible software architecture that, through micro-services, is able to exploit the elasticity mechanisms provided by the platform.

Local Model Checking in a Logic for Concurrency - Tommaso Padoan - 1062581 - Supervisor: Paolo Baldan

In the verification of software systems, the relevance of model checking techniques has been rapidly increasing. Properties expressed by logical formulae are tested on formal models of systems. When one is interested in properties regarding the concurrent features of computations, like causal dependency and independency between events, it is natural to use true concurrent system models and specification logics capable of expressing such concurrency properties. Event structures are a classical true concurrent model of computation. They represent systems in terms of the events that can occur and the causality and conflict relations between them. Event structures can be used as a semantic domain for interpreting a logic for concurrency Lhp that provides a logical characterization of history preserving bisimilarity, one of the strongest concurrent behavioural equivalences known to be decidable. The logic is able to predicate about events in computations and their causal dependency and concurrency as primitive concepts. In this thesis then we show that the model checking problem is decidable for an expressive fragment of the logic Lhp extended with fixpoint operators, interpreted over a class of event structures that, roughly speaking, capture the semantics of finite state systems. More precisely, concerning the logic, we focus on the alternation free fragment of the fixpoint extension of Lhp. As far as the event structures are concerned, we restrict to the class of strongly regular event structures, a mild refinement of the widely studied regular event structures. The decidability proof is constructive in the sense that it is based on the development of a local model checker in the form of a tableau system, for which we prove termination, soundness and completeness. In order to show the applicability of the developed model checking techniques we show how it instantiates to finite safe Petri nets, using the notion of unfolding of a net, allowing one to check alternation free formulae of Lhp on this kind of systems.

A New Methodology For Combining Graph Kernels - Carlo Maria Massimo - 1058513 - Supervisor: Alessandro Sperduti

Graph mining and particularly kernelized learning algorithms for graph-structured data have seen a steady growth in popularity during the last decades. A number of improvements over the existing graph kernels, have recently been proposed, further raising the performance limits. The procedure to estimate the performances of these kernels in real applications is still computationally demanding due to the essential process of hyper-arameter selection. In this study we want to determine if it is possible to devise a method that can substitute the commonly adopted procedures of kernel hyper-parameter selection, avoiding it entirely while preserving the predictive performances of the method. To assess the generality of the proposed methodology we analyse six different kernels, namely we consider three graph kernels that have recently been extended with contextual information and employ the contextualized and non-contextualized version for each one. The analyses are derived from commonly adopted real world bio-chemical datasets. Empirical results show that the proposed methodology is faster than the baseline method when considering large scale kernel combination while always maintaining comparable and in some cases superior performances.

Sentiment analysis per valutazioni su Tripadvisor - Sead Musa - 1013556 - Relatore: Francesco Ranzato

La Sentiment analysis assegna un giudizio positivo, negativo o neutrale ad un oggetto o entitá estraendo ed aggregando opinioni in forma testuale prese da commenti di individui con l’ausilio di programmi che analizzano li linguaggio naturale. In questo documento si partirá da dati presi da Tripadvisors in cui i giudizi sulle entitá sono espressi in un range di valori numerici. In seguito verrá discusso l’algoritmo che analizza e classifica i commenti e per finire si mostrerá un implementazione del algoritmo Borda Count che trova le preferenze e ordina le entitá.

Modelli di Programmazione Lineare Intera per il Vehicle Routing Problem - Marco Petrin - 1082330 - Relatore: Luigi De Giovanni

Questa tesi tratta il Vehicle Routing Problem con Pickup & Delivery e Time Windows. Sono stati analizzati e modificati due modelli presenti in letteratura, per creare due ulteriori nuovi modelli con i seguenti requisiti: ogni cliente deve essere visitato una sola volta da un solo veicolo; le richieste possono essere di Pickup&Delivery, solo Pickup e solo Delivery; il servizio di Pickup o Delivery presso il cliente i deve essere effettuato nei limiti delle Time Windows [ai; bi]; il carico del veicolo, ad ogni nodo visitato, non deve essere negativo e non deve eccedere la capacità totale del veicolo (che può essere diversa a seconda del veicolo); le richieste di solo Pickup possono prevedere il Delivery il giorno successivo; per ogni cliente i, il vertice di origine Oi, deve essere visitato dallo stesso veicolo e prima della visita di i, mentre il vertice di destinazione Di, deve essere visitato dallo stesso veicolo e dopo della visita di i; formulazione con soli vincoli lineari. Sono stati presi in considerazione diversi problemi derivanti dal Vehicle Routing Problem, evidenziando la vasta applicazione che hanno nel mondo reale. L'obiettivo è stato trovare il percorso migliore per soddisfare tutte le richieste dei clienti minimizzando i costi e rispettando tutti i vincoli imposti. Successivamente sono stati presentati i modelli di Programmazione Lineare Intera e gli strumenti utili per implementare e risolvere tali modelli. E' stata analizzata la formulazione generale di un modello di Programmazione Lineare Intera e le possibili soluzioni ottenibili.

February 2016

Un calcolo formale per gli attori Scala Akka e i loro tipi - Giulia Brusaferro - 1106514 - Relatore: Silvia Crafa

Scopo di questa tesi è presentare un calcolo formale che modelli il comportamento degli attori Scala Akka. In particolare in questo lavoro viene presentato un linguaggio A che modella la creazione degli attori, lo scambio di messaggi e il cambio di comportamento. All'interno dell’elaborato viene data evidenza di come l’esecuzione dei programmi scritti in A e in Akka coincida. Viene poi data un'estensione del linguaggio A in modo da inserire la gerarchia degli attori e la terminazione. Anche le esecuzioni dei programmi scritti nel nuovo linguaggio esteso A+ mostrano essere le stesse dei corrispondenti programmi scritti in Akka. Infine viene presentato un sistema di tipi per il linguaggio A che si ispira al modulo sperimentale Akka Typed e viene dimostrato che se un programma scritto nel nostro linguaggio formale è ben tipato, allora si può garantire che, a tempo di esecuzione, ogni attore sarà in grado di gestire tutti i messaggi che gli vengono inviati.

Self-Rando: Practical Load-time Randomization against Run-Time Exploits - Tommaso Frassetto - 1082077 - Supervisor: Mauro Conti

Software is developed under the assumption that it will only execute as intended by the programmer. However, attackers have used memory vulnerabilities for many decades to take control of vulnerable software. Despite the deployment of security countermeasures, such as Data Execution Prevention, Address Space Layout Randomization and Stack Canaries, attackers continue to resort to more advanced exploits, like Return-Oriented Programming. In this context, many recent security solutions rely on randomization in order to obscure the memory layout of a running application to the attacker. However, most of these solutions randomize their code at compile time, with many drawbacks that hinder the real-world feasibility of these solutions, the most important being that the build and distribution costs do not scale. In this thesis, we introduce Self-Rando, a load-time memory randomization tool. With Self-Rando, a single binary can be distributed that randomizes itself each time it is executed. Self-Rando does not require changes to the source code, the compiler or the kernel. Self-Rando has a negligible impact on performance. We have shared Self-Rando with the Tor Project, which is currently testing it in order to include it in future versions of Tor Browser.

December 2015

PathS: un servizio Location-Based per percorsi alternativi - Tobia Zorzan - 606518 - Relatore: Claudio Enrico Palazzi

La diffusione capillare di dispositivi smartphone con componenti tecnologiche sempre più evolute offre le potenzialità per creare una rete di sensori distribuiti in grado di raccogliere un’ingente mole di dati. I dati raccolti possono essere elaborati per fornire il supporto a nuovi servizi che non si basano sulle sole informazioni statiche ma su un contesto dinamico modificato dall'interazione degli utenti. Questo tipo di scenario è denominato Web Squared e il progetto PathS vuole essere un prototipo che segue questo paradigma. La sua componente client raccoglie informazioni aggiuntive sui tragitti pedonali percorsi dagli utenti. La parte server elabora le informazioni raccolte e mantiene una base di dati in grado di supportare servizi di interrogazione con criteri aggiuntivi rispetto a quelli tradizionali. Questa tesi espone quali sono stati i principi e le valutazioni eseguite nella realizzazione del componente PathS Server, i risultati raggiunti e le possibili aree di miglioramento individuate.

RPiDS: Raspberry Pi IDS - A Fruitful IDS for IoT - Alessandro Sforzin - 1014847 - Supervisor: Mauro Conti

Our technology keeps advancing towards a future where everything is connected together. The Internet of Things (IoT) goal is to make every device accessible from the Internet. Even the most common electrical appliances, such as ovens and light bulbs, will have their own IP addresses, and will be reachable remotely. While this enhanced connectivity will definitely improve our quality of life, it also raises serious security and privacy questions; the resource constrained nature of IoT entities makes traditional security techniques impractical. This thesis presents a novel intrusion detection architecture for the IoT. It discusses the feasibility of employing a low powered device as the core component of an Intrusion Detection System (IDS). Concretely, the performance of the Raspberry Pi, one of the most used commodity single-board computers, while running Snort, a widely known and open source IDS, was thoroughly studied. Experiments show that the proposed architecture based on resource constrained devices, such as the Raspberry Pi, can effectively serve as IDS.

Online Evolution of Foraging Behaviour in a Swarm of Real Robots - Alessandro Zonta - 1081173 - Supervisor: Alessandro Sperduti

This thesis describes a study in evolutionary robotics conducted completely in hardware without using simulations. The experiments employ on-line evolution, where robot controllers evolve on-the-fly in the robots' environment as the robots perform their tasks. The main issue we consider is the feasibility of dealing a complex task in a realistic time-frame. In particular, we investigate whether a population of six robots can evolve foraging behaviour in one hour. The experiments demonstrate that this is possible and they also shed light on some of the important features of our evolutionary system. Further to the specific results we also advocate the system itself. It provides an example of a replicable and affordable experimental setup for other researches to engage in research into on-line evolution in a population of real robots.

October 2015

DELTA: Data Extraction and Logging Tool for Android - Elia Dal Santo - 1014162 - Supervisor: Mauro Conti

In this thesis, we first survey the existing logging tools available on the Android platform, comparing the features of each tool and their impact on the system, and highlighting some of their shortcomings. Our investigation shows that the existing tools are often lacking in terms of flexibility, customization and extensibility. Then, we present DELTA - Data Extraction and Logging Tool for Android, our own logging logging framework. DELTA improves on the existing solutions in terms of flexibility, fine-grained tuning capabilities, extensibility and advanced logging features not present in other tools. We run a thorough evaluation of our implementation of DELTA . The results show that our tool is feasible and has a low impact on the performance of the system. We make the DELTA source code and toolset available to the research community, so researchers can leverage it to streamline the process of logging data for their experiments.

Analisi su dati aziendali reali per l'applicazione di tecniche di Collaborative Filtering e studio del framework MyMediaLite - Giulia Battistin - 1061554 - Relatore: Fabio Aiolli

La tesi tratta lo studio di Sistemi di Raccomandazione basati sul Collaborative Filtering e l'applicazione di questi algoritmi a dati aziendali reali. In collaborazione con l'azienda Ergon Informatica s.r.l. abbiamo analizzato dati di acquisti di generi alimentari da parte di aziende di distribuzione riguardanti un periodo di 10 anni. Abbiamo poi trasformato questi dati in una forma adatta all'applicazione di algoritmi di Collaborative Filtering. Per i test è stata utilizzata la libreria MyMediaLite creata appositamente per questo tipo di problemi. Infine si è fatta un'attenta analisi dei risultati ottenuti dai test, e si è mostrato quale codifica dei dati Ergon risulta migliore e quale algoritmo è il più performante per questo problema. Si è concluso che i Sistemi di Raccomandazione non solo sono utili nel campo dell'e-commerce ma risultano valore aggiunto anche in ambiti di tipo tradizionale.

Analisi e Sviluppo di un Modello di Gestione di Progetti per Menarini IFR - Sebastiano Favaro - 1035063 - Relatore: Tullio Vardanega

La tesi si occupa di gestione dei progetti IT, collocando le modalità e gli standard consolidati a livello globale in un caso particolare: la casa farmaceutica Menarini. Il lavoro di tesi si è svolto, dopo una fase iniziale di studio delle Best Practices e degli Standard esistenti, tramite un intervento all’interno dell’azienda con lo scopo di migliorare le modalità di gestione dei progetti. L’obiettivo è stato l’introduzione di sistemi per una gestione più accurata dei processi rimuovendo le componenti di impredicibilità, di casualità e migliorando il tracciamento. L’attività effettuata viene definita Tailoring, cioè l’adattamento degli standard di gestione dei progetti ad un contesto ben preciso. I modelli sviluppati, assieme alle procedure di supporto ad essi, sono stati riconosciuti come migliorativi dalla dirigenza di Menarini, e hanno rappresentato la base di un software che è stato sviluppato dall’azienda ospitante (Netcom) e che implementa le idee espresse a livello teorico. L’approccio adottato, che ha portato alla realizzazione dei modelli e del materiale correlato, costituisce un esempio di Tailoring di Standard e Best Practices ad un caso reale; pertanto esso può essere di ispirazione per raggiungere scopi simili, anche in altri contesti, sebbene il modello non possa essere direttamente esportato ad altre realtà, in quanto costituito su un caso specifico.

Routing e mobilità in reti ad hoc di droni - Luca Busato - 1082258 - Relatore: Claudio Enrico Palazzi

Le reti mobile ad hoc sono caratterizzate dall'assenza di collegamenti fisici tra i nodi di cui sono composte. In queste reti non vi è una topologia fissata poiché i nodi possono muoversi liberamente; pertanto, risulta necessario utilizzare dei protocolli di routing dinamici per l'instradamento dei pacchetti. La tesi si propone di analizzare quattro dei più diffusi protocolli di routing all'interno di una rete mobile ad hoc composta di droni. L'utilizzo di tali dispositivi introduce la necessità di valutare le performance dei protocolli di routing, non solo nel comune spazio bidimensionale dei software di simulazione, ma anche all'interno di uno spazio tridimensionale. Altra caratteristica fondamentale che contraddistingue lo studio delle reti mobile ad hoc è la scelta del modello di mobilità dei nodi che più si adatta allo scenario considerato. All'interno dell'elaborato verrà analizzato il comportamento dei protocolli di routing scelti, al variare di tre differenti modelli di mobilità per droni.

Metodi di preprocessing applicati alla predizione di serie temporali - Gianluca Carlesso - 1057762 - Relatore: Fabio Aiolli

Le aziende nella loro attività lavorativa raccolgono una grande quantità di dati. Que- sti dati contengono molte informazioni che riguardo il contesto aziendale e il mercato in cui esse partecipano. I dati hanno bisogno di essere analizzati e processati per poter estrarre le informazioni e consentire alle aziende di adottare una strategia di business intelligence per incrementare il loro vantaggio competitivo. Nel lavoro di tesi svolto, l’esigenza informativa dell’azienda è quella di predire l’andamento di ven- dita di una serie di prodotti per consentire in anticipo lo stoccaggio dei prodotti in magazzino e la loro conseguente vendita a breve termine. Il lavoro utilizza il metodo di predizione Support Vector Regression, ben noto nell’ambito dell’apprendimento automatico, per effettuare tali previsioni e si concentrerà maggiormente sull’adozio- ne di tecniche di preprocessing sui dati per raffinare e migliorare ulteriormente le previsioni fornite. In particolare, i dati potrebbero contenere valori anomali, detti outliers, che causano rumore nella fase di apprendimento e di conseguenza anche nella fase di predizione. Risulta importante individuare tali valori e gestirli in mo- do opportuno. Le tecniche disponibili in letteratura sono diverse e direttamente correlate con il contesto in esame in cui vengono sviluppate. Una tecnica molto efficace in un contesto potrebbe non esserlo in un altro. La tesi adotta un approccio sperimentale combinando metodi presenti in letteratura con intuizioni empiriche. Il lavoro è stato realizzato in collaborazione con l’azienda Ergon Informatica S.r.l che ha messo a disposizione la sua esperienza nel campo dei sistemi gestionali d’azienda e ha fornito i dati che sono stati utilizzati per la parte applicativa della tesi.

September 2015

LineSwitch: Tackling Control Plane Saturation Attacks in Software-Defined Networking - Fabio De Gaspari - 1040435 - Supervisor: Mauro Conti

Software Defined Networking (SDN) is a recently proposed networking architecture, which aim is to decouple the networking logic (the control plane) from the data forwarding functionalities (the data plane). This separation allows a virtually centralized point of control on the network, while providing a powerful abstraction of the underlying physical infrastructure complexity. Unfortunately, beside opportunities, the SDN paradigm creates new vulnerabilities too. In fact, researchers showed that the required communication channel between the control and data plane of SDN creates a potential bottleneck in the system. Attackers can easily exploit such bottleneck to mount powerful Denial of Service attacks against the SDN control plane, such as the control plane saturation attack, which can severely hinder the performance of the network. This thesis presents LineSwitch, an efficient and effective solution against the control plane saturation attack. LineSwitch combines SYN proxy techniques and probabilistic blacklisting of network traffic. We implemented LineSwitch as an extension of OpenFlow, the current reference implementation of SDN, and evaluated it under different traffic scenarios. Moreover, we also compared LineSwitch with the current state-of-the-art solution against control plane saturation attack. The results we obtained show that our proposal, compared to the state-of-the-art, reduces the time overhead by up to 30%, while ensuring the same level of protection.

Progettazione e realizzazione di un sistema di Sentiment Analysis per microblogging - Alessia Trivellato - 623656 - Relatore: Melucci Massimo

La grande diffusione dei social network ed il loro ruolo nella società contemporanea, rappresentano una delle novità più interessanti di questi ultimi anni, tanto da aver catturato l'interesse di ricercatori, giornalisti, imprese, movimenti e governi. La Sentiment Analysis, un nuovo campo di ricerca dell'informatica che combina Natural Language Processing (NLP), Machine Learning (ML) e psicologia, cerca di entrare in tale campo, con l'obiettivo di capire e monitorare in maniera analitica l'enorme quantità di dati e di ''sentiment'' prodotta dalla rete. Le opinioni, i sentimenti, gli atteggiamenti e le emozioni sono gli oggetti di studio di questa disciplina. Il lavoro svolto durante questa tesi di laurea mira alla progettazione e sviluppo di un sistema di analisi testuale, basato sui metodi propri del Machine Learning, in grado di rilevare il sentimento espresso dagli utenti sul social network Twitter, riguardo alcuni dei principali partiti politici ed esponenti italiani. Il sistema software realizzato è in grado di scaricare testi di interesse (nel nostro caso tweet), supportare l'utente nella fase di etichettatura manuale, verificare le prestazioni del classificatore ed infine fornire i risultati della classificazione automatica, il tutto mediante interfaccia grafica.

Analysis and Comparison of Position-based Routing Protocols for 3D MANETs - Daniele Ronzani - 1057310 - Supervisor: Claudio Enrico Palazzi

Recent evolutions of Mobile Ad-hoc Networks (MANETs) have considered microaerial vehicles (drones), generalizing the topology from a 2D model to a 3D one, thus generating a 3D MANET or Drone Ad-hoc Network (DANET). Indeed, the capability of drones to fly generates a scenario where nodes are not just distributed on a plain surface. This is a very interesting and technically challenging scenario, when considering routing of messages between endpoints. The wireless nature of the connection, node mobility and the lack of a communication infrastructure further complicates the problem of routing messages between endpoints. This problem is clearly exacerbated in a 3D scenario; yet, the presence of alternative routes that pass through non-planar multi-hop routes provides new possibilities that are not well exploited by current state-of-the-art algorithms. It is hence very interesting for the scientific community to study how routing protocols, designed for 2D scenarios, have been adapted to deal with 3D MANETs and whether there is a winner approach among existing ones. In this context, this thesis focuses on the difficulties and the state-of-the-art of protocols on 3D routing, drawing analysis strengths and weaknesses of all the related routing protocols proposed so far (to the best of our knowledge). Moreover, a comparison of these protocols through a common scenario is performed.

Towards a Realistic Model for Failure Propagation in Interdependent Networks - Agostino Sturaro - 1061521 - Supervisor: Mauro Conti

Recently, there has been an effort at integrating different infrastructures together, connecting them through the Internet. One remarkable example of this development is the smart grid, a modernization of the electrical grid that introduces a level of automation that can only be possible though a constant exchange of information between all parts of the electrical network. The interactions between the power and communications networks, necessary for the correct functioning of the smart grid, make one network dependent on the other. The communications network depends on the power grid for electrical energy, while the power grid depends on the communications network to coordinate all its components. The structure of the smart grid brings many advantages, such as improved monitoring and energy savings, but it also creates new vulnerabilities. That is, if there are problems in the communications network, the power grid will be affected as well, and vice-versa. Because of this, failures can spread back and forth between the two networks, causing cascade effects with a devastating impact on the whole system. The goal of this thesis is understanding the effects of interdependencies between critical infrastructural networks, focusing on the study of failure propagation between the Internet and the power grid. We propose a new model, HINT (Heterogeneous Interdependent NeTworks), to better capture and reproduce the mechanics of cascading failures. This thesis is an extension of the research work presented in the paper 'Towards a realistic model for failure propagation in interdependent networks', submitted for possible publication in a important conference in the area.

July 2015

Adding Contextual Information to Graph Kernels - Riccardo Tesselli - 1057064 - Supervisor: Alessandro Sperduti

Nowadays the amount of available data is overwhelming, not only the amount of data is increasing, but the structure of the data itself is evolving. It is convenient, for various application domains, to store data that possess inherently structural and relational characteristic. This kind of data is best represented by graphs. The application domains with graph-structured data are becoming important in current technologies and they are going to play a crucial role in the future. Some of the application domains that benefit from graph-structured data are Chemoinformatics, Bioinformatic, Computer Vision and Natural Language Processing. In these domains the computation of an analytical solution is often prohibitive or it is not clear how to formally define such a solution. We need technologies derived from Machine Learning in order to automatically process this data. In particular, kernel methods have been successful within the classification task we are interested in. Kernel methods for graph-structured data are usually defined in terms of kernels based on simple substructures that represent local features. In this thesis, we propose to extend the information carried by the local features extracted from different graph kernels. Consequently we propose the addition of contextual information: a substructure that appears in two different graphs will match only if it appears with the same context in both graphs. This idea has been applied to existing state-of-the-art graph kernels, such as the Weisfeiler-Lehman subtree kernel and the Ordered Decomposition DAG kernels. In this work we give an introduction and the necessary background knowledge to the problem; later we introduce the novel idea of contextual information and we provide an implementation of it on the different kernels, and finally we show some promising results on real-world graph classification datasets.

Study and analysis of software-enforced solutions to facilitate the timing analysis for software programs for multicore COTS processors - Alessandro Cornaglia - 1061636 - Supervisor: Tullio Vardanega

The continuous demand for processors guaranteeing high-performance and computing, also in real-time and embedded systems, has promoted the adoption of more complex hardware features, such as the advent of multicore and manycore processors. On one hand these features are able to increase the required computational performance, but, on the other hand, they impose a more complex analysis to determine the applications worst case execution time (WCET). This complexity is caused by the inter-core timing interference on the access to shared hardware resources. Interference forces the adoption of more complex WCET analysis tools that hardy provide tight results but they often resort to pessimistic over-approximations to keep the problem tractable. Considerable effort is being invested in devising WCET analysis techniques for modern multi- core processors that produce tight upper bounds with moderate effort on the part of the user. One of these analysis techniques is the probabilistic timing analysis (PTA), which is able to assures tight bounds just relying on the probability of the events. However, this analysis requires the introduction of both software or hardware improvement to assure good characteristics to the processor under analysis. A more complex challenge is provided by Commercial Off The Shelf (COTS) multicore processors, that are typically oriented to achieve better average performance rather than system analysability. In fact, they do not employ hardware features known to be easy to analyse. At the same time, COTS manufactures tend to not provide much details on the timing behaviour of their hardware, thus challenging the analysis. COTS processors can only be enforced via software after an intensive hardware behaviour categorization process. The first contribution of this work is to provide a method to categorize processors timing behaviour. This methodology can be helpful in the investigation of both source of variations and interference effects. The second contribution is close to tackle the interference problem on the access to shared hardware resources and in particular for a multicore COTS processor. A set of enforced-software solutions is proposed to reduce the latencies due to interference and for these is provided a concrete evaluation on the COTS processor.

Scaling Virtual Machine deployment in an open-source cloud stack - Andrea Gardiman - 1058076 - Supervisor: Tullio Vardanega

Cloud computing is one of the most hyped subject in IT. One of its many advantages is the elasticity, the ability to dynamically acquire or release computing resources, i.e., Virtual Machines (VMs), in response to demand. The elasticity is meaningful to the user only if it happens in a short time. However, experiments with real platforms show that the VM startup workflows usually take longer than VMs' OS boot-up time. This thesis focuses on how platform configuration and source code architecture choices can affect VM deployment speed in a cloud platform, OpenNebula. A default OpenNebula installation deploys 512 VMs (on 16 hosts) in 615 seconds on average and in 1256 in the worst case. By environment optimizations (i.e. enabling host cache) we reached 63.2 and 133 seconds, respectively for average and worst case. Unfortunately, even source code issues contribute to VM startup times, such as unnecessary locks in communications with hypervisors, expensive use of SSH connections and scalability bottlenecks due to a lack of horizontal parallelism. Improvements on those issues led us to reach 53.54 seconds on average and 87.8 seconds in the worst case. To summarize, compared to the default installation, optimizing only the configuration improves the average by 5.9x and in the worst case by 4.8x. Optimizing the code, the average improves by 12x and the last VM by 14.4x. Our improvements are in the infrastructure management layer, and are technology agnostic. This means that besides the advantages over the short term, our fixes will be useful even in the future evolution of cloud computing platform, which will comprise more PaaS and containers adoption.

Embodied Three-fold Adaptivity in a Swarm of real robots: The Guiding Effect of Social Learning on Evolution - Massimiliano Rango - 1061559 - Supervisor: Luigi De Giovanni

Embodied evolutionary robotics involves populations of robots that execute algorithms inspired by biological evolution in order to learn one or more behaviors while operating in their task environment. This master thesis focuses, within this field, on real hardware robots that simulate reproduction by exchanging artificial genetic information and creating new virtual individuals that take control of a robot's hardware. We investigate a novel adaptive system based on evolution, individual learning, and social learning in a swarm of physical Thymio II robots. The system is based on distinguishing inheritable and learnable features in the robots and defining appropriate operators for both categories. In this context, we choose to make the sensory layout of the robots inheritable, thus evolvable, and the robot controllers learnable. We run tests with a basic system that employs only evolution and individual learning and compare this with an extended system where robots can disseminate their learned controllers. Results show that social learning increases the learning speed and leads to better controllers.

Sviluppo di un agente intelligente per il gioco Geister: metodi montecarlo e trattamento di informazione imperfetta. - Mirco Pretto - 1035553 - Relatore: Alessandro Sperduti

L'obiettivo di questa tesi è lo sviluppo di un agente intelligente che giochi ad ''Die guten und die bosen Geister'', (Geister). Questo gioco è di interesse alla ricerca in ambito machine learning in quanto è caratterizato da un'informazione imperfetta. Inoltre la semplicità delle meccaniche di base rende possibile la costruzioni di agenti intelligenti più semplici e focalizzati sulla trattazione dell'informazione incompleta e la profilazione dell'avversario. Verrà analizzato lo stato dell'arte per la ricerca di strategie offline ed online. Si studieranno poi, in modo particolare, gli agenti sottoposti alla competizione Ghosts-Challenge. Da questi si partirà per la costruzione di un agente intelligente più avanzato dell'attuale stato dell'arte. Nel farlo si valuterà il metodo Monte Carlo applicato alla ricerca nello spazio delle partite, Monte Carlo Tree Search, che risulta avere le migliori prestazioni.

Sviluppo di un agente intelligente per il gioco Geister: Policy di esplorazione per game tree con informazione imperfetta - Schio Alessandro - 1061507 - Relatore: Alessandro Sperduti

Questa tesi si propone di cercare soluzioni per la risoluzione di Ghosts, un gioco ad informazione imperfetta con multiple opzioni di vittoria. Innanzitutto presenta un'analisi delle soluzioni dello stato dell'arte per questo tipo di giochi ed analizza gli agenti presentati ad una competizione (Ghosts Challenge) organizzata per lo stesso scopo di questa tesi. Dopo l'analisi delle soluzioni presenti vengono implementate alcune proposte che modificano alcune delle soluzioni partecipanti alla Ghosts Challenge con focus particolare sulle soluzioni che implementano Monte Carlo Tree Search e sue varianti. Vengono quindi sviluppate alcune soluzioni che cercano di introdurre nella simulazione del metodo MCTS la caratteristica di avere multiple possibilità di vittoria ed altre soluzioni che utilizzano le caratteristiche dello stato di gioco per influenzare la scelta della mossa. Infine, si cerca di riunire i due approcci creando una policy di simulazione che varia il modo di scegliere la mossa in base alle caratteristiche. Ciascuna soluzione è stata verificata tramite scontro diretto contro le soluzioni conosciute per valutarne l'efficacia.

April 2015

InTeGreen: Bolzano's Intelligent Transportation System in the IoT Perspective - Matthias Dieter Wallnöfer - 1035088 - Supervisor: Tullio Vardanega

The aim of this master thesis is to explore possible integration scenarios of an Intelligent Transport System platform (InTeGreen) in an Internet of Things environment. This work was promoted by the TIS innovation park, a local research institution based in Bolzano - South Tyrol - Italy, which plans various enhancements for the platform, not limited to extra sensor devices but also, among others, to the urban car sharing system. As an inhabitant of the city I had often the chance to notice the uncontrolled traffic flows which cause heavy congestion, particularly on rainy days or the ''mercatino'' (Christmas market) season. That evidence persuaded me about the usefulness of project. As an Information Technology master student of the University of Padua I enjoy the study of IT systems, system integration, reuse, middleware and databases. Even more I am a fan of Free Software and Open Data. These were the main motivation to engage in this project in collaboration with the department of ''Free Software & Open Technologies'' at the TIS innovation park.

Soluzioni scalabili per il monitoring di web application in sistemi service-oriented - Simone Carriero - 1061568 - Relatore: Tullio Vardanega

Il progetto alla base di questa tesi nasce da un caso di studio reale in contesto enterprise, all'interno del quale sono state evidenziate alcune necessità da soddisfare attraverso il monitoring delle applicazioni web fornite agli utenti. Esse sono legate al contesto metodologico e tecnologico, rispettivamente la metodologia agile e lo stile architetturale SOA (Service Oriented Architecture). Dal punto di vista tematico il problema è stato inquadrato nell' ambito dell APM (Application Performance Monitoring), mentre dal punto di vista tecnico e tecnologico è stato collocato nel contesto del data-processing. In pratica, quello che si deve fare per soddisfare le necessità individuate è calcolare delle metriche a partire dagli eventi che si manifestano all'interno del sistema da monitorare. Visto che tale sistema è caratterizzato dall'essere fornito as a Service e dall'essere basato su SOA, la gestione di tali eventi può essere considerata gestione di big data, richiedendo quindi tecniche di processing specifiche. L'obiettivo della tesi si colloca principalmente in quest'ultimo asse dello spazio della soluzione, ed è quello di proporre un'architettura di processing focalizzandosi sull'ottenimento della scalabilità.

Climb The World: applicazione di tecniche persuasive ad un serious game - Silvia Segato - 1057353 - Relatore: Ombretta Gaggi

Il ruolo che la tecnologia ha nella vita quotidiana delle persone è diventato sempre più dominante, fornendo nuovi mezzi che semplificano e facilitano aspetti nella routine quotidiana. Tuttavia, spesso questi mezzi hanno portato anche a un maggior grado di inattività a livello fisico, facendo diminuire la quantità di attività motoria giornaliera, con conseguenti gravi effetti sulla salute e sul benessere. Da questa osservazione nasce “Climb the World”, un serious game che mira a sfruttare l’omnipresenza della tecnologia per rendere le persone più attive nella vita quotidiana, spingendole a prendere le scale al posto dell’ascensore o delle scale mobili. Lo scopo di questa tesi è quello di studiare, analizzare ed implementare tecniche persuasive in “Climb the World”, al fine di motivare le persone a giocarvici maggiormente e diventare più attive. Tali tecniche sono state adattate al mondo dei serious game e della gamification, utilizzando anche il fattore dell’influenza sociale dei propri pari. L’efficacia di queste tecniche è stata verificata e provata sperimentalmente.

Un algoritmo adattivo per il lancio intelligente di trigger in ClimbTheWorld - Mattia Bazzega - 1040020 - Relatore: Ombretta Gaggi

Questa tesi descrive la realizzazione di un sistema persuasivo per ClimbTheWorld, un serious game per device mobili Android che mira all'incentivazione dell'attività fisica. Il gioco, attraverso la simulazione di una scalata, stimola l'utente a fare le scale, scegliendo quindi quelle tradizionali, rispetto a quelle mobili o all'ascensore. L'integrazione apportata a questa applicazione ha visto lo sviluppo di un algoritmo adattivo che, ispirandosi agli algoritmi genetici, ricava delle informazioni riguardo i momenti della giornata in cui l'utente fa scalini e, più in generale, attività fisica. In base a questo processo di apprendimento, nel periodo di attività cerca di lanciare nei giusti momenti degli appositi trigger che ricordano alla persona di giocare con l'applicazione facendo scalini. Questi trigger, quindi, vengono notificati all'utente solo in certe situazioni e, in particolare, se non viene riscontrato un miglioramento costante, giorno dopo giorno, del suo punteggio. In tal modo si intrattiene l'utente, dando ad esso la possibilità di migliorarsi ottenendo dei punteggi sempre maggiori e al contempo lo si sollecita a tenersi in forma. Inoltre il gioco è corredato da un meccanismo di bilanciamento energetico che prevede l'applicazione di opportune misure correttive per preservare la batteria del dispositivo e che può arrivare all'arresto temporaneo dell'algoritmo in caso di criticità rilevate nel livello della stessa.

Manifold Exploration Direct Illumination - Lorenzo Tessari - 1014342 - Supervisor: Colussi Livio

Light sampling is a well known strategy to increase image convergence rate; it can be done as in next-event estimation with Direct Illumination and as in Bidirectional Path Tracing where one side of the path is constructed starting from the light sources. Some type of paths, however, are difficult to sample regardless of the method used: we are proposing a new sampling technique which takes full advantage of the Manifold Exploration Solver to create pure transmissive paths, where light flows through specular objects in refractive bounces. We will implement it over classic Path Tracing with Multiple Importance Sampling as a testbed, comparing it against the widely used Direct Illumination; other algorithms like Bidirectional Path Tracing and Metropolis Light Transport could take benefit of it as well, carefully adapting its strategy not only as in substitution of Direct Illumination but also into their own sampling approach. Finally we advance a relaxed problem for the Manifold Exploration Solver in regard of our needs, which could ideally increase its convergence rate; a first analysis of its results is performed empirically.

February 2015

Realizzazione di una vista platform-specific model con supporto per sistemi multi-core in ambiente CONCERTO - Michele Tonon - 603613 - Relatore: Tullio Vardanega

Il progetto di cui tratta questo lavoro di tesi consiste nella realizzazione di una vista PSM (Plataform Specific Model, è la specializzazione aderente al sistema hardware sottostante del modello indipendente dalla piattaforma specificato dall'utente) per il progetto CONCERTO (http://www.concerto-project.org/) operante nell'ambito del supporto allo sviluppo di applicazioni real-time embedded su processori multi-core, che vada a sostituire l'attuale trasformazione da modello utente a PSM, fissa per regole e nascosta all'utente, aggiungendo la possibilità di modificare l'associazione di componenti software (task) con componenti hardware (core) in modo guidato da algoritmi prestabiliti selezionabili dall'utente, o manualmente, secondo scelte esplicite dell'utente. La soluzione proposta dovrà inoltre prevedere l'integrazione della nuova trasformazione con lo strumento di analisi di schedulazione MAST, sviluppato da terze parti e integrato nella tecnologia CONCERTO, e essere predisposto per attività di retropropagazione dei risultati agli elementi del modello utente.

Two Big Data application frameworks with different concurrency model: a comparative analysis of their implementations - Luca Tronchin - 1035266 - Supervisor: Silvia Crafa

Nowadays technology allows better interconnections between people generating an enormous amount of data that, when taken as a whole, can reveal more information than you would get if considered separately. To improve efficient analysis of these huge amounts of data, it is necessary to distribute the computation on multiple machines. The goal of this thesis is to analyze how two different programming paradigms, namely the shared memory model and the actor model, can influence the development of applications that manage these huge masses of data. The thesis compares the two models mentioned above, by analyzing a couple of concrete projects implemented on two concrete platforms. The result is both a conceptual comparison of models and an experimental analysis based on some concrete executions.

Sviluppo di un gestore web-based per presentazioni interattive - Sara Bonotto - 1035215 - Relatore: Ombretta Gaggi

Questo lavoro di tesi si pone l’obiettivo di realizzare una parte integrante del software Primo Round, atta ad automatizzare la gestione di presentazioni interattive. L’applicazione web è pensata per agevolare la gestione di eventi con più presentazioni e il contenuto delle stesse. L’interessante novità delle presentazioni consiste nella possibilità di partire da presentazioni esistenti in formato .pptx che, dopo una conversione in formato html, possono essere integrate all’interno del sistema. É inoltre prevista l’integrazione di slide interattive per coinvolgere il pubblico durante le presentazioni. Nelle slide interattive è possibile integrare sondaggi ai quali le persone presenti all’evento possono rispondere utilizzando il proprio dispositivo mobile. La tesi presenta il progetto nella sua totalità soffermandosi sugli aspetti più interessanti ed innovativi di quelle che sono state le tecnologie coinvolte nello sviluppo.

OASIS: Operational Access Sandboxes for Information Security - Daniel Simionato - 1035038 - Supervisor: Mauro Conti

Android’s permission system follows an “all or nothing” approach when installing an application. The end user has no way to know how the permissions are actually used by the application, and can not regulate how the sensitive data flows during its execution. Malware applications often leverage Android permission system by repackaging popular apps applications after inserting a malicious payload with the purpose of leaking sensitive information. This thesis presents OASIS (Operational Access Sandboxes for Information Security), a trusted component that allows application developers to execute operations on sensitive data by delegating the execution of those operations to a trusted service. No sensitive information is disclosed to the applications using the system. OASIS allows the end user to have full control over the data available to applications, and also grants policy based regulation of sensitive data flows. Moreover, the system can be deployed via a simple application installation, and does not require any modification to the stock Android OS.

A Personalized Recommender System For The Financial Domain - Simone Tiso - 1014186 - Supervisor: Francesca Rossi

Nowadays, to suggest interesting recommendations to the users is very important, because it allows to guide users to the best choice into their purchases. In order to carry out good recommendations we take account past users purchases, using their feedbacks (ratings) on products. These approaches are known as Collaborative Filtering. These systems assume that similar users will buy similar products. Other systems try to infer preferences through a conversation with the user. In particular, they try to extract information from the queries that the user writes into the search bar. These approaches are known as Conversational Recommender Systems. In this thesis we define a Recommender System for the financial domain. Our model is able to suggest financial products and investments to the users, according to their preferences. In order to do this, we integrate the conversational recommender system and collaborative filtering approaches with a representation of the user preferences. In particular, we define and compare four models to identify the best approach to use. In order to calculate the similarity among users, we define three new approaches. These approaches allow us to understand the distance between a pair of users, based on their preferences.

December 2014

VoAP, una soluzione per ridurre il ritardo di coda a supporto di applicazioni interattive - Michele Massaro - 1057513 - Relatore: Claudio Enrico Palazzi

L'utilizzo di applicazioni interattive per l'intrattenimento casalingo ha subito un forte incremento, a seguito della diffusione di Internet oltre che alla comodità ed alle alte prestazioni fornite dalle reti wireless. Nonostante l'utilizzo massiccio di questi nuovi servizi permangono alcuni problemi non ancora risolti. Ad esempio, se si cerca di far coesistere flussi dati e flussi real-time, i primi causeranno alte latenze e jitter ai secondi, rendendo la fruizione dei servizi che si basano su di essi poco piacevole per l'utente a causa dei significativi ritardi di coda generati. Ciò che è stato identificato come causa principale è l'algoritmo di controllo della congestione del protocollo di trasporto TCP, ideato in un periodo in cui queste problematiche non erano immaginabili. Questa tesi presenta una soluzione pensata principalmente per gli scenari casalinghi e propone un algoritmo (VoAP) che risiede all'interno dell'Access Point wireless. Il suo compito è quello di monitorare e controllare tutti i flussi che passano attraverso la rete locale, evitando che siano causa di accodamenti e conseguenti ritardi; per riuscire a limitarli viene utilizzata l'Advertised Window, che è una variabile già presente all'interno dei protocolli attuali e tramite la sua modifica evita le congestioni causate da TCP. Il risultato che VoAP riesce ad ottenere è una bassa latenza (e jitter) dei pacchetti, pur senza sacrificare il throughput dei flussi dati.

PathS: un'applicazione basata sul paradigma Web Squared - Stefano Tombolini - 1062546 - Relatore: Claudio Enrico Palazzi

Il miglioramento e la diffusione delle tecnologie mobili ha aperto le porte ad una nuova era del Web, quella del Web Squared. I sensori di cui sono equipaggiati dispositivi come smartphone e tablet sono in grado di raccogliere dati distribuiti che possono essere utilizzati per creare nuove informazioni. In questo contesto possono essere sfruttate a pieno le potenzialità offerte dalla Realtà Aumentata tramite applicazioni accattivanti ed innovative. Questo elaborato ha come scopo quello di fornire una panoramica generale sul contesto Web Squared e sul funzionamento della Realtà Aumentata. In seguito viene esposto il funzionamento dell'applicazione PathS realizzata in questo ambito per il sistema operativo Android e che ha come scopo quello di migliorare il servizio di navigazione pedonale.

L'impatto dei framework cross-platform sui consumi energetici delle applicazioni mobile. - Andrea Colombari - 1057768 - Relatore: Ombretta Gaggi

Questa tesi si pone l'obiettivo di confrontare diversi framework con lo sviluppo nativo Android, ed analizzare l'impatto che hanno sui consumi energetici dei nostri smartphone. Il motivo che sta alla base di questa ricerca, è legato ad uno dei problemi che maggiormente viene percepito dagli utilizzatori di dispositivi mobili e che, per ora, ha come soluzione provvisoria l'ottimizzazione hardware e software. Per monitorare i consumi energetici si è utilizzato uno strumento, il Power Monitor, che permette di rilevare con precisione il consumo di ogni versione del software che si è realizzata. Il software realizzato consiste in un serious game, dal titolo ''il gioco dei pesci'', che viene mandato in esecuzione, senza alcun tipo di interazione da parte dell'utente, per comprendere l'impatto che quest'ultimo ha sulla durata della batteria. Si sono confrontate sei versioni de ''il gioco dei pesci'' realizzate tramite: MoSync, Titanium, jQuery, Sencha Touch, applicazione nativa per Android e HTML/Javascript. Oltre a monitorare i consumi di ogni applicazione installata su un dispositivo Android, si monitorano anche i consumi delle applicazioni web realizzate con Sencha Touch, jQuery e HTML/Javascript. Dopo aver terminato i vari test si commentano e confrontano i consumi, sui principali browser per dispositivi Android e i consumi delle applicazioni installate su quest'ultimi.

PaaSSOA e Amazon Web Services: Un’implementazione di un SOA-based PaaS sopra un istanza di IaaS reale - Valentino Baraldo - 1018053 - Relatore: Tullio Vardanega

Negli ultimi anni abbiamo visto la crescita del cloud computing, molti fornitori di applicazioni hanno deciso di spostare il loro core business su applicazioni basate su cloud. Questo si esprime attraverso uno stack formato da tre layer: Infrastructure as a Service (IaaS), Platform as a Service (PaaS) e Software as a Service (SaaS). IaaS e SaaS sono ormai ben esplorati, Amazon Web Services è un esempio di provider IaaS leader nel mercato e numerosi sono ad oggi i SaaS provider; lo strato PaaS tuttavia rimane in parte inesplorato. E ’chiaro, anche attraverso le implementazioni reali, quali sono i ruoli e le responsabilità di IaaS e SaaS in uno stack cloud e quali sono i principi fondamentali che guidano una buona progettazione architetturale. PaaS invece non è stato ancora pienamente compreso, ruolo, caratteristiche e principi di progettazione architetturale rimangono ancora offuscati, aprendo nuove possibilità nel campo di ricerca specifico. E ’stato dimostrato che i principi SOA ed in generale la service orientation possono essere una valida guida per un design del layer PaaS con un ruolo di mediazione tra strati adiacenti, IaaS e SaaS. Il progetto PaaSSOA è una reale dimostrazione di questa intuizione, esso è un PaaS che permette ospitare e gestire servizi utente sviluppati in linguaggio Jolie. Possiede per natura una forte service orientation ed abbraccia la caratteristica di elasticity, parte del paradigma del cloud computing. Il contributo che questo lavoro di tesi vuole portare è quello di confermare che un SOA-based PaaS può risiedere in un contesto reale di cloud computing attraverso un’implementazione reale e delineare un paradigma service oriented arricchito con le caratteristiche richieste dal cloud computing.

CAPTCHaStar! A novel graphical CAPTCHA through interactive image discovery - Claudio Guarisco - 1057761 - Supervisor: Mauro Conti

Over the last years, most websites on which users can register (e.g., email providers, social networks) adopted a CAPTCHA (Completely Automated Public Turing test to tell Computers and Humans Apart) as a countermeasure for automated attacks. As an example, the most common type of CAPTCHA is the text-based one: it prompts the user to recognize a distorted text. The battle of wits between designers and attackers of CAPTCHAs led to current ones being annoying and hard to resolve for users. In this thesis, we propose CAPTCHaStar, a new image-based CAPTCHA that relies on user interaction. This novel CAPTCHA exploits the innate human ability to recognize shapes in a confused environment. We assess the effectiveness of our proposal for the two key aspects: usability and resiliency to automated attacks. First, we evaluated the usability, carrying out a thorough user study. Then, we tested the resiliency of our proposal against automated attacks. The results of our evaluation show that CAPTCHaStar is more user friendly than text-based CAPTCHAs, while being still resilient to automated attacks. This suggest that our technique is promising for a practical wide adoption, as well as motivate further research along the same direction.

Assessing users privacy in crowdsourcing environmental data - Federico Lancerin - 1057505 - Supervisor: Mauro Conti

With the smartphone revolution that took place in the past ten years most of us nowadays carries an important piece of technology in their pocket: a smartphone. In particular, everyone can now become a contributor in developing the society of the future. We are talking about the presence of a significant amount of inexpensive sensors in modern smartphones, that brought a tremendous increase in the attractiveness of participatory sensing. Nowadays we have an increasing number of devices (leading to the so called Internet of Things) that produce a large amount of sensing data. This paved the way to new services that provide us with, e.g., informations about our living environment. One of the beauties of this technology is that the data collection part usually does not require the user having to put a significant effort into it and, for example, a common walk to the grocery store automatically becomes also a way to monitor the concentration of air pollutants along the path to the store. This, in turn, can lead a concerned party to investigate the pollutants' source so to limit or extinguish their dangerous presence in the future. Unfortunately, the individual data collection however, poses several privacy and trust issues between the contributor and the crowdsourcing service. We do not want for example the data that we contribute to a public environmental monitoring service to be used against us. After all, everyone is willing to effortlessly contribute for the good of the society, a far as there is no cost associated with it, even related to potential privacy loss. Threats to participants' privacy can significantly reduce their willingness to contribute. Consequently, researchers are called to investigate such security threats, and possibly design participatory services that are transparent about the data that they require while being privacy-aware. In this thesis, we evaluate the privacy threats for users contributing to a privacy aware air quality monitoring service. We consider a scenario in which the participants contribute to the system by sending information about the outdoor environment and in particular: temperature, humidity, carbon monoxide and luminosity. The participants only give a rough information about the position where they are (e.g., just the name of the neighbourhood, or the ID of the cell tower that their smartphone is currently paired to). As such, they might believe their exact position is not revealed to the environmental data collector. We took environmental measurements with the aid of a new off-the-shelf device called Sensordrone. The device works while paired with a modern smartphone, which in turn is used to store the data and possibly transmit it to the data collector. Since these devices are new in the scene, in the early stage of this thesis we evaluate their viability as crowdsourcing platform. The main contribution of this thesis is assessing the knowledge that an attacker could gain from eavesdropping the environmental data collected by a contributor to a participatory sensing service. In particular,the focus is on whether the adversary is able to trace (and with what level of accuracy) the position of the participant, only looking at the collected environmental data and to understand what are the factors that influence the success of the attacker. Knowing those factors will enables us to suggest some improvements to environmental monitoring services that leverage the crowdsourcing opportunity to strengthen their users privacy and augment the willingness of other users to participate. We performed a thorough analysis of the attacker capabilities and showed for example that with our technique, an eavesdropped path just 100 meters long and the most ideal conditions, the attacker would be able to discover the exact participant's destination 93% of the times.

October 2014

Allineamento multiplo di sequenze tramite un algoritmo di ricerca locale stocastico - Alessandro Daniele - 1035073 - Relatore: Valle Giorgio

L’allineamento multiplo di sequenze (MSA) è un importante problema della bioinformatica il cui scopo è trovare relazioni tra residui di due sequenze biologiche collegate da una relazione evoluzionistica, strutturale o funzionale. MSA è un problema di ottimizzazione per il quale, all'interno della tesi, viene proposto un algoritmo di ricerca locale stocastico chiamato SALSA (Sequence Alignment by Local Search Algorithm). La particolarità di tale algoritmo sta nell'introduzione di un sistema più efficiente per il calcolo della funzione obiettivo che permette una più rapida esplorazione dello spazio delle soluzioni rispetto ad altri metodi simili.

MITHYS: Mind The Hand You Shake - Protecting mobile devices from SSL usage vulnerabilities - Sebastiano Gottardo - 1014797 - Supervisor: Mauro Conti

The main purpose of this study is to investigate SSL vulnerabilities, highlighted by recent studies, that are affecting a significant number of mobile applications. Most of the times, these vulnerabilities are due to improper uses of the SSL protocol (in particular, in its handshake phase), resulting in applications exposed to man-in-the-middle attacks. These applications often handle users’ sensitive data, such as bank accounts, login credentials and conversations logs. As an attempt to solve the problem, this study presents MITHYS, a system able to: (i) detect applications vulnerable to man-in-the-middle attacks, and (ii) protect them against these attacks. The MITHYS system’s architecture is designed to be independent from the considered platform, allowing implementations on the most popular mobile operative systems nowadays. In order to prove the feasibility of the MITHYS solution, this project describes the implementation of a prototype, named MITHYSApp, for the Android platform. Being operating at the application level, MITHYSApp does not require any special permissions nor OS modifications. A thorough set of experiments will assess the validity of the solution in terms of detecting and protecting mobile applications from man-in-the-middle attacks, without introducing significant overheads. These features make MITHYSApp immediately deployable on a large user base.

MrsP (Multiprocessor Resource Sharing Protocol): implementazione e valutazione - Sebastiano Catellani - 1015666 - Relatore: Tullio Vardanega

Multiprocess Resource Sharing Protocol propone un approccio innovativo per la condivisione di risorse globali. Burns e Wellings propongono una variante multiprocessor di Priority Ceiling Protocol con l'obiettivo di utilizzare, per sistemi multiprocessor partizionati, le tecniche di analisi di schedulabilità dei sistemi single processor. Per poterlo fare, occorre che il tempo di attesa per accedere alle risorse rifletta la contesa parallela, dovuta alla condivisione tra più processori, ma limitando il tempo di attesa dei job in coda senza precludere l'indipendenza dei job a priorità superiore che non la richiedono. MrsP prevede che l'esecuzione della sezione critica corrispondente alla risorsa, in caso di prerilascio del suo possessore, possa essere proseguita da parte del primo job della coda in attesa di accederla. In questa tesi, dopo aver analizzato nel dettaglio il protocollo, è elaborata una proposta di soluzione in grado di gestire anche gli aspetti che, nell'ambito teorico, non sono considerati. L'implementazione fornita è valutata tramite esperimenti che mirano a calcolare il costo delle singole primitive, valutare i costi aggiunti dal protocollo e, infine, confrontare MrsP con altri approcci.

Algoritmi di clustering Alignment-free per dati generati da tecnologie High Throughput Sequencing - Andrea Leoni - 1060082 - Relatore: Alessandro Sperduti

Negli ultimi 10 anni le tecnologie per il sequenziamento del DNA hanno fatto significativi passi in avanti e le moderne tecniche, chiamate High Throughput Sequencing, sono in grado di produrre, in poco tempo, un volume di dati enorme, che può raggiungere e superare i 500 GB di basi lette. La probabilità di errore nella lettura delle basi è però piuttosto elevata e nelle macchine moderne il numero di basi lette erroneamente raggiunge anche il 15% del totale. Le probabilità che sia avvenuto un errore nella lettura di una base viene chiamata quality value e viene fornita in output dalla macchina sequenziatrice. Nell'ambito del clustering di sequenze genomiche, sono stati proposti nel corso degli anni diversi metodi Alignment-free di misura della similarità tra due sequenze. Tali metodi Alignment-free non effettuano confronti diretti tra le sequenze e hanno il vantaggio di essere più veloci rispetto a quelli che invece sfruttano l'allineamento tra le sequenze, anche se ciò comporta una minore accuratezza. Nel lavoro di tesi si è introdotta con successo una famiglia di misure di similarità tra sequenze genomiche che tiene conto anche dei quality value e che, nell'accurato lavoro di testing effettuato, ottiene generalmente prestazioni migliori rispetto alle misure tradizionali.

July 2014

Modelli statistici applicati alla previsione di serie temporali - Dario Visonà - 1016042 - Relatore: Fabio Aiolli

Le aziende possiedono una grande mole di informazioni prodotte dall'esercizio dell'attività quotidiana. Lo scopo della tesi è di utilizzare parte di questi dati per prevedere eventi futuri, ovvero tramite l'applicazione di metodi statistici agli ordini passati prevedere il comportamento futuro dei clienti. Le informazioni sugli ordini futuri permette all'azienda di gestire la produzione valorizzando al meglio il proprio magazzino, permettendo di evadere completamente tutti gli ordini e evitare sprechi da sovrapproduzione. La tesi è stata realizzata grazie alla collaborazione con Ergon Informatica che ha messo a disposizione i dati e la loro esperienza nella gestione dei sistemi informativi d'azienda. Il lavoro della tesi si concentra principalmente nell'analisi delle serie temporali attraverso modelli statistici come ARIMA, SVR e un metodo ibrido chiamato ARIMA-SVR, valutandone i risultati con delle metriche oggettive. L'obiettivo che si vuole raggiungere è quello di fornire dei metodi da applicare nella realtà aziendale per aiutare i livelli decisionali a gestire e migliorare i propri processi aziendali.

Arduino, Interattività e Apprendimento - Filippo Monte - 1040410 - Relatore: Ombretta Gaggi

La tesi ha trattato lo sviluppo di uno strato computazionale per microcontroller Arduino Yùn. Questo strato permette allo sviluppatore di riprogrammare le schede Arduino senza dover per forza riscrivere il codice della scheda, ma semplicemente utilizzando richieste HTTP da un qualsiasi dispositvo si possa collegare ad internet. Scopo della tesi era realizzare questo strato superiore ''trasparente'' per rendere interattiva una stanza del museo del Parco degli Alberi Parlanti, di Treviso. La tesi rientra nella categoria della Domotica.

Intransitive Non-Interference by Unfolding - Francesco Burato - 1061630 - Supervisor: Paolo Baldan

Since the beginning of the computer era, the protection of confidential data from unauthorized accesses has been a key problem to address given the access of different users to the same systems. Basic direct flows of information can be prevented by adopting suitable policies, e.g., one can assign data a confidentiality level and adopt a no read up/no write down policy, i.e., avoid that the lower levels directly read higher level confidential information and that sensible data from a high level user could be passed to the lower levels. Implicit flows are more subtle. A high level user, malicious or not, could alter the behaviour of the system in such a way that confidential information is disclosed to the lower levels. For example think of a failure of the system caused by a parity check performed on a high level piece of information. The low level users could observe the failure and thus deduce some information (the parity) about that data. This scenario determined a shift from the idea of controlling user accesses to the idea of controlling the flow of information. A popular characterization of the absence of undesired information flow is based on the property of non-interference, which requires that the behaviour of higher level users does not cause any effect observable by the low level user. However, very often the requirement of a complete absence of a flow of information from the confidential to the public level is too strict. In the majority of cases it is impossible to avoid the flow of information from the private to the public level and a declassification layer is required in the system allowing for the downgrading of the confidentiality level of data which needs to be disclosed. The use of interleaving semantics to formalize and analyze this property inevitably causes the state explosion problem and it can make the verification infeasible. In the thesis we focus on systems modelled as Petri nets, one of the most popular models for concurrent and distributed systems, and we study the characterization of non-interference properties in terms of a well known true-concurrent semantics of this model, the unfolding semantics. Our aim is to provide algorithms to check these properties and show that in practice the state explosion problem can be mitigated using this approach. We show that the BNDC property, a formalization of non-interference well studied in the literature, can be characterized on contextual safe Petri nets. Moreover we extend the BNDC property to the BINI property, a formalization of intransitive non-interference that includes the treatment of downgrading or declassifying transitions in the system. This leads to an algorithm for checking BINI for safe Petri nets based on the construction of adequate complete prefixes of the unfolding. A prototype tool provides interesting results in this sense. We also apply the characterization of BNDC to analyse information flow in an imperative language with downgrading primitives, showing that also in this setting it is possible to use contextual Petri nets to detect undesired information flow from private to public level.

The Assertion Body of Knowledge : What software engineering practitioners should know to sensibly use assertions. - Ricardo Aguirre Reyes - 1020516 - Supervisor: Tullio Vardanega

Programming with Assertions (or programming with contracts) is a way to use the new features of programming languages, these features are based theoretical/scientific artifacts called assertions. Assertions were initially a logic and mathematical tool, for use with specifications, long before execution. Their use however has slowly moved toward software development proper. This evolution offers programmers the opportunity to express rigorous specifications, and its utilization can be seen as a modern programming discipline. This notwithstanding, rigorous, mathematically verified specifications continue to be a precious complement to software documentation, which forms an essential reference point throughout the entire software development process. This work aims to identify the body of knowledge that Software Engineering practitioners must be familiar with to be able to sensibly use assertions/contracts major capabilities. This effort is an attempt at characterizing the contents of the “programming with assertion” discipline. Notably, this work describes how the scope of assertions have evolved throughout the history of computer science in direct proportion with the scope of software systems. Highlighting that the latter, scope of modern software systems, arose a necessity: employing high level programming languages within assertions runtime support, which has an impact on construct software with the modern style, e.g., write programs to be integrated through reusability, meaning that the proved properties that have been demonstrated using analysis (static program verification) have been converted, due to modern construction style, into a set of “too limited proofs” and its reduced value affirm the need of operate assertions runtime support. With the use of assertions, programmers are able to write more expressive programs by intend (captured through assertions) as design specification, i.e., assertions empower the expressiveness of types and operations, in addition to what they could already express using strong typing. The aim of this work is establish the basis, for then clarify the place – and set the boundary – of “Programming with Assertions” with respect to the broad Software Engineering discipline, providing foundations for an “Assertions Programmer” curriculum development; pointing out a fair direction towards a long-term professional career. The work is divided in 3 Chapters: • I Introduction, Context and State of the Art • II The Assertions System and Programmer’s Perspective • III The Assertions Body of Knowledge and Conclusions

April 2014

Un sistema software per la simulazione di traffico aereo - Michele Da Ros - 623442 - Relatore: Francesca Rossi

Lo scopo di questo lavoro di tesi è la progettazione e la realizzazione di un sistema software di simulazione di traffico aereo integrato con i simulatori di volo prodotti dalla ditta FSC, che generi un insieme di velivoli che si spostano in maniera realistica in uno spazio aereo definito. Il fine è lo studio del problema del controllo del traffico aereo e di un possibile metodo di soluzione dei conflitti che sfrutti tecniche di intelligenza artificiale (in particolare la programmazione con vincoli).

Supporto nella ricerca di dati aziendali relazionati - Diego Benna - 622775 - Relatore: Tullio Vardanega

La tesi, a partire da un caso di studio concreto, si pone il fine di affrontare il problema generale di come raccogliere, gestire ed utilizzare le sempre più crescenti moli di informazioni eterogenee che le aziende stanno accumulando. L'obiettivo è trovare proposte di soluzione a partire dalle contromisure di un problema più grande e sempre più sentito: la crescita delle informazioni e della conoscenza nel Web intesa come comprensione di dati, fatti, informazioni. L'idea è di adottare le tecnologie semantiche, recente strumento nato per affrontare tali problematiche del Web, in ambito Enterprise. Tale proposta di soluzione consiste nella realizzazione di una base di conoscenza definita da linguaggi ontologici.

Una piattaforma interattiva per le presentazioni: realizzazione di un convertitore di slide PowerPoint in slide HTML - Yari Formaggio - 1038386 - Relatore: Ombretta Gaggi

Questo lavoro di tesi si pone l’obiettivo di realizzare un software in grado di convertire una presentazione PowerPoint, in un set di slide in formato HTML. Si vuole riuscire a riprodurre ogni slide, cercando di ridurre al minimo le differenze tra quella originale e quella convertita. Oltre a tutti gli oggetti presenti in ogni slide, si è cercato di riportare anche eventuali animazioni ad essi associate. E’ stato, tuttavia, necessario effettuare delle scelte riguardo quali feature supportare, o meno, durante il processo di conversione. Infatti, PowerPoint mette a disposizione dell’utente un numero così elevato di funzionalità e oggetti differenti, che sarebbe stato impossibile trattarli tutti nei limiti di tempo disponibili per questo progetto. Gli elementi che il convertitore supporta, al momento, permettono, comunque, di ottenere buoni risultati di traduzione, utilizzando come input una presentazione totalmente casuale. La tesi si inserisce in un contesto più ampio che riguarda una piattaforma web per la gestione di eventi live e/o online, che ha la caratteristica di essere interattiva e riuscire a coinvolgere gli utenti, durante la presentazione, fornendo la possibilità di compiere azioni concrete e in tempo reale come: mettere un commento su una slide, lasciare un feedback positivo, condividere la slide e rispondere a quesiti posti dal presentatore attraverso una slide. Questo software è stato realizzato ed è di proprietà dall’azienda Primo Round S.r.L. Il software convertitore, progettato ed implementato in questo progetto di tesi, costituisce il back end di Primo Round, e aggiunge le funzionalità necessarie a trasformare una presentazione PowerPoint, altrimenti usufruibile solo attraverso il relativo software Microsoft, in formato HTML, in modo tale da poter essere eseguita all’interno della piattaforma Primo Round.

Personalized And Dynamically Generated Playlists - Nicola Bortignon - 1034779 - Supervisor: Francesca Rossi

With the new social networks revolution, the world of computer science has started facing an entire new set of challenges. The content that was previously distributed in a specific format and available in a limited amount on a single personal computer is now aggregated and centralized in the world wide web. Music is a clear example of how the user experience has changed during the last 30 year. From the experience of listening to a CD with no more than 20 tracks during the late 90's to the web radios of late 2000's with hundreds of thousands of songs in a catalog, ending with the rising trend of personal, customized listening services, including user preference profiling based on millions of available audio files. Previous knowledge on how to deal with big data is no longer sufficient for offering the complete experience a user is looking for. Exploiting user behavior in order to satisfy his needs in real time has become the main goal to pursue. How can previous approaches be changed in order to suit this new scenario? How can new algorithms be developed for this set of new requirements? What are the characteristics of a platform that aims to offer a personalized and dynamically generated playlist service?

Can’t you hear me knocking: Identification of user actions on Android apps via traffic analysis - riccardo spolaor - 1034566 - Supervisor: Mauro Conti

While smartphone usage become more and more pervasive, people start also asking to which extent such devices can be maliciously exploited as “tracking devices”. The concern is not only related to an adversary taking physical or remote control of the device (e.g., via a malicious app), but also to what a passive adversary (without the above capabilities) can observe from the device communications. Work in this latter direction aimed, for example, at inferring the apps a user has installed on his device, or identifying the presence of a specific user within a network. In this thesis, we move a step forward: we investigate to which extent it is feasible to identify the specific actions that a user is doing on his mobile device, by simply eavesdropping the device’s network traffic. In particular, we aim at identifying user actions like browsing someone’s profile on a social network, posting a message on a friend’s wall, or sending an email. We design a system that achieves this goal starting from encrypted TCP/IP packets: it works through identification of network flows and application of machine learning techniques. We did a complete implementation of this system and run a thorough set of experiments, which show that it can achieve accuracy and precision higher than 95%, for most of the considered actions.

Easy App Green Domotic: Applicazione mobile per l’automazione di impianti domotici - Mattia Gamba - 1018270 - Relatore: Claudio Enrico Palazzi

Questa tesi riguarda un progetto in ambito IT svolto in collaborazione con l’azienda Connet Srl di Padova. La necessità espressa dall’azienda riguarda la mancanza di una componente software da associare a un sistema hardware di tipo domotico che permetta l’interazione tra tale sistema e il software. La piattaforma indicata per lo sviluppo è di tipo mobile, ossia riguarda smartphone e tablet, ma viene richiesto di rendere disponibile una modalità di accesso anche tramite personal computer (PC). Lo sviluppo ha coinvolto l’identificazione, l’analisi e l’utilizzo di software e framework dedicati alla creazione di applicazioni mobile multi-piattaforma con obiettivo Android e iOS, mentre per il PC ci si è avvalsi di un emulatore per evitare di sviluppare ulteriore software. L’interazione tra sviluppatore e azienda si è concentrata molto sull’aspetto grafico e sulla comunicazione di rete che ha influito sulle prestazioni dell’applicazione e sulle tecniche adottate per la sincronizzazione tra software e hardware. Sebbene gli strumenti multi-piattaforma abbiano evitato la necessità di usare codice nativo, si è dimostrata la difficoltà nell’integrare un completo supporto multi-piattaforma e multi-dispositivo tra due piattaforme diverse come Android e iOS. I risultati ottenuti dall’azienda sono stati più che soddisfacenti in occasione di due eventi nei quali è stata proposta al pubblico la soluzione hardware abbinata al software.

Monitoring LTE network status and implementing a Wireshark module for decoding a custom protocol - Michele Ciccozzi - 625450 - Supervisor: Claudio Enrico Palazzi

This thesis is about the implementation of a new module for the popular and open source packet analyzer tool called Wireshark, to introduce its decoding of packets sent in compliance of a private internal communication protocol; said protocol is a central part of the UMTS/HSPA/LTE mobile infrastructure product called PRIMO. The knowledge and information acquired from inspecting the communication protocol is then used to develop a tool dedicated to graphically depict a LTE network’s key performance indicators, thus showing its generic health status.

Metodi di machine learning applicati alla predizione di vendite - Stefano Tonello - 1035093 - Relatore: Fabio Aiolli

La crescita sempre più massiccia della quantità di informazione disponibile e l’aumentata “raggiungibilità” della stessa, hanno portato allo sviluppo di metodologie e strumenti che permettono di elaborare i dati e ricavarne informazioni non ovvie, di grande importanza per l’utilizzatore finale. In molte situazioni che interessano l’impresa e il management, emerge la necessità di pianificare le azioni future. La previsione è uno strumento importante per una pianificazione efficiente. Inoltre, tale strumento rende il decisore meno soggetto ad eventi inaspettati in quanto gli impone un approccio più scientifico riguardo alla conoscenza dell’ambiente in cui opera. Il lavoro della presente tesi si inserisce nell’ambito della Business Intelligence, in particolare nel fornire delle tecniche di machine learning per la predizione di dati di vendite. Il lavoro si è focalizzato sull’approccio classico per l’analisi delle serie storiche, con conseguente implementazione ed applicazione dei modelli Support Vector Machine, k-Nearest Neighbours e Artificial Neural Networks. Il lavoro di tesi ha inoltre approfondito lo studio e la creazione di nuove features ad approccio statistico per migliorare la qualità di predizione e per cercare di trovare una possibile corrispondenza fra le caratteristiche delle serie storiche e la bontà di predizione dei vari metodi.

GPGPU Programming: Raising the Abstraction Level - Luca Salucci - 1039721 - Supervisor: Silvia Crafa

In the last decade programmers and computer scientists had to face both old and new fundamental challenges, such as memory and storage challenge, concurrency and locality challenge, resiliency challenge and energy and power challenge: the latter has set forth the death of the Moore Laws as we knew it, in the last 50 years. A ''power wall'' has been reached, and this fact prevents engineers to obtain additional computational power by increasing the clock frequency of their architecture, and forced them to find and explore new solutions, mainly introducing parallelism. This trend in the architectures’ evolution forced programmers and language designers to face the complexity of concurrency and parallelism and the complex issues it brings in. New programming models and languages are needed to support the everyday programmer in the burdensome task of programming this new machines. In the last years the Graphics Processing Unit (GPU) and its massively parallel archi- tecture has been converted to a new purpose, giving rise to a new programming discipline, General Purpose GPU Programming (GP-GPU). Indeed its massively SIMD and power effi- cient architecture, even if developed and conceived for a specific task, proved to be good also for general purpose usage, particularly for some class of algorithms and applications where large amount of data need to be processed concurrently. Physics simulations, ray tracing, bioinformatics, evolutionary computation, machine learning, oil exploration, scientific image processing, linear algebra, statistics, 3D reconstruction and even stock options pricing, and many more fields and disciplines can get benefit from this architecture. For this reason the principal GPU manufacturers and vendors released new generic stream processing unit and simultaneously developed and promoted new programming models for exploiting this kind of architecture, mainly CUDA and Open-CL. Given their recent birth and their short life these programming models offer few features to programmers. The main language available within the CUDA platform is CUDA-C/C++, which is basically a NVIDIA extension to C/C++ giving an interface to the CUDA parallel computing platform. Even if currently acclaimed to be the most mature GP-GPU platform, CUDA C/C++ is still a low level programming language, lacking most of the features and constructs usually present in nowadays programming languages. As any experienced programmer knows, coding in C is not exactly the same as program- ming in Java, Scala, Ruby or any other modern programming language. Years of research and development in the language field made them way different from how they were in the ’70s. OO principles (such as classes, encapsulation, inheritance, polymorphism and dynamic dis- patching), functional programming paradigm (with higher-order functions, immutable data, type inference and sophisticated type system), together with exception handling and many other constructs and even more sophisticated features, dramatically shaped programming languages and influenced how programmers work, allowing more robust, scalable, flexible, modular and fail-safe code. Programming environments like C and Fortran allow complete and unrestricted access to computing hardware, but often require programmers to understand the low-level details of the hardware they target. Although these efficiency-oriented systems are essential to every computing platform, many programmers prefer to use higher level programming envi- ronments like Python or Ruby, focused on productivity rather than absolute performance. Productivity-focused programmers solving large or intensive problems do need high perfor- mance, and many seek to exploit parallel computing, but without the costs of understanding low-level hardware details or programming directly to a particular machine. Writing per- 4 formance portable code for such systems using low-level languages requires significant effort from a human expert. They provide low-level control of the hardware, with which C/C++ programmers can fine-tune their applications to enhance the performance significantly, by sacrificing high-level abstraction. Whilst the level of abstraction they provide gives much flexibility to the C/C++ programmers, it also has been an obstacle for others to adopt these low-level programming systems. The aim of this thesis is to test and evaluate some languages, developed with the inten- tion of providing programmers with richer and higher functionalities within the GP-GPU environment, and to consider their design, usability and performance. In Chapter 1 we are going to introduce the motivation for GP-GPU and to present both the hardware architecture on which we will work and the programming model developed on it. We will briefly analyze the evolution and trends in GPU hardware and Instruction Set Architecture (ISA). Chapter 2 will be covering background and related work on the topic, thus we will see some of the main libraries, languages and APIs developed to provide richer functionalities to GPU programmers. Hence we will move to X10, an open-source programming language developed to provide a programming model that can address the architectural challenge of multiples cores, hardware accelerators, clusters, and supercomputers in a manner that provides scalable performance in a productive manner. We will analyze the design and the main characteristics of X10 in Chapter 3, while in Chapter 4 we will focus on the GPU support and how their developers integrated it within the X10 programming model. In Chapter 5 we discuss the X10 implementation of the Conjugate Gradient algorithm - a solution method for linear equation systems - and the work done to develop it, focusing on the language features. A brief description of the Conjugate Gradient method and its parallelization approach is provided, then an overview of the main sparse matrix formats and their suitability for GPU is undertaken. Finally experimental results are presented, which compare the performance of the X10 GPU accelerated code, first against the X10 CPU equivalent, then against its CUDA equivalent. The CG code has been interfaced and exploited within a Matlab application which exploits it to solve a linear system, so at last we are going to see the speedup achieved thanks to the GPU acceleration, over the pure Matlab implementation. In Chapter 6 a different approach on the way to provide higher abstraction in GP-GPU is introduced. A DSL targeted for building portable mesh-based Partial Differential Equation (PDE) solvers and compile them for heterogeneous architectures, named Liszt, is presented. We will explore its design and implementation, describing the principles on which it is based. In the last chapter we will summarize what has been seen; both X10 and Liszt will be reviewed and the pros and cons of the two different approaches will be further discussed. The main focus will be on the usability and performance of the languages and on the tools provided to handle them. A personal perspective on the main trends in GPU computing and GP-GPU programming is given, with opinions and suggestions for language designers and developers. Summary of contributions In this work we provided a description of some state-of-the- art projects on the way to provide higher-level support for GPU and mainly an analysis of X10, a modern heterogeneous programming language for HPC programming. We used it to 5 implement a GPU accelerated Conjugate Gradient method to prove some concepts of high- level programming and to test its performance. We extended the Global Matrix Library - an X10 library for linear algebra - to include some new data-structures (i.e. Ellpack Matrix) and GPU accelerated operations on them. We provide it to the community for further development and future usage, on request. We also provided methods to - partially - handle matrices stored in the Matrix Market Exchange Format, which is widely adopted, and used them to accelerate some Matlab code with our GPU accelerated method.

La pratica del Business Process Management nelle aziende del territorio: adozione, diffusione, maturità - Francesco Cardin - 1035933 - Relatore: Tullio Vardanega

L'esperienza con i processi di business insegna che la forma influenza la funzione, cioè che il design di processo ne determina le prestazioni. Per design, si intende la specifica di quali persone devono svolgere quali compiti, in quale ordine, in quale posizione, in quali circostanze, con quali informazioni, e con quale grado di precisione. Il Business Process Management (BPM) è una disciplina gestionale focalizzata sull'uso di processi di business come un contributo significativo al raggiungimento degli obiettivi di un'organizzazione attraverso il miglioramento, la gestione continua delle prestazioni e governance dei processi aziendali essenziali. Con governance s'intende il sistema in base al quale i processi sono diretti e controllati. Sulla diffusione e adozione di pratiche di Business Process Management, Confindustria Padova (tramite un suo tavolo di lavoro tematico) ha lanciato nel 2013 un'indagine qualitativa, attraverso interviste dirette, presso un campione di aziende medie e grandi del territorio, non specificamente riferibili al settore dell'offerta dei servizi ICT, interessanti in quanto consumatrici di processi. L'indagine, la cui genesi e le cui risultanze sono oggetto della tesi, si poneva anche l'obiettivo di misurare il grado di maturità BPM di tale campione di aziende. A questo fine, l'indagine, oltre a creare consapevolezza presso le aziende del territorio, fornisce attraverso i suoi risultati un confronto sulle pratiche e maturità BPM, facendo emergere correlazioni tra la disciplina, gli obiettivi aziendali e i risultati.

CHECKPOINTING TECHNIQUES FOR DISTRIBUTED BIG DATA PIPELINES IN MULTI-TENANT CLUSTERS - Diego Giorgini - 1035660 - Supervisor: Tullio Vardanega

This thesis investigates the checkpointing techniques used by distributed big data pipelines. Checkpointing techniques have been employed to provide fault tolerance, but their use to interrupt and restart single tasks increased their importance in multi-tenant clusters, where re- sources are dynamically allocated among multiple computations. In the last decade the explosion of the Big Data trend renewed the interest in data-processing technologies. Since then new paradigms, largely inspired by Google MapReduce[20], have joined parallel RDBMSs in the effort of processing large dataset through distributed and paral- lel systems. Their success, contributed by the availability of large clus- ters of commodity hardware, encouraged comparisons of different ap- proaches and further research for more performant and powerful tools. This thesis analyzes distributed big data pipelines and the approaches used to checkpoint their operations. Firstly we explain the evolution of large datasets management and we describe the distributed data pipelines and multi-tenant clusters most diffused today. Secondly we investigate the checkpointing approaches employed by different tools, organizing them in a taxonomy and focusing on a particular aspect found in Spark and not completely disclosed in the public papers. Our main contribution is the analysis of such aspect of Spark which, during the shuffle phases, uses the communications buffers as implicit checkpoints.

February 2014

PaaSSOA: a Support System for the Specification and the Runtime Verification of Service Level Agreements in the Cloud - Alberto Zuccato - 622223 - Supervisor: Tullio Vardanega

In recent years, the transition to the Cloud model is proving to be an increasingly popular and cost-effective solution for services providers that operate at higher level of the SPI stack (SaaS layer). In this context, the Service-Oriented paradigm plays a major role because allows SaaS providers to leverage the composition (orchestration) of interoperable services in order to achieve flexible and scalable architectures, thus making the most from features and tools that are typical of the Cloud. One of these features is the Elastic Scalability. The latter allows the SaaS provider to dynamically adjust the resource capacity (leased from IaaS) based on the application use's profile. In this sense, SaaS providers often take great efforts at mapping the application requirements to IaaS requirements: if from one side they must enforce the SLA, or else, the service contract stipulated with users of the SaaS service (cloud application), from the other side they must consider the cost of IaaS resources for the support of the application. Since the application’s use profile is unpredictable from the standpoint of the SaaS provider, the latter might very appreciate a way to elastically adapt the capacity leased from the IaaS to the profile of use of the application so to get the most benefit at lower cost from the provision of the service. In the context of Cloud Computing SPI stack, the PaaS layer represents a very powerful opportunity for SaaS providers. Unfortunately, the potentialities of the PaaS mediation role has not been completely understood, so they are not fully exploited. In this thesis we implemented Elastic Scalability within a SOA PaaS framework prototype (PaaSSOA) in order to help SaaS providers achieving their business objectives. The service-oriented Jolie language, being the enabling technology of PaaSSOA, has allowed us to integrate in PaaSSOA a new core service using an instance of the Drools inference engine, thus achieving the necessary support system for the specification of SLAs, and the elastic adaption of IaaS requirements based on the runtime enforcement of SLAs themselves. The results obtained from the experimental evaluation of this integration confirm that the PaaS layer is the right layer for the support of Elastic Scalability and demonstrate the benefit for SaaS providers in the adoption of such abstraction, opening doors to new opportunities of business.

Virtual Friendship: Hiding interactions on Online Social Networks - Dario Vettore - 1013913 - Supervisor: Mauro Conti

The enormous popularity of Online Social Networks (OSNs), such as Facebook, changed the way people interact. Unfortunately, the centralized control from OSN providers leads to privacy concerns. To improve this situation, several systems have been proposed to hide information, such as user real identity, or content of exchanged messages, from OSN providers. However, they still have access to a large amount of information about users, and can infer further information when using data mining techniques, like the strength of their online interactions. In this thesis we propose VirtualFriendship, a novel solution that allows OSN users to browse each other user's profile and to exchange messages in the OSN, while keeping their interactions hidden from the OSN provider. In particular, users route their requests using other users acting as virtual connections throughout a decentralized channel and an anonymous network, such as Tor. The end-peers connections in this system are hidden to the OSN provider, so privacy and anonymity will be guaranteed to the users. In order to demonstrate the feasibility of our solution we implemented a proof of concept implementation. Furthermore, our analysis and thorough set of experiments show that the overhead introduced by our solution is very limited, and we believe negligible from a user perspective.

Client-server Configuration of Mobile Ad hoc Networks - Silvia Cibola - 1041206 - Supervisor: Luigi De Giovanni

With the recent proliferation of mobile devices, mobile ad hoc networks (MANETs) are gaining new interest among researchers. Many applications, such as multi-player games, are based on a client-server architecture, which can be obtained on MANETs by letting one of the client nodes also act as server. However, increased energy consumption for the server, along with the mobility of the devices, can lead to disconnections and node failures in the network. In order to solve this problem, it has been recently proposed to select more than one device to act as server, in turns. It is crucial to employ energy-aware methods when choosing the servers and the routing strategy, because mobile devices rely on battery power. We present several solutions that aim at maximizing the network's lifespan: a mixed integer linear programming model, several constructive heuristics and a stochastic local search algorithm. The proposed procedures have been implemented on a comprehensive network benchmark. Results show that fast heuristics are able to provide good solutions with respect to both network lifespan and total consumption. Furthermore, the availability of optimal or near optimal solutions helps identifying the key features of the nodes to be chosen as servers.

Engineering Nonstationary Adaptive Systems - Nicola Mularoni - 1034963 - Supervisor: Fabio Aiolli

One of the most challenging quest within Evolutionary Robotics is the evolution of the robot controllers for a certain task in an on-line context. The difficulty of on-line evolution lies in the fact that control needs to be learned while actually performing the task at hand. Previous work has shown how it is possible for an On-Line, On-Board Evolutionary Algorithm (such as Hybrid EvAg) to cope with dynamic environments producing robust and flexible controllers, which are able to face different circumstances, such as wade a river or cross a narrow bridge. The way robots could tackle the different environmental circumstances was by creating robot-organisms. However, one limitation of this work is the fixed way in which the world is changing. With this research we set out to extend the previous work in a scenario where the environment is changing continuously. In this scenario the robots are given a foraging task where they need to gather energy through harvesting ``plants''. Plants can exist in different sizes and consequently have different nutritional values. Furthermore, the bigger the plant is, the bigger the robot organism needed to harvest it. In this scenario the temperature of the world is varied, which affects both, the maximum speed of the robots, depending on the size of the organism, and the distribution of plants of different sizes. Moreover, various aspects of the environment, the agents, and the Evolutionary Algorithm are modified producing different system setup where the EA is always able to provide controllers that were adapting to the changing world while performing their task.

December 2013

Analisi Comparativa di Framework per lo Sviluppo Cross-Platform - Nicola Gonzo - 1035061 - Relatore: Ombretta Gaggi

In questa tesi vengono confrontati tre framework per lo sviluppo cross-platform. Grazie ad essi è possibile realizzare una singola applicazione funzionante su più piattaforme mobile. In questo modo, si riducono i tempi di sviluppo, in quanto si dovrà realizzare e mantenere una singola base di codice per tutte le piattaforme che si vogliono supportare. Principalmente si è verificato il funzionamento di questi framework su Android ed iOS, essi risultano infatti i sistemi operativi mobile più diffusi attualmente sul mercato. Al fine di giudicare i framework, si sono definiti alcuni criteri di valutazione, i più importanti dei quali sono le API, la comunità e le licenze che li caratterizzano. Per confrontarli al meglio, si è inoltre implementato lo stesso serious game con ognuno di essi. In questo modo si sono testate le principali API offerte, dando così un giudizio pratico delle funzionalità che caratterizzano i framework analizzati. I risultati ottenuti hanno dimostrato che queste soluzioni cross-platform sono una valida alternativa allo sviluppo nativo. Nonostante ciò, esse risultano ancora imperfette, in quanto non riescono a supportare al meglio le diverse piattaforme mobile. I risultati ottenuti hanno infatti evidenziato disparità di performance delle applicazioni realizzate tra Android ed iOS. I framework analizzati sono MoSync, Titanium e jQuery Mobile.

A user-customizable ZigBee-based Home Automation System - Alessandro Gonella - 603612 - Supervisor: Claudio Enrico Palazzi

Technologies for building a smart house have been around for several years. Smart homes with sensing, actuation, and networked devices have been anticipated for a long time, and both research and commercial versions have been built. However, home automation itself has not been widely adopted. This adoption failure is particularly surprising because many of the devices needed to enable home automation. The solution developed for this thesis and proposed in this document tries to face current Home Automation system's complications using some of the latest technologies, providing a low cost yet versatile system that the end user can personally install, configure, manage and upgrade.

Verifica di proprietà di safety su reti di Petri mediante interpretazione astratta - Roberto Pordon - 586661 - Relatore: Paolo Baldan

La tesi presenta un algoritmo che verifica una proprietà di safety su un generico sistema a transizione di stati, usando l'interpretazione astratta. L'algoritmo è poi applicato al caso delle reti di Petri. La tesi si conclude con un piccolo contributo che generalizza l'astrazione usata nell'algoritmo applicato alle reti di Petri.

Modelli statistici univariati e multivariati applicati alla predizione di ordini - Davide Dal Bosco - 1013960 - Relatore: Fabio Aiolli

La conoscenza di ciò che accadrà nel futuro, dal punto di vista dalla strategia aziendale, è un aspetto cruciale che deve essere valutato dai decisori d'azienda per il miglioramento del processo di decision making. Le informazioni sul futuro permettono di anticipare gli eventi e di conseguenza essere in grado di operare gli opportuni cambiamenti sui processi aziendali, in modo da massimizzare i ritorni economici, organizzativi e di gestione. Il lavoro della presente tesi si inserisce nell'ambito della Business Intelligence (BI), in particolare nel fornire delle tecniche statistiche per la predizione di dati di ordini applicate ad un caso aziendale reale. Il lavoro è stato realizzato in collaborazione con l'azienda Ergon Informatica S.r.l che ha messo a disposizione la sua esperienza nel campo dei sistemi gestionali d'azienda e fornendo i dati che sono stati adoperati per la parte applicativa della tesi. Il lavoro si è focalizzato sull'approccio moderno per l'analisi delle serie storiche, con conseguente applicazione dei modelli univariati ARIMA e modelli multivariati VAR. Per il caso multivariato sono state sfruttate delle informazioni aggiuntive relative alla similarità dei prodotti oggetto delle predizioni, ottenute mediante un'attività di clustering delle serie storiche. Per la costruzione dei modelli è stata seguita la procedura iterativa Box-Jenkins, percorrendo tutte le fasi previste da tale metodologia. Il lavoro di tesi ha messo inoltre a confronto i modelli di tipo univariato e multivariato applicati al caso reale in esame, utilizzando delle metriche oggettive per la valutazione delle predizioni e fornendo spunti per miglioramenti e sviluppi futuri.

Inline activity recognition su dispositivi mobili: applicazioni ad un serious game per l'incentivazione della mobilità - Nicola Beghin - 625043 - Relatore: Ombretta Gaggi

Questo lavoro di tesi si pone l’obiettivo di progettare e realizzare un sistema non invasivo capace di incentivare l’attività fisica durante le normali attività giornaliere, il tutto mediante il superamento dei limiti del progetto “Piano Stairs” di Volkswagen. Nell’ambito dell’activity recognition si è proceduto con l’addestramento di un classificatore supervisionato sottostante ai vincoli di esecuzione su mobile ma capace di funzionare in modalità inline (rispetto ai precedenti studi in modalità offline): questo per garantirne il funzionamento senza l’ausilio di strumenti terzi e con risultati (feedback all’utente) poco più che istantanei. E’ stato poi integrato durante lo sviluppo di un serious game su piattaforma Android, sia come esempio di applicazione pratica che come strumento di incentivazione dell’attività fisica.

Relaxing some constraints in the RUN scheduling algorithm - Luca Bonato - 1035858 - Supervisor: Tullio Vardanega

A recent implementation of the Reduction to UNiprocessor algorithm (RUN) highlighted its practical validity for scheduling real-time systems. Indeed, this implementation showed that the overhead it incurs to perform its scheduling decisions, impacts minimally on its theoretical optimality. Unfortunately, this algorithm assumes the unrealistic hypothesis of independent tasks. With this work we try to relax such constraint. Our efforts converged in the definition of a real-time resource sharing protocol that enables RUN to share resources. We also started to assess its practical validity, in order to understand how much the overhead it imposes affects the optimality of RUN. Our first results highlight that this overhead significantly depends on the number of tasks that share resources and how resources are distributed among these tasks. Moreover they highlight that the overall overhead is not negligible. We are currently conducting more experiments to determine a more precise trend in the reduction of the theoretical optimal utilization bound.

October 2013

October 2013

A Time-Composable Operating System for the Patmos Processor - Marco Ziccardi - 1035857 - Supervisor: Tullio Vardanega

The aim of this thesis is to port the TiCOS operating system to the Patmos processor. TiCOS is a light-weight operating system developed to obtain composability and analyzability and targeting single-processors. Patmos is a time-predictable single-processor developed in the framework of the T-CREST project. The aim of the T-CREST project is to develop a time-predictable multi-processor able to meet both the requirements of safety and processing capacity for modern real-time and embedded systems.

A Theory of Unfolding Prefixes - Alessandro Beggiato - 625554 - Supervisor: Paolo Baldan

As the use of concurrent and distributed systems grows, so does the need of formal models to specify, develop, and verify them in a reliable way. Formal models come equipped with a rigorous semantics, which is often expressed in terms of infinitary, non-effective structure. The key requisite to be able to effectively perform an automated verification on such systems is the capability of constructing a finite and effective approximation of such semantics, which properly captures some properties of interest. Specifically, this thesis focuses on the so-called unfolding semantics, a true concurrent semantics which represents explicitly, the possible events in computations of the systems and the dependency relations (causality, conflict, concurrency) between such events. The main contribution of this thesis is the definition of a general theory, parametrized on the modelling formalism and on the class of properties of interest, that enables to prove the existence of the finite complete prefix for an abstraction of the unfolding semantics of a formal model. The properties that such abstraction must satisfy to ensure the applicability of the theory are characterized algebraically. An algorithm to compute the finite complete prefix of abstract unfolding semantics is provided, and its correctness is proven. keywords: concurrent, unfolding, Petri nets, model checking, abstraction, prime algebraic.

General Game Playing: esplorazione dello stato dell'arte e sviluppo di un nuovo schema di controllo per CadiaPlayer - Mauro Scanagatta - 1014393 - Relatore: Fabio Aiolli

Il General Game Playing (GGP) è un giovane argomento di ricerca della IA, definito come l’arte di progettare un sistema in grado di giocare con successo ad un gioco che non ha mai incontrato prima. Nel corso degli anni sono stati sviluppati molti agenti giocanti estremamente sofisticati (per giochi come gli scacchi, la dama, il Go). Il grosso limite di questi sistemi risiede nel poter giocare solo al gioco per cui sono stati progettati. Deep Blue, il primo computer a battere un campione umano in un torneo ufficiale di scacchi, è incapace di giocare a dama - seppure si tratti di due giochi molto simili. Risulta dunque naturale chiedersi se i loro risultati meritevoli siano dovuti ad un’attenta progettazione umana, o ad una vera e propria intelligenza computazionale. La speranza è che la ricerca nel GGP possa portare allo sviluppo di una nuova generazione di algoritmi, in grado di comprendere delle regole arbitrarie, applicando una forma di general intelligence che gli permetta di adattarsi a nuovi ambienti. In questa tesi si cercherà di esplorare i risultati ottenuti nell’ambito del GGP e le principali nuove aree di ricerca, e di delineare alcune idee per lo sviluppo futuro. Presenteremo inoltre un nostro contributo originale alla disciplina, nella forma di un nuovo schema di controllo delle simulazioni per CadiaPlayer, uno dei migliori agenti GGP sviluppati.

Predizione di Link nelle reti sociali: analisi comparativa degli algoritmi per l'estrazione di caratteristiche e creazione di un classificatore per la predizione - Katia Friso - 1015432 - Relatore: Fabio Aiolli

Data una snapshot di una rete sociale, possiamo dedurre quali nuove interazioni tra i suoi membri più probabilmente si verificheranno nel prossimo futuro. Tale problema è stato formalizzato come Predizione di Link: questo fornisce informazioni significative sia per l’analisi della struttura di una rete che per l’estrazione dei link sconosciuti nelle reti incomplete. In questo lavoro consideriamo i problemi di previsione e classificazione di nuove relazioni tra attori di una rete sociale, in particolare esploriamo come prevedere nuove connessioni basandoci su quelle esistenti nella social network presa in esame, considerando esclusivamente la struttura della rete stessa e discutendo le sfide che derivano dall'elaborazione di una rete con più di un milione di utenti. Le caratteristiche topologiche della rete sono utilizzate per proporre diverse metriche/metodologie che possono, con successo, prevedere potenziali collegamenti e dunque prevedere come essa sarà strutturata in futuro. In questa tesi trattiamo il problema della Predizione di Link come un problema di classificazione binaria: forniamo un’analisi comparativa dei principali algoritmi proposti in letteratura e diverse varianti di essi utilizzati per l’estrazione delle caratteristiche e presentiamo il classificatore realizzato per la predizione di nuove relazioni. L’ostacolo più grande che le tecniche della Predizione di Link devono affrontare è l’estrazione strutturale delle features richieste per classificare i collegamenti. In questo lavoro presentiamo il nostro metodo che incorpora trentadue caratteristiche distinte utilizzate come input per la classificazione con Support Vector Machine. Le caratteristiche individuate mostrano una buona facilità di calcolo e risultano piuttosto efficaci nella risoluzione del problema della Predizione di Link. Dagli esperimenti svolti abbiamo constatato che l’utilizzo di sole informazioni locali sulla topologia della rete sono sufficienti per predire con un discreto successo gli archi mancanti.

Il Collaborative Filtering nei Sistemi di Raccomandazione: sperimentazione ed estensione di algoritmi di predizione per la raccomandazione di film - Marta Aduasio - 1015430 - Relatore: Fabio Aiolli

La nascita e la diffusione di Internet e dei suoi servizi hanno rappresentato una vera e propria rivoluzione tecnologica. Dagli anni '90 ad oggi, i passi in avanti sono stati innumerevoli. Nell'era del web 2.0, i fruitori di Internet godono di molteplici privilegi: shopping online, musica a portata di click, news, recensioni cinematografiche, pagine scientifiche. Milioni di utenti navigano ogni giorno sul web per acquistare un oggetto, leggere un libro, ascoltare musica, e non solo; sono sempre più diffusi siti web in cui è possibile scambiare opinioni o mostrare le proprie preferenze su ciò di cui si fruisce. E' in questo contesto ricco di offerte che i Sistemi di Raccomandazione trovano una collocazione ideale. Un Sistema di Raccomandazione (Recommender System) è un software di filtraggio di contenuti che guida un utente nelle sue scelte, fornendo risultati personalizzati. In questa tesi, ci siamo dedicati ad uno studio approfondito sullo stato dell'arte dei Recommender Sytems oggi; abbiamo analizzato i diversi approcci esistenti in letteratura, scegliendo quelli di Collaborative Filtering come centro del nostro lavoro. In particolare, ci siamo dedicati ai metodi neighborhood-based. La nostra proposta è un'estensione degli algoritmi di raccomandazione allo stato dell'arte. Gli esperimenti sono stati condotti su un sottoinsieme di MovieLens, piattaforma online di raccomandazioni cinematografiche, e possono essere racchiusi in due categorie: predizioni singole e predizioni combinate. Il concetto su cui ci siamo soffermati è proprio quello di ''vicinanza'' o ''similarità'': la differenza principale con altri metodi sta proprio nella scelta di non voler selezionare in anticipo i vicini, ovvero gli utenti o film più simili a quello in esame; l'idea è invece quella di pesare in maniera diversa il contributo di ciascun utente/film in base alla sua vicinanza con quello in esame. I metodi di predizione singola da noi elaborati sono una rivisitazione di quelli proposti nell'ultimo decennio. Successivamente, abbiamo provato ad implementare l'aggregazione di predittori: abbiamo prelevato le strategie di predizione che portavano ai risultati migliori e le abbiamo combinate tra loro. Dai risultati è emerso quanto ci si aspettava: le combinazioni di più strategie portano quasi sempre a risultati ancora migliori. Una parte di questo lavoro è stata inserita nella pubblicazione Efficient Top-N Recommendation for Very Large Scale Binary Rated Datasets, in Proceedings of the ACM RecSys 2013, realizzata dal prof. Fabio Aiolli

Covert Ephemeral Communication in Named Data Networking - Moreno Ambrosin - 1035635 - Supervisor: Mauro Conti

In the last decade, there has been a growing realization that the current Internet Protocol is reaching the limits of its senescence. This has prompted several research efforts that aim to design potential next-generation Internet architectures. Named Data Networking (NDN), an instantiation of the content-centric approach to networking, is one such effort. In contrast with IP, NDN routers maintain a significant amount of user-driven state. In this thesis we investigate how to use this state for covert ephemeral communication (CEC). CEC allows two or more parties to covertly exchange ephemeral messages, i.e., messages that become unavailable after a certain amount of time. Our techniques rely only on network-layer, rather than application-layer, services. This makes our protocols robust, and communication difficult to uncover. We show that users can build high-bandwidth CECs exploiting features unique to NDN: in-network caches, routers' forwarding state and name matching rules. We assess feasibility and performance of proposed cover channels using a local setup and the official NDN testbed.

Implementing RUN (Reduction to UNiprocessor): implementation and evaluation - Davide Compagnin - 623226 - Supervisor: Tullio Vardanega

The Reduction to UNiprocessor (RUN) scheduling algorithm represents an original approach to multiprocessor scheduling that exhibits the prerogatives of both global and partitioned algorithms, without incurring the respective disadvantages. As an interesting trait, RUN promises to reduce the amount of timing interference between cores, while being at the same time theoretically optimal. However, RUN has also raised some doubts on its practical viability in term of incurred overhead and required kernel support. Surprisingly, to the best of our knowledge, no practical implementation and empirical evaluation of the algorithm have been presented yet. In this thesis we present the first solid implementation of RUN and extensively evaluate its performance against P-EDF and G-EDF, with respect to empirical utilization cap, kernel overheads and inter-core interference. Our results show that RUN can be efficiently implemented on top of standard operating system primitives incurring moderate overheads and interference and supporting much higher schedulable utilization than its partitioned and global counterparts.

Esplorazione dell'uso di GPU per l'allineamento di log di eventi per il process mining - Ivan Belluco - 1035062 - Relatore: Alessandro Sperduti

La complessità crescente dei processi aziendali in molte organizzazioni stimola l'adozione di tecniche per la loro analisi, basate su modelli di processo. Tuttavia, i modelli possono non descrivere esattamente la realtà dei fatti. Risulta quindi importante controllare in che misura un processo aziendale reale sia descritto correttamente dal modello. Esistono diverse soluzioni a questo problema che possono variare per efficacia e efficienza. In questa tesi viene analizzata la possibilità di impiegare il GPU Computing per l'esecuzione di un algoritmo di allineamento di log alla base del funzionamento e validazione di molti algoritmi di Process Mining, valutandone le prestazioni rispetto alle attuali implementazioni per CPU.

Rassegna di modelli basati su RBM per l'elaborazione di sequenze temporali e valutazione/estensione di un caso di studio - Luca Pasa - 1035068 - Relatore: Alessandro Sperduti

Questa tesi propone una rassegna sullo stato dell’arte dei modelli di deep learning per dati sequenziali, andando ad seguire confronti e valutazioni ed individuando vantaggi e svantaggi dei modelli proposti. Alla fine di tale rassegna viene considerato approfonditamente un caso di studio significativo il quale incorpora molti dei vantaggi illustrati nei modelli valutati. Per tale modello, di tipo non lineare, viene proposto, sviluppato e testato un'estensione tramite un modello di tipo lineare. Vengono quindi proposti metodi di interazione tra i due modelli andando ad esporne i risultati, valutandone vantaggi e svantaggi.

GeoServer nel Cloud. Un caso di studio sulle modifiche architetturali nel passaggio a piattaforme Cloud - Cacco Federico - 624686 - Relatore: Tullio Vardanega

Negli ultimi anni l'utilizzo di piattaforme Cloud per la fornitura di servizi web sta diventando una soluzione sempre più diffusa ed economicamente vantaggiosa, ma che a volte non sembra essere stata ancora ben assimilata da parte di chi si occupa della progettazione e sviluppo dei servizi. In questa tesi si è dunque voluto dare una descrizione di come vada progettata l'architettura di un'applicazione che possa essere efficientemente utilizzata in piattaforme Cloud, così da poter sfruttarne al meglio le caratteristiche e gli strumenti li' messi a disposizione. Per far ciò sono state dapprima studiate le principali differenze che sussistono tra una piattaforma non Cloud ed una Cloud. Per dare maggior validità al lavoro svolto è stato preso in esame GeoServer, uno dei server geospaziali open source maggiormente utilizzati,progettato ancora secondo un'architettura client/server classica, ma che dati i servizi offerti trarrebbe molti vantaggi da un suo utilizzo in ambienti Cloud. Sono stati quindi individuati i limiti architetturali di GeoServer che non ne consentono un buon utilizzo su tali piattaforme, proponendo poi delle modifiche che consentono il superamento di tali limiti mantenendone comunque inalterate le funzionalità. Infine sono stati condotti dei test, usando come piattaforma Cloud Amazon AWS, per dimostrare i vantaggi della nuova architettura e confrontare alcune possibili alternative d'implementazione

Measuring similarity between health records using attributed-labeled graphs - Federico Baron - 1034765 - Supervisor: Claudio Enrico Palazzi

Health records provide a large amount of knowledge that can be employed by intelligent systems in order to support medical tasks. Case-based Reasoning (CBR) are a suitable approach in some clinical domains, since CBR cycle resembles the way physicians use their episodic knowledge to remember previous cases solved in the past. However, the huge complexity of data and the large amount of patient records, make the retrieval of similar cases an open challenge. We propose a template model for health records of a Dementia Unit using attributed-labeled graphs, whose expressivity permits to describe the key knowledge of these particular kinds of health records. We also provide a set of novel similarity measures for the retrieval of similar clinical cases. In order to evaluate our proposal, a Java implementation of the model and the measures has been done, as well as a user interface for graph acquisition and visualization. The experimentations proposed evaluate the performance of each one of the similarity measures through their accuracy, sensitivity and sensibility in retrieval task. The results show that some of the methods proposed correlates well with physicians' judgment and confirm that the attributed-labeled graph model fits well the Dementia Unit health record structure.

Interactive Subgroup Discovery - Andrea Imparato - 623480 - Supervisor: Francesca Rossi

Subgroup discovery is a Knowledge Discovery task that aims at finding subgroups of a population with high generality and distributional unusualness. In many cases the user could be interested in discovering and comparing subgroups that are difficult to find with the standard beam search. In this thesis we developed a novel method to explore the hypothesis space with the use of contingency tables analysis and the interaction between the user and the subgroup discovery system. To test the effectiveness of this approach we created several use cases on two different datasets.

Named Data on Vehicular Ad-hoc Networks - Davide Pesavento - 606640 - Supervisor: Claudio Enrico Palazzi

This work is centered around bringing a content-centric networking approach, namely NDN, to vehicular ad-hoc networks. To the best of our knowledge, this is the first time that such an integration is attempted. We built a prototype implementation of a complete NDN forwarding engine and tested it on-the-road for several days. The gathered results are promising and show that NDN has the potential of fulfilling the expectations, at least in scenarios that were traditionally considered difficult: highly dynamic network topologies due to elevated nodes mobility, disruption- and delay-tolerant networking. In particular, we believe that this is a clear demonstration that NDN on vehicular networks is feasible in practice. In order to achieve this goal we had to depart in few but significant ways even from the canonical NDN approach, proposing some changes aimed at enhancing the network performance. We validated our ideas and tuned the implementation through the use of an NDN simulator, which ultimately confirmed that our custom solutions are sound. We hope that they will serve to improve our future driving experience.

July 2013

Un modello di audit per verificare la conformità con i requisiti IT di Basilea 3 - Alessandro Lavezzo - 1013930 - Relatore: Tullio Vardanega

Basilea 3 è il nuovo schema di regolamentazione internazionale delle banche. Si tratta di un regolamento pubblicato dal Comitato di Basilea per la vigilanza banca- ria nel Dicembre 2010 e poi aggiornato nel giugno 2011 con l’obiettivo di rafforzare la capacità delle banche ad assorbire shock derivanti da tensioni finanziarie ed eco- nomiche. All’interno di Basilea 3 e di Basilea 2, la precedente normativa di cui Basilea 3 ne è l’evoluzione, troviamo diversi requisiti che ricoprono la funzione IT internamente agli istituti finanziari. Data la natura economico-finanziaria del regolamento in oggetto, quando questo tratta gli argomenti relativi all’ambito IT risulta essere carente nei dettagli. Questo problema risulta essere preoccupante quando ci si accinge a valutare la conformità di un istituto finanziario alle norme di Basilea 3. Infatti, la mancanza di dettagli della normativa potrebbe portare ad una errata valutazione della situazione bancaria, con il rischio di incorrere in sanzioni amministrative e di arrecare danni reputazionali, e non solo, alla banca sotto esame. Con questa tesi si è quindi voluto creare un modello di audit per permettere la verifica della conformità alla normativa Basilea 3 in ambito IT. Per interpretare correttamente le richieste della normativa si è fatto uso delle norme ISO che interessano le aree toccate da Basilea, dopo aver scartato le altre best practice disponibili. In questo modo è stato possibile ottenere dei requisiti nella forma desiderata: chiari, dettagliati e facilmente verificabili.

Sviluppo di un tool di supporto per la classificazione di e-mail concernenti l’assistenza a sistemi informativi - Mirko Polato - 1018402 - Relatore: Alessandro Sperduti

Sviluppo di un sistema di classificazione automatica di e-mail concernenti l’assistenza a sistemi informativi. Il sistema, inoltre, offre un meccanismo di gestione semi automatica della tassonomia di classi in cui i messaggi di posta elettronica sono categorizzati.

AIRCACHE : GEO-ANCHORED FLOATING DATA FOR MOBILE USERS - Henklajd Sadushi - 1018992 - Supervisor: Claudio Enrico Palazzi

Nowadays, the proliferation of high-end mobile devices has enabled the pos- sibility to create applications that pervasively cover our urban environment. However, the increasing demand for sharing and consuming information in this context requires new solutions able to sustain mobile-to-mobile communication. We envision a general scenario where opportunistic communications among mobile nodes taking place in our urban environment, are em- ployed to support content gathering and dissemination in an infrastructure-less fashion. In particular, in this context, we study and propose a solution for geo-anchoring data to specific location(s), achieved through replication and bouncing of the former in the interest area. The rationale is that while users come and go, the data remains anchored for a certain period of time or until the intended recipient(s) consumes them. To this end, we have devised a distributed, collision-free, application-layer solution whereby mobile nodes cooperate to deliver the depicted service. We validate the feasibility of our approach by means of extensive simulations through the use of realistic mobility models available in literature.

Preserving Smartphone Users' Anonymity in Cloudy Days - Mario Leone - 1013571 - Supervisor: Mauro Conti

The increasing spread of mobile cloud computing paradigm is changing the traditional mobile communication infrastructure. Today, smartphones can rely on virtual (software) ''clones'' in the cloud, offering backup/recovery solutions as well as the possibility to offload computations. As a result, clones increases the communication and computation capabilities of smartphones, making their limited batteries last longer. Unfortunately, mobile cloud introduces new privacy risks, since personal information of the communicating users are distributed among several parties. As an example, the cellular network operator knows how often users contact the cloud, and the cloud provider knows how often users' clones contact each other. In this thesis, we propose a solution implementing an anonymous communication protocol, that leverages properties of social networks and ad-hoc wireless networks. Our solution implements a protocol supporting anonymous end-to-end communication between two users in the network, and in turn between users and their device clones in the cloud. We consider an adversary model where each party observing a portion of the communication possibly colludes with others to uncover the identity of communicating users. We then extensively analyze the security of our protocol and the anonymity preserved against the above adversaries. Finally, we run thorough set of experiments that confirmed the feasibility and efficiency of our solution. We underline that this thesis extends our work first presented at the 3rd International Workshop on Privacy, Security and Trust in Mobile and Wireless Systems. A preliminary version of the work presented in this paper has been accepted for publication in Claudio Ardagna, Mauro Conti, Mario Leone, Julinda Stefa. Preserving Smartphone Users’ Anonymity in Cloudy Days. In Proceedings of the 3rd International Workshop on Privacy, Security and Trust in Mobile and Wireless Systems (IEEE MobiPST 2013), to appear Nassau, Bahamas, June 30-August 2, 2013.

April 2013

Take Control - design, implementation and software management of a home automation system - Matteo Spimpolo - 621249 - Supervisor: Claudio Enrico Palazzi

La tesi descrive la progettazione, la realizzazione e la gestione di un impianto di domotica, parlando delle tecnologie che si possono usare sia dal punto di vista hardware che software, spiegando e motivando le scelte architetturali intraprese. Il sistema di home automation realizzato ha lo scopo di essere più economico degli altri prodotti dello stesso tipo in commercio, di garantire una buone esperienza d'uso per l'utente e di raggiungere il maggior numero di utenti possibile. A tali fini sono state usate tecnologie a basso costo come Arduino, inoltre la gestione del sistema è delegata ad un'applicazione mobile da installare su un dispositivo già in possesso dell'utente e questa applicazione è realizzata grazie a strumenti per lo sviluppo di applicazioni mobile multi piattaforma. La tesi analizza anche questo tipo di strumenti e ne confronta due in particolare.

IBSS: Intelligent Brake Support System - Prototipazione di un Sistema intelligente di Collision Detection/Avoidance tramite visione artificiale a camera monoculare per il supporto alla frenata di automezzi - Stefano Bonetta - 1014793 - Relatore: Alessandro Sperduti

Nonostante i notevoli passi in avanti fatti negli ultimi anni nei campi della prevenzione e dello sviluppo di tecnologie per il miglioramento della sicurezza stradale, al giorno d'oggi il tasso di mortalità dovuto agli incidenti stradali rappresenta ancora una vera e propria pandemia che grava economicamente ed umanamente sulle spalle della società. L'apporto dato dalla ricerca in questo campo nell'ultimo decennio ha permesso di sviluppare sistemi di guida assistita sempre più evoluti ed affidabili, la cui diffusione tuttavia sembra ancora essere ostacolata da fattori quali i costi eccessivi e la naturale diffidenza da parte degli utenti. Conseguentemente, l'esplorazione di nuove soluzioni versatili ed a basso costo che siano in grado di fornire funzionalità di supporto alla guida secondo modalità che ne favoriscano la diffusione capillare tra l'utenza costituisce un ambito di ricerca complesso ed interessante da cui trarre spunto. Il sistema proposto, denominato IBSS (Intelligent Brake Support System), cerca di fornire una risposta pragmatica al problema esposto tenendo in considerazione quei fattori che sembrano oggigiorno frenare la diffusione massiva dei sistemi di guida assistita offrendo una soluzione a bassissimo costo ed altamente adattabile basata su visione artificiale a camera monoculare.

Sviluppo e integrazione di un sistema eye tracker per applicazioni in ambito medico - Nicola Riparelli - 625417 - Relatore: Ombretta Gaggi

In questa tesi viene presentato l'applicativo Gaze Tracker, software di eye tracking e gaze estimation integrato in un progetto di riabilitazione per bambini affetti da CVI. In particolare, è proposta una soluzione low cost che impiega una nuova tecnologia di tracking, e che soddisfa la richiesta iniziale da parte del Dipartimento di Salute della Donna e del Bambino dell'Università di Padova e del Dipartimento di Psicologia Generale di tracciare il movimento dell'occhio in fase di diagnosi e riabilitazione, al fine di ottenere un ulteriore feedback riguardo l'andamento delle stesse. Vengono quindi evidenziate le problematiche riguardo l'uso di tale tecnologia in questo specifico ambiente, le soluzioni già proposte in passato, ed una alternativa economica oggetto principale della tesi.

January 2013

Cache Pollution Attacks and Detection in Named Data Networking - Marco Teoli - 606549 - Supervisor: Mauro Conti

The current Internet architecture was designed as a mean of connecting pairs of hosts and allow them to reliably exchange packets. The way we use it every day deeply changed from pure communication to (mostly) content distribution. The wish to fill the gap between the underlying architecture and the information-centric nature of the current Internet traffic has inspired many new architectures with the goal of replacing the current infrastructure. Content-Centric Networking (CCN) is one of them. In CCN named content becomes a first-class citizen. In contrast with IP, addresses are not explicit. Content consumers simply request what they want to retrieve by name; the network is in charge of delivering the correct content. The decoupling of content and its location allows, among other things, the implementation of ubiquitous caching. Named Data Networking (NDN) is a prominent implementation of the CCN paradigm. NDN's reliance on caches for performance, reliability and data replication allows an adversary to perform attacks on the architecture that are very effective and relatively easy to implement. This thesis focuses on cache pollution attacks. In these attacks, the adversary's goal is to alter cache locality, increasing cache misses and link utilization for honest consumers. We review and evaluate previous work on these attacks and their countermeasures. To perform a meaningful analysis, we simulate Internet traffic with appropriate models on a realistic network: the German Research Network (DFN). Finally, given their importance on cache resilience, we perform pollution attacks on caches that rely on different replacement policies. Our results show that such attacks can be implemented in NDN using limited resources, and that their effectiveness is not limited to small topologies. We illustrate that countermeasures designed for IP are not easily applicable to NDN. On the other hand, existing mitigation techniques targeted to NDN provide only limited relief against realistic adversaries. We propose and evaluate a new technique, designed to detect high and low rate cache pollution attacks. Our technique is based on the analysis of variation in traffic distribution as seen by individual routers. We discuss the feasibility of this technique and suggest possible improvements.

December 2012

Applicazioni mobili cross-platform: analisi e implementazione - Fabrizio Vigato - 606513 - Relatore: Claudio Enrico Palazzi

La tesi riguarda un progetto esplorativo svolto per l'azienda Visionest Srl di Padova, la quale sentiva l'esigenza di espandere il proprio business nell'ambito dello sviluppo di applicazioni cross-platform per Smart Mobile Device (SMD), quali tablet e smartphone ad oggi sempre più diffusi. L'obiettivo principale riguarda un'ampia analisi dei migliori framework di sviluppo ad oggi disponibili e la conseguente selezione del più idoneo a fornire il supporto necessario al team di sviluppo aziendale. L'utilizzo delle tecnologie Web ha richiesto di valutare le funzionalità di HTML5 a beneficio della realizzazione di applicazioni mobili. Il progetto ha anche l'obiettivo di valutare il riutilizzo dei servizi Web aziendali allo scopo di poterli integrare nelle applicazioni per SMD. Infine, il framework selezionato è stato utilizzato per l'implementazione di un prototipo, il quale costituirà la base dell'applicazione da rilasciare ad un'azienda cliente di Visionest. Le analisi e le considerazioni effettuate sono di particolare rilevanza anche per altre aziende che guardano con interesse allo sviluppo di applicazioni mobili cross-platform.

Redesigning a real time kernel for time composability - Andrea Graziano - 606509 - Supervisor: Tullio Vardanega

Time composability is a guiding principle to the development and certification process of real-time systems. Existing research has devoted considerable effort to study the role of hardware architectures and their modern accelerating features in enabling the hierarchical composition of the timing behavior of software program considered in isolation. Little attention, however, has been devoted to the effect of real-time operating system on time composability at the application level. Scope of our investigation is to study which are the characteristics needed by a kernel to ensure time composability and consequently to investigate on what are the corrective measures to be taken in current real-time systems to introduce this interesting property at the operating system level.

Row-level content classification of development emails integrating rule based systems and machine learning techniques - Tommaso Dal Sasso - 603320 - Supervisor: Fabio Aiolli

Electronic communication means have become crucial with the adoption of soft- ware at any level of everyday life; playing a central role in the coordination of collaborative, distributed development. One widely used means is represented by emails from development mailing list, which contain questions and discus- sions among developers about design choices and various issues concerning the evolution of a system. The contents in these archives could lead to consistent information e.g., describing the system’s history during its evolution, or giving a meaningful insight on the currently active development tasks. The analysis of emails poses, however, some serious challenges: the text is often noisy, and usually contains characters that make it hard to build a robust parser to auto- matically extract accurate information. Previous research addresses these issues by working at the document level, without precisely discriminating the various sections that compose a development email. In this thesis we present a classification approach, which integrates machine learning, information retrieval and parsing techniques, to enable robust email content analysis at the line level. The developed technique classifies email lines in five categories—i.e., text, junk, code, patch, and stack trace—that allows one to subsequently apply ad hoc analysis techniques to exploit the peculiarities of each category and removing the sections of the content that would entail noise, reducing the effectiveness of the analysis. We evaluated our approach on a sta- tistically significant set of emails gathered from mailing lists of four unrelated open source systems, reaching high values of precision and recall.

Configurazione automatica di Heuristics Miner++ tramite il principio MDL - Daniele Turato - 621522 - Relatore: Alessandro Sperduti

In tempi recenti, il crescente interesse per l'analisi dei processi aziendali ha spinto le principali realtà del settore della business intelligence ad integrare degli strumenti di process mining nei propri pacchetti. Questo fatto ha portato in primo piano il bisogno di strumenti intuitivi e semplici da usare, che permettano quindi di ottenere nel più breve tempo possibili dei risultati tangibili anche a coloro che non possiedono una conoscenza approfondita dell'ambito. Gli algoritmi di process mining richiedono spesso un'accurata configurazione di diversi parametri, cosa molto difficoltosa per l'utente comune. Per questa esigenza è già stato proposto un approccio di configurazione automatica relativamente all'algoritmo di mining Heuristics Miner++, che mira a sgravare l'utilizzatore finale da tale compito. L'obbiettivo di questo lavoro di tesi è quello di cercare di sperimentare possibili tecniche per migliorare l'approccio preesistente di configurazione automatica, cercando di fornire un maggiore fondamento dal punto di vista teorico, utilizzando una codifica dei log e dei relativi modelli maggiormente aderente alla formulazione autentica del principio Minimum Description Length.

September 2012

Poseidon: Mitigating Interest Flooding Attacks in Named Data Networking - Alberto Compagno - 606512 - Supervisor: Mauro Conti

Internet has been one of the most successful inventions in the last fifty years. Thanks to its fast widespread availability has become the standard way for communications. The emerging usage models and new access methods expose some limitations of the current Internet architecture, that was conceived back in 1970-s. Content-Centric Networking (CCN) is an emerging networking paradigm being considered as a possible replacement for the current IP-based host-centric Internet infrastructure. In CCN, content becomes a first-class entity and is directly named. CCN focuses on content distribution, which dominates current Internet traffic and is arguably not well served by IP. Named-Data Networking (NDN) is an example of CCN. NDN is also an active research project under the NSF-sponsored Future Internet Architectures (FIA) program. FIA emphasizes security and privacy from the outset and by design. To be a viable Internet architecture, NDN must be resilient against current and emerging threats. This thesis tries to give its contribution to the development of this new architecture. This thesis focuses on distributed denial-of-service (DDoS) attacks, especially, interest flooding - an attack class that exploits key architectural features of the NDN architecture. We initially show that Interest Flooding Attacks (IFA) is a realistic threat and we demonstrate how to implement it. We show an adversary with limited resources can use such attacks to significantly influence network performance. We provide simulations on more than one topology to obtain better and more realistic results. We the introduce Poseidon: a toolkit for detecting and mitigating interest flooding attacks. We also report on the results of extensive simulations aimed at assessing effectiveness of out countermeasure.

Euristiche per problemi di sequenziamento basate su PQRTree - Marco Orlandin - 622202 - Relatore: Luigi De Giovanni

In questa tesi vengono proposti nuovi algoritmi euristici per una classe di problemi di sequenziamento di pattern nota come MOSP, Minimization of Open Stack Problem. Gli algoritmi si basano su una rappresentazione del problema che consente di sfruttare in modo innovativo le relazioni tra matrici binarie, proprietà delle matrici Consecutive Ones e strutture dati, i PQRTree convenientemente estesi, orientiate alla rappresentazione e manipolazione efficiente di permutazioni. In questo modo, le euristiche sviluppate non lavorano esplicitamente con la sequenza dei pattern, ma direttamente sulla loro rappresentazione matriciale e sui corrispondenti PQRTree.

True concurrency and atomicity: an approach with contextual Petri nets. - Alberto Franco - 1013881 - Supervisor: Paolo Baldan

Concurrent software is notoriously error-prone due to the possible unexpected interactions between concurrently executing processes. Testing is often not effective in discovering such errors since such intereferences heavily depends on the chosen scheduling and can appear very rarely. In the thesis we propose an approach for statically proving the absence of undesired interferences in concurrent programs. The approach is based on the definition of a so-called true concurrent semantics of the program which explicitly describes the possibly concurrent computation steps and their mutual dependencies. In the analysis we focus on atomicity properties, which assert that a program block acts in any computation as it were executed in isolation although it possibly interleaves with other blocks). We consider a simple multithreaded imperative language with atomic blocks that we call Atom, we develop its semantics and formally define a weak and a strong notions of atomicity for blocks in the language. In order to endow the Atom language with a true concurrent semantics, we first define an encoding of Atom programs into contextual Petri nets, an extension of a classical model of concurrency capable of faithfully expressing concurrent read accesses to resources. Then we consider the so-called unfolding semantics of the net. The unfolding is used to characterise potential interferences, i.e. interruptions of atomic sections which can determine atomicity violations. This provides a sound technique for proving atomicity properties: the absence of potential interferences in the unfolding implies that atomicity properties are respected in the original program. From a computational point of view, the unfolding provides a description of the possible evolutions of the program which is much more compact than the explicit representation of its state space. As such it represents a mean to tackle the state-space explosion problem which normally affects the verification of concurrent programs. The theoretical framework comes along with a tool, created as a proof of concepts for the proposed approach. The tool inputs programs in the Atom language, convert them into contextual Petri nets and identifies possible atomicity violations by analisying their unfolding.

A Simulator of a Stock Market with High Frequency Trading: Implementation and Initial Evaluations. - Matteo Brunati - 621981 - Supervisor: Gilberto File'

The influence of financial markets on the everyday life is becoming day by day more important. As the stock exchanges grow of importance and trades volume rise, new technologies are being deployed to exploit computers computation power, and replace the human mind in the intra-day trading world. Since these new trading technologies have being deployed, a new kind of trading has appeared: the High Frequency Trading (HFT), which is characterized by the fact that trades are carried out at a speed that only computers can keep up. This Master thesis approaches the understanding of the intra-day price movement on stock exchanges, where HFT may be employed, thanks to a financial market simulator called finsim. This simulator uses the Actor model to define a concurrent system where several independent traders interact between each other, following a specific trading logic. In this thesis we present the background, the design, the implementation notes and the first experiments regarding finsim.

Iterative voting and multi-mode control in preference aggregation - Andrea Loreggia - 1014235 - Supervisor: Francesca Rossi

Studio dei sistemi elettorali nei quali la presenza di agenti strategici può cambiare, attraverso l’utilizzo di tecniche di manipolazione e controllo, il risultato finale. Il lavoro di tesi, partendo da risultati precedenti, cerca di ampliare la conoscenza su alcuni ambiti specifici, in particolare si articola su tre diversi scenari: quale sia la difficoltà computazionale nell’utilizzare azioni di controllo con configurazioni di budget nuove, al fine di modificare il risultato finale della votazione; il comportamento di sistemi di voto iterativo che utilizzano regole di voto non considerate finora; come l’utilizzo di azioni di controllo singole o combinate cambi il comportamento di sistemi di voto iterativi convergenti.

Sviluppo di un sistema per la diagnosi e la riabilitazione di bambini affetti da CVI - Matteo Ciman - 1014530 - Relatore: Ombretta Gaggi

Questo progetto di tesi, realizzato in collaborazione con il Dipartimento di Salute della Donna e del Bambino ed il Dipartimento di Psicologia Generale dell'Università di Padova, ha visto la realizzazione di un sistema per la diagnosi e la riabilitazione di bambini affetti da Cerebral Visual Impairment (CVI), ovvero bambini la cui difficoltà visiva è riconducibile ad un problema del cervello e della zona adibita all'elaborazione degli stimoli visivi, piuttosto che a problemi riconducibili solamente all'occhio. Il progetto ha visto la realizzazione di una Rich Internet Application (RIA), che integra due serious games atti a sviluppare capacità visive e motorie, oltre ad abilità di problem solving, e la sua integrazione con un sistema di eye-tracking, sviluppato in un altro progetto di tesi, utilizzato per tracciare lo spostamento degli occhi durante gli esercizi proposti per la riabilitazione. Viste le innumerevoli combinazioni di deficit che si possono presentare in un bambino affetto da CVI, per tutto il tempo della progettazione e della realizzazione del sistema si è mantenuto come obiettivo fondamentale quello di costruire un sistema completamente personalizzabile, in maniera tale da adattarlo al meglio alle caratteristiche di ciascun bambino. Infine, attraverso il framework PhoneGap è stata fornita la possibilità di utilizzare l'applicazione web anche su dispositivi mobile come i tablet, per permettere la riabilitazione del bambino anche a casa attraverso lo svolgimento degli esercizi proposti dal medico.

Logics and Automata for history-dependent behavioural equivalences - Alberto Meneghello - 589355 - Supervisor: Paolo Baldan

Behavioural equivalences play a key role in the formal analysis of system specifications. They can be used to equate specification which, although syntactically different, denote the same system behaviour or to state, formally, that a system enjoys a desired property. A classical dichotomy opposes the interleaving equivalences, where concurrency of actions is reduced to the non-deterministic choice among their possible linearizations, to true-concurrent equivalences, where concurrency is taken as a primitive notion. True concurrent semantics are a natural choice when one is interested in capturing properties concerning the dependencies between computational steps, but they can be convenient also because they provide some relief to the so-called state-space explosion problem in the analysis of concurrent systems. In this thesis we propose an automata-theoretic characterisation of hereditary history preserving (hhp-) bisimilarity, a widely studied true concurrent behavioural equivalence, and characterized for being the canonical equivalence for the model of prime event structures, a causal model that describe a system in terms of events and the causal and concurrent relations between such events. The goal achieved in two steps. First, relying on the work of Baldan and Crafa, we provide a characterization of hhp-bisimilarity in terms of a simple logic which predicates only on existence and executability of events.The logical characterization naturally suggests a connection with History-Dependent automata, a computational formalism for modelling systems with dynamic allocation and deallocation of resources, which allow to trace the history of such resources over time. Then we identify a class of History-Dependent automata where prime event structures can be mapped in a way that the canonical behavioral equivalence for such automata coincides with hhp-bisimilarity.

July 2012

Un approccio causale alla Non-Interferenza su reti di Petri - Giuseppe Ferri - 1014218 - Relatore: Paolo Baldan

Tra i modelli per la concorrenza figurano in particolare i modelli causali, i quali prevedono di rappresentare l’esecuzione in parallelo di due processi distinti esplicitando le relazioni di ordine e di conflitto che vi sono fra le azioni, per poter identificare quali azioni possono essere svolte in concorrenza. Interessanti proprietà di un sistema concorrente, come ad esempio l’assenza di conflitto fra azioni, l’indipendenza delle scelte da eventuali politiche di scheduling e la sequenzialità, che non sono percepite come proprietà osservazionali, sono tutte proprietà legate alla causalità delle azioni, che è una caratteristica catturata dai modelli causali, utilizzando i quali è possibile esprimere queste proprietà in modo semplice. Nell’ambito dei modelli causali, le reti di Petri sono state oggetto di numerosi studi, in quanto esse costituivano un framework generale in cui le proprietà anzidette potevano trovare espressione. Nell’ambito dello studio della sicurezza dei sistemi informatici hanno riscosso parecchia attenzione le proprietà di Non-Interferenza, ossia quelle proprietà che permettono ad un sistema l’esecuzione di attività segrete senza produrre alcun effetto visibile ad un osservatore esterno non autorizzato: in particolare quando tali proprietà sono legate alla sicurezza del flusso delle informazioni pare possibile e naturale una loro formulazione in termini di semantica causale. L’obiettivo della tesi è quindi fornire una caratterizzazione delle proprietà di Non-Interferenza in termini di semantica causale usando come modello di riferimento le reti di Petri. Più precisamente, sulla base di alcuni risultati in letteratura, la tesi mostra come la semantica di unfolding possa venir utilizzata per la verifica di proprietà di Non-Interferenza su reti di Petri safe. La validità di tale proprietà è ridotta all’assenza di particolari condizioni, dette condizioni attive causali e condizioni attive di conflitto, in un prefisso finito dell’unfolding opportunamente generato. Il fatto che tali prefissi finiti possano aver dimensione esponenzialmente più piccola rispetto al marking graph indica che la tecnica proposta può essere molto più efficiente di altre analisi proposte in letteratura basate sulla generazione del marking graph. Dunque la tesi mostra come, in ultima istanza, l’analisi della Non-Interferenza eseguita sul prefisso finito dell’unfolding o ffra prestazioni decisamente più soddisfacenti rispetto all’analisi tradizionale basata sul marking graph.

Detecting Fake Profiles in On-Line Social Networks - Marco Secchiero - 622199 - Supervisor: Mauro Conti

On-line Social Networks (OSNs) are increasingly influencing the way people communicate with each other and share personal, professional and political information. At the same time, the OSNs are attracting the interest of the malicious entities that are trying to exploit the vulnerabilities and weaknesses of the OSNs. This phenomenon brought security researchers to study security and privacy threats in the OSNs. Some of them are trying to detect and mitigate threats to individual users. Indeed, OSNs having tens or hundreds of million users collectively generate billions of personal data content that can be exploited. So, detecting and preventing attacks to individual user privacy is a major challenge. Most of the current research has focused on protecting the privacy of an existing on-line profile in a given OSN. Instead, we note that there is a risk of not having a profile in the last fancy social network. The risk is due to the fact that an adversary may create a fake profile to impersonate a real person on the OSN. The fake profile could be exploited to build on-line relationships with the friends of victim of identity theft, with the final target of stealing personal information of the victim, via interacting on-line with the victim's friends. In this thesis, we report on the investigation we did on a possible approach to mitigate this problem. In doing so, we also note that we are the first ones to analyze social network graphs from a dynamic point of view within the context of privacy threats. As a contribution, part of this work has been submitted and accepted at the IEEE/ACM Cybersecurity of On-line Social Networks Workshop and it will be presented in Istanbul on August 26, 2012.

Kernel-level implementation of routing processes typical of mobile radio telecommunications UMTS/HSPA and LTE - Michele Marchetto - 603258 - Supervisor: Claudio Enrico Palazzi

This thesis is about the kernel implementation of the forwarding procedures from S1/Iu to Gi/sGi interfaces. The software developed is is part of the UMTS/HSPA/LTE mobile infrastructure product called PRIMO. The work has been carried out in Athonet, a startup company based in Trieste, under the supervision of Gianluca Verin, co-founder of the company.

Cloud Computing security, a concrete case: SidiOpen - Mirco Geremia - 621850 - Supervisor: Tullio Vardanega

Cloud Computing has become a keyword in Information Technology in these years; many companies already adopted this model attracted by its cost-efficiency and flexibility, considering it a natural and unavoidable step to keep up with the times. However, there's always a trail of mistrust following the rise of a new technology, and this time it comes with a concrete side: the lack of control that this paradigm brings with it puts a significant question mark about the security of this solution, that risks to compromise its adoption. In this work we want to analyze the Cloud Computing security situation, discovering what are the new threats it brings up and what its impact on the old ones; we'll try also to understand whether this feared lack of control represents a real issue or not and what can be done to overcome it. Then we want to confront with a concrete case of study in order to understand the real impact of this new solutions on security. We chose to analyze SidiOpen, an information system for the Italian dioceses provided through Windows Terminal Services, a particular implementation of a Software-as-a-Service model that allows a software installed in a server to be available to customers through the network. The result we are willing to obtain both from the general analysis and from the concrete case study, is to show that security in Cloud Computing systems can be faced and solved as well as in in traditional ones, and that it doesn't represent the overwhelming obstacle that many fear.

Exploring the power of GP for Data Mining - Andrea Zanetti - 622592 - Supervisor: Alessandro Sperduti

Symbolic regression via genetic programming (GP) has proven to be a very important and powerful tool among machine learning techniques. Its application to Data Mining (DM) for extraction of interesting novel knowledge from real-world databases constitutes a very interesting research topic because of its potential and differences from more traditional DM techniques. In the scope of this thesis project we developed a GP system based on the Open BEAGLE Evolutionary Computation (EC) framework designed to carry out DM tasks on ARFF-formatted datasets including different features such as data preprocessing, validation and cross-validation capability and automatic statistics computation, while the system architecture has been designed in a modular fashion in order to be easily editable and extensible. The system has been used to conduct different GP runs on a suite of mathematical and real-world datasets in order to gather useful analytical data, in the effort to explore the power which GP have (and might have) in the DM field. These tests led to different interesting observation and issues about the application of this methodology and about the acquired results, which have been compared to the ones obtained with other classical DM techniques used as performance benchmarks. A final series of tests has benn conducted by applying the multiobjective optimization paradigm to the GP DM in the effort to maximize the trade-off between the output models accuracy and their complexity; this analysis involved the application and the comparison of two popular and competitive Multiobjective Optimization Evolutionary Algorithms (EMOAs), NSGA-II and SMS-EMOA.

April 2012

LifePuzzle: un'applicazione per la creazione collaborativa di fotolibri - Piero Bizzotto - 621711 - Relatore: Ombretta Gaggi

Il lavoro svolto in questa tesi intende trattare i dettagli riguardo la creazione di un'applicazione, costruita sulla piattaforma Apps del social network Facebook, che tramite l'utilizzo delle tecnologie web più moderne permette la condivisione di fotografie tramite fotolibri e modifica degli stessi in modo collaborativo in tempo reale, con una ulteriore possibilità di condivisione sotto forma di presentazioni animate.

Sviluppo di un sistema di raccomandazione di percorsi turistici - Michele Torresin - 622072 - Relatore: Ombretta Gaggi

In questa tesi viene presentato PhotoTrip, un servizio in grado di consigliare itinerari di viaggio contenenti punti di interesse turistico, questi vengono individuati tramite l’analisi delle fotografie contenute all’interno di Flickr , il principale servizio online di gestione e condivisione foto. Le modalità di generazione dei punti di interesse, completamente automatiche, e la quantità dei dati a disposizione, circa 350 milioni di foto contenute in Flickr aventi tag geografici, consentono a PhotoTrip di essere utilizzato in ogni parte del mondo. Inoltre permette agli utenti, che ne fossero interessati, di ottenere informazioni aggiuntive su ciò che è ritratto all’interno delle foto stesse, soddisfando così la sete di sapere dei più curiosi.

Valore strategico dell'IT Governance - Claudio Bosco - 622191 - Relatore: Tullio Vardanega

L' IT Governance è una funzione organizzativa che controlla la formulazione e l'attuazione della strategia riguardante la componente di Information Technology (IT), ossia le modalità con cui si intende gestire l'IT per soddisfare le esigenze attuali e future di un'organizzazione. A partire dalla fine degli anni '90 le tematiche riguardanti l'IT Governance hanno cominciato a riscuotere crescente interesse, anche da parte delle aziende italiane. In questa tesi vengono affrontati gli elementi che consentono all'IT Governance di fornire un valore strategico all'organizzazione, con particolare attenzione agli aspetti riguardanti la misurazione e la valutazione. Si mostra come non sia possibile definire una corretta strategia di IT Governance in mancanza di un efficace sistema di misurazione e valutazione della qualità dei processi che supportano l'erogazione dei servizi su cui si basa l'attività dell'azienda. A supporto di questa congettura vengono esposti i risultati di una rilevazione sui temi dell'IT Governance, condotta per conto di Confindustria Padova su un ampio campione di aziende del Veneto. La rilevazione trova i suoi fondamenti teorici in ITIL, per quanto riguarda la terminologia e gli aspetti di IT Service Management, e in CMMI, in particolare CMMI-SVC e SCAMPI, per le metodiche di misurazione e valutazione. I risultati ottenuti vengono confrontati con quelli di rilevazioni simili svolti in contesti in qualche modo paragonabili. Emergono problemi specifici, come la difficoltà ad adattare i framework di IT Service Management (ovvero raccolte di best practice riguardanti la realizzazione di pratiche e processi di IT Service Management) alla realtà di una piccola o media azienda, in cui le risorse in termini di tempo e personale sono spesso ridotte. Vi sono però anche elementi comuni con aziende di grandi dimensioni, come le difficoltà ad effettuare un cambio culturale e a stimolare il commitment del Alto Management. In generale i risultati ottenuti rivelano uno scarso livello globale di maturità delle aziende rilevate rispetto ai temi dell'IT Governance. Emerge anche però che, dove pratiche di IT Governance vengono concretamente applicate, si riscontra un apporto di valore, in aziende di ogni dimensione, a dimostrazione di come sia possibile adottare e adattare le pratiche alle esigenze dell'azienda. I risultati ottenuti e le considerazioni fatte sono state poi condivise tramite un evento di presentazione organizzato da Confindustria Padova, e successivamente tramite interviste a dirigenti di aziende particolarmente sensibili verso le tematiche riguardanti l'IT Governance.

Influence and Bribery in Compact Preference Structures - Alberto Maran - 603359 - Supervisor: Kristen Brent Venable

In a multi-agent context where a set of agents declares their preferences over a common set of candidates, it is often the case that such agents interact and may influence each other and therefore modify their preferences, until hopefully they reach a stable state. Recent work has modelled the influence phenomenon in the case of voting over a single issue. This thesis generalize this model to account for preferences over combinatorially structured domains including several issues. When agents express their preferences as CP-nets, we propose a way to model influence and to aggregate preferences by interleaving voting and influence convergence. We also provide results about the resistance of this setting to bribery considering different voting rules and costing schemes.

February 2012

Sentiment Analysis in Short and Informal Text - Marco Veluscek - 622214 - Supervisor: Alessandro Sperduti

Sentiment Analysis is the application of natural language processing, computational linguistics, and text classification/analytics in order to identify a piece of text as positive or negative, according to its author's general feeling. Emotions, feelings and opinions can profoundly affect individual behavior and decision-making. With the rise of the Web and the social networks, people can be influenced by a very large number of contents. This kind of content belongs to an informal domain, where emotions seem to be frequently important for expressing friendship, showing social support or as part of online arguments. The tasks of Sentiment Analysis are particular hard in an informal context, mainly because it is really difficult to find rules and common expressions in this kind of text. Moreover, usually message from social networks is short text which is even more difficult to process, due to the fact it gives just few information about the context. These are the main reasons why there are just a few algorithms able to solve this problem and their accuracy is strictly related to the specific domain for which they were designed. So, this project addresses the problem of Sentiment Analysis on informal and short text. This paper first shows a detailed description of the problem, a formal definition and abstraction, goals, challenges and some basic and most used techniques. Then, describes all the used approaches and the implemented algorithms. In the first place, we applied some unsupervised techniques from the natural language processing field together with some affective word lists. Alone this approach, let us reached a good effectiveness of 65% on a baseline of 78%. Since Sentiment Analysis can be seen as a classification problem, we also implemented and tested some classifiers from machine learning theory (e.g. Naive Bayes and Maximum Entropy). The gained accuracy, after some adjustments, was good but not better than the unsupervised approach. Although, combining the best solutions from these two different approaches, let us achieve a surprisly good accuracy of 73% on the baseline of 78%. So, what we could reasonably infer is that using Natural Language Processing techniques in conjunction with Machine Learning algorithms, allows you to reach the accuracy expected in more conventional classification problems address with machine learning approaches.

Developing a Spell Checker for Search Engine Queries - Andrea Zilio - 622488 - Supervisor: Massimo Marchiori

This work describes the development of a spell checker and corrector for search engines queries. The system detects and suggests corrections to possibly misspelled queries by generating a large set of candidates and by ranking them using a machine-learned ranking approach. About 150 feature are extracted from every query-candidate pair including statistical-based language model and error model features along with other signals that a web-scale speller should leverage. Different smoothed language models are trained on different datasets and tuned using publicly available data. We show that language models tuning, re-ranking top candidates, meta features, iterative correction and post-processing rules can significantly improve the precision of our speller, which won the third place in the recent Microsoft's Speller Challenge.

Unfolding of Contextual Petri Nets - Alessandro Bruni - 621513 - Supervisor: Paolo Baldan

The verification of concurrent systems often suffers the problem of state space explosion. When the system is described with Petri nets, a classical model for distributed and concurrent systems, a possible solution to mitigate this problem consists in using verification techniques based on the unfolding semantics. More precisely, as formerly shown by McMillan, given a finite state Petri net it is possible to construct a finite approximation of the unfolding semantic — called complete prefix — which entirely describes the behaviour of the system and can be used to efficiently verify its behavioural properties. This work focuses on the so called contextual Petri nets, an extension to Petri net able to represent the use of resources in read-only mode. In this work we studied the unfolding semantics for contextual Petri nets and provided an effective algorithm for its computation. We also studied and evaluated an unfolding approach based on the stable models semantic for general logic programs and compared it to the current unfolders written in imperative languages. Our last contribution is an efficient technique to check for reachability and deadlock conditions analysing the unfolding using the stable model semantic for logic programs.

Newsmatic: Visualizzazione automatica delle notizie sul web - Lorenzo Nesello - 603691 - Relatore: Massimo Marchiori

La tesi espone il procedimento svolto e i risultati ottenuti nella realizzazione di un aggregatore di notizie web che presenta i risultati sotto forma di immagini (cercate nel web). Legge i feed da alcuni siti di informazione e cerca gli argomenti di cui si parla. In base alla frequenza di argomenti elabora una classifica e la propone visivamente. E' possibile consultare anche tutti gli articoli relativi a quell'argomento

December 2011

FTP4Android - un framework per sviluppare una memoria remota distribuita in ambito mobile - Marco Ferrarese - 550441 - Relatore: Claudio Enrico Palazzi

Argomentazione del framework realizzato per sviluppare una memoria remota distribuita in ambito mobile

Trustworthiness in Service Oriented Computing - Nicola Miotto - 603680 - Supervisor: Claudio Enrico Palazzi

In the past years the Service Oriented paradigm has gained a growing attention, considered a revolution in the Internet age. One of the major advantages offered by this new paradigm is the possibility of automating the process of building distributed systems. A software agent should be delegated to discover the right services to be used in a composition. This would also optimize integration and reusability of software components. Many studies have addressed the different problems related to Service Oriented Architecture (SOA), like implementation, funding principles and so on. But trust provisioning is still an open challenge. In this thesis we show our research on the trustworthiness-related issues in SOA, providing a thorough investigation of the state of the art and essentially showing our analysis and proposal of a new rationale to found a new framework upon.

Event-based system for queue areas awareness - Enrico Sartorello - 622801 - Supervisor: Massimo Marchiori

Concezione, progettazione, sviluppo e testing di un sistema event-based e di un framework statistico associato per la modellazione di code in luoghi di erogazione di servizi, utilizzando come sorgenti dati reti sociali, servizi location-based, immagini (e relativo processing) e smartphone.

Portable Rich Internet Application: un caso di studio applicato ai videogiochi - Giorgia Galiazzo - 621693 - Relatore: Ombretta Gaggi

Il lavoro svolto in questa tesi ha riguardato la realizzazione di un pacchetto di serious game atti al trattamento della dislessia evolutiva in fase precoce, cioè in bambini in età prescolare in cui è stato riscontrato un rischio di sviluppo del disturbo. Il prodotto è stato realizzato sotto forma di Rich Internet Application (RIA) portabile, così da permetterne la fruizione sia da dispositivi desktop che da dispositivi touch mobile. Queste esigenze sono emerse da un'attenta analisi degli scenari di utilizzo e delle modalità d'interazione più consone al progetto. In particolare, per realizzare l'applicazione si sono valutate diverse tecnologie di sviluppo, propendendo infine per l'utilizzo di HTML5, CSS3 e JavaScript, la cui combinazione permette di realizzare delle applicazioni web interattive, senza il bisogno di plugin aggiuntivi e in grado di funzionare anche in modalità offline. Tuttavia, a causa della non completa maturità dei browser web mobile, per garantire la fruibilità del prodotto da dispositivi touch, è stato necessario avvalersi di un framework aggiuntivo, PhoneGap, che, con poche modifiche al codice, ha permesso di trasformare l'applicazione web in applicazione nativa, installabile in tutti i principali sistemi operativi mobile. Ne è risultato un prodotto perfettamente portabile e aderente alle esigenze, ovvero in grado di essere utilizzato per il trattamento della dislessia evolutiva, andando ad allenare le abilità coinvolte nella lettura in modo stimolante e piacevole per i bambini. Il progetto ha visto la collaborazione del Dipartimento di Psicologia Generale dell'Università degli Studi di Padova.

Progettazione e sviluppo di un social network per la collaborazione tra imprese - Angelo De Menis - 622200 - Relatore: Ombretta Gaggi

Il progetto trattato in questo elaborato di tesi ha come scopo la realizzazione di un social network per ambienti di business. Il progetto è stato commissionato dall'associazione Confindustria della provincia di Padova per fornire, alle aziende appartenenti al gruppo, uno strumento unificato di servizi per la collaborazione mediata da computer. Il prodotto realizzato consente alle aziende e ai loro dipendenti di creare il proprio profilo, attraverso un processo di registrazione rigido che permette l'iscrizione solo di utenti del gruppo Confindustria Padova. I documenti e le pubblicazioni interne a tale community, per la maggior parte dei casi, risultano infatti riservate. Fornisce funzionalità di collaborazione come ad esempio aree di condivisione di informazioni e documenti tra una parte dei membri. Ogni azienda iscritta potrà inoltre pubblicare la propria scheda di prodotti e servizi offerti per farsi conoscere dal resto del network. Vengono trattati dettagliatamente, all'interno dell'elaborato, sia il processo di analisi dei requisiti sia lo studio sulle principali piattaforme di social network engine che ha portato alla scelta della soluzione SocialEngine. Per ogni modifica o funzionalità realizzata, vengono descritte le scelte progettuali ed il dettaglio dell'implementazione così da garantire, negli sviluppi futuri, una solida formazione sulla realizzazione di moduli indipendenti per SocialEngine e sul framework Zend alla base della piattaforma. Il sito è stato reso pubblico a metà novembre 2011, entro i termini di tempo stabiliti. Tutti i requisiti obbligatori e desiderabili, e in alcuni casi anche opzionali, sono stati soddisfatti fornendo di fatto un prodotto completo dal punto di vista delle funzionalità richieste.

Business process management e process mining per il miglioramento dei processi aziendali. - Emanuele Fabbri - 621858 - Relatore: Alessandro Sperduti

Il presente elaborato di tesi intende illustrare le teorie di Business Process Management (BPM) e Process Mining in termini di possibilità di integrazione/ collaborazione e di possibilità di sviluppi futuri per il miglioramento dei processi aziendali. Scopo del presente elaborato è infatti documentare e analizzare questo studio, presentando i risultati ottenuti e le considerazioni fatte. Lo studio ha condotto alla realizzazione di un progetto in collaborazione con l’azienda di informatica Vecomp Software Srl di Villafranca di Verona. Il progetto, legato allo studio del caso specifico del prodotto di gestione documentale integrata “DocSuiteWeb 2010” di Vecomp Software Srl, ha condotto il percorso di ricerca verso la valutazione delle possibili sinergie tra le tecniche di modellazione business più classiche e le nuove metodologie di ricostruzione dei processi a partire dalle tracce (event log) lasciate da essi. La trattazione mostra contemporaneamente quale sia il livello di maturità che è stato raggiunto da queste metodologie gestionali, quanto si possano ritenere affidabili e quanto le aziende siano sempre più costrette a doverne fare uso nel momento in cui aumentano la propria dimensione. Lo studio degli event-log, ovvero dei testi memorizzati in modo automatico dalle applicazioni mentre vengono utilizzate, può essere utile sotto molteplici aspetti. Se i log sono scritti correttamente e con dettaglio (entro i limiti concessi dalla privacy) è possibile calcolare i processi che determinano le procedure gestite dal software, come pure valutare l’usabilità del software stesso (da un punto di vista grafico) per comprendere come organizzare le maschere grafiche per fornire un servizio migliore. Attraverso la combinazione dell’elaborazione di un modello derivato dalla configurazione del prodotto assieme ai dati di log generati dal lavoro effettivamente svolto dall’applicativo, è possibile valutare se il prodotto sia stato utilizzato nel modo atteso o in modo differente/imprevisto. La valutazione di queste differenze, detta “Conformance analysis”, se applicata in un contesto di software “workflow-driven”, apre la strada alla creazione di prodotti in grado di analizzare, valutare e migliorare se stessi in modo automatico, personalizzando il proprio funzionamento, rendendolo conforme con il comportamento richiesto da parte dell’utente finale.

September 2011

SmilingWeb, un player JavaScript per presentazioni multimediali in SMIL e SMIL Photoshow, un'applicazione per la condivisione online di fotolibri e presentazioni multimediali - Luca Danese - 603769 - Relatore: Ombretta Gaggi

La tesi si concentra sul problema della condivisione di fotografie digitali e sull'utilizzo dei social network per questo scopo. Viene utilizzato il linguaggio SMIL, uno standard W3C basato su XML, per creare un'applicazione Facebook per la condivisione di fotografie tramite fotolibri e presentazioni animate. A questo scopo è stato implementato un player in JavaScript per il linguaggio SMIL che possa funzionare su di un qualsiasi browser denominato SmilingWeb, quindi è stata creata l'applicazione SMIL Photoshow su Facebook che permette la creazione di slideshow e fotolibri che possono essere stampati oppure condivisi con gli amici online.

Valutazione di una soluzione client-server per giochi interattivi su MANET - Andrea Pavan - 622204 - Relatore: Claudio Enrico Palazzi

L'incontro tra le recenti tecnologie mobili e i videogiochi interattivi poggia le basi per la realizzazione di nuove e più coinvolgenti forme di intrattenimento. I dispositivi mobili moderni integrano componenti che consentono di instaurare reti per il gioco multiutente eliminando la richiesta di infrastrutture preesistenti. Questa peculiarità consente di avviare sessioni di gioco su reti estemporanee in qualunque luogo, anche in mobilità. L'architettura tipica dei videogiochi segue il paradigma client-server. Tuttavia, in uno scenario di gioco che coinvolga solo dispositivi mobili, accentrare le attività di gestione in un unico server può provocare la terminazione precoce delle sessioni di gioco a causa dell'elevato consumo energetico del nodo e la scarsa connettività di rete dovuta alla mobilità. Allo scopo di superare queste limitazioni è proposta la tecnica dei server di backup che consiste di introdurre nodi in grado di sostituire il server di gioco per garantire una più equa distribuzione del carico energetico e computazionale. In questa tesi sono presentati i modelli e i componenti software necessari per la costruzione di un framework di analisi, basato su simulazioni, a supporto delle ricerche condotte sullo scenario considerato. Lo strumento realizzato consente dunque di valutare l'impatto dell'introduzione della tecnica dei server di backup al fine di dimostrare il vantaggio indotto dal suo impiego.

Performance Evaluation with Realistic Mobility of a File Sharing DTN Protocol - Daniele Bonaldo - 604203 - Supervisor: Claudio Enrico Palazzi

In this thesis, we discuss and evaluate M2MShare, a DTN solution for mobile phones that leverages on nodes’ mobility and opportunistic contacts to enable proximity based file sharing. To this aim, we have integrated M2MShare in the Opportunistic Network Environment (ONE) simulator and tested its performance with realistic movement models in a map-based environment. This complex city-scale testbed includes a multitude of nodes representing real users engaged in their daily activities and movements, and allowed us to demonstrate the efficacy of M2MShare.

Assessment of Sequential Boltzmann Machines for Connectionist Lexical Processing - Alberto Testolin - 621897 - Supervisor: Alessandro Sperduti

Cognitive science is an interdisciplinary area of research related to the study of mind and intelligence from a broad range of perspectives, which comprises different characteristics of the representation and the processing of information in nervous systems. Thanks to the development of computers, new tools and ideas contributed to the growth of this challenging field. In particular, artificial intelligence researchers are interested in finding a way to reproduce into machines complex behaviours that resemble human abilities. A promising approach consists in creating computer programs that can learn from experience, adaptively modifying their behaviour depending on the information they process. This framework allows the development of flexible and powerful systems that can be very useful - sometimes indispensable - in many practical situations. At the same time, another possible application of these learning systems is to simulate biological nervous systems, thus providing important insights into their functioning. In this work we explore a family of innovative learning models that can effectively manipulate sequential data and therefore can handle temporal information. Time underlies many complex human behaviours, hence these models can be exploited to investigate interesting cognitive processes. In particular, our aim here is to explore some aspects of a peculiar human skill, intrinsically sequential, that is the ability to communicate with other individuals using a rich variety of procedures which constitute the language. Although the main purpose of this analysis is to focus on cognitive skills, these models might also be used in several practical applications, where contextual information should be taken into account in order to act properly. Due to the elevate computational complexity of these learning algorithms, special attention will be devoted to explore efficient implementations, in particular exploiting a recently introduced programming paradigm that allows to use modern graphical processors in order to carry out parallel computations.

Gestione lato Gateway della coesistenza in ambito wireless multihop di flussi VoIP e TCP - Michele Bortolato - 606548 - Relatore: Claudio Enrico Palazzi

L’utilizzo sempre maggiore delle reti wireless sta mettendo in evidenza la necessità di rendere tali reti in grado di supportare i carichi di lavoro tipici delle reti cablate tradizionali, ciò significa fare in modo che gli utenti possano usufruire delle tecnologie comunicative recenti anche in scenari con alto tasso di interferenza o di mobilità. Nonostante stia avvenendo una vera e propria migrazione dall’ambiente cablato verso una infrastruttura wireless (almeno per quanto riguarda la parte terminale) le prestazioni in alcune situazioni non possono dirsi ancora ottimali. Se, per esempio, si cercano di far coesistere flussi dati e flussi real ti- me accadrà che i primi eviteranno ai secondi di giungere a destinazione in maniera appropriata aggiungendo ritardi apparentemente ingiustificati ed un alto jitter. Capire le cause effettive di tale problema non è semplice e soprattutto intervenire in questi casi non sempre è possibile, data la potenziale variabilità della topologia dello scenario ed una difficile stima delle prestazioni ottenibili. Questa tesi presenta la realizzazione dell’algoritmo SAP-MH/SB adatto per scenari misti dove lo scenario wireless è di tipo multihop e si dispone di un gateway unico che fa da tramite tra la zona cablata e la zona wireless, essendo il gateway l’unico punto di contatto tra i due scenari questo è in grado di monitorare tutto il traffico e di applicare eventuali forme correttive. SAP-MH/SB agisce sui flussi TCP regolando le advertised window degli ACK di ritorno in modo da evitare un sovraccarico trasmissivo da parte degli agenti, cercando di assegnare equamente la banda per ciascun flusso TCP. Si è visto che il semplice monitoraggio dei tempi di ritardo nel buffer del gateway è sufficiente per garantire prestazioni accettabili, consentendo al flusso real time che scorre parallelamente di avere ritardi ragionevoli.

Soluzione di Business Intelligence presso Diesel - Intimate Division - Tommaso Villanova - 606510 - Relatore: Susi Dulli

Soluzione personale di Business Intelligence e sviluppo dell'algoritmo di Agrawal nell'ambiente Intimate Division-Diesel

July 2011

Trace JIT as Abstract Interpretation of Trace Semantics - Stefano Dissegna - 622261 - Supervisor: Francesco Ranzato

Tracing is a compilation technique that leverages runtime profiling of programs to find often executed paths and compile them at runtime. Its use is gaining a lot of traction especially for the compilation of dynamic languages where a lot of the information necessary to optimize the code is available only at runtime, making static compilation techniques less effective. The differences with traditional compilers pose the question of which optimizations are sound for tracing compilers. This thesis proposes a theoretical framework for tracing JIT compilation in which correctness of optimizations can be formally studied. The framework is based on abstract interpretation of the trace semantics of programs. We use it to formalize and prove the correctness of dead store elimination, type specialization, overflow test removal and guard implication. We also show the soundness of an existing optimization for allocation removal. We then show how an existing model for trace compilation can be expressed in terms of our framework.

Play With Eyes: uno strumento per lo screening visivo in età pediatrica - Alberto De Bortoli - 603482 - Relatore: Ombretta Gaggi

In questa tesi viene presentato lo strumento “Play With Eyes”, un serious game utilizzabile sia per effettuare screening visivo a partire dall'età prescolare sia per essere usato nelle visite oculistiche specialistiche. Lo strumento, che presenta un’architettura hardware e software basata su tecnologia Apple, è pensato per essere usato nelle scuole dell’infanzia da parte di personale non medico, abbattendo i costi ma allo stesso tempo consentendo uno screening che permetta di rilevare problemi evidenti legati all’apparato visivo, in particolare l'ambliopia. Il gioco prevede che il bambino utilizzi un dispositivo smartphone e risponda tramite operazioni touch in base a ciò che vede sul display posizionato alla corretta distanza, similmente a quanto avviene durante una visita oculistica. I risultati dello screening, che contengono informazioni utili riguardo la visione del bambino, vengano salvati per successive analisi. Lo strumento è stato testato presso la Scuola dell’Infanzia “Gianni Rodari” di Mogliano Veneto e il progetto ha visto la collaborazione del Dipartimento di Pediatria Salus Pueri dell’Università degli Studi di Padova

Implementation and Integration of a RANAP Module for a 3G Communication System - Luca Dei Zotti - 606172 - Supervisor: Claudio Enrico Palazzi

This thesis is about the implementation and integration of the Radio Access Net- work Application Part (RANAP) protocol, part of the UMTS signaling over the Iu-Interface. The work has been carried out in Athonet, a startup company based in Trieste, under the supervision of Gianluca Verin, co-founder of the company. During the work the RANAP protocol has beed updated from 3GPP Release 4 to the latest available specification of 3GGP Release 9, 3GPP TS 25.413 v9.5.1. The RANAP protocol is part of the protocol stack used in the company’s mobility gateway pro- duct which is part of the UMTS/HSPA/LTE mobile infrastructure product called PRIMO. Note: according to the Non-Disclosure Agreement (NDA) stipulated at the very beginning of the traineeship, and due to the very nature of the product, which in- volves interaction with cutting edge technology and third parties documents covered by NDA, part of the work carried at Athonet may not be disclosed. However, it is the author’s opinion that the architectural semplifications made for this document are clear enough to give an accurate idea of the work that has been done.

Sviluppo di un serious game per l'image labeling finalizzato alla ricerca di tag specifici - Andrea Giavatto - 606511 - Relatore: Claudio Enrico Palazzi

La precisione e l’accuratezza delle ricerche testuali nel Web sono au- mentate notevolmente negli ultimi anni. I motori di ricerca continuano ad affinare la qualità dei loro risultati fornendo risultati sempre più accurati in tempi rapidissimi. Tuttavia la ricerca di immagini ha goduto solo in parte di questi mi- glioramenti a causa della difficoltà nel catalogarle efficacemente in modo automatico. Questo spunto ha permesso di ideare un serious game che sfrutta il collaborative tagging per etichettare in modo accurato una grande quantità di immagini.

Progettazione e valutazione sperimentale di algoritmi simbolici per il preordine di simulazione - Guido Piero Zanetti - 585439 - Relatore: Francesco Ranzato

Il lavoro presentato in questa tesi introduce tre nuovi algoritmi per il calcolo del preordine di simulazione su strutture LTS. Lo scopo di questi algoritmi è migliorare il compromesso tra quantità di memoria richiesta e tempo di esecuzione degli algoritmi presenti in letteratura. Migliorare questo compromesso significa poter calcolare il preordine di simulazione su input di dimensioni sempre maggiori portando, di conseguenza, effettivi vantaggi nel campo della verifica formale e in particolare alle tecniche di Model Checking. Gli algoritmi proposti prevedono l'utilizzo delle strutture dati Reduced Ordered Binary Decision Diagram (ROBDD) per la simbolizzazione delle informazioni necessarie al calcolo. Uno studio comparativo tra gli algoritmi presentati e gli algoritmi presenti in letteratura evidenzia come l'introduzione degli ROBDD permetta di ottenere vantaggi in termini spaziali mantenendo comunque prestazioni computazionali efficienti.

April 2011

Studio di tecniche di Apprendimento Automatico per l’analisi e la classificazione di messaggi di posta elettronica. - Martina Astegno - 603687 - Relatore: Alessandro Sperduti

Il progetto di tesi si focalizza sullo studio e sulla valutazione di tecniche di ML da adottare per realizzare un sistema in grado, sulla base del modello appreso in una fase iniziale, di classificare le e-mail provenienti da una casella di posta dedicata. Il classificatore assegna ad ogni messaggio la classe di appartenenza scegliendo tra quelle all’interno della tassonomia fissata a priori. Vengono quindi illustrate tutte le tecniche e analisi, con i relativi test, che sono stati eseguiti per raggiungere il maggior valore di accuracy durante la classificazione.

Sviluppo di un Sistema di Localizzazione Indoor Basato su Marker Visivi Artificiali - Daniele Battaglia - 603684 - Relatore: Claudio Enrico Palazzi

La grande diffusione di smartphone degli ultimi anni e l'aumento delle loro prestazioni hanno aperto la strada allo sviluppo di nuove applicazioni. Queste possono trarre vantaggio dai diversi tipi di sensori e interfacce che coesistono nei dispositivi mobili. Lo scopo della tesi è quello di individuare un sistema per la localizzazione indoor di questi dispositivi che possa essere utilizzato come base per lo sviluppo di applicazioni location-aware. Nella tesi vengono prima analizzati i sistemi proposti in letteratura basati su onde radio e ne viene discussa l'applicabilità in contesti reali. Successivamente viene descritto il prototipo sviluppato basato su marker visivi artificiali discutendone in dettaglio le problematiche e le prestazioni ottenute.

Contributions to Model-Driven Engineering Infrastructures: from Target Languages to Model Editor Environments - Alessandro Zovi - 565845 - Supervisor: Tullio Vardanega

The work described in this thesis is positioned across two European projects: the ASSERT project and the CHESS project. The two projects have several commonalities and are both rooted on the adoption of a Model-Driven Engineering process for the development of high-integrity real-time software. The work of the author in the two was however on very different aspects. The former was the occasion of experimenting with the generation of source code targeting the Real-Time Specification for Java (RTSJ), in a manner amenable to the constraints and limitations of the target platforms of interest, which are embedded and shall exhibit a predictable behavior in the time and space dimensions. In this part (I) the RTSJ features which reduce predictability and static analyzability are discarded and then (II) the implementation decisions of the code generator are discussed by taking in consideration the limits and peculiarities of RTSJ. The latter was a concrete chance to engage in an international project with important industry partners. This part addresses the creation of a design environment to support a novel component-oriented approach rooted in Model-Driven Engineering; in particular, it describes the implementation of design views, on-the-fly verification and automation facilities.

A Comprehensive Analysis of TCP Variants through Realistic Simulation Testbed - Alessandro Eccher - 568678 - Supervisor: Claudio Enrico Palazzi

With TCP/IP communications between computer networks became possible. TCP, which among all is the primal protocol in charge of data transport, has been subject of a constant research in order to keep its efficiency high and exploit the latest technical innovations. Several TCP proposals have been developed until now and in this work we compared some of the most promising: Vegas, BIC, CUBIC, Hybla, FAST, Compound and Libra. To date many studies exist on those protocols which however utilized ad hoc testbeds for their evaluations. This fact prevented a direct comparison. In addition most of them favored simple network models respect to realistic ones, so it is still unclear how TCP implementations would behave on the Internet. In this thesis we have finally addressed those limits and produced an impartial evaluation of the aforementioned implementations over a realistic Internet-like simulation scenario. In our analysis we focused mainly on the features of efficiency, RTT-fairness and friendliness toward Newreno which are the main requisites for the new TCP proposals.

February 2011

Monitoraggio di sensori ambientali in rete P2P - Alberto Zatton - 604214 - Relatore: Claudio Enrico Palazzi

Le reti P2P hanno sempre avuto alte aspettative per le caratteristiche di flessibilità, costo, scalabilità, ridondanza dei dati che le contraddistinguono. Con questo lavoro si vuole dimostrare come il P2P non sia solo sinonimo di file sharing ma un modello valido per la realizzazione di un'applicazione commerciale per la condivisione di risorse e informazioni. In particolare si analizzerà la situazione dei Consorzi di Bonifica del Veneto, ognuno dei quali detiene i dati ambientali raccolti dai sensori dislocati nella propria porzione di territorio. Si studierà una soluzione per la condivisione dei dati tra i Consorzi, preferendo l'approccio P2P al modello Client/Server dopo aver valutato pro e contro di entrambi. Si dimostrerà la validità di JXTA come framework P2P sul quale basare l'applicazione. Si realizzerà ResourceNet, una piattaforma modulare basata su JXTA e scritta in Java in grado di condividere qualsiasi tipologia di risorsa, sia essa hardware, software o semplice informazione, tra i peer della rete. Si mostrerà come sono stati realizzati i moduli di ResourceNet che permettono ai Consorzi di condividere i dati dei sensori e monitorare i sensori condivisi attraverso un'interfaccia web-based ed utilizzando Google Maps.

December 2010

Un algoritmo branch-and-price per l'assegnamento dei veicoli sui piazzali aeroportuali - Mattia Barbieri - 606173 - Relatore: Luigi De Giovanni

L’incremento del traffico aereo negli ultimi anni ha sensibilmente aumentato la densità di aereoplani nello spazio aereo e ha causato una forte congestione nei maggiori aeroporti. A questi problemi viene data sempre maggiore attenzione, come testimoniato, ad esempio, dal progetto europeo “Integrated Airport Apron Safety Fleet Management – AAS”. Facendo riferimento a questo progetto, questa tesi cerca di risolvere in maniera efficiente il problema dell’assegnamento dei mezzi di supporto alle operazioni che si svolgono nell’apron (Ground Service-support Equipment, GSE) alle varie operazioni richieste da ciascun velivolo in sosta nell’apron (task). Viene proposto un approccio esatto al problema basato su una formulazione di Programmazione Lineare Intera. Questa tecnica si basa sulla definizione di un modello matematico e sull’applicazione di appositi algoritmi di ottimizzazione. Per raggiungere l’obiettivo consideriamo un modello a partizione basato su variabili di cammino e applichiamo una strategia risolutiva basata sulla generazione di colonne. L'algoritmo di branch-and-price così sviluppato si appoggia sul framework SCIP (Solving Constraint Integer Programs) per la sua implementazione.

Paleographic document analysis and writer identification - Manuel Giollo - 602866 - Supervisor: Fabio Aiolli

Through centuries, mankind produced a huge amount of handwritings, which describe the whole history and our past. In order to recover all this precious information and place them in the right years and countries, paleographers analyze the morphology of writing in ancient scripts and try to guess important relationship among documents. Unfortunately, but very important, experts' analysis can be highly subjective, due to their personal experience and culture, so it is very important to help such work with objective metrics. Computer science can be an helpful instrument in this sense, so the thesis goal is the study of state-of-art techniques useful in document images analysis and their application in historical texts. The task is quite complex, since few efforts have been done over this kind of scripts and lots of issues make the purpose rather ambitious, so the results of the thesis have to be considered just the first step toward a reliable, robust and effective system which could really help paleographers.

A critique of service orientation: from promises to practices - Andrea Baldovin - 565909 - Supervisor: Tullio Vardanega

The service-oriented architecture (SOA) is a recent paradigm for software architecture design and implementation. In this work we first review the object-oriented and the component-based development paradigms, which can be considered the ancestors of service orientation. This allows to make a comparison and to identify common traits among the mentioned architectural styles. We then proceed to analyze service orientation, both from a conceptual and from a technical point of view, to verify whether the founding principles of this paradigm can be actually implemented in practice, and what is the effort required to achieve this goal. Finally, a case study is presented to demonstrate some of the considerations produced along this work.

September 2010

Aggregating compactly represented preferences - Giorgio Dalla Pozza - 602752 - Supervisor: Francesca Rossi

We consider a scenario where several agents express their preferences over a common set of variable assignments, by means of a soft constraint problem for each agent, and we propose a procedure to compute a variable assignment which satisfies the agents’ preferences at best. Such a procedure considers one variable at a time and, at each step, asks all agents to express its preferences over the domain of that variable. Based on such preferences, a voting rule is used to decide on which value is the best for that variable. At the end, the values chosen constitute the returned variable assignment. We study several properties of this procedure and we show that the use of soft constraints allows for a great flexibility on the preferences of the agents, compared to similar work in setting where agents model their preferences via CP - nets, where several restrictions on the agents’ preferences need to be imposed to obtain similar properties. We also provide an experimental study that shows for several voting rules that applying them sequentially yields a considerable saving in time while providing winners that satisfy the voters as much as the solutions that would have been chosen by applying the rule directly on the induced ordering.

La certificazione storica del web: il progetto History Mark - Stefano Rigato - 546844 - Relatore: Massimo Marchiori

History Mark consiste in un servizio (o applicazione) web che offre la possibilità ai suoi utenti di effettuare delle certificazioni sulle proprie pagine web. Tali certificazioni hanno l’obbiettivo di fornire una garanzia di esistenza non solo dei contenuti testuali ma anche della struttura stessa della pagina web in un preciso istante di tempo. Questi propositi sono raggiunti attraverso la creazione di certificati temporali, che effettuano una sorta di marchio digitale inoppugnabile della pagina, garantito da History Mark stesso.

Kernel per grafi: nuovo approccio basato su DAG - Nicolò Navarin - 603685 - Relatore: Alessandro Sperduti

Questa tesi di machine learning propone un contributo nel contesto dei metodi kernel, in particolare dei kernel per grafi . Viene infatti definito un nuovo kernel basato su un invariante per grafi, anch'esso definito in questa tesi. Inoltre vengono definiti alcuni kernel su DAG, un particolare tipo di grafo aciclico, che sono impiegati nella definizione del kernel per grafi.

Studio ed implementazione di un approccio collaborativo per il recupero semantico in un sistema per l'analisi di documenti paleografici - Federico Venturin - 566336 - Relatore: Fabio Aiolli

La mancanza di certezze nell'ambiente paleografico ha portato alla nascita del progetto SPI. L'idea alla base di tale progetto non è di sostituire il paleografo e la sua opera, ma bensì di apportare uno strumento ulteriore di analisi; uno strumento che non sia legato alla soggettività del paleografo o di una corrente di pensiero, ma che sia basato esclusivamente su tecniche statistiche e quindi per loro natura oggettive. Questa tesi si colloca nell'ambito del progetto SPI ed ha avuto come obiettivo lo studio e la successiva implementazione di un approccio collaborativo per il recupero semantico delle risorse paleografiche in tale sistema. L'intenzione è quella di permettere ad una comunità di utenti di condividere in modo collaborativo, non solo le risorse paleografiche, ma anche i risultati delle analisi effettuate su di esse ed i metadati (generati dagli utenti stessi) che le descrivono. Questa conoscenza potrà poi essere sfruttata per il recupero ed il successivo ordinamento di risorse paleografiche presenti nel sistema come risposta a query di tipo semantico.

July 2010

A Delay Tolerant Solution for P2P file sharing in MANETs - Armir Bujari - 586980 - Supervisor: Claudio Enrico Palazzi

Mobile phones have already evolved from simple voice communication means into a powerful device able to handle multimedia documents, personal productivity applications, and all sort of connections to the Internet. Due to their low cost, they are growing in popularity and might eventually become the dominant mode by which users interconnect; e.g. by establishing opportunistic P2P ad-hoc connections exchanging information of interest just passing by each other. It is hence expected to see a popular application such as file sharing to become widely utilized even in this context. Despite this, P2P applications for Mobile Ad-hoc Networks (MANETs) in contrast to the wired Internet counterparts are still in their infancy. Due to the low density of mobile nodes or their limit in wireless radio range, continuous network connectivity cannot be sustained between wireless mobile phones, thus embodying a delay/disruption tolerant network (DTN). Indeed DTNs are used in supporting communications in situations with intermittent connectivity, long or variable delay, and high error rates - characteristics that common them with the wireless mobile world. They use (i) an asynchronous communication model (modeled after email) rather than rely on end-to-end communication and (ii) message replication techniques in order to maximize the probability of data delivery to destination. In this context, we have created M2MShare a P2P file sharing application for local ad-hoc disconnected networks. Our approach is based on an application layer overlay network where overlay routes are set up on demand by the search algorithm, closely matching network topology and transparently aggregating redundant transfer paths on a per-file basis. Moreover, M2MShare adopts the idea of a DTN into the mobile world addressing node density issue by providing means for an asynchronous information exchange similar to that of DTNs. It models the idea of a DTN in an infrastructure less environment where both source of the request and destination of the data are the same entities and intermediary nodes (servants) store-delegate-and-forward back the requested data. This forwarding path is dynamically established, each individual node locally selects the next best suited hop based on a metric defined at the protocol level and this process is entirely user-transparent. Mobility is not seen as an obstacle instead, we leverage user-device mobility to address the node density problem.

Integrazione di informazioni a priori per classificazione di dati da microarray - Francesco Zarpellon - 565832 - Relatore: Fabio Aiolli

Oggetto della tesi è lo studio delle tecniche informatiche, in specifico quelle di machine learning, applicate al campo dell’analisi dei dati provenienti da esperimenti scientifici ottenuti utilizzando la tecnologia dei microarray, e l’applicazione pratica di alcune tecniche di classificazione supervisionata a dati reali, con l’ideazione di una tecnica per integrare informazioni a priori sui dati per migliorare le prestazioni di classificazione di uno specifico algoritmo, SVM. Il lavoro si inserisce nel contesto di un progetto di ricerca interfacoltà dell’Università degli studi di Padova, che coinvolge il Dipartimento di Matematica Pura e Applicata, il Dipartimento di Ingegneria dell’Informazione e il Dipartimento di Biologia, al quale questo elaborato ha contribuito.

Sensor Data Gathering in Urban Vehicular Networks - Fabio Pezzoni - 587055 - Supervisor: Claudio Enrico Palazzi

Inter-vehicle Communication (IVC) is emerging in research prominence relying on direct communication between vehicles to satisfy the communication needs of a large class of applications. In this work we propose a solution for application based on data-gathering, that is the collection of information within a geographic region making use of vehicles as data sources and using IVC systems for the transmission of collected data. Two protocols have been designed: PAGUS, an abiding geocast protocol that geocast the query within the region of interest and VDG that actually collect data and forward it toward a fixed base station. Proposed solution aims to achieve the goal of gathering data optimizing the bandwidth consumption.