A novel spread estimation based abnormal flow detection in high-speed networks

Detecting the flows with abnormally large spreads over big network data can help us identify network attacks, such as DDoS attacks and scanners. Most per-flow measurement studies use compact data structures to reduce their memory requirements, fitting in the limited on-chip memory and catching up with the line rate. In this paper, we study a novel problem called spread estimation among multi-periods to measure the total number of distinct elements or the number of distinct k-persistent elements in a flow among multiple traffic measurement periods. In our design, we use an on-chip/off-chip model to record the per-flow traffic information, which uses small on-chip memory and matches the line rate, i.e., we use on-chip memory to filter out the duplicates, sample the elements, and store the sampled traffic data in off-chip memory. By performing the set operations on the sampled traffic data, we can derive the total number of distinct elements and the number of distinct k-persistent elements among multiple periods based on probability analysis. The experimental results on real Internet traffic traces show that, when performing spread estimation among multiple periods, our estimator is efficient in memory usage and estimation accuracy and can efficiently detect the stealthy DDoS attack and scanners.