Improved space protocol identification algorithm

Abstract

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 col 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 pattern 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 iciency 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.

Keywords

• space protocol
• protocol identification
• BM algorithm
• bit distance
• decimal jumping
• regular expression
• hierarchy association