Improved BM Pattern Matching Algorithm for Intrusion Detection

Author

Chen, Qingzhang ; Niu, Yibo ; Wang, Zhehu ; Du, Feng

Author_Institution

Coll. of Comput., Zhejiang Univ. of Technol., Hangzhou, China

Volume

1

fYear

2010

fDate

28-31 May 2010

Firstpage

440

Lastpage

444

Abstract

In the paper, two improved algorithms: BMLT and BMLS are proposed, in which the time complexity and space complexity of BM is improved. The algorithm of BMLT with a new pre-calculation function can increase in the movement of pattern significantly. The algorithm of BMLS can reduce the space complexity and maintain the time complexity by reducing a pretreatment function and recording the number of times that a bad char found in the pattern. Experiments indicate that the time complexity is reduced by 60% and the space complexity is reduced by 26% at most. Therefore, the improved algorithms can provide significant improvement in pattern matching performance when using in an IDS

Keywords

Computer networks; Computer security; Costs; Data security; Educational institutions; Information security; Intrusion detection; Paper technology; Pattern matching; Space technology; BM-algorithm; algorithm improvement; intrusion detection; network security; pattern matching;

fLanguage

English

Publisher

ieee

Conference_Titel

Computational Science and Optimization (CSO), 2010 Third International Joint Conference on

Conference_Location

Huangshan, Anhui, China

Print_ISBN

978-1-4244-6812-6

Electronic_ISBN

978-1-4244-6813-3

Type

conf

DOI

10.1109/CSO.2010.177

Filename

5533070