Exact and Heuristic Algorithms for Solving the Generalized Minimum Filter Placement Problem

Persistent Link:
http://hdl.handle.net/10150/194097
Title:
Exact and Heuristic Algorithms for Solving the Generalized Minimum Filter Placement Problem
Author:
Mofya, Enock Chisonge
Issue Date:
2005
Publisher:
The University of Arizona.
Rights:
Copyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.
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.The primary contributions of this dissertation are as follows. We formulate and discuss the modeling of this filter placement problem as a mixed-integer program. We then show the sensitivity of the optimal number of deployed filters as the required level of security changes, and demonstrate that current vertex cover-based heuristics are ineffective for problems with relaxed security levels. We identify a set of special network topologies on which the filter placement problem is solvable in polynomial time, focusing our attention on the development of a dynamic programming algorithm for solving this problem on tree networks. These results can then in turn be used to derive valid inequalities for an integer programming model of the filter placement problem. Finally, we present heuristic algorithms based on the insights gained from our overall study for solving the problem, and evaluate their performance against the optimal solution provided by our integer programming model.
Type:
text; Electronic Dissertation
Keywords:
Integer programming; Network security; route-based filters; Heuristics
Degree Name:
PhD
Degree Level:
doctoral
Degree Program:
Systems & Industrial Engineering; Graduate College
Degree Grantor:
University of Arizona
Advisor:
Smith, Jonathan C.
Committee Chair:
Smith, Jonathan C.

Full metadata record

DC FieldValue Language
dc.language.isoENen_US
dc.titleExact and Heuristic Algorithms for Solving the Generalized Minimum Filter Placement Problemen_US
dc.creatorMofya, Enock Chisongeen_US
dc.contributor.authorMofya, Enock Chisongeen_US
dc.date.issued2005en_US
dc.publisherThe University of Arizona.en_US
dc.rightsCopyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.en_US
dc.description.abstractWe 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.The primary contributions of this dissertation are as follows. We formulate and discuss the modeling of this filter placement problem as a mixed-integer program. We then show the sensitivity of the optimal number of deployed filters as the required level of security changes, and demonstrate that current vertex cover-based heuristics are ineffective for problems with relaxed security levels. We identify a set of special network topologies on which the filter placement problem is solvable in polynomial time, focusing our attention on the development of a dynamic programming algorithm for solving this problem on tree networks. These results can then in turn be used to derive valid inequalities for an integer programming model of the filter placement problem. Finally, we present heuristic algorithms based on the insights gained from our overall study for solving the problem, and evaluate their performance against the optimal solution provided by our integer programming model.en_US
dc.typetexten_US
dc.typeElectronic Dissertationen_US
dc.subjectInteger programmingen_US
dc.subjectNetwork securityen_US
dc.subjectroute-based filtersen_US
dc.subjectHeuristicsen_US
thesis.degree.namePhDen_US
thesis.degree.leveldoctoralen_US
thesis.degree.disciplineSystems & Industrial Engineeringen_US
thesis.degree.disciplineGraduate Collegeen_US
thesis.degree.grantorUniversity of Arizonaen_US
dc.contributor.advisorSmith, Jonathan C.en_US
dc.contributor.chairSmith, Jonathan C.en_US
dc.contributor.committeememberSmith, Jonathan C.en_US
dc.contributor.committeememberAskin, Ronald G.en_US
dc.contributor.committeememberPitu, Mirchandani B.en_US
dc.contributor.committeememberBayly, Bruce J.en_US
dc.contributor.committeememberIndik, Robert A.en_US
dc.identifier.proquest1311en_US
dc.identifier.oclc137354960en_US
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.