TY - JOUR
T1 - A packet filter placement problem with application to defense against spoofed denial of service attacks
AU - Armbruster, Benjamin
AU - Smith, J. Cole
AU - Park, Kihong
N1 - Funding Information:
The authors are grateful to the anonymous referees, whose comments helped improve the paper. B. Armbruster acknowledges the support of an Undergraduate Research Assistantship from the University of Arizona. J.C. Smith acknowledges the support of the Defense Advanced Research Projects Agency (DARPA) under Grant No. N66001-01-1-8925. K. Park was supported, in part, by grants from DARPA (AFRL F30602-01-2-0539), ETRI, NSF (ANI-9875789, EIA-9972883, ANI-0082861), and Xerox.
PY - 2007/1/16
Y1 - 2007/1/16
N2 - We analyze a problem in computer network security, wherein packet filters are deployed to defend a network against spoofed denial of service attacks. Information on the Internet is transmitted by the exchange of IP packets, which must declare their origin and destination addresses. A route-based packet filter verifies whether the purported origin of a packet is correct with respect to the current route map. We examine the optimization problem of finding a minimum cardinality set of nodes to filter in the network such that no spoofed packet can reach its destination. We prove that this problem is NP-hard, and derive properties that explicitly relate the filter placement problem to the vertex cover problem. We identify topologies and routing policies for which a polynomial-time solution to the minimum filter placement problem exists, and prove that under certain routing conditions a greedy heuristic for the filter placement problem yields an optimal solution.
AB - We analyze a problem in computer network security, wherein packet filters are deployed to defend a network against spoofed denial of service attacks. Information on the Internet is transmitted by the exchange of IP packets, which must declare their origin and destination addresses. A route-based packet filter verifies whether the purported origin of a packet is correct with respect to the current route map. We examine the optimization problem of finding a minimum cardinality set of nodes to filter in the network such that no spoofed packet can reach its destination. We prove that this problem is NP-hard, and derive properties that explicitly relate the filter placement problem to the vertex cover problem. We identify topologies and routing policies for which a polynomial-time solution to the minimum filter placement problem exists, and prove that under certain routing conditions a greedy heuristic for the filter placement problem yields an optimal solution.
KW - Combinatorial optimization
KW - Internet
KW - Route-based packet filtering
KW - Spoofed denial of service attack
KW - Vertex cover
UR - http://www.scopus.com/inward/record.url?scp=33749539695&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33749539695&partnerID=8YFLogxK
U2 - 10.1016/j.ejor.2005.09.031
DO - 10.1016/j.ejor.2005.09.031
M3 - Article
AN - SCOPUS:33749539695
SN - 0377-2217
VL - 176
SP - 1283
EP - 1292
JO - European Journal of Operational Research
JF - European Journal of Operational Research
IS - 2
ER -