고처리량 및 저메모리 패턴 매칭 아키텍처
Source
Evernote/IFTTT Feedly/A Pattern-Matching Scheme With High Throughput Performance and Low Memory Requirement.md
Summary
본 논문은 네트워크 보안(침입 탐지, 바이러스 보호 등)에서 사용되는 패턴 매칭 기술의 한계를 극복하기 위한 새로운 아키텍처를 제안한다. 기존 Aho-Corasick(AC) 알고리즘은 고속 네트워크 환경에서 처리량 부족과 큰 패턴 집합에 따른 2차원 상태 전이 테이블의 과도한 메모리 사용 문제를 가진다. 제안된 아키텍처는 ‘상태 기반 프리필터(stateful pre-filter)‘와 ‘AC 기반 검증 엔진’으로 구성된다. 프리필터는 이전 쿼리 결과를 활용하여 비트맵과 간단한 비트 연산으로 구현되며, 상태 전이 테이블의 크기를 패턴의 총 길이가 아닌 패턴의 개수에 비례하도록 줄여 메모리 효율성을 크게 향상시킨다. 이를 통해 처리량과 메모리 사용량 모두에서 기존 방식 대비 상당한 개선을 달성한다.
Key Points
- 기존 Aho-Corasick 알고리즘은 고속 네트워크 처리량 부족 및 대규모 패턴 저장 시 메모리 과다 사용 문제가 있음
- 상태 기반 프리필터(stateful pre-filter)와 AC 기반 검증 엔진으로 구성된 하이브리드 아키텍처 제안
- 프리필터는 이전 쿼리 결과를 최적화하여 활용하며, 비트맵과 단순 비트 연산(AND, shift)으로 효율적 구현 가능
- 상태 전이 테이블 크기를 패턴 총 길이 대신 패턴 개수에 비례하도록 설계하여 메모리 요구량 감소
- 고처리량 성능과 저메모리 요구사항을 동시에 만족하는 네트워크 보안용 패턴 매칭 솔루션