Search: onr:"swepub:oai:research.chalmers.se:fb30fd03-2f04-4868-8f63-30d921ca6642" >
Multiple Pattern Ma...
Multiple Pattern Matching for Network Security Applications: Acceleration through Vectorization
-
- Stylianopoulos, Charalampos, 1991 (author)
- Chalmers tekniska högskola,Chalmers University of Technology
-
- Almgren, Magnus, 1972 (author)
- Chalmers tekniska högskola,Chalmers University of Technology
-
- Landsiedel, Olaf, 1979 (author)
- Chalmers tekniska högskola,Chalmers University of Technology
-
show more...
-
- Papatriantafilou, Marina, 1966 (author)
- Chalmers tekniska högskola,Chalmers University of Technology
-
show less...
-
(creator_code:org_t)
- 2017
- 2017
- English.
-
In: 46th International Conference on Parallel Processing, ICPP 2017. - 9781538610428 ; , s. 472-482
- Related links:
-
https://research.cha... (primary) (free)
-
show more...
-
https://doi.org/10.1...
-
https://research.cha...
-
show less...
Abstract
Subject headings
Close
- Pattern matching is a key building block of Intrusion Detection Systems and firewalls, which are deployed nowadays on commodity systems from laptops to massive web servers in the cloud. In fact, pattern matching is one of their most computationally intensive parts and a bottleneck to their performance. In Network Intrusion Detection, for example, pattern matching algorithms handle thousands of patterns and contribute to more than 70% of the total running time of the system.In this paper, we introduce efficient algorithmic designs for multiple pattern matching which (a) ensure cache locality and (b) utilize modern SIMD instructions. We first identify properties of pattern matching that make it fit for vectorization and show how to use them in the algorithmic design. Second, we build on an earlier, cache-aware algorithmic design and we show how cache-locality combined with SIMD gather instructions, introduced in 2013 to Intel's family of processors, can be applied to pattern matching. We evaluate our algorithmic design with open data sets of real-world network traffic:Our results on two different platforms, Haswell and Xeon-Phi, show a speedup of 1.8x and 3.6x, respectively, over Direct Filter Classification (DFC), a recently proposed algorithm by Choi et al. for pattern matching exploiting cache locality, and a speedup of more than 2.3x over Aho-Corasick, a widely used algorithm in today's Intrusion Detection Systems.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datorteknik (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Engineering (hsv//eng)
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
- TEKNIK OCH TEKNOLOGIER -- Elektroteknik och elektronik -- Datorsystem (hsv//swe)
- ENGINEERING AND TECHNOLOGY -- Electrical Engineering, Electronic Engineering, Information Engineering -- Computer Systems (hsv//eng)
Keyword
- Hardware
- Pattern matching
- Data structures
- Algorithm design and analysis
- vectors
- SIMD instructions
- network security applications
- intrusion detection systems
- pattern matching
- Registers
- SIMD vectorization
- gather
- cache locality
- cache-aware algorithmic design
- Intrusion detection
- vectorization
- cache storage
- Program processors
- firewalls
Publication and Content Type
- kon (subject category)
- ref (subject category)
Find in a library
To the university's database