Deterministic Memory-Efficient String Matching Algorithms for Intrusion Detection

Abstract

Intrusion Detection Systems (IDSs) have become

widely recognized as powerful tools for identifying, deterring

and deflecting malicious attacks over the network.

Essential to almost every intrusion detection system is the

ability to search through packets and identify content that

matches known attacks. Space and time efficient string

matching algorithms are therefore important for identifying

these packets at line rate.

In this paper we examine string matching algorithms

and their use for Intrusion Detection. In particular, we focus

our efforts on providing worst-case performance that

is amenable to hardware implementation. We contribute

modifications to the Aho-Corasick string-matching algorithm

that drastically reduce the amount of memory required

and improve its performance on hardware implementations.

We also show that these modifications do

not drastically affect software performance on commodity

processors, and therefore may be worth considering in

these cases as well.

Keywords: System Design, Network Algorithms

I. INTRODUCTION

With each passing day there is more critical data accessible

in some form over the network. Any publicly

accessible system on the Internet today will be rapidly

subjected to break-in attempts. These attacks can range

from email viruses, to corporate espionage, to general destruction

of data, to attacks that hijack servers from which

to spread additional attacks. Even when a system cannot

be directly broken into, denial of service attacks can be

just as harmful to individuals, and can cause nearly equal

damage to the reputations of companies that provide services

over the Internet. Because of the increasing stakes

held by the various users of the internet, there has been

widespread interest in combating these attacks at every

level, from end hosts and network taps to edge and core

routers.

Intrusion Detection Systems (or IDSs) are emerging as

one of the most promising ways of providing protection

to systems on the network. The IDS market has been estimated

at $100 million by the Aberdeen Group, with expectations

that it will double in 2004 and keep growing in

future years. By automatically monitoring network traffic

in real time, intrusion detection systems can alert administrators

of suspicious activities, keep logs to aid in forensics,

and assist in the detection of new worms and denial

of service attacks.

As with firewalls, intrusion detection systems are growing

in popularity because they provide a site resilience to

attacks without modifying end-node software. While firewalls

only limit entry to a network based on packet headers,

intrusion detection systems go beyond this by identifying

possible attacks that use valid packet headers that

pass through firewalls. Intrusion detection systems gain

this capability by searching both packet headers and payloads

to identify attack signatures.

To define suspicious activities, an IDS makes use of a

set of rules which are applied to matching packets. A rule

consists at minimum of a type of packet to search, a string

of content to match, a location where that string is to be

searched for, and an associated action to take if all the conditions

of the rule are met. An example rule might match

packets that look like a known buffer overflow exploit in

a web server; the corresponding action might be to log the

packet information and alert the administrator.

Because of the utility of IDSs they are beginning to be

deployed in a wide range of operating environments. Endhosts

use them to monitor and prevent attacks from incoming

traffic. They can be found in network-tap devices that

are inserted into key points of the network for diagnostic

purposes. They will soon even find their way into edge

and core routers to protect the network infrastructure from

distributed attacks.

The challenge is that increasing line-rates and an explosion

in the number of attacks mounted as well as plummet-