# Patent

## Title
Detecting network address translation devices in a network based on network traffic logs

## Abstract

Network traffic logs of network traffic to and from host devices connected to a network that were collected over time are accessed. For each host device identified in the logs, a set of network traffic features indicative of whether the host device behaves like a Network Address Translation (NAT) device or an end host device is extracted from the logs for the host device. Each feature has values that vary over time based on the logs. A trained host device behavior classifier classifies the host device as either a NAT device or an end host device based on one or more of the feature values.

## Background
TECHNICAL FIELD
The present disclosure relates to detecting network address translation (NAT) devices in a network.
BACKGROUND
Network Address Translation (NAT) involves translating between Internet Protocol (IP) address spaces in a communication network so as to overcome a deficit of IP addresses for other devices connected to the network, provide anonymity, filter content, monitor network performance and/or share connectivity with the other devices in the network. Unauthorized NAT devices or NAT software in the network represent a significant network security threat because they may provide unrestricted access to the other network-connected devices or data. Wireless NATs (e.g., Wi-Fi® NAT devices) pose a particular security risk because they may allow unauthorized access to the network from considerable distances without wired connections. It is also important for network behavior analysis systems to be able to detect NAT devices. Accordingly, detecting and distinguishing between unauthorized and authorized NAT devices and NAT software is important for purposes of network security and behavior analysis.



BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a block diagram of a network environment in which embodiments used to detect Network Address Translation (NAT) devices may be implemented, according to an example embodiment.
FIG. 2 is an illustration of a high-level block diagram of a system to detect NAT devices, according to an example embodiment.
FIG. 3 is a flowchart of a method of detecting NAT devices, according to an example embodiment.
FIG. 4 is an illustration of example Hypertext Transfer Protocol (HTTP) logs from which information used to detect NAT devices may be extracted, according to an example embodiment.
FIG. 5 is an example table of host device behavioral features and their respective feature values extracted from HTTP logs, according to an example embodiment.
FIG. 6 is a plot that represents the number of flows or network transactions for a given host device per time window, according to an example embodiment.
FIG. 7 is a plot that shows the number of flows per time window taken from the plot of FIG. 6 sorted from lowest to highest quantile values across the time windows, according to an example embodiment.
FIG. 8 is a flowchart of a method of training a classifier based on information derived from HTTP logs to transition the classifier from an untrained state to a trained state so that the classifier may be used to classify between a NAT device and an end host device (i.e., a non-NAT device), according to an embodiment.
FIG. 9 is a block diagram of a computer system configured to perform the methods presented herein, according to an embodiment.



DESCRIPTION OF EXAMPLE EMBODIMENTS
Overview
Network traffic logs are collected over time for network traffic to and from host devices connected to a network. For each host device identified in the network traffic logs, multiple network traffic features are extracted which are indicative of whether the host device behaves like a Network Address Translation (NAT) device or an end host device, where each feature has values that vary over time. The host device is classified, using a classifier processor trained based on known network traffic, as either a NAT device or an end host device (i.e., a non-NAT device) based on one or more of the feature values for each of the multiple features.
Example Embodiments
Referring first to FIG. 1, there is shown a block diagram of an example network environment 100 in which embodiments used to detect Network Address Translation (NAT) devices may be implemented. Network environment 100 includes a first communication network 102 such as one or more local area networks (LANs), virtual LANs (VLANs), and virtual extended LANs (VxLANs) to communicate with a second communication network 104, which may include a wide area network (WAN) such as the Internet in addition to one or more LANs. Network 102 includes a firewall 106 connected with a proxy server device 108 (referred to simply as a “proxy server” 108) to serve as a focal point for network traffic to/from network 102 from/to network 104 through the firewall. Network 102 also includes a network switch 110 and a NAT enabled router 112 (referred to as a “NAT device” 112) both connected to proxy server 108.
Network 102 also includes host devices A and B connected with network switch 110 and host devices C, D, and E connected with NAT device 112. Host devices A-E may include server devices and/or client devices that execute applications and provide access to network 102 for users of the host devices A-E. Host devices A-E are each referred to as an “end” host device for reasons that will become apparent from the description below. Network traffic, e.g., Internet Protocol (IP) packets, to/from host devices A-E circulate within network 102 and pass to and from network 104 via network switch 110, NAT device 112, and proxy server 108. One or more intruder devices 120 may attempt an unauthorized access into network 102 through NAT device 112 or any other entry point into network 102. Network 102 is an example only and many different network topologies may be used with embodiments described herein. Dotted lines in FIG. 1 indicate example wireless links or connections while solid lines indicate example wired links.
An IP address is typically assigned to each device in network 102 (e.g., each of host devices A-E, proxy server 108, and NAT device 112), and each device may be identified by, or said to be associated with, its assigned IP address as indicated, for example, in IP packets flowing to and from the device. Each device may also be identified by a respective device name (such as an alphanumeric name) assigned to that device as also indicated in the IP packets.
NAT device 112 translates or maps the IP addresses in IP packets traversing the NAT device between a private IP address space for the devices in network 102 and a public IP address space exposed to network 104. As such, NAT device 112 modifies source and destination IP addresses in IP packets from the devices in network 102 destined for network 104 and from network 104 destined for the devices in network 102. As used herein, the term “NAT device” means any entity or instance that performs NAT, such as any physical device or hardware, virtual device or virtual machine, computer/software application, or service, such as a cloud based service, configured to perform NAT.
Proxy server 108 acts an intermediary or focal point for network traffic in the form of client-server transactions between “client” devices in network 102 (e.g., host devices A-E, network switch 110, and so on) and “server” devices in network 104. In such transactions, devices in network 102 act as clients that send requests to devices in network 104 through proxy server 108, and the devices in network 104 act as servers that send responses to the appropriate requesting clients through the proxy server 108. Proxy server 108 may also serve as a focal point for network traffic circulating between the devices in network 102. Thus, proxy server 108 has a comprehensive view of network traffic to and from the other devices in network 102 and monitors that network traffic.
With reference to FIG. 2, there is an illustration of a high-level system 200 for detecting NAT devices (e.g., NAT device 112) and/or proxy servers (e.g., proxy server 108) in network 102, according to an embodiment. System 200 includes proxy server 108 and a NAT detector 204. NAT detector 204 may reside on, or be part of, any device in network 102, or may be a stand-alone device that can access proxy server 108. Proxy server 108 captures network traffic logs 206 of network traffic flowing to and from the devices in network 102 over a period time, stores the logs, and makes them available to NAT detector 204. This process is referred to as “logging network traffic” to produce network traffic logs. In an embodiment, proxy server 108 captures Hypertext Transfer Protocol (HTTP) proxy logs (also referred to simply as “HTTP logs”) associated with IP packets to and from the other network devices in network 102. The HTTP proxy logs include information in HTTP headers for IP packets, including, but not limited to, IP addresses and device names, URLs, User-Agent strings, and the like.
Initially, each entity identified in the network traffic logs by IP address or device name is regarded as a generic “host device” that may be either a NAT device that performs NAT, or a end host device that does not perform NAT. A “host device” may be any physical device or hardware, virtual device or virtual machine, computer/software application, or service, such as a cloud based service, identifiable in the network traffic logs. A host device that performs NAT is a NAT device (as mentioned above), while a host device that does not perform NAT is an “end host device” or a “non-NAT” device. An “end host device”/“non-NAT device” may be any physical device or hardware, virtual device or virtual machine, computer/software application, or service, such as a cloud based service, which does not perform NAT.
The behavior of a NAT device actually includes a mixture of behaviors of individual devices, such as end host devices (i.e., not NAT devices) connected to the NAT device as well as behavior specific to the NAT device. Accordingly, NAT detector 204 recognizes this mixture of behaviors as exhibited in the captured HTTP logs to detect the NAT device, as described below. Accordingly, NAT detector 204 accesses captured HTTP logs 206 and derives information from the logs indicative of whether each host device identified in the logs (e.g., each host device in network 102) exhibits the behavior of a NAT device or an end host device (i.e., non-NAT device).
NAT detector 204 includes a host device behavior classifier 209 that has been trained in an a priori training phase to classify each host device identified in network traffic logs 206 as either a NAT device or an end host device that does not host a NAT application, based on the information derived from network traffic logs. Thus, trained classifier 209 classifies each device in network 102 as either a NAT device or an end host device based on the information derived from the network traffic logs and outputs classifier results 210. The operation of classifying is also considered one of detecting NAT devices and end host devices in network 102. In the examples of FIGS. 1 and 2, classifier results 210 indicate that host devices A, B having IP addresses 10.10.47.1, 10.10.23.2 are end host devices (non-NAT devices) and router 112 having IP address 10.10.13.7 is a NAT device.
With reference to FIG. 3 there is a flowchart of an example method 300 of detecting NAT devices in network 102 performed by NAT detector 204 based on network traffic logs 206 collected by proxy server 108. Method 300 is performed after the a priori training phase of classifier 209 in which the classifier has been trained to classify devices in a network as either NAT devices or end host devices based on certain information derived from known network traffic logs (which may be from network 102 or other networks), as will be described below. Method 300 may also be used to detect proxy servers in network 102.
At 305, proxy server 108 logs network traffic to and from the host devices in/connected to network 102 over time to produce network traffic logs 206, as mentioned above. In an example, proxy server 108 collects HTTP logs in consecutive non-overlapping time windows spanning multiple hours to produce respective HTTP logs in each time window. In an example, proxy server 108 collects HTTP logs in consecutive, non-overlapping, 30 minute time windows spanning 24 hours. Other time window periods and spanning durations may be used.
With reference to FIG. 4, there is an illustration of an example table of HTTP logs 400 captured by proxy server 108. Table of HTTP logs 400 includes (i) rows R1-R5 each representing an HTTP log for a client-server (c-s) network transaction, and (ii) multiple columns to record various types of information about the network transaction for each log. Typical HTTP logs may include many more than the five rows shown in the example of FIG. 5. For illustrative convenience, HTTP log table 400 is divided between a first table portion 405 having a first set of columns “TIMESTAMP” through “ELAPSED TIME” and a second table portion 410 having a second set of columns “S-IP” through “CS(USER-AGENT).” The “User-Agent” string typically identifies the client software running on the host device that originated a client-server request. In table 400, prefixes “S” and “C” are abbreviations for “server” and “client,” respectively. For instance, “SC-BYTES” means “server to client bytes” for downloaded bytes. Conversely, “CS-BYTES” means “client to server bytes” for uploaded bytes.
First table potion 405 includes columns to record (1) a TIMESTAMP for each c-s transaction or log, (2) HTTP STATUS code, (3) SC-BYTES to indicate a number of bytes transferred in an SC transaction packet, (4) SC-CONTENT BYTES to indicate a number of content bytes in an SC transaction packet (as opposed to total header and content bytes), (5) CS-BYTES to indicate a number of bytes in a CS transaction packet, (6) CS-CONTENT BYTES to indicate a number of content bytes in a CS transaction packet, (7) CS-METHOD to indicate an HTTP method used for the transaction, (8) CS-URL to indicate the access URL for the transaction (see example URLs URL1-URL5 from table portion 405, below), and (9) an ELAPSED TIME for the transaction. Example URLs URL1-URL5 are listed below in expanded form:

    
    
        URL1=http://en.wikipedia.org/wiki/Network_address_translation.
        URL2=ts4.mm.bing.net/th?q=SQL+Server+Technology&w=35&h=35&c=1&qlt=90&pid=lnlineBlock&mkt=en-GB&adlt=moderate&t=1.
        URL3=http://www.nytimes.com/.
        URL4=https://www.facebook.com/?_rdr.
        URL5=https://www.yahoo.com/.
    
    


Second table potion 410 includes columns to record (1) a S-IP address for the server, (2) an S-PORT for the server, (3) a C-IP address for the client, (4) a C-PORT for the client, (5) a CS-MIME-TYPE used in the transaction (where MIME means “Multipurpose Internet Mail Extensions”), (6) a CS(Referrer) (see the example Referrer string CS1 from table portion 410, below), and (7) a CS-User-Agent string (see the example User-Agent strings UA1-UA5 from table portion 410, below). In the example of FIG. 4, all of the server-side IP addresses are different, while all of the client-side IP addresses are the same. Example Referrer string CS1 from table portion 410 is shown below in expanded form:

    
    
        CS1=http://www.bing.com/images/lsearch?q=proxy+server&FORM=HDRSC2.
    
    


Example User Agent strings UA1-UA5 from table portion 410 are shown below in expanded form:

    
    
        UA1=Mozilla/5.O (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Ubuntu Chromium/37.0.2062.120 Chrome/37.0.2062.120 Safari/537.36.
        UA2=Mozilla/5.O (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Ubuntu Chromium/37.0.2062.120 Chrome/37.0.2062.120 Safari/537.36.
        UA3=Mozilla/5.O (Windows NT 6.3; rv:36.0) Gecko/20100101 Firefox/36.0.
        UA4=Mozilla/5.O (compatible, MSIE 11, Windows NT 6.3; Trident/7.0; rv:11.0) like Gecko.
        UA5=Opera/9.80 (X11; Linux i686; Ubuntu/14.10) Presto/2.12.388 Version/12.16.
    
    


Returning to FIG. 3, after HTTP logs 206 have been collected at 305, at 310 NAT detector 204 accesses the logs and identifies each host device therein by its IP address (e.g., client IP address) and/or device/client username. For each host device identified in the logs 206, NAT detector 204 extracts from the logs for the given host device a set of (i.e., multiple) time-varying network traffic behavioral features (also referred to simply as “features”) indicative of whether the host device behaves like a NAT device or an end host device. An example set of features extracted from the HTTP logs for the given host device in each time window includes:

    
    
        a. Number of unique contacted IP addresses;
        b. Number of unique User-Agent strings contained in the HTTP transaction (request header);
        c. Number of unique operating systems (OSs) including the version as parsed from the User-Agent string;
        d. Number of persistent connections (in an example, a connection to an IP address is considered to be persistent if it is active in at least five time windows from ten last consecutive time windows, where the time windows may be set to a time period of 30 minutes, one hour, two hours, or four hours, for example);
        e. Number of unique web browser versions as parsed from the User-Agent string;
        f. Number of bytes uploaded in the transaction;
        g. Number of bytes downloaded in the transaction; and
        h. Number of logs/transactions (also referred to as “flows”) for the host device in the time window.
    
    


The above features (a)-(h) are meant to be examples, only, and more or less features, or even different features, may be extracted from the HTTP logs.
Each feature in the set of features (a)-(h) for each host device takes on feature values that vary over time based on the information recorded in the logs for the given host device. In the example using time windows, NAT detector 204 extracts a feature value for each feature for each host device in each time window based on the HTTP logs for that host device for that time window, such that the feature values vary from window to window as the HTTP logs vary from window to window. The set of feature values (for the features (a)-(h)) for each window for each host device is referred to as a “feature vector” of features values that represents the behavior of the host device and, more specifically, whether the host device behaves more like a NAT device or more like an end host device, as determined by classifier 209.
With reference to FIG. 5, there is an example table of features 500 having columns to record feature values of behavioral features (a)-(h) extracted from logs 206 (i.e., number of unique contacted IP addresses, User-Agent strings, number of OSs, and so on). In one embodiment, each row in table of features 500 represents a set of feature values (i.e., a feature vector) for a different host device. In another embodiment, each row represents a set of feature values (i.e., a feature vector) for a different time window, but for the same host device.
As mentioned above, each feature has feature values that vary over time depending on the relevant information extracted from the HTTP logs. To illustrate this for one feature, reference is now made to FIG. 6, which is an example plot 600 of the average number of flows (i.e., feature (h) listed above) for the given host device per time window. In plot 600, the height of each vertical bar represents the number of flows in a given time window that spans 30 minutes, where all of the time windows collectively span 24 hours.
Returning again to FIG. 3, after the feature value for each feature in each set of features has been extracted in each time window for each host device at 310, at 312, trained classifier 209 classifies each host device as either a NAT device or an end host device based on one or more of the feature values (from corresponding ones of one or more of the time windows) for each feature in the set of features for the given host device. In one embodiment, classifier 209 may classify each host device based on all of the feature values for each feature in the set of features, in which case process flow in method 300 proceeds directly from operation 310 to operation 312.
In another embodiment, classifier 209 may classify each host device based on a subset of the feature values (i.e., one or more, but not all) selected from all of the feature values of each feature in the set of features. Accordingly, method 300 includes optional operations 315 and 320 to select the subset of feature values of each feature in the set of features used by classifier 209 to perform the classify operation 312. In this embodiment, process flow in method 300 proceeds from operation 310 to operation 312 through operations 315 and 320, as described below.
At 315, NAT detector 204 generates/identifies statistics indicative of how the feature values of each feature in each set of features for each host device vary or are distributed over time. Example statistics that may be generated include quantile values, such as a maximum value, a minimum value, and a median value. A further statistic may include a mean value. Feature value-based statistics other than those just described may also be generated.
After the feature statistics have been generated at 315, at 320 NAT detector 204 selects one or more time windows and thus one or more corresponding feature values of each feature of each set of features for each host device based on the statistics generated for that feature. It is desirable to capture/identify the one or more time windows (and thus, feature values) for each host device in which the host device was active and that filters out outlying feature values generated as a result of abnormal host device activities. To achieve this, in an example, NAT detector 204 selects, for each feature, the feature value from a top quarter of quantile values, such as the 90% quantile. It is understood that the 90% quantile is an example only, and other quantiles may be selected.
With reference to FIG. 7, there is an example plot 700 that shows the number of flows per time window (i.e., the vertical bars) taken from plot 600 of FIG. 6 sorted from lowest to highest values across the time windows. There is a similar “sorted” plot for each of the features (a)-(h) for each feature of each set of features for each host device. In this example, the 90% quantile is represented by bar 705.
In another embodiment, operation 320 may base the selection of one or more time windows from which feature values are to be used in the classification based on predetermined information defining particular ones of the time windows, i.e., time windows in particular time positions, rather than on generated statistics.
After select operation 320, at 312, trained classifier 209 of NAT detector 204 classifies each host device as either a NAT device or a end host device based on the one or more selected feature values (i.e., the one or more feature vectors) for the set of features for the given host device.
As mentioned above, NAT detection method 300 is performed after classifier 209 has been trained to classify NAT devices and end host user devices. In an embodiment, classifier 209 includes a linear Support Vector Machine (SVM), which is a learning algorithm that learns (i.e., is trained) with real/actual network traffic data; however, to train the SVM, labeled data (i.e., feature vectors) is needed, with end host device/NAT device labels that would indicate that the data is associated with a end host device (i.e., an end host user) or a NAT device (i.e., a host performing NAT). Obtaining such labeled data can be difficult because, typically, there are only a few NAT devices compared to a high number of end host devices in an actual network, which makes the data used to train the classifier highly imbalanced.
Accordingly, embodiments described below create artificial NAT devices for purposes of training the classifier simply by joining network traffic from multiple host devices into a single artificial host device (that represents an artificial NAT device). In this way, an arbitrary number of NAT devices may be simulated with any number of actual host devices, and many different feature vectors may be generated to train the SVM. For purposes of training the SVM, feature vectors for artificially created NAT devices are labeled as “positive samples” and feature vectors for actual host devices are labeled as “negative samples” for the SVM learning machine. This means that feature vectors for any actual NAT devices present in the network are incorrectly labeled as negative samples (which indicate end host devices or ordinary hosts to the classifier); however, it is assumed that the number of actual NAT devices in the network is significantly smaller than the number of actual end host devices (i.e., ordinary hosts). Therefore, incorrect labeling of negative samples for actual NAT devices has a minimal impact on training any classifier supporting noisy data training.
Classifier 209 may be based on or use supervised learning algorithms other than the linear SVM, which is described as an example, only.
With reference to FIG. 8, there is a flowchart of an example method 800 of training classifier 209 based on information derived from actual HTTP logs to transition the classifier from an untrained state to a trained state so that the classifier may be used to classify between a NAT device and an end host device, as in method 300.
At 815, multiple sets of actual/real HTTP logs 810(1)-(N) are collected over time for actual/real host devices in one or more networks, which may include, e.g., network 102. The HTTP logs 810 are referred to as known network traffic logs for purposes of training. The number of actual host devices typically includes a number of actual end host devices and a number of actual NAT devices. Each log in actual HTTP logs 810 is labeled to indicate end host device behavior, i.e., to indicate an end host device. The labeled actual HTTP logs are referred to as negative samples or negative instances because they are assumed not to indicate NAT devices.
At 820 (referred to as “NAT simulation”), artificial HTTP logs for a number of artificial NAT devices are created based on actual HTTP logs 810 in the following manner:

    
    
        a. The artificial NAT devices are created, each identified by a corresponding IP address. Each IP address may be an IP address in actual HTTP logs 810 that identifies an actual host device or an artificially created IP address. The number of artificial NAT devices is arbitrary. In one embodiment, the number of artificial NAT devices is equal to the number of actual host devices identified in the actual HTTP logs 810. In other embodiments, the number of artificial NAT devices is less than or greater than the number of actual host devices identified in actual HTTP logs 810;
        b. For each artificial NAT, multiple artificial HTTP logs are created from a corresponding set of actual HTTP logs for different actual host devices in the following manner. The set of actual HTTP logs are copied, and each HTTP log in the copied set of actual HTTP logs is associated with the given artificial NAT device instead of the different actual host devices. To do this, the different IP addresses of the different host devices in the set of copied actual HTTP logs are all replaced with the IP address of the given artificial NAT device. This creates a set of artificial HTTP logs for the given artificial NAT in addition to the original actual HTTP logs that were copied; and
        c. Each artificial log in the artificial HTTP logs is labeled to indicate NAT device behavior, i.e., to indicate a NAT device. The labeled artificial HTTP logs are referred to as positive samples or positive instances because they indicate NAT devices.
    
    


At 825, the labeled actual HTTP logs (i.e., negative instances) and the labeled artificial HTTP logs (i.e., positive instances) from 820 are merged into a file of labeled HTTP logs representative of both NAT devices (the positive instances) and end host devices (the negative instances).
At 830, operations 310 and, optionally, operations 315 and 320, described above are performed across the merged HTTP logs to generate one or more feature values for each feature of the set of features for each host device identified in the merged HTTP logs (i.e., for assumed end host devices and the artificial NAT devices). The feature values generated at 830 are labeled (i.e., indicated as positive and negative instances) according to the manner in which the HTTP logs from which the feature values were extracted are labeled.
At 835, classifier 209 implements a learning process to learn, or train, to classify between an end host device (i.e., an end host user) and a NAT device based on the labeled feature values from operation 830. In other words, classifier 209 trains based on the labeled HTTP logs so as to transition itself from an untrained state to a trained or learned state.
With reference to FIG. 9, there is depicted a block diagram of a computer system 900 to perform the methods presented herein. Computer system 900 may be part of any device in network 102, for example, proxy server 108, host devices A-E, NAT device 112, or switch device 110. Computer system 900 may also be a stand-alone system that accesses the HTTP logs from proxy server 108 to perform the methods described above. Computer system 900 includes a network interface unit 905 configured to enable network communications to send messages to and receive messages from devices in a network (e.g., devices in network 102). One or more processors 910 are provided that execute software stored in memory 920. Processor(s) 910 include, for example, one or more microprocessors and/or microcontrollers. To this end, the memory 920 stores instructions for software stored in the memory that are executed by processor(s) 910 to perform the methods described herein.
Memory 920 may comprise read only memory (ROM), random access memory (RAM), magnetic disk storage media devices, optical storage media devices, flash memory devices, electrical, optical, or other physical/tangible memory storage devices. Thus, in general, the memory 920 may comprise one or more tangible (non-transitory) computer readable storage media (e.g., a memory device) encoded with software comprising computer executable instructions and when the software is executed (by the processor(s) 910) it is operable to perform the operations described herein. Memory 920 may store NAT detector logic 925 to implement NAT detector 204 that performs NAT detection methods described in connection with FIGS. 2 and 3, classifier logic 930 to implement classifier 209 described above, classifier trainer logic 940 to implement the classifier training method described in connection with FIG. 8, and logger logic 945 to record network traffic as HTTP logs.
In addition, memory 920 stores data 950 used and generated by the processor 910 when executing the logic described above.
In summary, a NAT (or HTTP proxy) detection algorithm uses multiple features (e.g., 8 features) extracted from HTTP logs of network traffic which are collected in consecutive non-overlapping time windows of a predefined duration. In an embodiment, one or more representative feature values of each feature are selected, although all of the feature values may be used. For the purpose of training linear SVM on balanced data, artificial NAT devices are constructed by merging artificial logs with real/actual logs. Finally, host devices of any network are classified using the pre-trained linear SVM, but other classifiers can be used as well. The techniques described herein: only need HTTP logs to detect NAT hosts; provide a high accuracy of NAT detection; provide a capability to detect NAT devices with users having the same OS and web browser; provides a behavior classifier that is well trained on a sufficient amount and variety of positive and negative samples; and provides a good estimate of the actual number of users in a network.
In summary, in one form, a method is provided comprising: accessing logs of network traffic to and from host devices connected to a network that were collected over time; and for each host device identified in the logs: extracting, from the logs for the host device, multiple network traffic features indicative of whether the host device behaves like a Network Address Translation (NAT) device or a non-NAT device that does not perform NAT, each feature having values that vary over time; and classifying, using a trained classifier that is trained based on known network traffic, the host device as either a NAT device or a non-NAT device based on one or more of the feature values for each of the multiple network traffic features.
In summary, in another form, an apparatus is provided comprising: a network interface unit to communicate with a network; and a processor, coupled to the network interface unit, and configured to: access logs of network traffic to and from host devices connected to the network that were collected over time; and for each host device identified in the logs: extract, from the logs for the host device, multiple network traffic features indicative of whether the host device behaves like a Network Address Translation (NAT) device or a non-NAT device that does not perform NAT, each feature having values that vary over time; and classify, using a trained classifier that is trained based on known network traffic, the host device as either a NAT device or a non-NAT device based on one or more of the feature values for each of the multiple network traffic features.
In summary, in yet another form, a non-transitory processor readable medium is provided. The processor readable medium stores instructions that, when executed by a processor, cause the processor to: access logs of network traffic to and from host devices connected to a network that were collected over time; and for each host device identified in the logs: extract, from the logs for the host device, multiple network traffic features indicative of whether the host device behaves like a Network Address Translation (NAT) device or a non-NAT device that does not perform NAT, each feature having values that vary over time; and
classify, using a trained classifier that is trained based on known network traffic, the host device as either a NAT device or a non-NAT device based on one or more of the feature values for each of the multiple network traffic features.
The above description is intended by way of example only. Various modifications and structural changes may be made therein without departing from the scope of the concepts described herein and within the scope and range of equivalents of the claims.

## Claims

1. A method comprising:
accessing logs of network traffic to and from host devices connected to a network that were collected over time in consecutive non-overlapping time windows;
identifying the host devices in the accessed logs and, for each identified host device:
extracting, from the logs for the host device, multiple network traffic features, each feature having a respective value in each time window indicative of whether the host device behaves like a Network Address Translation (NAT) device or a non-NAT device that does not perform NAT, each feature having values that vary over time, wherein the features include a number of contacted unique Internet Protocol (IP) addresses indicated in the logs, a number of User-Agent strings included in packet headers, and a number of persistent connections;
classifying, using a trained classifier that is trained based on known network traffic, the host device as either a NAT device or a non-NAT device based on one or more of the feature values for each of the multiple network traffic features;
generating statistics indicative of how the values of each feature vary over time; and
selecting the one or more feature values based on the statistics.

2. The method of claim 1, wherein the extracting includes extracting further features to include:
a number of unique operating systems; and
a number of web browser versions.

3. The method of claim 1, wherein the extracting includes extracting further features to include:
a number of bytes uploaded; and
a number of bytes downloaded.

4. The method of claim 1, further comprising training the classifier based on (i) network traffic logs of actual network traffic to and from actual host devices in one or more networks, and (ii) artificial network traffic logs generated from the actual network traffic logs for artificial NAT devices.

5. The method of claim 4, wherein the training includes:
generating for each artificial NAT artificial network traffic logs from multiple actual network traffic logs;
labeling the artificial and actual network traffic logs as being indicative of NAT devices and non-NAT devices, respectively;
performing the extracting on the labeled artificial and actual network logs to produce one or more labeled feature values for each artificial NAT and non-NAT device indicated in the labeled network traffic logs; and
training the classifier using the one or more labeled feature values for each artificial NAT and non-NAT device.

6. The method of claim 5, wherein the generating the artificial network logs for each artificial NAT device includes:
copying a set of actual network traffic logs for different actual host devices; and
associating each actual network traffic log in the copied set of actual network traffic logs with the artificial NAT device instead of the different actual host devices.

7. The method of claim 1, wherein the host devices include a proxy server through which the host devices communicate in the network or access the network, and wherein the logs are collected by the proxy server.

8. The method of claim 1, wherein the host devices are identified in the network traffic logs by an Internet Protocol (IP) address or an alphanumeric host device name.

9. The method of claim 1, wherein the features further include:
a number of bytes uploaded in a network traffic transaction; and
a number of bytes downloaded in a network traffic transaction.

10. The method of claim 1, wherein the features further include:
a number of transaction logs for a given host device in a given time window.

11. An apparatus comprising:
a network interface unit configured to communicate with a network; and
a processor, coupled to the network interface unit, and configured to:
access logs of network traffic to and from host devices connected to the network that were collected over time in consecutive non-overlapping time windows;
identify the host devices in the accessed logs and, for each identified host device:
extract, from the logs for the host device, multiple network traffic features, each feature having a respective value in each time window indicative of whether the host device behaves like a Network Address Translation (NAT) device or a non-NAT device that does not perform NAT, each feature having values that vary over time, wherein the features include a number of contacted unique Internet Protocol (IP) addresses indicated in the logs, a number of User-Agent strings included in packet headers, and a number of persistent connections;

classify, using a trained classifier that is trained based on known network traffic, the host device as either a NAT device or a non-NAT device based on one or more of the feature values for each of the multiple network traffic feature;
generate statistics indicative of how the values of each feature vary over time and select the one or more feature values based on the statistics.

12. The apparatus of claim 11, wherein the processor is configured to train the classifier based on (i) network traffic logs of actual network traffic to and from actual host devices in one or more networks, and (ii) artificial network traffic logs generated from the actual network traffic logs for artificial NAT devices.

13. The apparatus of claim 12, wherein the processor is configured to train by:
generating for each artificial NAT artificial network traffic logs from multiple actual network traffic logs;
labeling the artificial and actual network traffic logs as being indicative of NAT devices and non-NAT devices, respectively;
performing the extracting on the labeled artificial and actual network logs to produce one or more labeled feature values for each artificial NAT and non-NAT device indicated in the labeled network traffic logs; and
training the classifier using the one or more labeled feature values for each artificial NAT and non-NAT device.

14. The apparatus of claim 11, wherein the features further include:
a number of bytes uploaded in a network traffic transaction; and
a number of bytes downloaded in a network traffic transaction.

15. A non-transitory computer readable storage media encoded with instructions that, when executed by a processor, cause the processor to:
access logs of network traffic to and from host devices connected to a network that were collected over time in consecutive non-overlapping time windows;
identify the host devices in the accessed logs and, for each identified host device:
extract, from the logs for the host device, multiple network traffic features each having a respective value in each time window indicative of whether the host device behaves like a Network Address Translation (NAT) device or a non-NAT device that does not perform NAT, each feature having values that vary over time, wherein the features include a number of contacted unique Internet Protocol (IP) addresses indicated in the logs, a number of User-Agent strings included in packet headers, and a number of persistent connections;
classify, using a trained classifier that is trained based on known network traffic, the host device as either a NAT device or a non-NAT device based on one or more of the feature values for each of the multiple network traffic feature;
generate statistics indicative of how the values of each feature vary over time; and
select the one or more feature values based on the statistics.

16. The non-transitory computer readable storage media of claim 15, further comprising instructions to cause the processor to train the classifier based on (i) network traffic logs of actual network traffic to and from actual host devices in one or more networks, and (ii) artificial network traffic logs generated from the actual network traffic logs for artificial NAT devices.

17. The non-transitory computer readable storage media of claim 16, wherein the instructions to cause the processor to train include instructions to cause the processor to:
generate for each artificial NAT artificial network traffic logs from multiple actual network traffic logs;
label the artificial and actual network traffic logs as being indicative of NAT devices and non-NAT devices, respectively;
perform the extracting on the labeled artificial and actual network logs to produce one or more labeled feature values for each artificial NAT and non-NAT device indicated in the labeled network traffic logs; and
train the classifier using the one or more labeled feature values for each artificial NAT and non-NAT device.

18. The non-transitory computer readable storage media of claim 15, wherein the features further include:
a number of bytes uploaded in a network traffic transaction; and
a number of bytes downloaded in a network traffic transaction.