Site reliability against anomalous behaviors

Abstract

Many attacks that threaten service providers and legitimate users are anomalous behaviors out of specification, and this dissertation mainly focuses on detecting “large” Internet flows consuming more resources than those allocated to them. Being able to identify large flows accurately can greatly benefit Quality of Service (QoS) schemes and Distributed Denial of Service (DDoS) defenses. Although large-flow detection has been previously explored, proposed approaches have not been practical for high-capacity core routers due to high memory and processing overhead. Additionally, more efficient schemes are vulnerable against specially tailored attacks in which attackers time their packets based on the knowledge of legitimate cross-traffic.

In this dissertation, we aim to design computation- and memory-efficient large-flow detection algorithms to effectively mitigate the large-flow damage in adversarial environments. We propose three large-flow detection schemes: Exact-Outside-Ambiguity-Region Detector (EARDet), Recursive Large-Flow Detection (RLFD), and the scheme of in-Core Limiting of Egregious Flows (CLEF), which is a hybrid scheme with one EARDet and two RLFDs. EARDet is a deterministic algorithm that guarantees exact large-flow detection outside an ambiguity region: there is no false accusation for legitimate flows complying with a low-bandwidth threshold, and no false negative for large flows above a high-bandwidth threshold, with no assumption on the input traffic or attack patterns. Because of the strong enforcement with the arbitrary window model, EARDet is able to immediately detect both flat and bursty flows. RLFD is designed to complement EARDet in detecting large flows in EARDet’s ambiguity region. RLFD is a probabilistic detection scheme that gives higher probability for detecting large flows with higher volume, thus guarantee limited damage (to legitimate flows) across a wide range of flow overuse amounts. Finally CLEF combines EARDet and RLFD to achieve both rapid detection for very large flows and eventually detection for small, persistent large flows. Theoretical analysis and experimental evaluation both suggest the CLEF’s efficiency and effectiveness outperform existing algorithms.