Exhaust: Optimizing Wu-Manber pattern matching for intrusion detection using Bloom filters

Document Type

Conference Proceeding

Source of Publication

2015 2nd World Symposium on Web Applications and Networking, WSWAN 2015

Publication Date

1-1-2015

Abstract

© 2015 IEEE. Intrusion detection systems are widely accepted as one of the main tools for monitoring and analyzing host and network traffic to protect data from illegal access or modification. Almost all types of signature-based intrusion detection systems must employ a pattern matching algorithm to inspect packets for malicious signatures. Unfortunately, pattern matching algorithms dominate the execution time and have become the bottleneck. To remedy that, we introduce a new software-based pattern matching algorithm that modifies Wu-Manber pattern matching algorithm using Bloom filters. The Bloom filter acts as an exclusion filter to reduce the number of searches to the large HASH table. The HASH table is accessed if there is a probable match represented by a shift value of zero. On average the HASH table search is skipped 10.6% of the time with a worst case average running time speedup over Wu-Manber of 33%. The maximum overhead incurred on preprocessing time is 1.1% and the worst case increase in memory usage was limited to 0.33%.

ISBN

9781479981717

Publisher

Institute of Electrical and Electronics Engineers Inc.

Last Page

6

Disciplines

Computer Sciences

Keywords

Bloom Filters, Intrusion Detection Systems, Network Security, Pattern Matching, Wu-Manber

Scopus ID

84943329755

Indexed in Scopus

yes

Open Access

no

Link to Full Text

Share

COinS