Gigabit Rate Packet Pattern-Matching Using TCAM

Fang Yu, Randy H. Katz and T. V. Lakshman

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-04-1341
July 2004

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2004/CSD-04-1341.pdf

In today's Internet, worms and viruses cause service disruptions with enormous economic impact. Current attack prevention mechanisms rely on end-user cooperation to install new system patches or upgrade security software, yielding slow reaction time. However, malicious attacks spread much faster than users can respond, making effective attack prevention difficult. Network-based mechanisms, by avoiding end-user coordination, can respond rapidly to new attacks. Such mechanisms require the network to inspect the packet payload at line rates to detect and filter those packets containing worm signatures. These signature sets are large (e.g., thousands) and complex. Software-only implementations are unlikely to meet the performance goals. Therefore, making a network-based scheme practical requires efficient algorithms suitable for hardware implementations. This paper develops a Ternary Content Addressable Memory (TCAM) based multiple-pattern matching scheme. The scheme can handle complex patterns, such as arbitrarily long patterns, correlated patterns, and patterns with negation. For the ClamAv virus database with 1768 patterns whose sizes vary from 6 bytes to 2189 bytes, the proposed scheme can operate at a 2 Gbps rate with a 240KB TCAM.


BibTeX citation:

@techreport{Yu:CSD-04-1341,
    Author = {Yu, Fang and Katz, Randy H. and Lakshman, T. V.},
    Title = {Gigabit Rate Packet Pattern-Matching Using TCAM},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2004},
    Month = {Jul},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2004/5467.html},
    Number = {UCB/CSD-04-1341},
    Abstract = {In today's Internet, worms and viruses cause service disruptions with enormous economic impact. Current attack prevention mechanisms rely on end-user cooperation to install new system patches or upgrade security software, yielding slow reaction time. However, malicious attacks spread much faster than users can respond, making effective attack prevention difficult. Network-based mechanisms, by avoiding end-user coordination, can respond rapidly to new attacks. Such mechanisms require the network to inspect the packet payload at line rates to detect and filter those packets containing worm signatures. These signature sets are large (e.g., thousands) and complex. Software-only implementations are unlikely to meet the performance goals. Therefore, making a network-based scheme practical requires efficient algorithms suitable for hardware implementations. This paper develops a Ternary Content Addressable Memory (TCAM) based multiple-pattern matching scheme. The scheme can handle complex patterns, such as arbitrarily long patterns, correlated patterns, and patterns with negation. For the ClamAv virus database with 1768 patterns whose sizes vary from 6 bytes to 2189 bytes, the proposed scheme can operate at a 2 Gbps rate with a 240KB TCAM.}
}

EndNote citation:

%0 Report
%A Yu, Fang
%A Katz, Randy H.
%A Lakshman, T. V.
%T Gigabit Rate Packet Pattern-Matching Using TCAM
%I EECS Department, University of California, Berkeley
%D 2004
%@ UCB/CSD-04-1341
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2004/5467.html
%F Yu:CSD-04-1341