BLAST: B‐LAyered bad‐character SHIFT tables for high‐speed pattern matching. Issue 3 (1st September 2013)

• Record Type: Journal Article
• Authors: Choi, Yoon‐Ho; Seo, Seung‐Woo
• Is Part Of: IET information security. Volume 7:Issue 3(2013)
• Page Start: 195
• Page End: 202
• Publication Date: 2013-09-01
• Subjects: search problems -- string matching -- text analysis -- computer network security; B‐layered bad‐character SHIFT tables -- high‐speed pattern matching -- multipattern matching algorithm -- space‐time tradeoff -- shift values -- BLAST algorithm -- text scanning -- byte checking -- single‐byte search unit -- single bad‐character SHIFT table -- multibyte search unit -- MBSU -- pattern search time -- attack patterns -- attack traffic conditions -- Wu‐Manber algorithm; Computer security -- Periodicals; Cryptography -- Periodicals; Computer networks -- Security measures -- Periodicals; Database security -- Periodicals; 005.8
• DOI: 10.1049/iet-ifs.2011.0305
• Languages: English
• ISSNs: 1751-8709

Abstract

Abstract : In this study, the authors propose a new multi‐pattern matching algorithm, called BLAST (B‐LAyered bad‐character Shift Tables with a single‐byte search unit), which considers space‐time tradeoff in the context of shift values during the search. Here, the term 'bad character' is a character that causes a mismatch. While checking multiple bytes in scanning the text at a time, the BLAST algorithm overcomes the reduction of the average shift value in a typical search, which is caused by the dependency on the multi‐byte search unit (MBSU) and the large frequency of the last character of the given patterns. From the theoretical analysis, the authors validate the correctness of the BLAST algorithm. Also, from the experimental results across different setups, the authors show that the BLAST algorithm provides the faster search time than the other algorithms. For example, the authors obtain an enhancement by as much as 212.41% on average for various numbers of attack patterns and attack traffic conditions compared with that of the modified Wu‐Manber algorithm. In addition, it is shown that the BLAST algorithm drastically reduces the amount of memory required for constructing the shift table based on a MBSU from 64 KB to 1 KB.