Kennedy, Alan, Wang, Xiaojun, Liu, Zhen and Liu, Bin (2010) Ultra-high throughput string matching for deep packet inspection. In: DATE 2010 - Design, Automation and Test in Europe Conference and Exhibition, 8-12 March 2010, Dresden, Germany. ISBN 978-1-4244-7054-9
Abstract
Deep Packet Inspection (DPI) involves searching a packet's header and payload against thousands of rules to detect possible attacks. The increase in Internet usage and growing number of attacks which must be searched for has meant hardware acceleration has become essential in the prevention of DPI becoming a bottleneck to a network if used on an edge or core router. In this paper we present a new multi-pattern matching algorithm which can search for the fixed strings contained within these rules at a guaranteed rate of one character per cycle independent of the number of strings or their length. Our algorithm is based on the Aho-Corasick string matching algorithm with our modifications resulting in a memory reduction of over 98% on the strings tested from the Snort ruleset. This allows the search structures needed for matching thousands of strings to be small enough to fit in the on-chip memory of an FPGA. Combined with a simple architecture for hardware, this leads to high throughput and low power consumption. Our hardware implementation uses multiple string matching engines working in parallel to search through packets. It can achieve a throughput of over 40 Gbps (OC-768) when implemented on a Stratix 3 FPGA and over 10 Gbps (OC-192) when implemented on the lower power Cyclone 3 FPGA.
Metadata
Item Type: | Conference or Workshop Item (Paper) |
---|---|
Event Type: | Conference |
Refereed: | Yes |
Uncontrolled Keywords: | field programmable gate arrays; string matching; |
Subjects: | Engineering > Telecommunication |
DCU Faculties and Centres: | DCU Faculties and Schools > Faculty of Engineering and Computing > School of Electronic Engineering |
Published in: | Proceedings of DATE 2010 - Design, Automation and Test in Europe Conference and Exhibition. . ISBN 978-1-4244-7054-9 |
Official URL: | http://www.date-conference.com/proceedings/PAPERS/... |
Copyright Information: | ©2010 EDAA |
Use License: | This item is licensed under a Creative Commons Attribution-NonCommercial-Share Alike 3.0 License. View License |
ID Code: | 15544 |
Deposited On: | 22 Jul 2010 13:26 by DORAS Administrator . Last Modified 26 May 2022 13:21 |
Documents
Full text available as:
Preview |
PDF
- Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
715kB |
Metrics
Altmetric Badge
Dimensions Badge
Downloads
Downloads
Downloads per month over past year
Archive Staff Only: edit this record