The reassembly of IP fragments and TCP streams are very important in Intrusion Detection Systems (IDS). However, existing reassembly algorithms that cache fragments entirely are memory-greedy. It is vulnerable to memory exhaustion denial of service (DOS) attacks. In this paper, we present a space-economical algorithm based on enhanced DAWG (Directed Acyclic Word Graph) automaton, which can detect the occurrences of a set of patterns in an out-of-order data stream. In contrast to existing algorithms, our algorithm scans each fragment by a multi-pattern matching automaton and just caches the returned solid-size index data structures, thus the memory requirement involved in caching fragments is largely reduced. Experiments and analysis show that our new algorithm greatly reduces the memory usage of reassembly in IDS and outperforms existing algorithms.
展开▼