Design of Bloom Filter Array for Network Anomaly Detection
Jieyan Fan, Dapeng Oliver Wu, Kejie Lu, Antonio Nucci · 2006
Despite the rapid advance in networking tech- nologies, detection of network anomalies at high-speed switches/routers is still far from maturity. To push the frontier, two major technologies need to be addressed. The first one is efficient feature-extraction algorithms/hardware that can match a line rate in the order of Gb/s; the second one is fast and effective anomaly detection schemes. In this paper, we focus on design of efficient data structure and algorithms for feature extraction. Specifically, we propose a novel data structure that extracts so-called two-directional (2D) matching features, which are shown to be effective indicators of network anomalies. Our key idea is to use aB loom fi lter array to trade off as mall amount of accuracy in feature extraction, for much less space and time complexity, so that our data structure can catch up with a line rate in the order of Gb/s. Different from the existing work, our data structure has the following properties: 1) dynamic Bloom filter, 2) combination of a sliding window with the Bloom filter, and 3) using an insertion-removal pair to enhance the Bloom filter with a removal operation. Our analysis and simulation demonstrate that the proposed data structure has a better space/time trade-off than conventional algorithms. For example, for a fixed time complexity, the conventional algorithm (i.e., hash table (1)) requires a memory of 1.01G bits while our data structure requires a memory of only 62.9M bits, at the cost of losing 1% accuracy in feature extraction.