[[alternative]]Application layer packet filter system based on RE2

碩士[[abstract]]隨著網路的快速發展，各式各樣的網路服務開始出現，每種服務運作時皆或多或少要佔用些許的網路頻寛，而要如何在有限的頻寛下能讓各種服務皆能正常運作，有效的頻寛分配與管理便成了相當重要的課題。 要能有效達到頻寛分配，首先便要能有效地分辨各種的通訊協定，然而舊有的封包過濾器皆未能有效地辨識P2P這類型的封包，因此本研究採用一種以正則表示法來分析應用層資訊的封包過濾器，並希望透過修改正則表示法函式庫的方式來提昇應用層封包過濾器的效能。本研究裏採用RE2這套新公佈的正則表式法函式庫為實驗組，原系統內建的GNU C Regex函式庫為對照組，透過比較二者的執行效能以驗証是否在改用RE2函式庫後能有效提昇封包過濾的效能，並進而達成改善頻寛分配的效能。[[abstract]]With the fast development of internet, various kinds of network service appear. Every of them need to take some amount of bandwidth when it work, so how to make all kinds of service work smoothly under limit bandwidth becomes very important issue for proper bandwidth distribution and management. If we want to distribute the bandwidth properly , at first, we have to correctly distinguish the communication protocol. However, the current packet filters are not able to recognize the P2P packet effectly. Thus,this research adopt the packet filter using regular expression for analyzing the application layer informations, and want to promote the efficiency of application layer packet filter through modifying the regular expression library. This research take RE2, a new released regular expression library on google code, as experimental group, and the original build-in GNU C Regex library as control group. Through comparing the execution efficiency to verify if we can promote the efficiency of packet filter after adopting the RE2 library, and to achieve the goal of bandwidth distribution improvement.[[tableofcontents]]圖 目 錄 VI 表 目 錄 VII 第一章 緒論 1 1.1 研究動機 1 1.2 研究目的 2 第二章 相關文獻探討 4 2.1 L7-filter 探討 4 2.2 Regular Expression 探討 5 2.2.1 起源 5 2.2.2 正規化語言理論 6 2.2.3 自動機理論 8 2.2.4 正則表示式語法 11 2.3 Regex函式庫 13 2.4 RE2函式庫 17 2.4.1 歷史背景 17 2.4.2 資料處理流程 18 2.4.3 RE2的特性 25 第三章 研究方法 28 3.1 環境說明 28 3.1.1 系統環境 28 3.1.2 L7-filter安裝 29 3.1.3 資料來源 31 3.1.4 選用的Pattern 32 3.2 測試的方法 34 第四章 結果分析 36 4.1 單一封包比對分析 36 4.2 連續性封包比對分析 39 第五章 結論與未來展望 42 參考文獻 44 附錄---英文論文 46 圖 目 錄 圖2-1：a(bb)+a 的DFA圖形 8 圖2-2：a(bb)+a 的NFA圖形之一 9 圖2-3：a(bb)+a 的NFA圖形之二 9 圖2-4：用Thompson`s演算法判斷 abbb 11 圖2-5：Regex函式庫簡單示意圖 14 圖2-6：Full Unicode Automata Graph 21 圖2-7：NFA轉DFA圖形 26 圖3-1：L7-Filter.conf設定內容 30 圖3-2：截取ftp連線封包 33 圖4-1：Regex比對時間及CPU耗用率 40 圖4-2：RE2比對時間及CPU耗用率 40 表 目 錄 表2-1：POSIX BRE 語法表 12 表2-2：POSIX ERE語法表 13 表2-3：POSIX character classes語法表 13 表2-4：regex_t的資料結構 15 表2-5：cflags參數說明 15 表3-1：系統環境列表 28 表3-2：各Pattern之正則表達式列表 34 表4-1：單一封包Regex完成比對時間(10000次) 37 表4-2：單一封包RE2完成比對間(執行10000次) 37 表4-3：各Pattern單一比對執行時間(10000次) 38 表4-4：Regex及RE2比對時間 39 表4-5：Regex及RE2記憶體配置情形 單位: KB 41[[note]]學號: 795410199, 學年度: 9