P-AC는 오토마타를 축소하여 다중 문자열 매칭을 하드웨어에 맞췄다

네트워크 보안 시스템은 빠른 데이터 스트림을 수천 개의 시그니처와 실시간으로 비교해야 한다. Aho-Corasick의 매력적인 점은 실행 시간이 문자열 수와 무관하다는 것이지만, 전이 테이블이 커질 수 있다.

Pao, Lin, Liu의 2010년 ACM TACO 논문은 유용한 선형 스트림 동작을 유지하면서 메모리 비용을 공략했다. 파이프라인 처리를 도입하여 상태 그래프를 순방향 간선만 포함하는 문자 트라이로 축소했다.

논문은 Snort에서 추출한 6,166개 문자열 시그니처 집합에 대해 문자당 약 18비트, 낮은 제어 논리 비용, 그리고 듀얼 포트 FPGA 메모리로 두 스트림을 동시에 처리하여 처리량을 두 배로 늘릴 수 있는 능력을 보고한다.

오토마타를 트라이로 파이프라인화

알고리즘의 매칭 약속을 오토마타의 한 가지 비대한 구현에서 분리한다.

트라이와 테이블 배치는 일반 전이를 파이프라인 친화적인 메모리로 대체한다.

증분 시그니처 변경은 FPGA 회로를 재구성하지 않고도 조회 테이블을 업데이트할 수 있다.

물리적 표현을 바꾸면서 알고리즘 불변식을 보존하라. 상태 기계를 하드웨어에 맞게 배치하면 동일한 검색 논리가 실용적이 될 수 있다.

P-AC는 침입 탐지에서 얻은 훌륭한 하드웨어 교훈이다. 돌파구는 새로운 매칭 규칙이 아니라, 알려진 규칙을 빠른 패킷 스트림에 충분히 작고, 병렬적이며, 업데이트 가능하게 만든 표현이었다.