Abstract
The signature-based intrusion detection is one of the most commonly used techniques implemented in modern intrusion detection systems (IDS). One of the powerful tools that gained wide acceptance in IDS signatures over the past several years is the regular expressions. However, the performance requirements of traditional methods for matching the incoming events against regular expressions are prohibitively high. This limits the use of regular expressions in majority of modern IDS products. In this work, we present an approach for selective matching of regular expressions. Instead of serially matching all regular expressions, we compile a set of shortest patterns most frequently seen in regular expressions that allows to quickly filter out events that do not match any of the IDS signatures. We develop a method to optimize the final set of patterns used for selective matching to reduce the amount of redundancy among patterns while maintaining a complete coverage of the IDS signatures set. Our experimental results on the DARPA data set and a live network traffic show that our method leads on average to 18%-34% improvement over a commonly used finite automata-based matching approach.
The work was supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) under Grant STOGP 3181091.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Markatos, E.P., Antonatos, S., Polychronakis, M., Anagnostakis, K.G.: Exclusion-based signature matching for intrusion detection. In: Proceedings of CCN, pp. 146–152 (2002)
Sourdis, I., Dimopoulos, V., Pnevmatikatos, D., Vassiliadis, S.: Packet pre-filtering for network intrusion detection. In: Proceedings of ANCS, pp. 183–192 (2006)
Roesch, M.: Snort - lightweight intrusion detection for networks. In: Proceedings of LISA, pp. 229–238. USENIX Association, Berkeley (1999)
Paxson, V.: Bro: a system for detecting network intruders in real-time. In: Proceedings of SSYM, p. 3. USENIX Association, Berkeley (1998)
Q1Labs. Qradar siem (2010), http://www.q1labs.com/
TippingPoint. Intrusion prevention systems (2010), http://www.tippingpoint.com/
Yu, F., Chen, Z., Diao, Y., Lakshman, T.V., Katz, R.H.: Fast and memory-efficient regular expression matching for deep packet inspection. In: Proceedings of ANCS, pp. 93–102 (2006)
Sidhu, R., Prasanna, V.K.: Fast Regular Expression Matching Using FPGAs. In: Proceedings of FCCM, pp. 227–238 (2001)
Smith, R., Estan, C., Jha, S., Siahaan, I.: Fast Signature Matching Using Extended Finite Automaton (XFA). In: Sekar, R., Pujari, A.K. (eds.) ICISS 2008. LNCS, vol. 5352, pp. 158–172. Springer, Heidelberg (2008)
Becchi, M., Crowley, P.: Efficient regular expression evaluation: theory to practice. In: Proceedings of ANCS, pp. 50–59 (2008)
Becchi, M., Crowley, P.: A hybrid finite automaton for practical deep packet inspection. In: Proceedings of CoNEXT, pp. 1–12 (2007)
Luchaup, D., Smith, R., Estan, C., Jha, S.: Multi-byte regular expression matching with speculation. In: Proceedings of RAID (2009)
Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation, 3rd edn. Pearson Addison-Wesley, Upper Saddle River (2007)
Hutchings, B.L., Franklin, R., Carver, D.: Assisting network intrusion detection with reconfigurable hardware. In: Proceedings of FCCM, Washington, DC, USA, p. 111. IEEE Computer Society, Los Alamitos (2002)
Lin, C.H., Huang, C.T., Jiang, C.P., Chang, S.C.: Optimization of pattern matching circuits for regular expression on FPGA. IEEE Trans. Very Large Scale Integr. Syst. 15(12), 1303–1310 (2007)
Lo, C.-T.D., Tai, Y.-G., Psarris, K.: Hardware implementation for network intrusion detection rules with regular expression support. In: Proceedings of SAC, pp. 1535–1539. ACM, New York (2008)
Smith, R., Estan, C., Jha, S., Kong, S.: Deflating the big bang: fast and scalable deep packet inspection with extended finite automata. SIGCOMM Comput. Commun. Rev. 38(4), 207–218 (2008)
Kumar, S., Chandrasekaran, B., Turner, J., Varghese, G.: Curing regular expressions matching algorithms from insomnia, amnesia, and acalculia. In: Proceedings of ANCS, pp. 155–164. ACM, New York (2007)
Smith, R., Estan, C., Jha, S.: Xfa: Faster signature matching with extended automata. In: Proceedings of IEEE S& P, Washington, DC, USA, pp. 187–201. IEEE Computer Society, Los Alamitos (2008)
Becchi, M., Cadambi, S.: Memory-efficient regular expression search using state merging. In: Proceedings of IEEE Infocom, Anchorage, AK. ACM, New York (May 2007)
Kumar, S., Dharmapurikar, S., Yu, F., Crowley, P., Turner, J.: Algorithms to accelerate multiple regular expressions matching for deep packet inspection. In: Proceedings of SIGCOMM, pp. 339–350. ACM, New York (2006)
Yu, F., Chen, Z., Diao, Y., Lakshman, T.V., Katz, R.H.: Fast and memory-efficient regular expression matching for deep packet inspection. In: Proceedings of ANCS, pp. 93–102. ACM, New York (2006)
Sommer, R., Paxson, V.: Enhancing byte-level network intrusion detection signatures with context. In: Proceedings of CCS, pp. 262–271 (2003)
Green, T.J., Miklau, G., Onizuka, M., Suciu, D.: Processing XML streams with deterministic automata. In: Proceedings of ICDT, London, UK, pp. 173–189. Springer, Heidelberg (2002)
Snort. Sourcefire Vulnerability Research Team\(^{\it TM}\) (VRT) Rules (2009), http://www.snort.org/assets/82/snort_manual.pdf
Stakhanova, N., Ghorbani, A.A.: Managing intrusion detection rule sets. In: Proceedings of EUROSEC, pp. 29–35. ACM, New York (2010)
Book, R.V., Karp, R.M., Miller, R.E., Thatcher, J.W.: Reducibility among combinatorial problems. The Journal of Symbolic Logic 40(4), 618+ (1975)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2001)
Alon, N., Awerbuch, B., Azar, Y.: The online set cover problem. In: Proceedings of STOC, pp. 100–105. ACM, New York (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Stakhanova, N., Ren, H., Ghorbani, A.A. (2011). Selective Regular Expression Matching. In: Burmester, M., Tsudik, G., Magliveras, S., Ilić, I. (eds) Information Security. ISC 2010. Lecture Notes in Computer Science, vol 6531. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-18178-8_20
Download citation
DOI: https://doi.org/10.1007/978-3-642-18178-8_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-18177-1
Online ISBN: 978-3-642-18178-8
eBook Packages: Computer ScienceComputer Science (R0)