Multi-Pattern Matching in Network Intrusion Detection

An intrusion detection system inspects traffic it is not a party to. It does not terminate connections, so it cannot rely on a peer’s cooperation in framing messages; it reconstructs what the endpoints must be seeing and runs pattern matching over that reconstruction. Both halves matter, and the second half is where most evasion lives: a rule that never fires because the engine looked at the wrong bytes is indistinguishable, operationally, from a rule that was never written.

A rule set is a set of patterns with context

Signature languages describe a detection as a pattern plus the conditions under which the pattern counts. In Suricata and Snort the shape is an alert header followed by keyword options:

alert http $HOME_NET any -> $EXTERNAL_NET any (
    msg:"request with suspicious client marker";
    flow:established,to_server;
    http.method; content:"POST";
    http.uri; content:"/upload";
    content:".php"; nocase;
    sid:100001; rev:1;
)

The header names action, protocol, source, destination, and direction. The options attach both matching constraints and metadata. The sid is the rule’s identity and rev versions it, which matters because a rule’s meaning changes over time while its identifier does not.

Two properties of this language drive engine design. First, most rules are anchored on cheap conditions such as port, direction, and protocol, and only a subset ever need to look at payload. An engine that matched every pattern against every byte would spend its capacity on traffic no rule could apply to. Second, the payload patterns are numerous and short. A mature rule set contains many thousands of literal strings, and matching them one at a time against a stream would multiply the cost by the rule count.

One pass over the stream with an automaton

The standard answer is to combine all literal patterns into a single automaton and run the stream through it once. The Aho–Corasick construction builds a trie of the patterns and adds failure links: when a transition is missing from a state, the failure link points at the longest proper suffix of the current match that is also a prefix of some pattern. Matching then never backtracks: every input byte causes at most one state transition, so the cost is linear in the input length plus the number of matches reported, independent of how many patterns are in the set.

Constructing the automaton costs time proportional to the total pattern length times the alphabet size for the dense-transition form, or total pattern length for the sparse form with a per-state failure walk. Memory is the binding constraint at scale: a state per trie node plus transition storage, where a dense table of 256 entries per state is simple and fast but large, and a sparse representation saves memory at the cost of a lookup per transition. Implementations routinely choose a memory-efficient automaton that handles the common case and fall back to individual matching for a small residue of patterns that the automaton represents poorly, such as very long strings or patterns with heavy wildcard content.

Two refinements appear in every practical engine. The first is to run the automaton only over the portion of the stream a rule could care about, using the cheap conditions to bound the region: a pattern anchored at the start of a URI needs no scanning beyond the URI. The second is to prefilter with a fast substring search, a Boyer–Moore style algorithm that skips ahead on mismatches, for the small number of high-value patterns that dominate the alert volume, letting the automaton handle the long tail.

Normalisation decides what the automaton sees

Matching bytes is meaningless if the bytes are not what the application will interpret. A request whose target is encoded differently at each hop, or a header split across TCP segments, presents a different byte sequence to the sensor than to the server. The engine therefore applies protocol-aware normalisation before matching: it reassembles the stream in sequence order, handles retransmissions, and decodes the layer-7 representation into a canonical form.

Reassembly is not optional, because TCP delivers a byte stream and the sensor sees packets. A pattern split across two segments is invisible to a per-packet matcher, and an attacker who controls segment sizes can choose where every boundary falls. Worse, TCP allows overlapping segments with different data, and different operating systems resolve the overlap differently: some favour the old data, some the new. The sensor must resolve overlaps the same way the target does, or it will match a stream the target never assembled. That is the core of the Ptacek and Newsham analysis, and it is why the reassembly policy is a per-target property rather than a global constant.

Normalisation continues above TCP. HTTP permits a request target expressed with percent escapes, with path segments that resolve away, and with parameters in an order the application may or may not treat as significant. A signature written against /upload.php does not fire on /upload%2Ephp unless the engine decodes before matching, and if it decodes, it must decode exactly as the server does, which returns to the same parser-differential problem described in Application Proxy Firewalls and Parser Differentials.

The design tension is unavoidable. Aggressive normalisation increases the chance of catching an obfuscated variant and increases the chance of an alert that does not correspond to anything the server would do. Conservative normalisation does the reverse. The usual resolution is to normalise to the documented interpretation for the protocol and to alert on inputs the specification forbids rather than trying to guess an implementation’s extension.

Evasion that survives normalisation

Some techniques target the matcher rather than the parser. Inserting bytes that the target ignores but the sensor does, such as an extra space in a header, a duplicate header the server uses last and the sensor uses first, or a comment in a protocol that allows them, shifts the matched region without changing the semantic request. This is insertion, and its dual is evasion: removing bytes the target would insert, so the sensor’s stream is shorter than the target’s.

Fragmentation at the IP layer produces the same effect one level down. A signature that inspects a transport header cannot match a non-initial fragment, so a datagram split into small pieces can deliver a payload the sensor never sees in context. The countermeasure is IP defragmentation before transport reassembly, with timeouts and size limits, and with an overlap policy matching the target’s.

Time-based evasion exploits the sensor’s own resource limits. A stream held open with slow dribbles keeps reassembly buffers occupied; a flood of incomplete connections exhausts the state table. Both are denial-of-service against the detector rather than against the target, and both are cheap. Engines respond with per-flow buffer caps and eviction policies, which in turn create the possibility of evicting state an attacker wants evicted before the malicious segment arrives.

What the alert means

A signature match is a statement about bytes at a point in a stream, not a statement about intent. The same pattern occurs in legitimate traffic whenever the pattern is short or generic, which is why rule sets carry flow direction constraints and protocol bindings to narrow the context. A rule without those constraints tends to produce alerts on traffic the rule author never considered, and the cost of that noise is borne by whoever has to triage it.

The complementary detection model does not use patterns at all: it models protocol behaviour and flags deviations, which is the approach Paxson’s Bro took by describing expected events per protocol rather than expected byte strings. The two models fail differently. Patterns miss variants they were not written for; behavioural models miss attacks that are valid protocol usage. Neither is a substitute for the other, and both depend on the same reassembly layer being correct.

A related dependency is that both models see only what reaches the sensor. Traffic on a path the sensor is not on, or traffic between two workloads on the same host, is invisible regardless of the matcher, which is the argument for enforcement and observation inside the host described in Microsegmentation and Policy at the Workload Boundary. Signature engines are strongest where the sensor sits on a choke point and the protocol is well-specified; both conditions are weaker than they were.