(3.236.228.250) 您好!臺灣時間:2021/04/17 06:58
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:戴鈺唐
研究生(外文):Yu-Tang Tai
論文名稱:最佳化字串比對演算法設計針對記憶體架構病毒偵測系統
論文名稱(外文):Optimization of Pattern Matching Algorithm for Memory Based Architecture
指導教授:張世杰張世杰引用關係
指導教授(外文):Shih-Chieh Chang
學位類別:碩士
校院名稱:國立清華大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2007
畢業學年度:95
語文別:英文
論文頁數:30
中文關鍵詞:字串比對網路入侵偵測系統
外文關鍵詞:pattern matchingnetwork intrusion detection system
相關次數:
  • 被引用被引用:0
  • 點閱點閱:284
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:16
  • 收藏至我的研究室書目清單書目收藏:0
現在人的生活愈來愈離不開網路,然而網路上電腦病毒猖獗,網路入侵偵測系統顯得愈來愈重要。網路入侵偵測系統是藉由字串比對,辨識出已知的惡意攻擊字串,來防止惡意程式的入侵。隨著網路速度和病毒數量的快速增加,傳統上單純使用軟體的作法,已經無法滿足高速網路的需求,所以有很多的硬體架構被提出來加速,主要分成邏輯基礎架構和記憶體基礎架構兩大類。
近年來記憶體基礎架構受到大家的矚目,基於容易更新病毒碼、容易擴增和成本較低廉的特性,使用記憶體為基礎的字串比對硬體架構,被廣泛的使用在網路入侵偵測系統上。隨著病毒數目的快速增加記憶體的使用量也隨之愈來愈大,而效率、成本、電源消耗,都和記憶體的大小有關。因此,一個成功的網路入侵偵測系統,必須有一個有效率使用記憶體的字串比對演算法和對應的硬體設計。
這篇論文裡我們提出一個有效率使用記憶體的字串比對演算法,藉由我們的演算法,可以降低在記憶體架構下,記憶體的使用量。針對Snort rule set,新的演算法和傳統Aho-Corasick演算法[5]相比,可以降低29% 的記憶體使用量。因為我們採用和其他方法完全不同的觀點,所以我們的方法可以用在其他方法上。例如將我們的方法用在目前效果最好的演算法,bit-split演算法[9]上,仍然可以減少22% 的記憶體使用量。
Due to the advantages of easy re-configurability and scalability, the memory-based string matching architecture is widely adopted by network intrusion detection systems (NIDS). In order to accommodate the increasing number of attack patterns and meet the throughput requirement of networks, a successful NIDS system must have a memory-efficient pattern-matching algorithm and hardware design. In this paper, we propose a memory-efficient pattern-matching algorithm which can significantly reduce the memory requirement. For total Snort string patterns, the new algorithm achieves 29% of memory reduction compared with the traditional Aho-Corasick algorithm [5]. Moreover, since our approach adopts views totally different from other memory reduction approaches, we can obtain substantial gain even after applying the existing state-of-the-art algorithms. For example, after applying the bit-split algorithm [9], we can still gain an additional 22% of memory reduction.
List of Contents:
Abstract i
Contents ii
List of Figures iii
List of Tables iv
Chapter 1 Introduction 1
Chapter 2 Review of the Aho-Corasick Algorithm 6
Chapter 3 Basic Idea 9
Chapter 4 State Traversal Mechanism on a merg_FSM 12
Chapter 5 Construction of the State Traversal Machine 19
Chapter 6 Experimental Results 25
Chapter 7 Conclusions 28
References 29

List of Figures:
Figure 1 (a): DFA for matching “bcdf” and “pcdg” 3
Figure 1 (b): Next state and output vector are stored in memory 4
Figure 2: State diagram of an Aho-Corasick machine 7
Figure 3: Aho-Corasick state table 8
Figure 4: Merging non-equivalent states 10
Figure 5: The architecture of the state traversal 11
Figure 6: New State diagram of merg_FSM 15
Figure 7: Stare transitions of the input string 17
Figure 8: State traversal pattern matching algorithm 18
Figure 9: Construction of pathVec and ifFinal 22
Figure 10: State diagram of the state traversal 24

List of Tables:
Table 1: Experimental results of the AC algorithm and our algorithm 27
Table 2: Experimental results of the bit-split algorithm and our algorithm 27
References
[1]. R. Sidhu and V. K. Prasanna. Fast regular expression matching using FPGAs. In Proc. of the 9th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM '01), pp. 227-238, 2001.
[2]. R. Franklin, D. Carver, and B.L. Hutchings. Assisting Network Intrusion Detection with Reconfigurable Hardware. In Proceedings of IEEE FCCM 2002, pp. 111-120, Apr. 2002.M. Anis, S. Areibi, and M. Elmasry, “Dynamic and Leakage Power Reduction in MTCMOS Circuits using an Automated Efficient Gate Clustering Technique,” Proc. of DAC, pp. 480–485, 2002.
[3]. J. Moscola, J. Lockwood, R. P. Loui and M. Pachos. Implementation of a Content-Scanning Module for an Internet Firewall. In Proc. of the 11th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM’03), Apr. 2003.
[4]. C. R. Clark and D. E. Schimmel. “Scalable Parallel Pattern Matching on High Speed Networks,” in Proceedings of the Twelfth Annual IEEE Symposium on Field Programmable Custom Computing Machines 2004 (FCCM '04), 2004.
[5]. A. V. Aho and M. J. Corasick. Efficient String Matching: An Aid to Bibliographic Search. In Communications of the ACM, 18(6):333–340, 1975.
[6]. Young H. Cho and William H. Mangione-Smith, A Pattern Matching Co-processor for Network Security. In 42nd IEEE/ACM Design Automation Conference, Anaheim, CA, June 13-17, 2005.
[7]. M. Aldwairi*, T. Conte, and P. Franzon. Configurable String Matching Hardware for Speeding up Intrusion Detection. In ACM SIGARCH Computer Architecture News, 33(1):99–107, 2005.
[8]. S. Dharmapurikar and J. Lockwood. Fast and Scalable Pattern Matching for Content Filtering. In Proceedings of Symposium on Architectures for Networking and. Communications Systems (ANCS), Oct 2005.C. Long and L. He, “Distributed Sleep Transistor Network for Power Reduction,” IEEE Transactions on VLSI systems, vol. 12, no. 9, Sep. 2004.
[9]. L. Tan and T. Sherwood. A high throughput string matching architecture for intrusion detection and prevention. In ISCA'05: 32nd Annual International Symposium on Computer Architecture, pp. 112-122, 2005.S. Pant, and D. Blaauw, “Static timing analysis considering power supply variations,” Proc. of ICCAD, 2005.
[10]. H. J. Jung, Z. K. Baker, and V. K. Prasanna. Performance of FPGA Implementation of Bit-split Architecture for Intrusion Detection Systems. In IPDPS 2006: 20th International Parallel and Distributed Processing Symposium, 2006.
[11]. M. Roesch. Snort- lightweight Intrusion Detection for networks. In Proceedings of LISA99, the 15th Systems Administration Conference, 1999.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔