[논문]네트워크 침입방지 시스템을 위한 고속 패턴 매칭 가속 시스템

김선일

doi:10.3745/kipsta.2005.12a.2.087

네트워크 침입방지 시스템을 위한 고속 패턴 매칭 가속 시스템
A High-speed Pattern Matching Acceleration System for Network Intrusion Prevention Systems 원문보기

정보처리학회논문지. The KIPS transactions. Part A. Part A, v.12A no.2 = no.92, 2005년, pp.87 - 94

초록
AI-Helper

패턴 매칭(Pattern Matching)은 네트워크 침입방지 시스템에서 가장 중요한 부분의 하나며 많은 연산을 필요로 한다. 날로 증가되는 많은 수의 공격 패턴을 다루기 위해, 네트워크 침입방지 시스템에서는 회선 속도로 들어오는 패킷을 처리 할 수 있는 다중 패턴 매칭 방법이 필수적이다. 본 논문에서는 현재 많이 사용되고있는 네트워크 침입방지 및 탐지 시스템인 Snort와 이것의 패턴 매칭 특성을 분석한다. 침입방지 시스템을 위한 패턴 매칭 방법은 다양한 길이를 갖는 많은 수의 패턴과 대소문자 구분 없는 패턴 매칭을 효과적으로 다룰 수 있어야 한다. 또한 여러 개의 입력 문자들을 동시에 처리 할 수 있어야 한다. 본 논문에서 Shift-OR 패턴 매칭 알고리즘에 기반을 둔 다중 패턴 매칭 하드웨어 가속기를 제시하고 여러 가지 가정 하에서 성능 측정을 하였다. 성능 측정에 따르면 제시된 하드웨어 가속기는 현재 Snort에서 사용되는 가장 빠른 소프트웨어 다중 패턴 매칭 보다 80배 이상 빠를 수 있다.

Abstract ▼ AI-Helper

Pattern matching is one of critical parts of Network Intrusion Prevention Systems (NIPS) and computationally intensive. To handle a large number of attack signature fattens increasing everyday, a network intrusion prevention system requires a multi pattern matching method that can meet the line speed of packet transfer. In this paper, we analyze Snort, a widely used open source network intrusion prevention/detection system, and its pattern matching characteristics. A multi pattern matching method for NIPS should efficiently handle a large number of patterns with a wide range of pattern lengths and case insensitive patterns matches. It should also be able to process multiple input characters in parallel. We propose a multi pattern matching hardware accelerator based on Shift-OR pattern matching algorithm. We evaluate the performance of the pattern matching accelerator under various assumptions. The performance evaluation shows that the pattern matching accelerator can be more than 80 times faster than the fastest software multi-pattern matching method used in Snort.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 PMA 수행에 관계되는 명령어를 먼저 정의하고 이들 명령어들의 수행시간을 분석하였다. 하나의 패턴 매칭 연산은 다음과 같이 수행된다고 정의한다.
본 논문에서는 Shift-OR 알고리즘을 효율적으로 구현하는 하드웨어 패턴 매칭 방법을 제시하고 확장하였다. 제시된 패턴 매칭 하드웨어(PMA)는 위에서 분석된 NIPS의 패턴 매칭 방법 갖아야 하는 조건들을 효과적으로 만족시킨다.
패턴 매칭은 NIPS에서 악의적 공격의 패턴을 패킷의 데이터에서 발견하는데 사용되고, Snort의 분석에서 알 수 있듯이 수행시간의 상당 부분을 차지하며 NIPS의 성능에 결정적인 영향을 미친다. 본 논문에서는 Snort의 구조와 패턴 매칭의 특성을 분석하였다. Snort는 효율적인 패턴옵션 처리를 위하여 다중 패턴 매칭 방법을 사용하는데 이 방법들은 다양한 길이를 갖는 많은 수의 패턴을 효과적으로 다룰 수 있어야 하며, 대소문자 구별 없는 패턴 매칭과 여러 개의 입력 문자를 동시에 처리 할 수 있는 능력이 있어야 한다.
본 논문에서는 기가비트급의 빠른 속도 요구를 만족하고 기존의 하드웨어 패턴 매칭 방법의 단점을 극복할 수 있는 하드웨어 기반의 패턴 매칭 방법을 제시한다. 이 방법은 잘 알려진 패턴 매칭 방법인 Shift-OR [20]에 기반을 두고 있다.
범용 프로세서에서 소프트웨어로 구현 되었을 때는 한 번에 처리되는 양이 레지스터의 크기에 제한을 받기 때문에 전체 패턴의 크기가 큰 경우에는 매우 느리게 동작하게 된다. 본 논문에서는 다중 패턴을 위한 Shift-OR 알고리즘을 효과적으로 구현하는 패턴 매칭 아키텍쳐를 제안하고, 또한 한 번에 여러 개의 입력 문자를 처리 할 수 있도록 확장한다. 본 논문은 다음과 같이 구성된다.

가설 설정

이들 AC와 MWM은 각각 Aho-Corasick 과 Wu-Manber 알고리즘에 기반을 두고 있다. PMA 가 Snort 에서 사용되는 소프트웨어 패턴 매칭 방법 대신에 사용되고 있다고 가정하고 실제 Snort가 수행 중 얻어진 데이터를 바탕으로 성능을 평가한다. Snort 수행에 사용된 PMA 시뮬레이터는 앞의 절에서 설명된 PMA구조를 시뮬레이션한다.
Shift-OR 연산은 두 개의 게이트 지연(1 AND and 1 OR gate delays)이 걸리고 매칭 발견 과정은 N의 값에 따라 1—4게이트 지연(0~4 AND and 1 OR gate delays)이 걸린다. 각 게이트의 연산은 무척 빠르기 때문에 Shift-OR 연 산 시간(Ts°)은 0.25에서 1사이클이 걸리고 매칭 발견 과정은 2사이클이 걸린다고 가정하였다. 벡터 계산시간이 소수점 밑의 숫자를 가질 경우 소수점 올림을 하여 정수값 을 취한다.
매칭 발견 장치나 우선순위 인코더는 패턴과 일치되는 문자열을 발견하였을 경우 PMA로부터 어떤 정보를 소프트웨어가 원하는가에 따라 다르게 설계될 수 있다. 본 논문에서 제시된 구조는 소프트웨어가 단지 매칭이 있는지 그리고 매칭이 있는 경우에 매칭 결과 벡터에서 매칭비트의 위치만을 알 필요가 있다고 가정하였다.
성능평가에서 PMA_reset 명령어는 모든 내부 벡터들을 초기화하는 수행만 하기 때문에 1사이클(cycle)동안에 수행 된다고 가정하였다. PMA_pattem_search 명령어의 수행시간은 매칭이 발견되기 전까지 수행 되어야 하는 패턴 매칭 연산의 수에 따라 변하게 된다.

제안 방법

PMA 가 Snort 에서 사용되는 소프트웨어 패턴 매칭 방법 대신에 사용되고 있다고 가정하고 실제 Snort가 수행 중 얻어진 데이터를 바탕으로 성능을 평가한다. Snort 수행에 사용된 PMA 시뮬레이터는 앞의 절에서 설명된 PMA구조를 시뮬레이션한다. PMA와 관련된 여러 가지 수행 중 문자 위치 테이블을 채우고 패턴 경계 벡터를 설정하는 것과 같은 과정은 시간상 중요하지 않기에 평가에서 제외되고 패턴 매칭에 직접 관계되는 수행 과정만이 평가 한다.
다음으로 shift size TV, 즉 한 번에 처리 될 수 있는 문자들의 수를 1에서 32까지 변화시키면서 PMA 의 성능을 측정하였다 (그림 7). Shift-OR 연산에 걸리는 시간은 0.
다음은 Snort에서 발견되는 패턴 매칭의 특성을 분석함으로써 침입 방지 시스템에서의 패턴 매칭 특성에 대하여 알아본다. Snort의 패턴 매칭 특성 증가장 중요한 것 중의 하나는 문자열 패턴의 수이다.
만약 느린 메모리 구현 방법이 사용되었다면은 접근 시간은 100사이클을 넘길 수 있다. 본 논문에서는 성능 평가를 위하여 이 메모리 접근시간을 2〜64사이클 까지 변하였다. 벡터 계산은 N개의 Shift-OR 연산과 하나의 매칭 발견 과정으로 구성되어 있다.
한 번의 패턴 매칭 연산에 걸리는 시간은 실제 하드웨어 구현에 사용되는 기술에 따라 달라질 수 있다. 성능평가를 위하여 본 논문에서는 패턴 매칭 연산에 사용되는 시간을 고정하지 않고 여러 가지로 변화하였다. 수행시간은 클락 주기 (clock cycle)로 측정되었다.
이 경우 게이트의 지연은 약log2 M-3 가 되며, PMA 경우에는 약 12게이트 지연이 된다. 성능평가를 위해 우선순위 인코더의 수행시 간을 2〜8사이클로 변화시켰다.
4GHz Pentium IV와 512MB 메모리를 갖는 Linux PC 에서 Snort를 수행하며 측정되었다. 이 측정을 위하여 Pentium 프로세서의 Time-stamp counter명령에24]를 사용하여 이들 소프트웨어들이 수행에 걸린 사이클을 측정하였 다. (그림 6)은 MWM 방법의 수행에 걸린 사이클을 기준으로 PMA 와 AC, MWM 의 속도 증가율(speedup)을 보여주고 있다.
0에서부터는 규칙들이 프로토콜과 발신지와 목적지의 포트번호로 규칙 집단(ruleset)을 이루고 다중 패턴 매칭 기법을 사용하여 규칙과 일치하는 패킷을 찾는 과정의 속도를 향상시키었다. 패킷이 도착하면, 패킷의 프로토콜과 발신지와 목적지 포트번호를 가지고 알맞은 규칙 집단을 찾고 그 규칙 집단에 있는 모든 'content' 옵션의 문자열 패턴에 대하여 다중 패턴 매칭 방법을 사용하여 조사를 한다.만약 매칭되는 패턴이 발견되면 그 패턴을 갖고 있는 모든 규칙에 대하여 RTN과 OTN에 차례로 조사된다.
번째 항목은 PMA_pattern_search의 수행시간이고, 마지막으로 세 번째 항목은 PMA_match_position 수행시간이다. 패턴 매칭 연산의 수(加提와 패턴 매칭의 수(Npm)는 Snort가 패킷 트래이스(Packet trace)를 가지고 수행하는 동안 측정하여 얻고, N, Tm 와 Tp은 위에서 설명된 것처럼 변화하며 수식(6)에 따라 PMA의 수행시간을 평가하였다. 사용된 패킷 트래이스는 DefCon 11 [22, 23]의 'Capture the flag contest'에서 수집된 것이다.

대상 데이터

패턴 매칭 연산의 수(加提와 패턴 매칭의 수(Npm)는 Snort가 패킷 트래이스(Packet trace)를 가지고 수행하는 동안 측정하여 얻고, N, Tm 와 Tp은 위에서 설명된 것처럼 변화하며 수식(6)에 따라 PMA의 수행시간을 평가하였다. 사용된 패킷 트래이스는 DefCon 11 [22, 23]의 'Capture the flag contest'에서 수집된 것이다. 'Defcon's Capture the Flag(CtF)' 경기는 가장 큰 오픈 컴퓨터 보안 해킹 게임이다.

데이터처리

본 논문에서 제시된 패턴 매칭 하드웨어 가속기(PMA)의 성능을 시뮬레이션 모델을 이용하여 평가하고 Snort에서 사용되는 소프트웨어 다중 패턴 매칭 방법들, 4C와 과 비교한다. 이들 AC와 MWM은 각각 Aho-Corasick 과 Wu-Manber 알고리즘에 기반을 두고 있다.

성능/효과

제시된 패턴 매칭 하드웨어(PMA)는 위에서 분석된 NIPS의 패턴 매칭 방법 갖아야 하는 조건들을 효과적으로 만족시킨다. PMA를 구성하는 장치들의 속도를 다양하게 가정하고 성능을 측정하여 보았을 때 PMA는 Snort에서 사용되는 가장 빠른 소프트웨어 패턴 매칭 방법보다 80배 이상 빠를 수 있었다.
(그림 6)에 나타난 결과는 MWM 이 AC 방법에 비해 약 두 배가 빠르다는 것을 보여주고 있다. 메모리 접근시간과 Shift-OR 연산 수행시간이 각각 8과 1사이클로 고정되고 우선순위 인코더의 수행시간이 1에서 부터 32사이클로 증가하였을 때, PMA의 속도 증가율은 4배에서 별 변화가 없었다. 반면 Shift-OR 연산의 수행과 우선순위 인코더의 수행이 각각 1과 4사이클로 설정되고 메모리 접근시간이 2부터 64사이클까지 증가되었을 때, PMA 의 속도 증가율은 8배에서 0.
이 결과는 또한 패턴 매칭 연산에서 메모리 접근에 들어가는 수행시간이 우선순위 인코더의 수행시간보다 더 많은 영향을 PMA 성능에 미친다는 것을 보여주고 있다. 우선순위 인코더의 수행시간 증가는 PMA 성능을 크게 변화시키지 못한 반면 메모리 접근시간의 증가는 PMA의 속도 증가율을 크게 줄였다. 이러한 결과가 나온 이유는 패턴 매칭 연산의 수 Npo 가 패턴 매칭의 수强 보다 훨씬 크기 때문이다.
이 결과는 PMA의 성능 이 메모리 접근 시간에 영향을 많이 받는다는 것을 보여주고 있다. 이 결과는 또한 패턴 매칭 연산에서 메모리 접근에 들어가는 수행시간이 우선순위 인코더의 수행시간보다 더 많은 영향을 PMA 성능에 미친다는 것을 보여주고 있다. 우선순위 인코더의 수행시간 증가는 PMA 성능을 크게 변화시키지 못한 반면 메모리 접근시간의 증가는 PMA의 속도 증가율을 크게 줄였다.
본 논문에서는 Shift-OR 알고리즘을 효율적으로 구현하는 하드웨어 패턴 매칭 방법을 제시하고 확장하였다. 제시된 패턴 매칭 하드웨어(PMA)는 위에서 분석된 NIPS의 패턴 매칭 방법 갖아야 하는 조건들을 효과적으로 만족시킨다. PMA를 구성하는 장치들의 속도를 다양하게 가정하고 성능을 측정하여 보았을 때 PMA는 Snort에서 사용되는 가장 빠른 소프트웨어 패턴 매칭 방법보다 80배 이상 빠를 수 있었다.
25사이클 걸릴 때 32개의 문자 위치벡터 테이블을 사용하면 PMA는 MWM 보다 약 80배 이상 빠르고, 16개의 문자 위치벡터 테이블을 사용하면 70배 정도 빠르게 된다. 종합적으로 이 결과는 빠른 메모리 접근시간과 큰 shift size는 PMA가 좋은 성능을 얻는데 중요하다는 것을 보여주고 있다. 고속의 메모리 접근 시간은 빠른 메모리 구현 기술을 사용하거나 입력 버퍼와 문자 위치 테이블의 접근 경로를 파이프라인화 함으로서 성취할 수 있다.

참고문헌 (25)

Code Red worm exploiting buffer overflow in IIS indexing service DLL. CERT Advisory CA-2001-19, Jan 2002
MS-SQL Server Worm. CERT Advisory CA-2003-04, Jan 2003
정보흠, 김정녀, 손승원, '침입방지시스템 기술 현황 및 전망,' 주간기술동향 통권 1098호, 2003. 6. 3
X. Zhang, C. Li, and W. Zheng, 'Intrusion Prevention System Design', Proceedings of the Fourth International Conference on Computer and Information Technology, September, 2004
Snort. http://www.snort.org/
S. Antonatos, K. G. Anagnostakis, and E. P. Markatos, 'Generating realistic workloads for network intrusion detection systems', ACM Workshop on Software and Performance, 2004
E. P. Markatos, S. Antonatos, M. Polychronakis, and K. G. Anagnostakis, 'Exclusion-based Signature Matching for Intrusion Detection', The IASTED International Conference on Communications and Computer Networks, Oct. 2002
C. J. Coit, S. Staniford, and J. McAlerney, 'Towards Faster String Matching for Intrusion Detection or Exceeding the Speed of Snort', The 2nd DARPA Information Survivability Conference and Exposition (DISCEX II), June 2002
N. Tuck, T. Sherwood, B. Calder, and G. Varghese, 'Deterministic Memory-Efficient String Matching Algorithms for Intrusion Detection', The 23rd Conference of the IEEE Communications Society (INFOCOM'04), March 2004
A. V. Aho and M.J. Corasick, 'Efficient string matching : An aid to bibliographic search', Communications of the ACM, 18(6):333-340, 1975

상세보기
Sun Wu and Udi Manber, 'AGREP - A Fast Approximate Pattern-Matching Tool', The 1992 Winter USENIX Conference, January, 1992
R. Sidhu, and V. K. Prasanna, 'Fast Regular Expression Matching using FPGAs', The 9th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, May 2001
B. L. Hutchings, R. Franklin, and D. Carver, 'Assisting Network Intrusion Detection with Reconfigurable Hardware', The 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, September 2002
J. Moscola, J. Lockwood, R. P. Loui, and M. Pachos, 'Implementation of a Content-Scanning Module for an Internet Firewall', The 11th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, April 2003
M. Gokhale, D. Dubois, A. Dubois, M. Boorman, S. Poole, and V. Hogsett, 'Granidt: Towards Gigabit Rate Network Intrusion Detection Technology', The 12th International Conference on Field-Programmable Logic and Applications, September 2002
Y. H. Cho, S. Navab, and W. H. Mangione-Smith, 'Specialized Hardware for Deep Network Packet Filtering', The International Conference on Field Programmable Logic and Applications, September 2002
I. Sourdis and D. Pnevmatikatos, 'Fast, Large-Scale String Match for a 10Gbps FPGA-based Network Intrusion Detection System', The 13th International Conference on Field Programmable Logic and Applications, September 2003
I. Sourdis and D. Pnevmatikatos, 'Pre-decoded CAMs for Efficient and High-Speed NIDS Pattern Matching', The 12th Annual IEEE Symposium on Field Programmable Custom Computing Machines, April 2004
S. Dharmapurikar, P. Krishnamurthy, T. Sproull, and J. W. Lockwood, 'Deep Packet Inspection Using Parallel Bloom Filters', The International Symposium on High Performance Interconnects (HotI), Aug. 2003
Ricardo A. Baeza-Yates, and Gaston H. Gonnet, 'A New Approach to Text Searching', The Communications of the ACM, October 1992

상세보기
C. KUN, S. Quan, and A. Mason, 'A Power-Optimized 64-bit Priority Encoder Utilizing Parallel Priority Look-Ahead', IEEE Int. Symposium on Circuits and Systems (ISCAS), May 2004
C. Cowan, S. Arnold, S. Beattie, C. Wright, and J. Viega, 'Defcon Capture the Flag: Defending Vulnerable Code from Intense Attack', The DARPA DISCEX III Conference, April 2003
Capture the RootFu!, The Shmoo Group, url http://www.shmoo.com/cctf/
IA-32 Intel $\circledR$ Architecture Software Developer's Manual, Volume 3: System Programming Guide, Intel, 2004
S. Naffziger, T. Grutkowksi, and B. Stackhouse, 'The Implementation of a 2-core Multi-Threaded Itanium Family Processor', IEEE International Solid-State Circuits Conference, 2005

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증