Key Techniques Of Data Filtering On High Speed Network

With the fast development of Internet, we get not only convenience, but also some bad influence. Some illegal activities on Internet including information pollution, attack and crime bring damages to Internet and threat the interest of legal users. Governments and organizations put much attention on techniques and tools for Internet content supervision, so that the abnormal data could be distinguished from normal data on Internet and criminal activities could be controlled or punished.Data filtering on Internet is an important method to control information transmitting and to maintain information security, by which harmful information could be monitored and filtered. With the development of broadband technique, the increasing network bandwidth has exceeded the increasing speed of CPU, which brings greatly challenges to the intrusion detection systems of backbone network. Since the speed of software process could not keep up with the demand of Internet speed, accelerating algorithms based on hardware are necessary for data filtering on Internet.In this thesis, we focused on several important data filtering techniques such as string matching, multi-packet matching and rule matching, and proposed some new algorithms in each field. Based on the proposed string matching algorithms, a hardware based Internet data filter was designed and implemented. Then we improved this data filter in functions and processing speed and designed an Internet data filter card. Simulation proved the usability and feasibility of our works.Primary innovative contributions of this thesis can be summarized as follows.1. We proposed three new string matching algorithms which could be fit for strings of large numbers. (1)Memory Efficient Parallel Longest Prefix Matcher——MEPLPM was proposed, which was based on PLPM and could contain more strings. (2) Decoupled Query and Analysis Parallel Longest Prefix Matcher——DQAPLPM was proposed, with which the scope of string occurrence rate would be extended compared with traditional BF based algorithms. (3)Dynamic Configurable Bloom Filters——DCBF was proposed, which could be applied to different string sets and increase the flexibility of Bloom Filter.2. We proposed a multi-packet matching algorithm based on DCBF and PBF. PBF is a multi-packet string matching algorithm which can work without defragment. Our new algorithm decreased the on-chip memory requirement of PBF with a little more off-chip memory cost. To fit for multi-flows on network, a fast flow state manage algorithm using BF and little CAM(Content Addressable Memory) was proposed to support this new algorithm.3. We proposed a fast rule matching algorithm based on PVMatcher. A 2-length rule was transformed as a pair of bit-vector operation, which can be accelerated by hardware. With PVMatcher, strings without matching any rules could be recognized quickly so the processing time could be reduced. Analysis shows that the memory requirement of PVMatcher is far less than that of traditional algorithms. The process speed of our new algorithm is obviously faster than traditional algorithms when the numbers of string is not large(eg: <20), which is consistent with the fact of Internet security applications.4. Based on the above researches, we designed an Internet data filter card. This card could filter data without defragment and work at very high speed. Tens thousand of strings and rules could be programmed into this card and most data in high speed network could be filtered. Elaborate design and simulation have been performed, proved the usability and feasibility of this card.