Fast Multipattern Search Algorithms for Intrusion Detection

• Autorzy: Kuri J. , Navarro G. , Mé L.
• Języki publikacji: EN

Abstrakty

EN

We present new search algorithms to detect the occurrences of any pattern from a given pattern set in a text, allowing in the occurrences a limited number of spurious text characters among those of the pattern. This is a common requirement in intrusion detection applications. Our algorithms exploit the ability to represent the search state of one or more patterns in the bits of a single machine word and update all the search states in a single operation. We show analytically and experimentally that the algorithms are able of fast searching for large sets of patterns allowing a wide number of spurious characters, yielding in our machine about a 75-fold improvement over the classical dynamic programming algorithm.

Słowa kluczowe

EN

approximate string matching; bit-parallelism; security; audit trails

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2003
• Tom: Vol. 56, nr 1,2
• Strony: 23--49
• Opis fizyczny: wykr., bibliogr. 28 poz.

Twórcy

autor

Kuri J.

autor

Navarro G.

autor

Mé L.

• Department of Computer Science, University of Chile, Blanco Encalada 2120, Santiago, Chile,

Bibliografia

• 1] Baeza-Yates, R.: Efficient Text Searching, Ph.D. Thesis, Dept. of Computer Science, Univ. of Waterloo, May 1989, Also as Research Report CS-89-17.
• [2] Baeza-Yates, R.: Text Retrieval: Theory and Practice, 12th IFIP World Computer Congress, I, Elsevier Science, September 1992
• [3] Baeza-Yates, R., Gonnet, G.: A new approach to text searching, Comm. of the ACM, 35(10), October 1992, 74-82.
• [4] Baeza-Yates, R., Navarro, G.: Faster Approximate String Matching, Algorithmica, 23(2), 1999, 127-158.
• [5] Baeza-Yates, R., Navarro, G.: New and Faster Filters for Multiple Approximate String Matching, Random Structures and Algorithms (RSA), 20, 2002, 23-49.
• [6] Bishop, M.: A standard audit log format, Proc. 19th National Information Systems Security Conference, 1995.
• [7] Boasson, L., Cegielski, P., Guessarian, I., Matiyasevich, Y.: Window Accumulated Subsequence Matching is linear, Annals of Pure and Applied Logic, 113, 2002, 59-80, Previous version in ACM PODS’99.
• [8] Das, G., Fleischer, R., Gasieniec, L., Gunopulos, D., K¨arkk¨ainen, J.: Episode Matching, Proc. 8th Annual Symposium on Combinatorial Pattern Matching (CPM’96), LNCS 1264, 1997.
• [9] Forrest, S., Perelson, A., Allen, L., Cherukuri, R.: Self-nonself discrimination in a computer, Proc. IEEE Symp. on Research in Security and Privacy, 1994.
• [10] Garvey, T., Lunt, T.: Model-based intrusion detection, Proc. 14th National Computer Security Conference, October 1991.
• [11] Grossi, R., Luccio, F.: Simple and Efficient String Matching with Mismatches, Information Processing Letters, 33(3), 1989, 113-120.
• [12] Jokinen, P., Tarhio, J., Ukkonen, E.: A Comparison of Approximate String Matching Algorithms, Software Practice and Experience, 26(12), 1996, 1439-1458.
• [13] Kendall, K.: A Database of Computer Attacks for the Evaluation of Intrusion Detection Systems, Master Thesis, MIT, Dept. of Electrical Engineering and Computer Science, June 1999.
• [14] Kumar, S.: Classification and Detection of Computer Intrusions, Ph.D. Thesis, Dept. of Computer Science, Purdue University, August 1995.
• [15] Kuri, J., Navarro, G.: Fast Multipattern Search Algorithms for Intrusion Detection, Proc. of the 6th International Symposium on String Processing and Information Retrieval (SPIRE’2000), IEEE CS Press, 2000.
• [16] Kuri, J., Navarro, G., M´e, L., Heye, L.: A Pattern Matching Based Filter for Audit Reduction and Fast Detection of Potential Intrusions, Proc. of the 3rd International Workshop on the Recent Advances in Intrusion Detection (RAID’2000), LNCS v. 1907, 2000.
• [17] Lunt, T.: A survey of intrusion detection techniques, Computers and Security, 12, 1993.
• [18] M´e, L.: Gassata, a genetic algorithm as an alternative tool for security audit analysis, Proc. of the 1st International Workshop on the Recent Advances in Intrusion Detection (RAID’98), 1998.
• [19] Muth, R., Manber, U.: Approximate Multiple Stri g Search, Proc. 7th Annual Symposium on Combinatorial Pattern Matching (CPM’96), LNCS 1075, 1996.
• [20] Myers, G.: A Fast Bit-Vector Algorithm for Approximate String Matching Based on Dynamic Progamming, Journal of the ACM, 46(3), 1999, 395-415.
• [21] Navarro, G.: Multiple Approximate String Matching by Counting, Proc. 3rd South American Workshop on String Processing (WSP’97), Carleton University Press, 1997.
• [22] Navarro, G.: Approximate Text Searching, Ph.D. Thesis, Dept. of Computer Science, Univ. of Chile, December 1998, Technical Report TR/DCC-98-14.
• [23] Navarro, G.: A guided tour to approximate string matching, ACM Computing Surveys, 33(1), 2001, 31-88.
• [24] Navarro, G.: NR-grep: a Fast and Flexible Pattern Matching Tool, Software Practice and Experience (SPE), 31, 2001, 1265-1312.
• [25] Navarro, G., Baeza-Yates, R.: Improving an Algorithm for Approximate Pattern Matching, Algorithmica, 30(4), 2001, 473-502.
• [26] Navarro, G., Baeza-Yates, R., Arcoverde, J.: Matchsimile: A Flexible Approximate Matching Tool for Searching Proper Names, Journal of the American Society for Information Science and Technology (JA-SIST), 2003, To appear. Earlier version in Proc. SBBD 2001.
• [27] Sellers, P.: The theory and computation of evolutionary distances: pattern recognition, J. of Algorithms, 1, 1980, 359-373.
• [28] Wu, S., Manber, U.: Fast text searching allowing errors, Comm. of the ACM, 35(10), October 1992, 83-91.