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

Benjamin Armbruster, J. Cole Smith, Kihong Park

Research output: Contribution to journalArticlepeer-review

12 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)1283-1292
Number of pages10
JournalEuropean Journal of Operational Research
Volume176
Issue number2
DOIs
StatePublished - Jan 16 2007

Keywords

  • Combinatorial optimization
  • Internet
  • Route-based packet filtering
  • Spoofed denial of service attack
  • Vertex cover

ASJC Scopus subject areas

  • Computer Science(all)
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Fingerprint Dive into the research topics of 'A packet filter placement problem with application to defense against spoofed denial of service attacks'. Together they form a unique fingerprint.

Cite this