Assessing Attack Vulnerability in Networks with Uncertainty

Abstract—A considerable amount of research effort has fo-cused on developing metrics and approaches to assess network vulnerability. However, most of them neglect the network un-certainty arisen due to various reasons such as mobility and dynamics of the network, or noise introduced in data collection process. To this end, we introduce a framework to assess vul-nerability of networks with uncertainty, modeling such networks as probabilistic graphs. We adopt expected pairwise connectivity (EPC) as a measure to quantify global connectivity and use it to formulate vulnerability assessment as a stochastic optimization problem. The objective is to identify a few number of critical nodes whose removal minimizes EPC in the residual network. While solutions for stochastic optimization problems are often limited to small networks, we present a practical solution that works for larger networks. The key advantages of our solution include 1) the application of a weighted averaging technique that avoids considering all, exponentially many, possible realizations of probabilistic graphs and 2) a Fully Polynomial Time Ran-domized Approximation Scheme (FPRAS) to efficiently estimate the EPC with any desired accuracy. Extensive experiments demonstrate significant improvement on performance of our solution over other heuristic approaches. I