On the difficulty of scalably detecting network attacks

Kirill Levchenko, Ramamohan Paturi, George Varghese

Research output: Contribution to journalConference article

Abstract

Most network intrusion tools (e.g., Bro) use per-flow state to reassemble TCP connections and fragments in order to detect network attacks (e.g., SYN Flooding or Connection Hijacking) and preliminary reconnaissance (e.g., Port Scans). On the other hand, if network intrusion detection is to be implemented at high speeds at network vantage points, some form of aggregation is necessary. While many security analysts believe that such per-flow state is required for many of these problems, there is no clear proof that this is the case. In fact, a number of problems (such as detecting large traffic footprints or counting identifiers) have scalable solutions. In this paper, we initiate the study of identifying when and how a security attack detection problem can have a scalable solution. We use tools from Communication Complexity to prove that the common formulations of many well-known intrusion detection problems (detecting SYN Flooding, Port Scans, Connection Hijacking, and content matching across fragments) require per-flow state. Our theory exposes assumptions that need to be changed to provide scalable solutions to these problems; we conclude with some systems techniques to circumvent these lower bounds.

Original languageEnglish (US)
Pages (from-to)12-20
Number of pages9
JournalProceedings of the ACM Conference on Computer and Communications Security
StatePublished - Dec 1 2004
Externally publishedYes
EventProceedings of the 11th ACM Conference on Computer and Communications Security, CCS 2004 - Washington, DC, United States
Duration: Oct 25 2004Oct 29 2004

Fingerprint

Intrusion detection
Agglomeration
Communication

Keywords

  • Communication complexity
  • Network intrusion detection

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications

Cite this

On the difficulty of scalably detecting network attacks. / Levchenko, Kirill; Paturi, Ramamohan; Varghese, George.

In: Proceedings of the ACM Conference on Computer and Communications Security, 01.12.2004, p. 12-20.

Research output: Contribution to journalConference article

@article{6a0e08c291154876a6e975b6a1c07133,
title = "On the difficulty of scalably detecting network attacks",
abstract = "Most network intrusion tools (e.g., Bro) use per-flow state to reassemble TCP connections and fragments in order to detect network attacks (e.g., SYN Flooding or Connection Hijacking) and preliminary reconnaissance (e.g., Port Scans). On the other hand, if network intrusion detection is to be implemented at high speeds at network vantage points, some form of aggregation is necessary. While many security analysts believe that such per-flow state is required for many of these problems, there is no clear proof that this is the case. In fact, a number of problems (such as detecting large traffic footprints or counting identifiers) have scalable solutions. In this paper, we initiate the study of identifying when and how a security attack detection problem can have a scalable solution. We use tools from Communication Complexity to prove that the common formulations of many well-known intrusion detection problems (detecting SYN Flooding, Port Scans, Connection Hijacking, and content matching across fragments) require per-flow state. Our theory exposes assumptions that need to be changed to provide scalable solutions to these problems; we conclude with some systems techniques to circumvent these lower bounds.",
keywords = "Communication complexity, Network intrusion detection",
author = "Kirill Levchenko and Ramamohan Paturi and George Varghese",
year = "2004",
month = "12",
day = "1",
language = "English (US)",
pages = "12--20",
journal = "Proceedings of the ACM Conference on Computer and Communications Security",
issn = "1543-7221",
publisher = "Association for Computing Machinery (ACM)",

}

TY - JOUR

T1 - On the difficulty of scalably detecting network attacks

AU - Levchenko, Kirill

AU - Paturi, Ramamohan

AU - Varghese, George

PY - 2004/12/1

Y1 - 2004/12/1

N2 - Most network intrusion tools (e.g., Bro) use per-flow state to reassemble TCP connections and fragments in order to detect network attacks (e.g., SYN Flooding or Connection Hijacking) and preliminary reconnaissance (e.g., Port Scans). On the other hand, if network intrusion detection is to be implemented at high speeds at network vantage points, some form of aggregation is necessary. While many security analysts believe that such per-flow state is required for many of these problems, there is no clear proof that this is the case. In fact, a number of problems (such as detecting large traffic footprints or counting identifiers) have scalable solutions. In this paper, we initiate the study of identifying when and how a security attack detection problem can have a scalable solution. We use tools from Communication Complexity to prove that the common formulations of many well-known intrusion detection problems (detecting SYN Flooding, Port Scans, Connection Hijacking, and content matching across fragments) require per-flow state. Our theory exposes assumptions that need to be changed to provide scalable solutions to these problems; we conclude with some systems techniques to circumvent these lower bounds.

AB - Most network intrusion tools (e.g., Bro) use per-flow state to reassemble TCP connections and fragments in order to detect network attacks (e.g., SYN Flooding or Connection Hijacking) and preliminary reconnaissance (e.g., Port Scans). On the other hand, if network intrusion detection is to be implemented at high speeds at network vantage points, some form of aggregation is necessary. While many security analysts believe that such per-flow state is required for many of these problems, there is no clear proof that this is the case. In fact, a number of problems (such as detecting large traffic footprints or counting identifiers) have scalable solutions. In this paper, we initiate the study of identifying when and how a security attack detection problem can have a scalable solution. We use tools from Communication Complexity to prove that the common formulations of many well-known intrusion detection problems (detecting SYN Flooding, Port Scans, Connection Hijacking, and content matching across fragments) require per-flow state. Our theory exposes assumptions that need to be changed to provide scalable solutions to these problems; we conclude with some systems techniques to circumvent these lower bounds.

KW - Communication complexity

KW - Network intrusion detection

UR - http://www.scopus.com/inward/record.url?scp=14844303748&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=14844303748&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:14844303748

SP - 12

EP - 20

JO - Proceedings of the ACM Conference on Computer and Communications Security

JF - Proceedings of the ACM Conference on Computer and Communications Security

SN - 1543-7221

ER -