TY - GEN
T1 - Accelerating regular expression matching using hierarchical parallel machines on GPU
AU - Lin, Cheng Hung
AU - Liu, Chen Hsiung
AU - Chang, Shih Chieh
PY - 2011
Y1 - 2011
N2 - Due to the conciseness and flexibility, regular expressions have been widely adopted in Network Intrusion Detection Systems to represent network attack patterns. However, the expressive power of regular expressions accompanies the intensive computation and memory consumption which leads to severe performance degradation. Recently, graphics processing units have been adopted to accelerate exact string pattern due to their cost-effective and enormous power for massive data parallel computing. Nevertheless, so far as the authors are aware, no previous work can deal with several complex regular expressions which have been commonly used in current NIDSs and been proven to have the problem of state explosion. In order to accelerate regular expression matching and resolve the problem of state explosion, we propose a GPU-based approach which applies hierarchical parallel machines to fast recognize suspicious packets which have regular expression patterns. The experimental results show that the proposed machine achieves up to 117 Gbps and 81 Gbps in processing simple and complex regular expressions, respectively. The experimental results demonstrate that the proposed parallel approach not only resolves the problem of state explosion, but also achieves much more acceleration on both simple and complex regular expressions than other GPU approaches.
AB - Due to the conciseness and flexibility, regular expressions have been widely adopted in Network Intrusion Detection Systems to represent network attack patterns. However, the expressive power of regular expressions accompanies the intensive computation and memory consumption which leads to severe performance degradation. Recently, graphics processing units have been adopted to accelerate exact string pattern due to their cost-effective and enormous power for massive data parallel computing. Nevertheless, so far as the authors are aware, no previous work can deal with several complex regular expressions which have been commonly used in current NIDSs and been proven to have the problem of state explosion. In order to accelerate regular expression matching and resolve the problem of state explosion, we propose a GPU-based approach which applies hierarchical parallel machines to fast recognize suspicious packets which have regular expression patterns. The experimental results show that the proposed machine achieves up to 117 Gbps and 81 Gbps in processing simple and complex regular expressions, respectively. The experimental results demonstrate that the proposed parallel approach not only resolves the problem of state explosion, but also achieves much more acceleration on both simple and complex regular expressions than other GPU approaches.
KW - graphics processing units
KW - pattern matching
KW - regular expression
UR - http://www.scopus.com/inward/record.url?scp=84863158654&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84863158654&partnerID=8YFLogxK
U2 - 10.1109/GLOCOM.2011.6133663
DO - 10.1109/GLOCOM.2011.6133663
M3 - Conference contribution
AN - SCOPUS:84863158654
SN - 9781424492688
T3 - GLOBECOM - IEEE Global Telecommunications Conference
BT - 2011 IEEE Global Telecommunications Conference, GLOBECOM 2011
T2 - 54th Annual IEEE Global Telecommunications Conference: "Energizing Global Communications", GLOBECOM 2011
Y2 - 5 December 2011 through 9 December 2011
ER -