{'fraction_non_alphanumeric': 0.036813518406759206, 'fraction_numerical': 0.010259505129752565, 'mean_word_length': 4.7972027972027975, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An efficient data structure for network anomaly detection

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/second; 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 the 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 (BFA) 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/second. Different from the existing work, our data structure has the following properties: (1) it dynamic Bloom filter, (2) combination of a it sliding window with Bloom filter, and (3) using an insertion–removal pair to enhance 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—8]) requires a memory of 1.01 Gbits while our data structure requires a memory of only 62.9 Mbits, at the cost of losing 1% accuracy in feature extraction. Copyright © 2008 John Wiley & Sons, Ltd.