An Efficient TCAM-Based Implementation of Multipattern Matching Using Covered State Encoding

摘要

This paper proposes a state encoding scheme called a covered state encoding for the efficient TCAM-based implementation of the Aho-Corasick multipattern matching algorithm, which is widely used in network intrusion detection systems. Since the information of failure transitions of the Aho-Corasick Nondeterministic Finite Automata (NFA) is implicitly captured in the covered state encoding and the failure transition entries can be completely eliminated, the Aho-Corasick NFA can be implemented on a TCAM with smaller number of entries than other schemes. We also propose constructing the modified Aho-Corasick NFA for multicharacter processing, which can be implemented on a TCAM using the covered state encoding. The implementation of modified Aho-Corasick NFA using the covered state encoding is also superior to other schemes in both TCAM memory requirement and lookup speed.