# Author Archives: sysdia

# 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*

__Abstract__:

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 (nicosia@ing.uniroma3.it, tel. 06 57333455)

# Friday December 9th – Securing Promiscuous Use of Untrusted USB Thumb Drives in Industrial Control Systems

WHEN: Friday December 9th at 14:30

WHERE: Via della Vasca Navale, 79 – Meeting room (1.10) on 1st floor

———

TITLE: 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

===WHEN===

Friday, June 17 at 12:00.

====== Where ======

Department of Engineering

Section of Computer Science and Automation

Via della Vasca Navale, 79

Meeting room (1.10) on 1st floor

===title===

An Efficient Partial Coverage Algorithm for Wireless Sensor Networks

===speaker===

Habib Mostafaei

PhD student in Computer Science and Automation

Roma Tre University

http://www.dia.uniroma3.it/~compunet/www/view/person.php?id=habib

===abstract===

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

# Seminars – Valentino Di Donato, Marco Di Bartolomeo and Gabriele Lospoto – June 1st @ 2:00PM

Wednesday, June 1st at 2:00 PM

=== Where ===

Department of Engineering

Section of Computer Science and Automation

Via della Vasca Navale, 79

Meeting room (1.10) on 1st floor

________________________________________________________

SEMINAR #1

=== Title ===

NetFork: Mapping Time to Space in Network Visualization

=== Speaker ===

Valentino Di Donato

PhD Student in Computer Science and Automation

Roma Tre University

http://www.dia.uniroma3.it/~compunet/www/view/person.php?id=didonato

=== 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

________________________________________________________

SEMINAR #2

=== 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

http://www.dia.uniroma3.it/~compunet/www/view/person.php?id=mdb

=== 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

SEMINAR #3

=== Title ===

How to Handle ARP in a Software-Defined Network

=== Speaker ===

Gabriele Lospoto

PhD Student in Computer Science and Automation

Roma Tre University

http://www.dia.uniroma3.it/~compunet/www/view/person.php?id=gabriele

=== 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

# Wednesday, April 27, 2016 – On information propagation, social influence, and communities

# Thursday, April 21st – On the Practical Applicability of SDN Research (Roberto Di Lallo) – RoutingWatch: Visual Exploration and Analysis of Routing Events (Massimo Rimondini)

=== When ===

Thursday, April 21st at 2:30 PM

=== Where ===

Department of Engineering

Section of Computer Science and Automation

Via della Vasca Navale, 79

Meeting room (1.10) on 1st floor

________________________________________________________

SEMINAR #1

=== Title ===

On the Practical Applicability of SDN Research

=== Speaker ===

Roberto di Lallo

PhD Student in Computer Science and Automation

Roma Tre University

http://www.dia.uniroma3.it/~compunet/www/view/person.php?id=roberto

=== 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

hardware.

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.

________________________________________________________

SEMINAR #2

=== Title ===

RoutingWatch: Visual Exploration and Analysis of Routing Events

=== Speaker ===

Massimo Rimondini

Researcher

Roma Tre University

http://www.dia.uniroma3.it/~compunet/www/view/person.php?id=max

=== 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.

Pizzonia.

# Tuesday, April 5th at 11:30 – Prof. Ulrich Pferschy – On the Quadratic Traveling Salesman Problem

WHERE

Department of Engineering

Section of Computer Science and Automation

Via della Vasca Navale, 79

Meeting room (1.10) on 1st floor

——–

**On the Quadratic Traveling Salesman Problem**

__Abstract:__

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.

# Wednesday, Jan 20th – Vincenzo Roselli – L-Drawings of Directed Graphs

=== When ===

Wednesday, Jan 20th at 5:00 PM

=== Where ===

Department of Engineering

Section of Computer Science and Automation

Via della Vasca Navale, 79

Meeting room (1.10) on 1st floor

=== Title ===

L-Drawings of Directed Graphs

=== Speaker ===

Vincenzo Roselli

Postdoctoral Researcher at Department of Engineering

Roma Tre University

http://www.dia.uniroma3.it/~compunet/www/view/person.php?id=cionzo

=== 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 – Thursday, december 17

Thursday, december 17 at 16:00 – 18:00.

N13 room, ground floor, Department of Engineering

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.