A packet filter placement problem with application to defense against spoofed denial of service attacks

A packet filter placement problem with application to defense against spoofed denial of service attacks

0.00 Avg rating0 Votes
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: , ,
Keywords: combinatorial optimization
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.