Malicious attacks can be launched by misusing the network address translation technique as a camouflage. To mitigate such threats, network address translation identification is investigated to identify network address translation devices and detect abnormal behaviors. However, existing methods in this field are mainly developed for relatively small-scale networks and work in an offline manner, which cannot adapt to the real-time inference requirements in high-speed network scenarios. In this paper, we propose a flexible and efficient network address translation identification scheme based on actively measuring the distance of a round trip to a target with decremental time-to-live values. The basic intuition is that the incoming and outgoing traffic from a network address translation device usually experiences the different number of hops, which can be discovered by probing with dedicated time-to-live values. We explore a joint effort of parallel transmission, stateless probes, and flexible measuring reuse to accommodate the efficiency of the measuring process. We further accelerate statistical counting with a new sublinear space data structure Bi-sketch. We implement a prototype and conduct real-world deployments with 1000 volunteers in 31 Chinese provinces, which is believed to bring insight for ground truth collection in this field. Experiments on multi-sources datasets show that our proposal can achieve as high precision and recall as 95% with a traffic handling throughput of over 106 pps.
As a widely adopted protocol, network address translation (i.e., NAT), also known as IP masquerading, provides transparent routing to hosts by mapping IP addresses from one realm to another [
In this work, we propose a flexible and efficient NAT identification scheme that can adapt to large-scale networks and fluctuated traffic. Our basic insight is that the hops he to an end device in NAT environment is in fact further than reaching out to the IP address it uses. To this end, we design an Active Decremental TTL-based (ADT) algorithm whose probes are composed of a series of ICMP packets with decremental TTL values (i.e., he, he −1, etc.). Compared with the ADT algorithm, the existing traceroute tools will send abundant small TTL (e.g., 1, 2) probes in the initial stage which undoubtedly cause the waste of upload bandwidth.
Given that the amount of incoming traffic is large, we carefully adopt several mechanisms including parallel transmission, stateless probes, measuring reuse and data approximation to implement the scheme. For computing statistics during identification requires tremendous query operations, we design a new sublinear space data structure (i.e., Bi-sketch) to avoid excessive intermediate information storage, simplify the counting process, and attain efficiency. Compared with Count-Min Sketch [
Note that existing techniques test their proposals on offline datasets due to the lack of NAT labeled traffic. To fill this gap, we implement a prototype and deploy it in real-world networks during the evaluation. In summary, we make the following contributions:
We implement a comprehensive NAT identification scheme integrating the proposed Active Decremental TTL-based (ADT) algorithm and several innovative mechanisms (i.e., parallel transmission, stateless probes, measuring reuse and data approximation). We propose a new sketch structure (i.e., Bi-sketch) to accelerate statistic computation with its error bound theoretically proved. Targeted at the lack of NAT labeled traffic datasets, we design a lightweight prototype by recruiting around 1000 volunteers from 31 Chinese provinces.
Time to live (TTL), as a field of IP header, is a mechanism that limits the lifespan or lifetime of packets in a network [
As shown in
NAT devices or gateways reduce the TTL of packets that they forward [
More than 90% hosts can be reached within 18 hops and the max hops of a normal route path will be less than 32 hops [
Time to live (TTL), as a field of IP header, is a mechanism that limits the lifespan or lifetime of packets in a network [
Operating system | Initial TTL |
---|---|
Windows NT/2000 | 128 |
Windows 95/98 |
32 |
Throughput | Cost | Real-time | Clientlessness | |
---|---|---|---|---|
Bellovin [ | middle | high | low | yes |
Revelio [ | low | middle | high | no |
Andreas [ | middle | high | high | no |
Livadariu [ | high | high | middle | yes |
Proposed | high | low | high | yes |
Based on the observation that on many operating systems, the IP header's ID field is a simple counter [
NAT Revelio [
Muller et al. [
Using passive measurement, Livadariu [
As is shown in
We first present the design of the active decremental TTL-based (ADT) algorithm and its initial assumption intuitively. Then, we implement a comprehensive NAT identification scheme integrating innovative and efficient mechanisms. Furthermore, we give the details of the sublinear space data structure (i.e., Bi-sketch) and its theoretical error bound.
In general, the detection of NAT should rely on different behavior patterns of NAT gateway and the host behind NAT, those complex detecting mechanisms will confuse the network in large-scale real-time NAT identification. In order to reduce the impact on the network, we use the Active Decremental TTL-based algorithm to build the NAT traffic analyzer. This algorithm can not only identify the NAT usage, but also measure the hops between the end hosts and the NAT devices or gateways.
The initial assumption of our ADT algorithm is that we are able to trace the real hops and compare them with the packet hops when our scheme sniffed a packet as
The initial TTL values of the packets and efficient hop trace are indispensable. There are methods for obtaining the initial TTL of the target hosts, such as OS fingerprint from the Nmap tool [
To further reduce bandwidth usage, the TTL values of probes are initially set to difference between initial TTL and reserved TTL and actively decrement instead of naively increasing. Suppose a host is 10 hops away from the measurement server, most small TTL (e.g., 1, 2, 3) probes are unnecessary and will get the Time−Exceeded replies [
There are several mechanisms of the NAT traffic analyzer for the flexible and efficient identification: 1) parallel transmission. To avoid blocking and deadlock, the analyzer directly processes link-layer frames rather than network sockets. 2) stateless probes. As shown in
As one of the most used Internet protocols, ICMP itself can carry a large amount of routing and terminal information as the probing protocol. We can even set the options in the ICMP packets to achieve our measurement purpose. Thus, when it sniffs packets from the targeted network, the analyzer runs as follows:
After the Sniffer, Filter, Classifier in In the Generation module, the destination address of the ICMP probe is set to the source address of the new stream packet. Then, the probes are created based on ADT algorithm and handled by the next step. The Transmission will send the ICMP probes in parallel. Then the replies of these probes will back to the analyzer and processed as Step (1).
Scanning of hosts on the Internet to infer NAT usage inevitably keeps the intermediate states. Local storage of intermediate states will cause a lot of storage and query costs, further reducing efficiency. Thus, the probes keeping the intermediate state, so-called stateless probes, is an intuitive idea. As shown in
We cannot deny that the errors caused by network anomalies cannot be completely eliminated. Thus, we further describe the errors in 5.2, and we experimentally characterize the analyzer's performance in 5. Additionally, there are also some decent works [
In the previous subsections, we introduce the parallel transmission and stateless probe mechanisms of the NAT traffic analyzer. However,
Based on the observation that two hosts are fixed in one stream, such as a TCP handshake, we only need to analyze the quintuple, including the source address, the destination address, the source port, the destination port, and the transport layer protocol of the packets to identify a stream as shown in
Bloom filter [
Inevitably, the false positive rate of the Bloom filter will increase as the number of packets increases. A reasonable method is to refresh the bloom filter at certain intervals. According to the formula
However, considering practicality, it is meaningless for network management and network security to only know the types (NAT/non-NAT) of each packet or each stream, and necessary statistical information is the real demand. Naively, directly storing the identification results will result in a lot of query costs. For example, assuming the types (NAT/non-NAT) of n streams have been identified and the new results of m packets have arrived, the cost of querying and storing to the corresponding streams will be
To address the statistics challenge of real-time large traffic, we propose the Bi-Sketch in
Given parameters
In fact, it is non-trivial, if not impossible, to attain the ground truth of NAT label for large-scale network traffic as it requires intensive involvements of the target (source of the traffic) for manual annotation. This further highlights the necessity of an effective measurement technique. To overcome the lack of ground truth for evaluation purposes, we implement a relatively light-weight prototype for demonstration purposes by building a server for centralized traffic analysis and recruiting distributed mobile terminals as end devices. The workflow is shown in
To attain traffic type ground truth, we design an annotation module for the participated devices to detect and report. Specifically, we refer to the Session Traversal Utilities for NAT (STUN) protocol [
Based on STUN, we can acquire whether the mobile terminal is on the Open Internet (non-NAT) or in other types (NAT) when it accesses the public STUN server. Note that merely obtaining the traffic type is not enough, meanwhile, we also require the hops of the end devices to the NAT gateways to evaluate the identification precision. For this, a terminal first obtains its public IP address by accessing some domain names. Then, existing tools, such as traceroute, are used to measure the hops away from the NAT gateway easily.
The diversity of mobile terminal operating systems, such as iOS and Android, poses new challenges for implementing the client-side prototype during real-world deployment. Obviously, developing dedicated software or plug-ins for each operating system is inflexible. Fortunately, we are aware that most Chinese users have the WeChat, which is known as a social platform/software, installed on their mobile devices [
We recruit 1000 volunteers from 31 provinces in China for traffic data annotation. The geo-distribution of their devices and the corresponding traffic types (w.r.t., STUN) are depicted in
Recall that our scheme is designed for flexible and efficient NAT identification. To test the effectiveness and performance, we use precision and recall for qualifying identification accuracy and use the throughput of handling incoming traffic for gauging its efficiency.
Only several ICMP probes are enough in our scheme [
By jointly considering the requirements of evaluating different performance aspects, we conduct experiments based on three sources of data (as shown in
Data source | Labeled | Size | Real-time | Deployment |
---|---|---|---|---|
Our prototype | √ | Small | Online | Centralized server |
M-lab NDT | X | Medium | Offline | -- |
CERNET | X | Large | Online | Network gateway |
Considering the difficulty of large-scale accuracy evaluation, we finally design a relatively light weight prototype whose components are all under our control. Besides, we also introduce the evaluation metrics of performance on precision rate and recall rate.
For fine-grained evaluation and analysis of the causes of errors, each data from volunteers is assigned the universally unique identifier (UUID). Then, not only the statistics of the data set are evaluated, but the errors of each sample will be also observed as shown in
According to the dataset from the prototype deployment in
NAT hops | Precision rate (%) | Recall rate (%) |
---|---|---|
3 | 95.0 | 95.0 |
2 | 99.6 | 99.2 |
1 | 100.0 | 99.4 |
0 | 100.0 | 100.0 |
To cope with the continuous high load in large-scale networks, high throughput is also an important indicator of the NAT identification scheme. The requirement on throughput majorly includes two aspects.
First, considering the continuous high load of large-scale networks, the throughput and capacity of the NAT identification scheme should keep stable rather than fluctuate sharply. In other words, huge memory usage should be avoided as much as possible. Therefore, we adopt about 1 billion packets from the M-lab NDT dataset [
Second, it is intolerable that lots of active probes occupy bandwidth and reduce the quality of service on the Internet. Therefore, we evaluate the size of the probe traffic under different loads and the impact of active measurement on the network. The result, shown in
Note that the scheme is deployed for throughput evaluation on an Ubuntu 16.04 platform with 4 core CPU and 8G RAM. Therefore, the NAT identification scheme takes into account high throughput and low cost, which means that the applicable scope of the proposed method includes the traffic analysis on the gateways of the backbone networks. Thus, we present the experiment in a real laboratory bed.
CERNET is the first nationwide education and research computer network in China. According to reports, the bandwidth of CERNET backbone has been up to 2.5 Gbps by the end of 2000. More than 2,000 education and research institutions, 1.2 million PCs and 20 million end users have connected to the CERNET. In order to demonstrate the feasibility of large-scale NAT identification, we deployed the scheme at a Border Gateway of CERNET in Jiangsu Province. The traffic's IP address range is 121.248.192.0/20, 202.119.112.0/20, 219.230.160.0/20, 222.193.96.0/20, 2001:250:5005::/48 and 2001:DA8:1004::/48. The NAT identification lasts from November 26, 2020 to December 2, 2020. About 500gigabytes traffic data is collected at intervals 14:00-15:00 every day.
Due to the security configuration of NAT gateways, about 30% of the traffic cannot be identified for the host not replying to ICMP probes. Therefore, the ADT NAT identification scheme, deployed on the CERNET, successfully identified about 70% of the traffic both in IPv4 and IPv6. As shown in
In this work, we introduce an active decremental TTL-based (i.e., ADT) algorithm and implement a real-time NAT identification scheme that can identify the NAT usage and measure the hops between the end devices and the NAT gateways. This work is practical and efficient for large-scale network security and network management scenarios. For flexible and efficient NAT identification, we innovatively adopt several mechanisms including parallel transmission, stateless probes, measuring reuse and data approximation. Besides, we provide our new sketch structure (i.e., Bi-sketch) for data approximation with its error bound theoretically proved. To solve the lack of NAT labeled dataset and comprehensively evaluate the ADT algorithm with ground truth, we also implement a light-weight prototype and conduct real-world deployments. Experiments indicate that our scheme outperformed the existing NAT usage identification methods in multiple metrics.
Tao Yang and Chengyu Wang contribute equally to the article. The authors thank those who contributed to write this article and give some valuable comments.
Obviously, the number of buckets in a row is:
Due to the random and uncertain arrival time of measurement results, the effect of the second correction should be saved in bucket
Therefore, let
Let
Hash collision is inevitable for large-scale data. There will be cases where the hash values of
Therefore, we can give the estimates of NAT traffic through Bi-Sketch, and the estimate has the following guarantees:
Given parameters
Set
Define the variable
by pairwise independence of
We can conclude that with probability at least