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

16 Pipelined Signature Matching for Malicious Access Detection 1050371 2005 3 11

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

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 23.02 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

1 1 2 5 2.1...................................... 5 2.2................................ 5 2.3...................... 6 2.4............................. 7 2.5........................... 9 2.5.1..................... 10 2.5.2 Quick Search...................... 11 2.6.............................. 12 2.7...................................... 13 3 14 3.1...................................... 14 3.2................................ 14 3.3............................ 16 3.4...................... 19 3.5 Shift Table........................ 20 3.6 URL Filtering............................ 22 3.6.1 URL Filtering................... 23 3.6.2 URL Filtering..................... 27 3.7...................................... 29 4 30 iii

4.1...................................... 30 4.2................................... 30 4.3................................. 31 4.4...................................... 33 5 34 37 38 iv

1.1 ( ) ( )............. 2 1.2 IP TCP.......................... 3 2.1............................ 6 2.2.................... 7 2.3 (2 )............... 8 2.4 ( ).............. 9 2.5 Quick Search................ 12 2.6 (URL Filtering )................... 13 3.1............................... 15 3.2............................ 16 3.3.................... 17 3.4 Quick Search..................... 18 3.5............................. 18 3.6.................. 19 3.7 Quick Search Shift Table.................. 21 3.8.................. 21 3.9.............................. 22 3.10 URL Filtering.......................... 23 3.11 URL.......................... 24 3.12 URL.......................... 26 3.13 URL......................... 27 3.14.............................. 28 v

4.1 ( ).............. 31 4.2 (6 ))................ 32 vi

2.1...................... 10 4.1 URL Filtering.............. 32 vii

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

1.1 1.1 ( ) ( ) 1.1 Firewall 2

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

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

2 2.1 2.2 Firewall IDS IP SPI IP URL Filtering 5

2.3 2.3 2.1 1 1 1 2.1 1 2.2 N( ) 1 Action String.1 Signature.N String.N-2 String.N-1 StringN 6

2.4 2.2 2.1 N 2.2 1/N N 2.4 7

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

2.5 2.4 ( ) 2.5 2 1 1 1 1 9

2.5 2.5.1 Brute-Force Boyer-Moore Knuth-Morris-Pratt Quick Search [7] 2.1 2.1 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

2.5 Quick Search 2.5.2 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 1 2.5 N O N O 1 2 +1 2.5 2 +1 ( ) 11

2.6 2.5 Quick Search T Shift Table T 4 4 2.6 Quick Search URL Filtering IP URL URL URL Filtering 2.6 12

2.7 URL URL 2.6 (URL Filtering ) 2.7 Quick Search 1 1 1 13

3 3.1 URL Filtering 3.2 Quick Search Quick Search Quick Search 3.1 14

3.2 3.1 28 bit BK FS CH 3 3.1 3.2 0 1 0 1 1 0 1 0 15

3.3 3.2 3.3 3.3 Quick Search 1. String 2. Get Signature 3. Get Text 4. 2. 3. Compare 5. Action 16

3.3 Shift amount Shift Table Get Signature (2. ) 3.3 32bit(1word) 2048words Quick Search 3.4 3.5 17

3.3 3.4 Quick Search 3.5 18

3.4 3.4 3.6 3.6 Length Action 15words Text(64words) 4 1 19

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

3.5 Shift Table 4 24-8 ( 2 bit ) 8bit 3.7 Quick Search Shift Table 3.8 21

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

3.6 URL Filtering 3.6.1 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

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

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: www.kochi-tech.ac.jpcrlr Hostname Host: (CRLF) 3. URL IP Directory Hostname URL Directory Hostname 25

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

3.6 URL Filtering 3.6.2 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

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

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

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

4.3 20Byte[10] 150Byte 12 4.3 4.1 12 Throughput[Mbps] 11.5 11 10.5 10 4.1 9.5 1 2 4 6 # of Signature ( ) 1 31

4.3 6 4.2 30 Throughput[Mbps] 25 20 15 10 5 1 2 3 4 # of Processor 4.2 (6 )) 4.2 URL Filtering 4.1 (URL Filtering ) 4.1 URL Filtering (step) [Mbps] 4 5850 59.35 32

4.4 4.4 32bit DDMP URL Filtering 33

5 Firewall Firewall Firewall Firewall 4 23.02Mbps URL Filtering 59.3Mbps 34

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

URL Filtering 36

37

[1] H. Terada, S. Miyata and M. Iwata, DDMP s: self-timed super-pipelined datadriven multimedia processors, Proc. of the IEEE, 87(2), 282 296 1999. [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. 80-87, Sep. 28, 2004. [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. 361-366, Sep. 28, 2004. [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. 322-329, Sep. 28, 2004. [5] W. Richard Stevens TCP/IP Vol.1,,, Pearson Education Japan, 2000. [6],,,, IP, Internet Conference2000, 2000. [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 1999. [8] RFC 1738 Uniform Resource Locators (URL), December 1994. [9] RFC 2068 Hypertext Transfer Protocol HTTP/1.1, January 1997. [10] N. Tuck, T. Sherwood, B. Calder and G. Varghese, Deterministic Memory-Efficient 38

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