Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/19824
Title: Algorithms to speedup pattern matching for network intrusion detection systems
Authors: Zheng, K
Cai, Z
Zhang, X
Wang, Z 
Yang, B
Keywords: Exclusive matching
Intrusion detection
Negative pattern
Pattern matching
Issue Date: 2015
Publisher: Elsevier
Source: Computer communications, 2015, v. 62, 5065, p. 47-58 How to cite?
Journal: Computer communications 
Abstract: Abstract High-speed network intrusion detection systems (NIDSes) commonly employ TCAMs for fast pattern matching, and parallel TCAM-based pattern matching algorithms have proven promising to achieve even higher line rate. However, two challenges impede parallel TCAM-based pattern matching engines from being truly scalable, namely: (1) how to implement fine-grained parallelism to optimize load balancing and maximize throughput, and (2) how to reconcile between the performance gain and increased power consumption both due to parallelism. In this paper, we propose two techniques to answer the above challenges yielding an ultra-scalable NIDS. We first introduce the concept of negative pattern matching, by which we can splice flows into segments for fine-grained load balancing and optimized parallel speedup while ensuring correctness. negative pattern matching (NPM) also dramatically reduces the number of Ternary Content Addressable Memory (TCAM) lookups thus reducing the power consumption. Then we propose the idea of exclusive pattern matching, which divides the rule sets into subsets; each subset is queried selectively and independently given a certain input without affecting correctness. In concert, these two techniques improve both the pattern matching throughput and scalability in any scenario. Our experimental results show that up to 90% TCAM lookups can be saved, at the cost of merely 10% additional 2-byte index table lookups in the SRAM.
URI: http://hdl.handle.net/10397/19824
ISSN: 0140-3664
EISSN: 1873-703X
DOI: 10.1016/j.comcom.2015.02.004
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

5
Last Week
0
Last month
1
Citations as of Aug 17, 2017

WEB OF SCIENCETM
Citations

4
Last Week
0
Last month
0
Citations as of Aug 15, 2017

Page view(s)

38
Last Week
2
Last month
Checked on Aug 21, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.