As malicious attacks on computer systems increase in severity and sophistication, developing effective methods for protecting the Internet is among the most important challenges facing computer science today. Network-based security mechanisms offer both good coverage and the possibility of early threat detection, but they often conflict with the performance requirements of network elements because of the vast amounts of traffic data that must be analyzed. This project will apply massive-dataset (MDS) algorithmics to network security, bringing together two previously unconnected research areas. The objective is to achieve a qualitative improvement in network security by developing efficient, yet theoretically rigorous, algorithmic defenses that can be deployed at scale in modern networks.
The project addresses both fundamental algorithm-design problems and practical applications. MDS algorithmics provides a set of basic techniques for highly efficient (e.g., one-pass, small-space, polylog-time) analysis of large amounts of data. This project will investigate how these methods can be used for (1) online classification and property testing of packet streams, including efficient inference of streams generated by a mixture of stochastic sources, (2) detection of changes and anomalies in traffic patterns, and (3) development of computationally tractable models of traffic sources that support reasoning about a wide variety of adversarial behaviors and incorporate prior knowledge such as conventional intrusion-detection rules. The algorithmic toolkit developed in the course of the project will be applied to practical network-security problems such as recognizing denial of service activity, worm fingerprinting, and detecting botnets.
