Abstract
The main purpose of a network intrusion detection system (NIDS) is to inspect the packet header and payload against thousands of predefined malicious or suspicious patterns. These patterns describe behaviors such as denial of service attacks, port scans, or malware. To efficiently represent suspicious patterns, regular expressions are commonly adopted such as Snort[22], Bro[24], and ClamAV[25] because they have better expressive power and flexibility than explicit string patterns. Due to the increasing complexity of network traffic and the growing number of attacks, traditional software-based NIDS will become inadequate for networking needs due to its slowness. To speed up pattern matching, many researchers have proposed hardware approaches which can be classified into two main categories, the logic and the memory architectures. The logic architectures are mostly implemented on Field-Programmable Gate Array (FPGA) because FPGA allows for updating new attack patterns. In addition, the logic architecture is easy to handle certain types of regular expressions containing meta-characters, such as ‘*’, ‘|’, and ‘+’, etc. However, due to the increasing number of attacks, it is important to develop a new methodology to minimize the circuit area of the large number of regular expressions. Although the minimization of logic equations has been studied intensively in the area of computer-aided design (CAD), the minimization of multiple regular expressions has been largely neglected. In the first part of this dissertation, we present a novel sharing architecture allowing our algorithm to extract and share common sub-regular expressions. On the other hand, the memory architecture is also widely adopted by NIDS because of the advantages of easy re-configurability and scalability. Due to the increasing number of attacks, the required memory increases tremendously. Because the performance, cost, and power consumption of the memory architecture are directly related to the memory size, reducing the memory size has become imperative. In the second part of this dissertation, we propose a memory-efficient pattern-matching algorithm which can significantly reduce the memory requirement for the memory architecture. However, the memory architecture suffers the problem of memory explosion caused by certain types of regular expressions. It is well known that the number of states and transitions of a DFA can be exponential to the size of its corresponding regular expression. Implementing such regular expression pattern leads to extremely large memory requirements for storing the corresponding state transition table. In the third part of this dissertation, we propose a novel memory architecture which inserts marginal logic elements to improve the ability of traditional memory architecture to deal with complex regular expressions.