Ricerc@Sapienza

In this project, given a communication network, we address the problem of computing a lower bound to the transmission rate between two network nodes, notwithstanding the presence of an intelligent malicious attacker with limited destructive power.

Formally, we are given a link capacitated network N with source node s and destination node t, and a budget B for the attacker. We want to compute the Guaranteed Maximum Flow from s to t when an attacker can remove at most B edges.

This problem is known to be NP-hard for general networks. In this project, we want to devise efficient algorithms tailored for Internet-like networks. To this aim, we plan to start from a ILP (Integer Linear Programming)-based algorithm from the literature. Such algorithm creates ILP problems with too many variables and constraints, so that ILP solvers require too many resources (both in terms of RAM and computation time) to solve such problems.

In this project, starting from our previous work ([19], best paper at ISMIS 2018), we plan to devise novel Artificial Intelligence techniques enabling the computation of reduced networks, to be used in place of the input networks to assess their vulnerability by means of ILP. By effectively reducing/compressing the input networks, scalability and performance of our overall ILP-based approach to network vulnerability assessment will be substantially improved.

We will prove that all our novel employed network reductions, while substantially reducing the network size (both in terms of number of nodes and of edges), retain the same Guaranteed Maximum Flow, and so the reduced networks can be safely used in place of the original networks when assessing their vulnerability.

Finally, we plan to experimentally evaluate performance and scalability of our approach on a large collection of Internet-based networks collected by the University of Stanford (https://snap.stanford.edu/data/index.html).