Exact and heuristic algorithms for solving the generalized minimum filter placement problem |
| |
Authors: | E Chisonge Mofya J Cole Smith |
| |
Institution: | (1) Department of Systems and Industrial Engineering, The University of Arizona, P.O. Box 210020 |
| |
Abstract: | We consider a problem of placing route-based filters in a communication network to limit the number of forged address attacks
to a prescribed level. Nodes in the network communicate by exchanging packets along arcs, and the originating node embeds
the origin and destination addresses within each packet that it sends. In the absence of a validation mechanism, one node
can send packets to another node using a forged origin address to launch an attack against that node. Route-based filters
can be established at various nodes on the communication network to protect against these attacks. A route-based filter examines
each packet arriving at a node, and determines whether or not the origin address could be legitimate, based on the arc on
which the packet arrives, the routing information, and possibly the destination. The problem we consider seeks to find a minimum
cardinality subset of nodes to filter so that the prescribed level of security is achieved. We formulate a mixed-integer programming
model for the problem and derive valid inequalities for this model by identifying polynomially-solvable subgraphs of the communication
network. We also present three heuristics for solving the filter placement problem and evaluate their performance against
the optimal solution provided by the mixed-integer programming model.
The authors gratefully acknowledge the comments of two anonymous referees, whose input led to an improved version of this
paper.
Dr. Smith gratefully acknowledges the support of the Office of Naval Research under Grant #N00014-03-1-0510 and the Defense Advanced Research Projects Agency under Grant #N66001-01-1-8925. |
| |
Keywords: | Mixed-integer programming Facets Heuristics Computer network security Denial of service attacks |
本文献已被 SpringerLink 等数据库收录! |
|