P-AC made multi-string matching fit hardware by cutting the automaton down

Network security systems must compare a fast data stream against thousands of signatures in real time. The attractive part of Aho-Corasick is that its running time is independent of the number of strings, but its transition table can be large.

Pao, Lin, and Liu's 2010 ACM TACO paper kept the useful linear stream behavior while attacking the memory cost. By incorporating pipelined processing, the state graph is reduced to a character trie containing only forward edges.

The paper reports about 18 bits per character for a 6,166-string signature set extracted from Snort, low control-logic cost, and the ability to double throughput with dual-port FPGA memories by processing two streams concurrently.

Pipeline the automaton into a trie

It separates the algorithm's matching promise from one bulky implementation of its automaton.

The trie-and-table layout trades general transitions for pipeline-friendly memory.

Incremental signature changes can update lookup tables without reconfiguring the FPGA circuitry.

Preserve the algorithmic invariant while changing the physical representation. The same search logic can become practical when the state machine is laid out for the hardware.

P-AC is a nice hardware lesson from intrusion detection: the breakthrough was not a new matching rule, but a representation that made a known rule small, parallel, and updateable enough for fast packet streams.