Phd courses 2013

Security at work

Title: Security at work

Lecturer: Prof. Luca Viganò


In the Internet of Services (IoS), systems and applications are no longer the result of programming components in the traditional meaning but are built by composing services that are distributed over the network and reconfigured and consumed dynamically in a demand-driven, flexible way. However, composing services leads to new, subtle and dangerous, vulnerabilities due to interference between component services and policies, the shared communication layer, and application functionality.
I will present the AVANTSSAR Platform and the SPaCIoS Tool, two integrated toolsets for the formal specification and automated validation of trust and security of applications in the IoS at design time and run time, respectively. Both toolsets have been applied as a proof of concept on a set of security problem cases drawn from industrial and open-source IoS application scenarios, thereby paving the way to transferring project results successfully to industrial practice and to standardization bodies and open-source communities.
I will present also a number of particular results that have been obtained in the AVANTSSAR and SPaCIoS projects, such as previously unknown attacks, compositionality results, novel attacker models and techniques for efficient security verification and testing.


May 27 – June 5
Sala Seminar Ovest 11-13
(additional 4h t.b.a.)

Iterative rounding

Lecturer: Prof. Fabrizio Grandoni

Period: April 8-12,  May 6-10, 2013



Attendees are expected to be familiar with elementary notions of linear algebra, probability theory and, possibly, complexity theory and linear programming. However, all the needed definitions and lemmas will be recalled during the seminars.


Iterative Rounding is a recent, and very powerful tool to design approximation algorithms. The basic idea is as follows. One solves a (carefully chosen) linear programming relaxation of the considered NP-hard  problem. Then one rounds some variable in the fractional solution (which corresponds to fixing part of the solution under construction) according to proper rounding rules.

The problem is then simplified, and the process is iterated on the residual problem until a solution to the original problem is obtained. Alternatively or in combination to rounding, one can also relax (i.e. drop) one constraint. This leads to “slightly” infeasible solutions. In these seminars we will describe a representative sample of the most relevant results obtained via iterative rounding in the literature.

The seminars will be tentatively organized as follows. In the first week, we will introduce approximation algorithms, and present a few foundamental results and techniques in the area. The second week will be devoted to approximation algorithms based on linear programming. We will first introduce linear programming, and then present some LP-based techniques in approximation algorithms. The final part of the week will be devoted to iterative rounding.

Place: Sala Seminari W


April 8-12  and  May 6-10
Mon: 16 – 18
Tue, Wed, Thu, Fri: 9 – 11

Diffusion of information in static and dynamic graphs

Lecturer: Prof. Pierluigi Crescenzi

Period: 8-16 Luglio, 2013


Rumor spreading is a well-known gossip-based distributed algorithm for disseminating information in large networks. According to the synchronous push version of this algorithm, an arbitrary source node is initially informed, and, at each time step (a.k.a., round), an informed node u chooses one of its neighbors v uniformly at random, and this node becomes informed at the next time step. In the symmetric pull version of the algorithm, at each time step, a not informed node u randomly chooses one of its neighbors v; if v is informed, then u becomes informed at the next time step.

Finally, the push-and-pull version is a combination of the two previous versions, in which, at each time step, each informed node executes a “push operation”, and each not informed node executes a “pull operation”. Rumor spreading was first introduced in the context of replicated databases, as a solution to the problem of distributing updates and driving replicas towards consistency. Successively, it has been proposed in several other application areas, such as failure detection in distributed systems, peer-sampling, adaptive machine discovery, and distributed averaging in sensor networks. Apart from its applications, rumor spreading has also been deeply analyzed from a theoretical and mathematical point of view. In particular, the completion time of rumor spreading, that is, the number of steps required in order to have all nodes informed, has been investigated in the case of several different network topologies, such as complete graphs, hypercubes, random graphs, and preferential attachment graphs. Besides obtaining bounds on the completion time of  rumor spreading, most of these works also derive deep connections between the completion time itself and some classic measures of graph spectral theory, such as, for example, the conductance of a graph. The techniques and the arguments adopted in these studies strongly rely on the fact that the underlying graph is “static” and does not change over time. It is then natural to ask ourselves what is the speed of rumor spreading in the case of “dynamic” networks, where nodes and edges can appear and disappear over time (several emerging networking technologies such as ad hoc wireless, sensor, mobile networks, and peer-to-peer networks are indeed inherently dynamic). In this dynamic environment, even in the case of the simplest communication protocol that implements the broadcast operation, that is, the flooding protocol (according to which a source node is initially informed, and, whenever  an uninformed node has an informed neighbor, it becomes informed itself at the next time step), it has been shown that evolving graphs can exhibit communication properties which are much stronger than static networks. In this course, we will first review several results concerning the completion time of rumor spreading in the case of static networks. We will then present some results concerning the completion time of the flooding protocol, which have been obtained in the case of some interesting graph evolution models. Finally, we will present very recent results concerning the completion time of the push version of rumor spreading in the case of dynamic graphs.

Place: Sala Seminari Ovest


Lunedi’ 8 Luglio: 9-12
Lunedi’ 8 Luglio: 15-17
Martedi’ 9 Luglio: 9-12
Martedi’ 9 Luglio: 15-17

Lunedi’ 15 Luglio: 9-12
Lunedi’ 15 Luglio: 15-17
Martedi’ 16 Luglio: 9-12
Martedi’ 16 Luglio: 15-17