改进的空间协议识别算法  

Improved space protocol identification algorithm

作　　者：郑天明[1,2] 王韬[1] 郭世泽[3] 李华[1] 赵新杰[1] 

机构地区：[1]军械工程学院计算机工程系,河北石家庄050003 [2]中国人民解放军第六九零九工厂,江苏苏州215300 [3]北方电子设备研究所,北京100083

出　　处：《通信学报》2012年第5期183-190,共8页Journal on Communications

摘　　要：提出了一种适合空间协议识别的改进BM算法。首先给出了一种基于比特距离的空间数据预处理算法,增大字符集数量,并通过引入小数跳进机制,提高BM算法协议分组头匹配效率;然后应用正则表达式进行协议识别,利用层次关系法提高多层空间协议识别效率;最后对提出的算法进行了复杂度分析和实验验证。结果表明:对于识别模式串长度为m的单层协议,算法时间复杂度可降低到BM算法的(1+m/4)/m,对多层协议识别效率可提高2.5倍;同时,与BM算法相比,提出的算法可有效解决模式串长度不足与存在大量不确定数据的问题,在数据量较大情况下具有更高的识别效率,且所形成的分组可有效抑制正则表达式DFA匹配引擎状态膨胀。An improved boyer-moore （BM） algorithm for space protocol identification was proposed. First, a space data preprocessing technique based on bit distance was used to increase the size of data set. A decimal jumping technique was introduced to enhance the matching efficiency for the protocol head part of the BM algorithm. Then, the regular expression method was applied to proceed the protocol identification and the hierarchy associated analysis technique was proposed to improve the efficiency of multi-level space protocol identification. Finally, the complexity of the proposed algorithm was analyzed and verified with concrete experiments. The results show that with the proposed algorithm, as to pat- tern string length m, the time complexity of the single layer protocol identification can be reduced to （1＋m/4）/m of the BM algorithm. The efficiency of the protocol identification for multi-level layers can be improved about 2.5 times. Meanwhile, comparing with BM algorithm, the proposed algorithm can solve the problem of pattern string shortage and large wildcards in the space data. The identification efficiency in case of huge data packages can be improved and the new formed data block can restrain the state expansion for the DFA matching engine in regular expression.

关 键 词：空间协议 协议识别 BM算法 比特距离 小数跳进 正则表达式 层次关联 

分 类 号：TP393.08[自动化与计算机技术—计算机应用技术]