A new Multi-threaded and Interleaving Approach to Enhance String Matching for Intrusion Detection Systems.

Ali Shatnawi; Bushra AlHajouj; Moath Jarrah

Author(s)

Ali Shatnawi Department of Computer Engineering, College of Computer and Information Technology Jordan University of Science and Technology, Irbid, 22110, Jordan

Bushra AlHajouj Department of Computer Engineering, College of Computer and Information Technology Jordan University of Science and Technology, Irbid, 22110, Jordan

Moath Jarrah Department of Computer Engineering, College of Computer and Information Technology Jordan University of Science and Technology, Irbid, 22110, Jordan

Abstract

String matching algorithms are computationally intensive operations in computer science. The algorithms find the occurrences of one or more strings patterns in a larger string or text. String matching algorithms are important for network security, biomedical applications, Web search, and social networks. Nowadays, the high network speeds and large storage capacity put a high requirement on string matching methods to perform the task in a short time. Traditionally, Aho-Corasick algorithm, which is used to find the string matches, is executed sequentially. In this paper, a new multi-threaded and interleaving approach of Aho-Corasick using graphics processing units (GPUs) is designed and implemented to achieve high-speed string matching. Compute Unified Device Architecture (CUDA) programming language is used to implement the proposed parallel version. Experimental results show that our approach achieves more than 5X speedup over the sequential and other parallel implementations. Hence, a wide range of applications can benefit from our solution to perform string matching faster than ever before.

Publication Details

Page(s) 279-287

DOI DOI not available

Published Journal: International Journal of Communication Networks and Information Security, Volume: 10, Issue: 2, Year: 2018

Request the full text from PASTIC

References

Y.H.Kim,W.H.Park, 2014.A study on cyber threat prediction based on intrusion detection event for apt attack detection,“ Multimedia Tools and Applications 71 685 -698

R.T.Liu,N.F.Huang,C.H.Chen,C.N.Kao, 2004.A fast string-matching algorithm for network processor-based intrusion detection system,” ACM Transactions on Embedded Computing Systems 3 614 -633

N.Wattanapongsakorn, 2015.Web-based monitoring approach for network-based intrusion detection and prevention,Multimedia Tools and Applications 16 639 -641

C.Yin, 2017.Towards accurate intrusion detection based on improved clonal selection algorithm,” Multimedia Tools and Applications 19 19397 -19410

J.Zobel, 1996.Phonetic string matching: Lessons from information retrieval,” The Nineteenth annual international,ACM SIGIR conference on Research and Development in Information Retrieval 166 -172

K.Kukich, 1992.Techniques for automatically correcting words in text,” ACM Computing Surveys, 24 377 -439

W.T.Balke, 2004.Multi-objective query processing for database systems,” The Thirtieth International Conference on Very Large Data Bases VLDB Endowment 936 -947

D.Brown, 2000.System and methods for searching and matching databases,” US Patent no. 6 398 -

P.O.Kristensson, 2005.Relaxing stylus typing precision by geometric pattern matching,”,The Tenth International Conference on Intelligent User Interfaces, USA 151 -158

A.Tumeo,O.Villa, 2010.Accelerating DNA analysis applications on GPU clusters,“ The Eighth IEEE Symposium on Application Specific Processors, 71 -76

X.Zhou,B.Xu,Y.Qi,J.Li, 2008.MRSI: A fast pattern matching algorithm for anti-virus applications, 256 -261

B.Lampson,V.Srinivasan, 1999.IP lookups using multiway and multicolumn search,” IEEE/ACM Transactions on Networking (TON) 7 324 -334

R.D.Graham, 2014.Finite state machine parsing for internet protocols: faster than you think,” Security and Privacy Workshops, 185 -190

P.Garcia-Teodoro,J.Diaz-Verdejo,G.Maciá- Fernández, 2009.Anomaly-based network intrusion detection: techniques, systems and challenges,” computers & security, 28 18 -28

L.L.Cheng,S.M.Yiu, 2003.Approximate string matching in DNA sequences, 303 -310

D.Gusfield, 1997.Algorithms on strings, trees and sequences: computer science, -

L.Zhao,K.Zhou,J.Guo,S.Wang,T.Lin, 2018.A universal string matching approach to screen content coding,” IEEE Transactions on Multimedia 20 796 -809

A.V.Aho,M.J.Corasick, 1975.Efficient string matching: an aid to bibliographic search,” Communications of the ACM, 18 333 -340

S.Vidanagamachchi,S.Dewasurendra, 2013.Hardware software co-design of the Aho-Corasick algorithm: Scalable for protein identification?,”,The Eighth IEEE International Conference on Industrial and Information Systems 321 -325

M.Norton,Columbia, 2004.Optimizing pattern matching for intrusion detection, -

V.Bhardwaj,V.Garg, 2015.A comparative study of WuManber string matching algorithm and its variations,International Journal of Computer Applications 17 34 -38

Y.Jararweh,M.Jarrah, 2012.Exploiting GPUs for compute-intensive medical applications,” International Conference on Multimedia Computing and Systems 29 -34

M.Shehab,M.Al-Ayyoub,Y.Jararweh, 2017.Accelerating compute-intensive image segmentation algorithms using GPUs,”,The Journal of Supercomputing 73 1929 -1951

L.Deligiannidis,H.R.Arabnia, 2014.Parallel video processing techniques for surveillance applications,” International Conference on Computational Science and Computational Intelligence 183 -189

M.A.S.Al-khatib,A.H.Lone, 2018.Acoustic lightweight pseudo random number generator based on cryptographically secure LFSR,International journal of Communication Networks and Information Security 10 38 -45

N.P.Tran,M.Lee,S.Hong, 2013.High throughput parallel implementation of Aho-Corasick algorithm on a GPU,” Parallel and Distributed Processing Symposium Workshops,PhD Forum 1807 -1816

X.Zha, 2011.Multipattern string matching on a GPU,”,IEEE Symposium on Computers and Communications 277 -282

C.S.Kouzinopoulos,J.A.M.Assael,T.K.Pyrgiotis, 2014.A hybrid parallel implementation of the Aho-Corasick and Wu-Manber algorithms using NVIDIA CUDA and MPI evaluated on a biological sequence database, 1407 -

C.H.Lin,C.H.Liu,L.SChien,S.C.Chang, 2013.Accelerating pattern matching using a novel parallel algorithm on GPUs,”, 10 1906 -1916

M.Aldwairi,A.M.Abu-Dalo,M.Jarrah, 2017.Pattern matching of signature-based IDS using Myers algorithm under MapReduce framework,EURASIP Journal on Information Security 9 -19

P.S.Oke,A.S.Vaidya,Optimization, 2015.Optimization of parallel AhoCorasick multipattern matching algorithm on GPU,”, 3 5191 -5200

A.Ahmad,N.B.Idris,M.N.Kama, 2017.CloudIDS: Cloud intrusion detection model inspired by Dendritic cell mechanism,International journal of Communication Networks and Information Security 9 67 -75

S.Soroushnia,M.Daneshtalab,J.Plosila,T.Pahikkala, 2014.High performance pattern matching on heterogeneous platform,” Journal of Integrative Bioinformatics 11 88 -98

L.Ligowski, 2009.An efficient implementation of Smith Waterman algorithm on GPU using CUDA for massively parallel scanning of sequence databases,” IEEE International Symposium on Parallel & Distributed Processing 1 -8

M.Zeeshan,H.Javed, 2017.Discrete R-contiguous bit matching mechanism appropriateness for anomaly detection in wireless sensor networks,International journal of Communication Networks and Information Security 9 157 -163

G.Encarnação,N.Sebastião, 2011.Advantages and GPU implementation of high performance indexed DNA search based on suffix arrays,” International Conference on High Performance Computing and Simulation 49 -55

Y.Liu,B.Schmidt, 2012.Evaluation of GPU-based seed generation for computational genomics using BurrowsWheeler transform,” Parallel and Distributed Processing Symposium Workshops,PhD Forum 684 -690

D.Zhang,Y.Zhang,X.Huang, 2008.Parallelization of FM-index,”,The Tenth IEEE International Conference on High Performance Computing and Communications 169 -173

S.Cook,Newnes, 2012.CUDA programming: a developer's guide to parallel computing with GPUs,”, -

Snort, 2018., -

M.Aldwairi,D.Alansari, 2011.Fast pattern matching for intrusion detection using exclusion and inclusion filters,”,The Seventh International Conference on Next Generation Web Services Practices (NWeSP) 24 -30

Wireshark, 2018.,Wireshark v1.4 -