An Algorithm For Detecting Superpoints In Small Memory

A superpoint is a source IP (destination IP) that has communicated with a large number of distinct destinations (sources) during a measurement period. Detecting superpoints in real time is a meaningful work for network security and management. There has the similar behavioral characteristic in many network security incidents, e.g. distributed denial of service attacks (DDOS), worms and port scans. The common feature of these attacks is that the source IP (destination IP) will send or receive a larger number of links from distinct destinations (sources). All these source or destination IPs are the instances of superpoints.Although there have been some algorithms for detecting superpoints, they are not control the usage of the memory or do not deliver the desired accuracy. In this paper, we propose a new algorithm for detecting superpoints called as SuperpointTrap. The most essential advantage of SuperpointTrap is that it can work in tight memory space. Its accuracy and efficiency come from a new structure for data storage called Cache For each flow, Cache uses only one bit to record its information. The row and column of this bit are determined by the source IP and destination IP respectively. When the number of the flow in Cache is greater than the threshold, the host is considered as a superpoint. Then, this Superpoint’s information is exported and the corresponding information in Cache is cleared to facilitate the following packets and to effectively save the memory consumption. To further reduce the false negative rate (FNR), we also propose two improved algorithms:P-SuperpointTrap and BF-SuperpointTrap and analyze the above three algorithms.In this paper, we use different data sources to test our algorithms and adopt false positive rate (FPR) and false negative rate (FNR) as our evaluation metric. The experimental results show that SuperpointTrap can not only saves memory, but also accurately and efficiently detects the superpoints. By the experimental comparison of SuperpointTrap and two improved algorithms, the two improved algorithms can further reduce the false negative rate.