United States Patent [191
`Mayes et a1.
`
`US005793763A
`[11] Patent Number:
`[45] Date of Patent:
`
`5,793,763
`Aug. 11, 1998
`
`[54] SECURITY SYSTEM FOR NETWORK
`ADDRESS TRANSLATION SYSTEMS
`
`[75] Inventors: John C. Mayes. Redwood City. Calif.;
`Brantley W. Coile. Athens, Ga.
`
`[73] Assignee: Cisco Technology, Inc.. San Jose. Calif.
`
`Y. Reckhter. B.. Moskowitz. D. Karrenberg. and G. de
`Groot. “Address Allocation for Private Internets. " RFC
`1597. T]. Watson Research Center. IBM. Corp. Chrysler
`Corp.. RIPE NCC. Mar. 1994.
`
`K. Egevang and P. Francis. “The IP Network Address
`Translator (NAT).” RFC 1631. Cray Communications. N'IT.
`May. 1994.
`
`[21] Appl. No.: 552,807
`[22] Filed:
`Nov. 3, 1995
`
`[51] Int. Cl.6 ...................................................... .. H04J 3/24
`[52] US. Cl. ........................ .. 370/389; 370/401; 370/466;
`395/ 187.01
`[58] Field of Search ................................... .. 370/389. 351.
`370/249. 401. 466; 395/186. 187.01
`
`[56]
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,962,532 10/1990 Kasimj et a1.
`
`380/25
`
`5,159,592 10/1992 Perkins . . . . . . . . . . . . .
`
`. . . . . .. 370/401
`
`340/825.52
`2/1994 Kasprzyk et a1.
`5,287,103
`395/200
`5,371,852 12/1994 Attanasio et a].
`370/54
`5,430,715
`7/1995 Oorbalis et a1. ..
`370/249
`5,477,531 12/1995 McKee et a1.
`395/186
`5,513,337
`4/1996 Gillespie et a1. .
`370/466
`5,550,984
`8/1996 Gelb ............... ..
`5,623,601
`4/1997 Vu .................................... .. 395/l87.0l
`
`OTHER PUBLICATIONS
`
`Internet posting for Test Sites to Beta Test an IP Address
`Translation product; posted on ?rewalls mailing list: posting
`made on or after Oct. 28,1994.
`
`Primary Examiner-Douglas W. Olms
`Assistant Examiner-Shick Horn
`Attorney, Agent, or Firm-Beyer & Weaver. LLP
`
`[57]
`
`ABSTRACT
`
`A system and method are provided for translating local IP
`addresses to globally unique IP addresses. This allows local
`hosts in an enterprise network to share global IP addresses
`from a limited pool of such addresses available to the
`enterprise. The translation is accomplished by replacing the
`source address in headers on packets destined for the Inter
`net and by replacing destination address in headers on
`packets entering the local enterprise network from the
`Internet. Packets arriving from the Internet are screened by
`an adaptive security algorithm. According to this algorithm,
`packets are dropped and logged unless they are deemed
`nonthreatening. DNS packets and certain types of ICMP
`packets are allowed to enter local network In addition. FTP
`data packets are allowed to enter the local network. but only
`after it has been established that their destination on the local
`network initiated an FTP session.
`
`42 Claims, 11 Drawing Sheets
`
`N
`
`Does the trnnslollnn slot speedy
`0 static translation?
`
`15 the inbound
`pocket on ICMP
`pocket’?
`
`218*‘
`Drop and
`to Pocket
`9
`I212
`.
`Process Inbound
`pocket 05 required
`for dynamic
`translations
`
`N is the ICMP Pocket
`of an approved type?
`Y
`[229
`Trcnslole
`PM“
`1 w
`/'
`Forward
`Pocket
`J
`
`226
`
`fLQm
`
`Is a secure flog
`set in the
`translation stol?
`
`Does the inbound
`pocket meet
`UDP/TCP Security
`Criteria?
`
`Drop and Leg
`pocket
`22.]
`
`Google Ex. 1105, pg. 1
`
`

`

`US. Patent
`
`Aug. 11, 1998
`
`Sheet 1 of 11
`
`5,793,763
`
`/- 180.
`
`PRIVATE
`NETWORK
`INTERFACE
`
`18b [
`EXTERNAL
`NETWORK
`INTERFACE
`
`[Z2
`
`[10
`
`FLASH MEMORY
`1
`[24
`12 [
`I/o CIRCUIT G
`14
`[
`
`DISPLAY
`
`CPU
`
`16 /
`MEMORY
`
`FIG. 1
`
`Google Ex. 1105, pg. 2
`
`

`

`US. Patent
`
`Aug. 11, 1998
`
`Sheet 2 of 11
`
`5,793,763
`
`Google Ex. 1105, pg. 3
`
`928$8w
`
`\l/Ii.mu.$852a.828mm3%
`
`$38I22n:“6BoaIanum—I
`
`VS
`
`533m52226:.
`
`
`
`{9502omisfifi
`
`mm
`
`mm..\
`
`
`
`#55332foimz
`
`¥u=1v~=H
`
`94
`
`#m:_m#=H
`
`m:o_#o=_wmmo
`
`v»
`
`Google Ex. 1105, pg. 3
`
`
`
`
`

`

`US. Patent
`
`Aug. 11, 1998
`
`Sheet 3 of 11
`
`5,793,763
`
`(j 94
`96
`
`Start
`
`Hos on outbound
`pocket been received?
`
`90
`[
`
`N
`
`.
`Is 0 tronslotlon slot
`
`N
`
`lo
`
`Is the host listed in o
`-
`
`table of GHSOfOGttCSrJtFOHSIUtIOD
`Y
`
`106
`.
`. /
`E?‘mt'nefghe iré‘ns'f‘to'gnt
`
`s o
`
`r
`
`e
`
`"0
`
`Is pocket O
`TCP pocket?
`N
`
`118
`Y
`>
`
`2
`
`“unable? D’ errgor
`104
`Y
`f
`Drop
`outbound rmket
`120 |_\
`[
`Creote o
`t
`consn?? ‘on
`
`A l tocdte 0
`translation Slot
`\108
`
`Y
`
`Is the SYN
`bit set?
`N
`
`Locate the
`Connection Slot
`for the host
`
`\-122
`
`112
`
`\
`
`Translate the
`P Source
`Address
`t
`F ix Check Sums
`t
`Route the Pocket /”6
`outside of Network
`
`/-114
`
`124
`
`FIG. 3
`
`Google Ex. 1105, pg. 4
`
`

`

`US. Patent
`
`Aug. 11, 1998
`
`Sheet 4 of 11
`
`5,793,763
`
`Tronslotion Slot
`
`Connection Slot
`
`/-132
`130
`Next
`\ Globol ’134
`Locol r136
`Conn H38
`Free ’"740
`Stamp "25
`Flogs "
`UDP Holes "146
`TCP Holes "'48
`
`162\
`
`160
`Next
`Flcl9s /
`168K Foddr
`170
`F Port
`K L Port
`Delto
`'\ Stomp
`176\ x fer
`178" Stort
`
`FIG. 4A
`
`_
`
`FIG. 4B
`
`Google Ex. 1105, pg. 5
`
`

`

`US. Patent
`
`Aug. 11, 1998
`
`Sheet 5 of 11
`
`5,793,763
`
`202
`
`Has an inbound packet
`been received?
`
`204
`
`206'
`
`N Does a translation slot exist
`for packet destination?
`{Y
`/210
`(Does the translation slot specify
`Y
`a static translation’?
`
`N
`
`[214
`
`.
`pliktehte oknbfggg
`pocket?
`
`Y
`
`N
`
`Drop and
`Log Packet
`
`313
`1
`Drop and
`log Packet
`[212
`Process inbound
`packet as required
`for dynamic
`translations
`
`N Is the ICMPdPtacket)
`e?
`of an a rave
`pp
`yp
`Y
`[220
`l
`T
`t
`“ms 0 6
`Pocket
`[222
`Forward
`Packet
`
`$0
`
`18s: tseicrprihlloq
`translation slot?
`Y
`
`N
`
`226
`
`.
`
`.
`
`,3
`
`Does the inbound
`packet meet
`UDP/TCP Security
`Crlterlo‘
`N
`Drop and Log
`Pocket
`228]
`
`Google Ex. 1105, pg. 6
`
`

`

`US. Patent
`
`Aug. 11, 1998
`
`Sheet 6 of 11
`
`5,793,763
`
`240
`
`r242
`
`246
`
`Is inbound pocket
`0 UDP pocket?
`
`Does the UDP pocket
`meet specified UDP
`security or iterio?
`
`Does the TCP
`pocket meet specified
`security cr iter :0?
`
`Google Ex. 1105, pg. 7
`
`

`

`US. Patent
`
`Aug. 11,1998
`
`Sheet 7 of 11
`
`5,793,763
`
`$5 A than
`H963 m5 3
`
`230w n to%
`#963 m5 3
`
`A25
`
`2/7363 2535 30m
`
`$1
`
`
`x2523 of £39:
`
`>
`
`$2;
`r3960 0 P25
`
`A .QPN
`
`§ 26a
`
`in
`
`NAN
`
`26o
`
`LD
`
`Google Ex. 1105, pg. 8
`
`

`

`US. Patent
`
`Aug. 11, 1998
`
`Sheet 8 of 11
`
`5,793,763
`
`wymo;
`
`cOZUmccooommooNQN
`
`
`LOVym_xm#o_m“mmmo_%z>m.
`
`co_¥ocmymmvwigoo_%xo<vcoW#hucmwoWhoa
`
`wgomyo:2cmo_oexm
`
`:o_#umc=ooommoo
`
`
`
`
`
`cc=02c_zofios#o_m
`
`
`
`wo%c_“mxuoa
`
`
`
`meocaanymmoo
`
`cmHHgoam
`
`meuoamcflmooo
`
`>¥_L:omwmpg#mme
`
`mo_Lm:_o
`
`m65%
`
`
`
`wyo_mco_wo_mco_y
`
`
`
`#mxooqvcson:_mmoo
`
`m~_:vcoomnwcoyos
`
`wmm
`
`Google Ex. 1105, pg. 9
`
`omm
`
`Google Ex. 1105, pg. 9
`
`
`
`
`
`
`
`

`

`US. Patent
`
`Aug. 11, 1998
`
`Sheet 9 of 11
`
`5,793,763
`
`300
`
`302
`
`Does on FTP
`control connection
`s iot exist?
`
`304
`
`Has the local
`host issued 0
`port command?
`
`Is 0 connection
`s lot ova 1 lob le?
`
`[-308
`Create a
`connection 5 iot
`for the inbound
`pocket
`
`310
`Done
`T/F
`
`#2
`Done
`D/L
`
`FIG. 9
`
`Google Ex. 1105, pg. 10
`
`

`

`US. Patent
`
`Aug. 11, 1998
`
`Sheet 10 of 11
`
`5,793,763
`
`212 \
`
`320
`
`Start
`
`324
`
`Is the pocket
`a ping request;
`N
`Y
`
`322
`
`Y Is the inbound pocket
`Kan ICMP pocket?
`N
`
`328
`
`330
`
`Is the inbound pocket Y
`O UDP pocket?
`
`Does tileuglgcket
`mee
`security criter in?
`
`N
`
`332
`
`N
`
`Y
`
`Is the inbound packet N
`
`334
`r Does the pocket
`Y
`meet the TCP '
`\ security criteria?
`
`326
`Is the ICMP
`pocket of on
`
`\
`N
`
`approved type’? _J
`
`Y
`
`336
`
`338
`
`Done
`T/F
`
`DOA
`
`FIG. 10
`
`Google Ex. 1105, pg. 11
`
`

`

`US. Patent
`
`Aug. 11, 1998
`
`Sheet 11 0f 11
`
`5,793,763
`
`Ezra
`2:33 at
`62 E25 38
`
`E03 2: $8
`SN u tam
`
`of .2 ES Em
`5:858 a $8
`
`9585 522 z E; 5:853 88
`~22 #963
`
`
`
`N“ 65% 2 65m
`
`22 E a: v2 :5 A 10%
`Es 3m g: 2% E03 2: 3
`
`gm. gm
`
`Google Ex. 1105, pg. 12
`
`

`

`5,793,763
`
`1
`SECURITY SYSTEM FOR NETWORK
`ADDRESS TRANSLATION SYSTEMS
`
`BACKGROUND OF THE INVENTION
`
`2
`receiving packets on the Internet. it has a global IP address
`which is unavailable to any other host. After the host
`disconnects from the Internet. the enterprise takes back its
`global IP address and makes it available to other hosts
`wishing to access outside networks.
`To implement a NAT. a translation system must be
`provided between the enterprise private network and the
`Internet. By virtue of this location. the translation must act
`as a ?rewall to protect the local private network from
`unwanted Internet packets. In view of this requirement. it
`would be desirable to have a system which employs NAT
`and provides a secure ?rewall.
`
`SUMMARY OF THE INVENTION
`The present invention provides a system which employs
`NAT in conjunction with an adaptive security algorithm to
`keep unwanted packets from external sources out of a
`private network. According to this algorithm. packets are
`dropped and logged unless they are deemed nonthreatening.
`Domain Name Section “DNS” packets and certain types of
`Internet Control Message Protocol “ICMF’ packets are
`allowed to enter local network. In addition. File Transfer
`Protocol ‘FTP’ data packets are allowed to enter the local
`network. but only after it has been established that their
`destination on the local network initiated an FTP session.
`These and other features and advantages of the present
`invention will be presented in more detail in the following
`speci?cation of the invention and the ?gures.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 is a block diagram of a computer system for
`implementing the processes of a Network Address Transla
`tion system in accordance with this invention.
`FIG. 2 is a schematic diagram of a private network
`segment connected to the Internet via a NAT system of this
`invention.
`FIG. 3 is a process ?ow diagram showing generally the
`steps involved in transmitting an outbound packet through a
`NAT system to the Internet in accordance with this inven
`tion.
`FIG. 4A is a schematic illustration of a translation slot and
`associated ?elds in accordance with this invention.
`FIG. 4B is a schematic illustration of a connection slot
`and associated ?elds in accordance with this invention.
`FIG. 5 is a process ?ow diagram showing generally how
`an inbound packet is treated by a NAT system of this
`invention.
`FIG. 6 is a process ?ow diagram illustrating in some detail
`the security features employed to screen inbound packets
`destined for a local host having a static translation slot.
`FIG. 7 is a process ?ow diagram depicting a process for
`screening UDP packets destined for a local host having a
`static translation slot.
`FIG. 8 is a process ?ow diagram depicting a process for
`screening TCP packets destined for a local host having a
`static translation slot.
`FIG. 9 is a process ?ow diagram depicting those steps that
`may be employed to screen for FTP data destined for a
`private network.
`FIG. 10 is a process ?ow diagram depicting generally a
`security algorithm for screening packets destined for a local
`host having a dynamic translation slot.
`FIG. 11 is a process ?ow diagram depicting a process for
`screening UDP packets destined for a local host having a
`dynamic translation slot.
`
`The present invention relates to address n'anslation sys
`terns for mapping local Internet Protocol “IP” addresses
`used by hosts on a private network to globally unique IP
`addresses for communication with hosts on the Internet. The
`address translation systems have adaptive security mecha
`nisms to protect the private network from certain packet
`types sent from the Internet.
`Private networks are commonly connected to the Internet
`through one or more routers so that hosts (PCs or other
`arbitrary network entities) on the private network can com
`municate with nodes on the Internet. Typically. the host will
`send packets to locations both within its private network and
`on the Internet. To receive packets from the Internet. a
`private network or a host on that network must have a
`globally unique 32-bit IP address. Each such I? address has
`a four octet format. Typically. humans communicate IP
`addresses in a dotted decimal format. with each octet written
`as a decimal integer separated from other octets by decimal
`points.
`Global IP addresses are issued to enterprises by a central
`authority known as the Internet Assigned Number Authority
`(“IANA”). The IANA issues such addresses in one of three
`commonly used classes. Class A IP addresses employ their
`?rst octet as a “netid” and their remaining three octets as a
`“hostid.” The netid identi?es the enterprise network and the
`hostid identi?es a particular host on that network As three
`octets are available for specifying a host. an enterprise
`having class A addresses has 224 (nearly 17 million)
`addresses at its disposal for use with possible hosts. Thus.
`even the largest companies vastly underuse available class A
`addresses. Not surprisingly. Class A addresses are issued to
`only very large entities such as IBM and A11‘. Class B
`addresses employ their ?rst two octets to identify a network
`(netid) and their second two octets to identify a host (hostid).
`Thus. an enterprise having class B addresses can use those
`40
`addresses on approximately 64.000 hosts. Finally. class C
`addresses employ their ?rst three octets as a netid and their
`last octet as a hostid. Only 254 host addresses are available
`to enterprises having a single class C netid.
`Unfortunately. there has been such a proliferation of hosts
`on the Internet. coupled with so many class A and B licenses
`issued to large entities (who have locked up much address
`space). that it is now nearly impossible to obtain a class B
`address. Many organizations now requiring Internet access
`have far more than 254 hosts-for which unique IP
`addresses are available with a single class C network
`address. It is more common for a mid to large size enterprise
`to have 1000 to 10.000 hosts. Such companies simply can
`not obtain enough 1P addresses for each of their hosts.
`To address this problem a Network Address Translation
`(“NAT”) protocol has been proposed. See K. Egevang and P.
`Francis. ‘The IP Network Address Translator (NAT).”
`Request For Comments “RFC" 1631. Cray
`Communications. N'IT. May 1994 which is incorporated
`herein by reference for all purposes. NAT is based on the
`concept of address reuse by private networks. and operates
`by mapping the reusable IP addresses of the leaf domain to
`the globally unique ones required for communication with
`hosts on the Internet. In implementation. a local host wish
`ing to access the Internet receives a temporary 1P address
`from a pool of such addresses available to the enterprise
`(e.g.. class C 254 addresses). While the host is sending and
`
`20
`
`30
`
`45
`
`65
`
`Google Ex. 1105, pg. 13
`
`

`

`3
`FIG. 12 is a process ?ow diagram depicting a process for
`screening TCP packets destined for a local host having a
`dynamic translation slot.
`
`DESCRIPTION OF THE PREFERRED
`EMBODHVIENTS
`
`l. De?nitions
`
`The following terms are used in the instant speci?cation.
`Their de?nitions are provided to assist in understanding the
`preferred embodiments described herein.
`A “host" is a PC or other arbitrary network entity residing
`on a network and capable of communicating with entities
`outside of its own network through a router or bridge.
`A “router" is a piece of hardware which operates at the
`network layer to direct packets between various nodes of
`one or more networks. The network layer generally allows
`pairs of entities in a network to communicate with each other
`by ?nding a path through a series of connected nodes.
`A “packet” is a collection of data and control information
`including source and destination node addresses and source
`and destination ports. The octet of destinations and ports
`make every connection and packet unique.
`
`2. Overview
`The invention employs various process steps involving
`data manipulation. These steps require physical manipula
`tion of physical quantities. Typically. these quantities take
`the form of electrical or magnetic signals capable of being
`stored. transferred. combined. compared. and otherwise
`manipulated. It is sometimes convenient. principally for
`reasons of common usage. to refer to these signals as bits.
`values. variables. characters. data packets. or the like. It
`should be remembered. however. that all of these and similar
`terms are to be associated with the appropriate physical
`quantities and are merely convenient labels applied to these
`quantities.
`“
`Further. the manipulations performed are often referred to
`in terms. such as translating. running. selecting. specifying.
`determining. or comparing. In any of the operations
`described herein that form part of the present invention.
`these operations are machine operations. Useful machines
`for performing the operations of the present invention
`include general purpose and specially designed computers or
`other similar devices. In all cases. there should be borne in
`mind the distinction between the method of operations in
`operating a computer or other processing device and the
`method of computation itself. The present invention relates
`to method steps for operating a Network Address Translation
`system in processing electrical or other physical signals to
`generate other desired physical signals.
`The present invention also relates to an apparatus for
`performing these operations. This apparatus may be spe
`cially constructed for the required purposes. or it may be a
`general purpose programmable machine selectively acti
`vated or recon?gured by a computer program stored in
`memory. The processes presented herein are not inherently
`related to any particular computer or other apparatus. In
`panicular. various general purpose machines may be used
`with programs written in accordance with the teachings
`herein. or it may be more convenient to construct a more
`specialized apparatus to perform the required method steps.
`The general structure for a variety of these machines will
`appear from the description given below.
`Still further. the present invention relates to machine
`readable media on which are stored program instrucu'ons for
`
`10
`
`20
`
`25
`
`35
`
`45
`
`55
`
`65
`
`5.793.763
`
`4
`performing operations on a computer. Such media includes
`by way of example magnetic disks. magnetic tape. optically
`readable media such as CD ROMs. semiconductor memory
`such as PCMCIA cards. etc. In each case. the medium may
`take the form of a portable item such as a small disk.
`diskette. cassette. etc.. or it may take the form of a relatively
`larger or immobile item such as a hard disk drive or RAM
`provided in a computer.
`FIG. 1 shows a typical computer-based system which may
`be used as a secure Network Address Translation system of
`the present invention. Shown is a computer 10 which
`comprises an input/output circuit 12 used to communicate
`information in appropriately structured form to and from the
`parts of computer 10 and associated equipment. a central
`processing unit 14. and a memory 16. These components are
`those typically found in most general and special purpose
`computers 10 and are intended to be representative of this
`broad category of data processors.
`Connected to the input/output circuit 12 are inside and
`outside high speed Local Area Network intmfaces 18a and
`18b. The inside interface 18a will be connected to a private
`network. While the outside interface 18b will be connected
`to an external network such as the Internet. Preferably. each
`of these interfaces includes (1) a plurality of ports appro
`priate for communication with the appropriate media. and
`(2) associated logic. and in some instances (3) memory. The
`associated logic may control such communications intensive
`tasks as packet integrity checking and media control and
`management. The high speed interfaces 18a and 18b are
`preferably multi-port Ethernet interfaces. but may be other
`appropriate interfaces such as FDDI interfaces. etc.
`The computer system may also include an input device
`(not shown) such as a keyboard. A ?ash memory device 22
`is coupled to the input/output circuit 12 and provides addi
`tional storage capability for the computer 10. The ?ash
`memory device 22 may be used to store programs. data and
`the like and may be replaced with a magnetic storage
`medium or some other well known device. It will be
`appreciated that the information retained within the ?ash
`memory device 22. may. in appropriate cases. be incorpo
`rated in standard fashion into computer 10 as part of the
`memory 16.
`In addition. a display monitor 24 is illustrated which is
`used to display the images being generated by the present
`invention. Such a display monitor 24 may take the form of
`any of several well-known varieties of cathode ray tube
`displays and ?at panel displays or some other type of
`display.
`Although the system shown in FIG. 1 is a preferred
`computer system of the present invention. the displayed
`computer architecture is by no means the only architecture
`on which the present invention can be implemented. For
`example. other types of interfaces and media could also be
`used with the computer.
`FIG. 2 shows a network arrangement 32 employing a
`network address translation system 34 of the present inven
`tion. Translation system 34 acts as a connection between an
`enterprise network 36 and the Internet 38. On the Internet
`side. translation system 34 connects to an Internet router 40
`via a line 42. Internet router 40. in turn. connects to Internet
`destinations 44 through a line 46. On the enterprise network
`side. translation system 34 connects to a router 48 via a line
`50. Router 48 is. in turn. linked to various nodes on the
`enterprise network 36 including node 52 (via line 54) and
`node 56 (via line 58).
`As an example. assume that node 52 sends packets 60a
`and 60b to router 48 along line 54. Packet 60a is destined for
`
`Google Ex. 1105, pg. 14
`
`

`

`5,793,763
`
`5
`the Internet as indicated by a packet header 62. In contrast,
`packet 60b is destined to for a node on the enterprise
`network as indicated by packet header 64. Upon receiving
`packets 60a and 60b. router 48 then routes packet 60b along
`line 58 to node 56 and routes packet 60a along line 50 to
`translation system 34.
`To this point. the system behaves consistent with most
`conventional networking protocols. However. packet 60a
`contains source address 66 which is not a Qobally unique IP
`address. Therefore. node 52 can not expect a reply from the
`Internet destination of packet 600. To remedy this problem.
`packet 60a is routed through translation system 34 which
`modi?es the packet so that it can establish a connection with
`a desired Internet destination. Speci?cally. when data packet
`60a reaches translation system 34. its local source address
`66 is replaced with an authorized global 1? source address 68
`selected from a pool of available global IP addresses 70.
`Pool 70 includes all or some subset of the global IP source
`addresses allocated to enterprise network 36.
`After packet 60a has been retooled with global IP address
`68. translation system 34 sends it along line 42 to Internet
`router 40. Router 40 then forwards it to the appropriate
`destination. Thereafter the Internet destination can reply
`with a packet of its own destined for global IP address 68.
`Upon receipt of such packet. translation system 34 will
`detennine if it presents a security risk. If not. it will replace
`address 68 on the inbound packet with the local address of
`node 52 and then forward the modi?ed packet to router 48.
`After the node 52 ?nishes its Internet session. address 68
`may be made available to other nodes desiring Internet
`access. In this manner. a relatively small number of global
`IP addresses can be used by a much larger network of hosts.
`
`20
`
`3. Processing of Packets Received by the NAT
`System
`The methods of this invention apply a security algorithm
`to network address translation. The basic address translation
`methodolgy may be directly adapted from RFC 1631. pre
`viously incorporated by reference.
`FIG. 3 details a process 90 that may be employed by
`network address translation system 34 upon receipt of
`packet from enterprise network 36. Such outbound packets
`are received at the inside interface 18a of system 34. The
`process begins at 94 and in a decision step 96 determines
`whether an outbound packet has been received from a host
`on enterprise network 36. If not. the system simply awaits
`receipt of such packet. If. on the other hand. such packet was
`indeed received. a decision step 98 determines whether the
`host sending the packet is listed in a table of allocated
`translation slots. This table includes a list of global and local
`IP addresses for all hosts that have a translation slot opened.
`Translation slots will be described in more detail below. For
`now. it is su?icient to recognize that a host’s local IP address
`will appear in the table of allocated translation slots if a
`translation slot has indeed been allocated for that host. To
`perform step 98. the NAT system ?rst examines the out
`bound packet source header to identify the local IP address.
`and then determines if that address is located in the trans
`lation slot table. If so. step 98 is answered in the a?irmative.
`Assuming that step 98 is in fact answered yes (i.e.. the
`translation slot table lists the local 1? source address on the
`packet). a process step 106 examines the actual translation
`slot for the local host identi?ed in the translation slot table.
`If on the other hand. step 98 is answered in the negative (i.e..
`the host sending the packet is not listed in the table of
`allocated translation slots). a decision step 100 determines
`
`45
`
`50
`
`55
`
`65
`
`6
`whether a new translation slot is available. If not. an error is
`logged at process step 102 and the packet is dropped without
`transmission at a step 104. Thereafter. process control
`returns to step 96. and system 34 awaits the next outbound
`packet. Steps 102 and 104 are necessary because the number
`of translation slots is limited by the number of global IP
`addresses available to the enterprise network. If the enter
`prise has only a single class C address collection. for
`example. no more than 254 translation slots can be used at
`any given time. The system of this invention does release
`global IP addresses (i.e.. it closes translation slots and
`removes their entries from the translation slot table) after a
`de?ned timeout period. Such period may be adjusted by the
`network according to the speci?c network’s requirements. A
`typical default value is 24 hours for example.
`Assuming that decision step 100 is answered in the
`affirmative (Le. a free translation slot exists). a process step
`108 allocates one such translation slot to the host sending the
`packet. The NAT system the ?lls the newly allocated slot
`with various pieces of relevant information (detailed below)
`including the local host’s local IP address and a global IP
`address selected from the pool of available addresses. In a
`speci?c embodiment. the global unique I? address selected
`from this pool is obtained by simply picking the next
`available address sequentially. The NAT system also enters
`the global and local IP addresses for the new translation slot
`in the translation slot table.
`Now. regardless of how a translation slot was identi?ed
`(via step 106 or 108). the next step is a decision step 110
`which determines whether the outbound packet is a Trans
`mission Control Protocol ‘TCP” packet. As known to those
`of skill in the art. this determination can be made by
`checking the appropriate ?eld in the packet header. The TCP
`protocol requires a connection be established before com
`munication can be commenced.
`If the outbound packet turns out not to be a TCP packet.
`a process step 112 simply translates the IP source address on
`that packet. In other words. the private source address
`initially appearing on the packet is replaced with the global
`unique IP address in the associated translation slot. After the
`1? source address has been replaced at step 112. a process
`step 114 ?xes the checksums at the end of the packet.
`Speci?cally. the address translator will modify the IP check
`sum and the TCP checksum. Since the differences between
`the original and translated versions of the packet are known.
`the checksums are efficiently updated with a simple adjust
`ment rather than a complete recalculation. Details including
`sample code are provided in RFC 1631. The address trans
`lator must also modify those parts of ICMP and FFP packets
`where the IP address appears. Next. the retooled packet is
`routed by translation system 34 to the Internet The process
`is then complete at 124.
`Assuming that decision step 10 determines that the packet
`is indeed a TCP packet. a decision step 118 then determines
`whether the “synchronized sequence number" SYN bit has
`been set in the TCP segment of a TCP header. As known to
`those skill in the art. this bit is set in the “code bits” section
`of the TCP header. When the SYN bit is set. it implies that
`the local host is attempting to establish a connection with a
`host on the Internet. Assuming that the internal host is in fact
`attempting to establish a connection. (i.e.. decision step 118
`is answered in affirmative). translation system 34 creates a
`new connection slot (if any are available) at a process step
`120. That slot is ?lled information uniquely describing the
`connection: the remote I? address. the remote port number.
`and the local port number. Concurrently therewith. the new
`connection is registered in a “connection ?eld” of the
`
`Google Ex. 1105, pg. 15
`
`

`

`5 ,793.763
`
`15
`
`7
`translation slot. Thereafter. process control is directed to step
`112 were the 1P source address is translated as described
`above. Then. the packet checksums are corrected and the
`packet is routed to the Internet as described above. Assum
`ing that decision step 118 is answered in the negative (i.e..
`the SYN bit is not set). the system will assume that a TCP
`session has already been synchronized and locate the con
`nection object associated with internal host’s current con
`nection as a step 122. This may be accomplished with a
`hashing algorithm for example. Thereafter. process control
`is directed to step 112 where the translation. modi?cation.
`and forwarding functions are performed as described above.
`If the outbound packet is a TCP packet without its SYN bit
`set and no existing connection is open. an error has occurred
`It should be apparent from the above discussion that there
`is essentially no security mechanism to block outbound
`packets. Most enterprises expect this behavior.
`FIG. 4A is a schematic depiction of a translation slot 130
`provided for use with the system/methods of this invention.
`In practice. the translation slot takes the form of a data
`structure stored in memory of the NAT system. In the
`translation slot data structure. a “nex ” ?eld 132 holds a
`pointer to the next translation slot in the translation slot
`table. This ?eld is updated whenever the next successive
`25
`translation slot times out while the slot at issue remains. A
`“global” ?eld 134 provides the global unique 1P address
`temporarily held by the host having the translation slot. A
`“local" address ?eld 136 speci?es the local address of the
`host. The global and local address ?elds are set when the
`translation slot is opened and they remain ?xed throughout
`the life of the slot.
`A “connection" ?eld 138 contains a listing of the con
`nection slots. if any. appended to the translation slot. More
`than one connection slot may be associated with a given
`translation slot. as many users may be using a given host to
`access the Internet. Each associated process will have its
`own connection slot. The connection ?eld 138 is updated
`each time a new connection slot is opened or timed out
`Next. a “free” ?eld 140 is reserved for a connection slot of
`a static translation slot. A “stamp” ?eld 142 provides a time
`stamp indicating when the translation slot last sent or
`received a packet. Thus. the stamp ?eld is updated each time
`an Internet packet passes from or to the local host. This is
`used for purposes of timing out a translation slot.
`Next. a “?ags” ?eld 144 contains one or more ?ags that
`may be set in connection with the translation slot 130.
`Examples of such ?ags include a “static ?ag" to be set when
`the translation slot is a “static" rather “dynamic" translation
`slot. This distinction will be discussed in more detail below.
`Another ?ag is a “port” ?ag to be set when a port command
`is issued by a local host initiating an FTP session. The User
`Detection Protocol Holes “UDP Holes” ?eld 146 and the
`"TCP Holes" ?eld 148 specify “conduits” or exceptions to
`the adaptive s