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).
As anticipated, in our previous work [19] we presented an algorithm that applies three (GMF-retaining) network reduction techniques performing a complete exploration of the input network.
With respect to [19], in this project we aim at advancing the state of the art in the following directions:
1) We will introduce new network reduction techniques to our workflow, and formally prove their correctness (i.e., that the reduced networks still retain the GMF of the initial networks);
2) We will explore the use of Artificial Intelligence approaches (e.g., based on (Deep-)Machine Learning, ML) to design or automatically discover effective heuristics able to intelligently guide our network exploration algorithm towards locations where our network reduction techniques can be fruitfully applied. With this, we aim to substantially improve the entire input network preprocessing time and to be able to deal with very large input networks.
3) We will design and implement efficient algorithms and implementations for all phases of our workflow;
4) We will evaluate the performance of our overall approach on several Internet sub-graphs from the Stanford Large Network Dataset Collection (SLNDC).
This will also advance the state of the art with respect to the algorithms proposed in [1,2,19], as we will use them as our base cases.
Finally, it is worth stressing that our goal is not to select classes of networks for which the Network Interdiction Problem (NIP) is polynomial, but rather to effectively solve the NIP for the class of networks of our interest, i.e., very large Internet-like networks.
In particular, Internet-like networks typically do not fall in the classes of networks for which NIP is known to be polynomial, see, e.g., [1].
Hence, our approach is much in the spirit with which Mixed Integer Linear Programming (MILP) and Integer Linear Programming (ILP) solvers (see, e.g., [20]), model checkers (see, e.g., [23,24]), controllers synthesisers (see, e.g., [25]), local search-based (see, e.g., [27]), SAT and SMT solvers (see, e.g., [28]) are built.
Of course, being our problem NP-hard, our approach (if P is different from NP) will still result in an exponential algorithm in the worst case. However, preliminary experimental results in [19] show that, by applying the three instance transformation techniques presented there, off-the-shelf ILP solvers can be made able to perform vulnerability analysis of networks with around 200,000 nodes.
In this project, we will push further such results, by also showing its effectiveness on different (yet Internet-like) networks.
REFERENCES
[1] C.A. Phillips. The network inhibition problem. In Proc. STOC 1993, 776-785. ACM, 1993.
[2] R.K. Wood. Deterministic network interdiction. Math. Comp. Mod., 17(2):1-18, 1993.
[18] J. Evans. Optimization Algorithms for Networks and Graphs. Routledge, 2017.
[19] T. Mancini, F. Mari, I. Melatti, I. Salvo, and E. Tronci. An Efficient Algorithm for Network Vulnerability Analysis Under Malicious Attacks. In Proc. ISMIS 2018, 302-312.
[20] Y. Lin, L.M. Austin, and J.R. Burns. An intelligent algorithm for mixed-integer programming models. Comp. Oper. Res., 19(6):461-468, 1992.
[23] E. M. Clarke, O. Grumberg, and D.A. Peled. Model Checking. MIT Press, 1999.
[24] T. Mancini, F. Mari, A. Massini, I. Melatti, F. Merli, and E. Tronci. System level formal verification via model checking driven simulation. In Proc. CAV 2013, LNCS 8044.
[25] F. Mari, I. Melatti, I. Salvo, and E. Tronci. Model based synthesis of control software from system level formal specifications. ACM TOSEM, 23(1), 2014.
[27] T. Mancini, P. Flener, and J. Pearson. Combinatorial problem solving over relational databases: View synthesis through constraint-based local search. In Proc. SAC 2012.
[28] J. Marques-Silva and S. Malik. Propositional SAT Solving. Springer, 2018.