System and method for identifying devices behind network address translators

Abstract

An apparatus for monitoring a plurality of devices that use a plurality of networks includes a network interface and a processor. The processor is configured to receive, via the network interface, a plurality of packets that were collectively communicated, from the devices, via all of the networks, to aggregate the packets, using at least one field that is included in respective packet headers of the packets, into a plurality of packet aggregations, such that all of the packets in each one of the packet aggregations were collectively communicated from no more than one of the devices, to group the packet aggregations into a plurality of groups, such that there is a one-to-one correspondence between the groups and the devices, in that all of the packets in each of the groups were collectively communicated from a different respective one of the devices, and to generate an output in response thereto.

1 - 32 . (canceled) 
     
     
         33 . Apparatus for monitoring a plurality of devices that use a plurality of networks, the apparatus comprising:
 a network interface; and a processor, configured: to receive, via the network interface, a plurality of packets that were collectively communicated, from the devices, via all of the networks, to aggregate the packets, using at least one field that is included in respective packet headers of the packets, into a plurality of packet aggregations, such that all of the packets in each one of the packet aggregations were collectively communicated from no more than one of the devices, to group the packet aggregations, based on information contained in the packet aggregations, into a plurality of groups, such that there is a one-to-one correspondence between the groups and the devices, in that all of the packets in each of the groups were collectively communicated from a different respective one of the devices, and to generate an output in response to the grouping.   
     
     
         34 . The apparatus according to  claim 33 , wherein at least one of the networks is serviced by a network address translator (NAT). 
     
     
         35 . The apparatus according to  claim 33 , wherein the processor is configured to group the packet aggregations by: for each packet aggregation of the packet aggregations: identifying, in at least one packet of packets belonging to the packet aggregation, at least one device identifier that uniquely identifies the one of the devices from which the packet was communicated, and using the identified device identifier, associating the packet aggregation with the one of the devices from which the packets belonging to the packet aggregation were communicated. 
     
     
         36 . The apparatus according to  claim 35 , wherein the device identifier is selected from the group consisting of: an Internet cookie, an identifier for advertisers (IDFA), an identifier for vendors (IDFV), an Android advertising identifier (AAID), a universally unique identifier (UUID), an international mobile station equipment identity (IMEI), an international mobile subscriber identity (IMSI), and a media access control (MAC) address. 
     
     
         37 . The apparatus according to  claim 35 , wherein the processor is configured to identify the device identifier by decoding the at least one packet belonging to the packet aggregation. 
     
     
         38 . The apparatus according to  claim 33 , wherein the processor is configured to group the packet aggregations by:
 for each packet aggregation of the packet aggregations:   identifying, in at least one packet belonging to the packet aggregation, at least one device identifier, in response to the identified device identifier, calculating a likelihood that the packets belonging to the packet aggregation were communicated from a particular one of the devices, and associating the packet aggregation with the particular one of the devices, with the calculated likelihood.   
     
     
         39 . The apparatus according to  claim 33 , wherein the field is an internet protocol identification (IPID). 
     
     
         40 . The apparatus according to  claim 33 , wherein, in aggregating the packets into the plurality of packet aggregations, the processor is configured to aggregate, into any given packet aggregation of the packet aggregations, any given packet of the packets, in response to at least one of:
 the given packet belonging to the same transmission control protocol (TCP) connection as does a last-received packet of the given packet aggregation, and a TCP timestamp included in the given packet being within an expected offset range from a TCP timestamp included in the last-received packet of the given packet aggregation.   
     
     
         41 . The apparatus according to  claim 40 , wherein the processor is further configured to compute the expected offset range by applying a machine-learned model that computes the expected offset range. 
     
     
         42 . The apparatus according to  claim 41 , wherein the machine-learned model computes the expected offset range by assuming that a rate of increase of the TCP timestamp varies as a function of a time of day. 
     
     
         43 . The apparatus according to  claim 33 , wherein the processor is configured to group the packet aggregations by:
 Identifying respective device-usage characteristics exhibited by the packet aggregations, and based on the device-usage characteristics, grouping the packet aggregations into the plurality of groups.   
     
     
         44 . The apparatus according to  claim 43 , wherein the device-usage characteristics are at least partly based on destination internet protocol (IP) addresses included in the packet aggregations. 
     
     
         45 . The apparatus according to  claim 44 , wherein the processor is configured to group the packet aggregations by:
 computing, for each packet aggregation of the packet aggregations, a characteristic vector, wherein each element of the vector corresponds to a different respective destination IP address, and a value of the element represents a number of times, in the packet aggregation, that a connection was established with the destination IP address, subsequently, reducing a dimensionality of each characteristic vector, and subsequently, grouping any given first one of the packet aggregations with a second one of the packet aggregations, in response to an angle between the characteristic vector of the first one of the packet aggregations and the characteristic vector of the second one of the packet aggregations being less than a threshold.   
     
     
         46 . The apparatus according to  claim 43 , wherein the device-usage characteristics are at least partly based on respective times at which the packets were communicated. 
     
     
         47 . The apparatus according to  claim 43 ,
 wherein the packet aggregations are a second plurality of packet aggregations and the plurality of groups are a second plurality of groups, and   wherein the processor is configured to group the second plurality of packet aggregations into the second plurality of groups, by:   grouping a first plurality of packet aggregations into a first plurality of groups, based on device identifiers identified in the first plurality of packet aggregations,   from the first plurality of groups, learning a rule for grouping packet aggregations based on the device-usage characteristics, and   using the rule, grouping the second plurality of packet aggregations into the second plurality of groups.   
     
     
         48 . A method for monitoring a plurality of devices that use a plurality of networks, the method comprising:
 using at least one field that is included in respective packet headers of a plurality of packets that were collectively communicated from the devices via all of the networks, aggregating the packets into a plurality of packet aggregations, such that all of the packets in each one of the packet aggregations were collectively communicated from no more than one of the devices; based on information contained in the packet aggregations, grouping the packet aggregations into a plurality of groups, such that there is a one-to-one correspondence between the groups and the devices, in that all of the packets in each of the groups were collectively communicated from a different respective one of the devices; and   generating an output in response to the grouping.   
     
     
         49 . The method according to  claim 48 , wherein at least one of the networks is serviced by a network address translator (NAT). 
     
     
         50 . The method according to  claim 48 , wherein grouping the packet aggregations comprises:
 for each packet aggregation of the packet aggregations:   identifying, in at least one packet of packets belonging to the packet aggregation, at least one device identifier that uniquely identifies the one of the devices from which the packet was communicated, and   using the identified device identifier, associating the packet aggregation with the one of the devices from which the packets belonging to the packet aggregation were communicated.   
     
     
         51 . The method according to  claim 50 , wherein the device identifier is selected from the group consisting of: an Internet cookie, an identifier for advertisers (IDFA), an identifier for vendors (IDFV), an Android advertising identifier (AAID), a universally unique identifier (UUID), an international mobile station equipment identity (IMEI), an international mobile subscriber identity (IMSI), and a media access control (MAC) address. 
     
     
         52 . The method according to  claim 50 , wherein identifying the device identifier comprises identifying the device identifier by decoding the at least one packet belonging to the packet aggregation. 
     
     
         53 . The method according to  claim 48 , wherein grouping the packet aggregations comprise:
 for each packet aggregation of the packet aggregations:   identifying, in at least one packet belonging to the packet aggregation, at least one device identifier, in response to the identified device identifier, calculating a likelihood that the packets belonging to the packet aggregation were communicated from a particular one of the devices, and associating the packet aggregation with the particular one of the devices, with the calculated likelihood.   
     
     
         54 . The method according to  claim 48 , wherein the field is an internet protocol identification (IPID). 
     
     
         55 . The method according to  claim 48 , wherein aggregating the packets comprises aggregating, into any given packet aggregation of the packet aggregations, any given packet of the packets, in response to at least one of:
 the given packet belonging to the same transmission control protocol (TCP) connection as does a last-received packet of the given packet aggregation, and   a TCP timestamp included in the given packet being within an expected offset range from a TCP timestamp included in the last-received packet of the given packet aggregation.   
     
     
         56 . The method according to  claim 55 , further comprising computing the expected offset range, by applying a machine-learned model that computes the expected offset range. 
     
     
         57 . The method according to  claim 56 , wherein the machine-learned model computes the expected offset range by assuming that a rate of increase of the TCP timestamp varies as a function of a time of day. 
     
     
         58 . The method according to  claim 48 , wherein grouping the packet aggregations comprises:
 identifying respective device-usage characteristics exhibited by the packet aggregations; and   based on the device-usage characteristics, grouping the packet aggregations into the plurality of groups.   
     
     
         59 . The method according to  claim 58 , wherein the device-usage characteristics are at least partly based on destination internet protocol (IP) addresses included in the packet aggregations. 
     
     
         60 . The method according to  claim 59 , wherein grouping the packet aggregations comprises:
 computing, for each packet aggregation of the packet aggregations, a characteristic vector, wherein each element of the vector corresponds to a different respective destination IP address, and a value of the element represents a number of times, in the packet aggregation, that a connection was established with the destination IP address,   subsequently, reducing a dimensionality of each characteristic vector, and   subsequently, grouping any given first one of the packet aggregations with a second one of the packet aggregations, in response to an angle between the characteristic vector of the first one of the packet aggregations and the characteristic vector of the second one of the packet aggregations being less than a threshold.   
     
     
         61 . The method according to  claim 58 , wherein the device-usage characteristics are at least partly based on respective times at which the packets were communicated. 
     
     
         62 . The method according to  claim 58 ,
 wherein the packet aggregations are a second plurality of packet aggregations and the plurality of groups are a second plurality of groups, and   wherein grouping the second plurality of packet aggregations into the second plurality of groups comprises:   grouping a first plurality of packet aggregations into a first plurality of groups, based on device identifiers identified in the first plurality of packet aggregations, from the first plurality of groups, learning a rule for grouping packet aggregations based on the device-usage characteristics, and using the rule, grouping the second plurality of packet aggregations into the second plurality of groups.   
     
     
         63 . A method for monitoring a plurality of devices that use at least one network that is serviced by a network address translator (NAT), the method comprising:
 using at least one field that is included in respective packet headers of a plurality of packets that were communicated from the devices via the network, aggregating the packets into a plurality of packet aggregations, such that all of the packets in each one of the packet aggregations were collectively communicated from no more than one of the devices;   for each packet aggregation of the packet aggregations: identifying, in at least one packet in the packet aggregation, at least one device identifier that uniquely identifies the one of the devices from which the packet was communicated, and based on the identified device identifier, associating the packet aggregation with the one of the devices; and generating an output in response to the associating.