The Research Of Parallel Multi-pattern Matching Algorithms And Hardware Implementation

As the national economy is growing rapidly, high-tech industry that is represented by the internetindustry has attained great development. Various advanced network devices for transmission,routing and terminal utilization have been made use of, and novel application that is based on theinternet keeps popping up. Data transmitted by the internet is booming explosively and the contentis just as diverse and complicated. Therefore it is truly crucial to maintain security and stabilizationof data transmission on the internet, to prevent and hold back potential hazardous behaviors and tofacilitate the healthy growth of internet industry, by discovering malicious information from hugeamount of data. In order to meet this requirement, facilities for network security, such as intrusiondetection\protection systems, come into being. An intrusion detection system is responsible formonitoring data flow on the internet, and to have deep detection for data packet on the internetonline is its primary function, which may figure out harmful information and hazardous behaviors.As a result, valid and efficient strategies for scouting data content are demanded, which are theso-called pattern matching algorithms.In this dissertation, a novel parallel multi-pattern matching algorithm is proposed. Thisalgorithm originates from the existing classical uni-character multi-pattern matching algorithm, theAC algorithm, and is its multi-character improved algorithm. It is available to process multiplecharacters in parallel, and more efficient in saving executing time and space expense remarkably.The new algorithm inherits concision, high-efficiency, systematicness and easy-to-use from the ACalgorithm, and tends to be more flexible and configurable to meet requirement from several types ofapplication. In this part, explicit introduction on principal characteristics of the new algorithm andrelated methods is presented, it includes computational model that actualizes the function of thealgorithm, algorithm finite state machine that generalizes essence of the algorithm idea, how to takeadvantage of and construct the algorithm finite state machine and proof of the algorithm’s validity,dependability and high-efficiency.A practical solution to implement the new algorithm, which takes advantage of a fieldprogrammable gate array chip as its core component, a new pattern matching engine system, isproposed in the dissertation. Validity and feasibility is verified by the engine system, andpreliminary evidence to assess practical data processing performance of the new algorithm isprovided by it as well. In this part, deep research and study on top architecture and module partition,workflow, functions, work principals, constructing basis and methods, as well as verification andtest by simulation, et al, are given out. At last, a successful sample of the engine system isintroduced, which is exemplified to help clarify and verify related design methods and to demonstrate impact from distinct performance parameters on the whole system. Theoreticalevaluation on performance of the sample is also compared by data from experiments, which provesvalidity of the design.