DEVELOPING A FASTER PATTERN MATCHING ALGORITHMS FOR INTRUSION DETECTION SYSTEM
DOI:
https://doi.org/10.47839/ijc.18.3.1520Keywords:
Algorithms, Pattern Matching, Boyer-More, Aho-Corasick, Rabin Karp, Knuth-Morris-Pratt, IDS, Intrusion Detection System, signature based malicious.Abstract
Fast pattern matching algorithms mostly used by IDS, which are considered one of the important systems used to monitor and analyze host and network traffic. Their main function is to detect various types of malicious and malware files by examining incoming and outgoing data through the network. As the network speed growing, the malicious behavior and malware files are increasing; the pattern matching algorithms must be faster. In this research paper we are presenting a new method of pattern matching, which could be a platform for enhancement in the future. In this field, researchers spared no efforts to introduce fast algorithms for pattern matching. The Most popular algorithms are Boyer-Moore, Aho–Corasick, Naïve String search, Rabin Karp String Search and Knuth–Morris–Pratt. Based on studying these techniques we are developing algorithms that process the text data, using different algorithm technique and then we’ll test the performance and compare the processing time with the fastest proven pattern matching algorithms available. Document the result and draw the overall conclusion.References
M. Crochemore, T. Lecroq, “Pattern-matching and text-compression algorithms,” ACM Computing Surveys (CSUR), vol. 28, issue 1, pp. 39-41, March 1996.
R.S. Boyer, J.S. Moore, “A fast string searching algorithm,” Communications of the ACM, vol. 20, issue 10, pp. 762-772, 1977.
A. Aho, M. Corasick, “Efficient string matching: an aid to bibliographic search,” Communications of the ACM, vol. 18, issue 6, pp. 333-340, 1975.
J. Fan, K. Su, “An efficient algorithm for matching multiple patterns,” IEEE Transactionson on Knowledge and Data Engineering, vol. 5, issue 2, pp. 339-351, 1993.
S.K. Shivaji, Prabhudeva S., “Plagiarism detection by using Karp-Rabin and string matching algorithm together,” International Journal of Computer Applications, vol. 116, issue 23, pp. 1–5, 2015.
S. Wahlstrom, “Evaluation of string searching algorithms,” Proceedings of the IDT Mini-Conference on Interesting Results in Computer Science and Engineering, 2013, pp. 1-6.
G. Behera, “Novel pattern matching algorithm in genome sequence analysis,” International Journal of Computer Science and Information Technologies, vol. 5, issue 4, pp. 5450–5457, 2014.
E. Silva de Moura, G. Navarro, N. Ziviani, R. Baeza-Yates, “Fast and flexible word searching on compressed text,” ACM Transactions on Information Systems, vol. 18, issue 2, pp. 113-139, 2000.
S. Hasib, M. Motwani, A. Saxena, “Importance of Aho-Corasick string matching algorithm in real world applications,” International Journal of Computer Science and Information Technologies, vol. 4, issue 3, pp. 467-469, 2013.
M. Alicherry, M. Muthuprasanna,V. Kumar, “High speed pattern matching for network IDS/IPS,” Proceedings of the 2006 IEEE International Conference on Network Protocols, 12-15 Nov. 2006, pp. 187-196.
A. Corasick, The Life n Photo, 2008, [Online]. Available at: https://cskane.wordpress.com/2008/07/23/aho-corasick-trie
K. Namjoshi, G. Narlikar, “Robust and fast pattern matching for intrusion detection,” Proceedings of the 2010 IEEE International Conference INFOCOM, 14-19 March 2010, pp. 1-10.
P. Pandiselvam, T. Marimuthu, R. Lawrance, “A comparative study on string matching algorithms of biological sequences,” 2013, [Online]. Available at: https://arxiv.org/ftp/arxiv/papers/1401/1401.7416.pdf
M. Kharbutli, M. Aldwairi, A. Mughrabi, “Function and data parallelization of Wu-Manber pattern matching for intrusion detection systems,” Network Protocols and Algorithms, vol. 4, no. 3, pp. 46-61, 2012.
M. Dubiner’, Z. Galilt, E. Magen, “Faster tree pattern matching,” Journal of the ACM, vol. 41, issue 2, pp. 205-213, March 1994.
S. Doria, G. Landau, “Construction of Aho Corasick automaton in linear time for integer alphabets,” 2012, [Online]. Available at: http://cs.haifa.ac.il/~landau/gadi/shiri.pdf
R. Bhukya, and D. V. L. N. Somayajulu, “Exact multiple pattern matching algorithm using DNA sequence and pattern pair,” International Journal of Computer Applications, vol. 17, issue 8, pp. 32-38, 2011.
A. Ziad, M. Aqel, I. Emary, “Multiple skip multiple pattern matching algorithm (MSMPMA),” IAENG International Journal of Computer Science, vol. 34, no. 2, pp. 14-20, 2007.
H. Gharaee, S. Seifi, and N. Monsefan, “A survey of pattern matching algorithm in intrusion detection system,” Proceedings of the 7th IEEE International Symposium on Telecommunications (IST), 2014, pp. 946-953.
C.-H. Lin, et al., “Accelerating pattern matching using a novel parallel algorithm on GPUs,” IEEE Transactions on Computers, vol. 62, issue 10, pp. 1906-1916, 2013.
R. M. Karp, M. O. Rabin, “Efficient randomized pattern-matching algorithms,” IBM Journal of Research and Development, vol. 31, issue 2, pp. 249-260, 1987.
R. Ehtesham, M. El-Kharashi, F. Gebali, “A fast string search algorithm for deep packet classification,” Computer Communications, vol. 27, issue 15, pp. 1524-1538, 2004.
L. Colussi, “Correctness and efficiency of the pattern matching algorithms,” Information and Computation, vol. 95, issue 2, pp. 225-251, Dec. 1991.
M. Crochemore, A. Czumaj, L. Gasieniec, S. Jarominek, T. Lecroq, W. Plandowski, W. Rytter, “Speeding up two string matching algorithms,” Algorithmica, vol. 12, no. 4-5, pp. 247-267, 1994.
Downloads
Published
How to Cite
Issue
Section
License
International Journal of Computing is an open access journal. Authors who publish with this journal agree to the following terms:• Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
• Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
• Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
