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 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. In this paper, we use tools from Communication Complexity to prove that the common formulations of many well-known intrusion detection problems 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.