Design of Bloom filter array for network anomaly detection

Research output: Chapters, Conference Papers, Creative and Literary WorksRGC 32 - Refereed conference paper (with host publication)peer-review

5 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Title of host publicationIEEE GLOBECOM 2006 - 2006 Global Telecommunications Conference
PublisherInstitute of Electrical and Electronics Engineers, Inc.
ISBN (electronic)1-4244-0357-X
ISBN (print)1-4244-0356-1
Publication statusPublished - Nov 2006
Externally publishedYes

Publication series

NameGLOBECOM - IEEE Global Telecommunications Conference
ISSN (Print)1930-529X

Conference

Title2006 Global Telecommunications Conference (IEEE GLOBECOM 2006)
PlaceUnited States
CitySan Francisco
Period27 November - 1 December 2006

Abstract

Despite the rapid advance in networking technologies, 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 a Bloom filter array to trade off a small 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. © 2006 IEEE.

Citation Format(s)

Design of Bloom filter array for network anomaly detection. / Fan, Jieyan; Wu, Dapeng; Lu, Kejie et al.
IEEE GLOBECOM 2006 - 2006 Global Telecommunications Conference. Institute of Electrical and Electronics Engineers, Inc., 2006. (GLOBECOM - IEEE Global Telecommunications Conference).

Research output: Chapters, Conference Papers, Creative and Literary WorksRGC 32 - Refereed conference paper (with host publication)peer-review