Algorithms Based On FM Sketch For Detecting Superpoints

With the rapid development of the computer network, network attacks occur frequently, such as worm attacks, distributed denial of service(DDoS) attacks, port scans and so on. These attacks generate a large number of network connections within a short time, and further cause network congestion and even paralysis. For example, a compromised host doing fast scanning for worm propagation often makes a high number of connections to distinct destinations within a short time. When a DDoS attack happens, a lot of distinct hosts will send packets to the victim. The superpoints are source hosts that connect with a great deal of destination hosts during a measurement interval. Therefore, detecting the superpoints in real time is very significant for network security and management.This paper use Flajolet-Martin(FM) Sketch and IP mangling to detect superpoints. FM Skecth is a randomized couting structure, and IP mangling uses a hash function mapping IP addresses into bit strings with size 32, and the hash function is reversible. Based on the above two techniques, we propose two algorithms for detecting superpoints. The first algorithm consists of five 2-dimentional bit arrays and six hash functions. Four of these functions select some consecutive bits from source IP strings as function values. Source IP addresses can be reconstructed by the overlapping of hash bit strings, although they are not stored explicitly. This scheme significantly reduces the number of memory accesess. This algorithm consists of two modules. The online module processes each arriving packet and updates bit arrays, and the offline processing module estimates the cardinalities of superpoints, reconstructs source IP addresses and outputs the information of superpoints. The second algorithm applies IP mangling in the online module. The algorithm first mangle source IP addresses before updating bit arrays. Finally, in the offline module we reverse the reconstructed source IPs by using IP mangling.We do experiments by using traces collected from different locations of the Internet. We adopt the positive rate and the negative rate as evaluation metric. The experimental results show that the proposed algorithms can detect superpoints precisely and efficiently through comparing with the existing algorithm.