Min–max optimization of node‐targeted attacks in service networks

Fortz, Bernard; Mycek, Mariusz; Pióro, Michał; Tomaszewski, Artur

doi:10.1002/net.22191

Download

Article (Scientific journals)

Min–max optimization of node‐targeted attacks in service networks

Fortz, Bernard; Mycek, Mariusz; Pióro, Michał et al.

2024 • In Networks, 83 (2), p. 256-288

Peer Reviewed verified by ORBi

Permalink
https://hdl.handle.net/2268/307698

DOI
10.1002/net.22191

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

main.pdf

Author postprint (767.57 kB)

Download

All documents in ORBi are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

Computer Networks and Communications; Hardware and Architecture; Information Systems; Software

Abstract :

[en] This article considers resilience of service networks that are composed of service and control nodes to node‐targeted attacks. Two complementary problems of selecting attacked nodes and placing control nodes reflect the interaction between the network operator and the network attacker. This interaction can be analyzed within the framework of game theory. Considering the limited performance of the previously introduced iterative solution algorithms based on non‐compact problem models, new compact integer programming formulations of the node attack optimization problem are proposed, which are based on the notion of pseudo‐components and on a bilevel model. The efficiency of the new formulations is illustrated by the numerical study that uses two reference networks (medium‐size and large‐size), and a wide range of the sizes of attacks and controllers placements.

Disciplines :

Quantitative methods in economics & management
Computer science

Author, co-author :

Fortz, Bernard ; Université de Liège - ULiège > HEC Liège Research > HEC Liège Research: Business Analytics & Supply Chain Mgmt ; Department of Computer Science Université Libre de Bruxelles Brussels Belgium ; INOCS, INRIA Lille France

Mycek, Mariusz; Institute of Telecommunications Warsaw University of Technology Warsaw Poland

Pióro, Michał ; Institute of Telecommunications Warsaw University of Technology Warsaw Poland ; Faculty of Electronics, Telecommunications and Informatics Gdańsk University of Technology Gdańsk Poland

Tomaszewski, Artur; Institute of Telecommunications Warsaw University of Technology Warsaw Poland

Language :

English

Title :

Min–max optimization of node‐targeted attacks in service networks

Publication date :

March 2024

Journal title :

Networks

ISSN :

0028-3045

eISSN :

1097-0037

Publisher :

Wiley

Volume :

Issue :

Pages :

256-288

Peer reviewed :

Peer Reviewed verified by ORBi

Additional URL :

https://onlinelibrary.wiley.com/doi/pdf/10.1002/net.22191

Available on ORBi :

since 11 October 2023

Statistics

Number of views

27 (5 by ULiège)

Number of downloads

20 (1 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

Bibliography

B. Addis, M. Di Summa, and A. Grosso, Identifying critical nodes in undirected graphs: Complexity results and polynomial algorithms for the case of bounded treewidth, Discrete Appl. Math. 161 (2013), 2349–2360.
E. Calle, S. G. Cosgaya, D. Martínez, and M. Pióro, “Solving the backup controller placement problem in SDN under simultaneous targeted attacks,” 2019 11th International Workshop on Resilient Networks Design and Modeling (RNDM), IEEE, New York, 2019, pp. 1–7.
E. Calle, D. Martínez, M. Mycek, and M. Pióro, Resilient backup controller placement in distributed SDN under critical targeted attacks, Int. J. Crit. Infrastruct. Prot. 33 (2021), 12–260.
M. Campêlo, V. A. Campos, and R. C. Corrêa, On the asymmetric representatives formulation for the vertex coloring problem, Discrete Appl. Math. 156 (2008), 1097–1111.
P. Carroll, B. Fortz, M. Labbé, and S. McGarraghy, A branch-and-cut algorithm for the ring spur assignment problem, Networks 61 (2013), 89–103.
B. Colson, P. Marcotte, and G. Savard, Bilevel programming: A survey, 4OR 3 (2005), 87–107.
T. Das, V. Sridharan, and M. Gurusamy, A survey on controller placement problem in SDN, IEEE Commun. Surv. Tutor. 22 (2020), 472–503.
A. de Sousa, D. Mehta, and D. Santos, “The robust node selection problem aiming to minimize the connectivity impact of any p node failures,” Design of Reliable Communication Networks; 13th International Conference, IEEE, New York, 2017, pp. 138–145.
S. Dempe, Foundations of bilevel programming, Springer Science & Business Media, New York, 2002.
W. Ellens. Effective resistance and other graph measures for network robustness. Master's thesis, Leiden University, 2011.
L. Faramondi, R. Setola, S. Panzieri, F. Pascucci, and G. Oliva, Finding critical nodes in infrastructure networks, Int. J. Crit. Infrastruct. Prot. 20 (2017), 3–15.
F. Giles and W. Pulleyblank, Total dual integrality and integer polyhedra, Linear Algebra Appl. 25 (1979), 191–196.
B. Heller, R. Sherwood, and N. McKeown, “The controller placement problem,” Proceedings of the First Workshop on Hot Topics in Software Defined Networks, Association for Computing Machinery, New York, 2012, pp. 7–12.
T. Hu, Z. Guo, P. Yi, T. Baker, and J. Lan, Multi-controller based software-defined networking: A survey, IEEE Access 6 (2018), 15980–15996.
S. Iyer, T. Killingback, B. Sundaram, and Z. Wang, Attack robustness and centrality of complex networks, PLoS One 8 (2013), e59613.
T. Kleinert, M. Labbé, I. Ljubić, and M. Schmidt, A survey on mixed-integer programming techniques in bilevel optimization, EURO J. Comput. Optim. 9 (2021), 100007.
M. Lalou, T. Mohammed Amin, and H. Kheddouci, The critical node detection problem in networks: A survey, Comput. Sci. Rev. 28 (2018), 92–117.
J. Lu, Z. Zhang, T. Hu, P. Yi, and J. Lan, A survey of controller placement problem in software-defined networking, IEEE Access 7 (2019), 24290–24307.
M. Manzano, J. Marzo, E. Calle, and A. Manolovay, “Robustness analysis of real network topologies under multiple failure scenarios,” 17th European Conference on Networks and Optical Communications (EuCNC), IEEE, New York, 2012, pp. 1–6.
M. Mycek, M. Pióro, A. Tomaszewski, and A. de Sousa, “Optimizing primary and backup SDN controllers' placement resilient to node-targeted attacks,” 17th International Conference on Network and Service Management (CNSM 2021), IEEE, New York, 2021, pp. 397–401.
S. Orlowski, M. Pióro, A. Tomaszewski, and R. Wessäly, SNDlib 1.0—Survivable network design library, Networks 55 (2010), 276–286.
N. Perrot and T. Reynaud, “Optimal placement of controllers in a resilient SDN architecture,” 12th International Conference on the Design of Reliable Communication Networks (DRCN), IEEE, New York, 2016, pp. 145–151.
M. Pióro, M. Mycek, and A. Tomaszewski, Network protection against node attacks based on probabilistic availability measures, IEEE Trans. Netw. Serv. Manag. 18 (2021), 2742–2763.
M. Pióro, M. Mycek, A. Tomaszewski, and A. de Sousa, “On joint primary and backup controllers' placement optimization against node-targeted attacks,” 12th International Workshop on Resilient Networks Design and Modelling (RNDM 2022), IEEE, New York, 2022, pp. 1–7.
D. F. Rueda, E. Calle, and J. L. Marzo, “Improving the robustness to targeted attacks in software defined networks (SDN),” 13th International Conference on Design of Reliable Communication Networks (DRCN 2017), VDE, Frankfurt, 2017, pp. 1–8.
D. F. Rueda, E. Calle, and J. L. Marzo, Robustness comparison of 15 real telecommunication networks: Structural and centrality measurements, J. Netw. Syst. Manag. 25 (2017), 269–289.
D. Santos, A. de Sousa, and C. M. Machuca, “Combined control and data plane robustness of SDN networks against malicious node attacks,” 14th International Conference on Network and Service Management (CNSM), IEEE, New York, 2018, pp. 54–62.
D. Santos, A. de Sousa, and C. M. Machuca, “Robust SDN controller placement to malicious node attacks,” 21st Conference on Innovation in Clouds, Internet and Networks and Workshops (ICIN), IEEE, New York, 2018, pp. 1–8.
D. Santos, A. de Sousa, and C. M. Machuca, The controller placement problem for robust SDNs against malicious node attacks considering the control plane with and without split-brain, Ann. Telecommun. 74 (2019), 575–591.
D. Santos, A. de Sousa, and P. Monteiro, Compact models for critical node detection in telecommunication networks, Electron. Notes Discrete Math. 64 (2018), 325–334.
J. M. Simmons, Optical network design and planning, 2nd ed., Springer, Cham, 2014.
A. K. Singh and S. Srivastava, A survey and classification of controller placement problem in SDN, Int. J. Netw. Manag. 28 (2018), e2018.
A. Tomaszewski, M. Pióro, and M. Mycek. Min-max optimization of attacks on nodes vs. max-min optimization of controller placements in service networks (10th Int. Netw. Optim. Conf.) 2022, pp. 69–74.