Browse DORAS
Browse Theses
Latest Additions
Creative Commons License
Except where otherwise noted, content on this site is licensed for use under a:

Extraction of fingerprint from regular expression for efficient prefiltering

Wang, Xiaofei and Jiang, Junchen and Lin, Wei and Tang, Yi and Wang, Xiaojun and Liu, Bin (2009) Extraction of fingerprint from regular expression for efficient prefiltering. In: ICCTA 2009 - International Conference on Communications Technology and Applications, 16-18 October 2009 , Beijing, China. ISBN 978-1-4244-4816-6

Full text available as:

PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader


Deep packet inspection at high speed has become extremely important due to its application in a wide range of network applications, such as network security and network monitoring. Network intrusion detection system (NIDS) uses a collection of signatures of known security threats and viruses to scan the payload of each packet. Signatures are often specified in the form of regular expressions (regex), called patterns, which are traditionally implemented as finite automata. Deterministic finite automata (DFA) is fast, but requires prohibitive amounts of memory which limits their practical use. Instead of matching an incoming packet with each individual regex in a ruleset, we match the packet with a fixed substring, called fingerprint, of a regex first. Fixed string matching is faster and consumes less energy than regex matching. The fact is that if a packet does not match with the fingerprint of a regex, it will not match the regex itself. So fingerprints can be used in a prefilter engine to filter out those packets and do not match any of the fingerprints of the regex in a rule set, which represents normal non-malicious traffic. This actually reduces the number of regex rules being matched, which results in increased throughput of the NIDS. We present a weight scheme to extract a good fingerprint from a regex. A good fingerprint is the one that not only indicates the regex uniquely, but also occurs as less as possible in the matching procedure. We demonstrate how to use fingerprints for efficient prefiltering by means of Bloom filters in practice.

Item Type:Conference or Workshop Item (Paper)
Event Type:Conference
Uncontrolled Keywords:computer viruses; digital signatures; feature extraction; filtering theory; fingerprint identification; finite automata; string matching;
Subjects:Engineering > Electronic engineering
DCU Faculties and Centres:DCU Faculties and Schools > Faculty of Engineering and Computing > School of Electronic Engineering
Published in:2009 IEEE International Conference on Communications Technology and Applications. . Institute of Electrical and Electronics Engineers. ISBN 978-1-4244-4816-6
Publisher:Institute of Electrical and Electronics Engineers
Official URL:
Copyright Information:©2009 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
Funders:Enterprise Ireland
ID Code:15528
Deposited On:20 Jul 2010 16:14 by DORAS Administrator. Last Modified 20 Jul 2010 16:14

Download statistics

Archive Staff Only: edit this record