On the difficulty of scalably detecting network attacks

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.