본문 바로가기 주메뉴 바로가기
22대 대한민국 국회 국회정보길라잡이 국회의원검색
회원가입 로그인
HOME

정보검색

소장정보 검색

국회도서관 홈으로 정보검색 소장정보 검색
결과 내 검색 동의어 포함
결과 내 검색 동의어 포함

-

목차보기

Title Page

국문 초록

Abstract

Contents

List of Abbreviations 17

Chapter 1. Introduction 18

1.1. Background and Motivation 19

1.1.1. Internet Worms 19

1.1.2. Signature-based Intrusion Detection 20

1.1.3. Pattern Matching Algorithms 23

1.2. Previous Work 27

1.2.1. Internet-Wide Vulnerability Estimation 27

1.2.2. Characteristics of the MWM Algorithm 28

1.3. Contributions and Outline of This Dissertation 30

Chapter 2. Botnet-Nurtured Worm: Using Information Collected by Botnets to Create Importance Scanning Worms 36

2.1. Introduction 36

2.2. Is the Importance Scanning Worm Practical? 39

2.3. Botnet-Nurtured Worm: Problem definition 43

2.3.1. What is a 'Botnet-Nurtured Worm'? 43

2.3.2. Network Set-Up 44

2.3.3. Objectives and Preliminaries 46

2.4. Botnet-Nurtured Worm: Sample Collection 49

2.4.1. Examine Filtering Threshold of Firewall 49

2.4.2. How to Collect Samples 52

2.5. Botnet-Nurtured Worm: Estimation of the Vulnerable-Host Group Distribution 57

2.5.1. Point Estimator of Proportion of Vulnerable Hosts in a Group 58

2.5.2. Required Group Sample Size 60

2.5.3. Estimating Vulnerable-Host Group Distribution 62

2.5.4. Example 63

2.6. Botnet-Nurtured worm: Validation 63

2.6.1. Description of Network Set-Up 64

2.6.2. Experiments under Different Number of Independent Trials 66

2.6.3. Experiments under Different Sample Sizes 67

2.6.4. Experiments under Different Number of Bots 69

2.6.5. Experiments under Different Scan Rates 70

2.6.6. Experiments under Different Probabilities that a Target System Replies for a Scan 71

Chapter 3. L+1-MWM: Bad-Character SHIFT Table With A Multi-Byte Search Unit(이미지참조) 73

3.1. Introduction 73

3.2. Extension of the Length of the Shortest Pattern 75

3.2.1. Analysis of the Snort Rule Sets 75

3.2.2. Influence of Length Extension of the Shortest Patterns 76

3.3. Operation of the L+1-MWM Algorithm based on LSP Extension(이미지참조) 78

3.3.1. Overall Operation of the L+1-MWM Algorithm(이미지참조) 78

3.3.2. The Preprocessing Stage 80

3.3.3. The Scanning Stage 84

3.3.4. Example 88

3.4. Validation of the L+1-MWM Algorithm(이미지참조) 92

3.5. Performance Evaluation 95

3.5.1. Expected Performance 95

3.5.2. Experiments 97

Chapter 4. BLAST: B-LAyered Bad-Character SHIFT Tables With A Single-Byte Search Unit 110

4.1. Introduction 110

4.2. Operation of the BLAST algorithm 111

4.2.1. Overall Operation of the BLAST Algorithm 111

4.2.2. The Preprocessing Stage 114

4.2.3. The Scanning Stage 118

4.2.4. Example 121

4.3. Layering Bad-Character SHIFT Tables 125

4.4. Performance Evaluation 131

4.4.1. Data Structure Analysis 131

4.4.2. Running Time Analysis 132

4.4.3. Experiments 135

Chapter 5. Conclusion 147

Chapter 6. Appendix 151

Bibliography 156

List of Tables

Table 2.1: Notation of parameters 47

Table 3.1: The SHIFT table comparison of the MWM algorithm and the... 96

Table 3.2: Number of each shift value in the SHIFT table of Table 3.1 96

Table 4.1: The SHIFT, HASH and PREFIX tables obtained from a set of... 124

Table 4.2: Analysis results of the MWM algorithm, the L+1-MWM algo-...(이미지참조) 131

Table 6.1: A vulnerable-host group distribution table, where parameters... 152

Table 6.2: Continued from Table.6.1. 153

Table 6.3: Analysis of patterns in Snort v2.0 rule sets 154

Table 6.4: Continued from Table.6.3 155

List of Figures

Figure 1.1: Main elements of the signature-based NIDS in an inline position 21

Figure 1.2: Classification of a skip-based algorithm. Here, the proposed... 25

Figure 1.3: Scanning example of the MWM algorithm; the bad-character... 29

Figure 1.4: Research areas in this dissertation, which are marked with bold... 31

Figure 2.1: Attacker's network set-up for remote scanning: a 'white circle'... 45

Figure 2.2: Scanning paradigm for collecting categorical data with two pos-... 53

Figure 2.3: Example of an attacker's network set-up, where... 56

Figure 2.4: MSE under different numbers of independent trials(Ns) and...(이미지참조) 66

Figure 2.5: MSE under different group sample sizes (n(i)) and under various... 67

Figure 2.6: MSE under different numbers of Bots(NB) and different distri-...(이미지참조) 69

Figure 2.7: MSE under different scan rates (sb(i)) and different distribu-...(이미지참조) 71

Figure 2.8: MSE under different probabilities that a target system replies... 72

Figure 3.1: Flowchart of the preprocessing stage in the L+1-MWM algorithm(이미지참조) 79

Figure 3.2: Flowchart of the scanning stage in the L+1-MWM algorithm(이미지참조) 81

Figure 3.3: Construction of strings of size mLSP (LSP) from a set of pat-... 88

Figure 3.4: The SHIFT, HASH and PREFIX tables obtained from Fig.3.3,... 89

Figure 3.5: The scanning process of the text in the L+1-MWM algorithm(이미지참조) 90

Figure 3.6: Pattern search time comparison by varying LSP for normal... 97

Figure 3.7: Pattern search time comparison by varying LSP for MIT-... 98

Figure 3.8: Pattern search time comparison by varying LSP for DEFCON... 98

Figure 3.9: Pattern search time comparison by varying LSP using real on-... 99

Figure 3.10: Snort running time comparison by varying LSP using traffic... 101

Figure 3.11: Pattern search time comparison by varying LSP using traffic... 102

Figure 3.12: Pattern search time comparison by various numbers of signa-... 102

Figure 3.13: Pattern search time comparison by various numbers of signa-... 103

Figure 3.14: Pattern search time comparison by various numbers of signa-... 104

Figure 3.15: Pattern search time comparison by various numbers of signa-... 104

Figure 3.16: Snort running time comparison by various numbers of signa-... 105

Figure 3.17: Pattern search time comparison by various numbers of signa-... 105

Figure 3.18: Pattern search time comparison for different system processors 109

Figure 4.1: Construction of strings of size LSP from a set of patterns,... 122

Figure 4.2: An illustration for setting up the SHIFTL0, SHIFTL1, HASH...(이미지참조) 123

Figure 4.3: The scanning process of the text in the BLAST algorithm. 126

Figure 4.4: Pattern search time comparison by varying LSP for normal... 135

Figure 4.5: Pattern search time comparison by varying LSP for MIT-... 136

Figure 4.6: Pattern search time comparison by varying LSP for DEFCON10... 137

Figure 4.7: Pattern search time comparison by varying LSP using traffic... 137

Figure 4.8: Snort running time comparison by varying LSP using traffic... 139

Figure 4.9: Pattern search time comparison by various numbers of signatures... 139

Figure 4.10: Pattern search time comparison by various numbers of signa-... 142

Figure 4.11: Pattern search time comparison by various numbers of signa-... 143

Figure 4.12: Pattern search time comparison by various numbers of signa-... 143

Figure 4.13: Snort running time comparison by various numbers of signa- 144

Figure 4.14: Pattern search time comparison for different system processors 145

초록보기

 시그너쳐 기반 네트워크 침입 탐지 시스템(Network Intrusion Detection System, NIDS)은 '시그너쳐 분석' 과정을 통해 알려진 시그너쳐 패턴과 데이터 트래픽을 비교함으로써 공격을 식별한다. 여기서, '시그너쳐'는 침입을 표현하며 '패턴'은 시그너쳐 내에 존재하는 특정한 문자열을 의미한다. 즉, 시그너쳐 분석을 통해 연속된 패킷을 해석하고 패킷 내 문자열과 시그너쳐 집합을 비교함으로써 침입 패킷을 식별해 낸다. 이 과정에서 고속의 시그너쳐 분석, 특히 고속의 패턴 정합, 과정은 실시간 침입 탐지를 가능하게 하는 핵심 역할을 수행하게 된다. 고속의 패턴 정합의 중요성은, 패턴 정합 시간이 침입 탐지 시스템 동작 시간의 40%에서 70%를 차지한다는 분석 결과에 의해 뒷받침된다. 본 학위 논문에서는 이러한 목적을 달성하기 위하여, 먼저 시그너쳐 분석과정에서 기본이 되는 침입을 설계하기 위한 새로운 실현가능한 기법을 제안한다. 또한, 새로운 두 가지 패턴 정합 알고리즘들을 제안한다. 먼저, 단일 바이트 탐색 유닛에 기반한 알고리즘의 자료구조를 최적화하며, 다음으로 다중 바이트 탐색 유닛에 기반한 알고리즘의 자료구조를 최적화한다. 구체적으로는, 다음의 세 가지 주목할 만한 결과를 제시한다.

1. 공격자 관점에서 중요 스케닝 웜 설계과정의 핵심 요소인 인터넷상에 위치한 취약한 호스트들의 분포를 유추하기 위한 최초의 실현 가능한 근사 화 방안: 인터넷 웜의 전파과정을 단순화 시키면서 "어떻게 인터넷상의 취약한 정보를 수집할 수 있는가?" 하는 문제에 대한 답을 얻기 위한 방안은 무엇일까? 이 문제를 해결하기 위하여, 공격자는 제안되어진 최대 가능성 근사 화(Maximum Likelihood Estimation, MLE)에 기반한 인터넷 취약성 분석 과정에서 봇넷을 이용한다. 봇넷은 악성 프로그램(일명, 봇)들의 분산 네트워크이다. MLE 이론에 기초한 이론적 분석결과와 시뮬레이션을 통한 실험적 검증 과정을 통해, 제안되어진 방안이 인터넷 상의 취약성 분포를 근사 화하는데 있어서 효과적임을 보인다. 즉, 근사화 되어진 취약성 분포가 인터넷 상의 실제 취약성 분포와 유사함을 보이도록 한다. 이를 뒷받침하기 위해, 타당한 샘플링 비율이 0.6%로 바운드되어 짐을 보인다.

2. 다중 탐색 유닛 기반의 새로운 다중 패턴 정합 알고리즘 (L+1-MWM): 이는 다중 탐색 유닛 기반의 알고리즘 성능이 시그너쳐 그룹에 존재하는 가장 짧은 패턴의 길이(Length of the Shortest Pattern, LSP)에 의해 저하된다는 문제 분석에 기반 하였으며, 그로 인한 부정적인 영향을 최소화하는 최적의 방안을 제안한다. 분석적 결과 및 실험적 결과에 기반하여 알고리즘의 유효성을 검증한다. 결과를 요약하면, L+1-MWM 알고리즘이 MWM 알고리즘에 비해 다양한 LSP값과 정상적인 트래픽의 탐색과정에서 평균 20%가량의 성능 향상을 보이며, 특히 LSP가 5이하인 경우에는 L+1-MWM 알고리즘이 평균 38.87%의 성능 향상을 보인다.

3. 단일 탐색 유닛 기반의 새로운 다중 패턴 정합 알고리즘 (B-LAyered bad-character SHIFT Table, BLAST): 다중 탐색 유닛에 기반한 다중 패턴 정합 알고리즘의 경우, 단일 탐색 유닛에 기반한 알고리즘에 비해 평균 시프트 값이 작아진다. 이를 극복하기 위하여, 단일 탐색 유닛에 기반한 여러 개의 나쁜 문자(bad-character) SHIFT테이블을 사용하는 다중 패턴 정합 알고리즘인 BLAST 알고리즘을 제안한다. 여기서, '나쁜 문자'란 텍스트와 패턴의 문자 비교과정에서 일치하지 않는 문자를 의미한다. 이는 다중 탐색 유닛 기반의 다중 패턴 정합 알고리즘과 같이, 많은 시그너쳐가 사용되어지는 상황의 문자열 탐색과정에서 좋은 성능을 보이며, 또한 다중 탐색 유닛 사용 과정에서 발생하는 평균 시프트 값의 감소 현상을 보완한다. 기본적으로 단일 탐색 유닛에 기반 함으로 인해, 기존의 다중 탐색 유닛을 사용하는 알고리즘에 비해 요구되어지는 메모리의 양도 줄일 수 있다. 분석적 및 실험적 결과에 기초하여 알고리즘의 유효성을 검증한다. 결과를 요약하면, 다양한 수의 시그너쳐와 공격 트래픽 하에서 BLAST알고리즘이 MWM 알고리즘에 비해 평균 236.12%의 성능향상을, L+1-MWM 알고리즘에 비해 평균 145.21%의 성능향상을 보인다.

본 학위 논문에서 기술된 위 세 가지 기법들은 시그너쳐 기반 고속의 네트워크 침입 탐지를 위한 최적의 패턴 정합 기법을 제공함으로써, 네트워크 기반 실시간 침입 탐지를 수행하는 시그너쳐 기반 고속의 네트워크 침입 탐지 시스템 설계를 가능하게 한다.

추천서가 (다양한 추천 자료를 만나보세요)

권호기사보기

권호기사 목록 테이블로 기사명, 저자명, 페이지, 원문, 기사목차 순으로 되어있습니다.
기사명 저자명 페이지 원문 기사목차