Classification Of Super Sources And Bit Sharing-Based Algorithms For Measuring Super Sources

Super source is a host which has connected with a large number of distinct hosts within the measurement period. It is also an important metric for profiling hosts in the field of network measurement. Super source reflects the end-to-end problems in the networks. With the development of internet, many cyber-attacks such as worm spreading, spam email delivery and denial-of-service attack occur frequently. One common characteristic of these attacks is that they usually send or receive a lot of packets in a short time. The problem of detecting these attacks can be viewed as detecting super sources. So super sources detection has very important applications in network security.This paper analyzes the advantages and disadvantages of the existing algorithms for detecting super sources and presents the bit sharing-based algorithm for detecting super sources. The algorithm uses three bit arrays to store network flow information, in this way it can have low space consumption. The algorithm has two modules:online processing module and offline processing module. In the online processing measurement period, the algorithm uses three bit sharing arrays to store all flow information. When a packet comes, the algorithm judges whether it belongs to a new flow or not. If the packet belongs to a new flow, it will be hashed into the three bit arrays, otherwise it will be discarded. According to the flow information stored in the three bit arrays, the algorithm estimates the hosts cardinalities. If a host’s cardinality is bigger than the threshold, it will be regarded as a super source.For know well the characteristics of super sources and its influences on network profiling, this paper classifies super sources into three types:a horizontal scan super source is a host connected with multiple destination IPs and few ports, a vertical scan super source is defined as the host with multiple ports and few destination IPs, the block scan super sources can be viewed as a combination of horizontal scans and vertical scans. Based on the algorithm for detecting super sources, this paper detects the three different super sources respectively and analyzes their characteristics.In experiments, four different traces collected from real networks are used. And the experimental results demonstrate that the algorithm can detect super sources accurately in small memory with low computation overhead.