research-article

Regular Expression Matching with Memristor TCAMs for Network Security

Authors:

Catherine E. Graves,

Brent Buchanan,

Sai Rahul Chalamalasetti,

John Paul Strachan,

Matthew P. HardyAuthors Info & Claims

NANOARCH '18: Proceedings of the 14th IEEE/ACM International Symposium on Nanoscale Architectures

Pages 65 - 71

https://doi.org/10.1145/3232195.3232201

Published: 17 July 2018 Publication History

Abstract

We propose using memristor-based TCAMs (Ternary Content Addressable Memory) to accelerate Regular Expression (RegEx) matching. RegEx matching is a key function in network security, where deep packet inspection finds and filters out malicious actors. However, RegEx matching latency and power can be incredibly high and current proposals are challenged to perform wire-speed matching for large scale rulesets. Our approach dramatically decreases RegEx matching operating power, provides high throughput, and the use of mTCAMs enables novel compression techniques to expand ruleset sizes and allows future exploitation of the multi-state (analog) capabilities of memristors. We fabricated and demonstrated nanoscale memristor TCAM cells. SPICE simulations investigate mTCAM performance at scale and a mTCAM power model at 22nm demonstrates 0.2 fJ/bit/search energy for a 36x400 mTCAM. We further propose a tiled architecture which implements a Snort ruleset and assess the application performance. Compared to a state-of-the-art FPGA approach (2 Gbps,~1W), we show x4 throughput (8 Gbps) at 60% the power (0.62W) before applying standard TCAM power-saving techniques. Our performance comparison improves further when striding (searching multiple characters) is considered, resulting in 47.2 Gbps at 1.3W for our approach compared to 3.9 Gbps at 630mW for the strided FPGA NFA, demonstrating a promising path to wire-speed RegEx matching on large scale rulesets.

References

[1]

Banit Agrawal and Timothy Sherwood. 2006. Modeling TCAM power for next generation network devices. In Performance Analysis of Systems and Software, 2006 IEEE International Symposium on. IEEE, 120--129.

[2]

Meng-Fan Chang, Chien-Chen Lin, Albert Lee, Chia-Chen Kuo, Geng-Hau Yang, Hsiang-Jen Tsai, Tien-Fu Chen, Shyh-Shyuan Sheu, Pei-Ling Tseng, Heng-Yuan Lee, et al. 2015. 17.5 A 3T1R nonvolatile TCAM using MLC ReRAM with sub-1ns search time. In Solid-State Circuits Conference-(ISSCC), 2015 IEEE International. IEEE, 1--3.

[3]

Xinming Chen, Brandon Jones, Michela Becchi, and Tilman Wolf. 2016. Picking pesky parameters: Optimizing regular expression matching in practice. IEEE Transactions on Parallel and Distributed Systems 27, 5 (2016), 1430--1442.

Digital Library

[4]

Paul Dlugosch, Dave Brown, Paul Glendenning, Michael Leventhal, and Harold Noyes. 2014. An efficient and scalable semiconductor architecture for parallel automata processing. IEEE Transactions on Parallel and Distributed Systems 25, 12 (2014), 3088--3098.

[5]

John E Hopcroft. 2008. Introduction to automata theory, languages, and computation. Pearson Education India.

Digital Library

[6]

Kun Huang, Linxuan Ding, Gaogang Xie, Dafang Zhang, Alex X Liu, and Kave Salamatian. 2013. Scalable TCAM-based regular expression matching with compressed finite automata. In Proceedings of the ninth ACM/IEEE symposium on Architectures for networking and communications systems. IEEE Press, 83--94.

Digital Library

[7]

Po-Tsang Huang and Wei Hwang. 2011. A 65 nm 0.165 fJ/Bit/Search 256\,\times\, 144 TCAM Macro Design for IPv6 Lookup Tables. IEEE Journal of Solid-State Circuits 46, 2 (2011), 507--519.

[8]

Snort intrusion detection system. 2018. (2018). Retrieved March 29 from http://www.snort.org/

[9]

Pilin Junsangsri, Fabrizio Lombardi, and Jie Han. 2014. A memristor-based tcam (ternary content addressable memory) cell. In Proceedings of the 2014 IEEE/ACM International Symposium on Nanoscale Architectures. ACM, 1--6.

Digital Library

[10]

Jing Li, Robert Montoye, Masatoshi Ishii, Kevin Stawiasz, Takeshi Nishida, Kim Maloney, Gary Ditlow, Scott Lewis, Tom Maffitt, Richard Jordan, et al. 2013. 1Mb 0.41 μm 2 2T-2R cell nonvolatile TCAM with two-bit encoding and clocked self-referenced sensing. In VLSI Circuits (VLSIC), 2013 Symposium on. IEEE, C104--C105.

[11]

Chad R Meiners, Jignesh Patel, Eric Norige, Eric Torng, and Alex X Liu. 2010. Fast regular expression matching using small TCAMs for network intrusion detection and prevention systems. In Proceedings of the 19th USENIX conference on Security. USENIX Association, 8--8.

Digital Library

[12]

Emmanuelle J Merced-Grafals, Noraica Dávila, Ning Ge, R Stanley Williams, and John Paul Strachan. 2016. Repeatable, accurate, and high speed multi-level programming of memristor 1T1R arrays for power efficient analog computing applications. Nanotechnology 27, 36 (2016), 365202.

[13]

Nitin Mohan, Wilson Fung, Derek Wright, and Manoj Sachdev. 2006. Design techniques and test methodology for low-power TCAMs. IEEE Transactions on Very Large Scale Integration (VLSI) Systems 14, 6 (2006), 573--586.

Digital Library

[14]

Naveen Muralimanohar, Rajeev Balasubramonian, and Norman P Jouppi. 2009. CACTI 6.0: A tool to model large caches. HP laboratories (2009), 22--31.

[15]

Koji Nii, Teruhiko Amano, Naoya Watanabe, Minoru Yamawaki, Kenji Yoshinaga, Mihoko Wada, and Isamu Hayashi. 2014. 13.6 A 28nm 400MHz 4-parallel 1.6 Gsearch/s 80Mb ternary CAM. In Solid-State Circuits Conference Digest of Technical Papers (ISSCC), 2014 IEEE International. IEEE, 240--241.

[16]

Kunyang Peng, Siyuan Tang, Min Chen, and Qunfeng Dong. 2011. Chain-based DFA deflation for fast and scalable regular expression matching using TCAM. In Proceedings of the 2011 ACM/IEEE Seventh Symposium on Architectures for Networking and Communications Systems. IEEE Computer Society, 24--35.

Digital Library

[17]

Deepak S Vijayasarathi, Mehrdad Nourani, Mohammad J Akhbarizadeh, and Poras T Balsara. 2005. Ripple-precharge TCAM: A low-power solution for network search engines. In Computer Design: VLSI in Computers and Processors, 2005. ICCD 2005. Proceedings. 2005 IEEE International Conference on. IEEE, 243--248.

Digital Library

[18]

Chengcheng Xu, Shuhui Chen, Jinshu Su, SM Yiu, and Lucas CK Hui. 2016. A survey on regular expression matching for deep packet inspection: Applications, algorithms, and hardware platforms. IEEE Communications Surveys & Tutorials 18, 4 (2016), 2991--3029.

Digital Library

[19]

Jinmin Yang, Jie Yang, Kun Huang, Huigui Rong, and Kin Fun Li. 2015. A compression approach to reducing power consumption of TCAMs in regular expression matching. Computer Communications 70 (2015), 86--94.

Digital Library

[20]

Fang Yu, Zhifeng Chen, Yanlei Diao, TV Lakshman, and Randy H Katz. 2006. Fast and memory-efficient regular expression matching for deep packet inspection. In Architecture for Networking and Communications systems, 2006. ANCS 2006. ACM/IEEE Symposium on. IEEE, 93--102.

Digital Library

[21]

Fang Yu, Randy H Katz, and Tirunellai V Lakshman. 2004. Gigabit rate packet pattern-matching using TCAM. In Network Protocols, 2004. ICNP 2004. Proceedings of the 12th IEEE International Conference on. IEEE, 174--183.

Digital Library

[22]

Le Zheng, Sangho Shin, and Sung-Mo Steve Kang. 2014. Memristor-based ternary content addressable memory (mTCAM) for data-intensive computing. Semiconductor Science and Technology 29, 10 (2014), 104010.

Cited By

Saleh SKoldehofe B(2023)The Future is AnalogProceedings of the 22nd ACM Workshop on Hot Topics in Networks10.1145/3626111.3628192(254-262)Online publication date: 28-Nov-2023
https://dl.acm.org/doi/10.1145/3626111.3628192
Dhull SSoni SNisar AKaushik B(2023)Energy-Efficient Differential Spin Hall Effect Ternary Content Addressable Memory2023 IEEE 23rd International Conference on Nanotechnology (NANO)10.1109/NANO58406.2023.10231186(545-549)Online publication date: 2-Jul-2023
https://doi.org/10.1109/NANO58406.2023.10231186
Saleh SGoossens ABanerjee TKoldehofe B(2022)Towards Energy Efficient Memristor-based TCAM for Match-Action Processing2022 IEEE 13th International Green and Sustainable Computing Conference (IGSC)10.1109/IGSC55832.2022.9969354(1-4)Online publication date: 24-Oct-2022
https://doi.org/10.1109/IGSC55832.2022.9969354
Show More Cited By

Index Terms

Regular Expression Matching with Memristor TCAMs for Network Security

Recommendations

Chain-Based DFA Deflation for Fast and Scalable Regular Expression Matching Using TCAM
ANCS '11: Proceedings of the 2011 ACM/IEEE Seventh Symposium on Architectures for Networking and Communications Systems

Regular expression matching is the core engine of many network functions such as intrusion detection, protocol analysis and so on. In spite of intensive research, we are still in need of a method for fast and scalable regular expression matching, where ...
Bypassing space explosion in high-speed regular expression matching

Network intrusion detection and prevention systems commonly use regular expression (RE) signatures to represent individual security threats. While the corresponding deterministic finite state automata (DFA) for any one RE is typically small, the DFA that ...
A regular expression matching circuit: Decomposed non-deterministic realization with prefix sharing and multi-character transition

This paper shows a compact realization of regular expression matching circuits on FPGAs. First, the given regular expression is converted into a non-deterministic finite automaton (NFA) by the modified McNaughton-Yamada method. Second, to reduce the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

NANOARCH '18: Proceedings of the 14th IEEE/ACM International Symposium on Nanoscale Architectures

July 2018

176 pages

ISBN:9781450358156

DOI:10.1145/3232195

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 July 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Funding Sources

Office of the Director of National Intelligence (ODNI), Intelligence Advanced Research Projects Activity

Conference

NANOARCH '18

Sponsor:

SIGDA

NANOARCH '18: IEEE/ACM International Symposium on Nanoscale Architectures

July 17 - 19, 2018

Athens, Greece

Acceptance Rates

NANOARCH '18 Paper Acceptance Rate 30 of 56 submissions, 54%;

Overall Acceptance Rate 55 of 87 submissions, 63%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
157
Total Downloads

Downloads (Last 12 months)15
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Saleh SKoldehofe B(2023)The Future is AnalogProceedings of the 22nd ACM Workshop on Hot Topics in Networks10.1145/3626111.3628192(254-262)Online publication date: 28-Nov-2023
https://dl.acm.org/doi/10.1145/3626111.3628192
Dhull SSoni SNisar AKaushik B(2023)Energy-Efficient Differential Spin Hall Effect Ternary Content Addressable Memory2023 IEEE 23rd International Conference on Nanotechnology (NANO)10.1109/NANO58406.2023.10231186(545-549)Online publication date: 2-Jul-2023
https://doi.org/10.1109/NANO58406.2023.10231186
Saleh SGoossens ABanerjee TKoldehofe B(2022)Towards Energy Efficient Memristor-based TCAM for Match-Action Processing2022 IEEE 13th International Green and Sustainable Computing Conference (IGSC)10.1109/IGSC55832.2022.9969354(1-4)Online publication date: 24-Oct-2022
https://doi.org/10.1109/IGSC55832.2022.9969354
Saleh SGoossens ABanerjee TKoldehofe B(2022) TCAmM CogniGron : Energy Efficient Memristor-Based TCAM for Match-Action Processing 2022 IEEE International Conference on Rebooting Computing (ICRC)10.1109/ICRC57508.2022.00013(89-99)Online publication date: Dec-2022
https://doi.org/10.1109/ICRC57508.2022.00013
Saleh SKoldehofe B(2022)On Memristors for Enabling Energy Efficient and Enhanced Cognitive Network FunctionsIEEE Access10.1109/ACCESS.2022.322644710(129279-129312)Online publication date: 2022
https://doi.org/10.1109/ACCESS.2022.3226447
Li CGraves CSheng XMiller DFoltin MPedretti GStrachan J(2020)Analog content-addressable memories with memristorsNature Communications10.1038/s41467-020-15254-411:1Online publication date: 2-Apr-2020
https://doi.org/10.1038/s41467-020-15254-4
Yang K(2019)Custom CMOS and Post-CMOS Crossbar Circuits for Resource-Constrained Hardware Security Primitives2019 IEEE International Electron Devices Meeting (IEDM)10.1109/IEDM19573.2019.8993473(13.7.1-13.7.4)Online publication date: Dec-2019
https://doi.org/10.1109/IEDM19573.2019.8993473
Levchenko NOkunev AZmejev D(2019)Implementation Variants of the Global Distributed Associative Computing Environment for the Parallel Dataflow Computing System “Buran”2019 IEEE East-West Design & Test Symposium (EWDTS)10.1109/EWDTS.2019.8884422(1-4)Online publication date: Sep-2019
https://doi.org/10.1109/EWDTS.2019.8884422

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents