International Journal of Information Technology and Computer Science (IJITCS)
IJITCS Vol. 6, No. 1, 8 Dec. 2013
Cover page and Table of Contents: PDF (size: 478KB)
FSM Circuits Design for Approximate String Matching in Hardware Based Network Intrusion Detection Systems
Full Text (PDF, 478KB), PP.68-75
Views: 0 Downloads: 0
Author(s)
Index Terms
FSM, Content Matching, Generalized Levensthein Distance, NFA, DFA
Abstract
In this paper we present a logical circuits design for approximate content matching implemented as finite state machines (FSM). As network speed increases the software based network intrusion detection and prevention systems (NIDPS) are lagging behind requirements in throughput of so called deep package inspection - the most exhaustive process of finding a pattern in package payloads. Therefore, there is a demand for hardware implementation. Approximate content matching is a special case of content finding and variations detection used by "evasion" techniques. In this research we will enhance the k-differentiate problem with "ability" to detect a generalized Levensthein edit distance i.e. transposition of two neighboring characters. The proposed designs are based on automata theory using the concept of state reduction and complexity minimization. The main objective is to present the feasibility of the hardware design and the trade-off between the simple next state and output functions of NFA and reduced number of required memory elements (flip-flops) of DFA.
Cite This Paper
Dejan Georgiev, Aristotel Tentov, "FSM Circuits Design for Approximate String Matching in Hardware Based Network Intrusion Detection Systems", International Journal of Information Technology and Computer Science(IJITCS), vol.6, no.1, pp.68-75, 2014. DOI:10.5815/ijitcs.2014.01.08
Reference
[1]SNORT (www.snort.org)
[2]Christopher R. Clark "Design of efficient FPGA circuits for matching complex patterns in network intrusion detection systems" , in partial fulfillment of the requirement for degree Master of science in Electrical and computer engineering , Georgia Institute of Technology, December 2003, pp 34-36
[3]Jan Holub - "Simulation of NFA in approximate content and sequence matching", Department of computer and science and engineering, Faculty of electrical engineering, Czech technical university Karlovo, Prague
[4]Jan Holub "Reduced nondeterministic finite automata for approximate content matching" , Department of computer and science and engineering, Faculty of electrical engineering, Czech technical university Karlovo, Prague
[5]Ioannis Sourdis "Efficient and high-speed FPGA-based string matching for packet inspection" , Technical University of Crete, Chania, July 2004
[6]Young H. Cho and Willian H. Mangione-Smith "Deep network packet filter design for reconfugurable devices" University of California, Los Angeles
[7]Reetinder Sidhu and Viktor K.Prasanna "Fast regular expression matching using FPGAs" , Department of EE-Systems, University of Southern California , Los Angeles CA 90089
[8]Christopher R. Clark, David E. Schimmel "Efficient reconfigurable logic circuit for matching complex network intrusion detection patterns" , In proceeding of international conference of field-programmable logic and applications (FPL), Lisbon, Portugal, September 2003
[9]Ricardo Baeza-Yates " Algorithms for string searching: a survey" ,Department of computer science ,University of Waterloo, Ontario, Canada
[10]Enoch O. Hwang - "Digital logic and microprocessor design with VHDL" , La Sierra University, Riverside
[11]Borivoj Melichar "Approximate string matching by finite automata" , Department of computer science and engineering, Czech Technical University, Prague.