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 (firstname.lastname@example.org, tel. 06 57333455)
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.
Venerdì 17 giugno alle ore 12:00.
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
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
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.
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 (email@example.com, tel. 06 57333455).
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.
Mercoledì 16 dicembre 2015 – ore 16:00 – 18:00.
Aula N13, piano terra, Dipartimento di Ingegneria Roma Tre
Via della Vasca Navale, 79, Roma
Over the years, the area of user modeling (and later on recommendation systems) produced a variety of user modeling techniques. These techniques were developed for modeling and representing the users in order to better understand their needs and provide them with personalized services. The common techniques in use are collaborative filtering and content/feature based, while in specific domains we can find also case-based, demographic and overlay approaches. However, the knowledge represented by these techniques is quite limited. In recent years, with the advent of web 2.0 and the social and semantic web, personal information becomes widely available online in various forms. This poses opportunities as well as major challenges for the classical user modeling approaches – how to make use of this information to enhance user modeling? As a potential solution to the problem, we are exploring the idea of graph-based user modeling representation, as an integrative framework that enables standard and simple representation of users’ characteristics, not limited to a specific technique. In various studies we demonstrated the potential benefits of this approach and it’s possible contribution to user modeling and recommender systems. The talk will briefly present the general idea of graph-based user modeling as well as research results that demonstrate its contribution to a variety of domains and scenarios.