Implementation of Aho-Corasick String Matching Algorithm on FPGA

Abstract

A review of the existing pattern matching algorithms shows that the software-based solutions pertaining to pattern matching do not encounter today’s throughput network systems. Pattern matching is used to examine Ethernet packet contents against thousands of predefined malicious or suspicious patterns. To accelerate the throughput of pattern matching architectures, hardwarebased solutions are getting more popularity. In this thesis, pattern matching architecture of open source network intrusion and preventions system (Snort) is proposed and implementation on FPGA using Aho-Corasick algorithm. According to Aho-Corasick algorithm, while matching input string in one pass there are three possible transition states i.e. Goto, Failure and Output. The Aho–Corasick algorithm used for pattern matching of snort IP, HTTP and TCP packet keywords considering a standard Ethernet packet size of 1500Bytes. The achieved results are evaluated on Xilinx (ISE) design suit tool which indicates that throughput and number of rule sets in the projected mechanism is higher as compared to other approaches. Many previous works have been proposed in this domain, however, solutions for limited rules have been discussed. Moreover, rule set level parallelism study while considering trade-off among resource utilization, operational frequency and resulting throughput has not been discussed. In this thesis we have presented the results of parallel implementation of a rule sets while dividing rule set into small sub-sets. A comparison of FPGA resources, operation frequency and throughput is also presented to evaluate parallelism efficiency of proposed architecture. It has been shown that throughput increases upto 27% by dividing rulesets into small subsets.