Constrained Row-Based Bit-Parallel Search in Intrusion Detection


  • Ambika Shrestha Chitrakar Norwegian University of Science and Technology
  • Slobodan Petrovic Norwegian University of Science and Technology


Most Intrusion Detection Systems (IDS) employ exact search for attack patterns in the analyzed traffic. Because of that, if an attacker introduces changes in the known attack pattern, the obtained new attack pattern becomes impossible to detect. To cope with this problem, an IDS can use approximate search instead of exact search. But then, false positives and false negatives can appear due to the fact that the type and/or the distribution of changes to the old attack traffic pattern is not taken into account. In this paper, we propose a new approximate search algorithm for IDS that introduces constraints on the numbers of individual change operations on the old attack traffic patterns. In such a way, we take into account a-priori knowledge about the type and/or distribution of changes. The experiments show that the false positive and false negative rates obtained with an IDS using approximate search with constraints are significantly reduced compared to a system without constraints. At the same time, the computational cost of introducing constraints is relatively small.

Author Biographies

Ambika Shrestha Chitrakar, Norwegian University of Science and Technology

Norwegian Information Security Laboratory

Slobodan Petrovic, Norwegian University of Science and Technology

Norwegian Information Security Laboratory


Snort. [Accessed: jan 2016].

Ricardo Baeza-Yates and Gaston H. Gonnet. A new approach to text searching. Commun. ACM, 35(10):74–82, October 1992.

Nguyen Le Dang, Dac-Nhuong Le, and Vinh Trong Le. A new multiple-pattern
matching algorithm for the network intrusion detection system. IACSIT International Journal of Engineering and Technology, 8(2):94–100, April 2016.

Simone Faro and Thierry Lecroq. Twenty years of bit-parallelism in string matching. In J. Holub, B. W. Watson, and J. Ždárek, editors, Festschrift for Bo?rivoj Melichar, pages 72–101. 2012.

Sung il Oh, Min Sik Kim, and Inbok Lee. An efficient bit-parallel algorithm for ids. In In Proc. of RACS 2013, pages 43–44, 2013.

J. Kuri and G. Navarro. Fast multipattern search algorithms for intrusion detection. In String Processing and Information Retrieval, 2000. SPIRE 2000. Proceedings. Seventh International Symposium on, pages 169–180, 2000.

Gonzalo Navarro and Mathieu Raffinot. Flexible Pattern Matching in Strings:
Practical On-line Search Algorithms for Texts and Biological Sequences. Cambridge University Press, New York, NY, USA, 2002.

Lin Tan and Timothy Sherwood. Architectures for bit-split string scanning in
intrusion detection. IEEE Micro, 26(1):110–117, 2006.

Sun Wu and Udi Manber. Fast text searching allowing errors. Commun. ACM,
35(10):83–91, October 1992.





Norsk Informasjonssikkerhetskonferanse 2016