Abstract:
A device identification server identifies a “household” to which a particular device belongs by associating the device with a LAN MAC address of the router through which the device connects to a wide area network such as the Internet because the LAN MAC address (i) is unique to the router and (ii) is not readily discoverable by interaction with the router through the wide area network, impeding spoofing by malicious entities. The device queries and receives the LAN MAC address of the router through the local area network. The device passes the LAN MAC address of the router along with its digital fingerprint to the device identification server. Devices that report the same LAN MAC address of the router through which they connect to the wide area network are determined to be from the same “household”, i.e., to be managed by one and the same entity.

Description:
[0001]    This application claims priority to U.S. Provisional Application 61/523,727, which was filed on Aug. 15, 2011, and which is fully incorporated herein by reference. 
     
    
     BACKGROUND OF THE INVENTION 
       [0002]    1. Field of the Invention 
         [0003]    The present invention relates generally to device recognition and, more particularly, methods of and systems for recognizing that multiple remote devices are likely under common control and operation. 
         [0004]    2. Description of the Related Art 
         [0005]    Device fingerprinting (also known as device recognition) is a technology which assigns a unique identifier based on a device&#39;s software and hardware settings. This identification technique is attractive because of its adaptability to any device—even where cookies have failed—including PCs, mobile devices, set top boxes, and game consoles. 
         [0006]    Device fingerprinting is used to improve on-line advertisement targeting, reduce click fraud, personalize website experiences, and enable multi-channel attribution. While device fingerprinting can identify individual devices, there is currently no accurate way to determine that two or more devices are under common control and operation, e.g., of the same household. 
         [0007]    Consider the computer network shown in  FIG. 1 , which depicts a sampling of typical connections of computing devices to a wide area network (WAN), i.e. the Internet cloud. The connections are made possible by an Internet Service Provider (ISP), which assigns an IP address to each subscriber connected to the network, for example, through a DSL or cable modem. The diagram shows that the subscriber at 100 Main Street is assigned the IP address 77.264.195.10, the public library is assigned the IP address 77.264.198.17, the City Hall is assigned IP address 88.157.64.171, and the subscriber at 2505 Wagonwheel Street is assigned IP address 88.157.64.100. Three of these subscribers have configured a local area network (LAN1, LAN2 and LAN3, as shown) through the use of a router. Downstream of each router are the computing devices residing within each respective LAN. Each such device is expected to share the same WAN IP address, but its location will be differentiated from all others according to its LAN IP address. 
         [0008]    A problem arises, however, when attempting to remotely identify devices that belong to the same household, because IP addresses are not static. That is because the entity assigning IP addresses—whether the ISP or the LAN administrator—typically assigns them for a finite period, known as a lease time. Lease time periods typically vary, and may be granted on the order of hours, days, months, or longer, according to the preference of the administrator. Therefore the population of computing devices associated with a particular LAN may share a common WAN IP address on one day, but share another WAN IP address the following day. 
         [0009]    To make matters worse, an ISP may rotate an available pool of WAN IP addresses among its many subscribers, such that computing devices in different households could be accessible through identical WAN IP addresses during different parts of the day. For example, from 8 AM to noon, IP address 77.264.195.10 may be assigned to the LAN 1 subscriber and associated with each of its computing devices, and later that same day from noon to 4 PM the same IP address may be assigned to the LAN 2 subscriber and associate with each of its computing devices. 
         [0010]    The same problem of rotating IP addresses according to lease time expiration can also occur at the LAN level. As in the WAN case, the rules governing assignment of the LAN IP address are typically configurable by the administrator. Although this does not affect the determination whether a particular computing device exists within an identified household, it emphasizes that, due its transience, the LAN IP address is unsuitable for use as an identifier for purposes of reliably fingerprinting a device. 
         [0011]    What is needed is a more reliable way to accurately determine whether two or more devices are under mutual control and operation. 
       SUMMARY OF THE INVENTION 
       [0012]    In accordance with the present invention, a device identification server identifies a “household” to which a particular device belongs by associating the device with data (i) that is unique to the router through which the device connects to a wide area network such as the Internet and (ii) that is not readily discoverable by interaction with the router through the wide area network. Using data that is not readily discoverable by interaction with the router through the wide area network impedes spoofing of such data by malicious entities. 
         [0013]    The primary function of a router is to manage a network boundary, distinguishing between network traffic intended for two or more networks connected to the router. In a typical installation, a router connects to a wide area network and a local area network. Accordingly, a router typically has a local area network interface and a wide area network interface. Details of the wide area network (WAN) interface are generally discoverable by interaction with the router through the wide area network. However, details of the local area network (LAN) interface are generally not so discoverable. A media access control (MAC) address of a given device is unique among all networked devices. The LAN MAC address of the router is usually unique among all LAN MAC addresses of all routers and is not readily discoverable by interaction with the router through the WAN. While a system administrator can manually change the LAN MAC address of a router such that uniqueness of the LAN MAC address is less certain, most leave the LAN MAC address unaltered. In addition, unlike WAN IP addresses, the LAN MAC address of the router is very stable and changes very rarely, if ever. 
         [0014]    The device identification server gains access to the LAN MAC address of the router by cooperation of the device to be identified by the device identification server. In addition to generating and providing a digital fingerprint to the device identification server, the device queries and receives the LAN MAC address of the router through the local area network. The device passes the LAN MAC address of the router along with its digital fingerprint to the device identification server. 
         [0015]    Devices that report the same LAN MAC address of the router through which they connect to the wide area network are determined to be from the same “household”, i.e., to be managed by one and the same entity. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0016]    Other systems, methods, features and advantages of the invention will be or will become apparent to one with skill in the art upon examination of the following figures and detailed description. It is intended that all such additional systems, methods, features and advantages be included within this description, be within the scope of the invention, and be protected by the accompanying claims. Component parts shown in the drawings are not necessarily to scale, and may be exaggerated to better illustrate the important features of the invention. In the drawings, like reference numerals may designate like parts throughout the different views, wherein: 
           [0017]      FIG. 1  is a block diagram showing a sampling of LAN configurations connected to a WAN, such as the Internet, in a typical system configuration. 
           [0018]      FIG. 2  is a diagram showing a number of devices coupled through routers to a wide area network and therethrough to a device identifier server in accordance with one embodiment of the present invention. 
           [0019]      FIG. 3  is a block diagram showing the routers of  FIG. 2  in greater detail. 
           [0020]      FIG. 4  is a transaction diagram illustrating one embodiment according to the invention of a method by which the device identification server computer of  FIG. 2  identifies a household of a particular device in accordance with an embodiment of the present invention. 
           [0021]      FIG. 5  is a block diagram showing a personal computing device of  FIG. 2  in greater detail. 
           [0022]      FIG. 6  is a block diagram showing the device identifier server of  FIG. 2  in greater detail. 
           [0023]      FIG. 7  is a block diagram of a device identification data record managed by the device identification server of  FIG. 6  in greater detail. 
       
    
    
     DETAILED DESCRIPTION 
       [0024]    In accordance with the present invention, a device identification server  250  ( FIG. 2 ) associates a LAN MAC address of a router  230  with digital fingerprints of devices  202 - 206  that communicate with device identification server  250  through router  230 . Devices whose digital fingerprints are associated with the same router LAN MAC address are presumed to be under common control and operation, i.e., constituents of the same household. 
         [0025]    As used herein, “household” does not necessarily infer a residential locale. Instead, “household” refers to constituent devices of a private network connected to wide area network (WAN)  240  (which is the Internet in this illustrative embodiment). Local area network (LAN)  220  is an example of such a private network, being connected to WAN  240  through router  230 . Many homes in which families have multiple devices accessing the Internet do so through a router and a LAN. Other establishments do so as well, such as businesses, libraries, government agencies, non-profit organizations, etc. In some cases, an unsecured router may, intentionally or unintentionally, be available for limited public access by transient computing devices that happen to come within wireless reception range of the router. According to the invention described herein, such transient devices are considered constituent devices of the LAN, and such a network is recognized herein as being a private network. All transient and non-transient computing devices accessing the LAN through a common router are members of the same household. 
         [0026]    As shown in  FIG. 3 , router  230  includes a LAN interface  302  and a WAN interface  312 , each of which can be Ethernet networking circuitry. Similarly, router  232  includes a LAN interface  322  and a WAN interface  332 , each of which can also be Ethernet networking circuitry. As shown in  FIG. 2 , LAN  220  connects router  230  with multiple devices  202 - 206 . Three such devices  202 - 206  are shown for illustration only, and may represent many more devices that in practice may exist within the same household. LAN  220  is typically under the control of a single entity, such as a family or a business. While LAN  220  is shown as a single network, it should be appreciated that LAN  220  can include multiple local area networks, all of which directly or indirectly access WAN  240  through router  230 . LAN  222  connects router  232  with multiple devices  208 - 212  in similar fashion. 
         [0027]    A number of IP addresses are reserved for private use and are not permitted to be used in WAN  240 , which is the Internet in this illustrative embodiment. Configuration of router  230  includes specifying addresses, e.g., private IP addresses, that are considered within LAN  220 . Accordingly, router  230  can distinguish between addresses within LAN  220  and addresses that should be routed through WAN  240 . 
         [0028]    Each of interfaces  302 ,  312 ,  322  and  332  ( FIG. 3 ) includes a MAC (Media Access Control) address and an IP (Internet Protocol) address. In particular, WAN interface  312  includes a WAN MAC address  314  and a WAN IP address  316 . WAN interface  332  includes a WAN MAC address  334  and a WAN IP address  336 . WAN MAC address  314  should be unique to router  230  throughout WAN  240 , and WAN MAC address  334  should be unique to router  232  throughout WAN  240 . However, most routers allow the system administrator to manually set the WAN MAC address and WAN MAC addresses are discoverable through WAN  240 . Accordingly, spoofing of another router&#39;s WAN MAC address is easy. 
         [0029]    WAN IP address  316  is unique to router  230  at any given time; however, WAN IP address  316  can change over time, making use of WAN IP address  316  alone a determining identifier of router  230  and the household behind it (i.e., the household of LAN  120 ) difficult and transitory. With similar limitations, WAN IP address  336  is unique to router  232  at any given time. 
         [0030]    LAN interface  302  includes a LAN MAC address  304  and a LAN IP address  306 . LAN interface  322  includes a LAN MAC address  324  and a LAN IP address  326 . LAN MAC addresses  304 ,  324  and LAN IP addresses  306 ,  326  have the advantage of not being discoverable through WAN  240 . Accordingly, spoofing LAN MAC addresses and LAN IP addresses is particularly difficult. In addition, access to LAN MAC addresses and LAN IP addresses by device identifier server  250  is not straightforward. 
         [0031]    LAN IP address  306  is unique to router  230  only within LAN  220 . Similarly, LAN IP address  326  is unique to router  232  only within LAN  222 . For example, the system administrator of router  232  can use the same private IP addresses for LAN  222  that the administrator of router  230  uses for LAN  220 . Router  232  can even have exactly the same LAN IP address as router  230 . 
         [0032]    However, LAN MAC address  304  should be unique to router  230  throughout all MAC addresses of devices of WAN  240  and of other LANs such as LAN  222 . Since LAN MAC address  304  is likely unique throughout all the Internet including LANs and is generally not publicly discoverable, device identification server  250  uses LAN MAC address  304 , in combination with WAN IP address  316 , to uniquely identify a household to which each of devices  202 - 206  belong. 
         [0033]    Similarly, LAN MAC address  324  should be unique to router  232  throughout all MAC addresses of devices of WAN  240  and of other LANs such as LAN  220 . Since LAN MAC address  324  is likely unique throughout all the Internet including LANs and is generally not publicly discoverable, device identification server  250  uses LAN MAC address  324 , in combination with WAN IP address  336 , to uniquely identify a household to which each of devices  208 - 212  belong. 
         [0034]    Since LAN MAC addresses can be manually set, neither LAN MAC address  304 ,  324  is absolutely guaranteed to be unique among all LAN MAC addresses of all routers connected to WAN  240 . However, while neither of the respective WAN IP addresses  316 ,  336  may remain constant, they each tend to be selected from a relatively small range of IP addresses. Accordingly, the combination of LAN MAC address  304  and WAN IP address  316 , and the combination of LAN MAC address  324  and WAN IP address  336 , each has a very high probability of uniquely identifying its associated router  230 ,  232  (respectively) among all routers connected to WAN  240 . LAN MAC address  304  or  324  is highly likely to be unique since few system administrators change LAN MAC addresses of routers and can therefore be a useful identifier of the router itself. 
         [0035]    For simplicity hereafter, the householding processes of the invention are described only with reference to router  230  and devices within LAN  220 . The description applies analogously to any other router communicating through WAN  240 . 
         [0036]    The manner in which device identifier server  250  obtains a LAN MAC address  304  of router  230  is illustrated by the transaction flow diagram  400  ( FIG. 4 ). Device identifier server  250  includes device identification logic  620  ( FIG. 6 ) that controls behavior of device identifier server  250  in identifying devices in the manner described herein. Device identifier server  250  is described in greater detail below. 
         [0037]    Device identification logic  620  sends a request for a digital fingerprint to device  204  ( FIG. 2 ) in step  402  ( FIG. 4 ). While device  204  is described herein as the illustrative example, each of devices  202 - 212  ( FIG. 2 ) can be configured to act in the manner described herein with respect to device  204 . 
         [0038]    Device  204  includes digital fingerprint generation logic  520  ( FIG. 5 ) that controls behavior of device  204  in response to the digital fingerprint request of step  402  ( FIG. 4 ). In step  404 , digital fingerprint generation logic  520  requests and receives LAN MAC address  304  ( FIG. 3 ) from router  230 . 
         [0039]    Most devices have an Address Resolution Protocol (ARP) table that includes known LAN IP addresses and associated LAN MAC addresses of all devices connected to the local area network, e.g., LAN  220  in this illustrative example. In addition, each device implementing the Internet Protocol has an IP address designated as a gateway IP address. All communications to an IP address other than the known IP addresses of the ARP table are forward to this gateway IP address. The device at the gateway IP address is responsible for redirecting communications to the intended recipient. In essence, the device of the gateway IP address is a router, regardless of whether the device is a dedicated router device or a computer configured to act as a router. Accordingly, each device connected to LAN  220  has LAN IP address  306  ( FIG. 3 ) of router  230  as the gateway IP address. The gateway IP address (e.g., LAN IP address  306  of router  230 ) is associated with LAN MAC address  304  within the ARP table of device  204 . 
         [0040]    Thus, device  204  receives LAN MAC address  304  during network configuration and stores LAN MAC address  304  in the networking logic inherent in the operating system of device  204 . Alternatively, device  204  can query router  230  directly for its LAN MAC address  304  as needed. 
         [0041]    In step  406  ( FIG. 4 ), digital fingerprint generation logic  520  ( FIG. 5 ) generates digital fingerprint  522 . Digital fingerprints are known and are described, e.g., in U.S. Pat. No. 5,490,216 (sometimes referred to herein as the &#39;216 patent), and in U.S. Patent Application Publications 2007/0143073, 2007/0126550, 2011/0093920, and 2011/0093701, the descriptions of which are fully incorporated herein by reference. 
         [0042]    In step  408  ( FIG. 4 ), digital fingerprint generation logic  520  sends digital fingerprint  522  and LAN MAC address  304 , retrieved in step  404 , to device identification logic  620  of device identification server  250 . The digital fingerprint  522  and LAN MAC address  304  pass through router  230  from device  204  to device identification server  250 , and WAN IP address  316  of router  230  is therefore available to device identification server  250 . 
         [0043]    In step  410  ( FIG. 4 ), device identification logic  620  associates the digital fingerprint received in step  408  with the LAN MAC address and WAN IP address received in step  408 . In another embodiment, during step  408 , digital fingerprint generation logic  520  may include the LAN MAC address as an input to the digital fingerprint  522 , such that it is concatenated, hashed, encrypted, or otherwise combined with other inputs to the fingerprinting algorithm in a manner that allows it to be recovered from the digital fingerprint  522  in step  410  by the device identification logic  620 . 
         [0044]    Device  204  is a computing device such as a smart-phone or personal computer and is shown in greater detail in  FIG. 5 . It should be appreciated that each of devices  202 - 212  is a computing device that is directly analogous to device  204 . Unless otherwise noted herein, the following description of device  204  is equally applicable to others of devices  202 - 212 . 
         [0045]    Device  204  includes one or more microprocessors  502  (collectively referred to as CPU  502 ) that retrieve data and/or instructions from memory  504  and execute retrieved instructions in a conventional manner. Memory  504  can include generally any computer-readable medium, for example, persistent memory such as magnetic and/or optical disks, ROM, and PROM and volatile memory such as RAM. 
         [0046]    CPU  502  and memory  504  are connected to one another through a conventional interconnect  506 , which is a bus in this illustrative embodiment and which connects CPU  502  and memory  504  to one or more input devices  508 , output devices  510 , and network access circuitry  512 . Input devices  508  can include, for example, a keyboard, a keypad, a touch-sensitive screen, a mouse, a microphone, and one or more cameras. Output devices  510  can include, for example, a display—such as a liquid crystal display (LCD)—and one or more loudspeakers. Network access circuitry  512  sends and receives data through computer networks such as LAN  220  ( FIG. 2 ), for example. 
         [0047]    A number of components of device  204  are stored in memory  504 . In particular, digital fingerprint generation logic  520  is all or part of one or more computer processes executing within CPU  502  from memory  504  in this illustrative embodiment but can also be implemented using digital logic circuitry. As used herein, “logic” refers to (i) logic implemented as computer instructions and/or data within one or more computer processes and/or (ii) logic implemented in electronic circuitry. Digital fingerprint  522  is data stored persistently in memory  504 . 
         [0048]    Device identification server  250  is a trusted server that can verify identity of a particular device and a household to which that particular device belongs and is shown in greater detail in  FIG. 6 . Device identification server  250  includes one or more microprocessors  602  (collectively referred to as CPU  602 ), an interconnect  606 , input devices  608 , output devices  610 , network access circuitry  612  that are directly analogous to CPU  502  ( FIG. 5 ), an interconnect  506 , input devices  508 , output devices  510 , network access circuitry  512 , respectively. As device identification server  250  ( FIG. 6 ) is a server computer, input devices  608  and output devices  610  can be omitted. 
         [0049]    A number of components of device identification server  212  are stored in memory  604 . In particular, device identification logic  620  is all or part of one or more computer processes executing within CPU  602  from memory  604  in this illustrative embodiment but can also be implemented using digital logic circuitry. Device identification data  624  is data stored persistently in memory  404 . In this illustrative embodiment, device identification data  624  is organized as one or more databases. 
         [0050]    Device identification data  624  includes a number of device identification data records such as device identification data record  700  ( FIG. 7 ). In this illustrative example, device identification data record  700  represents device  204  ( FIG. 2 ). Device identification data record  700  ( FIG. 7 ) includes a digital fingerprint  702 , which represents digital fingerprint  522  ( FIG. 5 ) of device  204  to thereby identify device  204 , and a household identifier  704  ( FIG. 7 ). In this illustrative embodiment, household identifier  704  represents an association between LAN MAC address  304  ( FIG. 3 ) and WAN IP address  316  of router  230 . 
         [0051]    It should be appreciated that, since devices  202 - 206  ( FIG. 2 ) connect to WAN  240  through router  230 , device identification data record  700  ( FIG. 7 ) for each of those devices will have the same household identifier  704  and therefore will be readily identifiable as being of the same household. Similarly, since devices  208 - 212  ( FIG. 2 ) connect to WAN  240  through router  232 , device identification data record  700  for each of those devices will have the same household identifier  704  and therefore will be readily identifiable as being of the same household. However, any of devices  202 - 206  will have a different household identifier  704  than any of devices  208 - 212 , thereby indicating distinct households. 
         [0052]    In this illustrative embodiment, digital fingerprint generation logic  520 , in step  408 , sends an irreversible, cryptographic hash of LAN MAC address  304  to device identification server  250 . In this way, device identification server  250  never has direct access to LAN MAC address  304  of router  230  but can still uniquely identify router  230  by the hash. Analogous digital fingerprint generation logic in others of devices  202 - 212  use the same hashing method to send irreversible, cryptographic hashes of LAN MAC addresses of routers  230 - 232 . In alternative embodiments, devices  202 - 212  send LAN MAC addresses in clear text and device identification server  250  has direct access to LAN MAC addresses of routers. In either embodiment, it is preferred that secure communications links, e.g., HTTPS transfers, are used to transport LAN MAC addresses to avoid discovery by unauthorized devices of LAN MAC addresses of routers  230 - 232 . 
         [0053]    In yet another embodiment, digital fingerprint  702  and household identifier  704  are inextricably combined, e.g., in an irreversible hash, such that device identification server  250  cannot readily identify devices of the same household. However, in such an embodiment, device identification server  250  identifies device  204  ( FIG. 2 ) as a different device when connected to WAN  240  through different LANs. 
         [0054]    Device identification server  250  can also store household identifier  704  ( FIG. 7 ) separately from digital fingerprint  702  in a many-to-many relationship in a relational database. In addition, WAN IP address  316  ( FIG. 3 ) can change and in fact does in most installations, particularly residential LANs. Accordingly, household identifier  704  ( FIG. 7 ) can change over time in embodiments in which WAN IP address  316  ( FIG. 3 ) is included therein. Device identification server  250  can separate LAN MAC address  304  from WAN IP address  316  such that household identifier  704  ( FIG. 7 ) is a relationship between a single LAN MAC address and one or more devices  202 ,  204 ,  206 . In an alternative embodiment, a household identifier received from a device that differs from a previous household identifier of the same device in WAN IP address only, i.e., has the same LAN MAC address, is determined to supersede the prior household identifier. In yet another embodiment, changes to household identifier  704  ( FIG. 7 ) are treated as a different household and all devices of the household eventually update their household identifier in subsequent performances of the transaction of transaction flow diagram  400  ( FIG. 4 ). 
         [0055]    The above description is illustrative only and is not limiting. The present invention is defined solely by the claims which follow and their full range of equivalents. It is intended that the following appended claims be interpreted as including all such alterations, modifications, permutations, and substitute equivalents as fall within the true spirit and scope of the present invention.