Middlebox services that inspect packet payload have become commonplace. Today, anyone can sign up for cloud-based Web application firewall with a single click. These services typically look for known patterns that might appear anywhere in the payload. The key challenge is that existing solutions for pattern matching have become a bottleneck as software packet processing technologies advanced. The popularization of cloud-based services has made the problem even more critical.
This paper presents an efficient multi-pattern string matching algorithm, called DFC. DFC significantly reduces the number of memory accesses and cache misses by using small and cache-friendly data structures and avoids instruction pipeline stalls by minimizing sequential data dependency. Our evaluation shows that DFC improves the performance by 2.0 to 3.6 times compared to the state-of-the-art on real tracffic workload obtained from a commercial network. It also outperforms other algorithms even in the worst case. In addition, the data structure construction time of DFC is much smaller than that of other algorithm. When applied to middlebox applications, such as network intrusion detection, anti-virus, and Web application fi rewall, DFC delivers 57%-160% performance improvement.
오늘날, 패킷의 페이로드를 조사하는 네트워크 미들박스 서비스들이 매우 보편화되었다. 예를 들어, 누구든지 단 한 번의 클릭만으로도 웹 어플리케이션 파이어월의 서비스를 이용한다. 일반적으로 이러한 미들박스 서비스들은 알려진 패턴들이 페이로드에 존재하는지 탐지를 하는데, 문제는 탐지를 위해 사용되는 기존의 알고리즘들에서 성능 병목 현상이 심각하게 일어나고 있다는 것이다. 이는 네트워크 미들박스 어플리케이션들의 구성요소들에 있어 패턴 매칭을 제외한 다른 부분에 많은 연구가 진행되었고 그들의 성능이 향상되었기 때문이며, 클라우드 기반 서비스의 치솟는 인기가 이 문제를 더욱 중요하게 만들고 있다.
이 연구에서 우리는 DFC라는 새로운 다중 패턴 매칭 알고리즘을 개발하였다. DFC는 크기가 작고 캐시 메모리에 친화적인 데이터 구조체를 이용하여 기존 알고리즘 대비 메모리 접근 횟수와 캐시 미스 횟수를 획기적으로 줄일 수 있었으며, 순차적인 데이터 의존성을 최소화하여 명령어 레벨 병행의 정도를 극대화하였다. 상업 네트워크의 실제 트래픽을 대상으로 실험을 진행한 결과, DFC가 최신 알고리즘 대비 2.0에서 3.6배 높은 성능을 보였으며, 심지어 페이로드가 패턴들로 가득찬 상황에서도 DFC가 더 높은 성능을 보였다. DFC를 네트워크 미들박스 어플리케이션에 적용해본 결과, 57%에서 160% 까지의 성능 향상을 도모할 수 있었다.
