Scalable and efficient distributed algorithms for defending against malicious Internet activity

The threat of malicious Internet activities such as Distributed Denial of Service (DDoS) attacks, spam emails or Internet worms/viruses has been increasing in the last several years. The impact and frequency of these malicious activities are expected to grow unless they are properly addressed. Unfortunately, the current Internet does not provide proper defense mechanisms against these malicious activities. In this thesis, we propose to design and evaluate a set of practical and effective protection measures against potential malicious activities in current and future networks. Our research objective is twofold.;First, we design the methods to defend against DDoS attacks. Our research focuses on two important issues related to DDoS attack defense mechanisms. One issue is the method to trace the sources of attacking packets, which is known as IP traceback. We propose a novel packet logging based (i.e., hash-based) traceback scheme using only a one-bit marking field in IP header. It reduces processing and storage cost by an order of magnitude than the existing hash-based schemes, and is therefore scalable to much higher link speed (e.g., OC-768). Next, we propose an improved traceback scheme with lower storage overhead by using more marking space in IP header. Another issue in DDoS defense is to investigate protocol-independent techniques for improving the throughput of legitimate traffic during DDoS attacks. We propose a novel technique that can effectively filter out the majority of DDoS traffic, thus improving the overall throughput of the legitimate traffic. Our baseline methodology is to preferentially filter packets that are more likely to come from attackers, based on the location information about the attackers learned using a generalized form of IP traceback.;Second, we investigate the problem of distributed network monitoring for early detection of Internet worms/viruses or spam emails. It is often desirable to perform data streaming analysis on the traffic aggregated over hundreds or even thousands of links/nodes, which will provide network operators with a holistic view of the network operation. However, sending raw traffic data to a centralized location (i.e., "raw aggregation") for streaming analysis is clearly not a feasible approach for a large network. We propose a set of novel distributed data streaming algorithms that allow scalable and efficient monitoring of aggregated traffic without the need for raw aggregation. Our algorithms target the specific network monitoring problem of finding common content in traffic traversing several nodes/links across the Internet. These algorithms find applications in network-wide intrusion detection, early warning for fast propagating worms, and detection of hot objects and spam tragic.;Simulation results based on real-world network topologies demonstrate that the proposed techniques can be efficiently used for defending against malicious Internet activity. We expect our algorithms and theoretical framework to apply to new applications in the future Internet.