Article ID: | iaor20084557 |
Country: | Netherlands |
Volume: | 176 |
Issue: | 2 |
Start Page Number: | 1283 |
End Page Number: | 1292 |
Publication Date: | Jan 2007 |
Journal: | European Journal of Operational Research |
Authors: | Smith J. Cole, Armbruster Benjamin, Park Kihong |
Keywords: | combinatorial optimization |
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.