Firewall IDS IP IP 1 HTTP 74% Quick Search 32 bit DDMP Mbps URL Filtering 59.3 Mbps i

Size: px

Start display at page:

Download "Firewall IDS IP IP 1 HTTP 74% Quick Search 32 bit DDMP 4 23.02 Mbps URL Filtering 59.3 Mbps i"

ありかつひきぎ
7 years ago
Views:

1 16 Pipelined Signature Matching for Malicious Access Detection

2 Firewall IDS IP IP 1 HTTP 74% Quick Search 32 bit DDMP Mbps URL Filtering 59.3 Mbps i

3 Abstract Pipelined Signature Matching for Malicious Access Detection Takuya Matsumoto Based on the conception of deep packet inspection, signature matching (SM) of application layer content is becoming an indispensable portion of most of the security systems such as firewall, intrusion detection system (IDS) and so on. Compared with other security techniques like static packet filtering and stateful packet inspection (SPI), SM is more computation intensive because of the heavy processing load for matching all the variable length payloads of network packets with the large predefined keywords set. Since SM module dominants the performance of the entire security system, a fast SM mechanism is required to keep up with the increasing network bandwidth. My work focuses on the development of pipelined parallel implementation of SM module, as well as its evaluation on the data driven multimedia processor (DDMP) simulator. When developing the SM module, the quick search (QS) algorithm is adopted owing to its fast performance. The evaluation result shows that when 4 nano-processor (npe) is used, the throughput of SM module can get to Mbps. In addition, a higher throughput which is 59.3Mbps can be obtained if the SM module is optimized for URL filtering. key words Pipelined Signature Matching Parallel Searching Data Driven MultiProcessor ii

Compared with other security techniques like static packet filtering and stateful packet inspection (SPI), SM is more computation intensive because of the heavy processing load for matching all the

4 Quick Search Shift Table URL Filtering URL Filtering URL Filtering iii

4...................... 19 3.5 Shift Table........................ 20 3.6 URL Filtering............................ 22 3.6.1 URL Filtering................... 23 3.6.2 URL Filtering.

5 iv

4...................................... 33 5 34 37 38 iv

6 1.1 ( ) ( ) IP TCP (2 ) ( ) Quick Search (URL Filtering ) Quick Search Quick Search Shift Table URL Filtering URL URL URL v

5............................. 18 3.6.................. 19 3.7 Quick Search Shift Table.................. 21 3.8.................. 21 3.9.............................. 22 3.10 URL Filtering.

7 4.1 ( ) (6 )) vi

8 URL Filtering vii

9 1 Personal Firewall Host PDA Firewall Firewall Firewall [1] 1

10 ( ) ( ) 1.1 Firewall 2

11 Firewall Firewall [2] IP [3] SPI [4] IP ( 1.2[5]) 1.2 IP TCP HTTP Firewall 1 URL Filtering HTTP HTTP 3

12 74% [6] 32bit 2 3 URL Filtering 4 5 4

13 Firewall IDS IP SPI IP URL Filtering 5

14 N( ) 1 Action String.1 Signature.N String.N-2 String.N-1 StringN 6

15 N 2.2 1/N N 2.4 7

16 (Judgment) 2.3 (2 ) M 2.2 M 1/M 8

17 ( )

18 Brute-Force Boyer-Moore Knuth-Morris-Pratt Quick Search [7] Brute-Force - O(n(1+1/( -1))) O(mn) - Boyer-Moore O(m+ ) O(n/m) O(m+rn) 2 Knuth-Morris-Pratt O(m) O(n) O(n) 1 Quick Search O(m+ )+O( ) O(n/ ) O(mn) 1 m n, r, Knuth-Morris-Pratt Quick Search Knuth-Morris-Pratt Quick Search 10

Knuth-Morris-Pratt O(m) O(n) O(n) 1 Quick Search O(m+ )+O( ) O(n/ ) O(mn) 1

19 2.5 Quick Search Quick Search Quick Search 1. Boyer-Moore 2. Occurrence 3. O(m+ )+O( ) (m ) 4. O(mn) (n ) 5. (Occurrence Shift Table) Quick Search Shift Table N O N O ( ) 11

20 Quick Search T Shift Table T Quick Search URL Filtering IP URL URL URL Filtering

21 2.7 URL URL 2.6 (URL Filtering ) 2.7 Quick Search

22 3 3.1 URL Filtering 3.2 Quick Search Quick Search Quick Search

23 bit BK FS CH

24 Quick Search 1. String 2. Get Signature 3. Get Text Compare 5. Action 16

25 3.3 Shift amount Shift Table Get Signature (2. ) bit(1word) 2048words Quick Search

26 Quick Search

27 Length Action 15words Text(64words)

28 3.5 Shift Table 3.5 Shift Table Quick Search Shift Table 1 8bit 128 ASCII 1 1word(32bit) word Shift Table 1 Shift Table word 1 1 word 4 ASCII 0x00 0x7F l 0 l 127 ( 3.8) bit 2 bit 4 20

29 3.5 Shift Table ( 2 bit ) 8bit 3.7 Quick Search Shift Table

30 3.6 URL Filtering URL Filtering URL Filtering URL Filtering IP HTTP URL [8][9]. IP URL 22

31 3.6 URL Filtering URL Filtering URL Filtering 3.10 URL Filtering 3.10 URL Filtering. 1. IP HTTP URL GET Command 2. HTTP GET Command IP URL HTTP GET Command 3. URL IP Directory Hostname URL 23

32 3.6 URL Filtering 4. URL URL ( 8Mwords(1word 4Byte) 8Kwords ) IP TCP. URL GET Command URL IP URL URL URL Directory 24

33 3.6 URL Filtering. 1. Directory IP Directory Directory GET Command GET ( ) Directory GET /kut J/index.html HTTP/1.1CRLR Directory GET Directory 2. Hostname Hostname.Hostname Hostname Host: (CRLF) Hostname Host: Hostname Host: (CRLF) 3. URL IP Directory Hostname URL Directory Hostname 25

34 3.6 URL Filtering IP URL IP Action URL URL 1. URL 2. Action 1. 26

35 3.6 URL Filtering URL Filtering URL Filtering 2 1 IP URL 1 URL 2 IP URL Directory Hostname URL Directory Hostname IP ( 3.13 ) Directory Hostname 3.13 URL 27

36 3.6 URL Filtering Directory Hostname ( 3.13 ) URL Filtering URL URL Quick Search Exact Matching URL Quick Search Quick Search 1 URL URL

37 3.7 1 URL 1 32bit (4 ) 3.7 Shift Table URL Filtering 29

38 4 4.1 Quick Search 4.2 URL Filtering 32bit DDMP 32bit DDMP DDMP 30

39 4.3 20Byte[10] 150Byte Throughput[Mbps] # of Signature ( ) 1 31

40 Throughput[Mbps] # of Processor 4.2 (6 )) 4.2 URL Filtering 4.1 (URL Filtering ) 4.1 URL Filtering (step) [Mbps]

41 bit DDMP URL Filtering 33

42 5 Firewall Firewall Firewall Firewall Mbps URL Filtering 59.3Mbps 34

43 DDMP ( ) Quick Search Shift Table M bit DDMP 32bit DDMP DDMP 32bit DDMP Snort 20Byte Quick Search 35

44 URL Filtering 36

45 37

46 [1] H. Terada, S. Miyata and M. Iwata, DDMP s: self-timed super-pipelined datadriven multimedia processors, Proc. of the IEEE, 87(2), [2] M. Iwata, D. Morikawa, R. Zhang, W. Su, Y. Zheng, L. Kong, H. Terada, Design Concept of An Embedded Data-Driven Firewall Processor, International Conference on Next Era Information Networking NEINE 04, Kochi, pp , Sep. 28, [3] D. Morikawa, T. Matsumoto, M. Iwata, Fast Packet Filtering in Data-Driven Embedded Firewall, International Conference on Next Era Information Networking NEINE 04, Kochi, pp , Sep. 28, [4] R.Zhang, M.Iwata, Y.Shirane, T.Asahiyama, W.Su, Y.Zheng, High Speed Stateful Packet Inspection in Embedded Data-Driven Firewall, International Conference on Next Era Information Networking NEINE 04, Kochi, pp , Sep. 28, [5] W. Richard Stevens TCP/IP Vol.1,,, Pearson Education Japan, [6],,,, IP, Internet Conference2000, [7] P.D. Michailidis and K.G. Margaritis, On-line String Matching Algorithms: Survey and Experimental Results, Department of Ap. Informatics, University of Macedonia, April [8] RFC 1738 Uniform Resource Locators (URL), December [9] RFC 2068 Hypertext Transfer Protocol HTTP/1.1, January [10] N. Tuck, T. Sherwood, B. Calder and G. Varghese, Deterministic Memory-Efficient 38

47 String Matching Algorithms for Intrusion Detection, Proc. of the IEEE Infocom Conference, Hong Kong,China March

12 DCT A Data-Driven Implementation of Shape Adaptive DCT

12 DCT A Data-Driven Implementation of Shape Adaptive DCT 1010431 2001 2 5 DCT MPEG H261,H263 LSI DDMP [1]DDMP MPEG4 DDMP MPEG4 SA-DCT SA-DCT DCT SA-DCT DDMP SA-DCT MPEG4, DDMP,, SA-DCT,, ο i Abstract