US 9,807,092 B1Grant
Systems and methods for classification of internet devices as hostile or benign
Issue Date:2017-10-31
•33 Claims
•37 Drawing Sheets
Abstract
A dynamic access pricing and active countermeasure system and method for detecting and protecting against automated Internet attackers that incapacitates or disables the attackers. The dynamic access pricing and active countermeasure generally includes 1) the provision of a device fingerprint by a device at the start of an iteration of the client-puzzle challenge-response protocol; 2) a dynamic access pricing policy associated with a transaction identifier; 3) the determination of the puzzle difficulty level based on the interaction history of the device fingerprint solely with respect to the dynamic access pricing policy; 4) the binding of the device fingerprint to the client puzzle challenge; the generation of transaction authorization codes that the device presents to a protected application, system, interface or device.
Metadata
Assignee
- DCS7, LLC
Inventor
- Kurt Gutzmann
Application Information
Application Number:US 15/157,356
Filing Date:2016-05-17
Priority Date:2013-07-05
Art Unit:2498
Classifications
IPC:
H04L29/06
Field of Search:
H04L 63/08H04L 63/0876G06F 21/36
Patent Drawings (37 sheets)
Description
[0001] This Application claims priority to U.S. Provisional Application No. 61/957,497, filed Jul. 5, 2013, and U.S. patent application Ser. No. 14/323,826, filed Jul. 3, 2014, the disclosures of which are incorporated herein in their entirety by reference.
BACKGROUND
[0002] The present disclosure relates generally to the classification or identification of internet devices as “hostile” or “benign” devices. Such devices include but are not limited to general computers executing software (such as a web browser) engaging as clients in the hypertext transfer protocol (HTTP) with one or more servers (web servers). Hostile devices are those that are or will be engaging in denial of service attacks. Denial of service attacks attempt to disrupt, destroy, or degrade the services provided by a web server by overwhelming it with a very large rate of requests.
[0003] The present disclosure provides systems and methods for classifying devices as hostile (attackers) or not, thereby permitting the mitigation of denial of service attacks by device-based filtering of requests.
[0004] Also provided are systems and methods relating to client-puzzles with dynamic access pricing (“DAP”) and more specifically to a DAP policy and active countermeasure against automated Internet attackers that incapacitates or disables the attackers. For purposes of this disclosure, “access pricing” means exchanging something of value for access to a resource, for example, exchanging central processor cycles (CPU time) required to compute a solution to a client puzzle based on the difficulty of the client puzzle, to gain access to an Internet resource. Accordingly, “dynamic access pricing” reflects changing “access pricing,” for example, as the amount of CPU time varies based on varying levels of difficulty of successive client puzzles.
[0005] The methods or individual steps of methods disclosed herein may be generally referred to as “protocols.” For purposes of this disclosure, “protocol” generally means a sequence and/or series of activities, functions, and/or communications for accomplishing particular objectives.
[0006] In one respect, the systems and methods address denial of service (DoS) attacks on the public Internet. The communications protocols controlling the operation of the Internet are known as the “Internet Protocol” (IP) suite, and commonly assigned a system of “layers” numbered from one through seven (1-7) according to the International Telecommunications Union (ITU) (1994). Briefly, the seven layers are 1) Physical 2) Data Link 3) Network 4) Transport 5) Session 6) Presentation and 7) Application. Even though the IP protocol suite does not explicitly call out the 7-layer OSI (Open Systems Interconnection) model, the OSI model is used when discussing IP protocols nonetheless in common practices. Here, the attention is on “Layer 7” or the “Application Layer.” The hypertext transfer protocol (Internet Engineering Task Force (IETF), 1999) is an application layer or layer-7 protocol that itself is comprised of other lower-level protocols, specifically the Transmission-Control-Protocol/Internet-Protocol (TCP/IP). The present disclosure is directed towards managing and mitigating DoS attacks using the HTTP protocol (or its encrypted transport version, HTTPS). In subsequent discussion of the background, “DoS attack” will mean generally attacks using the HTTP protocol.
[0007] The objective of a DoS attack is to deny a web site or service to its legitimate users by making it unavailable through an excessive volume or rate of HTTP requests. This is known as a flooding attack or a basic volumetric attack. These attacks seek to exhaust resources of the target such as network bandwidth, processor capacity, memory, connection pools, and so on. Attacks may be more subtle as well, exploiting a semantic or computational vulnerability of the target. For example, DoS attacks on a web site's “search” function are semantic in nature, since the attacker infers that some back-end database will be involved in processing the search query and may be overloaded more easily.
[0008] The attacker accomplishes the DoS attack by using a collection of computers known as “bots” or “zombies” (Mirkovic, 2008). These are computers that have been exploited through various viruses, malwares, or security vulnerabilities such that they can be remotely controlled by the attacker to carry out commands. These computers are referred to in the descriptions herein as ‘hostile devices.’ The bots altogether are known as a “botnet.” Botnets range in size from a few thousand computers to a million or more (Buscher, 2012). This provides the attacker with a significant computing power advantage over his target, where he is able to bring to bear a large and potentially debilitating number of requests against the targeted web servers or front-end devices (this is an asymmetric cyberwarfare method). Significantly, the actual software executing on a bot that is part of a DoS attack must be an HTTP client. However, unlike the typical web browsers used by people (Internet Explorer, FireFox, Chrome, Safari, Opera, et cetera), these bot web clients will generally (but not always) not execute any client-side scripting languages, including but not limited to ECMAScript, JavaScript, Jscript, and so on. The reason for this is that the bot has no interest in the user-experience features these languages provide, and executing them will only delay the bot from sending its next request in the flood. However, bots are often capable of accepting and returning information tokens such as, without limitation, cookies (IETF, 1999) or Uniform Resource Locator (URL) query parameters.
[0009] Client puzzles or proofs-of-work have been used as part of many systems and protocols for addressing DoS attacks. CAPTCHAs (Completely Automated Public Turing test to tell Computers and Humans Apart), usually a visual puzzle, are a type of client puzzle that is not precisely a proof of work; rather, a successful answer to a CAPTCHA classifies the responder as a human. However, many CAPTCHA schemes are considered ‘broken’ through the use of adversarial optical character recognition (A-OCR) techniques (e.g., Pretend We're Not a Turing Computer but a Human Antagonist (PWNTCHA)), http://caca.zoy.org/wiki/PWNtcha).
[0010] Mathematical proofs-of-work are generally considered more robust, and their functional requirements have been well-documented (Laurens, 2006). In general, a mathematical proof-of-work must satisfy the following requirements: 1) have a solution 2) server computational costs for puzzle generation and verification must be orders of magnitude smaller than client computational costs required to find a solution 3) puzzles must be solved in a limited amount of time 4) pre-computation of solutions in advance should be infeasible 5) previous solutions do not assist in finding future solutions 6) the puzzle-issuance and puzzle-verification process should not require any persistence of the connection state between the server and client. The present systems and methods satisfy these requirements. In addition to these requirements identified by (Laurens, 2006), puzzles (challenges), their solutions, and related parameters (expirations times, internet domain of applicability) must all be either tamper-proof or at least tamper-evident (Gutzmann, 2001). This requirement prevents clients from substituting easy puzzles for hard ones, for example. The present systems and methods satisfy this requirement through the use of message authentication codes (MAC).
[0011] A final requirement for layer-7 systems is that they must operate in a manner that does not affect the content delivery and rendering at the client web browser. In Feng et al.'s approach (Feng et al., U.S. Pat. No. 8,321,955), URLs are rewritten dynamically by a client-side JavaScript component and additional JavaScript is injected to the pages; thus, what is finally rendered at the client web browser is not what would be sent by a server in the absence of the proof-of-work protocol element. With the pervasive, complex, and unavoidable use of JavaScript today, Feng et al.'s approach potentially disrupts the proper rendering of the content due various reasons such as namespace collisions, function overloads, and modification of execution sequences of scripts. The present systems and methods use a short-duration ticketing approach that permits unmodified delivery of server content to the browser, thereby avoiding that problem.
[0012] While there are many possible proof-of-work systems, most commonly used are what are known as “hash pre-image” puzzles. In this type of puzzle, a client must find a concatenation of a server challenge and client ‘solution’ such that that pre-image (input string) to a one-way function (including but not limited to a ‘hash’ function, such as Message-Digest-5 (MD5), Secure Hash Algorithm (SHA), Secure Hash Algorithm 256 (SHA256), etc) that produces a server-specified number of leading zero bits in the output. The number of leading bits is typically called the puzzle difficulty. More difficult puzzles require larger computational costs and time on the client side; adjustments of the difficulty level have the effect of ‘throttling’ the client since it cannot make HTTP requests while involved in finding a solution. Variations on the basic hash pre-image puzzle exist. Some require that the leading bits evaluate to a number less/greater than some specified value (Rangasamy, 2011).
[0013] Much work has been done on DoS attacks at the lower layers of the communication model (e.g., Hill, U.S. Pat. No. 6,088,804; Cox, U.S. Pat. No. 6,738,814) since layer 3-4 attacks (e.g., the Transmission Control Protocol—Synchronize “TCP SYN” attack) form a large part of the DoS attacker's arsenal. At the application layer, Feng and Kaiser (Feng et al. U.S. Pat. No. 8,321,955) developed a DoS mitigation approach using a proof-of-work client puzzle for both layer 3-4, and for layer 7. Much of the disclosure in Feng et al.'s patent (U.S. Pat. No. 8,321,955) is focused on the lower network layers, but a final section discusses a client puzzle (a.k.a. proof-of-work) for an HTTP server. In this system and method, the claims are made for prioritizing traffic based on its past history of traffic rate or volume. All traffic is accepted in that system, but is directed to a high or low priority service running in a single computer. In the details of the embodiment of Feng et al.'s disclosure of a probabilistic data structure (“Bloom Filter”) is used to tally historical request counters on a per Internet Protocol address (IP address) basis. One of several drawbacks of this system is that it works on a single computer only due to the local data structure, the Bloom filter, used to determine puzzle difficulty based on request history. In practice, almost all large and commercially significant web sites are complex distributed systems (similar to elements 101-103 in FIG. 1 ). The need for distributed shared memory arises then, and this is addressed by the present disclosure. Feng et al.'s use of IP address alone also presents practical problems; for example, many internet service providers (e.g., Verizon, America Online) operate caching proxy servers as intermediaries between HTTP clients and servers. From the web server's point of view, then, there is a single IP address (that of the proxy) behind which there may be many thousands of distinct HTTP clients (“devices” as we call them here). Using Feng et al.'s request-counting approach, the proxy IP will be incorrectly de-prioritized thus delivering a poor user experience to all clients behind the proxy. That drawback is addressed by the current disclosure's use of device fingerprinting methods which differentiate many devices sharing the same IP address (this also is applied to the classification of bots that are polymorphic in their device fingerprint).
BRIEF SUMMARY OF AN EXEMPLARY EMBODIMENT
[0014] The disclosure generally relates to Internet attacker identification systems and methods which include 1) a proof-of-work puzzle protocol, 2) a method for adjusting a device's “attacker score” based on its protocol behavior, 3) a method for detecting tampering of proof-of-work puzzle parameters, 4) a method for limiting request rates of both benign and hostile devices, 5) a method for collecting device fingerprints and IP addresses and their associated status from a high-speed memory cache and persisting them to a database, 6) a web services deployment model to provide device classification services to third parties, and 7) a method for dissemination of device blacklists and whitelists to all subscribers of the web service, 8) a deployment model of the attacker identification system as a request filter at the front-end of a distributed web services system, and 9) a management server for control of the system parameters to enable various modes of classification and device request rate limiting.
[0015] The systems and methods also generally relate to client-puzzles with dynamic access pricing which includes 1) the provision of a device fingerprint by a “requesting device” at the start of an iteration of a client-puzzle challenge-response protocol; 2) a DAP policy associated with a transaction identifier; 3) the determination of a puzzle difficulty level by a “puzzle-issuer-verifier” based on the interaction history of the device fingerprint solely with respect to the DAP policy; 4) the binding of the device fingerprint to the client puzzle challenge; 5) the generation of transaction authorization codes that the device presents to a protected application, system, interface or device; and 6) the verification of transaction authorization codes and bound device fingerprint(s) by a “protected system”.
[0016] There has thus been outlined, rather broadly, some of the features of the systems and methods in order that the detailed description thereof may be better understood, and in order that the present contribution to the art may be better appreciated. There are additional features of the systems and methods that will be described hereinafter.
[0017] In this respect, before explaining at least one embodiment of the systems and methods in detail, it is to be understood that the disclosure is not limited in its application to the details of construction or to the arrangements of the components set forth in the following description or illustrated in the drawings. The systems and methods are capable of other embodiments and of being practiced and carried out in various ways. Also, it is to be understood that the phraseology and terminology employed herein are for the purpose of the description and should not be regarded as limiting.
BRIEF DESCRIPTION OF THE DRAWINGS
[0018] Non-limiting and non-exhaustive embodiments will be described with reference to the following figures, wherein like reference numerals refer to like parts throughout the various figures unless otherwise specified.
[0019] FIG. 1 is a block diagram illustrating the overall architecture of the present systems and methods as a multi-subscriber device classification service. FIG. 1 is a system architecture diagram for deployment of the systems and methods in a highly scalable manner to support device fingerprinting, classification, and white/black list distribution. This system architecture describes an embodiment of the systems and methods as a web service for numerous subscribers;
[0020] FIG. 2 is a block diagram illustrating the overall of the present systems and methods as a stand-alone system. FIG. 2 is a system architecture diagram for deployment of the systems and methods in a highly scalable manner to support device fingerprinting, classification, and white/black list filtering at a system's front end. This architecture describes an embodiment of the systems and methods as a stand-alone system for classifying devices making requests of a single web service;
[0021] FIG. 3A is a flowchart (an “activity diagram” which is a multiple side-by-side flowchart divided into lanes illustrating both control flow in a lane and data flows between the entities performing the actions in each lane) showing the operation of the proof-of-work protocol of the present systems and methods when deployed as web service for multiple subscribers (this corresponds to the architecture diagram in FIG. 1 );
[0022] FIG. 3B is a flowchart (an “activity diagram” which is a multiple side-by-side flowchart divided into lanes illustrating both control flow in a lane and data flows between the entities performing the actions in each lane) showing the operation of the proof-of-work protocol of the present systems and methods when deployed as web service for multiple subscribers (this corresponds to the architecture diagram in FIG. 1 );
[0023] FIG. 3C is a flowchart (an “activity diagram” which is a multiple side-by-side flowchart divided into lanes illustrating both control flow in a lane and data flows between the entities performing the actions in each lane) showing the operation of the proof-of-work protocol of the present systems and methods when deployed as web service for multiple subscribers (this corresponds to the architecture diagram in FIG. 1 );
[0024] FIG. 4A is a flowchart (an “activity diagram” which is a multiple side-by-side flowchart divided into lanes illustrating both control flow in a lane and data flows between the entities performing the actions in each lane) showing diagram showing the detailed operation of the proof-of-work protocol of the systems and methods between a client and a host;
[0025] FIG. 4B is a flowchart (an “activity diagram” which is a multiple side-by-side flowchart divided into lanes illustrating both control flow in a lane and data flows between the entities performing the actions in each lane) showing diagram showing the detailed operation of the proof-of-work protocol of the systems and methods between a client and a host;
[0026] FIG. 4C is a flowchart (an “activity diagram” which is a multiple side-by-side flowchart divided into lanes illustrating both control flow in a lane and data flows between the entities performing the actions in each lane) showing diagram showing the detailed operation of the proof-of-work protocol of the systems and methods between a client and a host;
[0027] FIG. 4D is a flowchart (an “activity diagram” which is a multiple side-by-side flowchart divided into lanes illustrating both control flow in a lane and data flows between the entities performing the actions in each lane) showing diagram showing the detailed operation of the proof-of-work protocol of the systems and methods between a client and a host;
[0028] FIG. 4E is a flowchart (an “activity diagram” which is a multiple side-by-side flowchart divided into lanes illustrating both control flow in a lane and data flows between the entities performing the actions in each lane) showing diagram showing the detailed operation of the proof-of-work protocol of the systems and methods between a client and a host;
[0029] FIG. 4F is a flowchart (an “activity diagram” which is a multiple side-by-side flowchart divided into lanes illustrating both control flow in a lane and data flows between the entities performing the actions in each lane) showing diagram showing the detailed operation of the proof-of-work protocol of the systems and methods between a client and a host;
[0030] FIG. 5 is a flowchart illustrating a sub-operation of the present systems and methods. FIG. 5 is a state transition model for devices;
[0031] FIG. 6 is a flowchart illustrating a sub-operation of the present systems and methods. FIG. 6 is a state transition for servers implementing the classification method;
[0032] FIG. 7 is a flowchart illustrating a sub-operation of the present systems and methods. FIG. 7 is a state transition for the proof-of-work puzzle;
[0033] FIG. 8 is a state transition diagram for a device associated with its device fingerprint, with two states conferring access by the device to a particular transaction, and a single state where the device is denied access (“lockout”);
[0034] FIG. 9 is a generalization of the state transition diagram of FIG. 8 , where the number of allowed and denied (“lockout”) states comprise arbitrary numbers;
[0035] FIG. 10A is a protocol sequence flowchart between a protected system, a requesting device, and a puzzle-issuer-verifier showing the provision of the device fingerprinting and puzzle-solving script by the protected system to the requesting device at the start of the protocol, the provision of the device fingerprint by the requesting device to the puzzle-issuer, and the incorporation of the device fingerprint into the transaction authorization codes at the completion of the protocol;
[0036] FIG. 10B is a protocol sequence flowchart between a protected system, a requesting device, and a puzzle-issuer-verifier showing the provision of the device fingerprinting and puzzle-solving script by the protected system to the requesting device at the start of the protocol, the provision of the device fingerprint by the requesting device to the puzzle-issuer, and the incorporation of the device fingerprint into the transaction authorization codes at the completion of the protocol;
[0037] FIG. 10C is a protocol sequence flowchart between a protected system, a requesting device, and a puzzle-issuer-verifier showing the provision of the device fingerprinting and puzzle-solving script by the protected system to the requesting device at the start of the protocol, the provision of the device fingerprint by the requesting device to the puzzle-issuer, and the incorporation of the device fingerprint into the transaction authorization codes at the completion of the protocol;
[0038] FIG. 10D is a protocol sequence flowchart between a protected system, a requesting device, and a puzzle-issuer-verifier showing the provision of the device fingerprinting and puzzle-solving script by the protected system to the requesting device at the start of the protocol, the provision of the device fingerprint by the requesting device to the puzzle-issuer, and the incorporation of the device fingerprint into the transaction authorization codes at the completion of the protocol;
[0039] FIG. 10E is a protocol sequence flowchart between a protected system, a requesting device, and a puzzle-issuer-verifier showing the provision of the device fingerprinting and puzzle-solving script by the protected system to the requesting device at the start of the protocol, the provision of the device fingerprint by the requesting device to the puzzle-issuer, and the incorporation of the device fingerprint into the transaction authorization codes at the completion of the protocol;
[0040] FIG. 10F is a protocol sequence flowchart between a protected system, a requesting device, and a puzzle-issuer-verifier showing the provision of the device fingerprinting and puzzle-solving script by the protected system to the requesting device at the start of the protocol, the provision of the device fingerprint by the requesting device to the puzzle-issuer, and the incorporation of the device fingerprint into the transaction authorization codes at the completion of the protocol;
[0041] FIG. 10G is a protocol sequence flowchart between a protected system, a requesting device, and a puzzle-issuer-verifier showing the provision of the device fingerprinting and puzzle-solving script by the protected system to the requesting device at the start of the protocol, the provision of the device fingerprint by the requesting device to the puzzle-issuer, and the incorporation of the device fingerprint into the transaction authorization codes at the completion of the protocol;
[0042] FIG. 10H is a protocol sequence flowchart between a protected system, a requesting device, and a puzzle-issuer-verifier showing the provision of the device fingerprinting and puzzle-solving script by the protected system to the requesting device at the start of the protocol, the provision of the device fingerprint by the requesting device to the puzzle-issuer, and the incorporation of the device fingerprint into the transaction authorization codes at the completion of the protocol;
[0043] FIG. 10I is a protocol sequence flowchart between a protected system, a requesting device, and a puzzle-issuer-verifier showing the provision of the device fingerprinting and puzzle-solving script by the protected system to the requesting device at the start of the protocol, the provision of the device fingerprint by the requesting device to the puzzle-issuer, and the incorporation of the device fingerprint into the transaction authorization codes at the completion of the protocol;
[0044] FIG. 10J is a protocol sequence flowchart between a protected system, a requesting device, and a puzzle-issuer-verifier showing the provision of the device fingerprinting and puzzle-solving script by the protected system to the requesting device at the start of the protocol, the provision of the device fingerprint by the requesting device to the puzzle-issuer, and the incorporation of the device fingerprint into the transaction authorization codes at the completion of the protocol;
[0045] FIG. 10K is a protocol sequence flowchart between a protected system, a requesting device, and a puzzle-issuer-verifier showing the provision of the device fingerprinting and puzzle-solving script by the protected system to the requesting device at the start of the protocol, the provision of the device fingerprint by the requesting device to the puzzle-issuer, and the incorporation of the device fingerprint into the transaction authorization codes at the completion of the protocol;
[0046] FIG. 10L is a protocol sequence flowchart between a protected system, a requesting device, and a puzzle-issuer-verifier showing the provision of the device fingerprinting and puzzle-solving script by the protected system to the requesting device at the start of the protocol, the provision of the device fingerprint by the requesting device to the puzzle-issuer, and the incorporation of the device fingerprint into the transaction authorization codes at the completion of the protocol;
[0047] FIG. 10M is a protocol sequence flowchart between a protected system, a requesting device, and a puzzle-issuer-verifier showing the provision of the device fingerprinting and puzzle-solving script by the protected system to the requesting device at the start of the protocol, the provision of the device fingerprint by the requesting device to the puzzle-issuer, and the incorporation of the device fingerprint into the transaction authorization codes at the completion of the protocol;
[0048] FIG. 10N is a protocol sequence flowchart between a protected system, a requesting device, and a puzzle-issuer-verifier showing the provision of the device fingerprinting and puzzle-solving script by the protected system to the requesting device at the start of the protocol, the provision of the device fingerprint by the requesting device to the puzzle-issuer, and the incorporation of the device fingerprint into the transaction authorization codes at the completion of the protocol;
[0049] FIG. 11 is an interaction flow model for an embodiment of the systems and methods where the puzzle-issuer-verifier uses a key-value memory cache with expiration time support to accomplish the lookback and lockout features described further below;
[0050] FIG. 12 is a graph showing the expected time to solve a client puzzle as a function of its difficulty level, based on a benchmark of hash-reversal puzzles executed on a typical desktop computer;
[0051] FIG. 13 is an interaction flow model for an embodiment of the systems and methods wherein the protected-system, the puzzle-issuer-verifier and a supporting memory cache are located within a single system boundary to create a “self-defending” system;
[0052] FIG. 14 is an interaction flow model for an embodiment of the systems and methods wherein the puzzle-issuer-verifier and its supporting memory cache are distinct system elements from the protected-system and the requestor and where the requestor has a pre-deployed set of software for generating device fingerprints and solving client puzzles;
[0053] FIG. 15 is a table showing the generalized form of the parameters of a dynamic access pricing policy; and,
[0054] FIG. 16 is a table showing a simplified form of the parameters of a dynamic access pricing policy.
DETAILED DESCRIPTION OF AN EXEMPLARY EMBODIMENT
A. Overview
[0055] Reference throughout this specification to “one embodiment” or “an embodiment” means that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least one embodiment of claimed subject matter. Thus, the appearances of the phrase “in one embodiment” or “an embodiment” in various places throughout this specification are not necessarily all referring to the same embodiment. Furthermore, the particular features, structures, or characteristics may be combined in one or more embodiments.
[0056] Turning to the drawings, in which similar reference characters denote similar elements throughout the several views, the figures illustrate 1) a proof-of-work protocol, 2) a method for adjusting a device's “attacker score” based on its protocol behavior, 3) a method for detecting tampering of puzzle parameters, 4) a method for limiting request rates of both benign and hostile devices, 5) a method for collecting device fingerprints and their associated status from a high-speed memory cache and persisting them to a database, 6) a web services deployment model to provide device classification services to third parties, 7) a method for dissemination of device blacklists and whitelists to all subscribers of the web service, 8) a stand-alone deployment model for classifying requestors of a single web service, and 9) a management server for control of the system parameters to enable various modes of classification and device request rate limiting.
[0057] In one exemplary embodiment, the figures and tables illustrate the following:
[0058] 1. The delivery of the fingerprinting and puzzle-solving script by a protected system to a requesting device in response to the request for access to a transaction or content prior to the requesting device's engagement with the puzzle-issuer-verifier;
[0059] 2. The generation of a device fingerprint by the requesting device prior to its request for a puzzle from the puzzle-issuer-verifier;
[0060] 3. The incorporation of the device fingerprint into the puzzle challenge by the puzzle-issuer-verifier;
[0061] 4. The binding of the device fingerprint and a disambiguating nonce with a message authentication code (MAC) using a cryptographic key (the “MAC key”) shared between the protected-system and the puzzle-issuer-verifier and unknown to the requesting-device;
[0062] 5. The determination of puzzle difficulty based on the device fingerprint, the number of access attempts by the device within a policy-specified time period (“lookback period”) and the current state of the device;
[0063] 6. The transition of the device state among an “initial” state, one or more “allowed” states, and one or more “denied” states based on an access attempt counter compared with a threshold value; and,
[0064] 7. The supply of a puzzle of a high degree of difficulty to a requesting device upon its transition to a denied state.
B. Proof of Work Protocol for Device Classification, and Dynamic Access Pricing Protocol
[0065] The proof-of-work protocol is a type of challenge-response authentication method. In this present embodiment, we are seeking to classify an HTTP client (device) as either hostile or benign. A hostile device is one that is engaging in a denial of service attack. A denial of service attack is characterized by a large (flooding) number of HTTP requests against a web server in an attempt overwhelm its processing capacity and take it offline.
[0066] The notion of a proof-of-work protocol is that in order to gain access to a service, the requestor must show proof that some computational work has been performed in advance of the request. These protocols generally are based on solving some sort of puzzle which takes some time for the requestor, but takes very little time for the server to verify that the solution is in fact a solution. The asymmetry of the solution time relative to the verification time is what reduces the advantage of a denial-of-service attacker against its target.
[0067] The most common proof-of-work puzzles involve finding some string of characters which when appended to a server-provided challenge and then processed by a one-way or digest function product a digest that has a specified number of zeroes in the leading bits of the digest. The number of leading zero bits required is called the difficulty of the puzzle. These puzzles are also called “hash pre-image” puzzles (the input to a transformation function is sometimes called a “pre-image” and its output an “image”).
[0068] A variation of this puzzle is to require that the binary number represented by the first n bits of the digest be less than or equal to some number. This method provides a more granular control over the computational difficulty than the single difficulty level puzzle. This also improves the chances that a solution to the puzzle exists.
[0069] As part of a device classification protocol, the proof-of-work puzzle serves two purposes: 1) determination of a requesting device's capability to solve puzzles, and 2) to limit the rate of requests that a device can make by occupying its central processing unit (CPU) with computational work finding solutions to puzzles. If a device does not attempt to solve the puzzles provided as part of the protocol, it will eventually be classified as hostile.
[0070] Turning now to FIG. 4 , we provide a description of the proof-of-work protocol. When a requesting device, 401, (a computer running a web browser or similar software), makes an HTTP request of a server, 402, that request will initially be accompanied by no proof-of-work. The server inspects the request for “cookie” elements (403) that are used to communicate the puzzle parameters and solutions between the requesting device and the server. An HTTP cookie is a piece of information issued by a server to a requestor, and is returned on subsequent requests to the server. The presence or absence of the protocol cookies will be used later to determine whether to issue a puzzle to the requestor.
[0071] The server now calculates a server-side device fingerprint, 404. The details of this process are discussed in “F. Method for Collecting Device Fingerprints and Their Associated Status from a High-speed Memory Cache and Persisting them to a Database”.
[0072] The server-side device fingerprint is an identifier of the requestor that is almost surely unique. This device fingerprint is called ‘server-side’ because it does not require a deep inspection of the requesting computer's characteristics, relying only on information provided in the request itself. We shall refer to this fingerprint henceforth as the SS_fingerprint.
[0073] This embodiment can identify devices that display polymorphism in their device fingerprint and can classify those devices as hostile. This will be the case for devices engaged in denial-of-service attacks that attempt to elude detection or classification by making permutations in the User-Agent, Referrer, X-Forwarded-For, and other HTTP header elements. However, all of these polymorphisms are related to the same IP address over time. The degree of polymorphism may be on the order of hundreds of variations for a sophisticated attacker. Given that the attacker will typically generate hundreds of HTTP requests per second during an attack, each of those requests will be identified by a particular fingerprint, and will be classified as hostile within a few iterations of the proof-of-work protocol. Characteristically, attackers will not engage in the execution of client scripting language such as, without limitation, JavaScript or ECMAscript; this behavior causes them to be classified as hostile regardless of the number of polymorphs they exhibit in the server-side fingerprint.
[0074] Now, the server examines the request for the presence of a device fingerprint calculated by the execution of a JavaScript script supplied to the requestor by the server. In the initial steps of the protocol this fingerprint will be absent, but will appear in subsequent requests by a requestor that executes JavaScript. Henceforth we will refer to this as the JS_Fingerprint.
[0075] Once these preliminary steps have been completed, the server takes the best available device fingerprint (the JS_Fingerprint is preferred over the SS_Fingerprint for this purpose), and checks to see if this fingerprint is a fingerprint that is on the black list (a “black-listed” fingerprint) 406. If so, the request is dropped and the protocol is terminated. If not, the protocol continues. Now, the server checks to see if the fingerprint is a white-listed fingerprint, 408. If so, the request passes through for continuation of normal processing.
[0076] At this point, 409, the request is inspected for the presence of a solution to a previously supplied puzzled. If not, a puzzle is generated based on the following, 410; the puzzle and its solution are represented by cookies (though other methods may be used, including but not limited to URL parameters and embedded constants in JavaScript). Turning to FIG. 7 , this corresponds to the MISSING state (704) in the puzzle state transition diagram. The parameters of the proof-of-work protocol are as follows, given by their notation name and corresponding cookie name (any names may be used for the cookies):
Ns, POW_NONCE—a random number generated to make each puzzle unique
[0077] Te, POW_EXPIRATION—a future time after which a solution is considered expired and may not be used as proof-of-work. The expiration time is typically set only far enough in the future to deliver the requested content, perhaps 10 seconds. Web pages generally have dozens of ‘referral’ elements in them that cause the browser to make additional requests automatically, e.g. for images, ads, and so on.
Gd1, POW_GPUZ1—The difficulty of the puzzle; in the case of a single-parameter hash pre-image puzzle this is the only parameter of difficulty. It is the required number of leading zero bits in that case. In the two-parameter difficulty puzzle, it is the number of bits to form an integer for evaluation against the value in POW_GPUZ2.
Gd2, POW_GPUZ2—In the case of the two-parameter puzzle difficulty specification, this is the number that is compared with the leading bits of the solution.
Cb, POW_CHALLENGE—This is a random string generated by the server and forms the base of a subsequent full challenge.
Cs, POW_CHALLENGE_SERVER—This is the challenge supplied to the requestor by the server. It is a hash of the POW_CHALLENGE_SERVER, an expiration time based on the server's internal clock (POW_EXPIRATION), a nonce (random number, POW_NONCE), the puzzle difficulty parameters (POW_GPUZ1 and POW_GPUZ2), the Internet domain, Dc, to which this applies (e.g. *.website.com) and a server-secret, Ks. The server-secret is never disclosed, and when appended to the foregoing elements provides a message authentication code (MAC) such that later solutions of the puzzle are known to be tamper-free, authentic, and originated at this system or server. Cs=Hash(Ns,Cb,Ks,Te,Dc,Gd);
POW_SOLUTION_CLIENT_NONCE—In a supplied JavaScript script, the requestor generates an additional random number. This element is appended to the POW_CHALLENGE_SERVER to form the complete challenge POW_CHALLENGE_CLIENT. The purpose of the client nonce is to further randomize the puzzle and reduce attempts by hostile requestors at puzzle replay attacks.
POW_CHALLENGE_CLIENT—This is the challenge for which the requestor must find a solution satisfying the puzzle difficulty requirements.
POW_FINGERPRINT—This is the locally computed device JS_Fingerprint.
POW_SOLUTION_PREIMAGE_PREFIX—This is a solution to the server-supplied proof-of-work puzzle. This value, when appended to the POW_CHALLENGE_CLIENT, and processed with a message digest function (e.g. SHA256) will satisfy the difficulty parameters in POW_GPUZ1 and/or POW_GPUZ2.
Gd1, POW_GPUZ1—The difficulty of the puzzle; in the case of a single-parameter hash pre-image puzzle this is the only parameter of difficulty. It is the required number of leading zero bits in that case. In the two-parameter difficulty puzzle, it is the number of bits to form an integer for evaluation against the value in POW_GPUZ2.
Gd2, POW_GPUZ2—In the case of the two-parameter puzzle difficulty specification, this is the number that is compared with the leading bits of the solution.
Cb, POW_CHALLENGE—This is a random string generated by the server and forms the base of a subsequent full challenge.
Cs, POW_CHALLENGE_SERVER—This is the challenge supplied to the requestor by the server. It is a hash of the POW_CHALLENGE_SERVER, an expiration time based on the server's internal clock (POW_EXPIRATION), a nonce (random number, POW_NONCE), the puzzle difficulty parameters (POW_GPUZ1 and POW_GPUZ2), the Internet domain, Dc, to which this applies (e.g. *.website.com) and a server-secret, Ks. The server-secret is never disclosed, and when appended to the foregoing elements provides a message authentication code (MAC) such that later solutions of the puzzle are known to be tamper-free, authentic, and originated at this system or server. Cs=Hash(Ns,Cb,Ks,Te,Dc,Gd);
POW_SOLUTION_CLIENT_NONCE—In a supplied JavaScript script, the requestor generates an additional random number. This element is appended to the POW_CHALLENGE_SERVER to form the complete challenge POW_CHALLENGE_CLIENT. The purpose of the client nonce is to further randomize the puzzle and reduce attempts by hostile requestors at puzzle replay attacks.
POW_CHALLENGE_CLIENT—This is the challenge for which the requestor must find a solution satisfying the puzzle difficulty requirements.
POW_FINGERPRINT—This is the locally computed device JS_Fingerprint.
POW_SOLUTION_PREIMAGE_PREFIX—This is a solution to the server-supplied proof-of-work puzzle. This value, when appended to the POW_CHALLENGE_CLIENT, and processed with a message digest function (e.g. SHA256) will satisfy the difficulty parameters in POW_GPUZ1 and/or POW_GPUZ2.
[0078] In order to detect replay attacks (re-use of puzzle solutions), the server initializes the usage count Cs in a memory cache server to zero, 411. A memory cache server is network-accessible store permitting the storage, retrieval, modification, and expiration of “key-value pairs”. This memory cache operates as a “blackboard” for a large number of replicated servers engaged in this protocol. As a defense against denial-of-service attacks, the system is required to process large number of requests simultaneously and be able to share information among all of the servers in the system. At (427) where the challenge usage count is incremented, its value may be compared to a threshold to determine if excessive usage of a challenge is occurring which would indicate a replay attack. This can be confirmed by examining the SS_Fingerprint and JS_Fingerprints associated with challenge; when two or more different fingerprints are submitting solutions to the same challenge, a replay attack is underway. Those devices may then be black-listed.
[0079] The server now stores SS_Fingerprint, 412, in the memory cache. The server then initialized the “attack score” to a nominal value, 413, for this device fingerprint in the memory cache.
[0080] Now, the server sends the puzzle back to the requestor. In the present embodiment, the HTTP cookie mechanism is used to convey the puzzle. Other embodiments could use what are known as “URL Parameters”, where information is appended to the URL returned as part of the server response. Yet other embodiments could embed all of the puzzle parameters in the supplied puzzle solving script. The puzzle solving script language presently used is JavaScript, due to its ubiquity, but other scripting languages including but not limited to Adobe Flash may be used as well.
[0081] Upon receipt of the puzzle and its associated solver and device fingerprinting JavaScript, the client sets to work, 412. The client generates its own nonce, Nc, 413, appends this to the server challenge, Cs, forming the client challenge, Cc, and executes the puzzle solving routine, 414. The solver is a loop that iterates over Cc, appending the value of the loop counter to the Cc, calculating the digest (hash) and evaluating the number of leading zeroes (POW_GPUZ1) for a single-difficulty type puzzle, or comparing the value of leading bits against the evaluation criteria (POW_GPUZ2) for a two-parameter level of difficulty puzzle. If the criteria are satisfied, a solution has been found; otherwise iteration continues. Puzzles in general must meet the requirement of solubility in order to avoid infinite looping on the part of the requestor.
[0082] Once the solution has been found, the script now computes the value of JS_Fingerprint as the requestor's device fingerprint. The script now executes a reload of the current URL (the original request), 415. Now however, the request for the same (previous) URL will also contain the cookie supplied by the server (described above), plus three additional cookies comprising the JS_Fingerprint. The three cookies represent the client challenge, Cc, a solution S, and the JS_Fingerprint. This cookie-returning behavior by the browser is standards-compliant (IETF Request for Comments (RFC) 2161).
[0083] So far, the behavior of a benign, or non-hostile, device has been described. The hostile device behavior is described hereafter. A benign device executes the server-supplied puzzle solver and device fingerprinting routines, and returns puzzle solutions with subsequent requests (FIG. 7, 702 ). At this point the device has been neither blacklisted nor whitelisted. It is still undergoing classification. The flow in the protocol now returns to 403, and proceeds as before until reaching 416 where the solution begins verification by the server.
[0084] At 416 the proper set of puzzle and solution parameters is checked. Next, at 417, the value of Ts as represented in the POW_EXPIRATION cookie is compared against the current value of the server's clock to determine if the solution is expired. The lifetime of a solution does not depend on the requesting computer's clock, nor any synchronization between the server and requestor clocks. The puzzle cookies themselves are set with an expiration time that is relative to the requestor's clock (there is a general expectation among networked computers that their clocks are in general agreement, say within seconds, but drifts or errors of minutes are possible). A standards-compliant HTTP browser will not send expired cookies with a request, based on its local clock value. To allow for significant drifts between the server and any number of requestors, the cookie expiration times are set far enough into the future to allow them to be returned as part of the second request for the URL. The actual expiration of the puzzle solution, however, depends only on the server's clock. If the solution is expired (FIG. 7, 706 ), processing is directed to (432), which we will discuss later. For the case of an unexpired solution, processing continues to 418.
[0085] Now, the first of three tamper detection checks are performed. These are described more fully in “D. Method for Detecting Tampering of Puzzle Parameters”. As these tamper detection checks are passed (418, 420, 422), and a solution is verified (425), the request is passed through this protocol for normal processing (435). If any of the checks fail, processing is directed to 432. The puzzle state is set to TAMPERED (FIG. 7, 705 ).
[0086] At 426, the server checks to see if the server challenge Cs is in the memory cache. If so, the usage of the challenge is incremented, 427. Otherwise, the usage count of Cs is initialized to 1, as this is the first time the solution has been provided for it. At this point the usage count may be evaluated to determine if it is excessive. The re-use or replay of solutions is explicitly permitted in this protocol to avoid any deleterious effects on the user experience of contemporary web sites. Web sites have much complex structure, various content types (e.g., images, sounds, hypertext), and executable elements (e.g., JavaScript, Flash, etc) which are in many cases intricately dependent on each other for proper function, display, and rendering. A web page may require several dozen or even close to a hundred separate HTTP requests to completely render itself. The present embodiment does not interfere in this process once the proof-of-work has been verified. This is accomplished by establishing the useful life of the solution through its expiration time (typically 10 seconds, though this is an adjustable parameter, suited to a particular site's content and rendering times). If the challenge has been submitted with a solution previously, the puzzle state is set to “VALID RESUBMITTED SOLUTION”, FIG. 7 (703).
[0087] At this point in the protocol, the state of the puzzle has been determined as one of the states in FIG. 7 . Now, the attacker score for the device is adjusted according to the method detailed in “C. Method for Adjusting a Device's “attacker Score” Based on Its Protocol Behavior”. In general, where the puzzle state is TAMPERED the attacker score for the device will be increased, and for a state of NEW_VALID_SOLUTION it will be decreased, and for MISSING or VALID_RESUBMITTED_SOLUTION no change will be made. System operators may determine other score adjustments, however, effectuated through the management server (FIG. 1, 110 , and FIG. 2, 207 ).
[0088] Now, some response content is returned to the requestor. The particulars of the visible content are unimportant, and even a blank page may be used. Since the objective is to engage a device in the protocol and ultimately classify it, some innocuous web page may be returned. The JavaScript of the puzzle solver and device fingerprinter is added to the basic Hyper Text Markup Language (HTML) of the response; this is the important part of the response. For a human user, they will generally be unaware that device fingerprinting and puzzle-solving is happening, perhaps only a slight delay of a second or two.
[0089] Alternative exemplary embodiments are systems and methods which use dynamic access pricing (“DAP”) in order for a requestor to obtain access to a resource, where the resource may be a transaction, content, service or other elements delivered to the requestor by the system upon which the request is made. For example, the requestor may be a web browser requesting a logon form from a web server (site). In another example, the requestor may be a television set-top box requesting account information via an application programming interface (“API”) at the head end of the cable television network. As previously discussed, “access pricing” in general refers to exchanging something of value for access to a resource. An example is ticket pricing for an event such as a sporting event or musical concert. The dynamic aspect reflects changing prices, perhaps as the number of available tickets grows smaller the price may go up in reflection of supply and demand principles from economics.
[0090] For purposes of this disclosure, the value exchanged is central processor cycles (CPU time) required to compute a solution to a client puzzle based on the difficulty of the client puzzle. The solution thus obtained comprises a type of currency unit. A solution that has been verified is called a “proof of work”. In general, units of currency obtained by puzzle-solving activities are referred to as “cryptocurrencies”. The units of a cryptocurrency are typically referred to as “coins”. Coins may be of different, or dynamic, values based on the CPU time required to obtain them, or based on the difficulty level of the client puzzle solved. For purposes of this disclosure, the difficulty level of the client puzzle is the “denomination” or value of the coin.
[0091] The price for access to a resource (as described above) is not fixed in the disclosed exemplary embodiments. The dynamic aspect of access prices for a resource reflects the behavior of the requestor with respect to a protocol which in large part resembles the protocol already described in FIGS. 4A-4F . What is different here is that puzzle difficulties are determined by a dynamic access pricing policy (“DAP policy”). The prices (analogous to puzzle difficulty) vary according to the behavior of the device solely with respect to the protocol and DAP policy, and do not depend any external factors as in (Feng et al. (previously discussed)).
[0092] It is useful to now define some terms which will be used in the following disclosure of an exemplary DAP protocol. A “protected-system” generally means a communicably reachable system or service that provides a resource (as described above) to a “requestor”. A “requestor” means a device that makes requests for access to a resource. A “puzzle-issuer-verifier” means a communicably reachable service or system that issues client puzzles to a requestor, verifies the requestor's solution, and then issues a proof-of-work to the requestor. The proof-of-work may be viewed as a “coin” with which the requestor pays the access price of the requested resource to the protected-system. In the following discussion, however, the proof-of-work resulting from a successfully verified solution will be called a “transaction authorization code” (“TAC”).
[0093] With reference now to FIGS. 10A-10N , as an alternative embodiment of the fingerprinting script (412, 415), the protected application, system, interface or device provides the device fingerprinting script or program as part of the initiation of the protocol (10001). In other alternative embodiments such as embedded devices (e.g., cable TV set-top boxes) where the manufacturer has the ability to store programs directly on the requesting device in advance, the fingerprinting and puzzler-solver codes may already be present on the requesting device.
[0094] As a result of the provisioning of the fingerprint script prior to the initial puzzle request (10001), a device fingerprint is provided as part of the request along with a transaction identifier at the initiation of the protocol (10002). This permits the puzzle-issuer-verifier to incorporate the device fingerprint, or even a set of fingerprints of various types, into the puzzle challenge (10003). This is in contrast to the method shown at (410) where fingerprints do not form part of the challenge.
[0095] This aspect of the protocol in the exemplary embodiment binds the requesting device to its fingerprint(s) throughout the entire protocol, even up to the point where the protected system is verifying the transaction codes (10004, 10005, 10006). This prevents hostile devices from engaging in fingerprint polymorphism to evade the protocol. Even if an attacking device tampers with the device fingerprint script, perhaps supplying its own fingerprint, it remains bound to that fingerprint for the entire protocol, since any changes will be detected by mismatching message authentication codes (“MAC”) (10004, 10005, 10006).
[0096] To ensure that requesting devices do not engage in fingerprint polymorphism, and to differentiate otherwise identical devices behind network address translating (“NAT”) routers or proxies, the puzzle-issuer-verifier adds a random nonce (10003) to the fingerprints declared by the device at the time of the puzzle request, and then computes a MAC on the fingerprint(s) and the nonce, to produce the fingerprint-nonce-MAC. This additional element is used to generate the puzzle challenge for the requesting device as shown previously in (410), thereby achieving the binding of the requesting device to the puzzle and in the case of a successful puzzle solution, to the transaction authorization codes received as well (10007).
[0097] Note that if at any point in the verification steps performed by the puzzle-issuer-verifier or the protected-system should the message authentication codes fail to match, the protocol stops (10007, 10008, 10009, 10010, 10011, 10012, 10013). The puzzle-issuer-verifier, having now received a verified and valid solution to a challenge by a requesting device in an “allowed” state, prepares a set of transaction authorization codes (“TAC”) to return to the requesting device. The TACs comprise a time value and four groups of elements as follows:
[0098] The time value for the expiration time for these following transaction codes based on adding the validity duration (for example, 5 seconds as shown in FIG. 16 ) to the current time of the system clock. This expiration time is referred to below as “TXN_EXPIRATION”.
[0099] The first MAC group comprises the following and the resulting MAC will be denoted “fingerprint-nonce-MAC”:
[0100] 1. The device fingerprint
[0101] 2. The fingerprint-nonce
[0102] 3. The fingerprint-nonce-MAC (message authentication code on the first two elements) computed using the shared MAC key
The second MAC group comprises the following and the resulting MAC will be denoted “TMAC”:
[0103] 1. The transaction ID
The third MAC comprises the following and the resulting MAC will be denoted “TXN_EXPIRATION_MAC”:
[0104] 1. TXN_EXPIRATION
The fourth and final group computes a MAC on the three preceding MACs, and the result will be denoted “TXN_MAC”:
1. fingerprint-nonce-MAC
2. TMAC
3. TXN_EXPIRATION_MAC
[0105] This final MAC code effectively binds the device fingerprint, the disambiguating nonce, the transaction ID, and the validity period together as a single unit. Tampering with any of the elements will result in an invalid MAC re-computation check (10005, 10006) on the protected-system, so this enforces honest transmission by the untrustworthy requesting-device of the codes from the puzzle-issuer-verifier to the protected-system.
[0106] With continuing reference to FIGS. 10A-10N , a detailed description of protocol as represented by the sequence flowchart is now provided. The protocol begins with the requestor making a request for access to a resource of the protected-system (10014). This may take the form of an HTTP request, or other network protocol, for example. The protected-system receives the request (10015), and prepares the “augmented transaction”. The transaction may represent an HTML form, for example, or may be a content element such as a web page or graphic. The augmentation (10001) consists of adding a transaction ID, authorization tokens to the puzzle-issuer-verifier (API Token and MAC), the puzzle-issuer-verifier's network endpoints, and script which enables the requestor to compute its device fingerprint and to interact with the puzzle-issuer-verifier.
[0107] The protected system now sends the augmented transaction to the requestor (10016). The requestor fills any needed elements of the transaction (e.g. username and password in the case of an account logon request) (10017). The requestor begins the process of submitting the transaction request form (10018). In the case of an HTML form, for example, there is a “submit” action defined, and the script of the augmented transaction is configured to intercept the “submit” action (a.k.a. “hooking the button”) and begin the engagement of the requestor with the puzzle-issuer-verifier. The first step in engaging the requestor with the puzzle-issuer-verifier is to compute the device fingerprint, which is a locally computed value (415). Now the requestor makes a request for a puzzle from the puzzle-issuer-verifier, providing its device fingerprint as part of the request (10002).
[0108] The puzzle-issuer-verifier receives the request, and looks up the state of the device (see FIG. 8 ) by its fingerprint in a storage element (10019). If the device is not in an allowed state (10020), the lockout period is restarted, and the access price (puzzle difficulty) is set to the policy-specified maximum (10021) (see FIG. 16 ). The puzzle-issuer-verifier now increments the access attempt counter for the device associated by its device fingerprint (10011). The incremented value is compared (10022) against the threshold for transition to denied state (see FIGS. 15 and 16 ). If the device has crossed the threshold, the access price (puzzle difficulty) is set to the policy-specified maximum (10023), and the state of the device associated by its device fingerprint is set to the denied state (10024) as specified in the DAP policy (see FIG. 16 ). Otherwise, the device remains in allowed state, and the puzzle-difficulty is set to the value corresponding to the access attempt counter value (10025) (see FIG. 15 , or increment as in FIG. 16 ).
[0109] Processing paths for devices in the various states as determined by the foregoing steps now join at connector “F” (10026). For devices that are in a denied state, the puzzle-difficulty is at a maximum level intended to function as the active countermeasure. For the devices in the allowed state, the difficulty remains in the range where it will typically require less than 1 second to compute a solution.
[0110] The puzzle-issuer-verifier now prepares the challenge, which is the subject of a hash-reversal or pre-image search. The challenge comprises the elements already noted at (410), except that the device fingerprint is added to the challenge (10003). This serves the purpose of immutably binding the device fingerprint to the puzzle, the solution and the transaction codes. The challenge is stored for future use in detection of replay attacks (10027). The puzzle challenge is now transmitted to the requestor (10028).
[0111] The requestor adds its randomly generated client nonce (10029), as noted previously at (413). The script begins the solution process of identifying a pre-image that satisfies the specified difficulty (10030) as note previously (414). Once a solution has been found, the request submits it for verification to the puzzle-issuer-verifier (10031). The puzzle-issuer-verifier performs tamper-checks (10032), which are the same as previously noted in (418-426), except that the device fingerprint now forms part of the challenge in the tamper checking steps (418, 420,422). If tampering is present (10033), the puzzle-issuer-verifier issues a response indicating a tampered solution to the requestor (10034) and the protocol engagement now stops (10007).
[0112] Continuing on, the puzzle-issuer-verifier examines the expiration time for the puzzle against its current clock to determine if the puzzle has expired (10035), as previously noted at (417). If the puzzle has expired, the puzzle-issuer-verifier sends a response indicating so (10036) to the requestor, and the protocol stops (1008).
[0113] Continuing on with an untampered and unexpired solution, the puzzle-issuer-verifier re-computes the hash of the solution and challenge (10037) and counts the number of leading zero bits in the resulting hash to determine if the offered solution is in fact an actual, valid solution (10038, and 424, 425). If the solution is invalid, the puzzle-issuer-verified sends a response indicating so to the requestor (10039), and the protocol stops (10040, 10041).
[0114] Continuing on with a valid solution, the puzzle-issuer-verifier prepares the TACs (10042) to return to the requestor as proof-of-work that will be used to pay the access price for the requested resource. Using the shared MAC key between itself and the protected-system, the puzzle-issuer-verifier performs the TAC computation as previously described. The TACs form the valid response now sent to the requestor (10043). At this point, the puzzle-issuer-verifier has completed its role in the protocol and stops (10044).
[0115] Now, the requestor augments its completed transaction request (10045) with the TACs obtained at (10043). In the example mentioned earlier in this description of an account logon form, the visible fields of username and password are filled by the human user, while the script (unnoticed by the user) has engaged the protocol and obtained TACs and placed them in HTML “hidden” form fields which will be transmitted to the protected-system's transaction handler. The TACs need not be hidden, however, in cases such as API access which occurs programmatically between two computers and does not involve a human user. The requestor now sends the augmented transaction request to the protected-system (10046).
[0116] Upon receipt of the augmented transaction request, the protected-system re-computes the four message authentication codes (MACs) previously discussed. The requestor here is treated as a generally untrustworthy relayer of information between the puzzle-issuer-verifier and the protected-system, and the MACs serve as evidence of an honest relay of information or not. In another view of this, the puzzle-issuer-verifier functions as a cryptographic “witness” of the proof-of-work, and the TACs it generates are the witness statement.
[0117] The protected-system now re-computes the first of the four MACs (“fingerprint-nonce-MAC”) which is based on the device fingerprint or fingerprints if several have been used, and the disambiguation nonce (10047).
[0118] If the re-computed fingerprint-nonce-MAC and the fingerprint-nonce-MAC provided by the requestor in the TACs match, processing continues (10005). If there is a MAC mismatch, the protected-system may choose to continue in spite of this, or it may stop. This is a policy choice of the protected-system, sometimes referred to as “fail open” (10049) or “fail closed” (10048). The reason for the policy choice is that there may be instances where communications between the three protocol actors is not present, e.g., an “Internet partition event” or possibly the puzzle-issuer-verifier is unavailable due to operational reasons.
[0119] The protected-system now re-computes the remaining three MACs: “TMAC”, “TXN_EXPIRATION_MAC” and “TXN_MAC”. The re-computed and provided TXN_MACs are checked for a match, and if they match, processing proceeds (10050, 10006). If there is a MAC mismatch (10051), the protected-system may choose to continue in spite of this (10052), or it may stop (10010) for reasons noted above with the first fingerprint-nonce-MAC.
[0120] Now the re-computed and provided TXN_EXPIRATION MACs are checked for a match (10006), and if they match, processing proceeds (10054). If there is a MAC mismatch (10006, 10053), the protected-system may choose to continue in spite of this (10054, 10055), or it may stop (10011) for reasons noted above with the other MACs.
[0121] Finally, the expiration time “TXN_EXPIRATION” is compared to the current time of the protected-system's clock to see if the untampered expiration time has passed and rendered the TACs expired (10055). If the TACs are expired, the protected-system may choose to continue in spite of this (10056, 10058), or it may stop (10057, 10012) for reasons noted above with the MACs.
[0122] At this point (10058), the protected-system may compare the TACs against a record of previously used TACs as an optional element in the protocol. Whether or not to perform this check in practice would depend on the technical characteristics of the protected-system. The purpose of such a check is to enforce a single-use policy for TACs and thereby eliminate replay attacks. So, if the TACs have been used before (10059), this fact may be treated in similar manner as noted above, either continuing on in spite of it (10060, 10061), or stopping processing (10013).
[0123] Once all of the preceding steps have been performed and processing reaches (10061), the normal handling of the request occurs. In the case of the logon example mentioned earlier, this is when the username and password would be checked for validity. In the case of an API call, the function would be invoked by the protected-system. Any results (10062) from the processing are returned to the requestor (10063) and the transaction is now complete.
[0124] With reference now to FIGS. 8, 15, and 16 , the dynamic access pricing policy for any particular “Transaction Identifier” (FIG. 16 ) determines the difficulty level of the puzzle issued to a requesting device. The initial difficulty level, indicated in FIG. 15 as “Allowed_1_Access_Price[1],” is based on policy values determined independently of the device fingerprint, its interaction history, and any other externalities of the system, which is in contrast to and unlike Feng et al. (previously discussed) who uses external information such as IP reputation, geographic coordinates, and so on.
[0125] A central element of the dynamic access pricing policy is the state transition model for the device associated by its device fingerprint as shown in FIG. 8 . In the absence of any pre-existing information about a device (801), upon encountering the device (805) and its associated device fingerprint, the state of the device transitions to the state Allowed(1) (802). The device may make self-transitions to Allowed(1) (806), or transition (807) to the state Denied(1) (803) upon a threshold event. Once in the Denied(1) state, the device may self-transition (807) based on repeated access attempts while in the Denied(1) state. Once the lockout period expires (808), the device transitions to a second state, Allowed(2) (804). The second allowed state reflects the fact that the device was previously in the Denied(1) state; the Allowed(2) state could be thought of as a “probation” state. The device may now transition back to Denied(1) (803) based upon a threshold event (809), or if the device remains quiescent for a period of time (810), its state information is released and it returns to the Initial state (801).
[0126] As the device receives puzzles, the puzzle-issuer-verifier (FIG. 11, 11001 ) tallies the number of puzzle requests over time by the device fingerprint against the transaction identifier. This is the “access attempt counter” for the device fingerprint and the transaction identifier. The tally of access attempts is stored in manner such that the age of the counter is available to the puzzle-issuer-verifier upon later retrievals (FIG. 11, 11001 ).
[0127] The DAP policy includes the concept of a “lookback period” and a “lockout period”, whereby information about a device, such as its access attempt counter, is retained for a specified period of time, after which it is discarded or removed from storage. In the exemplary embodiment shown in FIG. 11 , this is accomplished by using a memory cache key-value store (“memcache”) with expiration times (11002). When a key-value pair is placed or updated in the memcache, a duration (expiration) for the storage is included, and the internal workings of the memcached automatically purge expired key-value pairs upon expiration, thereby providing the lookback mechanism of the DAP policy. The device fingerprint-nonce-MAC serves as the base key for storing and retrieving values associated with the requesting device, its interaction with a transaction, and its associated DAP policy.
[0128] The concept of a “transaction” here is broad. A transaction generally means the result of any request by a requesting device. This may include but not be limited to logon forms and their submission to a web site, requests for reports from a server, requests for a function to be performed (service), or requests for content or a web page.
[0129] DAP policies generally means one or more “allowed” states, one or more “denied” states, and an “initial” state (for example, as shown in FIGS. 8, 15, and 16 ). The state transition conditions or events are specified as part of the DAP policy. The DAP policy also specifies puzzle difficulty levels based on the state of a device and its access attempt counter, the lookback periods for allowed states, and the lockout periods for denied states. Furthermore, the related state-transition model of a DAP policy can be generalized, as shown in FIG. 9 , to accommodate a collection of allowed states (901, 902, 903) and denied states (904, 905, 906) with complex transition topologies possible. This creates the capability for nesting DAP policies to create multiple lookback periods, for example.
[0130] In general, the DAP policy provides a schedule or correspondence between access counter values and puzzle difficulties. Various methods for list compression may be used to provide more compact representations of a DAP policy's puzzle difficulties.
[0131] An exemplary embodiment of a simplified DAP policy is shown in FIG. 16 where puzzle difficulties begin with an initial value of 11, and are incremented by 1 on each subsequent access attempt during the lookback period. The lookback periods, lockout periods, and threshold for lockout of a DAP policy may be constants, as shown in FIGS. 15 and 16 , but these values may be represented by functions as well. For example, an attacker may notice by studying the protocol that the lockout threshold is 5 and occurs in a 60 second lookback period. Therefore the attacker may choose to limit any sequence of attacks to comply with these limits and avoid detection. However, if a random number, say between 4 and 8 is used for the lockout threshold, and a random number between 45 and 75 seconds is used for the lookback period (and this changes with each update of the access attempt counter), the discernment of the policy parameters becomes more difficult for the attacker, thereby complicating efforts to avoid detection.
[0132] DAP policies may also start with a higher initial access difficulty and gradually reduce the difficulty as a device consistently complies with the protocol and does not engage in device fingerprint polymorphism. The DAP policy may even increase the difficulty after initial reducing them. One use case where a higher initial difficulty and lower subsequent difficulties are useful occurs when an attacking device would ordinarily engage in polymorphism and change its fingerprint on each puzzle request, attempting to appear “new” and obtain the possibly lower initial difficulty. By specifying a higher initial difficulty and lower subsequent difficulties, the attacking device is “rewarded” for keeping the same fingerprint on subsequent puzzle requests (but it is still subject to the lockout threshold for excessive attempts on the transaction). If the attacking device does engage in fingerprint polymorphism on each request, the higher initial price, at a minimum, functions as a request rate limiter, thereby reducing the attack intensity against the targeted transaction.
[0133] As previously discussed, most cyber-attacks involve a high degree of automation as part of the strategy. For example in an attack where unauthorized access to user accounts is the objective, lists of compromised user names and passwords from one system are tried against another (as yet uncompromised) system in the knowledge it is a not uncommon practice for users to the employ the same username and password on many different systems. Thus, one breach or compromise can lead to many others. The business of trying the credentials against new targets requires a high degree of automation to produce useful or valuable number of account takeovers.
[0134] In the case where the attacker is working against a system protected by the protocol described herein, the use of “basic” bots (automated attackers that do not have any capabilities for executing scripts provided to them) fail entirely, since they cannot request or solve puzzles and thereby obtain transaction authorization codes required to submit a logon request. The uselessness of the basic bot compels the attacker to employ “advanced” (a.k.a. “impersonator”) bots that have script execution capabilities. The advanced bots will engage in the protocol described here, obtain puzzles, solve them, and submit logon attempts with valid transaction authorization codes. However, in order to be useful, these bots must engage in a large number of logon attempts, and will produced access attempt counter threshold violations as a result. When this occurs, the exemplary DAP policy provides a “maximum difficulty” puzzle to the now locked-out device to solve.
[0135] For puzzles of the hash-reversal type (414), the solution time is an exponential function of the number of leading zeroes required when the challenge and the solution are concatenated and then hashed using a one-way function. A benchmark of this solution time on a typical desktop computer produced the expected solution time versus difficulty graph shown in FIG. 12 . Generally DAP policies would specify puzzle difficulties in the range where the expected solution time is well below 1 second (in the range of 5 to 10 referring to graph shown in Error! Reference source not found. This is because for human users of systems, there should be no observable or adverse effect on the user's experience as a result of solving puzzles.
[0136] Accordingly, the exemplary systems and methods are initially provided to determine whether or not a device will in fact solve puzzles at all, and not as much for trying to rate-limit devices at the outset. Knowing that a device will solve a puzzle, though, provides an opportunity to supply a much more difficult or “hard” puzzle when the device crosses the access attempt threshold and enters the denied or lockout state. The effect of the hard puzzle on the attacking device is to occupy the central processing unit (CPU) in a tight loop running the brute-force solver as it seeks a solution. This CPU-boundedness prevents the device from initiating any further attacks from that particular process or thread, and steals CPU resources away from any other concurrent processes or threads. This effectively removes the device from the larger “botnet” of which it is a member. This feature of the disclosed systems and methods functions as an “active countermeasure” against the attacking device.
[0137] Since botnets may comprise hundreds or thousands of computers usually under the control of single or a few “herders” (human managers), the fact that the botnet is shrinking over time as the bots go offline as a result of hard puzzles may go unnoticed by the herders. Even if the herders provide explicitly interrupts to the CPU-bound bot, or have external timers to interrupt the CPU-bound bot, this will be ineffective, since once the device (bot) returns for a new puzzle, it will be issued yet another hard puzzle since it has not emerged from the denied or lockout state. Thus, the DAP policy mechanism of providing hard puzzles upon entry to the denied or lockout states comprises an “active countermeasure” against individual bots and collections of them (“botnets”). This active countermeasure reduces attack intensity (frequency of requests) by individual devices and by the collective botnet as well.
C. Method for Adjusting a Device's “Attacker Score” Based on its Protocol Behavior
[0138] Each device classified by this embodiment accrues a score (‘attacker score’) indicative of its maliciousness or lack thereof. Referring to FIG. 5 , a state transition diagram, a device not seen by the system (i.e. there are no device fingerprints present) is NEW (501). As a NEW device it is assigned a nominal attacker score.
[0139] As described earlier in “B. Proof of Work Protocol”, device fingerprints of two types are generated to uniquely identify a device (the server-side fingerprint, SS_Fingerprint, and the more exact JS_Fingerprint). Upon a request of the server by a device, its SS_Fingerprint is computed and stored in the memory cache. Once this value is present in the memory cache, the state of the device transitions to KNOWN:SS_PRINT_ONLY (502). After compliant execution of the puzzle solver and fingerprinting script, the device will transition to KNOWN:SS_PRINT_AND_JS_PRINT (503). At this point, a device known only by its SS_Fingerprint or by that and its JS_Fingerprint is in what may be called the “gray list” (506). The gray list is the set of devices about which a final classification of either hostile of benign has yet to be made. The objective of the attacker score is to resolve the gray list devices into either a black list entry or a white list entry.
[0140] As a device participates correctly in the proof-of-work protocol, its attacker score is reduced over successive successful iterations of the proof-of-work protocol. Having seen sufficient evidence of benign behavior confirming the ability of the system to limit its request rate if necessary, the device's attacker score eventually crosses a threshold value thereby placing it on the white list (FIG. 5, 504 , FIG. 4, 429, 430, 431 ).
[0141] In the case of a hostile device, protocol violations will occur, resulting in an increase of the attacker score (FIG. 4, 432 ). Primarily in the case of denial-of-service attackers (“bots”) they will fail to execute the server-supplied JavaScript puzzle solver and device fingerprinter. As successive protocol violations occur, the attacker score will eventually cross a threshold thereby placing the device on the black list (FIG. 5, 505 , and FIG. 4, 433,434 ).
[0142] The amounts by which the attacker score is reduced or increased are adjustable by the system operator, as are the thresholds for white or black listing (FIG. 4, 430, 433 ). In addition, the various protocol violations may have individual score increments assigned (e.g. a missing puzzle is not deemed as hostile as a tampered solution). Variation of these parameters adjusts how long it takes for devices to be classified. For example, a single successful puzzle solution might be considered sufficient for whitelisting, and a single failure might result in blacklisting. In general, however, several iterations through proof-of-work protocol are desirable operationally, to account for normal puzzle and cookie expiration events.
D. Method for Detecting Tampering of Puzzle Parameters
[0143] During the verification of a puzzle solution, three tamper detection checks are performed. The full challenge claimed by the request to be the basis of the puzzle is recomputed independently by the server from Cs (obtained from the cookie) and the client nonce, Nc. The digest (hash) of these values must match Cc for a solution to pass this first tamper detection. The tampering that is detected here is the substitution of an easier Cs or one for which a hostile requestor has already computed a solution. If the challenges match (419), processing continues to 420, otherwise processing is directed to 432.
[0144] Considering FIG. 4 , at 420, the second tamper detection check is performed. All of the elements forming the server challenge Cs, except the server secret Ks, are resupplied by the requestor after solving the puzzle. The server challenge is recomputed from the parameters supplied by requestor with the addition of the server's secret key, Cs=Hash(Ns,Cb,Ks,Te,Dc,Gd). The tampering that is detected here is the substitution or alteration of any puzzle parameter that makes it easier to solve or extends its usability period (expiration time). Non-hostile devices will not alter these parameters, but hostile devices may do so in efforts to defeat the protocol. If the challenges match (421), processing continues to 423, otherwise processing is directed to 432.
[0145] At 422, the third tamper detection check is performed. Using the now-verified puzzle parameters from 420, the client challenge Cc is recomputed with the client nonce, Nc, and compared with the value of Cc supplied by the requestor. The tampering that is being detected here is the substitution or alteration of Cc such that a puzzle may be easier to solve. If the recomputed challenge and the supplied challenge match (423), processing continues to 424, otherwise processing is directed to 432.
[0146] Finally, the solution to the puzzle itself is verified by the server (424). The requestor's solution, S, is appended to the now-verified client challenge, Cc, and the digest (hash) is computed. In the case of a single difficulty parameter puzzle (as shown in FIG. 4 ) the resulting digest H=hash(Cc,S) is inspected to see if the first Gd leading bits are all zero. If so, the solution is valid and processing continues to 426. If not valid, processing is directed to 432. Again, a benign device will perform all of the steps necessary to provide a tamper-free and valid solution to the puzzle supplied by the server.
[0147] At each step in the verification, tampering of the solution, seeking to extend its usability, or submitting invalid solutions is deemed to indicate hostile device behavior. Importantly, a device engaged in denial-of-service attacks must, in order to succeed or be effective, be able to issue HTTP requests at a high rate. The time required to solve the puzzles prevents the hostile device from issuing attack requests against its target (the server here). Puzzle difficulty is adjustable by the server. Puzzle solution times will vary according the CPU speed of the requestor device, and the difficulty level required. These times can range from a few microseconds, to many seconds. For example, if a particular difficulty level requires 500 milliseconds (½ of a second) to solve, on average, then the average request rate is limited to 2 per second (1/0.5). Considering that a typical DoS attacking device generates many thousands of requests per second, it will suffer a major degradation in its attack intensity if it complies with this protocol and solves the puzzles. From the attacker's point of view, there are two approaches to get around the protocol. The first approach is to tamper with it, substituting easy but invalid answers, and replaying valid answers alone or in conjunction with a number of collaborating attack devices sharing puzzles and solutions. The second approach is to ignore the protocol entirely. Either of these protocol behaviors is judged hostile and will eventually result in the blacklisting of the device.
E. Method for Limiting Request Rates of Both Benign and Hostile Devices
[0148] The method for limiting the request rates of devices is based on the difficulty of the puzzle assigned to a requestor by the server. In turn, the puzzle difficulty is a function of the device's current attacker score. The applicability of this method is only for devices which support and execute server-supplied scripts or programs. In the current embodiment, this requestor-side functionality is based on JavaScript. Other languages may be used, including but not limited to Java, Jscript, VBScript, Flash, languages that compile to JavaScript such as Haxe, CoffeeScript, Kaffeine and so on.
[0149] The time required to find a solution to the proof-of-work puzzle is time that cannot be used by the requestor to make HTTP requests against the server. This puzzle-solving time functions as a throttle or rate-limiter. The difficulty level of a puzzle may range from the trivial to the trans-computable. A trivial puzzle would have a difficulty level of 1, and there would be 50% chance a solution will be found on the first attempt. This is because the digest function produces what seem to be random bits, ones and zeroes alternating in an unpredictable manner. So, from a computational complexity perspective, the probability of any single bit in the digest being a one or zero is ½. Obtaining a solution to a puzzle with difficulty level of n therefore is equivalent to flipping a fair coin n times and each time obtaining the same result (all heads or all tails). This is known as a Bernoulli trial. The probability of success on any single solution is then ½n and the expected number of attempts before a solution is found is simply 2n. For example, a puzzle with difficulty level of 18 will require on average 218 (262,144) attempts to find a solution. This is a relatively difficult puzzle for a contemporary computer. However, computational difficulty grows exponentially with the required number of leading zero bits.
[0150] Limiting of the request rate then is based on selecting a difficulty level that achieves the desired request rate. Without exact knowledge of the computational power of the requestor device, we can achieve relative rate limiting as opposed to exact rate limiting. The nominal attacker score for NEW devices (FIG. 5, 501 ) will have a corresponding difficulty level for puzzles issued to that device (the attacker score and the puzzle difficulty are not in general the same value). The nominal difficulty would be selected to require about 500 milliseconds on typical desktop computers. As the device increases its attacker score, the puzzle difficulty values increase. As the device decreases its attacker score, the puzzles become easier. One method for implementation of this is to maintain a table of attacker scores (or score ranges) and their corresponding puzzle difficulty levels.
F. Method for Collecting Device Fingerprints and their Associated Status from a High-Speed Memory Cache and Persisting them to a Database
[0151] The device fingerprint is used to uniquely identify and differentiate devices. As devices participate in the proof-of-work protocol, we must keep track of their attacker score. Later, the presence of a device fingerprint on a black or white list will be used to reject or accept requests respectively. The generation, collection, classification, persistence and distribution of device fingerprints classified as hostile or benign is an object of the embodiment.
[0152] Referring now to FIG. 1 , the “classifiers” (103) are an array of one or more servers providing an element of the embodiment of the embodiment. Collectively the classification servers comprise the classification service. The classification servers perform the proof-of-work protocol described in “B. Proof of Work Protocol for Device Classification” with the requestors. The memory cache (“Memcached”) (104) is a network service available to all of the classification servers. The memory cache stores pairs of keys and values and supports operations such as, without limitation, update, delete, and expiration of the data. In the present embodiment, the memory cache function is provided by Memcached (www.memcached.org), but other implementations including but not limited to CouchBase may be used as well. The memory cache is used to provide a high-speed shared memory among the classification servers. Requests are initially handled by the load balancer(s) (102), and depending on the load balancer used, successive requests by the same device may or may not be directed to the same classification server (“sticky” or “non-sticky” load balancing). In the present embodiment, the load balancer function is provided by HAProxy, though other load balancers, including but not limited to F5 Local Traffic Manager, Radware AppDirector, INGnx, CoyotePoint Equalizer, Barracuda Load Balancer, etc. may be used. A common requirement for any front-end load balancer and filter element is the ability to compute the server-side fingerprint (SS_Fingerprint), inspect HTTP cookies, and filter according to access control lists. All of the example possible balancer/filter elements cited support this minimal functionality.
[0153] As devices are gradually white-listed or black-listed, this status information is initially stored in the memory cache (104, 204). However, the memory cache is a volatile and non-persistent data store, so its contents must be periodically transferred to a database that provides persistent and reliable storage of the data (106). This is accomplished by the fingerprint publishing server (105). Referring now to FIG. 3 , periodically (301), preferably but not limitingly by means of an automatic task scheduler such as, without limitation, Unix/Linux cron, Autosys, or Windows Task Manager, the fingerprint publishing server queries all of the key-value pairs from the memory cache, performs any required transformations, and then adds new fingerprints or updates existing fingerprints in a database (302, 303, 106, 206). In the present embodiment, the database function is provided by MySQL, but other databases including but not limited to Oracle RDB, Microsoft SQL Server, Sybase, and so on could be used in alternative embodiments.
[0154] The fingerprint database comprises at a minimum the following tables: 1) a white list of device ID (Identifier) considered non-hostile, 2) a black list of device IDs considered hostile. Each list has at least the device fingerprint, IP address, time stamps of first and last seen events, the attacker score, and the time stamp of when it was placed on the list.
[0155] In the fingerprint dissemination method described more fully in “I. Method for Dissemination of Device Blacklists and Whitelists to All Subscribers of the Web Service”, the fingerprint publishing service (304) provides black and white lists of device fingerprints from this database to service subscribers.
G. Web Services Deployment Model to Provide Device Classification Services to Third Parties
[0156] The web services deployment model to provide device classification services to third parties provides a method for service subscribers to defend their web services from denial-of-service attacks without requiring extensive modifications to their own web services. In addition, as members of a set of subscribers, each member benefits from accumulation of device fingerprints of hostile devices, potentially before these devices engage in attacks against them. By having advance identification of attacker devices, service subscribers can deploy forward filtering elements to blunt future attacks (“forewarned is forearmed”).
[0157] Turning to FIGS. 1 and 3 now (FIG. 3 is similar to FIG. 4 , with some details elided to provide clarity on the operation of the web service rather than the proof-of-work protocol for device classification), which respectively show the web services deployment architecture and its related activity model, we consider an initial request by an unclassified device in FIG. 3, 305 . As in 403-408, at 306-309 already white-listed devices pass the filtering function deployed in the third-party subscriber's Load-Balancer/Filter at 108. The HTTP request is forwarded by the Load-Balancer/Filter to a content server (109, 309).
[0158] Otherwise, the SS_Fingerprint is computed at 310, and if present on the local black list (314,317) the request is dropped. For a hostile device that does not follow the HTTP Redirect instruction (315) it will reappear in this processing shortly. Each time, a counter of the number of times this device identified by SS_Fingerprint fails to present a JS_Fingerprint is incremented (311). Now, after exceeding an adjustable threshold, the SS_Fingerprint is classified as a hostile device and placed on the blacklist (313) maintained by the fingerprint publishing service. Hostile devices will sometimes engage in behavior to alter their SS_Fingerprint, usually by varying the User-Agent string. In practice, an attacking computer will randomly select a User-Agent from a small pre-defined set (˜10). Each of these variations in SS_Fingerprint will eventually be black-listed as they are repeatedly presented without any proof-of-work, however.
[0159] If the device is on the local black list of the subscriber's front-end filter, the request is dropped (317).
[0160] If the device is as yet unclassified, an HTTP Redirect/302 response (312) is returned to the device to direct it to the device classification service. There are several possible behaviors of requesting devices at this point: 1) the requestor will follow the HTTP Redirect instruction to start engaging in the proof-of-work protocol with device classification service (this may be done by both devices eventually classified as hostile or non-hostile) 2) the requestor will ignore the HTTP Redirect instruction and make yet another request (305) against the subscriber's front-end Load-Balancer/Filter (108). As noted above, this behavior will eventually result in the device being classified as hostile and entered onto a local black list at the front-end filter (108, 313). The subscriber's front-end filter transmits black-listed device fingerprint and other particulars (e.g., timestamps, IP, expiration date, fingerprint type) to the fingerprint publishing service (107).
[0161] If the device follows the HTTP Redirect (Response Code 302) from the subscriber's front-end filter, it will make a subsequent HTTP request of the classification servers (103). At this point, the device will be engaged in the proof-of-work protocol for device classification described in “B. Proof of Work Protocol for Device Classification”. The device at this point may or may not cooperate with the protocol; cooperating devices will eventually be white-listed and non-cooperating devices will be black-listed. In practice, hostile devices may follow the HTTP 302 Redirect instruction at (315), but will fail to execute JavaScript proof-of-work scripts. They may either continue working against the classification servers, or return to the subscriber's front-end. Either way, because the SS_Fingerprint is computed in an identical manner by both the classification service and the fingerprinting routine deployed at the subscriber's front-end filter, the hostile devices will be blacklisted by either or both the classification service or the subscriber front-end filter.
[0162] Devices successfully solving puzzles while engaged in the proof-of-work protocol with the classification servers will eventually be white-listed.
[0163] It is conceivable that a hostile device will initially cooperate with the proof-of-work protocol in order to ‘sneak’ onto the white list. Once white-listed, it would then launch an attack with a high request rate against a target. This fact will normally be detected by the operational monitoring systems and personnel, however. The operational response in this case is to invalidate the current whitelist used by the front-end filter (102, 202), and cause all subsequent requesting devices to undergo re-classification.
[0164] From time to time, preferably but not limitingly according to an automatic task scheduler, the subscriber front-end filter updates (320, 108) its white and black list data (which may be in the form of access control lists or ACLs) from the fingerprint publishing service (319). This method is described more fully in “I. Method for Dissemination of Device Blacklists and Whitelists to All Subscribers of the Web Service”. As there are potentially many subscribers to the fingerprint publishing service, each subscriber benefits from the device classifications performed on the behalf of other subscribers.
H. Stand-Alone Deployment Model to Provide Device Classification Services to a Single Domain
[0165] Turning now to FIG. 2 , a deployment architecture for a stand-alone system for device classification for a single domain is shown. By single domain, we mean any web services sharing a common internet domain name, e.g. “.uspto.gov” or “.financialservices.com”. This is based on the behavior of standard-compliant web browsers (requesting devices) to return cookies to any server in such a domain name space. The proof-of-work protocol sets and reads cookies on either a domain-level basis or optionally on a per-service name basis.
[0166] The stand-alone deployment may be used where for various reasons it is not feasible or permitted to use the classification web service. One example of such a situation might be a government or military system where policies prohibit communication with external services. Another example would be the presence of an internal security policy requiring all critical services for maintaining system availability (which this classification service is) be operated under the physical control of the enterprise IT staff.
[0167] The stand-alone deployment model provides all of the same functions as the web services model described fully in “G. Web Services Deployment Model To Provide Device Classification Services To Third Parties”. In addition, the stand-alone model provides functionality at least for 1) the ability to immediately invalidate all white and black lists and initiate reclassification all new requestors, and 2) the ability to engage hostile but JavaScript-compliant attackers in the rate-limiting features of the proof-of-work protocol.
[0168] Again turning to FIG. 2 , the stand-alone deployment model comprises one or more front-end load-balancer/filter devices (202) as described in “G. Web Services Deployment Model To Provide Device Classification Services To Third Parties”, a classification filter software element (203), and content servers (208). The other elements of the classification service (204,205,206,207) are the same as for the web services deployment model. The content servers (208) may be of various types, but are in general web servers running the HTTP protocol and capable of implementing a request filter.
[0169] In this model, the classification function is provided by installing the proof-of-work protocol, attacker score adjustment, and black/white listing functions as a server request filter. A server request filter is a pre-processor for HTTP requests, performing its actions before the usual handling of the request occurs. In the present embodiment, the request filter is implemented, without limitation, as a “PHP auto-prepend” element in a “LAMP stack” machine (including without limitation LAMP: Linux, Apache, MySQL, PHP). Additionally, in the present embodiment, the root level .htaccess file identifies all content types of the server as subject to processing by the PHP processor. Alternatively, in a Java application server such as, without limitation, JBOSS, or Oracle WebLogic, the functionality would be implemented as a “servlet filter” element. Other possible variations include but are not limited to C, C#, VB (or other compatible Microsoft languages), and request filters implemented in Microsoft Internet Information Server (IIS). The classification filter performs all of the functions detailed in Sections B., C., D., E., and F.
I. Method for Dissemination of Device Blacklists and Whitelists to all Subscribers of the Web Service
[0170] This method for dissemination of device blacklists and whitelists to all subscribers of the web service provides a way for service subscribers to benefit from the denial-of-service attack experiences of other subscribers. In practice, denial-of-service attacks have targeted particular industry sectors (e.g. banking), and on successive days attacked first one bank, then another, and another, and so on. The same or largely same set of “bots” (commonly used short form for ‘robot’) is used by the attackers on successive attacks against different targets. In case of the present systems and methods deployed as a web service with a set of subscribers, the system will classify and obtain device fingerprints (at least the SS_Fingerprint and IP address) of the attacking “bots” on what is called “Day Zero” of the attack. The target on Day Zero will sustain the attack until the system generates the black and white lists and they are deployed into a forward filter (see FIG. 1, 102 , and FIG. 2, 202 ). Other subscribers not targeted on Day Zero will benefit from receiving the black list device fingerprint in advance of an attack on Day One, Day Two, etc. These subscribers can then efficiently filter requests based on these lists.
[0171] The method for dissemination of the black and white lists in the present embodiment of the systems and methods is as a web service. A web server accepts requests for the lists from a subscriber and returns the lists. A subscriber may request a complete set of black and white lists, or may select a subset based on date, time, attacker score, updates since last request, country of origin based on IP address mapping, and parameters of their subscription. The subscriber presents a credential in the form of, for example, user ID and password, or client certificate (e.g., X.509), or a one-time token value (e.g., RSA token) to gain access to the publishing service. The subscriber may also select a format for the list, including but not limited to, 1) a text file 2) a comma-separated values file 3) hypertext markup language (HTML) 4) standard query language (SQL) 5).htaccess deny and .htaccess allow 6) Web.config allow and Web.config deny 7) IP ranges 8) Decimal/CIDR IP notation 8) Cisco ACL.
[0172] Other possible methods for dissemination of the black and white lists may include, without limitation, 1) direct database connections 2) file transfers through File Transfer Protocol (FTP), Secure File Transfer Protocol (SFTP) and other variants 3) file transfers through Connect:Direct Network Data Mover (NDM) 4) delivery of compact data disks, flash memory drives, secure digital cards or other portable data storage devices, and 5) electronic mail attachments.
J. Management Server for Control of the System Parameters
[0173] Turning to FIGS. 1 and 2 , a management server (110, 207) comprises an element of the web services and stand-alone deployment models. The management server provides an interface for system operators to set, inspect, and modify various parameters of the classification system. In each deployment model, the setting, inspection, and modification of system parameters applies to: 1) the server secret, Ks 2) the expiration time for puzzle solutions, Te 3) the nominal attack score 4) the puzzle difficulty level parameter(s) associated with each score value or range of score values, and 5) the score increments or decrements for each of the state transitions in the proof-of-work protocol as shown in FIG. 7 (701-706).
[0174] The system parameters are placed in the memory cache (104,204) by the management server at system startup or by system operator actions. The classification servers (103) or filters (203) read the various parameters from the memory cache.
[0175] By virtue of its placement within the enterprise's infrastructure in the case of the stand-alone deployment model, the system operators may change the server secret, Ks, and also invalidate the white list in the event of hostile devices ‘sneaking’ onto the white list and initiating an attack. This change of the server secret key invalidates all currently valid puzzle solutions and causes all requestors to be treated as “new” (FIG. 5 ) and undergo reclassification. However, because hostile devices have used a ploy to evade the classification system's protocols, the threshold for whitelisting is made infinitely large so that no whitelisting occurs. In effect, devices remain in the “gray list” (506) or become black-listed until the protocol parameters are changed to permit white-listing to occur. The hostile devices initially gained entry to the white list by impersonating (i.e. solving puzzles) benign or rate-limitable devices. Now, in this operational mode of the system, they will not be whitelisted. The attacker may respond by solving puzzles again in an attempt to become whitelisted, but no whitelisting is permitted, and solving puzzles engages the attacker in request rate limitation as described in “E. Method for Limiting Request Rates of both Benign and Hostile Devices” thereby blunting the attack.
[0176] In the case of the web services deployment model sustaining such a masquerade attack, similar operational parameter adjustments may be made by the service operator, in this case on a per-subscriber basis.
K. Connections of Main Elements and Sub-Elements of the Systems and Methods
[0177] The main elements of the exemplary embodiments comprise 1) a proof-of-work protocol, 2) a method for adjusting a device's ‘attacker score’ based on its protocol behavior, 3) a method for detecting tampering of puzzle parameters, 4) a method for limiting request rates of both benign and hostile devices, 5) a method for collecting device fingerprints and their associated status from a high-speed memory cache and persisting them to a database, 6) a web services deployment model to provide device classification services to third parties, and 7) a deployment model of the attacker identification system as a request filter at the front-end of a distributed web services system, 8) a method for dissemination of device blacklists and whitelists to all subscribers of the web service and 9) a management server for control of the system parameters to enable various modes of classification and device request rate limiting.
[0178] Sub-elements of the exemplary embodiments comprise 1) a client puzzle (410, and FIG. 7 ) 2) two methods for device fingerprinting (404,415) 3) a front-end load-balancer and filtering device (102,202) 4) a subscriber load-balancer filter device (108) 5) classification servers (103) and classification filters (203) 6) a networked high-speed memory cache (104,204) 7) HTTP web content servers (109,208), 8) a device fingerprint and black/white list database (106,206), and 9) a fingerprint publishing service (105,205).
[0179] The connections between the main elements and the sub-elements are as follows in the exemplary embodiments:
[0180] The proof-of-work protocol (B.) uses a client puzzle to cause a device to expend CPU cycles as part of validating its request on a web service. The proof-of-work protocol also uses the server-side device fingerprinting (404) and client-side fingerprinting (415) to establish a device identifier that is almost surely unique. The proof-of-work protocol is executed by either the classification servers (103) or in an alternative embodiment the classification filter software (203). The proof-of-work protocol uses the high-speed memory cache (104,204) to store and share information among classification servers (103) or classification filters (203). The proof-of-work protocol generates white and black lists of device classifications and stores them in the high-speed memory cache (104,204).
[0181] The method of adjusting a device's “attacker score” based on its protocol behavior (C.) uses the networked high-speed memory cache (104,204) to store device attacker scores. The attacker score adjustment method is executed by either the classification servers (103) or in an alternative embodiment the classification filter software (203).
[0182] The method for detecting tampering of puzzle parameters (D.) is executed by either the classification servers (103) or in an alternative embodiment the classification filter software (203).
[0183] The method for limiting request rates of both benign and hostile devices (E.) uses the client puzzle (410, and FIG. 7 ) to control request rates of devices, specifically using the difficulty level parameters related to the attacker score. The method for limiting request rates of both benign and hostile devices (E.) is executed by either the classification servers (103) or in an alternative embodiment the classification filter software (203).
[0184] The method for collecting device fingerprints and their associated status from a high-speed memory cache and persisting them to a database (F.) transfers data from the networked high-speed memory cache (104,204) to a device fingerprint and black/white list database (106,206) via the fingerprint publishing service (105,205).
[0185] The web services deployment model to provide device classification services to third parties (G.) uses sub-elements identified here 1) a client puzzle (410, and FIG. 7 ) 2) two methods for device fingerprinting (404,415) 3) a front-end load-balancer and filtering device (102) 4) a subscriber load-balancer filter device (108) 5) classification servers (103) 6) a networked high-speed memory cache (104), 7) a device fingerprint and black/white list database (106), and 8) a fingerprint publishing service (105).
[0186] The stand-alone deployment model of the attacker identification system as a request filter at the front-end of a distributed web services system (H.) uses 1) a client puzzle (410, and FIG. 7 ) 2) two methods for device fingerprinting (404,415) 3) a front-end load-balancer and filtering device (102,202) 4) classification filters (203) 5) a networked high-speed memory cache (204) 7) HTTP web content servers (208), 8) a device fingerprint and black/white list database (206), and 9) a fingerprint publishing service (205).
[0187] The method for dissemination of device blacklists and whitelists to all subscribers of the web service (I.) uses 1) a device fingerprint and black/white list database (106,206), and 3) a fingerprint publishing service (105,205).
[0188] The management server for control of the system parameters to enable various modes of classification and device request rate limiting (J.) uses 1) a networked high-speed memory cache (104,204) and 2) a fingerprint publishing service (105,205).
L. Alternative Embodiments
[0189] Alternative embodiments of the systems and methods may be achieved in the following manners:
-
- [0190] 1. The front-end load-balancer and filtering device (102,202) may be implemented by using any number of open-source and commercial products including but not limited to HAProxy, F5 Local Traffic Manager (LTM), Radware AppDirector, INGnx, CoyotePoint Equalizer, and Barracuda Load Balancer
- [0191] 2. The classification server (103) or service (203) may be executed on any number of HTTP servers, both open-source and commercial products, including but not limited to AOLserver, Apache HTTP Server, Apache Tomcat, Boa, Caucho Resin Server, Caudium, Cherokee HTTP Server, HFS, Hiawatha HTTP Server, IBM HTTP Server, Internet Information Services, Jetty, lighttpd, LiteSpeed Web Server, NaviServer, NCSA HTTPd, nginx, nodejs, OpenLink Virtuoso, Oracle HTTP Server, Oracle iPlanet Web Server, Oracle WebLogic Server, thttpd, TUX web server, Wakanda Server, Xitami, Yaws, and Zeus Web Server.
- [0192] 3. The classification server (103) or service (203) and the method for transferring data from the memory cached to a database (F.) may be implemented in various software languages including but not limited to: PHP, Java, Perl, C, C++, C#, J#, Python, TCL, Cold Fusion, Visual Basic, Lua, Ruby, and Visual Basic .NET.
- [0193] 4. The client puzzles used by the proof-of-work protocol (B.) may include but not be limited to “Guided Tour Puzzle”, single level of difficulty hash pre-image puzzle, two-parameter hash pre-image puzzle, integer square root modulo a large prime, Weaken Fiat-Shamir signatures, Ong-Schnorr-Shamir signature, partial hash inversion, hash sequences, Diffie-Hellman-based puzzles, Mbound, Hokkaido, and Merkle tree based puzzles.
- [0194] 5. Database servers used for implementing the device fingerprint database (106,206) may include but not be limited to: 4D (4th Dimension), ADABAS, Adaptive Server Enterprise, Advantage Database Server (ADS), Altibase, Apache Derby, Clustrix, CUBRID, Datacom, DB2, Drizzle, Empress Embedded Database, EXASolution, Firebird, HSQLDB, H2, Informix Dynamic Server, Ingres, InterBase, Linter SQL RDBMS, LucidDB, MariaDB, MaxDB, Microsoft Access (JET), Microsoft Visual Foxpro, Microsoft SQL Server, Microsoft SQL Server Compact (Embedded Database), MonetDB/SQL, mSQL, MySQL, MemSQL, Nexusdb, HP NonStop SQL, Omnis Studio, OpenBase SQL, OpenEdge, OpenLink Virtuoso, Oracle RDB, Paradox, Pervasive PSQL, Polyhedra DBMS, PostgreSQL, R:Base, RDM, RDM Server, ScimoreDB, SmallSQL, SQL Anywhere, SQLBase, SQLite, Superbase, Teradata, UniData, and Xeround Cloud Database.
- [0195] 6. Device fingerprinting may implemented in a number of ways, including but not limited to: 41st Parameter DeviceInsight and Time Differential Linking (TDL), Oracle Adpative Access Manager (OAAM) Flash and JavaScript client-side fingerprinters, and the methods described above in (B.).
[0196] Further, one alternative system and method for a DAP protocol is shown in FIG. 13 , where the protected-system (13004), the puzzle-issuer-verifier (13001), and a shared memory cache (13002) supporting expiration times are configured within the same system boundary (13006). This configuration of elements is applicable to “Internet of Things” (IoT) devices such as industrial controllers, heating-ventilation-air-conditioning (HVAC) systems, automated tank gauging systems (ATGs), physical alarms (burglar alarms), home automation systems, automobiles, network routers, and the like, since currently many of these types of devices have network connectivity allowing remote access which can be the subject of a Distributed Denial of Service (“DDoS”) or account-takeover attack by external requestors (13003). This embodiment provides a “self-defense” capability for this class of devices.
[0197] A second alternative embodiment of a DAP protocol system and method is shown in FIG. 14 , where the protected-system (14004), the puzzle-issuer-verifier (14001), and a shared memory cache (14002) supporting expiration times are configured as in the exemplary embodiment shown in FIG. 11 . However, in this embodiment, the protected-system (14004) does not deliver the device fingerprint script and requestor-side protocol client (14005) (the code that request puzzles, solves them, submits them for verification, and sends transaction codes to the protected-system), since here that software code has been pre-installed on the requesting device (14003) by its manufacturer.
[0198] With a pre-installed device fingerprinter and protocol client, the requesting device can develop almost assuredly unique device fingerprints based the software's ability to access hardware elements such as CPU IDs, disk IDs, network interface media access coding, and in the case of mobile phones identifiers such as the IMEI (International Mobile Equipment Indicator) or ESN (Electronic Serial Number). The device can also access pre-installed digital certificates to support authentication. This second alternative embodiment is applicable to devices such as mobile phones, television set-top boxes, and many of the IoT devices noted for the first alternative embodiment above.
M. Operation of an Exemplary Embodiment
[0199] The operation of an exemplary embodiment of the systems and methods will be described in the first case as the stand-alone deployment architecture (H.), and in the second case as a web services deployment model with subscribers (G.). This order of description will simplify the matter for the web services deployment since it may be viewed as a generalization of the stand-alone deployment model.
[0200] The stand-alone deployment is depicted in FIG. 2 . Before beginning operations, the classification filter (203) is installed as an HTTP request preprocessor in the various content servers (208). Configuration parameters of the content servers ensure that the filter is applied to content types possibly delivered by the server (e.g. html, text, img, and on on). The load-balance and front-end filter (202) will initially have no device fingerprints established as filter criteria; these will arrive later after devices are classified. The memory cache (204) is started, and it begins with no data in it. Next the management server (207) writes the protocol parameters into the memory cache. These are the values for internet domain of applicability (e.g. .uspto.gov), the puzzle expiration time Te, the server secret key Ks, a table of puzzle difficulties corresponding to values or ranges of attacker scores, the nominal attacker score, the white list and black list score threshold values, and the score increments and decrements for the puzzle state transitions shown in FIG. 7 . As a general condition of distributed systems operations, all computers participating in the system should engage in a time-synchronization protocol such as, without limitation, Network Time Protocol (NTP) in order assure close agreement among their respective clocks. Finally, the database server and fingerprint publishers are started.
[0201] Now that the system is initialized, it is ready to classify requestor devices. Devices are initially NEW or unknown and therefore engaged in the proof-of-work protocol. Hostile devices will incur protocol violations that gradually increase their attacker score. As they continue to interact with classification filter, their attacker score will cross the black list threshold and they will be noted as such in the memory cache (204). In typical operations, only a few iterations of the proof-of-work protocol (e.g. 2-4) are necessary to reliably classify a device as hostile. Similarly, benign or non-hostile devices will after a few iterations of the protocol be classified as such and noted so in the memory cache. The design driver for the memory cache instead of direct writing to the database is the need for processing very high rates of request, since during a denial-of-service attack request rates may be several hundreds of thousands per second. The memory cache is orders of magnitude faster than the physical disk Input/Output (I/O) of a database server.
[0202] Periodically, the memory cache is copied to the database (206) by fingerprint publishing service (205). As white and black lists accumulate, they are transmitted to the load-balancer front-end filter (202) and placed as filter criteria on incoming requests. Requests originating from white-listed devise are allow to pass, and those from black-listed devices are refused or dropped.
[0203] In the possible case of hostile devices masquerading as non-hostile ones in order to gain white list status whereupon they launch a high request rate attack, such an event is readily detected by typical monitoring functions of distributed web systems. An alert is typically generated by the monitoring functions for handling by the operations staff. The operational response to this masquerade attack is to reset the server secret key, invalidate the white list in the database server (206), restart the memory cache (204) clearing all data from it, and remove the white list filter from the front-end filter (202). A final step in the operational response to this attack is to set new attacker score adjustment and puzzle difficulty parameters in place such that no white-listing occurs, so that all JavaScript-compliant devices will be required to incur delay through puzzle-solving work. If the hostile devices resort to protocol violating behavior because of the throttling effect of the proof-of-work puzzles, they will be blacklisted.
[0204] The operation of an embodiment in the second case as a web services deployment model with subscribers is similar to what just been described for the stand-alone case. In terms of system configuration, instead of a classification filter software element installed as request preprocessor, a dedicated set of classification servers comprising the classification service (103) embodies this function now. In addition, two load-balancer front-end filtering elements are deployed, one in front of the classification service (102) and another (108) in front the subscriber's web system. The operation of the management server (110), memory cache (104), fingerprint publisher (105), fingerprint database (106) are as described for the stand-alone case already. The system state is initialized in the same manner described above for the stand-alone case, with the addition that both front-end filter devices (102,108) have no filter criteria in place (in a multi-subscriber scenario, initialization of the filter criteria for 102 is constrained in scope each particular subscriber). A final configuration element is the establishment of a fully-qualified domain name (FQDN) for the classification service such its domain is the same as the subscriber's. For example, the classification might be designated “classifier.uspto.gov”. The reason for this is that cookies involved in the proof-of-work protocol should be sent by standards-compliant devices to any server in the domain *.uspto.gov.
[0205] Now, the service is ready to classify requestors. Initially requests will be made of some web service in subscriber's domain (e.g. www.uspto.gov). The front-end filter (108) will determine whether a device is white-listed, black-listed, or unclassified. White-listed device's request will be passed through to their destination, black-listed device's request will be refused or dropped, and unclassified devices will be redirected to the classification service. In the case of device disrespecting the redirection, the front-end filter (108) will black-list them itself. This subscriber local blacklist will be periodically collected by fingerprint publishing service.
[0206] Devices following the redirect to the classification service will be engaged in the proof-of-work protocol and eventually be classified as hostile or benign/non-hostile. The device fingerprints for the white and black list are periodically sent to the subscriber front-end filter (108) for application as request filter criteria.
[0207] As a networking consideration, it is important that the network path for sending the filter criteria to the subscriber be independent of the external path to the front-end filter. During a denial-of-service attack the external link may become saturated or unusable, so a separate, private path for communicating between the classification service and the subscriber front-end filter is possibly, without limitation, as a private network link, packet radio link, or some other assured secondary channel.
[0208] In the multi-subscriber situation, which is an exemplary operational embodiment, all subscribers will share in the white and black lists of device fingerprints though periodic or on-demand distributions of that information.
[0209] In the case of the masquerade attack described for the stand-alone deployment case, the same operational responses will be made by the system operator of the classification service. These actions must be coordinated between the subscriber and classification service operator.
[0210] As an alternative embodiment, an exemplary DAP system is shown in FIG. 11 . In the exemplary embodiment of FIG. 11 , the puzzle-issuer-verifier (11001), and a shared memory cache (11002) supporting expiration times are enclosed by a system boundary, i.e. the memory cache communicates with the puzzle-issuer-verifier. The protected-system (11004) is external to the system boundary as is the requestor (11003). This embodiment is applicable to systems where the protected-system is a web site or a network API service, and the requestor is a web browser or script-capable program accessing the network API service. The puzzle-issuer-verifier operates as a web service in this case. Where the requestor is a browser, the communication between it and the puzzle-issuer-verifier is implemented using XMLHttpRequest (XHR) calls, either in single-origin mode or in cross-origin-resource-sharing (CORS) mode.
[0211] What has been described and illustrated herein is exemplary embodiments of the systems and methods along with some of its variations. The terms, descriptions and figures used herein are set forth by way of illustration only and are not meant as limitations. Those skilled in the art will recognize that many variations are possible within the spirit and scope of this disclosure in which all terms are meant in their broadest, reasonable sense unless otherwise indicated. Any headings utilized within the description are for convenience only and have no legal or limiting effect.
Claims
What is claimed is:
1. A dynamic access pricing and active countermeasure method against automated Internet attackers, comprising:
receiving a request for access to an Internet resource from a device;
assigning a transaction identifier to the request;
obtaining a device fingerprint of the device;
determining a device state of the device;
incrementing an access attempt counter associated with the device fingerprint if the device is in an initial state or allowed state;
accessing a dynamic access pricing (DAP) policy associated with the transaction identifier;
providing a first puzzle to the device, wherein the device fingerprint is incorporated into the first puzzle and the first puzzle has a difficulty level based on the DAP policy for at least one of the access attempt counter value and the device state;
receiving a solution to the first puzzle from the device and performing at least one tamper check on the solution, wherein the at least one tamper check includes at least one of:
computing a tamper check puzzle using a device nonce returned in the solution and the first puzzle, and comparing the tamper check puzzle with a full challenge returned in the solution,
comparing the first puzzle with a returned puzzle that is returned in the solution, and
computing a verified tamper check puzzle using the device nonce and at least one verified untampered parameter of the solution, and comparing the verified tamper check puzzle with the full challenge;
blacklisting the device if two or more different fingerprints submit solutions to the full challenge;
computing at least one transaction authorization code (TAC) based on at least one of: a fingerprint-nonce-Message Authentication Code (MAC), a transaction identification MAC (TMAC), a transaction code validity duration MAC (TXN_EXPIRATION), and a transaction MAC (TXN_MAC);
providing the at least one TAC to the device;
receiving an augmented transaction request from the device;
computing at least one verification MAC based on the augmented transaction request for each of the at least one MAC used in computing the at least one TAC; and
comparing each of the at least one verification MAC with the corresponding MAC used in computing the TAC.
2. The method of claim 1, wherein obtaining the device fingerprint comprises:
providing a device fingerprinting script to the device which, when executed, causes the device to generate and return the device fingerprint; and,
receiving the device fingerprint from the device.
3. The method of claim 1, further comprising setting the difficulty level of the first puzzle to a maximum difficulty of the DAP policy if the device is in a denied state.
4. The method of claim 1, further comprising comparing a number of access attempts indicated by the access attempt counter with a threshold for transition to a denied state, and setting the difficulty level of the first puzzle to a maximum difficulty of the DAP policy if the number of access attempts exceeds the threshold for transition to a denied state.
5. The method of claim 1, further comprising providing a second puzzle to the device, wherein the second puzzle has a difficulty level that is different than the difficulty level of the first puzzle.
6. The method of claim 1, wherein determining whether the device is in an initial state, an allowed state, or a denied state is based at least in part on at least one of a lookback period and a lockout period of the DAP policy.
7. The method of claim 1, wherein the interaction history comprises the state of the device and a number of access attempts associated with the device fingerprint.
8. The method of claim 7, further comprising associating and storing the first puzzle and number of access attempts associated with the device fingerprint.
9. The method of claim 1, further comprising adding a random nonce to the device fingerprint to generate a fingerprint-nonce-message authentication code (fingerprint-nonce-MAC), and the first puzzle is based at least in part on the fingerprint-nonce-MAC.
10. The method of claim 1, further comprising terminating engagement with the device if tampering is detected.
11. The method of claim 1, further comprising determining whether the first puzzle is expired, and terminating engagement with the device if the first puzzle is expired.
12. The method of claim 1, further comprising:
determining whether the solution is valid by computing a hash of the solution and the first puzzle and comparing the number of leading zero bits in the hash with the difficulty level of the puzzle; and,
terminating engagement with the device if the solution is not valid.
13. The method of claim 1, further comprising terminating engagement with the device if any verification MAC does not match the corresponding MAC used in computing the TAC.
14. The method of claim 1, further comprising maintaining engagement with the device if any verification MAC does not match the corresponding MAC.
15. The method of claim 1, further comprising determining whether the at least one TAC has been used for a previous request for access to the network resource.
16. A non-transitory computer-readable medium, comprising:
instructions that, when executed by a processor, cause the process or perform a dynamic access pricing (DAP) and active countermeasure method against automated Internet attackers, comprising:
receiving a request for access to an Internet resource from a device;
assigning a transaction identifier to the request;
obtaining a device fingerprint of the device;
determining a device state of the device;
incrementing an access attempt counter associated with the device fingerprint if the device is in an initial state or allowed state;
accessing a dynamic access pricing (DAP) policy associated with the transaction identifier;
providing a first puzzle to the device, wherein the device fingerprint is incorporated into the first puzzle and the first puzzle has a difficulty level based on the DAP policy for at least one of the access attempt counter value and the device state;
receiving a solution to the first puzzle from the device and performing at least one tamper check on the solution, wherein the at least one tamper check includes at least one of:
computing a tamper check puzzle using a device nonce returned in the solution and the first puzzle, and comparing the tamper check puzzle with a full challenge returned in the solution,
comparing the first puzzle with a returned puzzle that is returned in the solution, and
computing a verified tamper check puzzle using the device nonce and at least one verified untampered parameter of the solution, and comparing the verified tamper check puzzle with the full challenge;
blacklisting the device if two or more different fingerprints submit solutions to the full challenge;
computing at least one transaction authorization code (TAC) based on at least one of: a fingerprint-nonce-Message Authentication Code (MAC), a transaction identification MAC (TMAC), a transaction code validity duration MAC (TXN_EXPIRATION), and a transaction MAC (TXN_MAC);
providing the at least one TAC to the device;
receiving an augmented transaction request from the device;
computing at least one verification MAC based on the augmented transaction request for each of the at least one MAC used in computing the at least one TAC; and
comparing each of the at least one verification MAC with the corresponding MAC used in computing the TAC.
17. The non-transitory computer-readable medium of claim 16, wherein obtaining the device fingerprint comprises:
providing a device fingerprinting script to the device which, when executed, causes the device to generate and return the device fingerprint; and,
receiving the device fingerprint from the device.
18. The non-transitory computer-readable medium of claim 16, wherein the method further comprises setting the difficulty level of the first puzzle to a maximum difficulty of the DAP policy if the device is in a denied state.
19. The non-transitory computer-readable medium of claim 16, wherein the method further comprises comparing a number of access attempts indicated by the access attempt counter with a threshold for transition to a denied state, and setting the difficulty level of the first puzzle to a maximum difficulty of the DAP policy if the number of access attempts exceeds the threshold for transition to a denied state.
20. The non-transitory computer-readable medium of claim 16, wherein the method further comprises providing a second puzzle to the device, wherein the second puzzle has a difficulty level that is different than the difficulty level of the first puzzle.
21. The non-transitory computer-readable medium of claim 16, wherein determining whether the device is in an initial state, an allowed state, or a denied state is based at least in part on at least one of a lookback period and a lockout period of the DAP policy.
22. The non-transitory computer-readable medium of claim 16, wherein the interaction history comprises the state of the device and a number of access attempts associated with the device fingerprint.
23. The non-transitory computer-readable medium of claim 22, wherein the method further comprises associating and storing the first puzzle and number of access attempts associated with the device fingerprint.
24. The non-transitory computer-readable medium of claim 16, wherein the method further comprises adding a random nonce to the device fingerprint to generate a fingerprint-nonce-message authentication code (fingerprint-nonce-MAC), and the first puzzle is based at least in part on the fingerprint-nonce-MAC.
25. The non-transitory computer-readable medium of claim 16, wherein the method further comprises terminating engagement with the device if tampering is detected.
26. The non-transitory computer-readable medium of claim 16, wherein the method further comprises determining whether the first puzzle is expired, and terminating engagement with the device if the first puzzle is expired.
27. The non-transitory computer-readable medium of claim 16, wherein the method further comprises:
determining whether the solution is valid by computing a hash of the solution and the first puzzle and comparing the number of leading zero bits in the hash with the difficulty level of the first puzzle; and,
terminating engagement with the device if the solution is not valid.
28. The non-transitory computer-readable medium of claim 16, wherein the method further comprises terminating engagement with the device if any verification MAC does not match the corresponding MAC used in computing the TAC.
29. The non-transitory computer-readable medium of claim 16, wherein the method further comprises maintaining engagement with the device if any verification MAC does not match the corresponding MAC.
30. The non-transitory computer-readable medium of claim 16, wherein the method further comprises determining whether the at least one TAC has been used for a previous request for access to the network resource.
31. A dynamic access pricing and active countermeasure system against automated Internet attackers, comprising:
a protected system;
a puzzle-issuer-verifier; and
at least one storage device,
wherein the protected system is configured to receive a request for access to an Internet resource from a device and assign a transaction identifier to the request and the puzzle-issuer-verifier is configured to:
obtain a device fingerprint of the device;
determine a device state of the device;
increment an access attempt counter associated with the device fingerprint if the device is in an initial state or allowed state;
access a dynamic access pricing (DAP) policy associated with the transaction identifier;
provide a puzzle to the device, wherein the device fingerprint is incorporated into the puzzle and the puzzle has a difficulty level based on the DAP policy for at least one of the access attempt counter value and the device state;
receive a solution to the puzzle from the device and perform at least one tamper check on the solution, wherein the at least one tamper check includes at least one of:
computing a tamper check puzzle using a device nonce returned in the solution and the puzzle, and comparing the tamper check puzzle with a full challenge returned in the solution,
comparing the puzzle with a returned puzzle that is returned in the solution, and
computing a verified tamper check puzzle using the device nonce and at least one verified untampered parameter of the solution, and comparing the verified tamper check puzzle with the full challenge;
blacklist the device if two or more different fingerprints submit solutions to the full challenge;
compute at least one transaction authorization code (TAC) based on at least one of: a fingerprint-nonce-Message Authentication Code (MAC), a transaction identification MAC (TMAC), a transaction code validity duration MAC (TXN_EXPIRATION), and a transaction MAC (TXN_MAC);
provide the at least one TAC to the device;
receive an augmented transaction request from the device;
compute at least one verification MAC based on the augmented transaction request for each of the at least one MAC used in computing the at least one TAC; and
compare each of the at least one verification MAC with the corresponding MAC used in computing the TAC.
32. The system of claim 31, wherein the storage device is configured to associate and store the puzzle and a number of access attempts indicated by the access attempt counter associated with the device fingerprint.
33. The system of claim 31, wherein the puzzle-issuer-verifier is further configured to verify the solution.
Patent Citations (22)
| Patent | Date | Inventor | Cited By |
|---|---|---|---|
| US6088804(A) | 2000-07-01 | Hill et al. | Applicant |
| US6738814(B1) | 2004-05-01 | Cox et al. | Applicant |
| US6789203(B1) | 2004-09-01 | Belissent | Applicant |
| US6944663(B2) | 2005-09-01 | Schuba et al. | Applicant |
| US7600255(B1) | 2009-10-01 | Baugher | Applicant |
| US7853533(B2) | 2010-12-01 | Eisen | Applicant |
| US8112483(B1) | 2012-02-01 | Emigh et al. | Applicant |
| US8151327(B2) | 2012-04-01 | Eisen | Applicant |
| US8321955(B2) | 2012-11-01 | Feng et al. | Applicant |
| US2002/0143914(A1) | 2002-10-01 | Cihula | Applicant |
| US2002/0163926(A1) | 2002-11-01 | Moharram | Applicant |
| US2003/0093509(A1) | 2003-05-01 | Li | Examiner |
| US2009/0113559(A1) | 2009-04-01 | Schneider | Applicant |
| US2009/0192853(A1) | 2009-07-01 | Drake et al. | Applicant |
| US2010/0031315(A1) | 2010-02-01 | Feng et al. | Applicant |
| US2010/0180333(A1) | 2010-07-01 | Bono | Examiner |
| US2011/0218860(A1) | 2011-09-01 | Barber | Applicant |
| US2011/0231913(A1) | 2011-09-01 | Feng et al. | Applicant |
| US2012/0189194(A1) | 2012-07-01 | Srivastava | Applicant |
| US2012/0323700(A1) | 2012-12-01 | Aleksandrovich et al. | Applicant |
| US2013/0055374(A1) | 2013-02-01 | Kustarz et al. | Applicant |
| US2013/0312097(A1) | 2013-11-01 | Turnbull | Applicant |
Non-Patent Literature (21)
- Buscher, “Tracking DDoS Attacks: Insights into the business of disrupting the Web”, NATO Cyber Defense Center of Excellence CYCON dated Jun. 2012.Applicant
- International Telecommunications Union (ITU), IT RecommendationX.200, “Data Networks and Open System Communications-Open Systems Interconnection-Model and Notation, Basic Reference Model,” Jul. 1994.Applicant
- Internet Engineering Task Force (IETF), Request for Comments 2616, “Hypertext Transfer Protocol-HTTP/1,1”, Jun. 1999.Applicant
- J. Mirkovic, et al., Internet Denial of Service: Attack and defense Mechanisms, Prentice-Hall, 2008.Applicant
- J. Crowcroft et al., “Lazy Zusan: Dumb waiting as proof of work,” University of Cambridge Technical Report No. 703, Nov. 2007.Applicant
- J. Rangasamy, et al. “An integrate approach to cryptographic mitigation of denial-of-service attacks”, Proceedings of the 6th ACM Symposium on Information, Computer and Communications Security (ASIACCS) 2011.Applicant
- Kurt Gutzmann, “Role-Based Access Control in HTTP Environment”, IEEE Journal of Internet Computing, Jan. 2001.Applicant
- M. Abliz et al., “A Guided Tour Puzzle for Denial of Service Prevention”, Proceedings of the Annual Computer Security Applications Conference, 2009.Applicant
- P. Mittal et al., “Towards Deployable DDoS Defense for Web Application”, Arxiv preprint arXiv:1110-1060, Oct. 5, 2011.Applicant
- V. Laurens et al., “Requirements for Client Puzzles to Defeat the Denial of Service and Distributed Denial of Service Attacks”, The International Arab Journal of Information Technology, vol. 3, No. 4, Oct. 2006.Applicant
- Y. Xie et al., “Monitoring the Application-Layer DDos Attacks for Popular Websites,” IEEE/ACM Transactions Networking, vol. 17, No. 1, Feb. 2009.Applicant
- H. Beitollahi et al., “Tackling Application-layer DDoS Attacks”, Procedia Computer Science; SciVerse ScienceDirect, dated 2012.Applicant
- H. Beitollahi et al., “Analyzing well-known countermeasures against distributed denial of service attacks”, Computer Communications, dated 2012.Applicant
- Y. Chen et al., “A Novel DDoS Attack Defending Framework with Minimized Bilateral Damages”. Dept. of Electrical & Computer Engineering, SUNY—Binghamton, Binghampton NY 13902; Dept. of Computer Science & Software Engineering, Auburn University, Auburn, AL 36849, dated 2010.Applicant
- P. Djalaliev, “Mitigating Botnet-Based DDoS Attacks Against Web Servers”, Submitted to the Graduate Faculty of the Dietrich School of Arts and Sciences—University of Pittsburgh, dated 2013.Applicant
- E. Kaiser, “Addressing Automated Adversaries of Network Applications”, Submitted to the Dissertation Committee—Portland State University, dated 2010.Applicant
- S. Khor, et al. “DaaS: DDoS Mitigation as-a-service”, IEEE/IPSJ International Symposium on Applications and the Internet, dated 2011.Applicant
- P. Vu, “Defending Against Distributed Denial of Service Attacks Using a Cloud Based Architecture”, Thesis—The University of Houston, Clear Lake, Dated Dec. 2012.Applicant
- B. Waters et al., “New Client Puzzle Outsourcing Techniques for DoS Resistance”, Princeton University, Princeton, NJ; RSA Laboratories, Bedford, MA, Oct. 25-29, 2004.Applicant
- S. Zargar et al., “A Survey of Defense Mechanisms Aganist Distributed Denial of Service (DDoS) Flooding Attacks”, IEEE, 2013.Applicant
- K. Gutzmann, “System and Methods for Classifying Internet Devices as Hostile or Benign”, filed Jul. 3, 2014, U.S. Appl. No. 14/323,826.Applicant