基于Hough变换的NAT规模被动估计新方法*

管 涛，王科人，徐正国

(盲信号处理重点实验室，成都610041)

1 引言

网络地址转换器(Network Address Translator，NAT)允许多个内网主机使用相同公网地址连接互联网，它可以缓解IPv4地址数量紧张的问题[1]。目前，NAT已经在互联网中大量部署，范围涵盖了小型的家庭网络以及大型的企业内网。NAT提高了网络使用的隐私性，隐藏了内部网络的大小和拓扑结构。但是，从网络管理和网络安全的角度来说，NAT的大量使用严重影响了网络的正常管理，并且造成了潜在的安全隐患。在被动接收条件下实现NAT检测对网络管理和网络安全威胁检测具有重要作用，例如对僵尸网络的规模检测和未授权的设备接入等。因此，被动接收条件下的NAT流量检测及其规模估计成为工业界和学术界关注的问题。

NAT流量检测需要判断某个IP是否使用了NAT，而NAT规模估计还要对NAT后面主机数量进行估计。目前已有大量工作对NAT流量检测及规模估计进行了研究。

在NAT流量检测方面，文献[2－3]综合了初始TTL(Time To Live)、IPID(IP Identification)、TCP SYN、TCP源端口、TCP时间戳等特征进行NAT流量检测。文献[4－10]则采用的是流量统计的方法，通过训练学习流量特征对NAT流量进行检测。实验结果表明，这些方法均达到了较高的检测率。

在NAT规模估计方面，文献[11]最早提出利用主机发送IPID序列的连续性来估计NAT主机数目。当IPID随机产生或者为固定值(如0)时，文献[11]方法会失效，文献[12]在此基础上进一步关联IPID、TCP序列号和源端口序列进行综合判断。文献[13]给出了一种基于TCP/IP协议栈指纹的NAT检测方法，其适用于NAT后主机具有不同操作系统的情形。文献[14－15]利用了HTTP协议中的User－Agent和Cookie信息出现的种类数进行估计。文献[16]提取了ICMP和TCP中的时间戳值，采用时钟漂移特征区分不同主机。文献[17－18]指出了通过主机启动时间和TCP时钟频率可以唯一标识一台主机，因此采用TCP时间戳序列可以估计NAT规模大小。

本文主要关注的是NAT规模估计问题，即在给定一段时间内的网络数据的条件下，研究如何准确估计NAT后面主机数量。总的来说，现有NAT规模估计的两类方法均存在一定问题:统计IPv4、TCP或HTTP头部中字段种类，如TTL值、User－Agent等，其使用条件比较有限，且分辨率较差;通过提取序列特征可以更准确地估计NAT规模大小，如对IPID序列、TCP序号序列和TCP时间戳序列的连续线段进行检测，但目前采用的方法是密度聚类或线性递归，当线段发生交叉或距离较近时误判率较高，且无法解决初始类别的选择问题。

因此，为了更好地估计出NAT规模，我们将采用Hough变换对基于TCP时间戳序列的估计方法进行改进。我们的解决思路为:对于TCP时间戳和数据包接收时间，由于不同主机的开机时间和TCP时钟频率存在一定的差异，它们体现出不同的线性关系;该线性关系在坐标图中表现为直线，基于计算机视觉中的Hough变换方法递归放大该坐标图像，从而检测出现的直线数目即可获得NAT规模大小。区别于以往估计方法的地方在于，我们改变了序列连续性检测方式，利用计算机视觉的方法解决了初始类别的选择问题，并改进了序列发生交叉或距离较近时的判断精度。

本文组织结构如下:第2节对NAT条件下TCP时间戳与数据包接收时间之间的关系进行建模分析;第3节介绍基于Hough变换的NAT主机数目估计算法;第4节给出了算法在仿真和实际数据条件下的实验结果;第5节对全文进行总结。

2 模型建立

TCP时间戳在RFC1323中引入，它作为TCP头部的选项字段，长度为10 Byte[19]。其主要有两个作用，一是精确测量往返传输时延，二是防止高速传输网络下TCP序号的冲突。TCP时间戳选项中包含长度为32 bit的TSval子字段，它代表当前数据包发送主机设置的TCP虚拟时钟值。下文无特殊说明时，TCP时间戳均指的是TSval子字段。

在被动接收条件下，假设我们获得从某个IP发出的一系列包含TCP时间戳的IP数据包，其中第i个数据包的发送时间为si，TCP时间戳值为ti，它们构成一个TCP时间戳序列。根据RFC1323规定，发送方数据包中的TCP时间戳ti与发送时间si之间应保持线性关系ti=ksi+t0。其中:k为TCP虚拟时钟频率，它与操作系统内核直接相关，RFC建议取值范围为1～1000 Hz，常见的时钟频率有{2 Hz，10 Hz，100 Hz，250 Hz，500 Hz，1000 Hz};t0为初始计数值，它与开机时间直接相关，一般从开机起始为0或某个随机值。

对于被动捕获方，数据包发送时间si是未知的，我们只能获取捕获时间。假设第i个数据包的捕获时间为ri，数据包经历的路径时延为τi，那么有ri=si+τi，捕获时间 ri与时间戳 ti满足 ti=kri－ kτi+t0。定义相对捕获时间为xi，TCP时间戳值为yi如式(1)所示:

那么有 yi=k·xi+b，其中 b=t0+kr1－ kτi。假设在时间跨度T中，收到的含时间戳的数据包个数为N，即数据集合为{(xi，yi)|i=1，2，…，N}。路径时延τi为随机变量，当接收时间跨度T较小时，τi可近似为常数，此时，yi与xi能够较好地满足线性关系。

在TCP时间戳y与相对捕获时间x存在的线性关系y=kx+b中，斜率k是TCP虚拟时钟频率，截距b由主机的开机时间和数据包传输时延决定。因此，采用TCP时间戳序列进行NAT规模估计基于三个假设条件:NAT不修改TCP时间戳值;具有相同TCP时钟频率的主机不在同一时刻开机;数据包传输时延不发生剧烈变化。也就是说，用TCP时钟频率和时间戳起始值可以标识一台主机，这在实际条件下通常是满足的[17－18]。理论上讲，由于时钟频率最大值为1000 Hz，最小可分辨的开机时间差异为1 ms。

对某包含6台主机的NAT设备采集TCP时间戳序列，其中主机1和主机2为Windows XP操作系统，主机3～6为Ubuntu 12.04操作系统，特别地，主机4～6为同一型号设备。画出相对捕获时间和TCP时间戳的散点图如图1所示，线性关系在坐标图中表现为直线，可以看出不同主机表现出不同的线性关系。

图1 NAT中不同主机表现出不同的线性关系Fig.1 Different host behind NAT shows different linearity

假设NAT包含的主机数量为M，对数据包相对捕获时间x和TCP时间戳y建立如下的线性混合模型:

式中，主机数量 M 未知，模型参数{(k1，b1)，(k2，b2)，…，(kM，bM)}未知。这是一个典型的无监督聚类问题，本文将其转化为检测坐标图中的直线数目，通过基于Hough变换的方法估计直线数量。

3 算法描述

为了估计出NAT规模大小，只需要检测TCP时间戳与相对捕获时间坐标图上直线的数目。从计算机视觉角度出发，图像上直线检测可以通过Hough变换完成。由于图像分辨率的原因，利用Hough变换进行检测时，需要进行多级迭代放大，从而更加准确地检测出直线数目。

3.1 数据预处理

由于线性关系的稳定性与路径时延抖动相关，为尽量减小时延抖动对检测的影响，数据的时间跨度需要限制在比较小的长度内。在数据预处理时，我们将数据按照一定的时间长度T分段进行处理。通常时间长度T根据目标的平均流量来确定，从而保证用于识别的数据量足够且具有一定的反应速度。此外，相同TCP时间戳为重复信息，我们只保留第一次出现的数据点。

进行Hough变换前，还需要将分段后的数据二值化映射为图像。假设映射后图像的大小为W×H，即宽度为W，高度为H，那么图像分辨率为

归一化映射后得到原数据点在图像上的坐标点为

将图像上对应坐标置为1即可生成二值图像。生成图像后，再对图像做一次边缘检测处理，完成数据预处理。

3.2 Hough 变换

标准Hough变换采用如下参数形式表示一条直线[20]:

式中，变量ρ表示从原点到直线的垂直距离，变量θ表示原点到直线的垂向量与x轴的夹角。

参数空间(ρ，θ)需要离散化，Hough变换后可以获得离散化参数空间上的分布矩阵，矩阵的每个元素代表落在相应参数位置的图像点数，其峰值点则代表图像上可能存在对应参数的直线。假设输入数据为(x，y)，Hough 变换后得到

对Hough变换的矩阵H检测参数空间中出现的峰值点，并得出当前图像中的直线数目。

参数空间(ρ，θ)的离散精度决定着检测结果的精度，距离ρ的离散化精度记为Rho，夹角θ离散化区间记为Theta。此外，还需要设置H矩阵的峰值判决门限V。

3.3 递归放大

受图像分辨率的限制，需要对检测得到的直线进行递归放大进而获得更精确的结果。首先按照检测结果对图像进行分割，选择已检测到的直线邻域的数据作为新的输入数据重新检测。对于不归属于任何已检测直线的数据，同样作为新的输入数据重新检测。

在选择已检测到直线的邻域数据时，当数据点与直线的距离小于邻域半径ε时，认为数据点归属该直线的领域。已知TCP虚拟时钟频率大于0，当图像上检测到的直线斜率显著大于0时，我们认为不需要再放大。为了减小奇异点的影响，对于获取的数据量小于门限值Th的不做检测处理。

3.4 具体步骤

基于Hough变换的NAT规模被动估计算法的具体步骤如图2所示。

图2 算法具体步骤Fig.2 Detailed procedure of the proposed algorithm

算法中涉及的关键检测参数及实验中采用的典型值如表1所示。

表1 算法关键参数列表Table1 Key parameters of the proposed algorithm

4 实验结果

本节首先在真实数据环境下，对本文算法和已有算法进行验证。为了进一步测试算法性能，我们搭建实验网络，对比本文算法和已有算法的性能。

下面实验将对两种常用的针对TCP时间戳序列实现NAT规模估计的算法进行对比。

(1)Bursztein 算法[17]

通过TCP时间戳在特定TCP虚拟时钟频率下增长的误差值判断两个数据包是否属于同一主机，设定 TCP虚拟时钟频率集合为{2 Hz，10 Hz，100 Hz，250 Hz，500 Hz，1000 Hz}，时 间 间 隔 为10 ms，误差范围为 0.1%。

(2)Wicherski算法[18]

以同一TCP连接(即TCP五元组相同)的数据包作为初始类，通过最小均方误差线性回归方法求取其对应的TCP虚拟时钟频率及估计的开机时间，并将相同时钟频率下开机时间小于δboot的归为同一主机，设置 δboot=2 ms。

注意到，Bursztein算法中将TCP虚拟时钟频率作为先验信息，Wicherski算法则假设同一连接的所有数据包属于同一主机，而本文算法并没有添加这些限制条件。

4.1 真实数据验证

采集真实环境下某网络出口的数据，取其中两个IP地址的TCP时间戳序列进行检测。第1个IP地址的流量和流数分别为4.1 Mbit/s和7192，图3(a)所示的为第1个IP地址数据的检测结果，三种算法检测得到主机数目均为4，与人工分析结果一致。第2个 IP地址的流量和流数分别为35.6 Mbit/s和43 734，图3(b)所示的为第2个IP 地址数据的检测结果，本文算法检测得到主机数目为21，与人工分析结果一致，而Bursztein算法和Wich-erski算法检测结果分别为14和18。

图3 真实数据检测结果Fig.3 Experiment results on real data

4.2 性能对比测试

采用实验网络产生数据进行对比测试，实验采用的网络连接如图4所示。在NAT设备后面连接若干台主机，这些主机持续地随机访问服务器，数据采集点位于NAT设备与服务器之间。

图4 实验网络连接图Fig.4 Experimental network setup

我们采用检测准确率α和偏差值δ评价算法性能。对于特定主机数目M，当检测得到M个主机时，检测正确，否则检测错误。假设检测次数为N，检测正确的次数为P，第n次检测得到的主机数为Xn，准确率α和偏差值δ定义如式(7)所示:

选取主机数目M范围为[1，20]，检测次数N=500，统计算法的检测准确率和偏差值如图5所示。从图中可以看出，本文算法检测的准确率要高于Bursztein算法和Wicherski算法，检测的偏差值要小于Bursztein算法和Wicherski算法，这说明本文算法性能要优于这两种传统算法。

图5 实验结果对比图Fig.5 Comparison results on experimental network

选定主机数目为M=10，查看检测结果的分布如图6所示。从检测的分布图可以看出本文算法的分布较为集中，而其他两种算法得到分布较为分散，这进一步表明本文算法性能更好。

图6 主机数目为10时检测结果分布对比图Fig.6 Distributions comparison with 10 hosts

由于Bursztein算法是根据数据点之间的时间戳差和接收时间差来判断是否其是否属于同一主机，当多个主机的时间戳相差较小时，Bursztein算法会将这些数据都归于同一主机，从而发生误判。Wicherski算法是基于同一连接属于同一主机这一假设，在短连接条件下数据点较少使得拟合误差较大，进而引起误判。而本文算法是基于Hough变换进行直线检测，即使存在主机时间戳相差较小或存在大量短连接的情况，从图像上依然可以较为准确地区别出不同的直线。

检测图像大小W×H和邻域半径ε是本文算法非常关键的参数，选择不同的参数组合对其灵敏度进行分析。图7(a)为单独改变图像大小的实验结果，图7(b)为单独改变邻域半径的实验结果。从理论上讲，基于Hough变换对直线进行检测要求映射后的图像分辨率适中，当图像上的点过于稀疏时，检测会发生一定偏差。实验结果显示图像大小对算法准确率影响不大。检测邻域半径ε决定着放大的区域，当ε过小时，放大区域包含数据可能不完整，而过大时，放大区域可能包含额外的数据，这些都会对检测结果产生影响。实验结果表明，适中的邻域半径能够达到最好的检测效果。

图7 不同参数条件下检测结果对比Fig.7 Comparison results with various parameter settings

5 结束语

针对NAT主机数目检测问题，本文利用TCP时间戳与数据包接收时间之间存在的线性关系，提出了一种基于Hough变换的NAT主机数目自动识别算法。与以往工作相比，该算法解决了多个主机时间戳相距较近以及短连接导致误识别的问题。实验测试结果表明了算法的有效性，且性能优于已有算法。

本文算法并不局限于对TCP时间戳序列进行分析，它可以很容易地扩展至IPID序列和TCP初始序号序列的线性关系自动识别中。下一步工作将考虑利用更多的可用先验信息，从而进一步提高算法的性能。

[1]RFC 1631，The IP Network Address Translator(NAT)[S].

[2]焦程波，郑辉，黄宇.被动式远程网络地址翻译器识别系统[J].电子科技大学学报，2012(6):899－904.JIAO cheng － bo，ZHENG Hui，HUANG Yu.Novel passive remote network address translation detecting system[J].Journal of University of Electronic Science and Technology of China，2012(6):899 －904.(in Chinese)

[3]Detection of NAT devices[EB/OL].[2014 －06 －07].http://www.muni.cz/ics/research/projects/4622/web/natdet.

[4]Li R，Zhu H L，Xin Y，et al.Remote NAT detect algorithm based on support vector machine[C]//Proceedings of International Conference on Information Engineering and Computer Science(ICIECS).Wuhan:IEEE，2009:1 －4.

[5]高骥翔.基于网络流量特征的NAT识别方法[D].成都:电子科技大学，2012.GAO Jixiang.NAT Detection Based on Network Traffic Feature[D].Chengdu:University of Electronic Science and Technology of China，2012.(in Chinese)

[6]Detecting NAT Devices using sFlow[EB/OL].[2014 －06 －07].http://www.sflow.org/detectNAT/.

[7]Abt S，Dietz C，Baier H，et al.Passive remote source NAT detection using behavior statistics derived from NetFlow[M]//Emerging Management Mechanisms for the Future Internet.Berlin:Springer，2013:148 －159.

[8]Krmicek V，Vykopal J，Krejci R.Netflow based system for NAT detection[C]//Proceedings of the 5th International Student Workshop on Emerging Networking Experiments and Technologies.New York:ACM，2009:23 －24.

[9]Li R，Zhu H L，Xin Y，et al.Passive NATted hosts detect algorithm based on directed acyclic graph support vector machine[C]//Proceedings of 2009 International Conference on Multimedia Information Networking and Security.Wuhan:IEEE，2009:474 －477.

[10]Gokcen Y，Foroushani V A，Heywood.Can we identify NAT behavior by analyzing Traffic Flows[C]//Proceedings of 2014 IEEE Security and Privacy Workshops.San Jose:IEEE，2014:132 －139.

[11]Bellovin S.A technique for counting NATted hostes[C]//Proceedings of the 2nd ACM SIGCOMM Workshop on Internet Measurement.New York:ACM，2002:267－272.

[12]Mongkolluksamee S，Fukuda K，Pongpaibool P.Counting NATted hosts by observing TCP/IP field behaviors[C]//Proceedings of 2012 IEEE International Conference on Communications(ICC).Ottawa:IEEE，2012:1265－1270.

[13]Beverly R.A robust classifier for passive TCP/IP fingerprinting[M]//Passive and Active Measurement.Berlin:Springer，2004:158 －167.

[14]Maier G，Schneider F，Feldmann A.NAT Usage in Residential Broadband Networks[M]//Passive and Active Measurement.Berlin:Springer，2011:32 －41.

[15]白雪，钱步仁，梁华庆.一种检测NAT后主机数目的方案[J].计算机安全，2009(4):46－48.BAI Xue，QIAN Buren，LIANG Huaqing.A scheme for counting NATted hosts[J].Computer Security，2009(4):46 －48.(in Chinese)

[16]Kohno T，Broido A，Claffy K.Remote physical device fingerprinting[J].IEEE Transactions on Dependable and Secure Computing，2005，2(2):93 －108.

[17]Bursztein E.Time has something to tell us about network address translation[EB/OL].(2007－07－08)[2014－ 06 － 07].http://cdn.1y.tl/publications/time － has－something－to－tell－us－about－network－ address－ translation.pdf.

[18]Wicherski G，Weingarten F，Meyer U.IP agnostic realtime traffic filtering and host identification using TCP timestamps[C]//Proceedings of 2013 IEEE 38th Conference on Local Computer Networks.Sydney:IEEE，2013:647－654.

[19]RFC 1323，TCP extensions for high performance[S].

[20]Duda R O，Hart P E.Use of the hough transformation to detect lines and curves in pictures[J].Communications of the ACM，1972(15):11－15.