Annals of Computer Science and Information Systems, Volume 21

DOI: http://dx.doi.org/10.15439/2020F106

Citation: Proceedings of the 2020 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 21, pages 295–301 (2020)

Full text

Abstract. 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.

References

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. http://dx.doi.org/10.1145/997150.997156. [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. Springer, 2004. http://dx.doi.org/10.1007/978-3-540-31815-6 17 pp. 204–210. [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. http://dx.doi.org/10.1016/0895-7177(93)90236-R. [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. http://dx.doi.org/10.1007/s10589-013-9589-9. [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.