Reduced Merge_FSM Pattern Matching Algorithm for Network Intrusion Detection
Int. J. on Recent Trends in Engineering and Technology,, 10 (2):
6 (January 2014)Abstract
Pattern matching is a significant issue in intrusion detection systems (IDS), as it
is required to identify and restrict certain virus patterns by matching them with the
patterns present in the database. The performance of an Intrusion Detection System is
dependent on two metrics that is throughput and the total number of patterns that can fit
on a device. Many hardware approaches are proposed to accelerate pattern matching.
Among hardware approaches, memory based architecture has attracted a lot of attention
because of its easy reconfiguration and scalability. In memory architecture approach. First,
the virus string patterns are compiled to a finite-state machine (FSM) whose output is
asserted when any substring of input strings matches the string patterns. The speed of
comparisons and memory required to store virus string patterns is evaluated through the
number of state transitions made. In this paper, a new pattern-matching algorithm
‘Reduced Merge_FSM’ is proposed which significantly reduce the memory requirement
and provides faster matching, by reducing the state transitions, than that of existing Finite
State Machine (FSM) based approaches. This reduction in states results in optimization of
memory and also the comparison time. To prove the efficiency of the proposed algorithm,
it is compared through experimentation with the existing AC-Algorithm and Merge_FSM.