Detection

From Computing and Software Wiki

Current revision as of 00:16, 24 March 2008

The typical function of a NIDS is based on a set of signatures, each describing one known intrusion threat. ANIDS examines network traffic and determines whether any signatures indicating intrusion attempts are matched.

The simplest and most common form of NIDS inspection is to match string patterns against the payload of packets captured on a network link.

For instance, consider the (simplified) signature shown here:

alert tcp $EXTERNAL_NET any -> $HTTP_SERVERS 80 (content:‘‘/usr/bin/perl’’)

It is a A simple intrusion detection rule, taken from snort, a widely-used open-source NIDS. This signature matches all TCP/IP packets originating from computers outside the monitored domain (i.e., the $EXTERNAL NET), destined to the web servers of the monitored domain (i.e., the $HTTP SERVERS at port 80 ), and containing the string “/usr/bin/perl” in the payload. If the NIDS determines that a packet matches this rule, it infers that a malicious client may be trying to make the web server execute the perl interpreter, hoping to gain unauthorized access. To decide whether a packet matches the signature, the NIDS needs to check the (TCP/IP) packet header for the specified values (i.e., $EXTERNAL NET, $HTTP SERVERS, 80). In addition, the NIDS needs to check whether the payload contains the string “/usr/bin/perl”.

There are two main algorithms for pattern matching:

E2xB: A domain­specific string matching algorithm for intrusion detection:

In this context, we present ÌÎÍ}Ï\Ð , a string matching algorithm that is designed specifically for the relatively small input size (in the order of packet size) and small expected matching probability that is common in a NIDS environment.

These assumptions allow string matching to be enhanced by first testing the input (e.g., the payload of each packet) for missing fixed-size sub-strings of the original signature string, called elements. The false positives induced by ÌÎ͇Ï\Ð , e.g., cases with all fixed-size sub-strings of the signature showing up in arbitrary positions within the input, can then be separated from actual matches using standard string matching algorithms"

Boyer-Moore algorithm:

Boyer-Moore algorithm

The Boyer-Moore algorithm is considered as the most efficient string-matching algorithm in usual applications. A simplified version of it or the entire algorithm is often implemented in text editors for the «search» and «substitute» commands.

The algorithm scans the characters of the pattern from right to left beginning with the rightmost one. In case of a mismatch (or a complete match of the whole pattern) it uses two precomputed functions to shift the window to the right. These two shift functions are called the good-suffix shift (also called matching shift and the bad-character shift (also called the occurrence shift).

One of the best references in string matching is: http://www-igm.univ-mlv.fr/~lecroq/string/