关键词: 节约内存, 模式匹配, 入侵检测, Aho-Corasick算法

Abstract: Because Network Intrusion Detection System（NIDS） needs to check for thousands of known attack patterns in every packet，pattern matching computations dominates in the overall cost of running a NIDS.With network speed and the number of detection rules constantly increasing，pattern matching as a key component，is becoming the bottleneck in NIDS as well as.This paper presents a memory efficient multi-pattern matching algorithm based on non-deterministic finite automaton，called MEAC.By compacting state table，MEAC algorithm stores state and state transition in a single vector，drastically reduces the amount of memory usage，gains more caching and prefetching opportunity，and thus benefits from cache performance.Experimental results show that the average memory usage of MEAC algorithm decreases by 92.3%~98.4% compared to other Aho-Corasick algorithms，and maintains the perfect performance of Aho-Corasick algorithm at the same time.

Key words: memory efficient, pattern matching, intrusion detection, Aho-Corasick algorithm