JUCS - Journal of Universal Computer Science 15(14): 2747-2764, doi: 10.3217/jucs-015-14-2747
Optimal Serverless Networks Attacks, Complexity and some Approximate Algorithms
expand article infoCarlos Aguirre‡, Ramon Huerta§, Lev Tsimring§
‡ Universidad Autónoma de Madrid, Madrid, Spain§ University of California, San Diego, United States of America

Corresponding author: Carlos Aguirre ( carlos.aguirre@uam.es )

© Carlos Aguirre, Ramon Huerta, Lev Tsimring.
This article is freely available under the J.UCS Open Content License.
Citation: Aguirre C, Huerta R, Tsimring L (2009) Optimal Serverless Networks Attacks, Complexity and some Approximate Algorithms. JUCS - Journal of Universal Computer Science 15(14): 2747-2764. https://doi.org/10.3217/jucs-015-14-2747
Open Access
Abstract
A network attack is a set of network elements that are disabled by an adversary. The goal for the attack is to produce the most possible damage to the network in terms of network connectivity by disabling the least possible number of network elements. We show that the problem of finding the optimal attack in a serverless network is NP-Complete even when only edges or nodes are considered for disabling. We study a node attack policy with polynomial complexity based on shorter paths and show that this attack policy outperforms in most cases classical attacks policies such as random attack or maximum degree attack. We also study the behavior of different network topologies under these attack policies.
Keywords
network connectivity, optimal attack problem, NP-complete attack strategies