PERG: A scalable pattern-matching accelerator

TitlePERG: A scalable pattern-matching accelerator
Publication TypeConference Paper
Year of Publication2008
AuthorsHo, J., and G. Lemieux
Conference NameMicrosystems and Nanoelectronics Research Conference, 2008. MNRC 2008. 1st
Pagination29 -32
Date Publishedoct.
KeywordsBloomier filters, ClamAV antivirus database, computer virus signatures, computer viruses, false positives, field programmable gate arrays, filters, FPGA, network intrusion detection systems, pattern matching, PERG, scalable pattern-matching accelerator

PERG is an FPGA application for accelerating detection of computer virus signatures (patterns). A pattern consists of a sequence of one or more segments separated by gaps of fixed lengths. PERG preprocesses a database of these patterns into hardware. To our knowledge, PERG is the first pattern matching hardware targeting viruses, as well as the first among network intrusion detection systems (NIDS), which are similar in nature to PERG, to implement Bloomier filters. This makes guarding against false positives faster than traditional Bloom filters because verification requires checking against one pattern instead of several patterns. Using the ClamAV antivirus database, PERG fits 80,282 patterns containing over 8,224,848 characters into one modest FPGA chip with a small (4 MB) off-chip memory. The architecture achieves roughly 26x improved density (characters per memory bit) compared to the next-best NIDS pattern-matching engine which fits only 1/250th the characters. With an estimated throughput of about 200MB/s, PERG keeps up with most network or disk interfaces.


a place of mind, The University of British Columbia

Electrical and Computer Engineering
2332 Main Mall
Vancouver, BC Canada V6T 1Z4
Tel +1.604.822.2872
Fax +1.604.822.5949

Emergency Procedures | Accessibility | Contact UBC | © Copyright 2021 The University of British Columbia