| Deep Packet Inspection (DPI) is a critical component in Network Intrusion Detection System (NIDS). It affects the performance of NIDS. DPI not only inspects the protocol headers of packets but also checks the payload. An analysis shows that in Snort, an open source software-based NIDS, the signature matching alone consumes 30% to 80% of the CPU time. While the network bandwidth and the size of the signature set keep growing, to perform real time deep packet inspection is an important issue.Bloom Filter is an efficient data structure using a bit-array to present data set and enabling fast membership query. The space efficiency is achieved at the cost of a small probability of false positive, that is, an element may be announced as in the set while it is not. Though a content analyzer could be used to decide the final match, there are two drawbacks in this scheme. Firstly, the extra analysis in the analyzer might become the performance bottleneck. Secondly, the size of signature set might have a negative effect the performance of the analyzer, and analyzer is inefficient in memory usage.This thesis gives a deep research on Bloom Filters and concludes the main research in Bloom Filters and some important variations. The analysis of current research shows that there may well be further improvements to be found. Considering the space efficiency, this thesis proposes a memory-efficient Bloom filter design which is called VHBF (Value Hash Bloom Filter). Using secondary hash filtering method, VHBF can decrease the false positive rate involved in membership query. What is more, VHBF is a memory-efficient structure. Experiments are performed to test this new structure. Simulation results support the theoretic analysis; VHBF has a better performance in memory usage and a lower false positive rate than extended Bloom Filter. And, a parallel deep packet inspection engine using Value Hash Bloom Filter is implemented, analysis shows that it can perform well on high speed network. |
PDF Full Text Request