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
Carlos 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. 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 |  |
AbstractA 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.
Keywordsnetwork connectivity, optimal attack problem, NP-complete attack strategies