Kangaroo: Accelerating String Matching by Running Multiple Collaborative Finite State Machines
Kangaroo: Accelerating String Matching by Running Multiple Collaborative Finite State Machines
复制标题
Kangaroo：通过运行多个协作有限状态机加速字符串匹配
DOI：
10.1109/jsac.2014.2358841
复制
发表时间：
2014
影响因子：
16.4
通讯作者：
Wang Xiaojun
中科院分区：
文献类型：
--
作者：
Wang Xiaofei;Liu Bin;Jiang Junchen;Xu Yang;Wang Yi;Wang Xiaojun
字符串匹配是网络入侵检测系统和防病毒扫描器等网络安全应用中的关键技术，在这些应用中，每个数据包的有效载荷都要与数千种模式进行真实的实时检测。随着互联网链路的传输速率越来越高，要求匹配引擎的速度也越来越快。现有的确定性有限自动机（DFA）为基础的方法实现高吞吐量的代价是非常昂贵的内存成本，因此，他们是不适合的情况下，只有有限的片上存储器资源是可用的。为了实现快速匹配的速度，同时控制内存开销，在本文中，我们提出了袋鼠，一个紧凑的字符串匹配方案，扫描多个字符，每次并行运行多个小型有限状态机。具体来说，Kangaroo通过并行访问k个不同的存储器，在一个周期内处理k个连续的字符，其中k是一个预定义的因子，可以根据应用程序的要求进行调整。Kangaroo的记忆力很强。Snort和ClamAV规则集上的实验评估表明，与最先进的基于DFA的方法相比，通过单个Kangaroo匹配引擎可以实际实现速度的十倍提高，并且具有降低的内存成本。
String matching is a key technique for network security applications such as network intrusion detection systems and antivirus scanners, where the payload of every packet is inspected against thousands of patterns in real time. As the transmission rate of Internet links is getting higher and higher, the speed of matching engines is required to be faster and faster. Existing deterministic finite automaton (DFA)-based approaches achieve high throughput at the expense of extremely expensive memory cost; therefore, they are not suitable for the scenarios where only limited on-chip memory resources are available. To achieve fast matching speed while controlling memory expense, in this paper, we propose Kangaroo, a compact string matching scheme that scans multiple characters each time by running multiple small-sized finite state machines in parallel. Specifically, Kangaroo processes k consecutive characters mostly in one cycle by accessing k different memories in parallel, where k is a predefined factor that can be tuned based on the requirement of applications. Kangaroo is memory efficient. Experimental evaluations on Snort and ClamAV rule sets show that a tenfold increase in speed can be practically achieved by a single Kangaroo matching engine with a reduced memory cost comparing with the state-of-the-art DFA-based approaches.