王勝德臺灣大學：電機工程學研究所陳柏宏Chen, Bo-HongBo-HongChen2007-11-262018-07-062007-11-262018-07-062007http://ntur.lib.ntu.edu.tw//handle/246246/53068TCP通訊協定缺乏安全機制、尤其對於阻斷服務攻擊(DoS)，網路資源易於嚴重佔用，雖然目前都許多文獻及商品宣稱對於阻斷服務攻擊有保護的功能，但不能完全阻擋，也可能產生誤判；狀態封包檢測(Stateful Packet Inspection, SPI)是目前比較新的技術，可以有效抵制SYN洪流(SYN Flooding)的攻擊，許多文獻會對此主題進行探討。本論文主要討論是在SPI技術以及相關的連線表(Session Table)資料結構。作為連線表的資料結構必須能支援:(1)匹配時採用定長匹配技術，(2)表的項目數量龐大，(3)表的插入及刪除動作頻繁，(4)表的數據寬度較寬。因此尋找一個符合以上特性的演算法非常重要。PATRICIA演算法的特色是: (1)空間複雜度不變，(2)搜尋、插入、刪除效能優異，(3)適合硬體實作；所以PATRICIA演算法適合於連線表；文獻上已有方法改善插入動作，使得插入時，不用再重新搜尋一遍。本論文提出雙向的PAT-FM演算法，進一步改善刪除動作，在每一個node中能記錄上一層node的位址，使得刪除時，能得到固定的刪除處理時間，進而讓整體更有效率，模擬所得的結果證明本論文所提的方法的確能改善整體的執行效率。另外，實作後下載到Xilinx ML-405上驗證，也證明雙向PAT-FM可以在真正的硬體上正常動作。The security-related deficiencies in the TCP/IP protocol make networks vulnerable to intruders. The denial-of-service (DoS) attacks are such intrusions that saturate the target of victim machine with external communications requests, such that it cannot respond to its intended users. Stateful Packet Inspection (SPI) is a key technology that makes a stateful firewall able to hold in memory significant attributes of connections to prevent DoS attacks, such as SYN flooding, the most common DoS attack on the Internet. In this paper, we first investigate SPI technologies and related session table architectures in order to improve the performance of firewall machines. The PATRICIA tree is good at supporting the expensive match, insert, and delete operations in the session table. In this thesis, we use a kind of PATRICIA tree, called Doubly Link PAT-FM algorithm and improve the delete operations. Finally, we implemented the proposed system in hardware and experimental results show its effectiveness.第一章 介紹 1 第二章 相關研究 3 第一節 SYN洪流攻擊 3 第二節 狀態封包檢測 4 第三節 連線表 8 第三章 雙向PAT-FM演算法 11 第一節 動機 11 第二節 搜尋動作 12 第三節 插入動作 14 第四節 刪除動作 15 第五節 更新連線動作 17 第六節 接收封包行程 17 第七節 Timeout行程 18 第四章 演算法實作 20 第一節 工具 20 第一項 Visual C++ 6.0 20 第二項 Celoxica DK design suite 21 第三項 ModelSim SE PLUS 6.1c 23 第四項 Xilinx ISE 8.2i 24 第五項 Xilinx Platform Studio 8.2i 24 第二節 評估板 25 第三節 流程 26 第一項 規格製定 26 第二項 演算法設計 29 第三項 硬體實作 32 第四項 Synthesis, Place & Route 39 第五項 下載至評估板與展示 39 第五章 數據分析 43 第一節 演算法分析 43 第二節 演算法複雜度比較 46 第六章 結論 47 第七章 參考文獻 485065434 bytesapplication/pdfen-US封包分類狀態連線表PATRICIA algorithmpacket classificationstateful packet inspectionsession tablethesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53068/1/ntu-96-J94921060-1.pdf