Memristor TCAMs Accelerate Regular Expression Matching for Network Intrusion Detection
Authors:
- Catherine E. GravesCGCatherine E. Graves
- Si-Ty LamSLSi-Ty Lam
- Xuema LiXLXuema Li
- Lennie KiyamaLKLennie Kiyama
- Martin FoltinMFMartin Foltin
- Matthew P. HardyMHMatthew P. Hardy
- John Paul StrachanJSJohn Paul Strachan
- Can LiCLCan Li
- Xia ShengXSXia Sheng
- Wen MaWMWen Ma
- Sai Rahul ChalamalasettiSCSai Rahul Chalamalasetti
- Darrin MillerDMDarrin Miller
- 26 August 2019
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Nanotechnology
- Vol. 18 (1536125X) , 963-970
Abstract
We propose memristor-based TCAMs (Ternary Content Addressable Memory) circuits to accelerate Regular Expression (RegEx) matching through in memory processing of finite automata. RegEx matching is a key function in network security to find malicious actors. However, RegEx matching latency and power can be incredibly high and current proposals are challenged to perform wire-speed matching for large rulesets. Our approach dramatically decreases operating power, enables high throughput, and the use of nanoscale memristor TCAM circuits (mTCAMs) enables compression techniques to expand rulesets. We fabricated and demonstrated nanoscale memristor TCAM cells. SPICE simulations investigate performance at scale and a mTCAM dynamic power model using 16nm layout parameters demonstrates ~0.2 fJ/bit/search energy for a 36 × 250 mTCAM array. A tiled architecture is proposed to implement a Snort ruleset and assess application performance. Compared to a state-of-the-art FPGA approach (2 Gbps, ~1W), we show × 4 throughput (8 Gbps) at 55% the power (0.55W) without standard TCAM power-saving techniques. Our performance comparison improves further when striding (searching multiple characters at once) is considered, resulting in 47.2 Gbps at 1.2W for our approach compared to 3.9 Gbps at 630mW for strided FPGA NFA, demonstrating a promising path to wire-speed RegEx matching on large scale rulesets.Keywords
Funding Information
- Office of the Director of National Intelligence
- Intelligence Advanced Research Projects Activity (2017-17013000002)
This publication has 21 references indexed in Scilit:
- Repeatable, accurate, and high speed multi-level programming of memristor 1T1R arrays for power efficient analog computing applicationsNanotechnology, 2016
- A Survey on Regular Expression Matching for Deep Packet Inspection: Applications, Algorithms, and Hardware PlatformsIEEE Communications Surveys & Tutorials, 2016
- A compression approach to reducing power consumption of TCAMs in regular expression matchingComputer Communications, 2015
- Picking Pesky Parameters: Optimizing Regular Expression Matching in PracticeIEEE Transactions on Parallel and Distributed Systems, 2015
- Memristor-based ternary content addressable memory (mTCAM) for data-intensive computingSemiconductor Science and Technology, 2014
- Chain-Based DFA Deflation for Fast and Scalable Regular Expression Matching Using TCAM2011
- Fast and memory-efficient regular expression matching for deep packet inspection2006
- Ripple-precharge TCAM: a low-power solution for network search engines2006
- Modeling TCAM power for next generation network devices2006
- Network Applications of Bloom Filters: A SurveyInternet Mathematics, 2004