Skip to main content

2014 | OriginalPaper | Buchkapitel

SSE Instruction and Block Predetermination-Based Automaton Optimization

verfasst von : Tianlong Yang, Hongli Zhang, Xiaolong Cao, Zhihong Tian, Mahmoud T. Qassrawi

Erschienen in: Unifying Electrical Engineering and Electronics Engineering

Verlag: Springer New York

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Techniques to decrease the memory requirements of large patterns set for an intrusion detection system (IDS), block predetermination, and block matching based on a self-balancing binary search tree (AVL) are defined in this chapter. By introducing SSE instruction, the new DFA matching system can increase matching efficiency when compared to the standard AC implementation. For illustration, a number of tests, according to different lengths or different amount of patterns were used to show how many DFA states and how much memory can be saved by the design. Empirical results show that at best an SSE-AVL-based implementation of DFA can save about 98 % of memory usage in common DFA when using randomly generated patterns. The hybrid of block DFA and common character DFA can effectively suppress memory requirements, and with the help of block predetermination with two-level-AVL filtration and SSE instruction, the matching speed performs better than standard AC under single process case.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Fußnoten
1
Block string: string with length 16.
 
2
Non-zero jump: In AC automaton matching, when the automaton reads a legal character, the destination state is an integer number larger than 0. in this chapter we name this kind of destination jump as non-zero jump.
 
Literatur
1.
Zurück zum Zitat Brumley D, Newsome J, Song D, Wang H, Jha S (2006) Towards automatic generation of vulnerability based signatures. In: Security and privacy, 2006 I.E. symposium on, IEEE. pp 15–30 Brumley D, Newsome J, Song D, Wang H, Jha S (2006) Towards automatic generation of vulnerability based signatures. In: Security and privacy, 2006 I.E. symposium on, IEEE. pp 15–30
2.
Zurück zum Zitat Rubin S, Jha S, Miller B (2005) Language-based generation and evaluation of NIDS signatures. In: Security and privacy, 2005 I.E. symposium on, IEEE. pp 3–17 Rubin S, Jha S, Miller B (2005) Language-based generation and evaluation of NIDS signatures. In: Security and privacy, 2005 I.E. symposium on, IEEE. pp 3–17
3.
Zurück zum Zitat Sommer R, Paxson V (2003) Enhancing byte-level network intrusion detection signatures with context. In: Proceedings of the 10th ACM conference on computer and communications security, ACM. pp 262–271 Sommer R, Paxson V (2003) Enhancing byte-level network intrusion detection signatures with context. In: Proceedings of the 10th ACM conference on computer and communications security, ACM. pp 262–271
4.
Zurück zum Zitat Wang H, Guo C, Simon D, Zugenmaier A (2004) Shield: vulnerability-driven network filters for preventing known vulnerability exploits. In: ACM SIGCOMM computer communication review, ACM, vol 34. pp 193–204 Wang H, Guo C, Simon D, Zugenmaier A (2004) Shield: vulnerability-driven network filters for preventing known vulnerability exploits. In: ACM SIGCOMM computer communication review, ACM, vol 34. pp 193–204
5.
Zurück zum Zitat Yegneswaran V, Giffin J, Barford P, Jha S (2005) An architecture for generating semantics-aware signatures. In: Proceedings of the 14th conference on USENIX security symposium-volume 14, USENIX association. pp 7–7 Yegneswaran V, Giffin J, Barford P, Jha S (2005) An architecture for generating semantics-aware signatures. In: Proceedings of the 14th conference on USENIX security symposium-volume 14, USENIX association. pp 7–7
6.
Zurück zum Zitat Yang L, Karim R, Ganapathy V, Smith R (2011) Improving NFA-based signature matching using ordered binary decision diagrams. In: Recent advances in intrusion detection. Springer, pp 58–78 Yang L, Karim R, Ganapathy V, Smith R (2011) Improving NFA-based signature matching using ordered binary decision diagrams. In: Recent advances in intrusion detection. Springer, pp 58–78
7.
Zurück zum Zitat Song T, Wang D (2009) A path combinational method for multiple pattern matching. In: Proceedings of the 5th ACM/IEEE symposium on architectures for networking and communications systems, ACM. pp 76–77 Song T, Wang D (2009) A path combinational method for multiple pattern matching. In: Proceedings of the 5th ACM/IEEE symposium on architectures for networking and communications systems, ACM. pp 76–77
8.
Zurück zum Zitat Piyachon P, Luo Y (2006) Efficient memory utilization on network processors for deep packet inspection. In: Proceedings of the 2006 ACM/IEEE symposium on architecture for networking and communications systems, ACM. pp 71–80 Piyachon P, Luo Y (2006) Efficient memory utilization on network processors for deep packet inspection. In: Proceedings of the 2006 ACM/IEEE symposium on architecture for networking and communications systems, ACM. pp 71–80
9.
Zurück zum Zitat Dharmapurikar S, Lockwood J (2005) Fast and scalable pattern matching for content filtering. In: Architecture for networking and communications systems, 2005. ANCS 2005. Symposium on, IEEE. pp 183–192 Dharmapurikar S, Lockwood J (2005) Fast and scalable pattern matching for content filtering. In: Architecture for networking and communications systems, 2005. ANCS 2005. Symposium on, IEEE. pp 183–192
13.
Zurück zum Zitat Wu S, Manber U (1994) A fast algorithm for multi-pattern searching. Tech. rep., Technical Report TR-94-17, University of Arizona Wu S, Manber U (1994) A fast algorithm for multi-pattern searching. Tech. rep., Technical Report TR-94-17, University of Arizona
14.
Zurück zum Zitat Allauzen C, Raffinot M (1999) Oracle des facteurs dun ensemble de mots. Tech. rep., Technical Report 99–11, Institut Gaspard-Monge, Université de Marne-la-Vallée Allauzen C, Raffinot M (1999) Oracle des facteurs dun ensemble de mots. Tech. rep., Technical Report 99–11, Institut Gaspard-Monge, Université de Marne-la-Vallée
15.
Zurück zum Zitat Morris J, Pratt V. A linear pattern-matching algorithm. Computing Center Morris J, Pratt V. A linear pattern-matching algorithm. Computing Center
16.
Zurück zum Zitat Boyer R, Moore J (1977) A fast string searching algorithm. Commun ACM 20(10):762–772MATHCrossRef Boyer R, Moore J (1977) A fast string searching algorithm. Commun ACM 20(10):762–772MATHCrossRef
17.
Zurück zum Zitat Jacob N, Brodley C (2006) Offloading IDS computation to the GPU. In: Computer security applications conference, 2006. ACSAC ‘06. 22nd Annual, IEEE. pp 371–380 Jacob N, Brodley C (2006) Offloading IDS computation to the GPU. In: Computer security applications conference, 2006. ACSAC ‘06. 22nd Annual, IEEE. pp 371–380
18.
Zurück zum Zitat Kouzinopoulos C, Margaritis K (2009) String matching on a multicore GPU using CUDA. In: Informatics, 2009. PCI ‘09. Thirteenth Panhellenic conference on, IEEE. pp 14–18 Kouzinopoulos C, Margaritis K (2009) String matching on a multicore GPU using CUDA. In: Informatics, 2009. PCI ‘09. Thirteenth Panhellenic conference on, IEEE. pp 14–18
19.
Zurück zum Zitat Peng J, Chen H (2010) CUgrep: a GPU-based high performance multi-string matching system. In: Future computer and communication (ICFCC), 2010 2nd International Conference on, IEEE, vol 1. pp 77–81 Peng J, Chen H (2010) CUgrep: a GPU-based high performance multi-string matching system. In: Future computer and communication (ICFCC), 2010 2nd International Conference on, IEEE, vol 1. pp 77–81
20.
Zurück zum Zitat Mu S, Zhang X, Zhang N, Lu J, Deng Y, Zhang S (2010) Ip routing processing with graphic processors. In: Proceedings of the conference on design, automation and test in Europe. European Design and Automation Association, pp 93–98 Mu S, Zhang X, Zhang N, Lu J, Deng Y, Zhang S (2010) Ip routing processing with graphic processors. In: Proceedings of the conference on design, automation and test in Europe. European Design and Automation Association, pp 93–98
21.
Zurück zum Zitat Peng J, Chen H, Shi S (2010) The GPU-based string matching system in advanced ac algorithm. In: Computer and information technology (CIT), 2010 I.E. 10th international conference on, IEEE. pp 1158–1163 Peng J, Chen H, Shi S (2010) The GPU-based string matching system in advanced ac algorithm. In: Computer and information technology (CIT), 2010 I.E. 10th international conference on, IEEE. pp 1158–1163
22.
Zurück zum Zitat Smith R, Estan C, Jha S (2008) XFA: faster signature matching with extended automata. In: Security and privacy, 2008. SP 2008. IEEE symposium on, IEEE. pp 187–201 Smith R, Estan C, Jha S (2008) XFA: faster signature matching with extended automata. In: Security and privacy, 2008. SP 2008. IEEE symposium on, IEEE. pp 187–201
23.
Zurück zum Zitat Kumar S, Dharmapurikar S, Yu F, Crowley P, Turner J (2006) Algorithms to accelerate multiple regular expressions matching for deep packet inspection. ACM SIGCOMM Comput Commun Rev 36(4):339–350CrossRef Kumar S, Dharmapurikar S, Yu F, Crowley P, Turner J (2006) Algorithms to accelerate multiple regular expressions matching for deep packet inspection. ACM SIGCOMM Comput Commun Rev 36(4):339–350CrossRef
24.
Zurück zum Zitat Clark C, Schimmel D (2004) Scalable pattern matching for high speed networks. In: Field-programmable custom computing machines, 2004. FCCM 2004. Twelfth annual IEEE symposium on, IEEE. pp 249–257 Clark C, Schimmel D (2004) Scalable pattern matching for high speed networks. In: Field-programmable custom computing machines, 2004. FCCM 2004. Twelfth annual IEEE symposium on, IEEE. pp 249–257
25.
Zurück zum Zitat Hopcroft J, Motwani R, Ullman J (2007) Introduction to automata theory, languages, and computation. Addison-Wesley, America Hopcroft J, Motwani R, Ullman J (2007) Introduction to automata theory, languages, and computation. Addison-Wesley, America
26.
Zurück zum Zitat Sidhu R, Prasanna V (2001) Fast regular expression matching using FPGAS. In: Field-programmable custom computing machines, 2001. FCCM ‘01. The 9th annual IEEE symposium on, IEEE. pp 227–238 Sidhu R, Prasanna V (2001) Fast regular expression matching using FPGAS. In: Field-programmable custom computing machines, 2001. FCCM ‘01. The 9th annual IEEE symposium on, IEEE. pp 227–238
Metadaten
Titel
SSE Instruction and Block Predetermination-Based Automaton Optimization
verfasst von
Tianlong Yang
Hongli Zhang
Xiaolong Cao
Zhihong Tian
Mahmoud T. Qassrawi
Copyright-Jahr
2014
Verlag
Springer New York
DOI
https://doi.org/10.1007/978-1-4614-4981-2_244

Neuer Inhalt