String matching architectures for network security on reconfigurable computers

Network-connected devices often have vulnerabilities susceptible to exploitation. In order to protect individual systems and the entire network, network operators must ensure that attacks do not traverse their network links. One method for understanding the attacks on a network is an Intrusion Detection System (IDS). Intrusion Detection Systems use sophisticated rules utilizing string matching to detect potential malicious packets. Due to the high string matching rates required, this filtering requires significant computational resources. Fortunately, the computational requirements can be met by Field Programmable Gate Array (FPGA) devices. This thesis describes two efficient hardware string matching architectures developed to provide high levels of time and area performance.;The Knuth-Morris-Pratt (KMP) algorithm is an efficient string matching technique that requires a minimum of comparisons through the use of a pre-computed transition table. This thesis presents a modification of the basic algorithm that allows its use in an efficient hardware architecture, allowing the system to accept at least one character in each cycle. The memory-based units allow runtime pattern reconfiguration. A major contribution is a proof of the worst-case buffer size requirement such that throughput is maintained with no chance of a false negative. The buffered KMP algorithm reduces the overall work done, and thereby the area required is lower as well.;In another approach, a set of tools was developed for automatic synthesis of highly efficient intrusion detection systems. This approach uses a high-level, graph-based partitioning methodology to produce "hardwired" architectures compiled to the FPGA device. The automated design techniques and architecture allows faster clock rates and extensive reuse of hardware components for dramatic increases in area-time performance. Through design-time compilation, the methodology yields designs that take advantage of pattern redundancy. To extend the capabilities of the hardwired architectures, extensions were developed that provide support for rules requiring string literal extensions including wild-card separated patterns with bounding restrictions.;By combining the two techniques into a hybrid system, improvements in terms of area, memory efficiency, and frequency performance are achieved, while providing on-the-fly reprogramming.