Algorithms Based On Bitmaps For Detecting Stealthy Spreaders

Stealthy spreader is a source IP (destination IP) that has communicated with a fixed number of distinct destinations (sources) during a measurement period. In the real network, the detection of stealthy spreaders is often very difficult, because they may perform scanning deliberately at a low rate. We observe that these spreaders can easily evade the detection because they may mix in the normal flows. Therefore, the detection of these spreaders is very important, whether for neither the security nor the management. Such as moderate-worm propagation or bonnet scan has similar behavioral characteristics, they send packets to destination host. These hidden attackers easily confuse us and they are hard to be detected.Although the Superpoint-detection technology has been very mature, those algorithms for detecting spreaders can not detect stealthy spreaders. In this paper, we propose two algorithms, which are based on the Bitmap matrix. The two algorithms avoid the drawbacks of traditional Superpoint-detection technology. Being lightweight, the proposed schemes can detect scan sources in high speed networking while residing in SRAM.The first detection algorithm proposed CBS can online detect stealthy spreaders from network traffic. The main structure of the algorithm consists of three Bitmap-matrixes, for each line of the three matrixes a counter is appended for recording the number of1in the line. The algorithm also includes four hash function functions, which hash the source and destination IP to generate the rows and column of the Bitmap matrixes. For the arrival of each packet the three Bitmap-matrixes and counters will be updated. When the line counter is greater than threshold value, the statistical process will be performed. Though this algorithm is simple and takes up less storage space, the accuracy is not very high.To further improve the accuracy, we also propose another detection algorithm, BS algorithm, which is used to off-line detect stealthy spreaders. It also consists of three Bitmap-matrixes, and a new structure called Cache used to store source IPs and their cardinality. Comparing with CBS. BS algorithm is more accurate with slow processing speed. In this paper, we use different data sources to test our algorithms and adopt false positive rate (FPR), false negative rate (FNR) and weighted mean relative difference (WMRD) as our evaluation metrics. Experimental results show that CBS algorithm not only saves memory space, but also can achieve real-time monitoring of the network. BS algorithm can highly accurately detect stealthy spreaders.