서지주요정보
High performance multi-string pattern matching for network applications = 네트워크 어플리케이션을 위한 고성능 다중 패턴 매칭 알고리즘에 관한 연구
서명 / 저자 High performance multi-string pattern matching for network applications = 네트워크 어플리케이션을 위한 고성능 다중 패턴 매칭 알고리즘에 관한 연구 / Byung-Kwon Choi.
저자명 Choi, Byung-Kwon ; 최병권
발행사항 [대전 : 한국과학기술원, 2016].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8029190

소장위치/청구기호

학술문화관(문화관) 보존서고

MEE 16079

SMS전송

도서상태

이용가능

대출가능

반납예정일

초록정보

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% 까지의 성능 향상을 도모할 수 있었다.

서지기타정보

서지기타정보
청구기호 {MEE 16079
형태사항 v, 33 p. : 삽도 ; 30 cm
언어 영어
일반주기 저자명의 한글표기 : 최병권
지도교수의 영문표기 : Dongsu Han
지도교수의 한글표기 : 한동수
수록잡지명 : "DFC: Accelerating String Pattern Matching for Network Applications". The 13th USENIX Symposium on Networked Systems Design and Implementation (NSDI), (2016)
학위논문 학위논문(석사) - 한국과학기술원 : 전기및전자공학부,
서지주기 References : p. 28-32
주제 multi-pattern matching
multi-string pattern matching
network application
middlebox applications
Aho-Corasick algorithm
다중 패턴 매칭
다중 문자열 패턴 매칭
네트워크 어플리케이션
미들박스 어플리케이션
아호 코라식 알고리즘
QR CODE qr code