计算机应用 ›› 2010, Vol. 30 ›› Issue (8): 2157-2160.

• 信息安全 • 上一篇    下一篇

基于稀疏矩阵存储的状态表压缩算法

姚远1,刘鹏2,王辉1,笱程成1   

  1. 1.
    2. 解放军信息工程大学信息工程学院
  • 收稿日期:2010-03-01 修回日期:2010-04-04 发布日期:2010-07-30 出版日期:2010-08-01
  • 通讯作者: 刘鹏
  • 基金资助:
    国家863计划基金资助项目;国家863计划基金资助项目

Compression algorithm of state transition table based on sparse matrix

  • Received:2010-03-01 Revised:2010-04-04 Online:2010-07-30 Published:2010-08-01

摘要: 正则表达式匹配对于网络安全应用至关重要。将稀疏矩阵和索引表引入确定的有限自动机的状态转换表,提出了一种稀疏矩阵索引的状态压缩表算法,并给出了稀疏矩阵和索引表的构造方法。而后同字母压缩表算法结合,给出了该算法的优化策略。最后在实际规则集上进行评估,实验结果证明了算法的压缩效果,并进一步得出了算法的适用范围。

关键词: 确定的有限自动机, 深度包检测, 正则表达式, 稀疏矩阵, 压缩算法

Abstract: Regular expression matching is essential for network security applications. In this paper, a smi-SCT (State transition Compressed Table of sparse matrix index) algorithm was proposed.Firstly a sparse matrix and index table were introduced into Deterministic Finite Automaton (DFA) with a general create method of them. Then combined with the smi-SCT with alphabet compression table algorithm, an optimization strategy of the algorithm was given. At last proved the compression effect of smi-SCT and gave the applicable scope of smi-SCT according to the experimental results on compression effects.

Key words: Deterministic Finite Automaton (DFA), Deep Packet Inspection (DPI), regular expression, sparse matrix, compression algorithm