淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-1307201213583100
中文論文名稱 比較PCRE與RE2正規表達式函式庫在Snort入侵偵測系統中之效能
英文論文名稱 Comparing the Performance of PCRE and RE2 Regular Expression Libraries in the Snort Intrusion Detection System
校院名稱 淡江大學
系所名稱(中) 資訊工程學系碩士班
系所名稱(英) Department of Computer Science and Information Engineering
學年度 100
學期 2
出版年 101
研究生中文姓名 邱奕湶
研究生英文姓名 Yi-Chuan Chiu
學號 699410246
學位類別 碩士
語文別 中文
第二語文別 英文
口試日期 2012-07-02
論文頁數 61頁
口試委員 指導教授-蔡憶佳
委員-蔡憶佳
委員-陳伯榮
委員-林慶昌
中文關鍵字 網路攻擊  封包擷取  Snort  PCRE  RE2 
英文關鍵字 Network Attack  Packet Capture  Snort  PCRE  RE2 
學科別分類 學科別應用科學資訊工程
中文摘要 現今網路蓬勃發展導致網路攻擊不斷地變換型態,對於未知的攻擊防禦所以網路安全就相對的重要。大多網路對外防禦攻擊通常為防火牆與網路入侵偵測系統搭配,防火牆僅能阻擋非法的連線請求,當有一挾帶惡意攻擊的封包順利通過防火牆,網路入侵防禦系統就占了相當重要的角色。近年來最廣為使用的網路入侵偵測系統Snort因開放原始碼且容易進行修改,也有許多網站因應各式各樣的網路攻擊型態撰寫Snort規則散布於網路上供使用者取得,而Snort比對的正規表達式寫於Snort規則內故本研究將以Snort規則作為研究對象。
Snort經由PCRE(Perl Compatible Regular Expressions)正規表達式函式庫進行特徵碼比對,以判斷封包是否有挾帶異常的行為,本研究以Google發布的RE2正規表達式函數庫在Snort規則上進行修改,並以PCRE與RE2的CPU使用率、執行時間及記憶體使用多寡進行比較,結果證明RE2在進行Snort規則比對的執行時間而言較PCRE穩定。
英文摘要 A huge amount of online personal information has led to growing number of cyber-attacks. Most network defense strategies use firewalls and network intrusion detection systems. Firewalls can only block illegal connection requests, however, malicious packets can still get through the firewall. Therefore, network intrusion prevention systems play an important role in the defense of attacks. Snort is a commonly used network intrusion detection system. It is an open source software and easy to modify. Snort rules consist of formal descriptions of the attack patterns and through which Snort used to determine abnormal network traffics. The pattern is written in PCRE (perl compatible regular expression).
This study compares the use of Google's RE2 regular expression library and PCRE in Snort rules. Their cpu usages, execution time and memory amount are examined and the results showed RE2 has better performance than PCRE for certain patterns.
論文目次 目錄
目錄 III
圖目錄 IV
表目錄 V
第一章 緒論 1
1.1 研究背景 1
1.2 研究目的 2
第二章 相關研究 4
2.1 入侵防禦系統 4
2.2 正規表達式:非確定性自動機與確定性自動機 12
2.2.1 PCRE正規表達式函式庫 14
2.2.2 RE2正規表達式函式庫 20
2.2.2.1 剖析 23
2.2.2.2 簡化 24
2.2.2.3 編譯 24
2.2.2.4 比對 25
2.3 DARPA入侵偵測資料集 28
第三章 研究方法 29
3.1 系統環境 29
3.2 資料來源 29
3.3 正規表達式測試集 30
3.4 測試方法 32
第四章 實驗結果與討論 33
4.1 實驗結果 33
4.2 討論 39
第五章 結論與未來方向 40
參考文獻 41
附錄1 正規表達式用法 43
附錄2 PCRE進行比對程式碼 46
附錄3 RE2與PCRE比對效能圖 50
附錄4 英文論文 58

圖目錄
圖 1、PCRE指數時間 2
圖 2、RE2線性時間 2
圖 3、Snort執行過程 7
圖 4、Snort規則樹 10
圖 5、改進後的規則樹結構 12
圖 6、改進後的選項樹結構 12
圖 7、正規表達式轉換為非確定性自動機六種樣式 13
圖 8、PCRE比對方式(比對輸入字串abbb為例) 14
圖 9、PCRE比對流程圖 17
圖 10、ovector結構 19
圖 11、RE2比對方式(比對輸入字串abbb為例) 21
圖 12、非確定性自動機轉換成確定性自動機 23
圖 13、RE2比對流程圖 23
圖 14、比對字碼由0000(H)至FFFF(H) Unicode自動機圖形 25
圖 15、比對字碼由000000(H)至10FFFF(H) Unicode自動機圖形 25
圖 16、測試檔一:Email1 | URL系統耗用資源 33
圖 17、測試檔一:Email2 | URL系統耗用資源 34
圖 18、測試檔二:Email1 | URL系統耗用資源 35
圖 19、測試檔二:Email2 | URL系統耗用資源 36
圖 20、測試檔一:Email1系統耗用資源 50
圖 21、測試檔一:Email2系統耗用資源 51
圖 22、測試檔一:IP系統耗用資源 52
圖 23、測試檔一:URL系統耗用資源 53
圖 24、測試檔二:Email1系統耗用資源 54
圖 25、測試檔二:Email2系統耗用資源 55
圖 26、測試檔二:IP系統耗用資源 56
圖 27、測試檔二:URL系統耗用資源 57

表目錄
表 1、Snort三種模式與說明 6
表 2、Snort規則選項 9
表 3、Snort規則(以ddos.rules為例) 11
表 4、正規表達式的指令於虛擬機器內的指令 15
表 5、正規表達式四種樣式編碼 15
表 6、正規表達式a+b+比對aab於正規表達式虛擬機器執行 15
表 7、回溯(Backtracking)演算法執行於虛擬機器 16
表 8、PCRE比對函數 18
表 9、群組長度大小計算 19
表 10、Ken Thompson演算法執行於虛擬機器 21
表 11、部分Unicode位元序列 24
表 12、RE2比對函數 27
表 13、網路攻擊型態說明 28
表 14、DARPA’99測試資料說明 28
表 15、測試環境 29
表 16、測試檔案說明 30
表 17、正規表達式測試集來源 31
表 18、正規表達式測試集 31
表 19、Snort規則樣式(以smtp.rules為例) 32
表 20、PCRE與RE2時間比較(50次平均) 37
表 21、Snort規則功能相似正規表達式進行合併前(以smtp.rules為例) 38
表 22、Snort規則功能相似正規表達式進行合併後(以smtp.rules為例) 38
表 23、PCRE與RE2時間比較(Snort規則) 38
表 24、規則改寫 39
表 25、正規表達式用法 43
參考文獻 [1] 俄國士兵發動SpyEye殭屍網路攻擊 六個月狠撈美金320萬[http://tw.trendmicro.com/tw/about/news/pr/article/20111117061845.html], 2011
[2] RE2を試してみた。 - 初学者の箸置, [http://d.hatena.ne.jp/tkuro/20100317/1268807785], Mar 2010
[3] 蕭裕弘、賴冠輔、黃秀瓊、姜瑋婷,“以SystemC語言實作應用於Snort入侵偵測系統之PCRE比對引擎,”民生電子研討會, pp. 311-316, 2009。
[4] 谷曉鋼、江榮安、趙銘偉,“Snort 的高效規則匹配演算法,”計算機工程,Vol. 3, No. 18, pp. 155-157, 2006。
[5] 呂東偉、孟慶端、梁祖華、徐林,“Snort規則匹配過程改進,”計算機應用與軟件,Vol. 27, No. 10, pp. 123-125, 2006。
[6] 張浩置、楊中皇,“基於規則分類的網路入侵偵測系統之效能分析與改善,”2009聯合國際研討會,2009年11月,輔仁大學。
[7] 史美林、錢俊、許超,“入侵偵測系統資料集評測研究,”計算機科學,Vol. 33, No. 8, pp. 1-8, 2006。
[8] 傅仁宏,「基於RE2的應用層封包過濾系統」,碩士論文,資訊工程學系在職專班,淡江大學,新北市, 2010。
[9] 關凡宇,「以成本角度選擇網頁應用程式防禦策略」,碩士論文,資訊工程系,大同大學,臺北市, 2010。
[10] Performance comparison of regular expression engines, [http://sljit.sourceforge.net/regex_perf.html], Oct 2011
[11] DARPA Intrusion Detection Evaluation, [http://www.ll.mit.edu/mission/communications/CST/darpa.html]
[12] PCRE - Perl Compatible Regular Expressions, [http://www.pcre.org/]
[13] PCRE – Perl Compatible Regular Expression Library, [http://www.haifux.org/lectures/156/PCRE-Perl_Compatible_Regular_Expression_Library.pdf]
[14] Perl Compatible Regular Expressions - Wikipedia, the free encyclopedia, [http://en.wikipedia.org/wiki/Perl_Compatible_Regular_Expressions]
[15] re2 - an efficient, principled regular expression library - Google Project Hosting, [http://code.google.com/p/re2/]
[16] Regular Expression Matching Can Be Simple And Fast, [http://swtch.com/~rsc/regexp/regexp1.html]
[17] Implementing Regular Expressions, [http://swtch.com/~rsc/regexp/]
[18] Russ Cox, RE2: a principled approach to regular expression matching, [http://google-opensource.blogspot.com/2010/03/re2-principled-approach-to-regular.html], Mar 2010
[19] Snort, [http://www.snort.org]
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2013-07-31公開。
  • 同意授權瀏覽/列印電子全文服務,於2013-07-31起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信