On the difficulty of scalably detecting network attacks

Kirill Levchenko, Ramamohan Paturi, George Varghese

Research output: Contribution to journalConference article


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


  • Communication complexity
  • Network intrusion detection

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'On the difficulty of scalably detecting network attacks'. Together they form a unique fingerprint.

  • Cite this