Multi-stride Indexing: Improve NFA for Fast and Scalable DPI

HUO Sheng; ZHANG Dafang; LI Yanbiao

doi:10.1049/cje.2017.11.015

Volume 27 Issue 1

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2018 > 27(1): 86-92

HUO Sheng, ZHANG Dafang, LI Yanbiao, “Multi-stride Indexing: Improve NFA for Fast and Scalable DPI,” Chinese Journal of Electronics, vol. 27, no. 1, pp. 86-92, 2018, doi: 10.1049/cje.2017.11.015

Citation:

HUO Sheng, ZHANG Dafang, LI Yanbiao, “Multi-stride Indexing: Improve NFA for Fast and Scalable DPI,” Chinese Journal of Electronics, vol. 27, no. 1, pp. 86-92, 2018, doi: 10.1049/cje.2017.11.015

HUO Sheng, ZHANG Dafang, LI Yanbiao, “Multi-stride Indexing: Improve NFA for Fast and Scalable DPI,” Chinese Journal of Electronics, vol. 27, no. 1, pp. 86-92, 2018, doi: 10.1049/cje.2017.11.015

Citation:

PDF( 476 KB)

Multi-stride Indexing: Improve NFA for Fast and Scalable DPI

doi: 10.1049/cje.2017.11.015

College of Information Science and Engineering, Hunan University, Changsha 410082, China

Funds: This work is supported by the National Science Foundation of China (No.61472130), the National Basic Research Program of China (973) (No.2012CB315805), and the Prospective Research Project on Future Networks of Jiangsu Future Networks Innovation Institute (No.BY2013095-1-05).

More Information

Corresponding author: ZHANG Dafang (corresponding author) Ph.D., professor in Hunan University in China. His research interests include fault-tolerant, trusted computing and network security. (Email:dfzhang@hnu.edu.cn)
Received Date: 2016-03-10
Rev Recd Date: 2016-06-26
Publish Date: 2018-01-10

Abstract

Abstract

Regular expression matching is one of the key techniques for Deep packet inspection (DPI). Generally, the Deterministic finite automata (DFA) can process regular expression matching at a very high rate but memory inefficient. By contrast, the Non-deterministic finite automata (NFA) improves the memory efficiency significantly, at the cost of low speed. To meet the increasing demands on both throughput and memory scalability, we propose a novel schema to achieve fast regular expression with reasonable and controllable memory consumption. According to observations on matching real traffic, we design a Multi-Stride Indexing (MSI) table and divide each matching into two steps, toward the MSI table and the NFA respectively. the MSI table consumes a small fixed amount of on-chip memories(it is about 20KB for 2 stride level MSI table). After the most of unnecessary matching was eliminated via MSI table, we implement the fast-speed regular expression matching with NFA.
- Regular expression matching,
- Deep packet inspection (DPI),
- Non-deterministic finite automata (NFA),
- Multi-stride.

FullText(HTML)

References(20)

References

H. Jiang, G. Zhang, G. Xie, et al., "Scalable high-performance parallel design for network intrusion detection systems on manycore processors", ACM/IEEE Symposium on Architectures for Networking and Communications Systems, pp.137-146, 2013.

P. Gupta, S. Lin and N. Mckeown, "Routing lookups in hardware at memory access speeds", Proc. of Infocom., Vol.3, pp.1240-1247, 1998.

T. Yang, G. Xie, Y. Li, et al., "Guarantee IP lookup performance with FIB explosion", ACM Sigcomm Computer Communication Review, Vol.44, pp.39-50, 2014.

D. Luchaup, L. De Carli, S. Jha and E. Bach, "Deep packet inspection with dfa-trees and parametrized language overapproximation", INFOCOM 2014 Proceedings IEEE, pp.531-539, 2014.

F. Yu, Z. Chen, Y. Diao, T.V. Lakshman and R.H. Katz, "Fast and memory-efficient regular expression matching for deep packet inspection", ACM/IEEE Symposium on ANCS 2006, pp.93-102, 2006.

R. Smith, C. Estan, S. Jha, "XFA:Faster signature matching with extended automata", IEEE Symposium on Security and Privacy, 2008.

R. Smith, C. Estan, S. Jha, "Deflating the big bang:Fast and scalable deep packet inspection with extended finite automata", Proceedings of the ACM SIGCOMM 2008 Conference on Data Communication, 2008.

S. Kumar, S. Dharmapurikar, F. Yu, et al., "Algorithms to accelerate multiple regular expressions matching for deep packet inspection", SIGCOMM, Vol.36, No.4, pp.339-350, 2006.

C.R. Clark and D.E. Schimmel, "Scalable pattern matching for high speed networks", 12th Annual IEEE Symposium on FieldProgrammable Custom Computing Machines 2004, pp.249-257, 2004.

B.C. Brodie, R.K. Cytron and D.E. Taylor, "A scalable architecture for high-throughput regular-expression pattern matching", 33rd International Symposium on Computer Architecture, pp.191-202, 2006.

L. Tan, B. Brotherton and T. Sherwood, "Bitsplit stringmatching engines for intrusion detection and prevention", ACM Trans. Archit. Code Optim, Vol.3, No.1, pp.3-34, 2006.

I. Sourdis and D. Pnevmatikatos, "Pre-decoded cams for efficient and high-speed nids pattern matching", 12th Annual IEEE Symposium on FCCM 2004, pp.258-267, 2004.

F. Yu, R.H. Katz and T.V. Lakshman, "Gigabit rate packet pattern-matching using tcam", Proceedings of the 12th IEEE International Conference on ICNP 2004, pp.174-183, 2004.

Y. Zu, M. Yang, Z. Xu, et al., "GPU-based NFA implementation for memory efficient high speed regular expression matching", Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 12, pp.129-140, 2012.

X. Yu and M. Becchi, "GPU acceleration of regular expression matching for large datasets:Exploring the implementation space", Proceedings of the ACM International Conference on Computing Frontiers, CF 13. ACM, 2013.

H. Lu, K. Zheng, B. Liu, et al., "A memory-efficient parallel string matching architecture for high-speed intrusion detection", Selected Areas in Communications, IEEE Journal on, Vol.24, No.10, pp.1793-1804, 2006.

M. Alicherry, M. Muthuprasanna, and V. Kumar, "High speed pattern matching for network ids/ips", Proceedings of the 200614th IEEE International Conference on Network Protocols, pp.187-196, 2006.

N. Hua, H. Song, and T.V. Lakshman, "Variablestride multipattern matching for scalable deep packet inspection", INFOCOM 2009, IEEE, 2009.

"Regular expression pocessor", http://regex.wustl.edu, 2015.

V. Paxson. "Bro:A system for detecting network intruders in real-time", Comput. Netw., Vol.31, No.23-24, pp.2435-2463, 1999.

Relative Articles

Supplements(0)

Cited By

Proportional views