Hardware-based String Matching Algorithm In Network Content Analysis

The information revolution centered on Internet has changed people's lives and network is everywhere. However, beneath the Internet, content security has always been a problem. On one side, people depend on network more and more in their daily lives, and much more transactions in governments have to be done with network; on the other side, Internet is a double-edged sword, as hackers, virus and network attack are more and more popular. To keep clean of the network space and to protect the integrity of the "country" have become an important thing in the development of one country, and have become a great challenge of people. Network content analysis has attracted more and more attention to build the network enviroment with high-effiency and safety.This thesis focuses on the basic problem in network content analysis, and aims at the application of the hardware based string matching algorithm in network content analysis from the aspects of algorithm and system. There are several new ideas in this thesis:First, in the network content analysis, the payloads in the data message have to be decoded and checked besides the specific string matching. In the traditional string matching, the network messages are simply treated as orderless string, while its inside construct and the real meaning of the payloads are neglected. However, communications in network are based on the protocols, which are highly standardized data stream with clear meaning and value. So, a string matching and protocol decoding algorithm based on ABNF is proposed in this thesis. It can perform string matching and decode the protocol in a hardware manner, also can satisfy the needs of the network content analysis and improve the performance of the system.To retrieve the value of pattern string which matched with the input string, the traditional Bloom filter is extended to support value retrieve; meanwhile, a weighted extended Bloom filter is proposed in this thesis to eliminate the performance decrement in the above extended Bloom filter. Then the optimal configuration of the weighted extended Bloom filter(WEBF) is deduced. Also, to improve the performance of the matching, a WEBF engine ASIC chip is designed and the performance is given through simulation and experiment.To verify the function and performance of the string matching algorithm proposed in this thesis, we design a network content analysis platform based on embeded processor and WEBF engine. It is indicated that the string matching algorithm and the protocol decoder model is feasible with the advantage of high efficiency and low cost. In the meantime, GNU/Linux system on the platform is free and powerful and can implement complicated network transcation.From a wider aspect, network content analysis is a specific application of data flow management. Data flow management is a technique of manipulating a great amount of matching and endless flowing data.We always have a dream of designing a network Soc chip, which can support some basic network message operations such as packet classification, protocol paser and string matching in hardware manner and also contains several general processor cores. It can supply flexible and powerful ability to many network applications. We hope that it can become a basic systematic chip to provide technical support to the security and commercial development of our country. This thesis can be treated as an attempt to this orientation.