논문 08-33-11-08 한국통신학회논문지 '08-11 Vol. 33 No. 11 네트워크침입탐지시스템에서고속패턴매칭기의설계및구현 준회원윤여찬 *, 정회원황선영 * Design and Implementation of High-Speed Pattern Matcher in Network Intrusion Detection System Yeo-Chan Yoon* Associate Member, Sun-Young Hwang* Regular Member 요 약 본논문은네트워크침입탐지시스템에서고속패턴매칭알고리듬과그구조를제안한다. 제안된알고리듬은실시간입력패킷에서특정패턴을검사하며정확한문자열, 문자열값의범위, 그리고문자열값의조합등을검색한다. 본연구에서는입력패킷과패턴은동시에겹치는문자열들을검색하기위해상태전이그래프로모델링하였으며상태전이그래프는구현복잡도를줄이기위해입력임플리컨트단위로분할하였다. 제안된패턴매칭구조는상태전이그래프와입력된문자열을입력으로사용한다. 제안된패턴매칭기는 VHDL 언어로모델링하여구현하였으며, 성능분석을통하여제안된기법의적절성을검증하였다. Key Words : NIDS, Pattern Matching, STG, RAM, FPGA ABSTRACT This paper proposes an high speed pattern matching algorithm and its implementation. The pattern matcher is used to check patterns from realtime input packet. The proposed algorithm can find exact string, range of string values, and combination of string values from input packet at high speed. Given string and rule set are modelled as a state transition graph which can find overlapped strings simultaneously, and the state transition graph is partitioned according to input implicants to reduce implementation complexity. The pattern matcher scheme uses the transformed state transition graph and input packet as an input. The pattern matcher was modelled and implemented in VHDL language. Experimental results show the proprieties of the proposed approach. Ⅰ. 서론최근인터넷사용자의수가증가하고, 인터넷의용량이증대됨에따라네트워크를통한해킹시도가급증하고있으며그로인한피해역시날로심각해지고있다. 그결과네트워크보안의중요성이 점차부각되고있으며, 네트워크를통한해킹시도를탐지하고그에대응하기위한네트워크침입탐지시스템 (Network Intrusion Detection System) 에대한연구가매우활발히진행되고있다. 네트워크침입탐지시스템은악의적인공격을감지해내고, 인터넷시스템을보호하기위해사용된 본연구는정보통신부및정보통신연구진흥원의대학 IT 연구센터육성지원사업의연구결과로수행되었으며 IDEC 에서제공한 CAD tool 을이용해 simulation 을수행하였습니다. * 서강대학교전자공학과 CAD & ES. 연구실 (ducks@eecad.sogang.ac.kr) 논문번호 : KICS2008-09-383, 접수일자 : 2008 년 9 월 2 일, 최종논문접수일자 : 2008 년 10 월 14 일 1020
논문 / 네트워크침입탐지시스템에서고속패턴매칭기의설계및구현 다. 네트워크침입시도나공격은패턴이나서브패턴의조합으로표현될수있으므로, 패턴매칭이네트워크침입탐지시스템에서의가장중요한이슈이며, 사용하는패턴매칭알고리듬에따라네트워크침입탐지시스템의성능이결정된다 [1]. 현재네트워크침입탐지시스템의패턴데이터베이스에는수천개의패턴들이등록되어있으며, 패턴의수는더욱늘어날전망이므로, 패턴매칭에서의병목현상이더욱심해질것으로예상된다. 그러나 Snort나 OSSEC와같은침입탐지시스템들은대부분소프트웨어기반의패턴매칭만을지원하기때문에네트워크의속도가빨라지면모든패킷을검사하지못하는현상이발생하게된다. 따라서소프트웨어기반침입탐지시스템의성능향상을위한연구로패턴 / 스트링매칭알고리듬의개선, 다중컴퓨터를사용한 Load Balancing, 트래픽센서앞단에 Splitter를사용하는방법들이연구되고있다 [2][3]. 패턴매칭시소모되는시간을줄이기위해하드웨어를이용한패턴매칭시스템에대한연구가진행되었다. 하드웨어기반침입탐지시스템의성능향상을위해 Brute force, Deterministic finite automata (DFA), Non-deterministic finite automate (NFA) 방법들이연구되었다 [4][5][6]. 패턴매칭에서의성능향상을위해하드웨어를기반으로한침입탐지시스템도많은연구가진행되었다. 하드웨어기반침입탐지시스템은패턴매칭기를 FPGA로구현하므로패킷을고속으로처리할수있는장점을가진반면에패턴이업데이트될때마다 FPGA에새로적용해야하므로업데이트시간이오래걸린다는단점이있다. 본논문에서는입력패킷에서특정한스트링을효율적으로검색하는패턴매칭알고리듬을제안하고하드웨어로구현한다. 제안된패턴매칭기는입력된패턴을 FSM으로변환후 RAM에저장함으로써, 소프트웨어기반침입탐지시스템의빠른업데이트와하드웨어기반침입탐지시스템의빠른패턴매칭속도모두를추구할수있다. 본논문의구성은다음과같다. Ⅱ장에서는관련연구를통해기존의패턴매칭기에대해분석하고, Ⅲ장에서는제안된알고리듬에대해설명한다. Ⅳ장에서는제안된패턴매칭기를설계하고, Ⅴ장에서는구현된패턴매칭기의성능을분석한다. 마지막으로 Ⅵ장에서는결론을제시한다. Ⅱ. 관련연구 네트워크침입탐지시스템에서패턴매칭을위해트리구조, 트라이 (trie) 구조, 해시구조, 해시와트리를조합한구조, 상태천이그래프 (state transition graph) 를이용한구조등이사용된다 [7][8][9]. 네트워크시스템에서패턴매칭을하기위해필드포지션 (field position) 이정해진필드값의추출, 필드포지션에상관없는필드값의추출, 필드값의비교, 필드값의범위비교, 필드의일부값생략후비교, 다수조건들이조합된비교방법이주로사용된다. 하드웨어로구현하는패턴매칭기의경우많은설계제약조건이있어주로프로세서로패턴매칭을수행하거나, 해시구조, 해시와트리를조합한구조, 멀티웨이트리 (multi-way tree) 구조들을이용한구조들이발표되었다 [10][11][12]. 또한속도를높이기위하여다수의패턴매칭기들을직렬또는병렬로다단연결하여수행할수있으며, 분류자료들을다수로나눈후나누어진분류자료들을이용하여수행하는구조들이발표되었다 [13]. 2.1 트리구조트리또는트라이 (trie) 를이용한분류및검색구조는사전의검색, 그래픽에디터, 정지영상및동영상의압축등에자주사용된다. 트라이구조는사전의단어검색에주로사용되며, 주어진분류자료를포함하는가장근사한엔트리를찾을수있다는장점이있다. Quad-tree, Octree 등의멀티웨이트리 (multi-way tree) 구조는값의비교 (greater than, less than), 값의범위비교, 가장근사한분류자료의선택등의기능을수행할수있는장점이있으나, 복잡한조합규칙을사용하는분류는수행하지못하는단점이있다. 2.2 해시구조해시구조는구현이간단하여상용소자에서프로토콜분류를위한복호화과정 (exact matching) 에자주사용되는구조이다. 해시구조를이용한분류는분류자료의키값을계산하여해시표 (hash table) 의엔트리주소에대응하여색인을하는구조로, 값의비교 (greater than, less than), 범위, 임의의위치에서의패턴매칭, 최대우도매칭 (most likely-hood matching) 등에사용이어려운단점이있다. 해시구조는다수의분류자료가하나의키값에대응되는경우가있어, 분류자료들사이의충돌 (hash collision) 이 1021
한국통신학회논문지 '08-11 Vol. 33 No. 11 발생하는경우가있고, 분류자료와해시표엔트리가동일한지를비교하기위하여엔트리내에분류자료또는분류자료의인식정보를포함해야한다. 해시충돌을해결하는방법으로내부해싱 (internal hashing), 외부해싱 (external hashing), 해시와트리또는해시와트라이구조등이사용되고있다. 내부해싱은해시충돌이발생할경우다시해시함수를이용하여키값을계산함으로써다른해시표주소를할당받는방법이다. 외부해싱은한키값에해당하는해시표주소에다수의엔트리들을저장하는방법으로, 소프트웨어로구현할경우주로연결리스트 (linked list) 구조를사용하고, 하드웨어로구현할경우한해시표주소당다수의고정된수의엔트리들이저장되는구조들을사용한다. 상용제품중램을이용한캐쉬구조를사용하는구조중이와유사한구조들이있으나, 한주소에작은수의엔트리들이대응되므로 (set-associative mapping 또는 direct mapping), 일반적인 fully-associative mapping을사용하는 CAM(Content Addressable Memory) 과는다른구조이다. Fully-associative mapping 을사용하는 CAM은메모리의내용을이용하여색인을해야하므로, 색인자료가 CAM 내의모든엔트리 tag들과동시에비교되어야하는부담이있어구조가복잡하고큰용량을제작하기어렵다. 검색속도를높이기위하여해시표를직렬또는병렬로순차적으로검색하는다단구조들이발표되었다. 2.3 해시와트리를조합한다단검색구조검색속도를높이기위하여다양한검색구조들을동시에액세스하는방법과분류자료들을분할한후다수의검색구조들을이용하여순차적으로검색하는검색구조들을사용할수있다. 외부해시구조에서다수의해시표엔트리들을동시에비교후삽입및검색을하는방법을사용할수있다. 해시와트리를조합하여분류를하는구조는기존해시구조의충돌현상을해결하고, 면적을보다효율적으로사용하기위하여제안되었다. 해시와트리를조합하여분류를하는외부해시구조의구현예로분류자료를다수의부분으로일부분을이용하여해싱한후나머지분류정보를이용하여트라이구조로색인을하는구조가발표되었다. Ⅲ. 제안된패턴매칭알고리듬본논문에서제안된네트워크침입탐지시스템 그림 1. 제안된패턴매칭기의흐름도 을위한패턴매칭기는특정패턴의검색, 특정패 턴이조합된패턴을찾는기능이가능하다. 그림 1 은제안된패턴매칭과정의흐름을보인다. 검색해 야할패턴은상태천이그래프로표현될수있으며 제안된패턴매칭기는그림 1의전처리단계에서 생성된상태천이그래프를입력받는다. 상태천이그 래프는상태를의미하는노드와노드들을연결하는 방향성이있는에지로구성되며, 현재상태와입력 에의해출력과 next state가결정된다. 만일현재 입력된패킷에대한검색을마친후에는다음입력 을입력스트림큐로부터입력받는다. 생성된상태 천이그래프는검사과정을거치며, 상태천이그래프 의모든노드는모든입력의합집합이전체입력집 합 ( 항등함수 ) 이되어야하고, 모든입력들의 XOR 연산이공집합이되어야하는조건들을만족해야 한다. 모든입력의합집합이전체입력집합 ( 항등함 수 ) 이아니면상태천이그래프에지정되지않은입 력이있는경우이므로예상하지못하는동작을하 Input function Current state Next state Output 01000000 st0 st1 000000 01010000 st0 st4 000000 01010000 st0 st8 000000 0100---- st1 st2 000000 0101---- st2 st3 000000 0100---- st3 st0 Output1 0101---- st4 st5 000000 0100---- st5 st6 000000 0100---- st6 st7 000000 0100---- st7 st0 Output2 0101---- st8 st9 000000 0101---- st9 st10 000000 0100---- st10 st11 000000 0100---- st11 st0 Output3 그림 2. 상태천이그래프를표현하는상태천이표 1022
논문 / 네트워크침입탐지시스템에서고속패턴매칭기의설계및구현 scan( scan_start, input_stream[] ) { address initial state FALSE while (scan_start) { if ( (queue is not empty) && (STG entry is last implicant) (request gen flag is TRUE) ) { stream request to input stream queue request_flag FALSE last_implicant_flag FALSE if (stream input implicant) { address next state request gen flag TRUE else if (STG entry is last implicant) { address initial state request gen flag TRUE else { address++ if (address == initial state) request gen flag TRUE else request gen flag 표의엔트리는 Input function, Current state, Next state, Output 으로구성된다. 현재상태는주소로표현하였으며, 주소의초기값은 initial state 값을가진다. 초기상태의상태천이엔트리를읽은후입력패킷과엔트리의입력조건함수와비교한다. 입력조건함수가입력된패킷을포함하는경우 (implication) 엔트리의출력값을출력한후엔트리의 Next state" 로천이하며상태천이가있을때마다다음패킷을다시입력받아야할지가결정된다. 실제입력된패킷에는다수의패턴이중복되어존재할수있으며, 검색하는다수의패턴이서로중복되는경우는상태천이그래프를구성함으로써모두검색이가능하고, 상태천이그래프의한노드에서다수의패턴이대응될수있으므로, 한상태천이표에서다수의결과가출력될수도있다. 검색하는두패턴들이중복되는조합의예를그림 4에보이며, 그림 5는두패턴의중복되는조합의경우를보인다. 그림 4와그림 5의검색하는스트링들이서로겹치는경우는다음과같이동시에검색이가능하다. 검색스트링의시작이동일한한스트링이다른스트링에포함되는경우에두스트링 가나다 와 가나다라마 를동시에검색하는예를그림 6(a) 에보인다. 두검색스트링의시작이동일하지않지만한스트링이다른스트링에포함되는경우에두스트링을검색하는예를그림 6(b) 에보인다. 1 2 검색 string1 가나다라마검색 string1 가나다검색 string2 가나다라마검색 string2 가나다라마 3 4 검색 string1 가나다라마검색 string1 가나다라마검색 string2 가나다검색 string2 다라마 5 6 검색 string1 가나검색 string1 가나다 그림 3. 제안된패턴매칭알고리듬의유사코드 검색 string2 다라마 검색 string2 다라마 는경우가존재하며, 모든입력들의 XOR 연산이공집합이아닌경우한입력에대해해당하는상태천이가여러경우가존재하는경우이므로유효하지않은상태천이그래프이다. 그림 2는특정패턴을검색하는상태천이그래프의예로 etri", "switch", "SoC" 를검색하는상태천이그래프를보인다. 제안된패턴매칭알고리듬은입력스트링을이용하여검색상태를운행 (traversal) 한다. 상태천이 7 8 검색 string1 가나다라마검색 string1 다라마검색 string2 나다라검색 string2 가나다라마 9 10 검색 string1 나다라검색 string1 다라마검색 string2 가나다라마검색 string2 가나 11 검색 string1 다라마검색 string2 가나다 그림 4. 검색하는스트링들이중복되는조합의예 1023
한국통신학회논문지 '08-11 Vol. 33 No. 11 String head1 String head2 검색 string 1 검색 string 2 String tail1 String tail2 검색스트검색스트링1 링2 가가나나다다라마 -> 경우 Head1과 head2의교 (a) Tail1 과 tail2의비교 중복여부 1 = = 겹치는경우 2 = < 겹치는경우 3 = > 겹치는경우 4 < = 겹치는경우 5 < < 겹치지않는경우 6 < < 겹치는경우 7 < > 겹치는경우 8 > = 겹치는경우 9 > < 겹치는경우 10 > > 겹치지않는경우 11 > > 겹치는경우 설명 동일한스트링 (b) 그림 5. 검색하는스트링들이중복되는조합의경우 (a) 입력되는두스트링, (b) 입력되는두스트링의중복되는조합의경우 Ⅳ. 제안된패턴매칭회로의구조 제안된패턴매칭알고리듬을구현한회로는상태천이표를입력받아입력된패킷을검색한다. 제안된패턴매칭기는 1 G/s 이상고속의네트워크환경에대해고속으로패턴매칭이가능하며, 구현복잡도를줄이기위하여분류규칙, 검색스트링등의분류정보가실시간으로변경되지않는다고가정하였다. 상태천이그래프를소자에구현할경우패턴정보들을현장에서업데이트가능해야하므로램에저장하여관리한다. 업데이트된패턴은상태천이그래프의형태로램에저장되므로패턴이업데이트될때마다 FPGA를새로구성해야하는기존의 H/W 기반패턴매칭기에비해업데이트시걸리는시간이적다. 패턴매칭기회로는램에저장된상태천이그래프의엔트리들을읽어이용하여검색한다. 고속실시간패턴매칭기는임의의패턴을램에관리하면서빠른시간에함수연산을수행하기위하여많은설계제약조건들이있다. 제안된패턴매칭기의상태천이그래프실행회로구조를그림 7(a) 에보였으며, 그림 7(b) 에한상태천이그래프임플리컨트엔트리를수행하는유한상태기계회로를보였다. 제안된상태천이구조는 입력 Current Next state state 출력 가 state1 state2 나 state2 state3 다 state3 state4 가나다 control 출력 라 state4 state5 마 state5 state0 가나다라마 control 출력 (a) 검색스트링1 검색스트링2 가나나다다라마 입력 Current Next state state 출력 가 state1 state2 나 state1 state3 나 state2 state3 다 state3 state4 가나다 control 출력 라 state4 state5 마 state5 state0 나다라마 control 출력 (b) 그림 6. 검색하는스트링들이서로겹치는경우의검색예 (a) 시작이동일한한스트링이다른스트링에포함되는경우, 두스트링 가나다 와 가나다라마 를동시에검색하는예, (b) 두검색스트링의시작이동일하지않지만한스트링이다른스트링에포함되는경우에두스트링을검색하는예 천이에다수의클럭이필요하며한상태의입력과입력스트림들의임플리컨트수에영향을받는다. 한패킷입력에대한실행시간 (latency) 은가변적이므로, 패턴매칭기에서상태천이표를실행도중패킷입력을받을것인지말것인가를경우에따라결정하여입력을받는다. 패턴매칭기의전단에입력된패킷을저장하는큐가있으며, 큐는패턴매칭기로부터 request 신호를받으면 1 클럭내에패킷을패턴매칭기로출력한다. 상태천이가발생한경우, current state의마지막임플리컨트를읽은경우, 그림 7(b) FSM의 ST1에서입력을기다리는경우패턴매칭기는 request를생성하여큐로전송한다. 한상태천이그래프의엔트리에해당하는 STG 임플리컨트엔트리들은순차적으로실행되며, 한 -> 1024
논문 / 네트워크침입탐지시스템에서고속패턴매칭기의설계및구현 RAM 상의 STG 구조. Reset Implicant #1. Implicant #2. Comparison ok. State1 state 1. state 2. State 1 00-10- 01-11- 00-10- 01-11- -00 State 2-00 -01-10 -11 1-- Comparison ok. State 2 State 3 state 1. state 2. state 2. (a) -01-11 0-- -10 State 3 1-- 0-- Comparison ok. state 1. state 2. 그림 8. 패턴매칭을위하여 RAM 상에구성된 STG 구조의예 RAM 상의 STG 구조. Reset Implicant #1. Implicant #2. 00- State 1 10-01- 11- Comparison ok State1 state 2. (b) 10-01- 11- -00 State 2-01 -10-11 그림 7. 제안된패턴매칭기의회로구조 (a) 제안된패턴매칭기의 STG 실행구조, (b) 한 STG 임플리컨트엔트리를수행하는유한상태기계회로 1-- State 2 State 3-01 -11 0-- Comparison ok. state 2. state 2. -10 STG 엔트리내의입력임플리컨트를비교하는과정중에는패킷입력을받지않는다. 입력된패킷에대해 STG의한엔트리의모든 STG 임플리컨트엔트리를비교한후해당되는패턴이없는경우는초기상태로천이하면서다음패킷을입력받는다. 그림 8에패턴매칭을위하여램상에구성된 STG 구조의예를보인다. STG의모든입력의합집합이전체입력집합 ( 항등함수 ) 이되어야하지만, 지정되지않는입력조건들에대한임플리컨트들을지정하고비교하는것은실행시간의부담이크므로, 필요한입력임플리컨트조건들을표현하고그외의입력조건들인경우초기상태로천이하도록설계하였다. 그림 9는 RAM 상에구성된 initial state로의천이를생략한개선된 STG 구조의예를보인다. 입력된패킷이 STG 임플리컨트엔트리에해당되면 next state STG 엔트리의주소로천이하면서다음패킷을읽는다. 모든 STG 임플리컨트엔트리의천이과정중 output flag가유효하면 output control 신호를출력한다. 제안된패턴매칭기의상태천이표는출력함수와 next state를표현하기위하여입력변수 (input variable) 와입력시퀀스변수 (input sequence variable) 들로표현하며패턴매칭소자에서입력받는 State 3 0-- Comparison ok. 그림 9. RAM 상에구성된 STG 구조의예 (initial state 로의천이생략 ) 상태천이표의예를그림 10에보였다. 상태천이그래프는현재상태와입력 (input function) 에의해출력과다음상태가결정된다. 패턴매칭기에서함수의기능은진리표, SOPs, POSs, 임플리컨트, BDD(Binary Decision Diagram) 등다양한방법으로표현이가능하다. 두함수의연산과정은효율적인 BDD의경우 O(# BDD nodes) 로패턴매칭기의구현에다수의시간과클럭이필요하다 [14][15][16]. 제안된패턴매칭기는회로의구현복잡도를줄이기위하여함수를임플리컨트로표현하고, 상태천이표의엔트리를다시함수의임플리컨트단위로분류하였다. 임플리컨트는입력된패킷과쉽게연산이가능하므로회로의구현복잡도가많이개선되는효과가있다. 함수를 product term 또는다수의임플리컨트로표현한예를그림 11에보인다. 함수의표현에사용되는변수의값은 0, 1, 또는 don't-care 값을가질수있으며, 다수의변수의 product로구성되는임플리컨트는변수들의값과 don't-care 필터로표현이 1025
한국통신학회논문지 '08-11 Vol. 33 No. 11 Input Product Term (value, filter) 1(0100, 0101) 2(0101, 0011) 3(0101, 0011) 4(0100, 0101) 5(0101, 0010) 6(0100, 1001) 7(0101, 0111) 8(0100, 1001) 9(0100, 0010) 10(0100, 0100) 11(0101, 0011) 12(0101, 0011) 13(0100, 1111) 14(0100, 0011) Input Current Next Sequence Flag state state (value) Output 0000 0 st0 st1 000000 0000 0 st0 st4 000000 0000 1 st0 st8 000000 ---- 1 st1 st2 000000 ---- 1 st2 st3 000000 ---- 1 st3 st0 Output 1 ---- 1 st4 st5 000000 ---- 1 st5 st6 000000 ---- 1 st6 st7 000000 ---- 1 st7 st0 Output 2 ---- 1 st8 st9 000000 ---- 1 st9 st10 000000 ---- 1 st10 st11 000000 Output ---- 1 st11 st0 3 그림 10. 패턴매칭소자에서입력받는상태천이표의예 Implicant representation = value +don t-care filter. Value : 1000, don t-case filter : 0101. Product termimplicant 1-0- = or Value : 1001, don t-case filter : 0101. or Value : 1100, don t-case filter : 0101. or Value : 1101, don t-case filter : 0101. 그림 11. 제안된패턴매칭회로의임플리컨트표현가능하다. 하나의임플리컨트는다수의입력큐브또는벡터들을동시에표현할수있다. 제안된패턴매칭기는입력되는스트림값이상태천이표의입력입플리컨트값을비교하여상태 표 1. RAM에저장된 STG 엔트리의필드 STG entry field 설명 Entry valid flag 엔트리의유효성 ('1' 인경우유효한엔트리 ) Implicant value STG 입력 implicant value Implicant filter 입력 STG 입력 implicant don't-care filter Input function의 last implicant 인지를표현하는 fl Flag(last im ag (1 인경우유효한 input) plicant) 입력을받을것인지를결정하는 control 정보 입력 seq Sequence value 검색스트링의입력순서번호가있는경우, 입력의순서번호를표현하는 implicant value uence Sequence flag 검색스트링의입력순서번호가있는경우, 입력순서번호의 don't-care filter Current state 현재 state를표현하는큐브 Next state 다음 state를표현하는큐브 입력이 STG 입력에포함되는경우 Valid flag 출력신호의유효정보 출력 (1 인경우유효한 input) Control sig 입력이 STG 입력에포함되는경우출력신호 nals 또는 control signal set 의 link 천이를수행하며, 입력된값이입력임플리컨트의부분집합인지여부에대한검사는다음과같이계산할수있다. 입력된패킷의한변수가이 STG 임플리컨트의한변수의부분집합인지의검사는식 (1) 과표 1과같이계산이가능하다. 식 (1) 에서변수임플리케이션 (variable implication) 값이 1인경우입력이임플리컨트의부분집합인것을의미한다. 수식에서 + 는비트단위 OR연산, 는비트단위 AND 연산을뜻한다. (1) 임플리컨트의변수수를 n, 식 1의변수 v에대한임플리케이션을 으로표현할경우, 다수의변수들을포함하는입력벡터는수식 2와같이동시에병렬로계산이가능하다. 식 2에서 product term 임플리케이션값이 1인경우입력벡터가 STG 입력임플리컨트의부분집합인것을의미한다. (2) 1026
논문 / 네트워크침입탐지시스템에서고속패턴매칭기의설계및구현 표 2. 패턴매칭기의처리율 ( 상태천이단위 ) 예 Link speed Max. throughput Min 자료 throughput 자료 stream 경로 Clock cycle 1 Gbits/s 3,000 K frame/s 333 ns (or 512 ns) 8 bits @ 125, 128 Mhz 16 bits @ 62.5, 64 Mhz 8 ns, 8.19 ns 16.38 ns, 16 ns 32 bits @ 31.25 Mhz 32.77 ns 20 bits @ 125, 128 Mhz 8 ns, 8.19 ns 2.5 Gbits/s 10 Gbits/s 6,000 K frame/s 26,000 K frame/s 167 ns 10 ns 32 bits @ 100 Mhz 40 bits @ 62.5, 64 Mhz 64 bits @ 180 Mhz 80 bits @ 125, 128 Mhz 10.24 ns 16.38 ns, 16 ns 5.69 ns 8 ns, 8.19 ns 128 @ 80 Mhz 12.8 ns 제안된패턴매칭기는그림 11의각입력임플리컨트들로다시분류된상태천이표를램에관리하며, 표1에각 RAM 엔트리의필드를보인다. 자료의전송용량에따라최소길이자료의최대처리율 (throughput), 최소길이자료의프로세싱을위한처리율, 자료의데이터버스, 패턴매칭기의처리율 ( 상태천이단위 ) 의예를표 2에보인다. 제안된패턴매칭기는임플리컨트를입력받아상태천이를수행하는데 3 클럭이필요하며, 각상태의임플리컨트의수에의해영향을받는다. 하나의임플리컨트는다수의패턴을표현할수있다. 자료입력을검색하기위하여상태천이의평균입력임플리컨트수가 5 이하인경우, 128 bits @ 125Mhz 또는 64 bits @ 240Mhz로사용하여 1Gbits/s의입력스트림을검색할수있다. 한상태천이엔트리에서 5개의입력임플리컨트를동시에비교하는경우, 24 bits @ 125 Mhz, 48 bits @ 62.5 Mhz, 또는 96 bits @ 31.25 Mhz로 1Gb/s의입력스트림을검색할수있다. 상태천이엔트리각상태의평균사용하는임플리컨트수의입력을동시에비교하는경우, 한번의상태천이에 3 클럭이소요되므로아래표 2에서제시된패턴매칭기의처리율 /3 으로예측할수있다. 제안된패턴매칭기는용량확장을위하여다수의검색모듈을직렬또는병렬로연결하여검색이가능하다. 다수의검색모듈을병렬로 그림 12. 구현된패턴매칭기의시뮬레이션실험결과 구성하는경우, STG를분할하여동일한입력패킷에입력받아동시에검색할수있다. 패턴정보를 RAM에저장하므로검색해야할패턴이늘어날수록 RAM 용량이늘어나게되지만, STG 엔트리수에따른 RAM 용량예측결과, STG 엔트리수가 8192개일경우최대 3MB의 RAM을사용하므로오버헤드가크지않다. Ⅴ. 실험결과 제안한패턴매칭기는 VHDL 언어로구현하였으며, 구현된매칭기는 Modelsim 시뮬레이터로기능을검증하였다. 본문에서사용한그림 3과그림 11 의예제상태천이표를입력받아패턴매칭을수행하는실험결과를그림 12에보였다. 패킷을입력받아패턴을검색한결과는그림 12에서 high 값으로전이된 flag_d신호로확인할수있다. 표 3은시뮬레이션결과패킷이입력되었을때패턴매칭을위해걸리는클럭이기존해시구조패턴매칭기와비교하여평균 90.6% 감소하였음을보인다. 실험을통하여제안된구조의패턴매칭기가고속으로입력패킷을검색할수있음을보였다. 표 3. 해시구조패턴매칭기와제안된검색기의클럭사이클비교 입력해시구조패턴제안된구조감소율라인수매칭기 128 4,226,382 396,499 90.6 % 256 8,452,735 792,959 90.6 % 512 16,905,561 1,584,070 90.6 % 1027
한국통신학회논문지 '08-11 Vol. 33 No. 11 Ⅵ. 결론본논문에서는패턴을입력받아입력패킷과비교하는알고리듬을제안하고, 고속으로패턴매칭을할수있는회로를설계하고구현하였다. 현재상용패턴매칭기는대부분소프트웨어기반으로구현되어있으며, 하드웨어로구현된패턴매칭기는속도가빠르다는장점이있으나패턴의업데이트가어렵다는단점이있다. 제안된패턴매칭기는하드웨어로구현되어동작속도가빠르며패턴정보를 RAM에저장하므로업데이트가빠르다는장점이있으며, 패턴저장을위해요구되는 RAM 용량은최대 3MB로기존의하드웨어기반패턴매칭기에서의요구량보다적다. 구현복잡도를줄이기위하여비교할패턴, 입력패킷등의정보는동작중변경되지않는다고가정하였으며, 상태천이그래프를임플리컨트로다시분할하여수행하도록설계하였다. 실험결과를통하여제안된패턴매칭기가고속으로동작할수있음을보였으며, 구조가간단하고하드웨어리소스의사용량이작아네트워크침입탐지시스템에서패턴매칭을위하여효율적으로사용될수있을것으로기대된다. 참고문헌 [1] M. Fisk and G. Varghese, An Analysis of Fast String Matching Applied to Content-based Forwarding and Intrusion Detection, Technical Report CS2001-0670, University of California - San Diego, 2002. [2] N. Desai, Increasing Performance in High Speed NIDS: A look at Snort's Internals, Feb. 2002. [3] I. Charitakis, K. Anagnostakis, and E. Markatos, An Active Traffic Splitter Architecture for Intrusion Detection, in Proc. IEEE/ACM International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, Orlando, Florida, pp.238-241, Oct. 2003. [4] Y. Cho, W. Mangione-Smith, Deep Packet Filter with Dedicated Logic and Read Only Memories, in Proc. IEEE Symposium on Field-Programmable Custom Computing Machines, pp.125-134, Apr. 2004. [5] M. Aldwairi, T. Conte, and P. Franzon, Configurable String Matching Hardware for Speeding up Intrusion Detection, ACM SIGARCH Computer Architecture News, Vol.33, No.1, pp.99-107, Jan. 2005. [6] R. Sidhu and V. Prasanna, Fast Regular Expression Matching Using FPGAs, in Proc. IEEE Symposium on Field-Programmable Custom Machines, Rohnert Park, CA, pp.227-238, May 2001. [7] C. Hoffman and M. O'Donnell, Pattern Matching in Trees, Journal of the ACM, Vol.29, No.1, pp.68-95, Jan. 1982. [8] R. Karp and M. Rabin, Efficient Randomized Pattern-Matching Algorithms, IBM Journal of Research and Development, Vol.31, No.2, pp.249-260, Mar. 1987. [9] D. Pao, C. Liu, A. Wu, L. Yeung, and K. Chan, Efficient Hardware Architecture for Fast IP Address Lookup, in Proc. IEEE Infocom, New York, NY, Vol.2, pp.555-561, Jun. 2002. [10] S. Iyer, R. R. Kompella, and A. Shelat, ClassiPI: An Architecture for Fast and Flexible Packet Classification, IEEE Network Magazine, pp.24-32, Apr. 2001. [11] A. Feldmann and S. Muthukrishnan, Tradeoffs for Packet Classification, AT&T Technical Report, 1999. [12] A. Parakash and A. Aziz, OC-3072 Packet Classification Using BDDs and Pipelined SRAMs, in Proc. Hot Interconnects, Stanford, CA, pp.15-20, Aug. 2001. [13] J. Park and I. Jang, Parallelisation of Trie-based Longest Prefix Matching for Fast IP Address Lookups, Electronics Letters, Vol.38, No.25. pp.1757-1759, Dec. 2002. [14] S. Brown, R. Francis, J. Rose, and Z. Vranesic, Field-Programmable Gate Arrays, Kluwer Academic Publisher, 1992. [15] P. Ashar, S. Devadas, and A. Newton, Sequential Logic Synthesis, Kluwer Academic Publisher, 1992. [16] G. De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill, 1994. 1028
논문 / 네트워크침입탐지시스템에서고속패턴매칭기의설계및구현 윤여찬 (Yeo-Chan Yoon) 준회원 2007년 2월서강대학교전자공학과졸업 2007년 3월 ~ 현재서강대학교전자공학과대학원 CAD & Embedded Systems 연구실석사과정 < 관심분야 > 테스트용이화설계, NIDS 황선영 (Sun-Young Hwang) 정회원 1976년 2월서울대학교전자공학과졸업 1978년 2월한국과학원전기및전자공학과공학석사 1986년 10월미국 Stanford 대학전자공학박사 1976년 ~1981년삼성반도체주식회사연구원, 팀장 1986년 ~1989년 Stanford 대학 Center for Integrated System 연구소책임연구원Fairchild Semiconductor Palo Alto Research Center 기술자문 1989년 ~1992년삼성전자 ( 주 ) 반도체기술자문 1989년 3월 ~ 현재서강대학교전자공학과교수 < 관심분야 > SoC 설계및 framework 구성, CAD시스템, Com. Architecture 및 DSP System Design 등 1029