Optimal Sensor Placement for Detection against Distributed Denial of Service Attacks

M. H. Islam, K. Nadeem, S. A Khan


Distributed denial of service (DDoS) attacks have become a major threat to organizations and especially to internet and intranet. In DDoS attacks targets are overwhelmed by sending an enormous amount of traffic from a number of attack sites. The major task of any defense system is to detect these attacks accurately and quickly, before it causes an unrecoverable loss. Most of the research in this regard has been focused on the detection techniques without exploiting spatial placement of detection system in a network. The ideal way to completely eliminate the DDoS threat is to run detection mechanism on every node in the network, which is not a practical solution. In this paper, we focus on the optimized placement of detection nodes in a network for distributed detection of DDoS attacks which not only minimize the number of these node required but also reduce the cost, processing overheads and larger delays in identifying an attack. We examine the placement problem of finding a minimum cardinality set of nodes to detect DDoS attacks such that no attack traffic can reach the target without being monitored by these sensors. The placement problem is first formulated as set packing and then as set covering. The solution to both of these formulations is NP hard; therefore, two efficient heuristic algorithms are presented and compared for minimizing the number of detection nodes and finding the optimal placement in a network, thus preventing the impact of distributed attacks. Both algorithms give a near optimal number of detection nodes.

Full Text:



Wan, K.K.K.; Chang, R.K.C., "Engineering of a global defense infrastructure for DDoS attacks," Networks, 2002. ICON 2002. 10th IEEE International Conference on , vol., no., pp. 419-427,2002

Mirkovic, J., Robinson, M., Reiher, P. and Oikonomou, G. “Distributed Defense against DDoS Attacks”, University of Delaware CIS Department Technical Report CIS-TR-2005- 2.

CHANG, R. K. C. “Defending against flooding-based, distributed denial-of-service attacks:” A tutorial, IEEE Communications Magazine 40(10): 42–51

Aditya A., Ashwin B., Mike Reiter and Srinivasan Seshan, “Detecting DDoS Attacks on ISP Networks”, ACM SIGMOD/PODS Workshop on Management and Processing of Data Streams (MPDS), FCRC 2003, San Diego, CA.

Mirkovic, G. Prier, and P. L. Reiher, “Attacking DDoS at the source,” in Proceedings of the IEEE International Conference on Network Protocols (ICNP '02), pp. 312–321, Paris, France, November 2002

Mirkovic, J. and Reiher, P., D-WARD: A Source-End Defense Against Flooding Denial-of-Service Attacks, IEEE Transactions on Dependable and Secure Computing, Vol. 2, No. 3, July-September 2005, pp. 216-232

Guangsen Z., Manish, P: Cooperative Defense against DDoS Attacks. Journal of Research and Practice in Information Technology 38(1): (2006)

Garey, M.R., Johson, D.S., “Computers and Intractability: a Guide to the Theory of NP completeness”, W.H. Freeman and Company, San Francisco (1979)

Gallager, R. G. “Distributed Minimum Hop Algorithms”, Tech. Rep. P1175, MIT Laboratory for Information and Decision Systems, 1982

Seok B.J., Young W.C., Sehum K.“An Effective Placement of Detection Systems for Distributed Attack Detection in Large Scale Network” WISA 2004, LNCS 3325, pp. s204- 210, 2004

Dong, X., Riccardo, B., and Wei, Z.o, A Gateway-Based Defense System for Distributed DoS Attacks in High Speed Networks, in Proc. of IEEE Systems, Man, and Cybernetics Information Assurance Workshop (IAW), June 2001, pp. 212-219

El Defrawy, K.; Markopoulou, A.; Argyraki, K., "Optimal Allocation of Filters against DDoS Attacks," Information Theory and Applications Workshop, 2007 , vol., no., pp.140-149, Jan. 29 2007-Feb. 2 2007

Benjamin, A., Cole S.J., Kihong, P.; “A Packet Filter Placement Problem with Application to Defense Against Spoofed Denial of Service Attacks”, European Journal of Operation Research, Volume 176, Issue 2, 16 January 2007, Pages 1283-1292

Chvatal, V.; “A Greedy Heuristic for the SetCovering Problem”, Math. of OR 4:3 (1979), pp. 233-235

Hochbaun, D. S.; “Approximate Algorithms for the Set Covering and Vertex Covering Problems”, SIAM Journal on Computing,11 (1982), pp. 555-556

Johnson, D. S.; “Approximate Algorithms for Combinatorial Problems”, Journal of Computer System Science, 9 (1974), pp. 256- 278

Parekh, A. K.; “Analysis of Greedy Heuristic for Finding Small Dominating Sets in Graphs”, Information processing letters, 39 (1991), pp. 237-240

Vizing, V.G.; “A Bound on the External Stability Number of a Graph”, Doklady A.N., 1964 (1965), pp.729-731

Ruiliang, C., Jung-Min, P., Randolph, M.; "A Divide-and-Conquer Strategy for Thwarting Distributed Denial-of-Service Attacks," IEEE Transactions on Parallel and Distributed Systems, vol. 18, no. 5, pp. 577-588, May, 2007

Yu, C.; Kai, H.; Wei-Shinn K., “Collaborative Detection of DDoS Attacks over Multiple Network Domains” IEEE Transactions on Parallel and Distributed Systems, Volume 18, Issue 12, Page(s):1649 – 1662, Dec. 2007

Copyright (c) 2016 M. H. Islam, K. Nadeem, S. A Khan

Powered By KICS