• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>2011 Seventh ACM/IEEE Symposium on Architectures for Networking and Communications Systems >A Multi-dimensional Progressive Perfect Hashing for High-Speed String Matching
【24h】

A Multi-dimensional Progressive Perfect Hashing for High-Speed String Matching

机译：高速字符串匹配的多维渐进完美散列

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Aho-Corasick (AC) automaton is widely used for multi-string matching in today's Network Intrusion Detection System (NIDS). With fast-growing rule sets, implementing AC automaton with a small memory without sacrificing its performance has remained challenging in NIDS design. In this paper, we propose a multi-dimensional progressive perfect hashing algorithm named P2-Hashing, which allows transitions of an AC automaton to be placed in a compact hash table without any collision. P2-Hashing is based on the observation that a hash key of each transition consists of two dimensions, namely a source state ID and an input character. When placing a transition in a hash table and causing a collision, we can change the value of a dimension of the hash key to rehash the transition to a new location of the hash table. For a given AC automaton, P2-Hashing first divides all the transitions into many small sets based on the two-dimensional values of the hash keys, and then places the sets of transitions progressively into the hash table until all are placed. Hash collisions that occurred during the insertion of a transition will only affect the transitions in the same set. The proposed P2-Hashing has many unique properties, including fast hash index generation and zero memory overhead, which are very suitable for the AC automaton operation. The feasibility and performance of P2-Hashing are investigated through simulations on the full Snort (6.4k rules) and Clam AV (54k rules) rule sets, each of which is first converted to a single AC automaton. Simulation results show that P2-Hashing can successfully construct the perfect hash table even when the load factor of the hash table is as high as 0.91.
机译：Aho-Corasick（AC）自动机广泛用于当今的网络入侵检测系统（NIDS）中的多字符串匹配。随着规则集的快速增长，在不牺牲其性能的情况下实现具有较小内存的交流自动机在NIDS设计中仍然具有挑战性。在本文中，我们提出了一种称为P2-Hashing的多维渐进式完美哈希算法，该算法允许将AC自动机的过渡放置在紧凑的哈希表中而不会发生任何冲突。 P2-哈希基于以下观察结果：每个过渡的哈希键由两个维度组成，即源状态ID和输入字符。当在哈希表中放置过渡并导致冲突时，我们可以更改哈希键的维度值以将过渡重新哈希到哈希表的新位置。对于给定的AC自动机，P2-Hashing首先根据哈希键的二维值将所有转换分成许多小集合，然后将转换集逐步放入哈希表中，直到所有转换都被放置为止。插入过渡期间发生的哈希冲突只会影响同一集合中的过渡。提出的P2-Hashing具有许多独特的属性，包括快速的哈希索引生成和零内存开销，非常适合AC自动机操作。通过对完整的Snort（6.4k规则）和Clam AV（54k规则）规则集进行仿真研究，研究了P2-哈希的可行性和性能，其中每个规则集都首先转换为单个AC自动机。仿真结果表明，即使哈希表的负载因子高达0.91，P2-Hashing仍可以成功构建完美的哈希表。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号