Method and apparatus for trust-based, fine-grained rate limiting of network requests

• US 7,721,329 B2
• Filed: 01/15/2004
• Issued: 05/18/2010
• Est. Priority Date: 11/18/2003
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: AOL Inc. (Apollo Global Management, Inc.)
• Inventors: Toomey, Christopher Newell
• Primary Examiner(s): Moise; Emmanuel L
• Assistant Examiner(s): Khoshnoodi; Nadia
• Application Number:
  US10/759,596
• Publication Number:
  US 20050108551A1
• Time in Patent Office: 2,315 Days
• Field of Search: None
• US Class Current: 726/9
• CPC Class Codes: G06F 21/31 User authentication
• CPC Class Codes: G06F 21/33 using certificates
• CPC Class Codes: H04L 2209/42 Anonymization, e.g. involving pseudonyms
• CPC Class Codes: H04L 2209/76 Proxy, i.e. using intermediary entity to perform cryptographic operations
• CPC Class Codes: H04L 2209/80 Wireless
• CPC Class Codes: H04L 63/08 for authentication of entities cryptographic mechanisms or cryptographic arrangements for entity authentication H04L9/32
• CPC Class Codes: H04L 63/123 received data contents, e.g. message integrity
• CPC Class Codes: H04L 63/126 the source of the received data
• CPC Class Codes: H04L 63/1458 Denial of Service
• CPC Class Codes: H04L 9/002 Countermeasures against attacks on cryptographic mechanisms network architectures or network communication protocols for protection against malicious traffic H04L63/1441
• CPC Class Codes: H04L 9/3234 involving additional secure or trusted devices, e.g. TPM, smartcard, USB or software token network architectures or network communication protocols for supporting authentication of entities using an additional device in a packet data network H04L63/0853
• CPC Class Codes: H04L 9/3297 involving time stamps, e.g. generation of time stamps

Abstract

A method and apparatus for fine-grained, trust-based rate limiting of network requests distinguishes trusted network traffic from untrusted network traffic at the granularity of an individual user/machine combination, so that network traffic policing measures are readily implemented against untrusted and potentially hostile traffic without compromising service to trusted users. A server establishes a user/client pair as trusted by issuing a trust token to the client when successfully authenticating to the server for the first time. Subsequently, the client provides the trust token at login. At the server, rate policies apportion bandwidth according to type of traffic: network requests that include a valid trust token are granted highest priority. Rate policies further specify bandwidth restrictions imposed for untrusted network traffic. This scheme enables the server to throttle untrusted password-guessing requests from crackers without penalizing most friendly logins and only slightly penalizing the relatively few untrusted friendly logins.

Claims

1. A method of limiting unauthorized network requests, comprising the steps of:

identifying entities legitimately entitled to service, wherein an entity comprises a user id-client pair, said user id-client pair comprising an individual user-machine combination;

establishing said identified entities as trusted entities by, during a first session, issuing a trust token for each entity successfully authenticating to said network service, said trust token comprising a data object that includes a client identifier, said client identifier comprising at least one client-originated item of data that uniquely identifies the client machine, wherein said user ID-client pair represents a unique entity;

storing said issued trust token on said client machine;

in sessions subsequent to said first session, transmitting with a network request from a trusted entity said stored issued trust token along with said user ID, authentication credentials, and client identifier from said client machine to said network service;

processing said request from said trusted entity according to a first policy; and

responsive to a determination that a request is from an untrusted entity, said untrusted entity comprising an entity lacking a valid trust token;

processing said request from said untrusted entity according to at least a second policy;

wherein processing a request according to at least a second policy comprises adding a specified amount of incremental response latency when processing requests from untrusted entities.

2. The method of claim 1, wherein entities legitimately entitled to service comprise entities previously able to successfully authenticate to a network service.

3. The method of claim 2, wherein said network service comprises a server.

4. The method of claim 1, said data object including:

said user ID or a derivative thereof.

5. The method of claim 4, wherein said derivative comprises a cryptographic hash of the user ID.

6. The method of claim 4, wherein said data object further includes any of:

a time stamp of first authentication to said network service by said entity; and

a time stamp of a most recent authentication to said network service by said entity.

7. The method of claim 1, said client identifier comprising any of:

a client identifier assigned by said network service; and

a client identifier provided by the client.

8. The method of claim 7, further comprising a step of storing said issued trust token in a server side database, indexed according to a combination of user ID and client identifier.

9. The method of claim 8, further comprising the step of:

transmitting said client identifier assigned by said network service from said network service to said client upon successful authentication to said network service by said entity.

10. The method of claim 9, wherein said step of transmitting said client identifier assigned by said network service occurs via a secure channel.

11. The method of claim 9, said secure channel comprising a network connection secured via the SSL (secure sockets layer) protocol.

12. The method of claim 8, further comprising the steps of:

transmitting said user ID and client identifier to said server; and

retrieving said stored trust token from said database.

13. The method of claim 8, wherein said server side database serves a plurality of services.

14. The method of claim 1, further comprising a step of encrypting said trust token.

15. The method of claim 14, further comprising the step of:

transmitting said trust token from said network service to said client upon successful authentication to said network service by said entity.

16. The method of claim 15, wherein said step of transmitting said trust token occurs via a secure channel.

17. The method of claim 16, wherein said secure channel comprises a network connection secured via the SSL (secure sockets layer) protocol.

18. The method of claim 1, wherein said step of transmitting said stored, issued trust token occurs via a secured channel.

19. The method of claim 18, wherein said secured channel comprises a network connection secured via the SSL (secure sockets layer) protocol.

20. The method of claim 1, wherein processing requests from said trusted entities according to a first policy comprises the steps of:

validating said trust token; and

processing request without adding incremental response latency.

21. The method of claim 20, wherein said step of validating said trust token comprises the step of:

verifying that the user ID and a client identifier in the trust token match those presented by the client on the request.

22. The method of claim 21, wherein said step of validating said trust token further comprises any of the steps of:

verifying that a time stamp of a first authentication by the entity recorded in the trust token is no earlier than a specified earliest acceptable first-authentication time stamp; and

verifying that a time stamp of a last authentication by the entity recorded in the trust token is no earlier than a specified earliest acceptable last-authentication time stamp.

23. The method of claim 1, wherein response latency is added to a specified percentage of successful untrusted logins.

24. The method of claim 1, wherein processing remaining requests according to at least a second policy comprises adding a specified amount of incremental response latency when processing requests from untrusted IP addresses that have exceeded a configurable login rate.

25. The method of claim 1, wherein processing remaining requests according to at least a second policy comprises requiring an untrusted entity to complete a Turing test.

26. The method of claim 1, wherein said policies are applied by a server.

27. The method of claim 26, wherein said server applies rate policies for a plurality of network devices.

28. The method of claim 1, further comprising the step of:

updating said trust token after a login by a trusted entity.

29. A computer program product comprising computer readable code means embodied on a tangible medium, said computer readable code means comprising code for performing a method of limiting unauthorized network requests, said method comprising the steps of:

identifying entities legitimately entitled to service, wherein an entity comprises a user id-client pair, said user id-client pair comprising an individual user-machine combination;

establishing said identified entities as trusted entities by, during a first session, issuing a trust token for each entity successfully authenticating to said network service, said trust token comprising a data object that includes a client identifier, said client identifier comprising at least one client-originated item of data that uniquely identifies the client machine, wherein said user ID-client pair represents a unique entity;

storing said issued trust token on said client machine;

in sessions subsequent to said first session, transmitting with a network request from a trusted entity said stored issued trust token along with said user ID, authentication credentials, and client identifier from said client machine to said network service;

processing said request from said trusted entity according to a first policy; and

responsive to a determination that a request is from an untrusted entity, said untrusted entity comprising an entity lacking a valid trust token;

processing said request from said untrusted entity according to at least a second policy;

wherein processing a request according to at least a second policy comprises adding a specified amount of incremental response latency when processing requests from untrusted entities.

30. The method of claim 29, wherein entities legitimately entitled to service comprise entities able to successfully authenticate to a network service.

31. The method of claim 30, wherein said network service comprises a server.

32. The method of claim 29, said data object including:

said user ID or a derivative thereof.

33. The method of claim 32, wherein said derivative comprises a cryptographic hash of the user ID.

34. The method of claim 32, wherein said data object further includes any of:

a time stamp of first authentication to said network service by said entity; and

a time stamp of a most recent authentication to said network service by said entity.

35. The method of claim 32, further comprising the step of:

encrypting said trust token.

36. The method of claim 35, further comprising a step of:

transmitting said trust token from said network service to said client upon successful authentication to said network service by said entity.

37. The method of claim 36, wherein said the step of:

transmitting said trust token occurs via a secure channel.

38. The method of claim 37, wherein said secure channel comprises a network connection secured via the SSL (secure sockets layer) protocol.

39. The method of claim 35, further comprising the step of:

storing said issued trust token in a server side database, indexed according to a combination of user ID and client identifier.

40. The method of claim 39, further comprising the step of:

transmitting said client identifier assigned by said network service from said network service to said client upon successful authentication to said network service by said entity.

41. The method of claim 40, wherein said step of transmitting said client identifier assigned by said network service occurs via a secure channel.

42. The method of claim 40, said secure channel comprising a network connection secured via the SSL (secure sockets layer) protocol.

43. The method of claim 39, further comprising the steps of:

transmitting said useriD and client identifier to said server; and

retrieving said stored trust token from said database.

44. The method of claim 39, wherein said server side database serves a plurality of services.

45. The method of claim 29, said client identifier comprising any of:

a client identifier assigned by said network service; and

a client identifier provided by the client.

46. The method of claim 29, wherein said step of transmitting said stored, issued trust token occurs via a secured channel.

47. The method of claim 46, wherein said secured channel comprises a network connection secured via the SSL (secure sockets layer) protocol.

48. The method of claim 29, wherein processing requests from said trusted entities according to a first policy comprises the steps of:

validating said trust token; and

processing without adding incremental response latency.

49. The method of claim 48, wherein said step of validating said trust token comprises the step of:

verifying that the user ID and a client identifier in the trust token match those presented by the client on the request.

50. The method of claim 49, wherein said step of validating said trust token further comprises any of the steps of:

verifying that a time stamp of a first authentication by the entity recorded in the trust token is no earlier than a specified earliest acceptable first-authentication time stamp; and

verifying that a time stamp of a last authentication by the entity recorded in the trust token is no earlier than a configurable earliest acceptable last-authentication time stamp.

51. The method of claim 29, wherein response latency is added to a specified percentage of successful logins.

52. The method of claim 29, wherein processing remaining requests according to at least a second policy comprises adding a specified amount of incremental response latency when processing requests from IP addresses that have exceeded a configurable login rate.

53. The method of claim 29, wherein processing remaining requests according to at least a second policy comprises requiring an untrusted entity to complete a Turing test.

54. The method of claim 29, wherein said policies are applied by a server.

55. The method of claim 54, wherein said server applies rate policies for a plurality of network devices.

56. The method of claim 29, further comprising the step of:

updating said trust token after a login by a trusted entity.