(12) United States Patent (cid:9)
`Dietz et al. (cid:9)
`
`(to) Patent No.: (cid:9)
`(45) Date of Patent: (cid:9)
`
`US 6,665,725 B1
`Dec. 16, 2003
`
`11111111111101111111111!!!!11111211111111111111111110111111
`
`(54)
`
`(75)
`
`PROCESSING PROTOCOL SPECIFIC
`INFORMATION IN PACKETS SPECIFIED BY
`A PROTOCOL DESCRIPTION LANGUAGE
`
`Inventors: Russell S. Dietz, San Jose, CA (US);
`Andrew A. Koppenhaver, Littleton,
`CO (US); James F. Torgerson,
`Andover, MN (US)
`
`(73)
`
`Assignee: Hi/fn, Inc., Los Gatos, CA (US)
`
`Notice: (cid:9)
`* )
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 537 days.
`
`(21)
`
`Appl. No.: 09/609,179
`
`(22)
`
`Filed: (cid:9)
`
`Jun. 30, 2000
`
`(60)
`
`(51)
`(52)
`
`(58)
`
`(56)
`
`Related U.S. Application Data
`Provisional application No. 60/141,903, filed on Jun. 30,
`1999.
`
`Int. C1.7 (cid:9)
`U.S. Cl. (cid:9)
`
` GO6F 13/00
` 709/230; 709/246; 709/228;
`370/389
` 709/203, 206,
`Field of Search (cid:9)
`709/216, 217, 222, 246, 225, 228, 230,
`232; 703/26; 370/489, 13, 17
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,736,320 A
`4,891,639 A
`5,101,402 A
`5,247,517 A
`5,247,693 A
`5,315,580 A
`5,339,268 A
`5,351,243 A
`5,365,514 A
`5,375,070 A
`5,394,394 A
`5,414,650 A
`
`4/1988 Bristol
`1/1990 Nakamura (cid:9)
`3/1992 Chui et al. (cid:9)
`9/1993 Ross et al. (cid:9)
`9/1993 Bristol
`5/1994 Phaal (cid:9)
`8/1994 Machida (cid:9)
`9/1994 Kalkunte et al. (cid:9)
`11/1994 Hershey et al. (cid:9)
`12/1994 Hershey et al. (cid:9)
`2/1995 Crowther et al. (cid:9)
`5/1995 Hekhuis (cid:9)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`364/300
`340/825.5
`370/17
`370/85.5
`709/203
`370/13
`365/49
`370/92
`370/17
`364/550
`370/60
`364/715.02
`
`5,414,704 A (cid:9)
`
`5/1995 Spinney (cid:9)
`
` 370/60
`
`(List continued on next page.)
`
`OTHER PUBLICATIONS
`
`"Technical Note: the Narus System," Downloaded Apr. 29,
`1999 from www.narus.com, Narus Corporation, Redwood
`City California.
`
`Primary Examiner—Hosain T. Alam
`Assistant Examiner (cid:9) Khanh Quang Dinh
`(74) Attorney, Agent, or Firm—Dov Rosenfeld; Inventek
`
`(57) (cid:9)
`
`ABSTRACT
`
`A method of performing protocol specific operations on a
`packet passing through a connection point on a computer
`network. The packet contents conform to protocols of a
`layered model wherein the protocol at a at a particular layer
`level may include one or a set of child protocols defined for
`that level. The method includes receiving the packet and
`receiving a set of protocol descriptions for protocols may be
`used in the packet. A protocol description for a particular
`protocol at a particular layer level includes any child pro-
`tocols of the particular protocol, and for any child protocol,
`where in the packet information related to the particular
`child protocol may be found. A protocol description also
`includes any protocol specific operations to be performed on
`the packet for the particular protocol at the particular layer
`level. The method includes performing the protocol specific
`operations on the packet specified by the set of protocol
`descriptions based on the base protocol of the packet and the
`children of the protocols used in the packet. A particular
`embodiment includes providing the protocol descriptions in
`a high-level protocol description language, and compiling to
`the descriptions into a data structure. The compiling may
`further include compressing the data structure into a com-
`pressed data structure. The protocol specific operations may
`include parsing and extraction operations to extract identi-
`fying information. The protocol specific operations may also
`include state processing operations defined for a particular
`state of a conversational flow of the packet.
`
`17 Claims, 20 Drawing Sheets
`
`PARSER
`301
`
`ANALYZER
`303
`
`,.- 1502
`(
`
`PACKET
`ACQUISITION (cid:9)
`DEVICE
`
`
`
`MONITOR
`300 (cid:9)
`
`324
`
`DATABASE
`OF
`FLOWS
`(MFMORY)
`
`(1504 r 1506
`
`(cid:9)0. HOST
`PROCESSOR
`
`HOST
`MEMORY
`
`11
`
`(- 1510 (cid:9)
`
`NETWORK
`INTERFACE
`CARD
`
`DISK
`
`DB
`
`1508
`
`NOAC Ex. 1002 Page 1
`
`(cid:9)
`(cid:9)
`

`

`US 6,665,725 B1
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`7/1995 Galloway (cid:9)
`5,430,709 A (cid:9)
`7/1995 Harper (cid:9)
`5,432,776 A (cid:9)
`2/1996 Waclawsky et al. (cid:9)
`5,493,689 A (cid:9)
`3/1996 (cid:9) Hershey et al. (cid:9)
`5,500,855 A (cid:9)
`4/1996 (cid:9) Terasaka et al. (cid:9)
`5,511,215 A (cid:9)
`10/1996 (cid:9) Hershey et al. (cid:9)
`5,568,471 A (cid:9)
`11/1996 (cid:9) Stansfield et al. (cid:9)
`5,574,875 A (cid:9)
`12/1996 (cid:9) Hershey et al. (cid:9)
`5,586,266 A (cid:9)
`2/1997 Shwed (cid:9)
`5,606,668 A (cid:9)
`3/1997 (cid:9) Large et al. (cid:9)
`5,608,662 A (cid:9)
`5/1997 (cid:9)
`Iddon et al. (cid:9)
`5,634,009 A (cid:9)
`7/1997 (cid:9) Van Seters et al. (cid:9)
`5,651,002 A (cid:9)
`5,680,585 A (cid:9) * 10/1997 (cid:9) Bruell (cid:9)
`5,684,954 A (cid:9)
`11/1997 (cid:9) Kaiserswerth et al.
`5,703,877 A (cid:9)
`12/1997 (cid:9) Nuber et al. (cid:9)
`5,721,827 A (cid:9)
`2/1998 (cid:9) Logan et al. (cid:9)
`5,732,213 A (cid:9)
`3/1998 (cid:9) Gessel et al. (cid:9)
`5,740,355 A (cid:9)
`4/1998 Watanabe et al. (cid:9)
`5,761,424 A (cid:9)
`6/1998 Adams et al. (cid:9)
`5,764,638 A (cid:9)
`6/1998 Ketchum (cid:9)
`5,781,735 A (cid:9)
`7/1998 Southard (cid:9)
`5,784,298 A (cid:9)
`7/1998 (cid:9) Hershey et al. (cid:9)
`
`* (cid:9)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`370/13
`370/17
`709/206
`370/17
`709/246
`370/17
`395/403
`709/216
`709/216
`364/724.01
`709/206
`370/392
`703/26
`709/203
`370/395
`709/217
`709/216
`395/183.21
`709/232
`370/401
`709/238
`364/557
`
`5,787,253 A
`5,805,808 A
`5,812,529 A
`5,819,028 A
`5,825,774 A
`5,826,017 A
`5,835,726 A
`5,838,919 A
`5,841,895 A
`5,850,386 A
`5,850,388 A
`5,862,335 A
`5,878,420 A
`5,893,155 A
`5,903,754 A
`5,917,821 A
`6,014,380 A
`6,272,151 B1 *
`6,430,409 B1 *
`6,516,337 B1 *
`6,519,568 B1 *
`
`7/1998
`9/1998
`9/1998
`10/1998
`10/1998
`10/1998
`11/1998
`11/1998
`11/1998
`12/1998
`12/1998
`1/1999
`3/1999
`4/1999
`5/1999
`6/1999
`1/2000
`8/2001
`8/2002
`2/2003
`2/2003
`
`McCreery et al. (cid:9)
`Hansani et al. (cid:9)
`Czarnik et al. (cid:9)
`Manghirmalani et al.
`Ready et al. (cid:9)
`Holzmann (cid:9)
`Shwed et al. (cid:9)
`Schwaller et al. (cid:9)
`Huffman (cid:9)
`Anderson et al. (cid:9)
`Anderson et al. (cid:9)
`Welch, Jr. et al. (cid:9)
`de la Salle (cid:9)
`Cheriton (cid:9)
`Pearson (cid:9)
`Gobuyan et al. (cid:9)
`Hendel et al. (cid:9)
`Gupta et al. (cid:9)
`Rossmann (cid:9)
`Tripp et al. (cid:9)
`Harvey et al. (cid:9)
`
`709/227
`
`709/203
`
`370/245
`
`... 709/203
`
`370/401
`
`709/206
`
`709/228
`
`709/208
`
`382/155
`
`370/241
`
`370/252
`
`709/232
`
`707/10
`
`711/144
`
`709/238
`
`370/392
`
`370/392
`
`370/489
`
`455/422.1
`
`709/202
`
`705/1
`
`* cited by examiner
`
`NOAC Ex. 1002 Page 2
`
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Dec. 16, 2003
`
`Sheet 1 of 20 (cid:9)
`
`US 6,665,725 B1
`
`100
`
`CLIENT 4
`
`-4 (cid:9)
`
`M
`107
`
`CLIENT 3
`
`----
`106
`
`___J108
`
`116
`
`Th110
`
`121
`
`DATA COMMUNICATIONS
`NETWORK
`
`SERVER 2
`
`102
`
`125
`
`118
`
`123 1
`
`105
`
`CLIENT 1
`M
`104
`
`FIG. 1
`
`NOAC Ex. 1002 Page 3
`
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Dec. 16, 2003
`
`Sheet 2 of 20 (cid:9)
`
`US 6,665,725 B1
`
`C\J
`0
`U-
`
`. .=
`1 [II 0 ? 1
`
`
`0.
`
`0
`0
`Of=
`00
`
`m
`
`NOAC Ex. 1002 Page 4
`
`

`

`U.S. Patent (cid:9)
`
`Dec. 16, 2003
`
`Sheet 3 of 20 (cid:9)
`
`US 6,665,725 B1
`
`ANALYZER
`
`\ z
`
`co
`
`I (cid:9)
`
`co
`
`LL
`
`H z° 0
`Qua=
`cC — 2 =
`F_ I— cc LLI
`411 (cid:9)
`X 0
`LL— z
`a
`
`co
`
`Z W 0
`< rLI Z r,- <
`'NNO LLI M CC
`›- 0 r CC
`<° <
`0- U_
`Z
`z
`O
`co
`
`cc cc Z
`< OW
`0 13
`Z < <
`< H
`W r
`<
`< w
`
`CC (cid:9)
`
`co
`0
`co
`
`CC
`cc
`LU LU
`_J N
`6: 2 2
`< 0 a_
`0 0
`
`(1\\ (cid:9)
`
`_j Z uj\
`0 0 0
`<
`0 0-
`I— 5 0
`0 (i) Z
`Irf CC W <
`CL 0
`
`co
`
`co
`co
`
`NOAC Ex. 1002 Page 5
`
`(cid:9)
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Dec. 16, 2003
`
`Sheet 4 of 20 (cid:9)
`
`US 6,665,725 B1
`
`CX-\-- 401
`
`
`
`kir (cid:9)
`
`HIGH LEVEL
`PACKET
`DECODING
`DESCRIPTIONS
`
`402
`
`COMPILE
`DESCRIPTIONS
`
`C 403
`
`405
`
`GENERATE
`PACKET
`STATE
`INSTRUCTIONS
`AND
`OPERATIONS
`
`404
`
`GENERATE
`PACKET
`PARSE AND
`EXTRACT
`OPERATIONS
`
`406 —27ATTEFAIbPARSE
`
`EXTRACTION
`DATABASE
`
`408 (cid:9)
`
`409 D
`
`407
`
`STATE
`PROCESSOR \,
`INSTRUCTION
`DATABASE
`
`LOAD
`PARSING
`SUBSYSTEM
`MEMORY
`
`LOAD STATE
`INSTRUCTION, (cid:9)
`DATABASE
`MEMORY
`
`400
`
`410
`
`FIG. 4
`
`NOAC Ex. 1002 Page 6
`
`

`

`U.S. Patent (cid:9)
`
`Dec. 16, 2003
`
`Sheet 5 of 20 (cid:9)
`
`US 6,665,725 B1
`
`503
`
`504
`
`501
`
`/INPUT PACKET
`
`502
`
`LOAD PACKET 14 (cid:9)
`COMPONENT
`
`NO
`
`512
`
`BUILD
`PACKET
`KEY
`
`YES
`
`V
`FETCH NODE ANC
`--1- 505
`PROCESS FROM
`PATTERNS
`
`506
`
`NO
`
`YES
`
`513
`
`510
`
`500
`
`508
`
`YES
`ir
`EXTRACT
`ELEMENTS
`
`509
`
`FIG. 5
`
`NOAC Ex. 1002 Page 7
`
`

`

`U.S. Patent (cid:9)
`
`Dec. 16, 2003
`
`Sheet 6 of 20 (cid:9)
`
`US 6,665,725 B1
`
`601
`
`602
`
`/ PACKET
`
`COMPONENT AND
`PATTERN NODE
`
`603 --...
`
`•
`LOAD PACKET
`COMPONENT
`
`604
`
`MORE PACKE
`COMPONENT
`
`610
`
`LOAD KEY
`BUFFER
`
`EYES
`FETCH EXTRACTION
`AND PROCESS FROM'?
`' 605
`PATTERNS (cid:9)
`
`NO
`606
`
`ORE EXTRACTIO
`ELEMENTS?
`
`NOI.
`
`NEXT
`PACKET
`COMPONENT
`•
`
`E
`
`• YS
`607 1
`APPLY EXTRACTION
`PROCESS TO
`COMPONENT
`
`611
`
`609
`
`600
`
`608
`
`YES (cid:9)
`
`FIG. 6
`
`NOAC Ex. 1002 Page 8
`
`

`

`U.S. Patent (cid:9)
`
`Dec. 16, 2003
`
`Sheet 7 of 20 (cid:9)
`
`US 6,665,725 B1
`
`701
`
`V
`EY BUFFER AND (cid:9)
`PATTERN NODE
`
`702
`
`•
`
`LOAD PATTERN
`703 -- --\_77 N
`ELEMENT
`
`708 (cid:9) )
`
`704
`
`NO
`
`OUTPUT TO
`ANALYZER
`
`YES
`V
`HASH KEY BUFFER
`,s- 705
`ELEMENT FROM
`PATTERN NODE
`
`V
`
`PACK KEY & HASI-
`
`v
`NEXT PACKET
`COMPONENT
`
`706
`
`707
`
`FIG. 7
`
`709
`
`700
`
`NOAC Ex. 1002 Page 9
`
`

`

`U.S. Patent (cid:9)
`
`Dec. 16, 2003
`
`Sheet 8 of 20 (cid:9)
`
`US 6,665,725 B1
`
`800
`
`801
`
`•
`/UFKB ENTRY FOR
`PACKET
`
`V
`COMPUTE CONVERSATION
`RECORD BIN FROM HASH
`
`802
`
`803
`
`•
`REQUEST RECORD BIN/
`BUCKET FROM CACHE
`
`/— 804
`
`806
`
`805
`
`ORE BUCKET
`IN THE BIN?
`
`NO
`
`SET UFKB FOR
`PACKET AS 'NEW'
`
`
`V
`COMPARE CURRENT BIN
`AND BUCKET RECORD KEY
`TO PACKET
`
`NEXT BUCKET
`
`i-N
`
`KEY MATCH?
`
`807
`
`808
`
`r- 810
`
`809
`
`YES
`•
`MARK RECORD BIN AND
`BUCKET 'IN PROCESS' IN
`CACHE AND TIMESTAMP
`•
`SET UFKB FOR PACKET
`AS 'FOUND'
`
`•
`UPDATE STATISTICS FOR
`RECORD IN CACHE
`
`811 --\_...
`
`812
`
`813-x,o FIG. 8
`
`NOAC Ex. 1002 Page 10
`
`

`

`U.S. Patent (cid:9)
`
`Dec. 16, 2003
`
`Sheet 9 of 20
`
`US 6,665,725 B1
`
`901 (cid:9)
`
`
`
`902
`
`Q,....._ 910
`
`RPC
`REPLY
`,,.
`)1 =7MAPP
`
`RPC
`NNOUNCME
`PORTMAPP
`
`RPC
`BIND LOOKU
`REQUEST
`
`909
`
`903
`
`904
`
`EXTRACT PROGRAM
`
`GET 'PROGRAM',
`VERSION', 'PORT' AND
`'PROTOCOL (TCP OR
`UDP)
`
`7
`CREATE SERVER STAT
`E
`
`SAVE 'PROGRAM',
`VERSION', 'PORT AND
`'PROTOCOL (TCP OR
`UDP)' WITH NETWORK
`ADDRESS IN SERVER
`STATE DATABASE. KEY
`ON SERVER ADDRESS
`AND TCP OR UDP PORT.
`
`EXTRACT PORT
`
`GET 'PROGRAM',
`'VERSION' AND
`'PROTOCOL (TCP OR
`UDP)'
`
`908
`SAVE REQUEST
`
`SAVE 'PROGRAM',
`'VERSION' AND
`'PROTOCOL (TCP OR
`UDP)' WITH
`DESTINATION
`NETWORK ADDRESS.
`BOTH MAKE A KEY.
`
`907
`
`-IRPCV
`BIND
`LOOKUP
`REPLY l
`
`r------ 905
`
`906 --
`
`900
`
`LOOKUP REQUE
`
`FIND 'PROGRAM'
`AND VERSION'
`WITH LOOKUP OF
`SOURCE NETWORK
`ADDRESS.
`
`EXTRACT
`PROGRAM
`
`GET 'PORT' AND
`'PROTOCOL (TCP
`OR UDP)'.
`
`(cid:9)2
`
`FIG. 9
`
`NOAC Ex. 1002 Page 11
`
`

`

`U.S. Patent (cid:9)
`
`Dec. 16, 2003
`
`Sheet 10 of 20 (cid:9)
`
`US 6,665,725 B1
`
`1000 ----A
`
`PATTERN
`RECOGNITION
`DATABASE
`MEMORY
`
`100
`
`1001
`
`EXTRACTION
`OPERATIONS
`DATABASE
`MEMORY
`
`100
`
`100
`
`•• (cid:9)
`
`1031
`1004
`
`(cid:9) INR)OUT,,
`HOST INTERFACE MULTIPLEXR & CONTROL REGISTERS !CONTRL IN
`
`1006—\ PATTERN I
`RECOGNITN (cid:9)
`ENGINE I (cid:9)
`(PRE)
`
`100
`
`EXTRACTION ENGINE
`(SLICER)
`
`1031
`
`1007
`
`1013—
`
`PACKET\
`INPUT /
`
`PARSER INPUT BUFFER
`MEMORY
`
`PARSER
`
`OUTPUT PACKET KEY
`BUFFER AND PAYLOA
`Li
`MEMORY I (cid:9)
`
`1012
`
`ter, (cid:9)
`
`1021Th
`
`PACKET\
`START/
`
`INPUT BUFFER
`INTERFACE
` CONTROL
`NEXT
`PACKET
`
`101
`
`1011
`
`1025
`
`
`ANALYZER DATA READY
`INTERFACE
`
`CONTROL
`ANALYZER
`READY
`
`1023
`
`FIG. 10
`
`1027
`
`NOAC Ex. 1002 Page 12
`
`(cid:9)
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Dec. 16, 2003
`
`Sheet 11 of 20 (cid:9)
`
`US 6,665,725 B1
`
`1103
`
`7
`LOOKUP/
`UPDATE
`ENGINE
`(LUE)
`
`o
`
`
`
`1115 (cid:9)
`
`1122 --
`
`1118
`
`1107
`
`/
`
`HOST
`BUS
`INTER-
`FACE
`(HIB)
`
`ANALYZEF
`HOST
`0 INTERFAC
`AND
`CONTROL
`(ACIC)
`
`STATE
`PROCESSR
`INSTRUCN
`DATABASE
`(SPID)
`
`u r-1108
`
`CACHE
`
`1109
`
`UNIFIED
`FLOW
`/t_k_ KEY
`PARSER
`r--t/BUFFER
`INTER-
`(UFKB)
`FACE
`
`4*
`STATE 14
`PROCESSR
`(SP)
`
`—1119 1123
`
`UNIFIED MEMORY
`MEMORY INTER-
`CONTROL 0 FACE
`(UMC)
`
`FLOW
`INSERTION/ (cid:9)
`DELETION
`ENGINE
`(FIDE)
`
`N
`
`10111•111•111111111M.
`
`1110
`
`FIG. 11
`
`NOAC Ex. 1002 Page 13
`
`(cid:9)
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Dec. 16, 2003
`
`Sheet 12 of 20 (cid:9)
`
`US 6,665,725 B1
`
`C -X-1201
`/ UFKB ENTRY FOR
`
`V
`
`PACKET WITH
`STATUS 'NEW'
`
`1202
`
`1200------.A
`
`117
`ACCESS
`CONVERSATION
`RECORD BIN
`
`1
`
`y-1203
`
`REQUEST RECORD BIN/
`BUCKET FROM CACHE
`
`1204
`
`REQUEST NEXT
`BUCKET FROM
`CACHE
`
`1206-1
`
`1208
`
`1210
`
`SET UFKB FOR
`PACKET AS
`'DROP'
`
`1205
`
`1207
`
`1209
`
`INSERT KEY AND HASH
`N BUCKET, MARK 'USED
`WITH TIMESTAMP
`
`+
`COMPARE CURRENT BII
`AND BUCKET RECORD
`KEY TO PACKET
`
`yi,
`
`MARK RECORD BIN AND
`BUCKET 'IN PROCESS'
`AND 'NEW' IN CACHE
`
`1212— SET INITIAL STATISTICS
`FOR RECORD IN CACHE
`
`1213
`
`FIG. 12
`
`NOAC Ex. 1002 Page 14
`
`(cid:9)
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Dec. 16, 2003
`
`Sheet 13 of 20 (cid:9)
`
`US 6,665,725 B1
`
`1301
`
`1300 ------..a / UFKB ENTRY FOR
`
`PACKET WITH STATUS
`'NEW' OR 'FOUND'
`
`1302
`
`SET STATE
`PROCESSOR
`INSTRUCTION
`POINTER TO
`VALUE FOUND IN
`CURRENT STATE
`
`,--"----
`SAVE STATE
`PROCESSOR
`INSTRUCTION
`POINTER IN
`CURRENT FLOW
`RECORD
`
`NO
`
`SET STATE PROCESSOR
`INSTRUCTION POINTER TO
`VALUE FOUND IN UFKB ENTRY
`1
`FETCH INSTRUCTION FROM r 1304
`STATE PROCESSOR
`INSTRUCTION MEMORY
`
`1303
`
`PERFORM OPERATION BASED (cid:9)
`ON THE STATE INSTRUCTION
`
`1305
`
`NO
`
`DONE PROCESSING
`STATES FOR THIS
`PACKET?
`
`1307
`
`1308
`1310
`
`YES
`
`DONE PROCESSING
`TATES FOR THIS FLO
`
`1309
`
`YES
`
`SET AND SAVE FLOW REMOVAL
`STATE PROCESSOR
`INSTRUCTION IN CURRENT
`FLOW RECORD
`
`1311
`
`1313
`
`FIG. 13
`
`NOAC Ex. 1002 Page 15
`
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Dec. 16, 2003
`
`Sheet 14 of 20 (cid:9)
`
`US 6,665,725 B1
`
`Q Z OZ
`
`Z "- — 0
`mD
`
`1-0Z
`<,'•
`D<M"
`I-
`HW
`
`M WO
`
`co O
`
`w ww
`O m w
`<c°1
`tip
`COI
`
`r—
`
`LL
`
`Z WO
`LIJZI:C‹
`NOLLI
`>-1 01
`CC
`-° 0
`<1-14-LL
`<
`
`A
`
`NOAC Ex. 1002 Page 16
`
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Dec. 16, 2003
`
`Sheet 15 of 20 (cid:9)
`
`US 6,665,725 B1
`
`op o
`Lc)
`
`,___
`
`>-
`I-- CE
`cf) 0
`
`Ow
`2
`
`w (cid:9)
`
`-____
`
`-5-'; (cid:9)
`
`c\J
`co
`
`mw (cid:9)
`0 (cid:9)
`< 0
`(cid:9) 2 (cid:9)
`—1 uu (cid:9)
`< LI-
`0 (cid:9)
`
`A (cid:9)
`
`w N
`>- co
`_J
`< CO
`
`cc
`w
`u-)51
`cc col
`a.
`
`0
`cn (1)
`I-LI
`i C)
`0
`CC I-0'
`0_
`0
`
`---A
`
`U-I
`OL D
`CC <
`LLJ 0
`
`W
`Z Z
`
`I
`
`I
`O
`z01 o
`
`LL
`
`NOAC Ex. 1002 Page 17
`
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Dec. 16, 2003
`
`Sheet 16 of 20 (cid:9)
`
`US 6,665,725 B1
`
`1602
`
`0 - 3 Bytes
`
`offset 0 - 11
`
`Dst MAC
`Src MAC
`Dst MAC
`Src MAC
`
`Ac- 1600
`
`1604
`
`1608 (cid:9)
`
`
`
`Dst Hash (2)
`
`
`Src Hash (21
`
`1612
`
`1614
`
`Dst MAC (6)
`
`Src MAC (6)
`
`2 Offset = 12
`
`FIG. 16
`
`NOAC Ex. 1002 Page 18
`
`(cid:9)
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Dec. 16, 2003
`
`Sheet 17 of 20 (cid:9)
`
`US 6,665,725 B1
`
`1702
`
`1704
`
`offset ! (cid:9)
`12 to 13I
`
`Type
`
`//////////
`
`1708
`
`Type (2)
`Hash '1)
`1710 (cid:9)
`
`\L3 Offset = 14
`
`1700
`
`FIG. 17A
`
`1712
`
`L3 to
`[L3 +
`OHL / 4
`- 1]
`
`Mr (cid:9)
`WEIr, t 1 A
`WIECE1MAI AI
`INA Protocol v mix -
`
`Src Address
`Dst Address
`
`IDP = 0x0600*
`IP = 0x0800*
`CHAOSNET = 0x0804
`ARP = 0x0806
`VIP = OxOBAD*
`VLOOP = OxOBAE
`VECHO = OxOBAF
`NETBIOS-3COM = Ox3C00 -
`0x3COD#
`DEC-MOP = 0x6001
`DEC-RC = 0x6002
`DEC-DRP = 0)(6003*
`DEC-LAT = 0x6004
`DEC-DIAG = 0x6005
`DEC-LAVC = 0x6007
`RARP = 0x8035
`ATALK = 0x809B*
`VLOOP = 0x80C4
`VECHO = 0x8005
`SNA-TH = 0x80D5*
`ATALKARP = 0x80F3
`IPX = 0)(8137*
`SNMP = 0x814C#
`IPv6 = Ox86DD*
`LOOPBACK = 0x9000
`Apple = 0x080007
`* L3 Decoding
`# L5 Decoding
`
`1752
`
`ICMP = 1
`IGMP = 2
`GGP = 3
`TCP = 6*
`EGP = 8
`IGRP = 9
`PUP = 12
`CHAOS = 16
`UDP = 17*
`IDP = 22#
`ISO-TP4 = 29
`DDP = 37#
`ISO-IP = 80
`VIP = 83#
`EIGRP = 88
`OSPF = 89
`
`1750
`
`Dst Address
`Dst Hash (2)
`Src Address
`Src Hash (2)
`
`Protoc ol (1)
`
`L4 Off et = L3 + (IHU4)
`
`FIG. 17B
`
`* L4 Decoding
`# L3 Re-Decoding
`
`NOAC Ex. 1002 Page 19
`
`(cid:9)
`

`

`U.S. Patent
`
`Dec. 16, 2003
`
`Sheet 18 of 20
`
`US 6,665,725 B1
`
`PROTOCOL
`TYPE (I[:) ,
`
`A---1800
`
`FIELD LENGTH
`
`C oci
`(Opps ON
`
`16423
`
`FIG. 18A
`
`• II
`
`1802-2
`1802-1
`
`1802-M
`
`21870
`
`LUT NUM
`
`FIG. 18B
`
`LI
`
`PROTOCOL
`
`NOAC Ex. 1002 Page 20
`
`

`

`U.S. Patent (cid:9)
`
`Dec. 16, 2003
`
`Sheet 19 of 20 (cid:9)
`
`US 6,665,725 B1
`
`1901
`
`CO MMON.PDL
`
`1903
`
`FL OWS.PDL
`
`1905
`
`VIRTUAL.PDL
`
`1907
`
`ETHERNET.PDL
`
`ETHERTYPE
`
`IP.PDL
`
`TCP.PDL
`
`1913
`
`1915
`
`1917
`
`RPC.PDL
`
`Ni (cid:9) 1919
`
`1921---\y
`
`NFS.PDL
`
`1923-1\a FIG. 19
`
`NOAC Ex. 1002 Page 21
`
`

`

`U.S. Patent (cid:9)
`
`Dec. 16, 2003 (cid:9)
`
`Sheet 20 of 20
`
`US 6,665,725 B1
`
`IC— f--- 2001
`
`READ IN PDL SOURCE \- 2003
`MODULES
`
`•
`PARSE MODULES FOR
`SYNTAX
`
`_r---- 2005
`
`•
`FIRST PASS, CREATE
`ALL PARSE ELEMENTS
`
`\ j---- 2007
`
`2009
`
`•
`2ND PASS, BUILD FLOW
`SIGNATURE ELEMENTS
`
`•
`THIRD PASS, CREATE
`PAYLOAD ELEMENTS
`
`2011
`
`•
`Is FORTH PASS, BUILD
`TATES FOR EACH LINK)
`
`2013
`
`•
`READ IN LAYERING
`SOURCE MODULES
`
`\ —2015
`
`•
`WALK LAYERING LINKS
`FOR EACH PDL
`
`2017
`
`2019 --\_i
`
`•
`OUTPUT CPL
`INTERMEDIATE FILE
`
`2021
`
`FIG. 20
`
`NOAC Ex. 1002 Page 22
`
`(cid:9)
`

`

`US 6,665,725 B1
`
`1
`PROCESSING PROTOCOL SPECIFIC
`INFORMATION IN PACKETS SPECIFIED BY
`A PROTOCOL DESCRIPTION LANGUAGE
`
`CROSS-REFERENCE TO RELATED
`APPLICATION
`
`5
`
`10
`
`This application claims the benefit of U.S. Provisional
`Patent Application Serial No.: 60/141,903 for METHOD
`AND APPARATUS FOR MONITORING TRAFFIC IN A
`NETWORK to inventors Dietz, et al., filed Jun. 30, 1999, the
`contents of which are incorporated herein by reference.
`This application is related to the following U.S. patent
`applications, each filed concurrently with the present
`application, and each assigned to Apptitude, Inc., the 15
`assignee of the present invention:
`U.S. patent application Ser. No. 09/608,237 for
`METHOD AND APPARATUS FOR MONITORING
`TRAFFIC IN A NETWORK, to inventors Dietz, et al.,
`filed Jun. 30, 2000, and incorporated herein by refer- 20
`ence.
`U.S. patent application Ser. No. 09/608,126 for
`RE-USING INFORMATION FROM DATA TRANS-
`ACTIONS FOR MAINTAINING STATISTICS IN
`NETWORK MONITORING, to inventors Dietz, et al., 25
`filed Jun. 30, 2000, and incorporated herein by refer-
`ence.
`U.S. patent application Ser. No. 09/608,266 for ASSO-
`CIATIVE CACHE STRUCTURE FOR LOOKUPS
` 30
`AND UPDATES OF FLOW RECORDS IN A NET-
`WORK MONITOR, to inventors Sarkissian, et al., filed
`Jun. 30, 2000, and incorporated herein by reference.
`U.S. patent application Ser. No. 09/608,267 for STATE
`PROCESSOR FOR PATTERN MATCHING IN A 35
`NETWORK MONITOR DEVICE, to inventors
`Sarkissian, et al., filed Jun. 30, 2000, and incorporated
`herein by reference.
`
`FIELD OF INVENTION
`
`The present invention relates to computer networks, spe-
`cifically to the real-time elucidation of packets communi-
`cated within a data network, including classification accord-
`ing to protocol and application program.
`
`COPYRIGHT NOTICE
`
`A portion of the disclosure of this patent document
`contains material that is subject to copyright protection. The
`copyright owner has no objection to the facsimile reproduc-
`tion by anyone of the patent document or the patent
`disclosure, as it appears in the Patent and Trademark Office
`patent file or records, but otherwise reserves all copyright
`rights whatsoever.
`
`BACKGROUND
`
`40
`
`45
`
`50
`
`55
`
`There has long been a need for network activity monitors.
`This need has become especially acute, however, given the
`recent popularity of the Internet and other interconnected
`networks. In particular, there is a need for a real-time 60
`network monitor that can provide details as to the applica-
`tion programs being used. Such a monitor should enable
`non-intrusive, remote detection, characterization, analysis,
`and capture of all information passing through any point on
`the network (i.e., of all packets and packet streams passing 65
`through any location in the network). Not only should all the
`packets be detected and analyzed, but for each of these
`
`2
`packets the network monitor should determine the protocol
`(e.g., http, ftp, H.323, VPN, etc.), the application/use within
`the protocol (e.g., voice, video, data, real-time data, etc.),
`and an end user's pattern of use within each application or
`the application context (e.g., options selected, service
`delivered, duration, time of day, data requested, etc.). Also,
`the network monitor should not be reliant upon server
`resident information such as log files. Rather, it should allow
`a user such as a network administrator or an Internet service
`provider (ISP) the means to measure and analyze network
`activity objectively; to customize the type of data that is
`collected and analyzed; to undertake real time analysis; and
`to receive timely notification of network problems.
`The recognizing and classifying in such a network moni-
`tor should be at all protocol layer levels in conversational
`flows that pass in either direction at a point in a network.
`Furthermore, the monitor should provide for properly ana-
`lyzing each of the packets exchanged between a client and
`a server, maintaining information relevant to the current
`state of each of these conversational flows.
`Related and incorporated by reference U.S. patent appli-
`cation Ser. No. 09/608,237 for METHOD AND APPARA-
`TUS FOR MONITORING TRAFFIC IN A NETWORK, to
`inventors Dietz, et al, describes a network monitor that
`includes carrying out protocol specific operations on indi-
`vidual packets including extracting information from header
`fields in the packet to use for building a signature for
`identifying the conversational flow of the packet and for
`recognizing future packets as belonging to a previously
`encountered flow. A parser subsystem includes a parser for
`recognizing different patterns in the packet that identify the
`protocols used. For each protocol recognized, a slicer
`extracts important packet elements from the packet. These
`form a signature (i.e., key) for the packet. The slicer also
`preferably generates a hash for rapidly identifying a flow
`that may have this signature from a database of known
`flows.
`The flow signature of the packet, the hash and at least
`some of the payload are passed to an analyzer subsystem. In
`a hardware embodiment, the analyzer subsystem includes a
`unified flow key buffer (UFKB) for receiving parts of
`packets from the parser subsystem and for storing signatures
`in process, a lookup/update engine (LUE) to lookup a
`database of flow records for previously encountered con-
`versational flows to determine whether a signature is from
`an existing flow, a state processor (SP) for performing state
`processing, a flow insertion and deletion engine (FIDE) for
`inserting new flows into the database of flows, a memory for
`storing the database of flows, and a cache for speeding up
`access to the memory containing the flow database. The
`LUE, SP, and FIDE are all coupled to the UFKB, and to the
`cache.
`Each flow-entry includes one or more statistical measures,
`e.g., the packet count related to the flow, the time of arrival
`of a packet, the time differential.
`In the preferred hardware embodiment, each of the LUE,
`state processor, and FIDE operate independently from the
`other two engines. The state processor performs one or more
`operations specific to the state of the flow.
`A network analyzer should be able to analyze many
`different protocols. At a base level, there are a number of
`standards used in digital telecommunications, including
`Ethernet, HDLC, ISDN, Lap B, ATM, X.25, Frame Relay,
`Digital Data Service, FDDI (Fiber Distributed Data
`Interface), T1, and others. Many of these standards employ
`different packet and/or frame formats. For example, data is
`
`NOAC Ex. 1002 Page 23
`
`

`

`US 6,665,725 B1
`
`10
`
`15
`
`3
`transmitted in ATM and frame-relay systems in the form of
`fixed length packets (called "cells") that are 53 octets (i.e.,
`bytes) long. Several such cells may be needed to make up the
`information that might be included in the packet employed
`by some other protocol for the same payload information— 5
`for example in a conversational flow that uses the frame-
`relay standard or the Ethernet protocol.
`In order for a network monitor to be able to analyze
`different packet or frame formats, the monitor needs to be
`able to perform protocol specific operations on each packet
`with each packet carrying information conforming to dif-
`ferent protocols and related to different applications. For
`example, the monitor needs to be able to parse packets of
`different formats into fields to understand the data encapsu-
`lated in the different fields. As the number of possible packet
`formats or types increases, the amount of logic required to
`parse these different packet formats also increases.
`Prior art network monitors exist that parse individual
`packets and look for information at different fields to use for
`building a signature for identifying packets. Chiu, et al.,
`describe a method for collecting information at the session
`level in a computer network in U.S. Pat. No. 5,101,402,
`titled "APPARATUS AND METHOD FOR REAL-TIME
`MONITORING OF NETWORK SESSIONS AND A
`LOCAL AREA NETWORK." In this patent, there are fixed
`locations specified for particular types of packets. For
`example, if a DECnet packet appears, the Chiu system looks
`at six specific fields (at 6 locations) in the packet in order to
`identify the session of the packet. If, on the other hand, an
`IP packet appears, a different set of six locations are exam-
`ined. The system looks only at the lowest levels up to the
`protocol layer. There are fixed locations for each of the fields
`that specified the next level. With the proliferation of
`protocols, clearly the specifying of all the possible places to
`look to determine the session becomes more and more
`difficult. Likewise, adding a new protocol or application is
`difficult.
`It is desirable to be able to adaptively determine the
`locations and the information extracted from any packet for
`the particular type of packet. In this way, an optimal signa-
`ture may be defined using a protocol-dependent and packet-
`content-dependent definition of what to look for and where
`to look for it in order to form a signature.
`There thus is also a need for a network monitor that can
`be tailored or adapted for different protocols and for different
`application programs. There thus is also a need for a network
`monitor that can accommodate new protocols and for new
`application programs. There also is a need for means for
`specifying new protocols and new levels, including new
`applications. There also is a need for a mechanism to
`describe protocol specific operations, including, for
`example, what information is relevant to packets and pack-
`ets that need to be decoded, and to include specifying
`parsing operations and extraction operations. There also is a
`need for a mechanism to describe state operations to perform
`on packets that are at a particular state of recognition of a
`flow in order to further recognize the flow.
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`SUMMARY
`
`60
`
`One embodiment of the invention is a method of per-
`forming protocol specific operations on a packet passing
`through a connection point on a computer network. The
`packet contents conform to protocols of a layered model
`wherein the protocol at a particular layer level may include 65
`one or a set of child protocols defined for that level. The
`method includes receiving the packet and receiving a set of
`
`4
`protocol descriptions for protocols may be used in the
`packet. A protocol description for a particular protocol at a
`particular layer level includes any child protocols of the
`particular protocol, and for any child protocol, where in the
`packet information related to the particular child protocol
`may be found. A protocol description also includes any
`protocol specific operations to be performed on the packet
`for the particular protocol at the particular layer level. The
`method includes performing the protocol specific operations
`on the packet specified by the set of protocol descriptions
`based on the base protocol of the packet and the children of
`the protocols used in the packet. A particular embodiment
`includes providing the protocol descriptions in a high-level
`protocol description language, and compiling to the descrip-
`tions into a data structure. The compiling may further
`include compressing the data structure into a compressed
`data structure. The protocol specific operations may include
`parsing and extraction operations to extract identifying
`information. The protocol specific operations may also
`include state processing operations defined for a particular
`state of a conversational flow of the packet.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`Although the present invention is better understood by
`referring to the detailed preferred embodiments, these
`should not be taken to limit the present invention to any
`specific embodiment because such embodiments are pro-
`vided only for the purposes of explanation. The
`embodiments, in turn, are explained with the aid of the
`following figures.
`FIG. 1 is a functional block diagram of a network embodi-
`ment of the present invention in which a monitor is con-
`nected to analyze packets passing at a connection point.
`FIG. 2 is a diagram representing an example of some of
`the packets and their formats that might be exchanged in
`starting, as an illustrative example, a conversational flow
`between a client and server on a network being monitored
`and analyzed. A pair of flow signatures particular to this
`example and to embodiments of the present invention is also
`illustrated. This represents some of the possible flow signa-
`tures that can be generated and used in the process of
`analyzing packets and of recognizing the particular server
`applications that produce the discrete application packet
`exchanges.
`FIG. 3 is a functional block diagram of a process embodi-
`ment of the present invention that can operate as the packet
`monitor shown in FIG. 1. This process may be implemented
`in software or hardware.
`FIG. 4 is a flowchart of a high-level protocol language
`compiling and optimization process, which in one embodi-
`ment may be used to generate data for monitoring packets
`according to versions of the present invention.
`FIG. 5 is a flowchart of a packet parsing process used as
`part of the parser in an embodiment of the inventive packet
`monitor.
`FIG. 6 is a flowchart of a packet element extraction
`process that is used as part of the parser in an embodiment
`of the inventive packet monitor.
`FIG. 7 is a flowchart of a flow-signature building process
`that is used as part of the parser in the inventive packet
`monitor.
`FIG. 8 is a flowchart of a monitor lookup and update
`process that is used as part of the analyzer in an embodiment
`of the inventive packet monitor.
`FIG. 9 is a flowchart of an exemplary Sun Microsystems
`Remote Procedure Call application than may be recognized
`by the inventive packet monitor.
`
`NOAC Ex. 1002 Page 24
`
`

`

`US 6,665,725 B1
`
`ISO MODEL
`
`Layer Functionality Example
`
`5
`6
`FIG. 10 is a functional block diagram of a hardware parser
`in the interior of the cloud. A monitor 108 examines the
`subsystem including the pattern recognizer and extractor
`packets passing in either direction past its connection point
`that can form part of the parser module in an embodiment of
`121 and, according to one aspect of the invention, can
`the inventive packet monitor.
`elucidate what application programs are associated with
`5 each packet. The monitor 108 is shown examining packets
`FIG. 11 is a functional block diagram of a hardware
`(i.e., datagrams) between the network interface 116 of the
`analyzer including a state processor that can form part of an
`server 110 and the network. The monitor can also be placed
`embodiment of the inventive packet monitor.
`at other points in the network, such as connection point 123
`FIG. 12 is a functional block diagram of a flow insertion
`between the network 102 and the interface 118 of the client
`and deletion engine process that can form part of the
`10 104, or some other