Ricerc@Sapienza

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.

Vulnerabilities represent one of the main weaknesses of IT systems and the availability of consolidated official data, like CVE (Common Vulnerabilities and Exposures), allows for using them to compute the paths an attacker is likely to follow. However, even if patches are available, business constraints or lack of resources create obstacles to their straightforward application. As a consequence, the security manager of a network needs to deal with a large number of vulnerabilities, making decisions on how to cope with them.