Context-Aware Systems and Applications, and Nature of Computation and Communication. 6th International Conference, ICCASA 2017, and 3rd International Conference, ICTCC 2017, Tam Ky, Vietnam, November 23-24, 2017, Proceedings

Research Article

Enhancement of Wu-Manber Multi-pattern Matching Algorithm for Intrusion Detection System

  • @INPROCEEDINGS{10.1007/978-3-319-77818-1_7,
        author={Soojin Lee and Toan Phan},
        title={Enhancement of Wu-Manber Multi-pattern Matching Algorithm for Intrusion Detection System},
        proceedings={Context-Aware Systems and Applications, and Nature of Computation and Communication. 6th International Conference, ICCASA 2017, and 3rd International Conference, ICTCC 2017, Tam Ky, Vietnam, November 23-24, 2017, Proceedings},
        proceedings_a={ICCASA \& ICTCC},
        year={2018},
        month={3},
        keywords={Intrusion detection systems Pattern matching Network security Wu-Manber Bloom filters},
        doi={10.1007/978-3-319-77818-1_7}
    }
    
  • Soojin Lee
    Toan Phan
    Year: 2018
    Enhancement of Wu-Manber Multi-pattern Matching Algorithm for Intrusion Detection System
    ICCASA & ICTCC
    Springer
    DOI: 10.1007/978-3-319-77818-1_7
Soojin Lee1,*, Toan Phan1,*
  • 1: Korea National Defense University
*Contact email: cyberkma@gmail.com, pttoan.it@gmail.com

Abstract

Intrusion Detection System (IDS) is a monitoring system that is the most commonly used today. IDS monitors and analyzes network traffic to detect and prevent malicious behaviors. The main process of IDS is pattern matching, which typically accounts for about 70% of IDS processing time [9]. Wu-Manber [11] is one of the fastest pattern matching algorithms [3] which is commonly used in IDSs. It uses hash techniques to build the hash tables based on the shortest patterns. However, the difference between patterns often degrades the efficiency of the algorithm. In this paper, we propose an improved Wu-Manber algorithm that reduces dependence on the shortest patterns by combining Bloom filters. The experimental results show that our algorithm reduces the matching time by 10% in the worst case and 78% in the best case compared to the original Wu-Manber algorithm, and also reduces the memory usage by 0.3%.