Exact and approximation algorithms for sensor placement against DDoS attacks

• Autorzy: Junosza-Szaniawski Konstanty , Nogalski Dariusz , Wójcik Agnieszka

Identyfikatory

DOI

10.15439/2020F106

• Konferencja: Federated Conference on Computer Science and Information Systems (15 ; 06-09.09.2020 ; Sofia, Bulgaria)
• Języki publikacji: EN

Abstrakty

EN

In DDoS attack (Distributed Denial of Service), an attacker gains control of many network users by a virus. Then the controlled users send many requests to a victim, leading to lack of its resources. DDoS attacks are hard to defend because of distributed nature, large scale and various attack techniques. One of possible ways of defense is to place sensors in the network that can detect and stop an unwanted request. However, such sensors are expensive so there is a natural question about a minimum number of sensors and their optimal placement to get the required level of safety. We present 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 above placement problems are NP-hard, two efficient heuristics are designed, implemented and compared experimentally with exact linear programming solvers.

Słowa kluczowe

EN

Distributed Denial of Service; DDoS; sensor placement; network safety optimization; minimum multicut; heuristics

PL

rozproszona odmowa usługi; DDoS; lokalizacja czujnika; optymalizacja bezpieczeństwa sieci; heurystyka

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2020
• Tom: Vol. 21
• Strony: 295--301
• Opis fizyczny: Bibliogr. 17 poz., wz., rys., wykr.

Twórcy

autor

Junosza-Szaniawski Konstanty

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

autor

Nogalski Dariusz

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

autor

Wójcik Agnieszka

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

Bibliografia

• 1. S. T. Zargar, J. Joshi, and D. Tipper, “A survey of defense mechanisms against distributed denial of service (DDOS) flooding attacks,” IEEE Communications Surveys and Tutorials, vol. 15, no. 4, pp. 2046–2069, 2013. http://dx.doi.org/10.1109/SURV.2013.031413.00127
• 2. P. J. Criscuolo, “Distributed Denial of Service Trin00, Tribe Flood Network, Tribe Flood Network 2000, And Stacheldraht, CIAC-2319,” Department of Energy Computer Incident Advisory Capability (CIAC), Lawrence Livermore National Laboratory, 2000.
• 3. K. Wang, M. Du, S. Maharjan, and Y. Sun, “Strategic honeypot game model for distributed denial of service attacks in the smart grid,” IEEE Transactions on Smart Grid, vol. 8, no. 5, pp. 2474–2482, Sep. 2017. http://dx.doi.org/10.1109/TSG.2017.2670144
• 4. N. Provos and T. Holz, Virtual Honeypots: From Botnet Tracking to Intrusion Detection. Addison-Wesley, 2007. ISBN 978-0321336323
• 5. C. Cameron, C. Patsios, P. C. Taylor, and Z. Pourmirza, “Using Self-Organizing Architectures to Mitigate the Impacts of Denial-of-Service Attacks on Voltage Control Schemes,” IEEE Transactions on Smart Grid, vol. 10, no. 3, pp. 3010–3019, 2019. http://dx.doi.org/10.1109/TSG.2018.2817046
• 6. J. Mirkovic and P. Reiher, “A taxonomy of DDoS attack and DDoS defense mechanisms,” ACM SIGCOMM Computer Communication Review, vol. 34, no. 2, p. 39, 2004. [Online]. Available: http://portal.acm.org/citation.cfm?doid=997150.997156
• 7. S. Ranjan, R. Swaminathan, M. Uysal, A. Nucci, and E. Knightly, “DDoS-shield: DDoS-resilient scheduling to counter application layer attacks,” IEEE/ACM Transactions on Networking, vol. 17, no. 1, pp. 26–39, 2009. http://dx.doi.org/10.1109/TNET.2008.926503
• 8. S. B. Jeong, Y. Choi, and S. Kim, “An effective placement of detection systems for distributed attack detection in large scale networks,” in Information Security Applications, 5th International Workshop, WISA 2004, Jeju Island, Korea, August 23-25, 2004, Revised Selected Papers, ser. Lecture Notes in Computer Science, C. H. Lim and M. Yung, Eds., vol. 3325. pp. 204–210, Springer, 2004. [Online]. Available: https://doi.org/10.1007/978-3-540-31815-6_17
• 9. M. H. Islam, K. Nadeem, and S. A. Khan, “Efficient placement of sensors for detection against distributed denial of service attack,” 2008 International Conference on Innovations in Information Technology, IIT 2008, pp. 653–657, 2008. http://dx.doi.org/10.1109/INNOVATIONS.2008.4781681
• 10. D. S. Altner, Ö. Ergun, and N. A. Uhan, “The maximum flow network interdiction problem: Valid inequalities, integrality gaps, and approximability,” Oper. Res. Lett., vol. 38, no. 1, pp. 33–38, 2010. http://dx.doi.org/10.1016/j.orl.2009.09.013.
• 11. R. Wood, “Deterministic network interdiction,” Mathematical and Computer Modelling, vol. 17, no. 2, pp. 1 – 18, 1993. [Online]. Available: http://www.sciencedirect.com/science/article/pii/089571779390236R
• 12. M. Hemmati, J. Cole Smith, and M. T. Thai, “A cutting-plane algorithm for solving a weighted influence interdiction problem,” Computational Optimization and Applications, vol. 57, no. 1, pp. 71–104, Jan. 2014. [Online]. Available: https://doi.org/10.1007/s10589-013-9589-9
• 13. J. Omer and A. Mucherino, “Referenced vertex ordering problem: Theory, applications and solution methods,” Mar. 2020, working paper or preprint. [Online]. Available: https://hal.archives-ouvertes.fr/hal-02509522
• 14. L. R. Ford and D. R. Fulkerson, “Maximal flow through a network,” Canadian Journal of Mathematics, vol. 8, p. 399–404, 1956. doi: 10.4153/CJM-1956-045-5
• 15. T. Hu, “Multi-commodity network flows,” Operations Research, vol. 11, no. 3, p. 344–360, 1963. http://dx.doi.org/10.1287/opre.11.3.344
• 16. E. Dahlhaus, D. Johnson, C. Papadimitriou, P. Seymour, and M. Yannakakis, “The complexity of multiterminal cuts,” SIAM Journal on Computing, vol. 23, no. 4, pp. 864–894, 1994. doi: 10.1137/S0097539792225297
• 17. N. Garg, V. V. Vazirani, and M. Yannakakis, “Multiway cuts in directed and node weighted graphs,” in Automata, Languages and Programming, 21st International Colloquium, ICALP94, Jerusalem, Israel, July 11-14, 1994, Proceedings, ser. Lecture Notes in Computer Science, S. Abiteboul and E. Shamir, Eds., vol. 820. Springer, 1994. http://dx.doi.org/10.1007/3-540-58201-0_92 pp. 487–498.

Uwagi

1. Track 1: Artificial Intelligence

2. Technical Session: 13th International Workshop on Computational Optimization

3. Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).