Bloom Filters Optimized Wu-Manber for Intrusion Detection

Authors

Monther Aldwairi, Network Engineering and Security Department, Jordan University of Science and Technology
Koloud Al-Khamaiseh, cDepartment of Electrical Engineering, Tafila Technical University
Fatima Alharbi, College of Technological Innovation, Zayed University
Babar Shah, College of Technological Innovation, Zayed University

Prior Publisher

The Association of Digital Forensics, Security and Law (ADFSL)

Abstract

With increasing number and severity of attacks, monitoring ingress and egress network traffic is becoming essential everyday task. Intrusion detection systems are the main tools for capturing and searching network traffic for potential harm. Signature-based intrusion detection systems are the most widely used, and they simply use a pattern matching algorithms to locate attack signatures in intercepted network traffic. Pattern matching algorithms are very expensive in terms of running time and memory usage, leaving intrusion detection systems unable to detect attacks in real-time. We propose a Bloom filters optimized Wu-Manber pattern matching algorithm to speed up intrusion detection. The Bloom filter programs the hash table into a vector, which is quickly queried to exclude unnecessary searches. On average hash table searches are avoided 10.6% of the time. The proposed algorithm achieves a best-case speedup of 66% and worst-case speedup of 33% over Wu-Manber at the cost of 0.33% memory usage increase.

References

Roberts, L. (2000). Internet growth trends. IEEE Computer Magazine Internet watch column 2000.

Zheng, K., Cai, Z., Zhang, X., Wang, Z., Yang, B. (2015). Algorithms to speedup pattern matching for network intrusion detection systems, Computer Communications, 62, 47-58.

Aldwairi, M. (2006). Hardware-efficient pattern matching algorithm and architectures for fast intrusion detection. Available from NCSU Theses and Dissertations Institutional Repository (id 1840.16/3558).

Jirachan, T., & Piromsopa, K. (2015). Applying KSE-test and K-means clustering towards scalable unsupervised intrusion detection. Proceedings of the 12th International Joint Conference on Computer Science and Software Engineering (JCSSE}, (82-87). IEEE.

Aldwairi, M., Khamayseh, Y., & Al-Masri, M. (2015). Application of artificial bee colony for intrusion detection systems. Security and Communication Networks, 8(16), 2730- 2740. doi:10.1002/sec.588.

Roesch, M. (1999). Snort - lightweight intrusion detection for networks. Proceedings of the 13th USENIX Systems Administration Conference (LISA '99}. Seattle, W A. Snort. (2016). Network Intrusion Detection €3 Prevention System. Retrieved from https:/ /www.snort.org/.

Lam, V.T., Mitzenmacher, M., & Varghese, G. (2010). Carousel: scalable logging for intrusion prevention systems. Proceedings of the 7th USENIX conference on Networked systems design and implementation (NSDI'10} (pp. 24-39). Berkeley, CA, USA: USENIX Association.

Antonatos, S., Anagnostakis, K. & Markatos, E. (2004). Generating realistic workloads for network intrusion detection systems. SIGSOFT Software Engineering Notes. 29(1), 207-215.

Aldwairi, M., & Alansari, D. (2011). Exscind: fast pattern matching for intrusion detection using exclusion and inclusion filters. Proceedings of the Next Generation Web Services Practices (NWeSP) (24-30). Salamnca, Spain: IEEE. doi:10.1109/NWeSP.2011.6088148

Aldwairi, M., Conte, T., & Franzon P. (2004). Configurable String Matching Hardware for Speeding up Intrusion Detection. Proceedings of the Workshop on architectural support for security and antivzrus (WASSA}, zn conjunction with ASPLOS XI. Boston, MA.

Gharaee, H., Seifi, S. & Monsefan, N. (2014). A survey of pattern matching algorithm in intrusion detection system. Proceedings of the 7th International Symposium on Telecommunications (IST} (946-953), Iran.

Dharmaprikar, S., Krishnamurthy, P., Sproull, T. S., & Lockwood, J. W. (2004). Deep packet inspection using parallel bloom filters. IEEE Micro, 24(1), 52-61.

Yang, D., Xu, K. & Cui, Y. (2006). An improved Wu-Manber multiple patterns matching algorithm. Proceedings of the 25th IEEE International Performance, Computing, and Communications Conference (IPCCC), (680-686).

Sunday, D. (1990). A very fast substring search algorithm. Communications of the ACM, 33(8), 132-142.

Xunxun, C., Binxing, F., Lei, L., & Yu, J. (2005). WM+: An optimal multi-pattern string matching algorithm based on the WM algorithm. Proceedings of the 6th International Workshop on Advanced Parallel Processing Technologies ( AP PT) (515-523). Hong Kong, China.

Liu, C., Chen, A., Wu, D., & Wu, J. (2011). A DF A with extended character-set for fast deep packet inspection. Proceedings of the 2011 International Conference on Parallel Processing {ICPP}(1-10).

Beale, J., Baker, A., Esler, J. & Northcutt, S. (2007). Snort: IDS and IPS toolkit. Burlington, MA: Syngress Publishing, Elsevier.

Peng, Z., Wang, Y. & Xue, J. (2014). An Improved Multi-pattern Matching Algorithm for Large-Scale Pattern Sets. Proceedings of the Tenth International Conference on Computational Intelligence and Security (CIS) (197-200).

Zhang, W. (2016). An Improved Wu-Manber Multiple Patterns Matching Algorithm. Proceedings of the 2016 IEEE International Conference on Electronic Information and Communication Technology (ICEICT 2016)( 286-289).

Lee, J. K. Woo, J., & An, J. H. (2016). Improved Pattern Matching Method for Intrusion Detection Systems under DDoS Attack. Indian Journal of Science and Technology, 8(25), 1-4.

Aldwairi, M., & Al-Khamaiseh, K. (2015). Exhaust: Optimizing Wu-Manber Pattern Matching for Intrusion Detection using Bloom Filters. Proceedings of the 2nd World Symposium on Web Applications and Networking {WSWAN'2015}(1-6). Sousse, Tunisia: IEEE. doi:10.1109/WSWAN.2015.7209081

Dittrich, D. (2015, May 15). The DoS Project's trinoo distributed denial of service attack tool analysis. University of Washington. Retrieved from http://staff.washington.edu/dittrich/misc/ trinoo.analysis.

Kharbutli, M., Aldwairi, M., & Mughrabi, A. (2012). Function and Data Parallelization of Wu-Manber Pattern Matching for Intrusion Detection Systems. Network Protocols and Algorithms, 4(3), 46-61.

Boyer, R. S. & Moore, J. S. (1977). A fast string searching algorithm. Communications of the ACM, 20(10), 762- 772.

Aho, A. & Corasick, M. (1975). Efficient string matching: an aid to bibliographic search. Communications of the A CM, 18, 333-340.

Wu, S., & Manber, U. (1994). Fast algorithm for multi-pattern searching. Technical Report TR94-17. University of Arizona at Tuscan. Retrieved from http: //webglimpse.net/pubs/TR94-17.pdf.

Bloom, B. H. (1970). Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7), 422- 426.

Fan, L., Cao, P., Almeida, J. & Broder, A. (2000). Summary cache: a scalable widearea web cache sharing protocol. IEEE/ACM Transactions on Networking, 8(3), 281-293.

Partow, A. (2015, May 15). General purpose hash function algorithms. Retrieved from http://www.partow.net/programming/hash functions/ .

Ramakrishna, M., & Zobel, J. (1997). Performance in practice of string hashing functions. Proceedings of the 5th International Systems for (215-223). Conference Advanced on Database Applications.

Snort rules. (n.d.). Retrieved, May 15, 2015, from Snort website, http: //www.snort.org/.

DEFCON Organization. (n.d.). Retrieved, May 15, 2015, from DEFCON website, http://www.defcon.org.

Recommended Citation

Aldwairi, Monther; Al-Khamaiseh, Koloud; Alharbi, Fatima; and Shah, Babar (2016) "Bloom Filters Optimized Wu-Manber for Intrusion Detection," Journal of Digital Forensics, Security and Law: Vol. 11 , Article 5.
DOI: https://doi.org/10.15394/jdfsl.2016.1427
Available at: https://commons.erau.edu/jdfsl/vol11/iss4/5