Distance Comparison Based Parallel Pattern Matching

JIANG Haiyang; LI Xuefei; YANG Ye

doi:10.11999/JEIT210009

Volume 44 Issue 2

Feb. 2022

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2022 > 44(2): 581-590

JIANG Haiyang, LI Xuefei, YANG Ye. Distance Comparison Based Parallel Pattern Matching[J]. Journal of Electronics & Information Technology, 2022, 44(2): 581-590. doi: 10.11999/JEIT210009

Citation:

JIANG Haiyang, LI Xuefei, YANG Ye. Distance Comparison Based Parallel Pattern Matching[J]. Journal of Electronics & Information Technology, 2022, 44(2): 581-590. doi: 10.11999/JEIT210009

JIANG Haiyang, LI Xuefei, YANG Ye. Distance Comparison Based Parallel Pattern Matching[J]. Journal of Electronics & Information Technology, 2022, 44(2): 581-590. doi: 10.11999/JEIT210009

Citation:

JIANG Haiyang, LI Xuefei, YANG Ye. Distance Comparison Based Parallel Pattern Matching[J]. Journal of Electronics & Information Technology, 2022, 44(2): 581-590. doi: 10.11999/JEIT210009

PDF( 4064 KB)

Distance Comparison Based Parallel Pattern Matching

doi: 10.11999/JEIT210009

JIANG Haiyang^{1, 2, 3
,
,},
LI Xuefei^{1, 2},
YANG Ye^{1, 2}

1.
Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China
2.
University of Chinese Academy of Sciences, Beijing 100049, China
3.
Jiangsu Future Networks Innovation Institute, Nanjing 211111, China

Funds: The National Key Research and Development Program of China (2019YFB1804500), The GHfund B (20210702)

Received Date: 2021-01-05
Accepted Date: 2021-09-01
Rev Recd Date: 2021-09-01

Available Online: 2021-12-20

Publish Date: 2022-02-25

Abstract

Abstract

Multi-Pattern Matching(MPM) works as a core algorithm of packet processing procedure. In order to improve the performance, an efficient packet segmentation and parallel pattern matching algorithm–DCPM (Distance Comparison Parallel Matching) is proposed based on the Aho-Corasick (AC) algorithm. Comparing with existing solutions, DCPM eliminates the threads’ synchronization overhead and decreases the redundant detection overhead. The DCPM algorithm is evaluated on an eight-core processor server platform. The experimental results show that the performance is largely improved (1.3～3.5 times when processing real-world traffic with 8 threads, compared with existing solutions). Meanwhile, the performance of DCPM is less affected by the proportion of pattern strings in the traffic, the length of pattern strings, as well as the number of states in automata.
- Pattern matching,
- Multi-threads,
- Multi-core,
- Deep Packet Inspection(DPI),
- Aho-Corasick (AC) algorithm

FullText(HTML)

References(18)

References

[1]	REN Hao, LITT H, LIU Dongxiao, et al. Toward efficient and secure deep packet inspection for outsourced middlebox[C]. 2019 IEEE International Conference on Communications (ICC), Shanghai, China, 2019: 1–6.
[2]	JIANG Haiyang, ZHANG Guangxing, XIE Gaogang, et al. Scalable high-performance parallel design for network intrusion detection systems on many-core processors[C]. The Architectures for Networking and Communications Systems, San Jose, United States, 2013: 137–146.
[3]	BINSAHAQ A, SHELTAMI T R, and SALAH K. A survey on autonomic provisioning and management of QoS in SDN networks[J]. IEEE Access, 2019, 7: 73384–73435. doi: 10.1109/ACCESS.2019.2919957
[4]	LARABA A, FRANÇOIS J, CHRISMENT I, et al. Defeating protocol abuse with P4: Application to explicit congestion notification[C]. 2020 IFIP Networking Conference (Networking), Paris, France, 2020: 431–439.
[5]	KOPEK C V, FULP E W, and WHEELER P S. Distributed data parallel techniques for content-matching intrusion detection systems[C]. The MILCOM 2007 – IEEE Military Communications Conference, Orlando, USA, 2007: 1–7.
[6]	HAKAK S I, KAMSIN A, SHIVAKUMARA P, et al. Exact string matching algorithms: Survey, issues, and future research directions[J]. IEEE Access, 2019, 7: 69614–69637. doi: 10.1109/ACCESS.2019.2914071
[7]	BREMLER-BARR A, HAY D, and KORAL Y. CompactDFA: Scalable pattern matching using longest prefix match solutions[J]. IEEE/ACM Transactions on Networking, 2014, 22(2): 415–428. doi: 10.1109/TNET.2013.2253119
[8]	BOTACIN M, GALANTE L, CESCHIN F, et al. The AV says: Your hardware definitions were updated![C]. The 14th International Symposium on Reconfigurable Communication-centric Systems-on-Chip (ReCoSoC), York, UK, 2019: 27–34.
[9]	Cisco. Clam AntiVirus(ClamAv)[CP/OL]. http://www.clamav.net/.
[10]	Cisco. Snort official website[CP/OL]. https://www.snort.org/.
[11]	NAJAM M, YOUNIS U, and UR RASOOL R. Speculative parallel pattern matching using stride-k DFA for deep packet inspection[J]. Journal of Network and Computer Applications, 2015, 54: 78–87. doi: 10.1016/j.jnca.2015.04.013
[12]	FU Zhe, LIU Zhi, and LI Jun. Efficient parallelization of regular expression matching for deep inspection[C]. The 26th International Conference on Computer Communication and Networks (ICCCN), Vancouver, Canada, 2017: 1–9.
[13]	JIANG Peng and AGRAWAL G. Combining SIMD and many/multi-core parallelism for finite state machines with enumerative speculation[C]. The 22nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Austin, USA, 2017: 179–191.
[14]	CHOI B, CHAE J, JAMSHED M, et al. DFC: Accelerating string pattern matching for network applications[C]. The 13th USENIX Symposium on Networked Systems Design and Implementation (NSDI’16), Santa Clara, USA, 2016: 551–565.
[15]	WANG Xiang, HONG Yang, CHANG H, et al. Hyperscan: A fast multi-pattern regex matcher for modern CPUs[C]. The 16th USENIX Conference on Networked Systems Design and Implementation, Boston, USA, 2019: 631–648.
[16]	WANG Wei, ZHU Ming, ZENG Xuewen, et al. Malware traffic classification using convolutional neural network for representation learning[C]. 2017 International Conference on Information Networking, Da Nang, Vietnam, 2017: 712–717.
[17]	DEHKORDI A B, SOLTANAGHAEI M, and BOROUJENI F Z. The DDoS attacks detection through machine learning and statistical methods in SDN[J]. The Journal of Supercomputing, 2021, 77(3): 2383–2415. doi: 10.1007/s11227-020-03323-w
[18]	MIT: Darpa dataset[EB/OL]. http://www.ll.mit.edu/ideval/data/1999data.html/.