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

摘要： 模式匹配既是网络入侵检测系统（NIDS）的关键，也是NIDS中消耗资源最多的部分。随着网络速度和入侵检测规则的持续增长，模式匹配正在成为NIDS的性能瓶颈。提出了一种基于非确定有限自动机结构的Aho-Corasick算法，通过压缩状态表，把状态和状态变迁存储在一个单一向量中，显著降低了内存需求，获得了良好的cache性能。测试表明，与其他Aho-Corasick 算法相比，MEAC的内存消耗平均减少了92.3%~98.4%，同时保持了Aho-Corasick算法的良好性能。

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