(12) United States Patent
`Swander
`
`USOO6904529B1
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 6,904,529 B1
`Jun. 7, 2005
`
`(54) METHOD AND SYSTEM FOR PROTECTING
`A SECURITY PARAMETER NEGOTIATION
`SERVER AGAINST DENIAL-OF-SERVICE
`ATTACKS
`
`(75) Inventor: Brian D. Swander, Kirkland, WA (US)
`(73) Assignee: Microsoft Corporation, Redmond, WA
`(US)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(*) Notice:
`
`(21) Appl. No.: 09/561,046
`(22) Filed:
`Apr. 28, 2000
`(51) Int. Cl." ................................................. G06F 11/30
`(52) U.S. Cl. ........................ 713/201; 713/151; 713/200
`(58) Field of Search ................................. 713/200, 201,
`713/151
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`5,923,849 A * 7/1999 Venkatraman .............. 709/224
`5,958,053 A * 9/1999 Denker ....................... 713/201
`6,330,562 B1 * 12/2001 Boden et al. ................. 707/10
`OTHER PUBLICATIONS
`“Analysis of a Denial of Service Attack on TCP, Proceed
`ings of the 1997 IEEE Symposium on Security and Privacy,
`1997, pp. 208-223.*
`
`Computer Communications 22(10): “TCP/IP Security
`Threats and Attack Methods”, Jun. 25, 1999, 885–97.
`“Client Puzzles: A Cryptographic Countermeasure Against
`Connection Depletion Attacks, Proceedings of the 1999
`Network and Distributed System Security Symposium, pp.
`151-65.
`“Analysis of a Denial of Service Attack on TCP, Proceed
`ings of the 1997 IEEE Symposium on Security and Privacy,
`1997, pp. 208-223.
`* cited by examiner
`Primary Examiner Justin T. Darrow
`(74) Attorney, Agent, or Firm-Leydig, Voit & Mayer, Ltd.
`(57)
`ABSTRACT
`A method and System protects a Security parameter nego
`tiation Server that Stores States for connection requests
`pending negotiations from malicious denial-of-Service
`attacks that attempt to flood the Server with false requests.
`The degradation of performance of the Server is dynamically
`detected, Such as by monitoring the running intervals of a
`reaper that removes unneeded States. When performance
`degradation of the System is detected, relevant performance
`variables Such as negotiation delay, extra retransmission
`delay and packet drop percentage are dynamically adjusted
`to reduce the workload on the negotiation Server. Limiting
`the number of States with incomplete negotiation status for
`each client and the total number of Such states further
`enhances the effectiveness of the protection against denial
`of-Service attackS.
`
`16 Claims, 3 Drawing Sheets
`
`
`
`
`
`
`
`
`
`
`
`Reader thread
`
`Sever thread
`
`146
`
`Determine reaper
`fun interial
`
`
`
`
`
`Adjust perf.
`wariables to reduce
`system workload
`
`144
`
`148
`
`Yes
`
`interwax SCS
`No
`
`Adjust perf.
`variables to retuff
`to original values
`
`Deny further
`request from client
`
`Yes
`
`150
`
`Neg-pending
`SAs is
`s?
`
`58
`
`No
`
`154
`
`Deny further new
`requests
`
`Yes
`
`total
`perding SAs X =
`threshold
`
`58
`
`New request
`drop rate is 0?
`
`
`
`16
`
`decrease new
`request drop rate
`
`Eric
`
`Cloudflare - Exhibit 1027, page 1
`
`

`

`U.S. Patent
`
`Jun. 7, 2005
`
`Sheet 1 of 3
`
`US 6,904,529 B1
`
`20
`
`SYSTEMMMORY
`
`(ROM)
`
`BIOS
`
`RAM
`(RAM)
`OPERATING
`SYSTEM
`
`APPLICATION
`PROGRAM
`
`OTHER
`PROGRAM
`MODULES
`
`PROGRAM
`DATA
`
`PERSONACOMPUTER
`
`21
`
`48
`
`PROCESSING
`UNIT
`
`VEDEO
`ADAPTER
`
`23
`
`22
`
`24
`
`26
`
`25
`
`35
`
`36
`
`53
`
`NWORK
`INTERFACE
`
`Monitor
`
`47
`
`32
`
`33
`
`34
`
`37 HARD DISK
`DRIVE
`NTERFAC
`
`MAGDISK OPTICAOISK SERIALPORT
`DRIVE
`RIVE
`INTERFACE
`INTERFACE
`NTERFACE
`
`38
`
`hard disk
`drive
`
`s
`-SE
`Magnetic disk optical drive
`drive
`
`30
`
`27
`
`28
`
`46
`
`51
`
`OEC29
`Modem
`
`54
`
`50
`
`29 -
`
`31
`
`
`
`OPERATING
`SYSTEM
`
`APPLICATION
`PROGRAMS
`
`PROG
`MODULES
`
`Figure 1
`
`armer a
`Keytoard
`
`40
`
`Mouse
`42
`
`49
`
`REMOTE COMPUTER
`
`50
`
`36
`
`
`
`APPLICATION
`PROGRAMS
`
`Cloudflare - Exhibit 1027, page 2
`
`

`

`U.S. Patent
`
`Jun. 7, 2005
`
`Sheet 2 of 3
`
`US 6,904,529 B1
`
`
`
`
`
`90
`
`86
`
`Host Computer
`
`Connection
`Request
`
`External Network
`
`82
`
`internal Network
`
`FIG 2
`
`Cloudflare - Exhibit 1027, page 3
`
`

`

`U.S. Patent
`
`Jun. 7, 2005
`
`Sheet 3 of 3
`
`US 6,904,529 B1
`
`Reaper thread
`
`Server thread
`
`Determine reaper
`
`w
`
`142
`
`R.
`
`140
`
`
`
`
`
`
`
`
`
`Adjust perf.
`variables to reduce
`system workload
`
`Y
`eS
`
`
`
`Interval 2 60S
`
`144
`-1.
`
`No
`
`148
`
`152
`
`Deny further
`request from client
`
`156
`
`Deny further new
`requests
`Q
`
`
`
`Adjust perf.
`variables to return
`to original values
`
`Yes
`
`
`
`Neg-pending
`SAS D = 6?
`
`150
`
`
`
`
`
`No
`
`154
`
`Yes
`
`-
`Total
`pending SAs > =
`threshold?
`
`NO
`
`158
`
`
`
`
`
`
`
`New request
`drop rate = 0?
`
`Yes
`
`FIG. 3
`
`160
`
`decrease new
`request drop rate
`
`End
`
`Cloudflare - Exhibit 1027, page 4
`
`

`

`1
`METHOD AND SYSTEM FOR PROTECTING
`A SECURITY PARAMETER NEGOTIATION
`SERVER AGAINST DENIAL-OF-SERVICE
`ATTACKS
`
`TECHNICAL FIELD OF THE INVENTION
`This invention relates generally to network
`communications, and more particularly to Security threats to
`communication Servers in a network environment.
`
`BACKGROUND OF THE INVENTION
`The Internet has entered the new millenium as the most
`important computer network of the World. Everyday, mil
`lions of people use the Internet to communicate with each
`other and to gather or Share information. Moreover, elec
`tronic commerce (“E-commerce”) using the World-Wide
`Web (WWW) of the Internet as its backbone is rapidly
`replacing and changing the conventional brick-and-mortar
`StOreS.
`The Security of communications through the Internet,
`however, has always been a major concern. This problem is
`related to the underlying network communication protocol
`of the Internet, the Internet Protocol ("IP"), which is respon
`Sible for delivering packets across the Internet to their
`destinations. The Internet Protocol was not designed to
`provide Security features at its level of network communi
`cation operation. Moreover, the flexibility of IP allows for
`Some creative uses of the protocol that defeat traffic auditing,
`access control, and many other Security measures. IP-based
`network data is therefore wide open to tampering and
`eavesdropping. As a result, it Substantial risks are involved
`in Sending Sensitive information acroSS the Internet.
`To address the lack of Security measures of the Internet
`Protocol, a set of extensions called Internet Protocol Secu
`rity (“IPSec) Suite has been developed to add security
`services at the IP level. The IPSec Suite includes protocols
`for an authentication header (AH), encapsulating Security
`protocol (ESP), and a key management and exchange pro
`tocol (IKE). A significant advantage of the IPSec Suite is
`that it provides a universal way to secure all IP-based
`network communications for all applications and users in a
`transparent way. Moreover, as the IPSec Suite is designed to
`work with existing and future IP standards, regular IP
`networks can Still be used to carry communication data
`between the sender and recipient. The IPSec Suite is also
`Scalable and can therefore be used in networks ranging from
`local-area networks (LANS) to global networks such as the
`Internet.
`Even though the IPSec standard provides a comprehen
`Sive and robust way to Secure network communications
`against tampering and eavesdropping, the components
`implementing the IPSec Suite themselves may be subjected
`to various Security threats in the network environment. For
`instance, the IPSec layer includes a component called an
`“Internet Key Exchange” (“IKE”) server, which is respon
`sible for negotiating with another IKE for security
`parameters, collectively called a "Security ASSociation”
`("SA), of Security operations for Securing a given network
`communication Stream. For each Secured communication
`Stream, a separate SA has to be negotiated and maintained.
`Because of the System resources required for handling each
`communication requests, it is possible for an attacker to
`construct and Send a large number of false communication
`requests, forcing the IKE Server to consume large amounts
`of System resources. Such an attack potentially can burden
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,904,529 B1
`
`2
`the Server to the extent that it is no longer able to Serve
`legitimate users.
`
`SUMMARY OF THE INVENTION
`In View of the foregoing, the present invention provides a
`method and System for protecting a network Security Server
`for negotiating network Security parameters, Such as an
`Internet Key Exchange (“IKE”) server of the IPSec Suite,
`from denial-of-service attacks that flood the server with false
`connection requests. The Vulnerability of the Security Server
`to Such attacks comes from the need for the Server to
`maintain State data for on-going negotiations in response to
`requests from unknown clients. In accordance with the
`invention, the resilience of the negotiation Server to Such
`attackS is Significantly enhanced by dynamically detecting
`the degradation of the performance of the System, and
`dynamically adjusting relevant performance variables, Such
`as negotiation delay, retransmission delay, and packet drop
`percentage, etc., to reduce the States maintained by the
`negotiation Server when performance degradation is
`detected. A useful indicator of the system health may be the
`interval between consecutive runs of a reaper for removing
`States that are no longer useful. To further enhance the
`effectiveness of the protection against denial-of-Service
`attacks, the maximum number of States pending negotiation
`responses for Outstanding new negotiation requests from a
`client may be limited, and the total number of Stored States
`pending negotiation responses may also be limited.
`Additional features and advantages of the invention will
`be made apparent from the following detailed description of
`illustrative embodiments, which proceeds with reference to
`the accompanying figures.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`While the appended claims set forth the features of the
`present invention with particularity, the invention, together
`with its objects and advantages, may be best understood
`from the following detailed description taken in conjunction
`with the accompanying drawings of which:
`FIG. 1 is a block diagram generally illustrating an exem
`plary computer System on which the present invention may
`be reside;
`FIG. 2 is a Schematic diagram Showing a networked
`computer having a negotiation Server for negotiation of
`Security parameters for Securing network communications,
`and
`FIG. 3 is a flow diagram showing a proceSS embodying a
`method of the invention for protecting the negotiation Server
`against denial-of-Service attackS.
`DETAILED DESCRIPTION OF THE
`INVENTION
`Turning to the drawings, wherein like reference numerals
`refer to like elements, the invention is illustrated as being
`implemented in a Suitable computing environment.
`Although not required, the invention will be described in the
`general context of computer-executable instructions, Such as
`program modules, being executed by a personal computer.
`Generally, program modules include routines, programs,
`objects, components, data structures, etc. that perform par
`ticular tasks or implement particular abstract data types.
`Moreover, those skilled in the art will appreciate that the
`invention may be practiced with other computer System
`configurations, including hand-held devices, multi
`processor Systems, microprocessor based or programmable
`
`Cloudflare - Exhibit 1027, page 5
`
`

`

`US 6,904,529 B1
`
`15
`
`3
`consumer electronics, network PCs, minicomputers, main
`frame computers, and the like. The invention may also be
`practiced in distributed computing environments where
`tasks are performed by remote processing devices that are
`linked through a communications network. In a distributed
`computing environment, program modules may be located
`in both local and remote memory Storage devices.
`With reference to FIG. 1, an exemplary system for imple
`menting the invention includes a general purpose computing
`device in the form of a conventional personal computer 20,
`including a processing unit 21, a System memory 22, and a
`System buS 23 that couples various System components
`including the System memory to the processing unit 21. The
`System buS 23 may be any of Several types of bus Structures
`including a memory bus or memory controller, a peripheral
`bus, and a local bus using any of a variety of bus architec
`tures. The System memory includes read only memory
`(ROM) 24 and random access memory (RAM) 25. A basic
`input/output System (BIOS) 26, containing the basic routines
`that help to transfer information between elements within
`the personal computer 20, Such as during Start-up, is Stored
`in ROM 24. The personal computer 20 further includes a
`hard disk drive 27 for reading from and writing to a hard disk
`60, a magnetic disk drive 28 for reading from or writing to
`a removable magnetic disk 29, and an optical disk drive 30
`for reading from or writing to a removable optical disk 31
`such as a CD ROM or other optical media.
`The hard disk drive 27, magnetic disk drive 28, and
`optical disk drive 30 are connected to the system bus 23 by
`a hard disk drive interface 32, a magnetic disk drive inter
`face 33, and an optical disk drive interface 34, respectively.
`The drives and their associated computer-readable media
`provide nonvolatile Storage of computer readable
`instructions, data structures, program modules and other
`data for the personal computer 20. Although the exemplary
`environment described herein employs a hard disk 60, a
`removable magnetic disk 29, and a removable optical disk
`31, it will be appreciated by those skilled in the art that other
`types of computer readable media which can Store data that
`is accessible by a computer, Such as magnetic cassettes, flash
`memory cards, digital Video disks, Bernoulli cartridges,
`random access memories, read only memories, and the like
`may also be used in the exemplary operating environment.
`A number of program modules may be Stored on the hard
`disk 60, magnetic disk 29, optical disk 31, ROM 24 or RAM
`45
`25, including an operating System 35, one or more applica
`tions programs 36, other program modules 37, and program
`data 38. A user may enter commands and information into
`the personal computer 20 through input devices Such as a
`keyboard 40 and a pointing device 42. Other input devices
`(not shown) may include a microphone, joystick, game pad,
`Satellite dish, Scanner, or the like. These and other input
`devices are often connected to the processing unit 21
`through a Serial port interface 46 that is coupled to the
`System bus, but may be connected by other interfaces, Such
`as a parallel port, game port or a universal Serial bus (USB).
`A monitor 47 or other type of display device is also
`connected to the System buS 23 via an interface, Such as a
`video adapter 48. In addition to the monitor, personal
`computers typically include other peripheral output devices,
`not shown, Such as Speakers and printers.
`The personal computer 20 may operate in a networked
`environment using logical connections to one or more
`remote computers, Such as a remote computer 49. The
`remote computer 49 may be another personal computer, a
`Server, a router, a network PC, a peer device or other
`common network node, and typically includes many or all of
`
`50
`
`4
`the elements described above relative to the personal com
`puter 20, although only a memory storage device 50 has
`been illustrated in FIG.1. The logical connections depicted
`in FIG. 1 include a local area network (LAN) 51 and a wide
`area network (WAN) 52. Such networking environments are
`commonplace in offices, enterprise-wide computer
`networks, intranets and the Internet.
`When used in a LAN networking environment, the per
`sonal computer 20 is connected to the local network 51
`through a network interface or adapter 53. When used in a
`WAN networking environment, the person computer 20
`typically includes a modem 54 or other means for establish
`ing communications over the WAN 52. The modem 54,
`which may be internal or external, is connected to the System
`bus 23 via the serial port interface 46. In a networked
`environment, program modules depicted relative to the
`personal computer 20, or portions thereof, may be Stored in
`the remote memory Storage device. It will be appreciated
`that the network connections shown are exemplary and other
`means of establishing a communications link between the
`computerS may be used.
`In the description that follows, the invention will be
`described with reference to acts and Symbolic representa
`tions of operations that are performed by one or more
`computers, unless indicated otherwise. AS Such, it will be
`understood that Such acts and operations, which are at times
`referred to as being computer-executed, include the manipu
`lation by the processing unit of the computer of electrical
`Signals representing data in a structured form. This manipu
`lation transforms the data or maintains it at locations in the
`memory System of the computer, which reconfigures or
`otherwise alters the operation of the computer in a manner
`well understood by those skilled in the art. The data struc
`tures where data is maintained are physical locations of the
`memory that have particular properties defined by the format
`of the data. However, while the invention is being described
`in the foregoing context, it is not meant to be limiting as
`those of skill in the art will appreciate that various of the acts
`and operation described hereinafter may also be imple
`mented in hardware.
`Referring now to FIG. 2, the present invention is directed
`to a way to protect a Security parameter negotiation Server,
`Such as an IKE server of the IPSec Suite, from malicious
`denial-of-service attacks that attempt to flood the server with
`false connection requests. For illustration purposes, the
`invention will be described below in connection with a
`preferred embodiment that implements the IPSec Suite
`protocols for Secured delivery of network communications.
`It will be appreciated, however, that the System and method
`of the invention for providing protection against denial-of
`Service attacks can also be effectively used with other
`network Security protocols that require negotiations of Secu
`rity parameters for Securing network communications.
`In the embodiment shown in FIG. 2, a computer 70
`implements the IPSec Suite protocols for secured delivery of
`IP-based packets. The components supporting the IPSec
`protocols include a policy agent 72, an IPSec driver 74, and
`an Internet Key Exchange (“IKE”) server 76. The security
`policies assigned to the host computer 70 by the adminis
`trator of the system determine the levels of security for
`various types of communications. The Security policies are
`picked up by the policy agent 72 and passed the IKE Server
`76 and the IPSec driver 74. The IKE Server 76 uses the
`negotiation policies associated with the assigned Security
`policies to conduct negotiations with a peer (i.e., the IKE
`component of another computer on the network) to establish
`Security parameters for communications with the host of the
`
`25
`
`35
`
`40
`
`55
`
`60
`
`65
`
`Cloudflare - Exhibit 1027, page 6
`
`

`

`S
`peer. The negotiated Security parameters include, for
`example, the parameters for authentication and encryption
`methods and the keys, and are collectively referred to in the
`IPSec Suite protocols as a Security Association ("SA"). The
`results of the negotiation by the IKE server 76 is passed to
`the IPSec driver 74, which performs security operations,
`Such as data encryption, on packets of a communication
`Stream using the negotiated SA for that Stream.
`In this illustrated embodiment, the host computer 70 on
`which the IPSec components reside is part of an internal
`network 80 such as a local-area network (“LAN”). The host
`computer 70 is also connected to an external network 82,
`Such as the Internet, and communicates with other comput
`erS on the external network by Sending and receiving packets
`based on the Internet Protocol. The host computer 70 in this
`arrangement functions as a firewall or gateway for comput
`ers on the internal network 80 to communicate with com
`puters on the external network 82. For example, a computer
`84 on the internal network may communicate with a com
`puter 86 on the external network 82 by transmitting IP-based
`communication packets 92 through the host computer 70,
`whose IPSec components will handle the task of securing
`the communication Stream. When the host computer is used
`in this capacity of a gateway for the internal network, the
`IPSec components, such as the IKE server 76, especially
`have to be resilient to attackS mounted by malicious attack
`erS on the external network while providing Services to
`legitimate users.
`In accordance with an aspect of the invention, the IKE
`server 76 may be vulnerable to denial-of-service attacks that
`flood it with false connection requests if no special protec
`tion measure is taken. The Vulnerability of the IKE server to
`such flooding attacks comes from the need for the IKE
`Server to Store States not only for Successful negotiations but
`also for on-going negotiations. AS shown in FIG. 2, when an
`initial communication request 90 comes from a computer 86
`on the external network 82, the IKE server 76 initiates a
`negotiation process with the peer IKE 88 of the requesting
`computer 86 to establish the security parameters for the
`communication. Under the IKE protocol of the IPSec Suite,
`this negotiation involves two phases. In the first phase, the
`two IKE peers 76 and 88 establish a secure channel for
`conducting the IKE negotiation (called the IKE SA). In the
`Second phase, the two IKE peers negotiate general purpose
`SAS over the Secure channel established in the first phase.
`The first phase is typically accomplished in a “main mode'
`that involves three two-way exchanges between the SA
`initiator and the recipient. The Second phase is accomplished
`in a “quick mode” that is less complicated than the main
`mode Since the negotiation is already inside a Secure chan
`nel. AS these phases and modes of the IKE negotiation
`process are defined in the IKE protocol and well known to
`those skilled in the art, it is not necessary to describe them
`in greater detail here.
`It is important, however, for purposes of the invention to
`understand that to Support the negotiation process the IKE
`Server has to Store a “state' associated with the negotiation.
`Specifically, when a request 90 for a new negotiation with a
`peer arrives, the IKE Server allocates System resources to
`create a State for the negotiation. In this context, the State is
`a proposed SA to be established by negotiation. AS shown in
`FIG. 2, the IKE server 76 maintains a state table 120 that is
`a list of all SAS pending negotiation as well as SAS that have
`been Successfully negotiated. The resources allocated for the
`SA State include dynamically allocated memory and a criti
`cal Section for Synchronization. The SA State record Starts
`with data including the peer address, an indication of
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,904,529 B1
`
`15
`
`25
`
`6
`whether the server is the initiator or responder of the
`negotiation, the current State of the negotiation (e.g., an
`OAK MM SETUP state as will be described below). As
`the negotiation proceeds, more information is filled into the
`SA State, Such as the key generation data, the negotiation
`attributes, the authentication material, etc. At the end of the
`main mode phase of the negotiation, the SA is fully filled
`Out.
`It is important to note that at the time the SA state is
`created in response to a negotiation request, the IKE does
`not know whether the request is really from the peer
`computer identified in the request. After creating the State for
`the new negotiation request, the IKE Server processes the
`request to see whether it is valid, and then responds if the
`request is valid. The rest of negotiation then follows, with
`four more round trip packet eXchanges. Part of this exchange
`authenticates the peer, and at that time the IKE can deter
`mine if it should allow access to that peer. This peer
`authentication does not occur until the third round trip,
`however. In short, the IKE server has to create a state
`immediately in response to a request from any unknown
`Source, and the peer authentication takes place later. Thus, a
`malicious user of the peer computer can Send in a large
`number of requests to force the IKE Sever to create a large
`number of States. This consumes System resources, making
`the System to run slower. AS the System runs slower, it
`cannot reclaim resources quickly, causing the System to run
`even slower and finally coming to a grinding halt.
`In accordance with the invention, the resilience of the IKE
`Server to the denial-of-Service attack is significantly
`improved by dynamically detecting when the performance
`of the System begins to degrade, and adjusting performance
`variables to actively remove unneeded States and reduce the
`workload of the IKE server. The effectiveness of the pro
`tection against denial-of-Service attacks is further enhanced
`and the ability of the Server to Serve legitimate requests is
`improved by limiting the number of States for pending
`negotiations for each client and the total number of Such
`States. These protective measures are described in greater
`detail in the following description.
`In accordance with a feature of the embodiment, the
`activation periodicity of a reaper component 122 of the
`System is used as a primary barometer for the System health.
`The function of the reaper 122 is to remove unwanted States
`from the state table 120 of the IKE server 76. The reaper is
`Scheduled to run at fixed intervals, although the actual
`intervals between consecutive runs of the reaper would
`depend on the System workload. For instance, in a multi
`threading System, the reaper thread may be Scheduled to run
`every 45 seconds. On a lightly loaded System, the reaper
`thread will be activated at or close to the Scheduled time.
`When the system is under a heavy workload, however, the
`operating System may fall behind its Schedule and activate
`the reaper later than the Scheduled time. As a result, the
`interval between two consecutive runs of the reaper becomes
`longer than 45 Seconds. AS the workload of the System
`becomes heavier, the intervals between consecutive runs of
`the reaper are likely to increase. The delay in the activation
`of the reaper thus serves as a reliable indicator of whether
`the System is being overloaded.
`When the reaper activation intervals become longer than
`the Scheduled interval, dynamic adjustments of relevant
`performance variables are made to reduce the load on the
`System. In a preferred embodiment, the performance Vari
`ables that affect the operation of the IKE server include
`negotiation delay, retransmission delay, and packet drop
`percentage. The negotiation delay controls how long a
`
`Cloudflare - Exhibit 1027, page 7
`
`

`

`7
`negotiation process is allowed to last. By reducing the
`negotiation delay, pending negotiations are timed out
`Sooner, and their associated SAS are removed from the State
`table 120. The retransmission delay is the time the IKE
`server 76 will wait for a response from the requesting
`computer before retransmitting a packet in the negotiation
`process. Increasing the retransmission delay makes retrans
`missions further apart. As a result, the System makes fewer
`retransmissions per unit time, thereby reducing the workload
`on the System. The packet drop percentage is the percentage
`at which the incoming negotiation packets are randomly
`dropped. Increasing the packet drop percentage means that
`the System handles fewer requests and therefore does leSS
`work. Adjusting these performance variables to reduce the
`system workload allows the system to heal itself from a burst
`of attack and to withstand Short loads that far exceed its
`normal capacity. It will be appreciated that other perfor
`mance variables that have direct or indirect impacts on the
`Workload of the System may also be adjusted to lessen the
`overloading of the System.
`The adjustments of the performance variables are prefer
`ably made in a progressive manner Such that they are gradual
`at first and become more drastic as the System overloading
`becomes more Severe. By way of example, referring to FIG.
`3, each time the reaper thread is activated (step 140), the
`interval between the present run and the previous run is
`determined (step 142). In this example, the reaper 122 is
`scheduled to run at an interval of 45 seconds. If the reaper
`actually runs at an interval equal to or greater than 60
`Seconds (step 144), the performance variables are modified
`to reduce the workload of the system (146). After the reaper
`run interval returns to the range between 60 seconds and 45
`Seconds, the performance variables may be modified in the
`opposite direction to allow them to move back toward their
`initial values (step 148). For instance, in one
`implementation, the negotiation delay has a minimum value
`of 30 seconds and a maximum value of 60 seconds. Each
`time the reaper run interval exceeds 60 Seconds, the nego
`tiation delay is decreased by 5 Seconds. After the reaper run
`interval returns to below 60 Seconds, the negotiation delay
`is increased by one Second for each reaper run. Similarly, the
`transmission delay may have a minimum of O Second and a
`maximum of 15 Seconds, with an increment Step of 3
`Seconds and a decrement Step of 1 Second. The drop packet
`percentage has a minimum of 0 and a maximum of 100, with
`increment and decrement Steps of 3 and 5, respectively.
`Also, the packet drop percentage Starts to be incremented
`only if the negotiation delay is already at its minimum. In
`this way, the IKE Server avoids dropping packets until it
`becomes necessary to do So.
`Adjusting performance variables to reduce the System
`Workload as described above is effective in preventing the
`IKE Server from being paralyzed by a flooding attack.
`Nevertheless, Since those performance variables are global,
`the workload reduction does not discern valid clients from
`potentially malicious attackers. As a result, the Server will
`equally deny Service to valid users and malicious attackers.
`In this regard, the protection against denial-of-Service
`attacks in a preferred embodiment is made more focused on
`potential attackers by limiting the number of States pending
`negotiation for each client. By way of example, the number
`of Outstanding requests for each client may be limited to a
`Selected number, Such as 6. When it is detected that a client
`already has 6 or more States pending negotiation (step 150),
`the thread that processes negotiation requests simply drops
`any Subsequent new request from the Same client as iden
`tified by the IP address of the request (step 152). This
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,904,529 B1
`
`8
`eliminates the possibility of being flooded by false requests
`generated by an attacker on a Single machine.
`It is, however, possible for an attacker to put fake Source
`IP addresses in the false requests (which is commonly called
`“spoofing”). To deal with that possible Scenario, in a pre
`ferred embodiment a configurable threshold (e.g., 1000) is
`also set for the total number of States pending negotiation.
`Specifically, when the IKE server 76 sends a response to a
`new request for negotiation, the State it allocates is marked
`to indicate that the negotiation for this State is not completed,
`such as by setting a flag named “OAK MM SETUP". This
`Setting is not changed unless the IKE Server receives a valid
`response from the client that Sent the request. In the case of
`Spoofing, Since Source IP addresses of the false requests are
`fake, it is unlikely that the attacker would receive the
`negotiation packets from the IKE Server and respond accord
`ingly. Thus, the total number of States with pending nego
`tiations is an indicator of the possibility that the IKE server
`is under a flooding attack.
`When the reaper runs, it checks the total number of states
`with the negotiation-pending flag Set. If the total number
`exceeds the pre-configured threshold (step 154), the IKE
`Server is told not to accept any new connection request (Step
`156) and to more aggressively time out those negotiation
`pending States. In this way, valid connections are given the
`opportunity to progress (i.e., to complete the negotiations),
`and once the n