Generalized aho-corasick algorithm for signature based anti-virus applications

Tsern-Huei Lee*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

19 Scopus citations

Abstract

Because of its accuracy, signature matching is considered an important technique in anti-virus/worm applications. Among some famous pattern matching algorithms, the Aho-Corasick (AC) algorithm can match multiple patterns simultaneously and guarantee deterministic performance under all circumstances and thus is widely adopted in various systems, especially when worst-case performance such as wire speed requirement is a design factor. However, the AC algorithm was developed only for strings while virus/worm signatures could be specified by simple regular expressions. In this paper, we generalize the AC algorithm to systematically construct a finite state pattern matching machine which can indicate the ending position in a finite input string for the first occurrence of virus/worm signatures that are specified by strings or simple regular expressions. The regular expressions studied in this paper may contain the following operators: * (match any number of symbols), ? (match any symbol), and {min, max} (match minimum of min, maximum of max symbols), which are defined in ClamAV, a popular open source anti-virus/worm software module, for signature specification.

Original languageEnglish
Title of host publicationProceedings of 16th International Conference on Computer Communications and Networks 2007, ICCCN 2007
Pages792-797
Number of pages6
DOIs
StatePublished - 1 Dec 2007
Event16th International Conference on Computer Communications and Networks 2007, ICCCN 2007 - Honolulu, HI, United States
Duration: 13 Aug 200716 Aug 2007

Publication series

NameProceedings - International Conference on Computer Communications and Networks, ICCCN
ISSN (Print)1095-2055

Conference

Conference16th International Conference on Computer Communications and Networks 2007, ICCCN 2007
CountryUnited States
CityHonolulu, HI,
Period13/08/0716/08/07

Fingerprint Dive into the research topics of 'Generalized aho-corasick algorithm for signature based anti-virus applications'. Together they form a unique fingerprint.

  • Cite this

    Lee, T-H. (2007). Generalized aho-corasick algorithm for signature based anti-virus applications. In Proceedings of 16th International Conference on Computer Communications and Networks 2007, ICCCN 2007 (pp. 792-797). [4317914] (Proceedings - International Conference on Computer Communications and Networks, ICCCN). https://doi.org/10.1109/ICCCN.2007.4317914