1. bookVolume 32 (2022): Edition 1 (March 2022)
Détails du magazine
Première parution
05 Apr 2007
4 fois par an
access type Accès libre

Exact and Approximation Algorithms for Sensor Placement Against DDoS Attacks

Publié en ligne: 31 Mar 2022
Volume & Edition: Volume 32 (2022) - Edition 1 (March 2022)
Pages: 35 - 49
Reçu: 07 Jun 2021
Accepté: 17 Sep 2021
Détails du magazine
Première parution
05 Apr 2007
4 fois par an

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.


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

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. Search in Google Scholar

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Articles recommandés par Trend MD

Planifiez votre conférence à distance avec Sciendo