I 1111111111111111 11111 1111111111 1111111111 111111111111111 1111111111 11111111
`US007013482B 1
`
`(12) United States Patent
`Krumel
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,013,482 Bl
`Mar.14,2006
`
`(54)
`
`METHODS FOR PACKET FILTERING
`INCLUDING PACKET INVALIDATION IF
`PACKET VALIDITY DETERMINATION NOT
`TIMELY MADE
`
`(75)
`
`Inventor: Andrew K. Krumel, San Jose, CA
`(US)
`
`6,009,475 A
`6,011,797 A *
`6,020,758 A
`6,049,222 A
`
`12/1999 Shrader ...................... 709/249
`1/2000 Sugawara .............. 370/395.51
`2/2000 Patel . ... ... ... ... ... .. ... ... ... 326/40
`4/2000 Lawman . . . . . . . . . . . . . . . . . . . . . . 326/38
`
`(Continued)
`
`FOREIGN PATENT DOCUMENTS
`
`(73) Assignee: 802 Systems LLC, Chicago, IL (US)
`
`WO
`
`WO 96/34479
`
`10/1996
`
`( *) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 614 days.
`
`(21) Appl. No.: 09/611,775
`
`(22)
`
`Filed:
`
`Jul. 7, 2000
`
`(51)
`
`(52)
`(58)
`
`Int. Cl.
`H04L 9/00
`(2006.01)
`G06F 15/16
`(2006.01)
`U.S. Cl. ......................... 726/13; 713/154; 709/229
`Field of Classification Search ................ 713/201,
`713/154; 709/229, 249, 225; 370/356, 389,
`370/392, 395.21, 395.32, 401; 726/13, 11
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5,343,471 A
`5,426,378 A
`5,426,379 A
`5,530,695 A *
`5,590,060 A
`5,657,316 A *
`5,740,375 A
`5,745,229 A
`5,794,033 A
`5,835,726 A
`5,884,025 A
`5,903,566 A
`5,905,859 A *
`5,968,176 A
`5,974,547 A
`6,003,133 A
`
`8/1994 Cassagnol ................... 370/401
`6/1995 Ong .. ... ... ... .. ... ... ... ... .. . 326/39
`6/1995 Trimberger ... ... ... ... ... .. . 326/39
`6/1996 Dighe et al. ................ 370/232
`12/1996 Granville .................... 702/155
`8/1997 Nakagaki et al. ........... 370/394
`4/1998 Dunne et al. . .. ... ... . 395/200.68
`4/1998 Jung . ... ... ... .. ... ... ... ... .. . 356/73
`8/1998 Aldebert et al. ............ 395/653
`11/1998 Shwed et al. . .. ... ... . 395/200.59
`3/1999 Baehr et al. ........... 395/187.01
`5/1999 Flammer .................... 370/406
`5/1999 Holloway et al.
`.......... 713/201
`10/1999 Nessett et al. .............. 713/201
`10/1999 Klimenko ... .. ... ... ... ... .. ... 713/2
`12/1999 Moughanni et al. ........ 713/200
`
`(Continued)
`
`OTHER PUBLICATIONS
`
`3com. "SuperStack 3 Firewall", 2000 3com.*
`
`(Continued)
`
`Primary Examiner-Gregory Morse
`Assistant Examiner-Michael J. Simitoski
`(74) Attorney, Agent, or Firm-Loudermilk & Associates
`
`(57)
`
`ABSTRACT
`
`Methods and systems for firewall/data protection that filters
`data packets in real time and without packet buffering are
`disclosed. A data packet filtering hub, which may be imple(cid:173)
`mented as part of a switch or router, receives a packet on one
`link, reshapes the electrical signal, and transmits it to one or
`more other links. During this process, a number of filters
`checks are performed in parallel, resulting in a decision
`about whether each packet should or should not be invali(cid:173)
`dated by the time that the last bit is transmitted. To execute
`this task, the filtering hub performs rules-based filtering on
`several levels simultaneously, preferably with a program(cid:173)
`mable logic or other hardware device. Various methods for
`packet filtering in real time and without buffering with
`programmable logic are disclosed. The system may include
`constituent elements of a stateful packet filtering hub, such
`as microprocessors, controllers, and integrated circuits. The
`system may be reset, enabled, disabled, configured, and/or
`reconfigured with toggles or other physical switches. Audio
`and visual feedback may be provided regarding the opera(cid:173)
`tion and status of the system.
`
`66 Claims, 13 Drawing Sheets
`
`,s-...
`~ l
`
`I
`
`11
`
`... .L.., ..
`
`11.0-l
`
`,ss
`
`Ex.1001
`CISCO SYSTEMS, INC. / Page 1 of 29
`
`

`

`US 7,013,482 Bl
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`6,052,785 A
`6,052,788 A *
`6,076,168 A
`6,078,736 A
`6,092,108 A *
`6,092,123 A
`6,133,844 A *
`6,134,662 A *
`6,151,625 A
`6,175,839 Bl
`6,182,225 Bl
`6,215,769 Bl
`6,310,692 Bl
`6,326,806 Bl
`6,333,790 Bl
`6,335,935 Bl *
`6,343,320 Bl
`6,363,519 Bl
`6,374,318 Bl
`6,389,544 Bl
`6,414,476 Bl
`6,430,711 Bl
`6,549,947 Bl
`6,608,816 Bl *
`6,628,653 Bl
`6,640,334 Bl
`6,691,168 Bl *
`6,700,891 Bl
`6,734,985 Bl
`6,771,646 Bl
`6,779,004 Bl
`6,791,992 Bl *
`
`4/2000 Lin ............................ 709/225
`4/2000 Wesinger et al.
`........... 713/201
`6/2000 Fiveash ...................... 713/201
`6/2000 Guccione ............... 395/500.17
`7/2000 DiPlacido et al.
`.......... 709/224
`7/2000 Steffan .......................... 710/8
`10/2000 Ahne et al. ............ 340/815.45
`10/2000 Levy et al.
`................. 713/200
`11/2000 Swales ....................... 709/218
`1/2001 Takao ......................... 715/500
`1/2001 Hagiuda ..................... 713/201
`4/2001 Ghani ........................ 370/230
`10/2001 Fan ........................... 358/1.14
`12/2001 Fallside ....................... 326/38
`12/2001 Kageyama ................. 358/1.15
`1/2002 Kadambi et al.
`........... 370/396
`1/2002 Fairchild .................... 709/224
`3/2002 Levi ............................ 716/16
`4/2002 Hayes ........................ 710/107
`5/2002 Katagiri ...................... 713/300
`7/2002 Yagi ........................... 324/127
`8/2002 Sekizawa ..................... 714/47
`4/2003 Suzuki ....................... 709/229
`8/2003 Nichols ...................... 370/235
`9/2003 Salim ......................... 370/389
`10/2003 Rasmussen ................. 717 /171
`2/2004 Bal et al. .................... 709/238
`3/2004 Wong ......................... 370/401
`5/2004 Ochiai ....................... 358/1.15
`8/2004 Sarkissian ................... 370/392
`8/2004 Zintel ......................... 709/227
`9/2004 Yun et al. ................... 370/415
`
`FOREIGN PATENT DOCUMENTS
`
`WO
`WO
`
`WO 99/48303
`WO 00/02114
`
`9/1999
`1/2000
`
`OIBER PUBLICATIONS
`
`Hughes, James. "A High Speed Firewall Architecture for
`ATM/OC-3c", Feb. 1996.*
`
`IBM Technical Disclosure Bulletins NN8606320 (1986),
`NN950431
`(1995), NA81123528
`(1981), NN9704141
`(1997), NN9512419
`(1995), NN9502341
`(1995),
`NN9308183 (1993), NN8606254 (1986), NN83102393
`(1983).*
`Lakshman, T.V. "High-Speed Policy-based Packet Forward(cid:173)
`ing Using Efficient Multi-dimensional Range Matching",
`1998 ACM, pp. 203-214.*
`Network ICE Corporation. "Black ICE Pro User's Guide
`Version 2.0", Jun. 2000 (archive.mg).*
`Packeteer, Inc. "PacketShaper 4000 Getting Started Version
`4.0", Mar. 1999.*
`Symantec, Inc. "Norton Personal Firewall 2000 User's
`Guide Version 2.0", Jun. 2000 (archive.mg).*
`Xu, Jun and Mukesh Singhal. "Design of a High(cid:173)
`Performance ATM Firewall", 1999 ACM.*
`Xu, Jun and Mukesh Singhal. "Design of a High(cid:173)
`Performance ATM Firewall", 1998 ACM, pp. 93-102.*
`AARNet. "ATM", <http://www.aarnet.edu.au/engineering/
`networkdesign/mtu/atm.html>. *
`Derfler, Jr., Frank J. et al. How Networks Work, Sep. 2000,
`pp. 162-167.*
`Newton, Harry. Newton's TELECOM Dictionary, 2003
`CMP Books, pp. 78-79.*
`Unknown. "ATM Efficiency", <http://homepages.uel.ac.uk/
`u0227461/Website/efficiency.htm>. *
`"Jini Architecture Specifications." Version 1.1, Sun
`Microsystems, Inc., Oct. 2000. Available from Internet:
`http://www.sun.com/jini/specs/jinil_l.pdf, pp. 1-20.
`"Jini Device Architecture Specifications." Version 1.1, Sun
`Microsystems, Inc., Oct. 2000. Available from Internet:
`http://www.sun.com/jini/specs/devicearchl_l.pdf, pp. 1-
`14.
`Sollins, K., "The TFTP Protocol (Revision 2.0)", MIT, Jul.
`1992. Available from Internet: http://www.cis.ohio-state.
`edu/cgi-bin/rfc/rfc1350.html, pp. 1-10.
`
`* cited by examiner
`
`Ex.1001
`CISCO SYSTEMS, INC. / Page 2 of 29
`
`

`

`U.S. Patent
`
`Mar.14,2006
`
`Sheet 1 of 13
`
`US 7,013,482 Bl
`
`<,
`~
`
`(cid:143)
`(cid:143)
`(cid:143)
`(cid:143)
`
`E
`Q)
`·t;
`>,
`If)
`C:
`
`0 :ts
`Q) ·a
`,_
`C.
`.....
`(U
`(U
`1:::i
`
`,_
`~
`::l
`0
`10::
`,rn
`,_J
`10
`
`~
`
`<( -(!)
`
`LL
`
`Ex.1001
`CISCO SYSTEMS, INC. / Page 3 of 29
`
`

`

`U.S. Patent
`
`Mar.14,2006
`
`Sheet 2 of 13
`
`US 7,013,482 Bl
`
`~--o· I] ~ ~
`
`CL
`I-
`
`5
`
`.0 Q)
`Q) Cf)
`I ~
`
`-.
`\J -"-
`
`$
`Cl)
`0
`
`.:::. :s
`e
`Cl! --=
`
`0
`
`Cl)
`Cl)
`0
`Q.
`
`Cl) -Cl)
`.:::. -"C
`~ -C:
`0 = Cl)
`
`ctl
`CD
`
`0
`
`Cl) -Cl)
`.:::. -"C
`Cl) -C/l
`::::i ,_ -C:
`::::i -
`
`$
`c.,
`D ,__ __ Cl>..,.._...,
`(cid:143)
`D
`D
`
`,,3::
`C: ...
`
`ctl
`
`Ex.1001
`CISCO SYSTEMS, INC. / Page 4 of 29
`
`

`

`U.S. Patent
`
`Mar.14,2006
`
`Sheet 3 of 13
`
`US 7,013,482 Bl
`
`I (cid:143) DOD
`
`Packet Nibbles
`
`Repeatr Core
`
`I ~-&--
`
`I
`
`Packet
`Characteristics
`Logic
`
`- - - - - -Pass /Junk - - - - - - - -
`
`Packet Characteristics
`and Nibble Data············
`(No Buffering)
`
`Packet Type Filters
`
`Result
`
`Result Aggregator
`
`Entry to Look-Up
`
`/
`
`Rules Controller
`
`Run Rule#1
`
`Connection
`Cache
`
`- - - -1~ Rules Engine #1
`
`\.._-----'T'-Result#1-------~
`
`~----J1Result#N--------
`
`Get Rule YD•)
`
`~
`
`Rules Engine #N
`
`Rules Map
`Table
`
`i
`------Characteristics ID
`
`~ - - - - - -Ru le Dispatching Information
`
`Get Rule L\ 0-
`
`~
`
`FIG. 2
`
`Ex.1001
`CISCO SYSTEMS, INC. / Page 5 of 29
`
`

`

`U.S. Patent
`
`Mar.14,2006
`
`Sheet 4 of 13
`
`US 7,013,482 Bl
`
`Packet data
`
`Repeater Core
`
`pass/fail for each
`network
`
`-------------1
`
`Determine packet
`characteristics
`(protocol, addrs,
`ports, flags)
`
`Result
`Aggregator
`
`Level 2 Filters
`
`pass/fail
`
`Level 3 Filters
`
`1-------------1 Level 4 Filters
`
`Spoof Check
`
`pass/fail
`
`pass/fail
`
`pass/fail
`
`~3
`
`I
`
`: I
`
`I
`I
`-----------'
`
`transmit alarm information
`over netwrok
`
`s·y
`Alert LED • ... ~ ___ _J
`
`FIG. 3
`
`Ex.1001
`CISCO SYSTEMS, INC. / Page 6 of 29
`
`

`

`U.S. Patent
`
`Mar.14,2006
`
`Sheet 5 of 13
`
`US 7,013,482 Bl
`
`\
`I
`I
`
`,~
`
`i.--------~•
`OSL Route Cable Modem
`
`=====m
`
`External PHY----------1(cid:141) ~1 Controller
`PHY
`
`\
`
`data
`nibble
`
`i
`active
`PHY bO
`
`Junk/Pass for each
`PHY category
`
`acket
`
`e
`
`:al RARP
`13f-'-'-''-"----------'--'----+-----,!~
`~
`·~
`0
`,,:::
`;,:
`
`IP
`
`:No
`
`·
`i"'l " l - - - - - - -
`
`/
`/ - - Bastion PHY
`
`1+
`
`I
`
`Level 2 Filters
`
`'7S
`~Pa ss
`
`1"
`
`/
`
`Not present
`
`Filter IP
`Packet
`
`•
`
`FIG.4
`
`Ex.1001
`CISCO SYSTEMS, INC. / Page 7 of 29
`
`

`

`U.S. Patent
`
`Mar.14,2006
`
`Sheet 6 of 13
`
`US 7,013,482 Bl
`
`(~YSL
`
`· I Oatgram v.i
`
`Level 3 Filters.
`
`Unknown
`
`"IGMP
`
`ICMP
`
`~
`> - - -No~
`
`Yes
`
`·CLO
`> - - -No~
`
`. · ·~
`Yes~
`
`TCP•orUDP ..
`
`Yes
`
`No
`iL/00
`I
`Pass
`
`FIG. 5
`
`Yes
`
`Filter TCP
`and UDP
`datagram
`
`Pass
`
`signal i
`
`Junk
`signal
`
`I
`'
`
`Ex.1001
`CISCO SYSTEMS, INC. / Page 8 of 29
`
`

`

`i,-
`~
`N
`~
`~
`~
`i,(cid:173)
`Q
`"'-...,l
`
`e
`
`rJ'l
`
`'""" ~
`0 ....,
`-..J
`~ ....
`'JJ. =(cid:173)~
`
`O'I
`0
`0
`N
`'"""
`~,J;..
`~ :;
`~
`
`~ = ......
`~ ......
`~
`•
`r:JJ.
`d •
`
`complete
`
`ext
`pass
`
`int
`pass
`
`check
`state
`
`FIG. 6
`
`L...--__ _______ .i.____...i int if have comm state match
`
`.. J30
`
`and SYN set and ACK not set then pass
`20
`If PHY-e active and TCP and port-e:-~
`
`active port and store comm state)
`
`/. Co~:-r \_,,. / 2 l/
`
`state
`
`(
`
`------~'---+--"'~--' command then pass ext and (get client
`
`<-----1----...., and SYN not set and ACK set and PORT ~
`
`I ; /·:t~I
`
`If PHY-i active and TCP and port-e = 21
`
`'-------' If PHY-e active and UDP and port-e = 53 k ru,.
`
`then pass int if have comm state match
`
`then pass ext and store comm state
`If PHY-i active and UDP and port-e = 53 I/ l'l.'il
`
`ICMP, ... ) and active PHY
`Packet type (TCP, UDP,
`
`I I '1..-
`
`address, ports, and flags
`
`Determine packet IP
`
`110
`
`~ata
`r;acke1
`
`/D½
`
`signals for int & ext
`and bitwise-or pass
`then set comp signal
`If all checks complete
`
`/32-
`
`1------.i
`
`I
`
`+---------If PHY-i active and TCP then pass\/ / 2.0
`
`ext
`
`I 16
`
`II~
`
`then pass int & ext
`If TCP and (ACK set or FIN set)
`
`then pass int
`active and TCP and port-i = 80
`If server-mode enabled and PHY-e
`
`// l/
`
`67 then pass int & ext
`
`If port-i = 68 and port-e =
`
`___ -
`
`parallel (other protocols also handled simultaneously)
`TCP and UDP packets are evaluated for pass or fail in
`
`Ex.1001
`CISCO SYSTEMS, INC. / Page 9 of 29
`
`

`

`U.S. Patent
`
`Mar.14,2006
`
`Sheet 8 of 13
`
`US 7,013,482 Bl
`
`---lookup code
`
`Rules Dispatcher
`
`--(cid:141)
`
`r I
`
`Rule ID
`
`Rules
`Engine#N
`
`toggle states-(cid:173)
`datagram
`characteristics
`comm state--
`
`rule
`
`addr
`
`dt 1 -
`
`~['41,..-N
`
`• I
`
`Rules
`I\ Table #N
`
`\)
`1
`
`---~toggle states
`datagram
`characteristic:;
`--comm state
`
`Rules
`Engine#1
`
`rule
`data
`
`addr
`
`al
`"'
`l'i~\~
`
`Rules
`Table #1
`
`"
`0
`3
`,,,
`3
`~
`"
`.,
`"C
`C.
`CD
`
`0
`
`"
`al
`"'
`3 ~
`3
`z
`"'
`oi
`CD
`"
`It
`z
`
`C.
`
`Lookup comm state
`for external host
`
`c:omm state update
`
`Result Aggregator
`
`Pass Junk
`
`FIG. 7
`
`Ex.1001
`CISCO SYSTEMS, INC. / Page 10 of 29
`
`

`

`U.S. Patent
`
`Mar.14,2006
`
`Sheet 9 of 13
`
`US 7,013,482 Bl
`
`r<
`
`!~ ,
`/ /Determine uop\ \
`,i ( and TCP Packet I i
`1 '~1
`
`,s2-
`
`Pass signals for
`each network
`
`,ss-,
`
`~ - - - - - - - - - - - - - - - - - - - - ' Protocol back-end #1
`
`,.csfore;,,cleacsignals , , .
`
`Register
`Controller
`
`Protocol front-end #N
`
`store and clear
`signal for Reg '.
`
`store and clear
`signal for Reg N
`
`State
`Registers
`
`stor~ signa,
`
`~tatefill;'Filters
`
`L . - - - - - - - r - - - - - - - - - -~ - - - - - - - - - - - - - - - - - -P a s s signal for-~--~
`ea ch network
`
`I
`
`l l..t' r )
`
`Pass signal for
`each network -+---1(cid:141)
`
`Result Aggregator
`
`Compare
`characteristics to the
`allowed non-stateiul
`rules and make
`judgement
`
`·Nc111-Stateftil Filters
`
`FIG. 8
`
`Ex.1001
`CISCO SYSTEMS, INC. / Page 11 of 29
`
`

`

`U.S. Patent
`
`Mar.14,2006
`
`Sheet 10 of 13
`
`US 7,013,482 Bl
`
`_.::,t.
`co
`....
`C 0
`.... ~
`$ Q)
`Ez
`
`:r r
`
`0 w:,
`..J
`
`0
`....J a.
`
`en
`(!)
`LL
`
`-.::,t_
`ct!
`....
`C 0
`
`Q)~ x a,
`LU Z
`
`Ex.1001
`CISCO SYSTEMS, INC. / Page 12 of 29
`
`

`

`U.S. Patent
`
`Mar. 14,2006
`
`Sheet 11 of 13
`
`US 7,013,482 Bl
`
`internal!~
`
`I
`I
`
`I
`I
`I
`
`I
`I
`
`Ex.1001
`CISCO SYSTEMS, INC. / Page 13 of 29
`
`

`

`U.S. Patent
`
`Mar.14,2006
`
`Sheet 12 of 13
`
`US 7,013,482 Bl
`
`Remove from flood list
`
`Compare IP address
`and ports to flood
`list entries
`
`Yes
`
`junk packet
`
`l14(cid:141) 1------Yes
`
`No
`
`not set
`
`and client has reached
`
`<
`
`Yes
`
`FIG.11
`
`Unset SYN flag and
`add 1 to new ACK#
`
`Yes-~-<
`
`No
`
`I
`
`No
`
`Transmit ACK packet
`1) recalc TCP, IP, Eth checksums
`2) transmit
`
`No
`
`1) get flood list locations
`2) write bits into list
`3) swap MAC, IP, ports,
`and ACK#'s
`
`No
`
`Add to flood list
`
`Transmit RST packet (high priority):
`! 1) set RST flag
`· 2) recalc TCP, IP, Eth checksums
`3) transmit
`
`FIG.12
`
`Ex.1001
`CISCO SYSTEMS, INC. / Page 14 of 29
`
`

`

`U.S. Patent
`
`Mar.14,2006
`
`Sheet 13 of 13
`
`US 7,013,482 Bl
`
`For each flood list entry
`
`No
`
`Yes
`
`1 ) unset ACK and set RST flag
`2) add 1 to sequence #
`3) recalc checksums
`4) recalc TCP, IP, Eth checksums
`
`Transmit RST packet
`
`Remove from flood list
`
`FIG. 13
`
`Ex.1001
`CISCO SYSTEMS, INC. / Page 15 of 29
`
`

`

`US 7,013,482 Bl
`
`1
`METHODS FOR PACKET FILTERING
`INCLUDING PACKET INVALIDATION IF
`PACKET VALIDITY DETERMINATION NOT
`TIMELY MADE
`
`FIELD OF THE INVENTION
`
`The present invention relates to computer security and
`data protection systems and methods, and more particularly
`to firewall and data protection systems and methods for
`filtering packets, such as from the Internet, in real time and
`without packet buffering.
`
`BACKGROUND OF THE INVENTION
`
`2
`expertise in network administration or a similar field, so they
`can configure, optimize, and even build the complex filtering
`and security options provided by the software.
`While such devices and tools can be quite effective in
`5 providing "firewall" protection for sophisticated users of
`large office systems, they pose several barriers to unsophis(cid:173)
`ticated users of small office and home systems in the
`growing SOHO market. Current large office systems are
`expensive, difficult to set up, and require technical skills.
`10 What is needed for SOHO systems is a relatively inexpen(cid:173)
`sive, uncomplicated, "plug and play" type of Internet pro(cid:173)
`tection system that can be easily connected and configured
`by relatively unsophisticated users.
`
`15
`
`SUMMARY OF THE INVENTION
`
`The use of the Internet has exploded in recent years. Small
`and large companies as well as individual users are spending
`more time with their computers connected to the Internet.
`With the advent of Internet technologies, such as cable
`modems, digital subscriber lines, and other "broadband" 20
`access devices, users are connecting their computers to the
`Internet for extended periods of time.
`Such extended or "persistent" connection to the Internet
`brings many advantages to users in immediate access to the
`content on the Internet through the use of email, search 25
`engines, and the like. Unfortunately, however, persistent
`access to the Internet exposes connected computers to
`potential security threats, where intruders and "hackers"
`may compromise proprietary systems, engage in informa(cid:173)
`tion theft, or take control of the connected computers 30
`remotely. With more sophisticated tools at their disposal,
`hackers pose security and privacy risks to systems with
`persistent access to the Internet. Such security risks are even
`present for computers connected to the Internet for limited
`periods of time (such as through dial-up, modem connec- 35
`tions ), though to a lesser degree than the extended access
`computers.
`There are currently many different types of firewall sys(cid:173)
`tems available on the market, including proxy servers,
`application gateways, stateful inspection firewalls, and 40
`packet filtering firewalls, each of which provides a variety of
`strategies and services for data protection. Conventional
`packet filters typically are computers, routers, or ASICs
`based on general purpose CPUs. They perform their filtering
`duties by receiving a packet, buffering the data until a 45
`determination can be made, and forwarding the packet as
`applicable for the particular system. For example, a dual(cid:173)
`homed, Linux-based filter with two network cards might
`receive a packet completely, evaluate whether it meets
`specific criteria, and transmit the packet on the other net- 50
`work card. In another example, a router designed for switch
`mode routing might begin buffering a packet until a decision
`is made, then forward the packet on the applicable interface
`while still receiving the packet. With most packet filters,
`software is used and data is buffered.
`Sophisticated computer users working for medium- to
`large-sized companies have a variety of relatively expensive
`protection devices and tools at their disposal. Such devices
`and tools typically screen data packets received from the
`Internet with sophisticated software-based filtering tech- 60
`niques. Using relatively complex tools for software analysis,
`each packet is stored in a buffer and examined sequentially
`with software-based rules, which results in each packet
`being either accepted (and passed to the computer) or
`rejected (and disposed of by the software). This software
`often requires substantial computer knowledge and experi(cid:173)
`ence. Users of such devices and tools typically have an
`
`In accordance with the present invention, devices, meth-
`ods and systems are provided for the filtering of Internet data
`packets in real time and without packet buffering. A stateful
`packet filtering hub is provided in accordance with preferred
`embodiments of the present invention. The present invention
`also could be implemented as part of a switch or incorpo(cid:173)
`rated into a router.
`A packet filter is a device that examines network packet
`headers and related information, and determines whether the
`packet is allowed into or out of a network. A stateful packet
`filter, however, extends this concept to include packet data
`and previous network activity in order to make more intel(cid:173)
`ligent decisions about whether a packet should be allowed
`into or out of the network. An Ethernet hub is a network
`device that links multiple network segments together at the
`medium level (the medium level is just above the physical
`level, which connects to the network cable), but typically
`provides no capability for packet-type filtering. As is known,
`when a hub receives an Ethernet packet on one connection,
`it forwards the packet to all other links with minimal delay
`and is accordingly not suitable as a point for making
`filtering-type decisions. This minimum delay is important
`since Ethernet networks only work correctly if packets travel
`between hosts (computers) in a certain amount of time.
`In accordance with the present invention, as the data of a
`packet comes in from one link (port), the packet's electrical
`signal is reshaped and then transmitted down other links.
`During this process, however, a filtering decision is made
`between the time the first bit is received on the incoming
`port and the time the last bit is transmitted on the outgoing
`links. During this short interval, a substantial number of
`filtering rules or checks are performed, resulting in a deter(cid:173)
`mination as to whether the packet should or should not be
`invalidated by the time that the last bit is transmitted. To
`execute this task, the present invention performs multiple
`filtering decisions simultaneously: data is received; data is
`transmitted; and filtering rules are examined in parallel and
`in real time. For example, on a 100 Mbit/sec Ethernet
`55 network, 4 bits are transmitted every 40 nano seconds (at a
`clock speed of 25 MHz). The present invention makes a
`filtering decision by performing the rules evaluations simul(cid:173)
`taneously at the hardware level, preferably with a program-
`mable logic device.
`The present invention may employ a variety of network-
`ing devices in order to be practical, reliable and efficient. In
`addition, preferred embodiments of the present invention
`may include constituent elements of a stateful packet filter(cid:173)
`ing hub, such as microprocessors, controllers, and integrated
`65 circuits, in order to perform the real time, packet-filtering,
`without requiring buffering as with conventional techniques.
`The present invention preferably is reset, enabled, disabled,
`
`Ex.1001
`CISCO SYSTEMS, INC. / Page 16 of 29
`
`

`

`US 7,013,482 Bl
`
`4
`FIG. 3 is a flow chart illustrating the basic functions of a
`repeater core and four filter levels in accordance with
`preferred embodiments of the present invention;
`FIG. 4 is a diagram illustrating filtering functions of Level
`2 filters in relation to the flow of packet data from internal
`and external networks in accordance with preferred embodi(cid:173)
`ments of the present invention;
`FIG. 5 is a flow chart illustrating packet filtering functions
`of Level 3 filters in accordance with preferred embodiments
`10 of the present invention;
`FIG. 6 illustrates the rules by which TCP and UDP
`packets are evaluated in parallel in accordance with pre(cid:173)
`ferred embodiments of the present invention;
`FIG. 7 is a diagram illustrating parallel rule evaluation for
`15 TCP and UDP packets in accordance with preferred embodi(cid:173)
`ments of the present invention;
`FIG. 8 is a flow chart illustrating packet filtering functions
`of Level 4 filters in accordance with preferred embodiments
`of the present invention;
`FIG. 9 is a block diagram of the hardware components of
`a preferred embodiment of the present invention;
`FIG. 10 is an illustration of an exemplary design of an
`external case in accordance with preferred embodiments of
`the present invention;
`FIGS. 11 and 12 are flow diagrams illustrating SYN flood
`protection in accordance with preferred embodiments of the
`present invention; and
`FIG. 13 is a flow chart illustrating the process of "garbage
`collection" in flood lists in accordance with preferred
`embodiments of the present invention.
`
`25
`
`20
`
`3
`configured and/or reconfigured with relatively simple
`toggles or other physical switches, thereby removing the
`requirement for a user to be trained in sophisticated com(cid:173)
`puter and network configuration. In accordance with pre(cid:173)
`ferred embodiments of the present invention, the system 5
`may be controlled and/or configured with simple switch
`activation(s).
`Accordingly, one object of the present invention is to
`simplify the configuration requirements and filtering tasks of
`Internet firewall and data protection systems.
`Another object is to provide a device, method and system
`for Internet firewall and data protection that does not require
`the use of CPU-based systems, operating systems, device
`drivers, or memory bus architecture to buffer packets and
`sequentially carry out the filtering tasks.
`A further object of the present invention is to perform the
`filtering tasks of Internet firewall protection through the use
`of hardware components.
`Another object is to utilize programmable logic for fil(cid:173)
`tering tasks.
`Still another object is to provide a device, method, and
`system to carry out bitstream filtering tasks in real time.
`Yet another object is to perform parallel filtering, where
`packet data reception, filtering, and transmission are con(cid:173)
`ducted simultaneously.
`A further object of the present invention is to perform the
`filtering tasks relatively faster than current state-of-the-art,
`software-based firewall/data protection systems.
`Another object is to provide a device, method and system
`for firewall protection without the use of a buffer or tern- 30
`porary storage area for packet data.
`Still another object of the present invention is to design a
`device, method and system that does not require software
`networking configurations in order to be operational.
`A further object of the present invention is to provide a 35
`device, method and system for Internet firewall and data
`security protection that supports partitioning a network
`between client and server systems.
`It is a yet another object of the present invention to
`provide a device, method and system for Internet firewall 40
`and data protection that supports multiple networking ports.
`Another object is to maintain stateful filtering support for
`standard data transmission protocols on a per port basis.
`Still another object of is to configure network function(cid:173)
`ality using predefined toggles or other types of physical 45
`switches.
`A further object of the present invention is to conduct
`packet filtering without requiring a MAC address or IP
`address to perform packet filtering.
`Yet another object of the present invention is to facilitate 50
`the shortest time to carry out bitstream filtering tasks.
`Finally, it is another object of the present invention to be
`able to perform filtering rules out of order and without the
`current state-of-the-art convention of prioritizing the filter(cid:173)
`ing rules serially.
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`
`The present invention will be described in greater detail
`with reference to certain preferred and alternative embodi(cid:173)
`ments. As described below, refinements and substitutions of
`the various embodiments are possible based on the prin(cid:173)
`ciples and teachings herein.
`FIG. lAand FIG. 1B illustrate the physical positioning of
`a stateful packet filtering hub in accordance with the present
`invention in two exemplary network configurations. The
`packet filtering hub of the illustrated embodiments prefer(cid:173)
`ably serves as an Internet firewall/data protection system
`(hereafter "data protection system").
`With reference to FIG. lA, in the illustrated embodiment
`data protection system 1 is coupled through a port to router
`2 ( or cable modem or other preferably broadband, persistent
`network connection access device), which is linked through
`a broadband connection to other computer systems and
`networks, exemplified by Internet 8 and Internet Service
`Provider (ISP) 10. Packets of data are transmitted from an
`ISP, such as ISP 10, via Internet 8 to router 2. The packets
`are transmitted to data protection system 1, which analyzes
`55 the packets in "real time" and without buffering of the
`packets, while at the same time beginning the process of
`transmitting the packet to the internal network(s) in com(cid:173)
`pliance with the timing requirements imposed by the Eth(cid:173)
`ernet or other network standards/protocols. If a packet of
`60 data satisfies the criteria of the rules-based filtering per(cid:173)
`formed within data protection system 1, which is executed
`in a manner to be completed by the time the entire packet has
`been received by data protection system 1, then it is allowed
`to pass to hub 6 as a valid packet, which may then relay the
`65 cleared packet to computers 4a, 4b, 4c, etc. on the internal
`network. If a packet of data fails to meet the filtering criteria,
`then it is not allowed to pass as a valid packet and is
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The present invention may be more fully understood by a
`description of certain preferred embodiments in conjunction
`with the attached drawings in which:
`FIGS. lA and lB are application level diagrams illustrat(cid:173)
`ing exemplary data protection systems in accordance with
`the present invention;
`FIG. 2 is a flow diagram illustrating the components and
`operations of a preferred embodiment of the present inven(cid:173)
`tion;
`
`Ex.1001
`CISCO SYSTEMS, INC. / Page 17 of 29
`
`

`

`US 7,013,482 Bl
`
`5
`"junked." Junking is defined as changing bits or truncating
`data, depending on the type oflink, in a manner such that the
`packet is corrupted or otherwise will be detected by the
`receiving computers as invalid or unacceptable, etc. Without
`the intermediate positioning of data protection system 1, the 5
`packets would be transmitted directly to unprotected hub 6,
`thereby exposing computers 4a, 4b and 4c to security risks.
`It should also be noted that hub 6 is optional in accordance
`with the present invention; in other embodiments, data
`protection system 1 may be directly connected to a single 10
`computer or may have multiple ports that connect to mul(cid:173)
`tiple computers. Similar filtering is performed on packets
`that are to be transmitted from computers 4a, 4b, and 4c to
`Internet 8.
`With reference to FIG. lB, in this illustrated embodiment 15
`data protection system 1 is coupled via one port to DSL
`router 2 (again, the network access device is not limited to
`a DSL router, etc.), which provides the broadband connec(cid:173)
`tion to Internet 8. As with the embodiment of FIG. lA, data
`protection system 1 also is coupled to a number of comput(cid:173)
`ers 4a, 4b, etc., on the internal network, and serves to
`provide filtering for packets between computers 4a and 4b
`and Internet 8 in the manner described in connection with
`FIG. lA. In this embodiment, data protection system 1 is
`also connected via another port to hub 6, which serves as the
`main point of contact for incoming connections from the
`Internet for bastion hosts Sa and Sb, etc. In accordance with
`this embodiment, packets are transmitted to router 2 and
`then to data protection system 1. If the packets are approved
`by data protection system 1 (i.e., passing the filtering rules/
`checks performed with data protection system 1 while the
`packet is being received and transmitted), then the packets
`are allowed to pass as valid packets to computers 4a, 4b and
`hub 6. (The rules-based filtering process of preferred
`embodiments of the present invention will be described in
`more detail hereinafter.) Hub 6 may relay the packets to
`other internal host computers Sa, Sb, etc., on the local area
`network (LAN). These computers may include, for example,
`a Web and FTP server Sa, or a streaming audio server Sb, etc.
`Thus, in accordance with the illustrated embodiment, pack(cid:173)
`ets that passed the filtering rules/checks are passed as valid
`packets to computers, such as protected internal host com(cid:173)
`puter 4a, which as illustrated may be connected to printer 7.
`In this particular embodiment, a bastion port is provided that
`may be used to service more than one bastion host. In other
`embodiments, different network configurations may be uti(cid:173)
`lized in accordance with the present invention.
`FIG. 2 illustrates the general components and operations
`of certain preferred embodiments of the present invention.
`Connection to external network 12 is made by physical
`interface 14. Physical interface (or PHY) 14 preferably is
`implemented with