Method for detecting hosts behind network address translators

• US 8,037,167 B1
• Filed: 12/24/2002
• Issued: 10/11/2011
• Est. Priority Date: 12/24/2002
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property II LP (AT&T, Inc.)
• Inventors: Bellovin, Steven Michael
• Primary Examiner(s): Chea; Philip
• Assistant Examiner(s): Nash; Lashanya
• Application Number:
  US10/329,145
• Time in Patent Office: 3,213 Days
• Field of Search: 709223-227, 370/300, 370/474
• US Class Current: 709/224
• CPC Class Codes: H04L 43/045 for graphical visualisation of monitoring data
• CPC Class Codes: H04L 43/065 related to network devices
• CPC Class Codes: H04L 43/0888 Throughput
• CPC Class Codes: H04L 61/2514 between local and global IP addresses

Abstract

The present invention is a method and apparatus for counting the number of active hosts behind network address translation boxes. The technique is based on the observation that on many operating systems, the IP header'"'"'s ID field is a simple counter. By suitable processing of trace data, packets emanating from individual machines can be isolated, and the number of machines determined.

Claims

1. A method for counting hosts behind a network address translator in a network using a network device that is not behind the network address translator and using a protocol defining packets with identifiers, comprising:

reading a plurality of the identifiers that each include an internet protocol identification field read from an internet protocol header of a packet of a plurality of the packets transmitted from the network address translator, wherein the internet protocol identification field is adapted for fragment reassembly and is not an address;

forming a plurality of subsets of the packets based on the identifiers;

automatically adding packets having an internet protocol identification value of zero to a nonmatching subset selected from the plurality of subsets of the packets;

counting the plurality of subsets of the packets to determine a count of the plurality of subsets of the packets, wherein the plurality of subsets of the packets includes the nonmatching subset; and

reporting a determined count of the hosts behind the network address translator, wherein the determined count of the hosts is the count of the plurality of subsets of packets.

2. The method of claim 1, wherein the identifiers comprise values in identification fields of packet headers.

3. The method of claim 2, wherein the plurality of subsets comprise the packets containing sequential series of identification field values.

4. The method of claim 3, wherein each sequential series of identification field values contains gaps no greater than a predetermined maximum.

5. The method of claim 1, further comprising forming byte-swapped subsets of the plurality of the identifiers, each byte-swapped subset comprising a sequential series of byte-swapped values of the identifiers, and wherein counting includes counting the byte-swapped subsets of identifiers.

6. The method of claim 1, wherein the identifiers include, for each packet, at least one identifier indicative of a connection.

7. The method of claim 6, wherein the at least one identifier indicative of the connection comprises image file references in content of the packets.

8. The method of claim 6, wherein the connection is a transmission control protocol connection and the at least one identifier indicative of the connection comprises contents of packet header fields selected from the group consisting essentially of source host, source port, destination host, and destination port.

9. The method of claim 6, wherein the connection is a real-time transport protocol connection and the at least one identifier indicative of the connection comprises contents of packet header fields selected from the group consisting essentially of source machine identifier, sequence number, and timestamp.

10. The method of claim 6, wherein the forming the plurality of subsets includes:

forming groups of the packets according to the at least one identifier indicative of the connection; and

forming the plurality of subsets by linking the groups of the packets according to contents of the internet protocol identification field.

11. The method of claim 10, further comprising:

determining a pattern of identification field contents in the packets within a group; and

wherein the groups are linked according to the pattern of identification field contents.

12. The method of claim 11, wherein the pattern of identification field contents is a byte swapped sequence.

13. The method of claim 11, wherein the pattern of identification field contents is determined using cryptanalysis.

14. The method of claim 1, further comprising:

maintaining a first collection of sequences for normally-incremented internet protocol identification fields; and

maintaining a second collection of sequences for byte-swapped internet protocol identification fields.

15. The method of claim 1, wherein the identifiers are not a source host, source port, destination host, or destination port.

16. The method of claim 1, wherein the identifiers are internet protocol identifiers as defined in RFC 703.

17. The method of claim 1, wherein the identifiers are sequenced modulo 2¹⁶.

18. The method of claim 1, further comprising:

determining that a second identifier of the plurality of identifiers is exactly one higher than a first identifier of the plurality of identifiers via modulo 2¹⁶ sequencing.

19. The method of claim 1, further comprising:

maintaining a first collection of sequences for normally-incremented internet protocol identification fields;

maintaining a second collection of sequences for byte-swapped internet protocol identification fields;

determining whether or not a source machine of the packets uses byte-swapping; and

matching a new received packet against both the first collection and the second collection and only if no match is detected, forming a new subset.

20. The method of claim 1, further comprising:

detecting that values of the internet protocol identification field are randomized.

21. A method for determining a number of hosts behind a network address translator in a network using a network device that is not behind the network address translator and using a packet protocol defining a header with an identification string, comprising:

reading an identification string from a packet header of a packet transmitted from the network address translator, wherein the identification string is an internet protocol identification field, which is not an address and is adapted for fragment reassembly;

comparing the identification string with at least one series of identification strings formed from a plurality of previously read identification strings;

if the identification string matches one of the at least one series of identification strings, adding the identification string to the at least one series of identification strings, otherwise, starting a new series with the identification string;

automatically adding packets having an internet protocol identification value of zero to a nonmatching series selected from the at least one series of identification strings;

counting the at least one series of identification strings to determine a count of the at least one series of identification strings, wherein the count of the at least one series of identification strings is the number of hosts behind the network address translator, wherein the at least one series of identification strings includes the nonmatching series; and

reporting the number of hosts behind the network address translator.

22. The method of claim 21, wherein the series of identification strings contain identification strings with values that are consecutive.

23. The method of claim 21, wherein the comparing step includes:

checking whether the identification string is more than a predetermined time limit older or newer than a last read identification string in a series; and

if so, deeming the identification string not to match that series.

24. The method of claim 21, further comprising automatically dropping discovery packets.

25. The method of claim 21, further comprising coalescing at least one pair of identification string series having endpoints that are within a predetermined value of each other.

26. The method of claim 25, wherein coalescing the series of identification strings is performed only on pairs of identification string series that further have endpoints that are within a predetermined time limit of each other.

27. The method of claim 21, further comprising discarding series of identification strings having a number of identification strings lower than a predetermined minimum.

28. The method of claim 21, further comprising comparing the identification string with at least one series of byte-swapped identification strings formed from byteswapped values of the plurality of previously read identification strings.

29. The method of claim 21, wherein the identification string is added to more than one series if the identification string matches each of those series equally well.

30. The method of claim 21, wherein comparing includes:

checking whether the identification string has a value that is more than a predetermined value higher or lower than a value of a last read identification string in the at least one series; and

if so, deeming the identification string not to match the at least one series.

31. The method of claim 21, wherein comparing includes:

checking whether the identification string has a value exactly one higher than a value of a last read identification string in the at least one series, and, if so, deeming the string to match the at least one series; and

, if not,

checking whether the identification string has the value that is within a predetermined value higher or lower than the value of the last read identification string in the at least one series, and, if so, deeming the string to match the at least one series.

32. The method of claim 21, further comprising:

maintaining a first collection of sequences for normally-incremented internet protocol identification fields; and

maintaining a second collection of sequences for byte-swapped internet protocol identification fields.

33. A method for determining a number of hosts behind a network address translator in a network using a network device that is not behind the network address translator and using a packet protocol defining a connection identifier and a header with an internet protocol identification field, comprising:

reading a connection identifier and the internet protocol identification field from a packet transmitted from the network address translator, wherein the internet protocol identification field is adapted for fragment reassembly and is not an address;

based on the connection identifier, placing the packet in a group containing other packets transmitted over a common connection;

based on identification strings of packets, coalescing the group with at least one other group originating from a common host, to form a plurality of series of packets;

automatically adding packets having an internet protocol identification value of zero to a nonmatching series selected from the plurality of series of packets;

counting the plurality of series of packets to determine a count of the plurality of series of packets, wherein the count of the plurality of series of packets is the number of hosts behind the network address translator, wherein the plurality of series of packets includes the nonmatching series; and

reporting the number of hosts behind the network address translator.

34. The method of claim 33, wherein the series comprise packets containing sequential series of identification field values.

35. The method of claim 33, wherein the connection identifier comprises image file references in content of the packets.

36. The method of claim 33, wherein the common connection is a transmission control protocol connection and the connection identifier comprises contents of packet header fields selected from the group consisting essentially of source host, source port, destination host, and destination port.

37. The method of claim 33, wherein the common connection is a real-time transport protocol connection and the connection identifier comprises contents of packet header fields selected from the group consisting essentially of source machine identifier, sequence number, and timestamp.

38. The method of claim 33, further comprising:

determining a pattern of identification field contents in packets within the group; and

wherein groups are coalesced according to the pattern of identification field contents.

39. The method of claim 38, wherein the pattern of identification field contents is determined by determining whether the pattern is a byte swapped sequence.

40. The method of claim 38, wherein the pattern of identification field contents is determined using cryptanalysis.