NDLI: Realizing a Sub-Linear Time String-Matching Algorithm With a Hardware Accelerator Using Bloom Filters

Content Provider	IEEE Xplore Digital Library
Author	Po-Ching Lin Yin-Dar Lin Yuan-Cheng Lai Yi-Jun Zheng Tsern-Huei Lee
Copyright Year	1993
Abstract	Many network security applications rely on string matching to detect intrusions, viruses, spam, and so on. Since software implementation may not keep pace with the high-speed demand, turning to hardware-based solutions becomes promising. This work presents an innovative architecture to realize string matching in sub-linear time based on algorithmic heuristics, which come from parallel queries to a set of space-efficient Bloom filters. The algorithm allows skipping characters not in a match in the text, and in turn simultaneously inspect multiple characters in effect. The techniques to reduce the impact of certain bad situations on performance are also proposed: the bad-block heuristic, a linear worst-case time method and a non-blocking interface to hand over the verification job to a verification module. This architecture is simulated with both behavior simulation in C and timing simulation in HDL for antivirus applications. The simulation shows that the throughput of scanning Windows executable files for more than 10000 virus signatures can achieve 5.64 Gb/s, while the worst-case performance is 1.2 Gb/s if the signatures are properly specified.
Sponsorship	IEEE Computer Society Association for Computing Machinery (ACM)/SIGDA IEEE Computer Society Technical Committee on Design Automation
Starting Page	1008
Ending Page	1020
Page Count	13
File Size	1263803
File Format	PDF
ISSN	10638210
Volume Number	17
Issue Number	8
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2009-08-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Application software Intrusion detection Computer viruses Turning Computer architecture Heuristic algorithms Matched filters Timing Hardware design languages Throughput string matching Algorithms field-programmable gate arrays (FPGAs)
Content Type	Text
Resource Type	Article
Subject	Electrical and Electronic Engineering Software Hardware and Architecture

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A computationally efficient engine for flexible intrusion detection

A temporal bipartitioning algorithm for dynamically reconfigurable FPGAs

Stochastic Physical Synthesis Considering Prerouting Interconnect Uncertainty and Process Variation for FPGAs

Reconfigurable Accelerator for the Word-Matching Stage of BLASTN

ZyCAP: Efficient Partial Reconfiguration Management on the Xilinx Zynq

Achieving Programming Model Abstractions for Reconfigurable Computing

Mapping of generalized template matching onto reconfigurable computers

Traffic-Aware Design of a High-Speed FPGA Network Intrusion Detection System

ATOMi: an algorithm for circuit partitioning into multiple FPGAs using time-multiplexed, off-chip, multicasting interconnection architecture

Realizing a Sub-Linear Time String-Matching Algorithm With a Hardware Accelerator Using Bloom Filters

Similar Documents

A computationally efficient engine for flexible intrusion detection

A temporal bipartitioning algorithm for dynamically reconfigurable FPGAs

Stochastic Physical Synthesis Considering Prerouting Interconnect Uncertainty and Process Variation for FPGAs

Reconfigurable Accelerator for the Word-Matching Stage of BLASTN

ZyCAP: Efficient Partial Reconfiguration Management on the Xilinx Zynq

Achieving Programming Model Abstractions for Reconfigurable Computing

Mapping of generalized template matching onto reconfigurable computers

Traffic-Aware Design of a High-Speed FPGA Network Intrusion Detection System

ATOMi: an algorithm for circuit partitioning into multiple FPGAs using time-multiplexed, off-chip, multicasting interconnection architecture

Realizing a Sub-Linear Time String-Matching Algorithm With a Hardware Accelerator Using Bloom Filters