Exact and Approximation Algorithms for Sensor Placement Against DDoS Attacks

Junosza-Szaniawski, Konstanty; Nogalski, Dariusz; Rzążewski, Paweł

doi:10.34768/amcs-2022-0004

Abstract

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.

References

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.
Search in Google Scholar Back to article
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.10.1016/j.orl.2009.09.013
Search in Google Scholar Back to article
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.10.1016/j.ejor.2005.09.031
Search in Google Scholar Back to article
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.10.1109/ACCESS.2017.2702341
Search in Google Scholar Back to article
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.10.1109/CSNET.2018.8602966
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.10.3390/fi9030043
Search in Google Scholar Back to article
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.10.1109/TSG.2018.2817046
Search in Google Scholar Back to article
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.3390/e21020210751469133266925
Search in Google Scholar Back to article
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.10.2478/amcs-2019-0018
Search in Google Scholar Back to article
Criscuolo, P.J. (2000). Distributed Denial of Service: Trin00, Tribe Flood Network, Tribe Flood Network 2000, and Stacheldraht, Lawrence Livermore National Laboratory, Livermore.10.2172/792253
Search in Google Scholar Back to article
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.10.1007/978-3-319-21275-3
Search in Google Scholar Back to article
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.10.1109/TNSM.2020.2972405
Search in Google Scholar Back to article
Douligeris, C. and Mitrokotsa, A. (2004). DDOS attacks and defense mechanisms: Classification and state-of-the-art, Computer Networks 44(5): 643–666.10.1016/j.comnet.2003.10.003
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.usenix.org/conference/usenixsecurity15/technical-sessions/presentation/fayaz.
Search in Google Scholar Back to article
Ford, L.R. and Fulkerson, D.R. (1956). Maximal flow through a network, Canadian Journal of Mathematics 8: 399–404.10.4153/CJM-1956-045-5
Search in Google Scholar Back to article
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.10.1007/3-540-58201-0_92
Search in Google Scholar Back to article
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.10.1186/s13635-018-0079-6
Search in Google Scholar Back to article
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.10.1145/2935634.2935636
Search in Google Scholar Back to article
Goldberg, A.V. and Tarjan, R.E. (2014). Efficient maximum flow algorithms, Communications of the ACM 57(8): 82–89, DOI: 10.1145/2628036.10.1145/2628036
Search in Google Scholar Back to article
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.10.1007/s10589-013-9589-9
Search in Google Scholar Back to article
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.10.1016/j.comnet.2020.107645
Search in Google Scholar Back to article
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.10.1109/ACCESS.2020.3026923
Search in Google Scholar Back to article
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.10.1109/ACCESS.2020.2973023
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.10.1007/s10586-020-03184-1
Search in Google Scholar Back to article
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.10.1007/978-3-540-31815-6_17
Search in Google Scholar Back to article
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.10.1109/SRDS.2017.37
Search in Google Scholar Back to article
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.10.15439/2020F106
Search in Google Scholar Back to article
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.10.1109/JSAC.2016.2558958
Search in Google Scholar Back to article
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.10.1109/SP.2013.19
Search in Google Scholar Back to article
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.10.1109/ACCESS.2019.2908998
Search in Google Scholar Back to article
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.10.2478/v10006-010-0033-3
Search in Google Scholar Back to article
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.10.1109/TIFS.2018.2799425
Search in Google Scholar Back to article
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.10.1016/j.cose.2020.102107
Search in Google Scholar Back to article
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.10.1016/j.comnet.2020.107792
Search in Google Scholar Back to article
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.10.1145/997150.997156
Search in Google Scholar Back to article
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.10.1002/cpe.4266
Search in Google Scholar Back to article
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.10.2298/CSIS170328044M
Search in Google Scholar Back to article
Omer, J. and Mucherino, A. (2020). Referenced vertex ordering problem: Theory, applications and solution methods, Working paper/preprint, https://hal.archives-ouvertes.fr/hal-02509522.
Search in Google Scholar Back to article
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.10.2478/v10006-012-0022-9
Search in Google Scholar Back to article
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.10.1145/1216370.1216373
Search in Google Scholar Back to article
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.10.1145/3201775
Search in Google Scholar Back to article
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.10.1145/3274694.3274717
Search in Google Scholar Back to article
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.10.1109/TNET.2008.926503
Search in Google Scholar Back to article
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.10.1007/978-3-642-04444-1_3
Search in Google Scholar Back to article
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.10.1186/s13638-020-01803-4
Search in Google Scholar Back to article
Uciński, 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.
Search in Google Scholar Back to article
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.10.1109/TSG.2017.2670144
Search in Google Scholar Back to article
Wood, R. (1993). Deterministic network interdiction, Mathematical and Computer Modelling 17(2): 1–18.10.1016/0895-7177(93)90236-R
Search in Google Scholar Back to article
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.10.1109/ACCESS.2019.2914303
Search in Google Scholar Back to article
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.10.1109/SURV.2013.031413.00127
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article

Exact and Approximation Algorithms for Sensor Placement Against DDoS Attacks

Abstract

Paradigm

My account