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)

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.

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

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.

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.