Router-based anomaly/intrusion detection and mitigation

In this thesis, I propose and develop a network-based attack defense system, RAIDM. I focus on network based defense because of the following reasons: (i) network gateways/routers are the vantage points for detecting large scale attacks; (ii) only host based detection/prevention is not enough for modern networks. RAIDM has four components: sketch-based monitoring and detection, polymorphic worm signature generation, signature matching engines and network situational awareness.;The first module is sketch-based monitoring and detection. In this thesis, leveraging data streaming techniques such as reversible sketch, we design HiFIND [1], a High-speed Flow-level Intrusion Detection system. We also propose a two-dimensional sketch for attack differentiation. HiFIND (i) is scalable to flow-level detection on high-speed networks; (ii) is DoS resilient; (iii) can distinguish SYN flooding and various port scans (mostly for worm propagation) for effective mitigation; (iv) enables aggregate detection over multiple routers/gateways; and (v) separates anomalies to limit false positives in detection. Both theoretical analysis and evaluation with several router traces show that HiFIND achieves these properties. To the best of our knowledge, HiFIND is the first online DoS resilient flow-level intrusion detection system for high-speed networks (e.g. OC192), even for the worst case traffic of 40-byte-packet streams with each packet forming a flow.;The second module is polymorphic worm signature generation. Recently, worms and remote exploits sent by botnets have become the major tools for launching Internet attacks. It is critical to quickly generate signatures in response to those fast propagating threats. To this end, I have developed two types of automated worm signature generation approaches (token-based signature generator and length based signature generator) with different information availability requirement and underlying assumptions. Beside token based signature generator, we design a network-based Length-based Signature Generator (LESG) for worms exploiting buffer overflow vulnerabilities. We further prove the attack resilience bounds even under the worst case attacks with deliberate noise injection. Moreover, LESG is fast and noise-tolerant and has efficient signature matching.;The third module is signature matching engines. In this thesis, we design NetShield, a vulnerability signature based NIDS/NIPS which achieves high throughput comparable to that of the state-of-the-art regex-based systems while offering much better accuracy. This is accomplished because of the following contributions: (i) we propose a candidate selection algorithm that efficiently matches thousands of vulnerability signatures simultaneously using a small amount of memory; (ii) we propose a parsing transition state machine that achieves fast protocol parsing; (iii) we implement the NetShield prototype, including rewriting the ruleset of Snort to vulnerability signatures. Experimental results show that the core engine of NetShield achieves 1.9Gbps signature matching throughput for 794 HTTP vulnerability signatures on a 3.8GHz PC.;Finally, the fourth module is network situational awareness for botnet probings. Botnets dominate today's attack landscape. In this thesis, we investigate ways to analyze collections of malicious probing traffic in order to understand the significance of large-scale "botnet probes". In such events, an entire collection of remote hosts together probes the address space monitored by a sensor in some sort of coordinated fashion. Our goal is to develop methodologies by which sites receiving such probes can infer---using purely local observation---information about the probing activity: What scanning strategies does the probing employ? Is this an attack that specifically targets the site, or is the site only incidentally probed as part of a larger, indiscriminant attack? Our analysis draws upon extensive honeynet data to explore the prevalence of different types of scanning, including properties such as trend, uniformity, coordination and darknet avoidance. In addition, we design schemes to extrapolate the global properties of scanning events (e.g., total population and target scope) as inferred from the limited local view of a honeynet. (Abstract shortened by UMI.)...