Algorithms For Detecting Superpoints Based On Cuckoo Sampling

Superpoints are the hosts which connect with a great deal of different source hosts(destination hosts)in a measurement period.Lots of network attack events(DDoS,worm,port scanning)have the same behavior characteristics of network.Therefore,detecting superpoints is very important for network security and services.Real-time detecting superpoints and obtaining its information are one of the hot topics in the research of network security.To address the problem of existing algorithms for detecting superpoints requiring large memory consumption and achieving low measurement accuracy,we propose two algorithms for detecting superpoints based on Cuckoo sampling.The first algorithm combines Cuckoo sampling and Snare algorithm.It improves the updating operation for Snare by adopting a recursive insertion method in the process of data inserting,which avoids the multiple superpoints mapped onto the same storage location so as to make some superpoints fail to occupy place,consequently negatively impacting the accuracy of detecting.In addition,a great deal of redundant packets in the network can impact the whole performance of algorithms.In order to improve the detection performance of the first algorithm,the second algorithm with filters for detecting superpoints was proposed by applying redundant packet filter(Bloom Filter-0)and single-flow source filter(Bloom Filter-1)to Cuckoo sampling algorithm for detecting superpoints.Finally,we show the feasibility and accuracy of our algorithms through the analysis of theory and experiments.In the experiment part,we use three different network trace data to carry on the experiment.The results of the experiments indicate that algorithms for detecting superpoints based on Cuckoo sampling not only improve the utilization rate of memory space,but also can detect superpoints accurately and effectively.By comparing with other algorithms for detecting superpoints,the two proposed algorithms have some advantages in memory consumption and measurement accuracy.