Method and apparatus for tracing packets in a communications network

• US 7,356,689 B2
• Filed: 07/09/2001
• Issued: 04/08/2008
• Est. Priority Date: 07/09/2001
• Status: Active Grant

• Current Assignee: RPX Corporation
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Cheswick, William R, Burch, Hal Joseph
• Primary Examiner(s): Moazzami; Nasser
• Assistant Examiner(s): Hoffman; Brandon S
• Application Number:
  US09/901,286
• Publication Number:
  US 20030009554A1
• Time in Patent Office: 2,465 Days
• Field of Search: 713/200, 713/201, 709/200, 709/105
• US Class Current: 713/153
• CPC Class Codes: H04L 2463/146 Tracing the source of attacks
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/0894 Packet rate
• CPC Class Codes: H04L 43/50 Testing arrangements
• CPC Class Codes: H04L 63/1458 Denial of Service

Abstract

A method for tracing packets in a communications network directed to tracing a stream of anonymous packets received at a given target host, in order to identify their source, in response, for example, to a Denial-of-Service (“DoS”) attack on the target host. Advantageously, the tracing is performed without reliance on knowledge or cooperation from intervening Internet Service Providers (ISPs) along the path. The method is performed by applying a “burst load” (i.e., a brief but heavy load of transmitted packets) to various elements (i.e., links or routers) in the network and measuring the change in the rate with which the stream of packets arrive at the target. If the rate is substantially altered upon introduction of the burst load, then it may be deduced that the given element is most likely on the path from the source host of the DoS attack to the target host.

Claims

1. A method for tracing a sequence of packets to a potential source thereof within a communications network, the sequence of packets being received at a target host in said communications network at a received packet rate, the method comprising the steps of:

(a) identifying a plurality of network elements comprised in said communications network;

(b) applying a burst load to a selected one of said identified network elements in said communications network;

(c) measuring a change in said received packet rate in response to said application of said burst load to said selected network element;

(d) including said selected network element in a potential path if said change in said received packet rate fails to meet a predetermined criterion; and

(e) repeating steps (b), (c) and (d) on other selected network elements a plural number of times to generate a path leading from said target host to said potential source based on the selected network elements which have been included in said potential path.

2. The method of claim 1 wherein said communications network comprises the Internet.

3. The method of claim 1 wherein each of said selected network elements comprises a network link.

4. The method of claim 3 wherein said step of applying a burst load to said network link comprises transmitting packets to a subnetwork of said communications network to initiate a responsive flow of packets through said network link.

5. The method of claim 4 wherein said transmitted packets are spoofed from an end of said network link closest to said target host.

6. The method of claim 4 wherein said transmitted packets comprise UDP chargen requests.

7. The method of claim 1 wherein each of said selected network elements comprises a network router.

8. The method of claim 1 further comprising the step of generating a map comprising routes from said target host to a plurality of subnetworks of said communications network.

9. The method of claim 1 further comprising the step of eliminating said selected network element from consideration as said potential source of said sequence of packets when said change in said received packet rate meets the predetermined criterion.

10. The method of claim 1 wherein said predetermined criterion comprises a determination of whether said change in said received packet rate is less than a predetermined threshold.

11. The method of claim 9 wherein said step of eliminating said selected network element from consideration also eliminates from consideration one or more subnetworks of said communications network which are connected to said selected network element.

12. The method of claim 1 wherein said sequence of packets comprises a Denial-of-Service attack on said target host.

13. The method of claim 1 wherein said steps of applying said burst load, measuring said changes in said received packet rate, and determining said potential source of said sequence of packets, are executed under the control of an automated algorithm.

14. The method of claim 1 wherein said steps of applying said burst load and determining said potential source of said sequence of packets, are executed under the at least partial control of a human operator.

15. The method of claim 14 further comprising the step of displaying information, said information including data representative of said measured changes in said received packet rate, to said human operator, for use by said human operator in exercising said at least partial control.

16. An apparatus for tracing a sequence of packets to a potential source thereof within a communications network, the sequence of packets being received at a target host in said communications network at a received packet rate, the apparatus comprising:

(a) means for identifying a plurality of network elements comprised in said communications network;

(b) means for applying a burst load to a selected one of said identified network elements in said communications network;

(c) means for measuring changes in said received packet rate in response to said application of said burst load to said selected network elements;

(d) means for including said selected network element in a potential path if said change in said received packet rate fails to meet a predetermined criterion; and

(e) means for repeating an operation of means (b), (c) and (d) on other selected network elements a plural number of times to generate a path leading from said target host to said potential source based on the selected network elements which have been included in said potential path.

17. The apparatus of claim 16 wherein said communications network comprises the Internet.

18. The apparatus of claim 16 wherein each of said selected network elements comprises a network link.

19. The apparatus of claim 18 wherein said means for applying a burst load to said network link comprises means for transmitting packets to a subnetwork of said communications network to initiate a responsive flow of packets through said network link.

20. The apparatus of claim 19 wherein said transmitted packets are spoofed from an end of said network link closest to said target host.

21. The apparatus of claim 19 wherein said transmitted packets comprise UDP chargen requests.

22. The apparatus of claim 16 wherein each of said selected network elements comprises a network router.

23. The apparatus of claim 16 further comprising means for generating a map comprising routes from said target host to a plurality of subnetworks of said communications network.

24. The apparatus of claim 16 further comprising means for eliminating said selected network element from consideration as said potential source of said sequence of packets when said change in said received packet rate meets the predetermined criterion.

25. The apparatus of claim 16 wherein said predetermined criterion comprises a determination of whether said change in said received packet rate is less than a predetermined threshold.

26. The apparatus of claim 24 wherein said means for eliminating said selected network element from consideration also eliminates from consideration one or more subnetworks of said communications network which are connected to said selected network element.

27. The apparatus of claim 16 wherein said sequence of packets comprises a Denial-of-Service attack on said target host.

28. The apparatus of claim 16 wherein said means for applying said burst load, said means for measuring said changes in said received packet rate, and said means for determining said potential source of said sequence of packets, are executed under the control of an automated algorithm.

29. The apparatus of claim 16 wherein said means for applying said burst load and said means for determining said potential source of said sequence of packets are executed under the at least partial control of a human operator.

30. The apparatus of claim 29 further comprising means for displaying information, said information including data representative of said measured changes in said received packet rate, to said human operator, for use by said human operator in exercising said at least partial control.