Exact and approximation algorithms for sensor placement against DDoS attacks

• Autorzy: Junosza-Szaniawski Konstanty , Nogalski Dariusz , Rzążewski Paweł

Identyfikatory

DOI

10.34768/amcs-2022-0004

• Języki publikacji: EN

Abstrakty

EN

In a distributed denial of service (DDoS) attack, the attacker gains control of many network users through a virus. Then the controlled users send many requests to a victim, leading to its resources being depleted. DDoS attacks are hard to defend because of their distributed nature, large scale and various attack techniques. One possible mode of defense is to place sensors in a network that can detect and stop an unwanted request. However, such sensors are expensive, as a result of which there is a natural question as to the minimum number of sensors and their optimal placement required to get the necessary level of safety. Presented below are two mixed integer models for optimal sensor placement against DDoS attacks. Both models lead to a trade-off between the number of deployed sensors and the volume of uncontrolled flow. Since the above placement problems are NP-hard, two efficient heuristics are designed, implemented and compared experimentally with exact mixed integer linear programming solvers.

Słowa kluczowe

EN

DDoS; sensor placement; network safety optimization

PL

DDoS; umiejscowienie czujnika; optymalizacja bezpieczeństwa sieci

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2022
• Tom: Vol. 32, no. 1
• Strony: 35--49
• Opis fizyczny: Bibliogr. 54 poz., rys., wykr.

Twórcy

autor

Junosza-Szaniawski Konstanty

• Faculty of Mathematics and Information Science Warsaw University of Technology ul. Koszykowa 75, 00-662 Warsaw, Poland

autor

Nogalski Dariusz

• Military Communication Institute ul. Warszawska 22A, 05-130 Zegrze, Poland

autor

Rzążewski Paweł

• Faculty of Mathematics and Information Science Warsaw University of Technology ul. Koszykowa 75, 00-662 Warsaw, Poland; Faculty of Mathematics, Informatics and Mechanics University of Warsaw ul. Banacha 2, 02-097 Warsaw, Poland

Bibliografia

• [1] Afek, Y., Bremler-Barr, A. and Landau Feibish, S. (2013). Automated signature extraction for high volume attacks, Conference on Architectures for Networking and Communications Systems, San Jose, USA, pp. 147–156.
• [2] Altner, D.S., Ergun, Ö. and Uhan, N.A. (2010). The maximum flow network interdiction problem: Valid inequalities, integrality gaps, and approximability, Operations Research Letters 38(1): 33–38, DOI: 10.1016/j.orl.2009.09.013.
• [3] Armbruster, B., Smith, J.C. and Park, K. (2007). A packet filter placement problem with application to defense against denial of service attacks, European Journal of Operational Research 176(2): 1283–1292.
• [4] de Assis, M.V.O., Hamamoto, A.H., Abrão, T. and Proença, M.L. (2017). A game theoretical based system using Holt-Winters and genetic algorithm with fuzzy logic for DoS/DDoS mitigation on SDN networks, IEEE Access 5: 9485–9496, DOI: 10.1109/ACCESS.2017.2702341.
• [5] Belabed, D., Bouet, M. and Conan, V. (2018). Centralized defense using smart routing against link-flooding attacks, 2nd Cyber Security in Networking Conference, CSNet 2018, Paris, France, pp. 1–8, DOI: 10.1109/CSNET.2018.8602966.
• [6] Blazek, P., Gerlich, T. and Martinasek, Z. (2019). Scalable DDoS mitigation system, 2019 42nd International Conference on Telecommunications and Signal Processing (TSP), Budapest, Hungary, pp. 617–620.
• [7] Bonguet, A. and Bellaïche, M. (2017). A survey of denial-of-service and distributed denial of service attacks and defenses in cloud computing, Future Internet 9(3), Article no. 43, DOI: 10.3390/fi9030043.
• [8] Cameron, C., Patsios, C., Taylor, P.C. and Pourmirza, Z. (2019). Using self-organizing architectures to mitigate the impacts of denial-of-service attacks on voltage control schemes, IEEE Transactions on Smart Grid 10(3): 3010–3019.
• [9] Cetinkaya, A., Ishii, H. and Hayakawa, T. (2019). An overview on denial-of-service attacks in control systems: Attack models and security analyses, Entropy 21(2): 210, DOI: 10.3390/e21020210.
• [10] Chou, J.-J., Shih, C.-S., Wang, W.-D. and Huang, K.-C. (2019). Iot sensing networks for gait velocity measurement, International Journal of Applied Mathematics and Computer Science 29(2): 245–259, DOI: 10.2478/amcs-2019-0018.
• [11] Criscuolo, P.J. (2000). Distributed Denial of Service: Trin00, Tribe Flood Network, Tribe Flood Network 2000, and Stacheldraht, Lawrence Livermore National Laboratory, Livermore.
• [12] Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M. and Saurabh, S. (2015). Parameterized Algorithms, Springer, Cham, DOI: 10.1007/978-3-319-21275-3.
• [13] Daya, A.A., Salahuddin, M.A., Limam, N. and Boutaba, R. (2020). BotChase: Graph-based bot detection using machine learning, IEEE Transactions on Network and Servive Management 17(1): 15–29, DOI: 10.1109/TNSM.2020.2972405.
• [14] Douligeris, C. and Mitrokotsa, A. (2004). DDOS attacks and defense mechanisms: Classification and state-of-the-art, Computer Networks 44(5): 643–666.
• [15] El Defrawy, K., Markopoulou, A. and Argyraki, K. (2007). Optimal allocation of filters against DDoS attacks, 2007 Information Theory and Applications Workshop, La Jolla, USA, pp. 140–149.
• [16] Fayaz, S.K., Tobioka, Y., Sekar, V. and Bailey, M. (2015). Bohatei: Flexible and elastic DDOS defense, 24th USENIX Security Symposium, USENIX Security 15, Washington, USA, pp. 817–832, https://www.useni x.org/conference/usenixsecurity15/technical-sessions/presentation/fayaz.
• [17] Ford, L.R. and Fulkerson, D.R. (1956). Maximal flow through a network, Canadian Journal of Mathematics 8: 399–404.
• [18] Garg, N., Vazirani, V.V. and Yannakakis, M. (1994). Multiway cuts in directed and node weighted graphs, in S. Abiteboul and E. Shamir (Eds), Automata, Languages and Programming: 21st International Colloquium, ICALP94, Springer, Berlin, pp. 487–498.
• [19] Gera, J. and Battula, B.P. (2018). Detection of spoofed and non-spoofed ddos attacks and discriminating them from flash crowds, EURASIP Journal on Information Security 2018(1), Article no. 9, DOI: 10.1186/s13635-018-0079-6.
• [20] Gkounis, D., Kotronis, V., Liaskos, C. and Dimitropoulos, X.A. (2016). On the interplay of link-flooding attacks and traffic engineering, Computer Communication Review 46(2): 5–11, DOI: 10.1145/2935634.2935636.
• [21] Goldberg, A.V. and Tarjan, R.E. (2014). Efficient maximum flow algorithms, Communications of the ACM 57(8): 82–89, DOI: 10.1145/2628036.
• [22] Hemmati, M., Cole Smith, J. and Thai, M.T. (2014). A cutting-plane algorithm for solving a weighted influence interdiction problem, Computational Optimization and Applications 57(1): 71–104, DOI: 10.1007/s10589-013-9589-9.
• [23] Huang, L., Ran, J., Wang, W., Yang, T. and Xiang, Y. (2021). A multi-channel anomaly detection method with feature selection and multi-scale analysis, Computer Networks 185: 107645, DOI: 10.1016/j.comnet.2020.107645.
• [24] Huseinović, A., Mrdović, S., Bicakci, K. and Uludag, S. (2020). A survey of denial-of-service attacks and solutions in the smart grid, IEEE Access 8: 177447–177470.
• [25] Hwang, R.-H., Peng, M.-C., Huang, C.-W., Lin, P.-C. and Nguyen, V.-L. (2020). An unsupervised deep learning model for early network traffic anomaly detection, IEEE Access 8: 30387–30399.
• [26] Islam, M.H., Nadeem, K. and Khan, S.A. (2008). Efficient placement of sensors for detection against distributed denial of service attack, 2008 International Conference on Innovations in Information Technology, IIT 2008, Al Ain, UAE, pp. 653–657.
• [27] Jafarian, T., Masdari, M., Ghaffari, A. and Majidzadeh, K. (2021). A survey and classification of the security anomaly detection mechanisms in software defined networks, Cluster Computing 24(2): 1235–1253, DOI: 10.1007/s10586-020-03184-1.
• [28] Jeong, S.B., Choi, Y. and Kim, S. (2004). An effective placement of detection systems for distributed attack detection in large scale networks, in C.H. Lim and M. Yung (Eds), Information Security Applications: 5th International Workshop, WISA 2004, Springer, Berlin, pp. 204–210, DOI: 10.1007/978-3-540-31815-6_17.
• [29] Jiao, J., Ye, B., Zhao, Y., Stones, R.J., Wang, G., Liu, X., Wang, S. and Xie, G. (2017). Detecting TCP-based DDoS attacks in Baidu cloud computing data centers, 36th IEEE Symposium on Reliable Distributed Systems, SRDS 2017, Hong Kong, China, pp. 256–258, DOI: 10.1109/SRDS.2017.37.
• [30] Junosza-Szaniawski, K., Nogalski, D. and Wójcik, A. (2020). Exact and approximation algorithms for sensor placement against DDoS attacks, 2020 15th Conference on Computer Science and Information Systems (FedCSIS)/13th International Workshop on Computational Optimization, Sofia, Bulgaria, pp. 295–301, DOI: 10.15439/2020F106.
• [31] Kallitsis, M.G., Stoev, S.A., Bhattacharya, S. and Michailidis, G. (2016). AMON: An open source architecture for online monitoring, statistical analysis, and forensics of multi-gigabit streams, IEEE Journal on Selected Areas in Communications 34(6): 1834–1848, DOI: 10.1109/JSAC.2016.2558958.
• [32] Kang, M.S., Lee, S.B. and Gligor, V.D. (2013). The Crossfire attack, 2013 IEEE Symposium on Security and Privacy, SP 2013, Berkeley, USA, pp. 127–141, DOI: 10.1109/SP.2013.19.
• [33] Khalaf, B.A., Mostafa, S.A., Mustapha, A., Mohammed, M.A. and Abduallah, W.M. (2019). Comprehensive review of artificial intelligence and statistical approaches in distributed denial of service attack and defense methods, IEEE Access 7: 51691–51713.
• [34] Khapalov, A. (2010). Source localization and sensor placement in environmental monitoring, International Journal of Applied Mathematics and Computer Science 20(3): 445–458, DOI: 10.2478/v10006-010-0033-3.
• [35] Liaskos, C. and Ioannidis, S. (2018). Network topology effects on the detectability of Crossfire attacks, IEEE Transactions on Information Forensics and Security 13(7): 1682–1695.
• [36] Liu, X., Ren, J., He, H., Wang, Q. and Song, C. (2021). Low-rate ddos attacks detection method using data compression and behavior divergence measurement, Computers & Security 100: 102–107, DOI: 10.1016/j.cose.2020.102107.
• [37] de Miranda Rios, V., Inácio, P.R.M., Magoni, D. and Freire, M.M. (2021). Detection of reduction-of-quality ddos attacks using fuzzy logic and machine learning algorithms, Computer Networks 186: 107792, DOI: 10.1016/j.comnet.2020.107792.
• [38] Mirkovic, J. and Reiher, P. (2004). A taxonomy of DDoS attack and DDoS defense mechanisms, ACM SIGCOMM Computer Communication Review 34(2): 39–53, DOI: 10.1145/997150.997156.
• [39] Monnet, Q., Mokdad, L., Ballarini, P., Hammal, Y. and Ben-Othman, J. (2017). DoS detection in WSNs: Energy-efficient methods for selecting monitoring nodes, Concurrency and Computation: Practice and Experience 29(23), Article ID: e44266, DOI: 10.1002/cpe.4266.
• [40] Mowla, N.I., Doh, I. and Chae, K. (2018). CSDSM: Cognitive switch-based DDoS sensing and mitigation in SDN-driven CDNI word, Computer Science and Information Systems 15(1): 163–185, DOI: 10.2298/CSIS170328044M.
• [41] Omer, J. and Mucherino, A. (2020). Referenced vertex ordering problem: Theory, applications and solution methods, Working paper/preprint, https://hal.archives-o uvertes.fr/hal-02509522.
• [42] Patan, M. (2012). Distributed scheduling of sensor networks for identification of spatio-temporal processes, International Journal of Applied Mathematics and Computer Science 22(2): 299–311, DOI: 10.2478/v10006-012-0022-9.
• [43] Peng, T., Leckie, C. and Ramamohanarao, K. (2007). Survey of network-based defense mechanisms countering the DoS and DDoS problems, ACM Computing Surveys 39(1): 3, DOI: 10.1145/1216370.1216373.
• [44] Pilipczuk, M. and Wahlström, M. (2018). Directed multicut is W[1]-hard, even for four terminal pairs, ACM Transactions on Computation Theory 10(3): 13:1–13:18, DOI: 10.1145/3201775.
• [45] Ramanathan, S., Mirkovic, J., Yu, M. and Zhang, Y. (2018). SENSS against volumetric DDoS attacks, Proceedings of the 34th Annual Computer Security Applications Conference, ACSAC 2018, San Juan, USA, pp. 266–277, DOI: 10.1145/3274694.3274717.
• [46] Ranjan, S., Swaminathan, R., Uysal, M., Nucci, A. and Knightly, E. (2009). DDoS-shield: DDoS-resilient scheduling to counter application layer attacks, IEEE/ACM Transactions on Networking 17(1): 26–39.
• [47] Studer, A. and Perrig, A. (2009). The Coremelt attack, in M. Backes and P. Ning (Eds), Computer Security— ESORICS 2009: 14th European Symposium on Research in Computer Security, Springer, Berlin, pp. 37–52, DOI: 10.1007/978-3-642-04444-1_3.
• [48] Suchanski, M., Kaniewski, P., Romanik, J., Golan, E. and Zubel, K. (2020). Radio environment maps for military cognitive networks: Density of small-scale sensor network vs. map quality, EURASIP Journal on Wireless Communications and Networking 2020(1): 189, DOI: 10.1186/s13638-020-01803-4.
• [49] Ucinski, D. (2012). Sensor network scheduling for identification of spatially distributed processes, International Journal of Applied Mathematics and Computer Science 22(1): 25–40, DOI: 0.2478/v10006-012-0002-0.
• [50] Wang, K., Du, M., Maharjan, S. and Sun, Y. (2017). Strategic honeypot game model for distributed denial of service attacks in the smart grid, IEEE Transactions on Smart Grid 8(5): 2474–2482.
• [51] Wood, R. (1993). Deterministic network interdiction, Mathematical and Computer Modelling 17(2): 1–18.
• [52] Zang, X.-D., Gong, J. and Hu, X.-Y. (2019). An adaptive profile-based approach for detecting anomalous traffic in backbone, IEEE Access 7: 56920–56934.
• [53] Zargar, S.T., Joshi, J. and Tipper, D. (2013). A survey of defense mechanisms against distributed denial of service (DDoS) flooding attacks, IEEE Communications Surveys and Tutorials 15(4): 2046–2069.
• [54] Zekri, M., Kafhali, S.E., Aboutabit, N. and Saadi, Y. (2017). Ddos attack detection using machine learning techniques in cloud computing environments, 2017 3rd International Conference of Cloud Computing Technologies and Applications (CloudTech), Rabat, Morocco, pp. 1–7.