TY - JOUR
T1 - Network topology vulnerability/cost trade-off
T2 - Model, application, and computational complexity
AU - Laszka, Aron
AU - Gueye, Assane
N1 - Publisher Copyright:
© Taylor & Francis Group, LLC.
PY - 2015
Y1 - 2015
N2 - Technological networks (e.g., telephone and sensor networks, Internet) have provided modern society with increased efficiency, but have also exposed us to the risks posed by their vulnerability to attacks. Mitigating these risks involves designing robust network topologies in situations where resources are economically constrained. In this study, we consider the vulnerability of network topologies from an economic viewpoint and propose security metrics, which are necessary for assessing the efficiency of our solutions. We define the vulnerability of a network as the potential loss in connectivity due to the actions of a strategic adversary. To derive vulnerability metrics, we revisit our recently introduced network blocking game models, which provide a framework for quantifying network topology vulnerability in adversarial environments. We assume that the network operator takes both security and economic goals into consideration. To model these goals, we generalize previous models by introducing usage costs and budget constraints for the operator. We study two natural constraint formulations, the maximum and the expected cost constraints, and derive the feasible vulnerability/cost region. Because the proposed metrics are based on game-theoretic models, computing them can be challenging. To elucidate these challenges, we provide a thorough complexity analysis for solving the proposed games.
AB - Technological networks (e.g., telephone and sensor networks, Internet) have provided modern society with increased efficiency, but have also exposed us to the risks posed by their vulnerability to attacks. Mitigating these risks involves designing robust network topologies in situations where resources are economically constrained. In this study, we consider the vulnerability of network topologies from an economic viewpoint and propose security metrics, which are necessary for assessing the efficiency of our solutions. We define the vulnerability of a network as the potential loss in connectivity due to the actions of a strategic adversary. To derive vulnerability metrics, we revisit our recently introduced network blocking game models, which provide a framework for quantifying network topology vulnerability in adversarial environments. We assume that the network operator takes both security and economic goals into consideration. To model these goals, we generalize previous models by introducing usage costs and budget constraints for the operator. We study two natural constraint formulations, the maximum and the expected cost constraints, and derive the feasible vulnerability/cost region. Because the proposed metrics are based on game-theoretic models, computing them can be challenging. To elucidate these challenges, we provide a thorough complexity analysis for solving the proposed games.
UR - http://www.scopus.com/inward/record.url?scp=84953851250&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84953851250&partnerID=8YFLogxK
U2 - 10.1080/15427951.2015.1018019
DO - 10.1080/15427951.2015.1018019
M3 - Article
AN - SCOPUS:84953851250
SN - 1542-7951
VL - 11
SP - 588
EP - 626
JO - Internet Mathematics
JF - Internet Mathematics
IS - 6
ER -