Space-time tradeoff in the Aho-Corasick string matching algorithm

Yisi Xu; Derek Pao

doi:10.1109/CNS.2015.7346899

Space-time tradeoff in the Aho-Corasick string matching algorithm

Yisi Xu
, Derek Pao

Department of Electrical Engineering

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

1 Citation (Scopus)

Abstract

The Aho-Corasick (AC) string matching algorithm is widely used in intrusion detection systems and anti-virus systems. The basic version consisting of the GOTO and failure functions is very memory efficient, but its processing speed is slow. On the other hand, the version with fully expanded transition rule table is much faster but it requires huge amount of memory space. In this article we study the space-time tradeoff in the AC algorithm. A transition rule table compression scheme based on transition edge elimination and perfect hashing is developed. The proposed method can reduce the size of the fully expanded transition rule table by a factor of 23 to 25, and the processing speed is 5 to 7.7 times the speed of the basic version.

Original language	English
Title of host publication	2015 IEEE Conference on Communications and NetworkSecurity, CNS 2015
Publisher	IEEE
Pages	713-714
ISBN (Print)	9781467378765
DOIs	https://doi.org/10.1109/CNS.2015.7346899
Publication status	Published - 3 Dec 2015
Event	3rd IEEE International Conference on Communications and Network Security, CNS 2015 - Florence, Italy Duration: 28 Sept 2015 → 30 Sept 2015

Conference

Conference	3rd IEEE International Conference on Communications and Network Security, CNS 2015
Place	Italy
City	Florence
Period	28/09/15 → 30/09/15

Research Keywords

deterministic finite automaton
string matching
transition rule table compression

Access Output

10.1109/CNS.2015.7346899

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@inproceedings{e157bb60b9d3403bb8b725e386956a27,

title = "Space-time tradeoff in the Aho-Corasick string matching algorithm",

abstract = "The Aho-Corasick (AC) string matching algorithm is widely used in intrusion detection systems and anti-virus systems. The basic version consisting of the GOTO and failure functions is very memory efficient, but its processing speed is slow. On the other hand, the version with fully expanded transition rule table is much faster but it requires huge amount of memory space. In this article we study the space-time tradeoff in the AC algorithm. A transition rule table compression scheme based on transition edge elimination and perfect hashing is developed. The proposed method can reduce the size of the fully expanded transition rule table by a factor of 23 to 25, and the processing speed is 5 to 7.7 times the speed of the basic version.",

keywords = "deterministic finite automaton, string matching, transition rule table compression",

author = "Yisi Xu and Derek Pao",

year = "2015",

month = dec,

day = "3",

doi = "10.1109/CNS.2015.7346899",

language = "English",

isbn = "9781467378765",

pages = "713--714",

booktitle = "2015 IEEE Conference on Communications and NetworkSecurity, CNS 2015",

publisher = "IEEE",

address = "United States",

note = "3rd IEEE International Conference on Communications and Network Security, CNS 2015 ; Conference date: 28-09-2015 Through 30-09-2015",

}

TY - GEN

T1 - Space-time tradeoff in the Aho-Corasick string matching algorithm

AU - Xu, Yisi

AU - Pao, Derek

PY - 2015/12/3

Y1 - 2015/12/3

N2 - The Aho-Corasick (AC) string matching algorithm is widely used in intrusion detection systems and anti-virus systems. The basic version consisting of the GOTO and failure functions is very memory efficient, but its processing speed is slow. On the other hand, the version with fully expanded transition rule table is much faster but it requires huge amount of memory space. In this article we study the space-time tradeoff in the AC algorithm. A transition rule table compression scheme based on transition edge elimination and perfect hashing is developed. The proposed method can reduce the size of the fully expanded transition rule table by a factor of 23 to 25, and the processing speed is 5 to 7.7 times the speed of the basic version.

AB - The Aho-Corasick (AC) string matching algorithm is widely used in intrusion detection systems and anti-virus systems. The basic version consisting of the GOTO and failure functions is very memory efficient, but its processing speed is slow. On the other hand, the version with fully expanded transition rule table is much faster but it requires huge amount of memory space. In this article we study the space-time tradeoff in the AC algorithm. A transition rule table compression scheme based on transition edge elimination and perfect hashing is developed. The proposed method can reduce the size of the fully expanded transition rule table by a factor of 23 to 25, and the processing speed is 5 to 7.7 times the speed of the basic version.

KW - deterministic finite automaton

KW - string matching

KW - transition rule table compression

UR - https://www.scopus.com/pages/publications/84966318449

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84966318449&origin=recordpage

U2 - 10.1109/CNS.2015.7346899

DO - 10.1109/CNS.2015.7346899

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9781467378765

SP - 713

EP - 714

BT - 2015 IEEE Conference on Communications and NetworkSecurity, CNS 2015

PB - IEEE

T2 - 3rd IEEE International Conference on Communications and Network Security, CNS 2015

Y2 - 28 September 2015 through 30 September 2015

ER -

Space-time tradeoff in the Aho-Corasick string matching algorithm

Abstract

Conference

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this