Compact Algorithms For Finding Superpoints In High Speed Networks

With the rapid development of Internet, network attacks become increasingly frequent, such as worm propagation, distributed denial-of-service attacks, port scanning, etc. They incur declining the quality of service. We call such a host a superpoint, which is the source that connects to a large number of distinct destinations in a short time. Real-time detecting superpoint and obtaining superpoint information are very important for network management and traffic monitoring.The original SuperpointTrap algorithm only identifies the superpoints, but does not record the number of all IP flows generated by each host. To improve the measurement accuracy, we propose C-SuperpointTrap algorithm and S-SuperpointTrap algorithm. C-SuperpointTrap algorithm composes of two modules:online measurement module and offline processing module. Online measurement module improves the updated operation of the original SuperpointTrap algorithm. There is no output of C-SuperpointTrap algorithm when the number of flow generated by the host is larger than a predefined threshold. In the measurement period, C-SuperpointTrap algorithm records the host information that makes superpoints detection more accurate. On offline processing module, a compensation mechanism is proposed to estimate the number of flow generated by each superpoint. The mechanism will compensate the number of flows that is not recorded because they arrive before a superpoint occupy its corresponding entry. In order to reduce the consumption of processing resource and enhance scalability, we further propose S-SuperpointTrap algorithm that is the combination of C-SuperpointTrap algorithm and flow sampling technique.In experiments, we use three traces gathered at different locations of the Internet to test our algorithms. The false negative rate, false positive rate and the Weighted Mean Relative Difference are the evaluation metric. The experimental results show that our algorithms have certain advantages in accuracy and memory consumption.