Lunedì 24 settembre – Approximating the Incremental Knapsack Problem

Lunedì 24 settembre 2018 alle ore 12.00, presso la sala riunioni della sez. di Informatica e Automazione del Dipartimento di Ingegneria dell’Università Roma Tre, il prof. Ulrich Pferschy dell’Università di Graz terrà un seminario dal titolo:

Approximating the Incremental Knapsack Problem


We consider the 0-1 Incremental Knapsack Problem (IKP) where the capacity grows over time periods and if an item is placed in the knapsack in a certain period, it cannot be removed afterwards. The contribution of a packed item in each time period depends on its profit as well as on a time factor which reflects the importance of the period in the objective function. The problem calls for maximizing the weighted sum of the profits over the whole time horizon.

In this work, we provide approximation results for IKP and its restricted variants. In some results, we rely on Linear Programming (LP) to derive approximation bounds. We first manage to prove the tightness of some approximation ratios of a general purpose algorithm currently available in the literature and originally applied to a time-invariant version of the problem. We also devise a Polynomial Time Approximation Scheme (PTAS) when the input value indicating the number of periods is considered as a constant. Then, we add the mild and natural assumption that each item can be packed in the first time period. For this variant, we discuss different approximation algorithms suited for any number of time periods and for the special case with two periods.

Joint work with Federico Della Croce and Rosario Scatamacchia


Per informazioni rivolgersi a G. Nicosia (, tel. 06 57333455)

Venerdì 9 dicembre – Securing Promiscuous Use of Untrusted USB Thumb Drives in Industrial Control Systems

QUANDO: Friday December 9th at 14:30
DOVE: Via della Vasca Navale, 79 – Sala riunioni (1.10) primo piano
TITOLO: Securing Promiscuous Use of Untrusted USB Thumb Drives in Industrial Control Systems

ABSTRACT — Industrial Control Systems (ICS) are sensible targets
for high profile attackers and advanced persistent threats, which
are known to exploit USB thumb drives as an effective spreading
vector. In ICSes, these devices are widely used to transfer files
among disconnected systems and represent a serious security
risks, since, they may be promiscuously used in both critical and
regular systems. We show a method that adopts cryptographic
techniques to inhibit critical machines from reading possibly
malicious files coming from regular machines on untrusted USB
thumb drives. Our approach exposes limited attack surface for
any malware, even those based on zero-days. We do not require
users to change the way they use removable storage devices, or
to authenticate. Our approach can be adopted for disconnected
machines and does not need complex key management. We
describe the architecture of our solution and provide a thorough
analysis of the security of our approach in the ICS context.

TITLE: USBCheckIn: Preventing BadUSB Attacks by Forcing Human-Device Interaction

ABSTRACT — The BadUSB attack leverages the modification of
firmware of USB devices in order to mimic the behaviour of a
keyboard or a mouse and send malicious commands to the host.
This is a new and dreadful threat for any organization. Current
countermeasures either require special USB devices or ask the
user to decide if the device can be used.
We propose a new approach that, before allowing the device
to be used, forces the user to interact with it physically, to
ensure that a real human-interface device is attached. Our
implementation is hardware-based and, hence, can be used with
any host, comprising embedded devices, and also during boot,
i.e., before any operating system is running. Our approach does
not require any special feature from USB devices.

An Efficient Partial Coverage Algorithm for Wireless Sensor Networks


Venerdì 17 giugno alle ore  12:00.

====== DOVE======
Dipartimento di ingegneria
Sezione di Informatica e Automazione
Via della Vasca Navale, 79
Sala riunioni – Primo piano


An Efficient Partial Coverage Algorithm for Wireless Sensor Networks


Habib Mostafaei

PhD student in Computer Science and Automation

Roma Tre University


Wireless sensor networks (WSNs) are currently adopted in a vast variety of domains. Due to practical energy constraints, in this field minimizing sensor energy consumption is a critical challenge. Sleep scheduling approaches give the
opportunity of turning off a subset of the nodes of a network without suspending the monitoring activities performed by the WSN—in order to save energy and increase the lifetime of the sensing system. Our study focuses on partial coverage, targeting scenarios in which the continuous monitoring of a limited portion of the area of interest is enough. In this paper, we present PCLA, an efficient algorithm based on Learning Automata that aims at minimizing the number of sensors to activate, such that a given portion of the area of interest is covered and connectivity among sensors is preserved. Simulation results show how PCLA can select sensors in an efficient way to satisfy the imposed
constraints, thus guaranteeing better performance in terms of both working-node ratio and WSN lifetime. Also, we show how PCLA outperforms state-of-the-art partial-coverage algorithms.

Joint work with A. Montieri, V. Persico, A. Pescape

1 giugno ore 14:00 – Seminari di Valentino Di Donato, Marco Di Bartolomeo e Gabriele Lospoto

=== Quando ===
Mercoledì, primo giugno ore 14:00

=== Dove ===
  Dipartimento di Ingegneria
  Sezione di Informatica e Automazione
  Via della Vasca Navale, 79
  Sala riunioni  – Primo piano



=== Title ===
  NetFork: Mapping Time to Space in Network Visualization

=== Speaker ===
  Valentino Di Donato
  PhD Student in Computer Science and Automation
  Roma Tre University

=== Abstract ===
Dynamic network visualization aims at representing the evolution of relational information in a readable, scalable, and effective way. A natural approach, called ‘time-to-time mapping’, consists of computing a representation of the network at each time step and animating the transition between subsequent time steps. However, recent literature recommends to represent time-related events by means of static graphic counterparts, realizing the so called ‘time-to-space mapping’. This paradigm has been successfully applied to networks where nodes and edges are subject to a restricted set of events: appearances, disappearances, and attribute changes. In this paper we describe NETFORK, a system that conveys the timings and the impact of path changes that occur in a routing network by suitable time-to-space metaphors, without relying on the time-to-time mapping adopted by the play-back interfaces of alternative network monitoring tools. A user study and a comparison with the state of the art show that users can leverage on high level static representations to quickly assess the quantity and quality of the path dynamics that took place in the network.

Joint work with M. Patrignani and C. Squarcella



=== Title ===
  There is More to Streamgraphs than Movies: Better Aesthetics via Ordering and Lassoing

=== Speaker ===
  Marco Di Bartolomeo
  PhD Student in Computer Science and Automation
  Roma Tre University

=== Abstract ===
Streamgraphs were popularized in 2008 when The New York Times used them to visualize box office revenues for 7500 movies over 21 years. The aesthetics of a streamgraph is affected by three components: the ordering of the layers, the shape of the
lowest curve of the drawing, known as the baseline, and the labels for the layers. As of today, the ordering and baseline computation algorithms proposed in the paper of Byron and Wattenberg are still considered the state of the art. However, their
ordering algorithm exploits statistical properties of the movie revenue data that may not hold in other data. In addition, the baseline optimization is based on a definition of visual energy that in some cases results in considerable amount of visual
distortion. We offer an ordering algorithm that works well regardless of the properties of the input data, and propose a 1-norm based definition of visual energy and the associated solution method that overcomes the limitation of the original baseline
optimization procedure. Furthermore, we propose an efficient layer labeling algorithm that scales linearly to the data size in place of the brute-force algorithm adopted by Byron and Wattenberg. We demonstrate the advantage of our algorithms over
existing techniques on a number of real world data sets.

Joint work with Yifan Hu


=== Title ===
  How to Handle ARP in a Software-Defined Network

=== Speaker ===
  Gabriele Lospoto
  PhD Student in Computer Science and Automation
  Roma Tre University

=== Abstract ===
The Address Resolution Protocol (ARP) enables communication between IP-speaking nodes in a local network by reconstructing the hardware (MAC) address associated with the IP address of an interface. This is not needed in a Software-Defined Network (SDN), because each device can forward packets without the need to learn this association. We tackle the interoperability problem arising between standard network devices (end systems, routers), that rely on ARP, and SDN datapaths, that do not handle ARP packets natively. In particular, we propose a general approach to handle ARP in a SDN, that is applicable in several network scenarios, is transparent for existing devices, and can coexist with any packet forwarding logic implemented in the controller. Our approach reduces ARP traffic by confining it to the edge of SDNs and requires a minimal set of flow entries in the datapaths. We argument about its applicability and confirm it with experiments performed on SDN datapaths from a range of different vendors.

Joint work with Roberto di Lallo, Massimo Rimondini and Giuseppe Di Battista

Mercoledì 27 April 2016 – On information propagation, social influence, and communities

Presso la “Sala riunioni”, primo piano, Dipartimento di Ingegneria, Via della Vasca Navale 79, 00149 Roma, Italy
Mercoledì 27 April 2016
Dalle ore 12:00 alle 13:00
The seminar will feature a presentation by Francesco Bonchi on his recent research in this area. 
Abstract: With the success of online social networks and microblogging platforms such as Facebook, Tumblr, and Twitter, the phenomenon of influence-driven propagations, has recently attracted the interest of computer scientists, sociologists, information technologists, and marketing specialists. In this talk we will take a data mining perspective, discussing what (and how) can be learned from a social network and a database of traces of past propagations over the social network. Starting from one of the key problems in this area, i.e. the identification of influential users, we will provide a brief overview of our recent contributions in this area. We will expose the connection between the phenomenon of information propagation and the existence of communities in social network, and we will go deeper in this new research topic arising at the overlap of information propagation analysis and community detection.

Giovedì 21 aprile – On the Practical Applicability of SDN Research (Roberto Di Lallo) – RoutingWatch: Visual Exploration and Analysis of Routing Events (Massimo Rimondini)

=== Quando ===
Giovedì, 21 aprile ore 14:30
=== Dove ===
Dipartimento di ingegneria
Sezione di informatica e automazione
Via della Vasca Navale, 79
Sala riunioni (1.10) Primo piano


=== Titolo ===
On the Practical Applicability of SDN Research

=== Speaker ===
Roberto di Lallo
PhD Student in Computer Science and Automation
Roma Tre University

=== Abstract ===
Software-Defined Networking (SDN) is a de-facto established approach that separates
the packet switching functions of a device from its operational logic, which is
controlled by a piece of software. Due to its potential for realizing new network
architectures and services, a whole thread of scientific literature is devoted to
SDN and its most adopted incarnation, OpenFlow. However, limited attention has been
put in verifying the viability of the proposed approaches on currently available
We address this deficiency through the following contributions: i) a critical review
of the literature about SDN in terms of applicability issues stemming from publicly
documented limitations of OpenFlow implementations; ii) a methodology for verifying
the support of SDN-related functions in a network device, comprising an OpenFlow
compliance test as well as custom targeted tests; iii) an application of the
methodology to devices from 7 different vendors, unveiling extensive anomalous
behaviors affecting even the most basic features; iv) a discussion of this outcome
in terms of relevance of the discovered anomalies and of their implications on the
applicability of state-of-the-art contributions on SDN. Besides taking a snapshot of
the viability of research results, with this paper we intend to highlight aspects
that operators should consider when picking SDN devices.

Joint work with M. Gradillo, G. Lospoto, C. Pisa, and M. Rimondini.



=== Titolo ===
RoutingWatch: Visual Exploration and Analysis of Routing Events

=== Speaker ===
Massimo Rimondini
Roma Tre University

=== Abstract ===
Network operators invest significant resources in monitoring and troubleshooting the
infrastructure they run. Currently, the availability of large networks of probing
devices, like, for example, RIPE Atlas, dramatically increases the amount of data an
operator can rely on. In particular, the large amount of traceroutes they can
produce are both an opportunity and a challenge. In this paper we provide a detailed
description of RoutingWatch, a visual tool for interactively performing searches and
analysis of routing events inferred from a large set of traceroutes. The key design
choices of RoutingWatch are based on discussions with network operators. We evaluate
the effectiveness of our approach by conducting a preliminary user study.

Joint work with D. Ceneda, M. Di Bartolomeo, V. Di Donato, M. Patrignani, and M.

Martedì 5 aprile alle 11.30 – Prof. Ulrich Pferschy – On the Quadratic Traveling Salesman Problem

Martedì 5 aprile alle 11.30 presso il Dipartimento di Ingegneria dell’Università Roma Tre, il Prof. Ulrich Pferschy terrà un seminario su:

On the Quadratic Traveling Salesman Problem

The well-known Traveling Salesman Problem (TSP) asks for a shortest tour through all vertices of a graph with respect to the weights of the edges. More recently, the following generalization of TSP was introduced: In the Quadratic Traveling Salesman Problem (QTSP) there is a weight associated with every three vertices traversed in succession. As a special case, we also consider the case where these weights correspond to the turning angles of the tour and speak of the angular-metric traveling salesman problem (Angle TSP).
In this talk we apply a rather basic algorithmic idea and perform the separation of the classical subtour elimination constraints on integral solutions only. Surprisingly, it turns out that this approach is faster than the standard fractional separation procedure known from the literature. We also test the combination with strengthened subtour elimination constraints for both variants, but these turn out to slow down the computation. Furthermore, we provide a new ILP linearization for the Angle TSP that needs only a linear number of additional variables while the standard linearization requires a cubic number.
We also consider the maximization version of the QTSP. For the special case of the MaxAngle TSP we can observe an interesting geometric property if the number of vertices is odd. We show that the sum of inner turning angles in an optimal solution always equals pi. This implies that the problem can be solved by the standard ILP model without producing any integral subtours. Moreover, we give a simple constructive polynomial time algorithm to find such an optimal solution. If the number of vertices is even no such property holds.

Il seminario si svolgerà presso la sala riunioni della sez. di  Informatica e Automazione del Dipartimento di Ingegneria in via della Vasca Navale 79 a Roma (Google maps). Le  indicazioni per raggiungere il dipartimento sono disponibili al link:

Per ulteriori informazioni rivolgersi a G. Nicosia (, tel. 06 57333455).

Mercoledì 20 gennaio – Vincenzo Roselli – L-Drawings of Directed Graphs

=== Quando ===
Mercoledì 20 gennaio alle ore 17:00

=== Dove ===
Dipartimento di ingegneria
Sezione di informatica e automazione
Via della Vasca Navale, 79
Sala riunioni, primo piano

=== Titolo ===
L-Drawings of Directed Graphs

=== Speaker ===
Vincenzo Roselli
Postdoctoral Researcher at Department of Engineering
Roma Tre University

=== Abstract ===
We introduce L-drawings, a novel paradigm for representing directed
graphs aiming at combining the readability features of orthogonal drawings with the expressive power of matrix representations. In an L-drawing, vertices have exclusive x- and y-coordinates and edges consist of two segments, one exiting the source vertically and one entering the destination horizontally. We study the problem of computing L-drawings using minimum ink. We prove its NP-completeness and provide a heuristic based on a polynomial-time algorithm that adds a vertex to a drawing using the minimum additional ink. We performed an experimental analysis of the heuristic which confirms its effectiveness.

Joint work with Patrizio Angelini, Giordano Da Lozzo, Marco Di Bartolomeo, Valentino Di Donato, Maurizio Patrignani and Ioannis Tollis.

The paper will be presented at the forthcoming Sofsem 2016 – 42nd International Conference on Current Trends in Theory and Practice of Computer Science – January 23–28, 2016 – Harrachov, Czech Republic

Small group modeling in cultural heritage – modeling automatic detection of social behavior of museum visitor pairs – Prof. Tsvi Kuflik – Giovedì 17 dicembre

Giovedì 17 dicembre 2015 –  ore 16:00 – 18:00.

Aula N13,  piano terra, Dipartimento di Ingegneria Roma Tre

Via della Vasca Navale, 79, Roma


In many cases, visitors come to a museum in small groups. In these cases, the visitors’ social context has an impact on their museum visit experience. Knowing the social context may allow a system to provide socially-aware services to the visitors. Evidence of the social context can be gained from observing/monitoring the visitors’ social behavior. However, automatic identification of a social context requires on the one hand identifying typical social-behavior patterns, and on the other using relevant sensors that measure various signals and reason about them to detect the visitors’ social behavior. The talk will present such typical social-behavior patterns of visitor pairs, identified by observations, and then, the instrumentation, detection process, reasoning, and analysis of measured signals that enables to detect the visitors’ social behavior. Simple sensors’ data, such as proximity to other visitors, proximity to museum points-of-interest, and visitor orientation were used to detect social synchronization, attention to the social companion, and interest in museum exhibits. The presented approach may allow future research to offer adaptive services to museum visitors based on their social context, to support their group visit experience better.