네트워크 침입 탐지 시스템에서 고속 패턴 매칭기의 설계 및 구현
Design and Impelementation of High Speed Pattern Matcher in Network Intrusion Detection System
- 주제(키워드) NIDS , Pattern Matching
- 발행기관 서강대학교 대학원
- 지도교수 황선영
- 발행년도 2009
- 학위수여년월 2009. 2
- 학위명 석사
- 실제URI http://www.dcollection.net/handler/sogang/000000044916
- 본문언어 한국어
초록/요약
본 논문은 네트워크 침입 탐지 시스템에서 고속 패턴 매칭 알고리듬과 그 구조를 제안한다. 제안한 알고리듬은 실시간 입력 패킷에서 특정 패턴을 검사하며 정확한 문자열, 문자열 값의 범위, 그리고 문자열 값의 조합 등을 검색한다. 본 연구에서는 입력 패킷과 패턴은 동시에 겹치는 문자열들을 검색하기 위해 입력 임플리컨트 단위로 분할하였다. 제안한 패턴 매칭 구조는 상태 천이 그래프와 입력된 문자열을 입력으로 사용한다. 제안한 패턴 매칭기는 VHDL 언어로 모델링하여 구현하였으며, 성능분석을 통하여 제안한 기법의 적절성을 검증하였다.
more목차
제 1 장 서론 = 1
제 2 장 관련 연구 = 3
제 1 절 소프트웨어 기반 방식 = 3
1.1 절대문자열 비교 알고리듬 = 3
1.2 Boyer-Moore 알고리듬 = 4
1.3 Aho-Corasick 알고리듬 = 6
1.4 Knuth-Morriss-Pratt 알고리듬 = 6
제 2 절 하드웨어 기반 방식 = 8
2.1 트리 구조 = 8
2.2 해시 구조 = 9
2.3 해시와 트리를 조합한 다단 검색 구조 = 10
제 3 절 Content-Addressable Memory 기반 방식 = 11
제 3 장 제안한 패턴 매칭 알고리듬 = 12
제 1 절 제안한 패턴 매칭 알고리듬 = 12
1.1 패턴 매칭 알고리듬의 흐름도 = 12
1.2 제안한 패턴 매칭 알고리듬의 의사 코드 = 15
제 2 절 검색하는 패턴들이 중복되는 경우의 처리 방법 = 17
제 4 장 제안한 패턴 매칭 회로의 구조 = 21
제 1 절 패턴 매칭기의 구조 = 21
1.1 상태 천이 그래프 = 21
1.2 RAM 상에 구성되는 STG = 24
제 2 절 함수의 임플리컨트 표현 = 28
제 3 절 제안한 패턴 매칭기의 처리율 = 31
제 5 장 실험 결과 = 34
제 6 장 결론 및 추후과제 = 36
참고문헌 = 37
그림목차
그림 2-1. 절대문자열 비교 알고리듬 = 4
그림 2-2. Boyer-Moore 알고리듬 = 5
그림 2-3. Aho-Corasick 알고리듬을 이용하여 작성된 유한상태기계 = 6
그림 2-4. Knuth-Morris-Pratt 알고리듬 = 7
그림 3-1. 제안한 패턴 매칭기의 흐름도 = 13
그림 3-2. 상태천이 그래프를 표현하는 상태천이 표 = 14
그림 3-3. 제안한 패턴 매칭 알고리듬의 의사코드 = 16
그림 3-4. 검색하는 스트링들이 중복되는 조합의 예 = 18
그림 3-5. 검색하는 스트링들이 중복되는 조합의 경우 = 19
그림 3-6. 검색하는 스트링들이 서로 겹치는 경우의 검색 예 = 20
그림 4-1. 제안한 패턴 매칭기의 회로 구조 = 23
그림 4-2. 패턴 매칭을 위하여 RAM상에 구성된 STG구조의 예 = 25
그림 4-3. RAM상에 구성된 STG 구조의 예(initial state로의 천이 생략) = 26
그림 4-4. 패턴 매칭 소자에서 입력받는 상태천이표의 예 = 27
그림 4-5. 제안한 패턴 매칭 회로의 임플리컨트의 표현 = 28
그림 5-1. 구현된 패턴 매칭기의 시뮬레이션 실험 결과 = 35
표목차
표 4-1. RAM에 저장된 STG 엔트리의 필드 = 31
표 4-2. 패턴 매칭기의 처리율(상태천이 단위) 예 = 33
표 5-1. 해시 구조 패턴 매칭기와 제안한 검색기의 클럭 사이클 비교 = 35
