袁福祥，劉粉林，劉翀，劉琰，羅向陽

MLAR：面向IP定位的大規(guī)模網(wǎng)絡別名解析

袁福祥1,2，劉粉林1,2，劉翀1,2，劉琰1,2，羅向陽1,2

（1.信息工程大學網(wǎng)絡空間安全學院，河南 鄭州 450001；2. 數(shù)學工程與先進計算國家重點實驗室，河南 鄭州 450001）

為準確高效地對接口IP進行別名解析，支撐IP定位，提出一種大規(guī)模網(wǎng)絡別名解析算法（MLAR）?；趧e名IP與非別名IP的時延、路徑、Whois等的統(tǒng)計差異，設計過濾規(guī)則，在解析前排除大量不可能存在別名關系的IP，提高解析的效率；將別名解析轉(zhuǎn)化為分類，構建時延相似度、路徑相似度等四維新穎的特征，用于過濾后可能的別名IP和非別名IP的分類?；贑AIDA百萬級樣本的實驗表明，相比RadarGun、MIDAR、TreeNET，正確率提高15.8%、4.8%、5.7%，耗時最多降低77.8%、65.3%、55.2%；在應用于IP定位時，SLG、LENCR、PoPG這3種典型定位方法的失敗率降低65.5%、64.1%、58.1%。

別名解析；IP定位；網(wǎng)絡拓撲；網(wǎng)絡測量；機器學習

1 引言

準確地刻畫路由器級網(wǎng)絡拓撲，對于分析網(wǎng)絡的結構特性、感知網(wǎng)絡的動態(tài)變化等十分重要[1-3]?，F(xiàn)有的許多IP定位方法如SLG[4]、LENCR[5]、PoPG[6]等往往依賴于路由器、網(wǎng)絡地標（經(jīng)緯度已知的穩(wěn)定公網(wǎng)IP）及待定位目標間的連接和時延關系，對目標IP實施定位。由于商業(yè)隱私保護等，路由器間的真實連接情況及對應的拓撲難以獲取，研究者通常通過主動探測的方式進行推測。但路由器往往有多個接口，每個接口至少配置一個IP[7]，這些IP互為別名關系，通過探測獲取到的拓撲為IP接口級網(wǎng)絡拓撲，而非實際的路由器級拓撲，因此無法滿足基于路由器級拓撲的IP定位的需求。為了將IP接口級網(wǎng)絡拓撲轉(zhuǎn)化為路由器級網(wǎng)絡拓撲，需進行別名解析，即分析哪些IP存在別名關系，判定哪些接口IP實際屬于同一臺路由器。開展對路由器別名IP進行準確、高效的發(fā)現(xiàn)及識別技術研究，對于獲取真實的路由器級網(wǎng)絡拓撲，進而利用拓撲中節(jié)點間的連接關系準確地定位目標IP、追蹤敏感用戶、維護網(wǎng)絡空間安全具有重要意義[8-15]。

現(xiàn)有典型的別名解析方法分為基于主動探測和基于被動分析兩類?；谥鲃犹綔y的方法主要通過對接口IP的探測獲取響應報文，并基于響應報文首部源地址字段、標識字段以及可選字段等特點，進行別名解析；基于被動分析的方法則基于路由器主機名的命名規(guī)則、IP地址指派慣例及網(wǎng)絡構成，以及網(wǎng)絡圖結構等分析結果，進行別名解析。

典型的基于主動探測的別名解析方法如下。① 基于響應報文首部源地址字段的方法（如Mercator[16]、Iffinder[17]等），利用對路由器接口IP進行UDP高端口探測時，響應報文首部的源地址字段可能出現(xiàn)另一接口IP這一特性，通過對比探測目的IP和響應報文中的源地址IP，進行IP間別名關系判別。對該方法實際測試時發(fā)現(xiàn)，只有約66％的目的IP地址響應UDP高端口探測，這其中只有23％的地址返回原始目的IP以外的接口IP。②路由器多個接口IP通常共用唯一的計數(shù)器，每產(chǎn)生一個報文，計數(shù)器會在報文首部的IP標識字段（IP-ID，IP identification）設定相應的數(shù)值，若報文是連續(xù)的，該IP-ID值往往連續(xù)且線性增加?；跇俗R字段的方法則根據(jù)該特點，對可能存在別名關系的IP在較短的時間內(nèi)相繼發(fā)送多個請求報文，通過分析不同的響應報文中的IP-ID值，進行別名解析。例如，Ally[18]認為如果來自兩個IP的響應報文中IP-ID值有序并且鄰近，則該兩個IP為別名；RadarGun[19]認為兩個IP的多個響應報文中IP-ID序列較為相似，則該兩個IP為別名；MIDAR[20]則認為當IP-ID序列的單調(diào)變化趨勢相似時，兩個IP為別名。但RadarGun的作者指出，在測試中，只有31%的接口IP地址共享計數(shù)器；MIDAR中指出，僅約80.6％的接口IP會對探測返回可用于單調(diào)變化趨勢判別的IP-ID序列。③基于可選字段的方法如SideCar[21]、RIPAPT[22]、Pythia[23]等，則分別利用該字段可設置如記錄路由、時間戳等報文控制信息，并依據(jù)記錄結果中的接口IP、時間戳等信息對IP進行別名解析。但TreeNET[24]中指出，為了安全起見，大多數(shù)網(wǎng)絡設備阻止數(shù)據(jù)包進行選項設置，一般會直接丟棄帶有選項設置的報文。尤其自2014年2月以來，國際互聯(lián)網(wǎng)工程任務組（IETF，The Internet Engineering Task Force）建議網(wǎng)絡設備使用這種策略，致使這些方法幾乎不再可用。

公開發(fā)表的基于被動分析的別名解析方法相對較少，代表性的有：基于路由器主機名命名規(guī)則的方法認為主機名相同或命名規(guī)則相似的IP為別名[25]，基于IP地址指派慣例及網(wǎng)絡構成的方法認為屬于同一個/30或/31網(wǎng)段中的IP為別名關系[26]，基于圖結構分析的方法則通過對接口IP間連接關系的分析進行別名解析[27]。然而，通過大量的測試發(fā)現(xiàn)，路由器主機名難以獲取，命名規(guī)則不夠規(guī)范，路由器存在大量未知接口（遠超過4個），或無法得到接口IP間穩(wěn)定的連接關系的情形十分普遍，導致在解析的準確性方面，僅基于主機名、/30或/31子網(wǎng)的IP分配，及圖結構進行被動分析的別名解析方法不如基于主動探測的別名解析方法。

通過上述分析可知，在真實網(wǎng)絡環(huán)境下，現(xiàn)有別名解析方法并不總能夠獲取到用于解析的相關數(shù)據(jù)，其準確性難以保證。研究者試圖通過增加大量的探測或分析來解決該問題，但收效甚微，還引入大量的資源開銷，同時大大降低了方法的效率。此外，在實際應用時，絕大部分現(xiàn)有別名解析方法在處理大量接口IP時，由于并不知道哪些IP之間存在別名關系，對任意一對IP，這些方法往往需要對其進行別名關系判別，在別名解析前通過一系列特定的規(guī)則進行非別名IP過濾的方法非常少，個別典型方法如文獻[28]的過濾效果仍然有待提高。這樣，隨著接口IP數(shù)量的增加，低效的別名解析難以適用于大規(guī)模網(wǎng)絡。

上述問題的存在，使現(xiàn)有別名解析方法在實際應用時的準確率、效率一般，難以滿足大規(guī)模網(wǎng)絡的別名解析需求，從而影響了IP定位等實際應用的效果。例如，在使用SLG、LENCR、PoPG等基于路由器連接的目標IP定位時，由于無法準確高效地對大量的路由器接口IP進行別名解析，導致無法找到地標與目標IP間的共同路由器，不能根據(jù)地標位置估計目標IP的位置，從而造成基于共同路由器的定位方法失敗。因此，有必要設計一種準確高效、適用于大規(guī)模網(wǎng)絡的別名解析算法，以獲取準確的路由器級網(wǎng)絡拓撲，為目標IP定位等實際應用提供可靠的支撐。

針對上述問題，本文提出面向IP定位的大規(guī)模網(wǎng)絡別名解析算法MLAR（machine learning-based alias resolution）。MLAR利用別名IP及非別名IP在直接時延、探測路徑、Whois、主機信息等較容易獲取的數(shù)據(jù)的統(tǒng)計差異，實現(xiàn)對大規(guī)模接口IP相對準確高效的別名解析，從而獲取較為真實的路由器級網(wǎng)絡拓撲，準確定位目標IP。本文主要貢獻及創(chuàng)新之處如下。

1) 提出了一種面向IP定位的大規(guī)模網(wǎng)絡別名解析算法MLAR。MLAR可對大規(guī)模網(wǎng)絡中的路由器接口IP進行準確、高效的別名解析，從而對大規(guī)模網(wǎng)絡的路由器級網(wǎng)絡拓撲進行準確的刻畫，支撐基于網(wǎng)絡拓撲的IP定位等應用。

2) 設計了提高別名解析效率的過濾規(guī)則。根據(jù)接口IP所屬ISP、探測路徑及對應路由器主機信息的特性設計過濾規(guī)則，在進行別名解析之前，可依據(jù)規(guī)則排除不可能存在別名關系的IP對，從而減少別名解析的工作量，提高別名解析的效率。

3) 構建了用于對別名IP及非別名IP進行分類的四維特征向量。根據(jù)別名IP與非別名IP在直接時延、探測路徑等較易于獲取的數(shù)據(jù)方面的統(tǒng)計差異，將別名解析問題轉(zhuǎn)化為機器學習中的分類問題，構建了分類特征向量，訓練分類模型并用于對大規(guī)模網(wǎng)絡的接口IP進行別名解析，提高別名解析的準確率。

2 別名IP與非別名IP的差異分析

本節(jié)對路由器接口IP的直接時延、探測路徑、Whois信息、IP對應路由器主機信息等大量相關數(shù)據(jù)進行統(tǒng)計分析，并對別名IP與非別名IP在這些數(shù)據(jù)方面的統(tǒng)計差異進行詳細介紹。

2.1 直接時延

從源IP向目的IP發(fā)送請求數(shù)據(jù)包，目的IP會對請求進行響應，通過該過程中目的IP對請求的響應時間，可得到源IP與目的IP之間的直接時延[29]。該時延與源IP和目的IP之間的距離有較大關系，在網(wǎng)絡性能良好、擁塞不明顯的情況下，地理距離越大，數(shù)據(jù)包在源IP與目的IP間傳輸消耗的時延越大[30-31]。同一源IP到處于相同地理位置的兩個目的IP的時延往往相似，而到不同位置的目的IP的時延總會存在一定差異（除非目的IP大致分布于以源IP為圓心，源IP與目的IP距離為半徑的圓上）。存在別名關系的IP，配置在同一個路由器的不同接口上，其地理位置相同，因此兩個別名IP相對于同一源IP的時延相似，而不存在別名關系的IP之間不具有這種相似性。

本文獲取了大量位于中國及美國的別名IP及非別名IP樣本，從不同的探測源獲取到每個IP的時延，并計算一對別名及非別名IP間的時延差值。分別取10 000對上述差值，圖1為差值對比，其中“+”代表一對非別名IP間的時延差值，“○”則代表一對別名IP間的時延差值。圖1(a)中樣本位于中國北京，探測源位于成都；圖1(b)中樣本位于美國紐約，探測源位于亞特蘭大。由圖1可看出，同一探測源到一對別名IP的時延大多較為相似，差值較小，約小于5 ms，而到一對非別名IP的時延相似程度較低，時延差值較大。由圖1可得，從不同探測源獲取別名IP間及非別名IP間的時延差值往往存在明顯的差異，這種差異可用于區(qū)分別名IP與非別名IP。

圖1 不同城市的別名IP與非別名IP時延差值對比

Figure 1 Comparison of delay difference between alias IP and non-alias IP in different cities

2.2 探測路徑

路由器主要負責為轉(zhuǎn)發(fā)的每個數(shù)據(jù)包尋找一條最佳的傳輸路徑，從而將數(shù)據(jù)包高效地傳送到下一跳。為了能夠快速選擇出最佳路徑，路由器中保存了包含數(shù)據(jù)轉(zhuǎn)發(fā)策略的路由表，供路由選擇時使用[32]。通常，該路由表在相當一段時間內(nèi)是不變的，即路由節(jié)點的下一跳是相對固定的。從源IP到目的IP，通常會經(jīng)過多個路由器，由于每個路由節(jié)點的下一跳在一段時間內(nèi)相對固定，那么從源IP到目的IP的整條路徑也是固定的。

別名IP，被配置在同一路由器上，無論其地理位置，還是在拓撲中的邏輯位置都是相同的。根據(jù)上述路徑的穩(wěn)定性可知，從同一源IP到別名IP的探測路徑應相同或極為相似，而到非別名IP的路徑相似度應相對較低。利用traceroute，獲取從同一探測源到大量接口IP的探測路徑。對這些路徑進行分析發(fā)現(xiàn)，其相似程度可分為如下A~D這4種情況，圖2為不同情況的示意。其中，由于路徑的方向是由所經(jīng)過的路由器決定的，因此，本當兩條路徑不同的路由IP數(shù)量小于或等于2時，路徑的方向是相似的，當兩條路徑的跳數(shù)差異小于或等于2時，路徑的長度是相似的。

圖2 兩個IP的探測路徑相似性分析

Figure 2 Similarity analysis of probe paths between two IP

A：兩個接口IP的探測路徑方向、長度極為相似。如圖2(a)所示，從探測源T到IP1，IP2的探測路徑，跳數(shù)基本相同，且對應的每一跳基本是同一路由節(jié)點。

B：兩個接口IP的探測路徑方向相似，但長度不相似。如圖2(b)所示，從探測源T到IP1，IP2的探測路徑，跳數(shù)差異較大，但初始的多跳路由節(jié)點基本相同。

C：兩個接口IP的探測路徑長度相似，但方向不相似。如圖2(c)所示，從探測源T到IP1，IP2的探測路徑，跳數(shù)基本相同，但對應的每一跳幾乎是不同一路由節(jié)點。

D：兩個接口IP的探測路徑方向、長度都不相似。如圖2(d)所示，從探測源T到IP1，IP2的探測路徑，跳數(shù)存在一定差異，且對應的每一跳是不同一路由節(jié)點。

對于上述4種情況，A中兩個接口IP很大程度上存在別名關系，而C、D中兩個IP一般不可能存在別名關系。對于B，當探測路徑跳數(shù)相差較少時，該兩個IP可能存在別名關系，當路徑跳數(shù)相差較大，如3跳及以上時，該兩個IP幾乎不可能存在別名關系，還有一種極端的情況是兩個接口IP出現(xiàn)在同一條路徑上，此時兩個IP被配置在不同的路由器上，不可能存在別名關系。對1×106對別名IP及非別名IP的探測路徑進行統(tǒng)計分析，對應不同路徑相似程度的IP對所占比例如表1所示。

表1列出了別名IP及非別名IP的探測路徑相似程度對應A、B、C、D的比例，以及每種情況下路徑的方向及長度的不同相似程度的具體比例。由表1的統(tǒng)計結果可得，所有的別名IP對的路徑相似程度都屬于A或B，但屬于A的占98.1%，而屬于B的僅占1.9%，且非別名IP對中，路徑相似程度屬于A的僅有0.4%，而有13.1%的屬于B，這說明兩個IP探測路徑相似程度屬于A時，很大程度上可能互為別名，屬于B時是否為別名存在一定的不確定性，而當屬于C或D時，基本不會成為別名。這種別名IP及非別名IP在探測路徑的方向、長度方面相似程度的差異，可用于過濾不可能存在別名關系的IP，以及判別IP間是否存在別名關系。

表1 路徑相似程度統(tǒng)計

2.3 Whois信息

IP的Whois信息，即IP的詳細數(shù)據(jù)信息，主要包括IP所屬單位描述、IP的持有者及相關信息、信息最后修改時間等。存在別名關系的IP，被配置在同一個路由器上，其Whois信息往往相同，而非別名IP的Whois信息差異較為明顯。對1×106對別名IP及非別名IP的Whois信息進行統(tǒng)計，結果如表2所示，由表可以看出，至少有98.4%的別名IP對的Whois信息基本一致，相同的信息條數(shù)≥15，而約93.9%的非別名IP對的Whois信息僅有4項相似，如技術聯(lián)系人、通信地址等。盡管非別名IP間也存在個別的信息項相同，但總體而言，別名IP對與非別名IP對在Whois信息相似程度方面的差異，可以為別名解析提供幫助。由于IP的Whois信息無須通過探測獲取，僅通過查詢Whois信息庫即可得到，因此即使在待解析的路由器接口IP對探測無響應時，仍能夠在一定程度上利用Whois信息進行IP間別名關系的判別。

表2 相同Whois信息項的條數(shù)統(tǒng)計

2.4 路由器主機信息

作為網(wǎng)絡中重要的“樞紐”，路由器主要負責網(wǎng)絡中數(shù)據(jù)包的轉(zhuǎn)發(fā)。像計算機使用Windows、Linux等作為操作系統(tǒng)一樣，在路由器上，也有軟件在運行，可以等同地認為它們就是路由器的操作系統(tǒng)，這種系統(tǒng)主要負責完成路由表的生成和維護，如FreeBSD、Juniper JUNOS、OpenBSD等[33]。不同路由器的操作系統(tǒng)可能不同，存在別名關系的IP對應的路由器其操作系統(tǒng)一定相同。

為了提供多種服務，滿足不同的網(wǎng)絡需求，路由器會開放多個端口，不同的路由器開放的端口可能不一樣，存在別名關系的IP對應的路由器，其開放的端口及對應端口的狀態(tài)一定相同。此外，在相同時刻，存在別名關系的IP對應的路由器的運行狀態(tài)（即在線或者離線）是一致的，而不存在別名關系的IP對應的路由器，可能由于斷電或網(wǎng)絡中斷等導致其運行狀態(tài)不一致。

同樣地，分別對1×106對別名IP及非別名IP的主機信息進行統(tǒng)計后發(fā)現(xiàn)，約89.8%的別名IP對應的路由器的操作系統(tǒng)信息一致，約96.6%的別名IP對應的路由器的端口開放情況完全一致，所有的存在別名關系的一對IP對應的路由器的運行狀態(tài)完全一致，而非別名IP對應的路由器上述信息一致的比例分別僅為12.1%、6.9%、1.0%，差異較為明顯。

IP所屬的互聯(lián)網(wǎng)服務提供商（ISP，internet service provider）信息，也可用于判別IP間是否存在別名關系。配置在同一路由器上的IP，往往屬于同一ISP（骨干網(wǎng)路由器除外，因為個別骨干路由器不同接口IP可能屬于不同ISP）。若某兩個接口IP不屬于同一ISP，則該兩個IP不存在別名關系。

通過上述統(tǒng)計分析可知，別名IP的直接時延、探測路徑、Whois信息、路由器主機信息等數(shù)據(jù)相似性較高，而非別名IP間的這種相似性往往較低，這些明顯的差異可用于區(qū)分別名IP與非別名IP。

3 MLAR算法

基于第2節(jié)中給出的別名IP與非別名IP在直接時延、探測路徑等方面存在的差異，提出了基于機器學習的別名解析算法MLAR。MLAR給出了一組非別名IP過濾規(guī)則，排除不存在別名關系的IP，減少別名解析的工作量，提高別名解析的效率；MLAR將別名判別問題轉(zhuǎn)化為分類問題，將別名IP對作為正例樣本，非別名IP對作為負例樣本，構造了用于對別名IP對和非別名IP對進行分類的四維特征，對利用規(guī)則過濾后剩余的IP對進行別名解析。

3.1 MLAR基本原理與主要步驟

MLAR算法主要包括樣本集合構造、相關數(shù)據(jù)獲取、非別名IP過濾、分類特征表示等步驟，具體如下，其原理框架如圖3所示。

圖3 MLAR的原理框架

Figure 3 The principle framework of MLAR

輸入 別名IP及非別名IP樣本集，待解析路由器接口IP集S

輸出S中接口IP的別名解析結果

Step 1 樣本集合構造。從公開數(shù)據(jù)源或路由節(jié)點已知的網(wǎng)絡獲取特定目標區(qū)域內(nèi)一定數(shù)量存在別名關系的接口IP對，構成集合0；同時，獲取一定數(shù)量的不存在別名關系的IP對，構成集合1；總的樣本集合=0∪1。區(qū)域內(nèi)待解析的所有路由器接口IP構成集合S。

Step 2 相關數(shù)據(jù)獲取。分布式部署多個探測源，對集合及S中的接口IP進行探測，獲取從源IP到接口IP的時延和路徑；通過查詢相關IP信息庫，獲取每個接口IP所屬ISP及Whois信息；通過探測源對接口IP對應的路由器主機進行監(jiān)測，獲取其操作系統(tǒng)版本、端口開放情況以及主機運行狀態(tài)等信息。

Step 3 非別名IP過濾。對S中的任意接口IP進行兩兩組合，并利用Step 2獲取的數(shù)據(jù)，對IP所屬ISP、探測路徑及對應主機運行狀態(tài)進行統(tǒng)計。根據(jù)設計好的過濾規(guī)則，排除不存在別名關系的接口IP，剩余IP構成集合S。

Step 4 分類特征表示。"(IP, IP)∈∪S，利用IP, IP的時延、探測路徑、Whois、路由器主機等信息，根據(jù)設計好的分類特征生成方法，為樣本(IP, IP)構造特征向量,(1,2,3,4)。獲得中所有IP對的特征向量，構造集合。同樣，對于過濾后生成的集合S中的IP對，構造集合F。分類特征如表3所示。

Step 5 分類模型訓練。不同的分類器特點不同，對相同樣本的分類效率及效果會存在一定的差異（通常，線性分類器的效率相對較高。在線性分類器中，不同的分類器對數(shù)據(jù)缺失、噪聲等因素的敏感程度不同）。為保證良好的分類效率，同時結合Step 2中所獲取的相關數(shù)據(jù)的特點，如數(shù)據(jù)規(guī)模、數(shù)據(jù)缺失程度、噪聲數(shù)據(jù)的比例等，選擇合適的線性分類器。將特征向量集合作為分類器的輸入，對分類器進行訓練，得到分類模型Model。

Step 6 別名解析。對于集合S中待解析的IP對，將其特征向量集合F輸入已訓練好的模型Model，得到分類結果，即任意一對IP的別名解析結果。

上述步驟中，非別名IP過濾及分類特征的表示是算法最為關鍵的環(huán)節(jié)，3.2節(jié)和3.3節(jié)將對這兩部分分別進行具體闡述。

表3 特征集合

Figure 4 Comparison of the number of possible aliases with the actual number of aliases

3.2 非別名IP過濾

通過上述分析可知，若能夠在別名解析之前，盡可能地過濾掉不可能存在別名關系的IP對，則可以減少別名解析工作量，顯著提高別名解析的效率?；诘?節(jié)的統(tǒng)計分析，給出一組非別名IP過濾規(guī)則。對待判別IP對，通過如下規(guī)則進行過濾，排除不可能存在別名關系的IP對。設兩個路由器接口IP分別為IP1、IP2，IFalias(IP1, IP2)表示判別IP1與IP2是否存在別名關系的布爾型函數(shù)，若IFalias(IP1, IP2)=1，IP1與IP2存在別名關系；若IFalias(IP1, IP2)=0，IP1與IP2不存在別名關系，則有如下規(guī)則。

1) 由于同一路由器的不同接口IP屬于同一ISP，因此不屬于同一ISP的任意兩個非骨干路由接口IP不存在別名關系，即設ISP(IP)表示IP所屬的ISP，對于"IP1、IP2，若ISP(IP1)≠ISP(IP2)，則IFalias(IP1, IP2)=0。

2) 探測路徑中每一跳IP屬于不同的路由器，因此出現(xiàn)在同一條探測路徑中的兩個接口IP不存在別名關系，即設PATH表示一條探測路徑中的所有路由器IP構成的集合，對于"IP1、IP2，若(IP1?PATH)∧(IP2?PATH)，則IFalias(IP1, IP2)=0。

3) 同一探測源到同一路由器不同的接口IP的路徑方向相似，因此從同一探測源獲取的任意兩條路徑，其相同跳的IP不同的情況出現(xiàn)次數(shù)大于或等于3時，兩個接口IP不存在別名關系，即設List(IP)表示IP的探測路徑中所有中間路由器IP按從源IP向IP1的順序構成的集合，對于"IP1、IP2，設(List(IP1), List(IP2))表示List(IP1)與List(IP2)的不同元素構成的集合，若有|(List(IP1), List(IP2))|≥ 3，則IFalias(IP1, IP2)=0。

4) 同一探測源到同一路由器不同的接口IP的路徑長度相似，從同一探測源獲取的路徑的跳數(shù)差異大于或等于4時，兩個接口IP不存在別名關系，即設Len_T(IP)表示從探測源到IP的探測路徑的跳數(shù)，對于"IP1、IP2，若|Len_T(IP1)-Len_T(IP2)| ≥ 4，則IFalias(IP1, IP2)=0。

5) 在相同時刻，存在別名關系的IP對應同一臺路由器，其運行狀態(tài)是確定的，因此，對應主機運行狀態(tài)不同的任意兩個接口IP不存在別名關系，即設Status_t(IP)表示IP對應的主機在特定時刻的運行狀態(tài)的布爾型函數(shù)，Status_t(IP)=1，則主機在線，Status_t(IP)=0，則主機離線，若Status_t(IP1)≠Status_t(IP2)，則IFalias(IP1, IP2)=0。

對于待判別的IP集合及任意組合的一對IP，使用上述規(guī)則，進行過濾。需要說明的是，以上規(guī)則是有先后順序的。這是因為規(guī)則1)中IP所屬ISP可以通過查詢現(xiàn)有的數(shù)據(jù)庫獲??；規(guī)則2)、3)、4)為確保準確性，綜合采用多個探測源并行探測，并根據(jù)探測結果進行判別，耗時較少；相對而言，規(guī)則5)則需要對IP對應的主機監(jiān)測一段時間，因此將其放在最后進行，且僅對通過規(guī)則1)~4)過濾后的IP進行監(jiān)測。由2.2節(jié)的分析及表1統(tǒng)計結果可知，通常探測路徑的跳數(shù)差異大于或等于3時，兩個IP基本不存在別名關系，但為了降低個別特殊IP對帶來的誤判，在規(guī)則4)中，進一步將閾值增大為4。在MLAR中，依據(jù)上述過濾規(guī)則，排除不存在別名關系的IP對后，對剩余的IP對，利用3.3節(jié)中設計的分類特征表示方法，生成特征向量，進行分類及別名解析。

3.3 分類特征表示

基于第2節(jié)中對接口IP的時延、路徑、Whois、對應主機等信息的統(tǒng)計分析，本文給出了用于對別名IP和非別名IP進行分類的四維特征：時延相似度、路徑相似度、Whois信息相似度和主機信息相似度。之所以設計這樣四維特征并用于分類，是因為盡管大量的統(tǒng)計分析表明，別名IP與非別名IP在時延、路徑等多種數(shù)據(jù)方面存在差異，所獲取的各類數(shù)據(jù)仍可能會受到如時延膨脹、探測路徑的完整性、Whois的更新頻率以及主機的監(jiān)測時長等不同因素的影響，但這些因素將僅僅影響到相關的單維特征的分類效果；四維特征間的相關性較弱，不會相互影響。因此，在避免特征冗余的情況下，通過將多維特征用于分類，使在個別單維特征受到影響時，最終依然有望獲取到相對較好的分類效果。此外，所設計的四維特征對于分類是互補的，通過時延、路徑相似度可準確識別出地理分布不臨近的非別名接口IP，在此基礎上，Whois、主機信息相似度能夠進一步將別名IP和非別名IP區(qū)別開。本節(jié)對特征的表示進行具體介紹。

3.3.1 時延相似度

由2.1節(jié)的統(tǒng)計分析可知，同一源IP到存在別名關系的兩個IP的時延往往較為相似，到不存在別名關系的兩個IP的時延相似度較低，但受實際網(wǎng)絡狀況對時延的影響，仍有個例不符合該規(guī)律。僅利用單一源IP到任意兩個IP的時延相似度，難以判別IP間是否存在別名關系。而從多個源IP分別獲取到兩個IP的時延相似度，能夠減少網(wǎng)絡狀況的影響。為此，對待判別的IP對，采取從多個不同位置的源IP，分別獲取到兩個IP的時延。對于其中的每個IP，利用獲取到的多個時延，為該IP構造時延向量。對待判別的兩個IP，計算其時延向量的相似度，并作為一維分類特征，具體如下。

設任意兩個待解析的IP為IP, IP，分布式部署個位于不同位置的探測源1~N，從每個探測源分別對這兩個IP進行多次探測，對每個IP獲取一個最小時延，以盡可能減小網(wǎng)絡擁塞等影響。對于IP，其個最小時延為t,1,t,2, …,t,n，對于IP，其個最小時延為t,1,t,2, …,t,n。為IP, IP構造時延向量(t,1,t,2, …, t,k, …,t,n),(t,1,t,2, …, t,k, …,t,n)。利用式(1)計算D與D的相似度S，將其作為特征值。

3.3.2 路徑相似度

由2.2節(jié)的分析可知，一定時間內(nèi)，路由轉(zhuǎn)發(fā)的下一跳往往是不變的，從源IP到目的IP的路徑相對固定。存在別名關系的接口IP處于同一路由器上，當從同一探測源對其進行探測時，探測路徑（方向和長度）往往較為相似。對待解析的IP對，分別獲取不同源IP到兩個接口IP的路徑，并根據(jù)路徑構造向量，從而計算兩個IP的路徑相似度，作為分類特征。

設任意兩個待解析的接口IP為IP, IP，從探測源1~N分別對該兩個IP進行次探測。由于路由器至少擁有兩個接口，一些大型核心骨干路由器通常擁有10~30個接口[7]，為保證能夠盡可能全地發(fā)現(xiàn)探測路徑上每一跳路由器的接口IP，應置探測次數(shù)大于路由器接口數(shù)量，如取=50。本文按如下方式計算從探測源N到IP, IP的路徑相似度。

對于兩個IP的探測路徑，分別取次探測中出現(xiàn)次數(shù)最多的路徑跳數(shù)作為從探測源N到該IP的探測路徑長度，將從N得到的IP, IP的路徑向量分別記為path,n，path,n，path,n表示為(1,n,2,n, …, A,n, …,A,n)，path,n表示為：(1,n,2,n, …, B,n, …, B,n)。其中，，分別為IP, IP路徑的長度，A,，B,分別為兩個IP路徑上第跳出現(xiàn)的所有路由器接口IP構成的集合。若IP, IP為別名IP，則應有A,≈B,n，(A,n∩B,n)≈ (A,n∪B,)，且≈；若IP, IP為非別名IP，則A,與B,，與有一定差異。因此，將從N得到的IP, IP的路徑的相似度S表示為

式(2)中，當<時，置A+1,n~A,n為?；反之，當<時，置B+1,n~B,n為?。最終，IP, IP的路徑相似度S可表示為從個探測源獲取的路徑相似度的平均值，即

3.3.3 Who is信息相似度

通過2.3節(jié)關于IP的Whois信息分析可知，對于大多數(shù)存在別名關系的一對IP，其Whois信息較為一致，但統(tǒng)計發(fā)現(xiàn)，少量不存在別名關系的IP，其個別Whois信息項相同，這可能是由于信息更新不及時等導致。為了更好地根據(jù)Whois信息相似程度判斷IP間是否存在別名關系，對不同的Whois信息項賦權值，計算IP間Whois信息的相似度，并將其作為一維分類特征，具體表示如下。

存在別名關系的兩個IP，當其Whois信息完全相同時，總條數(shù)記為，記第條Whois信息為I，1≤≤。設任意兩個待解析的IP為IP, IP，當其第條信息相同時，有(I)=1，否則(I)=0。

一些不存在別名關系的IP，個別Whois信息項（如所屬網(wǎng)段、網(wǎng)絡名稱、所屬國家、狀態(tài)信息等）可能相同。這幾項信息對于判別IP間是否存在別名關系的貢獻，小于僅當IP間存在別名關系時才會相同的Whois信息，因此本文為不同信息項賦不同的權值。設該4條信息項構成的集合為，則將信息項I的權值(I)表示為

其中，<0.5＜，本文取=0.1，=0.9。對于IP與IP，設其相同信息項構成集合為，則其Whois信息相似度S可表示為

3.3.4 主機信息相似度

根據(jù)2.4節(jié)中大量探測數(shù)據(jù)的統(tǒng)計分析可知，存在別名關系的IP對應的主機，在操作系統(tǒng)版本、端口開放情況以及主機運行狀態(tài)方面，較為一致，尤其在主機運行狀態(tài)和端口開放方面，具有高度的一致性。不存在別名關系的IP，其對應主機的上述信息，往往不同，但個別IP的操作系統(tǒng)版本或部分開放端口相同。因此，為了充分考慮不同主機信息的特點，更好地依據(jù)主機信息對IP間別名關系進行判斷，按如下方式計算IP對應主機的信息相似度。

設任意兩個待解析的IP為IP, IP，從個探測源分別對其進行次探測，并根據(jù)每一次的探測結果，獲取IP對應主機的操作系統(tǒng)版本、端口開放情況以及主機運行狀態(tài)信息。對于任意時刻，只有在IP, IP對應的路由器主機的運行狀態(tài)完全相同的情況下，這兩個IP才有可能配置在同一路由器不同端口上，即存在別名關系。所以，在確保IP, IP對應的主機運行狀態(tài)相同的情況下，根據(jù)主機操作系統(tǒng)版本、開放端口數(shù)量及端口狀態(tài)，計算兩個IP對應的主機信息相似度如下。

考慮到別名IP間，上述信息任意時刻較為相似，而非別名IP則不然，因此，將IP, IP的主機信息相似度Sh表示為所有探測中信息相似度的均值，即

4 實驗設計及結果

為了驗證所提算法MLAR的有效性，本節(jié)給出了多組測試及結果分析。4.1節(jié)介紹了樣本數(shù)據(jù)的來源以及實驗相關的設置；4.2節(jié)分別對算法中的非別名IP過濾規(guī)則，以及別名解析算法的效果進行測試；4.3節(jié)采用幾種不同的方法進行多組別名解析，并從正確率、效率及應用于IP定位的效果等方面，對不同方法進行對比分析。

4.1 實驗設置

實驗中接口IP樣本數(shù)據(jù)主要來源于CAIDA。該網(wǎng)站提供了大量的可靠路由器級網(wǎng)絡拓撲數(shù)據(jù)，其中包含路由節(jié)點，以及節(jié)點的接口IP和位置信息，每個節(jié)點的多個接口IP相互間存在別名關系，通過將同一路由節(jié)點的不同接口IP進行兩兩組合，可構造別名IP集；同時，不同節(jié)點間的接口IP，不存在別名關系，將不同路由節(jié)點的接口IP進行兩兩組合，構造非別名IP集。

為獲取豐富的時延、路徑等探測數(shù)據(jù)，需在待解析的接口IP周圍分散部署多個探測源。對于上述樣本中屬于中國的路由節(jié)點接口IP，在鄭州、北京、上海、廣州、天津、成都等地部署10個探測源，并從每個探測源對各個IP進行探測；同樣地，對于屬于美國的路由節(jié)點接口IP，在紐約、芝加哥、亞特蘭大、華盛頓、邁阿密、西雅圖等地部署10個探測源，并從每個探測源對各個IP進行探測。文獻[34]指出，網(wǎng)絡的路由路徑在短時間內(nèi)（如一個月）是相對穩(wěn)定的。通過對大量探測數(shù)據(jù)的統(tǒng)計分析后發(fā)現(xiàn)，路由路徑的確存在上述穩(wěn)定性。因此，為保證探測數(shù)據(jù)的可靠性，應保證在較短的時間周期內(nèi)對接口IP進行探測。接口IP的ISP、Whois信息，主要通過查詢相關IP信息庫獲取，IP對應的路由器主機信息，則利用Nmap獲取。

表4 實驗設置

利用獲取到的IP的時延、路徑等信息，依據(jù)3.1節(jié)中別名解析算法的具體步驟，對樣本進行如下的別名解析測試。具體的實驗設置如表4所示。

4.2 別名解析測試及結果分析

本節(jié)利用已知樣本，分別對MLAR的非別名IP過濾效果及別名解析效果進行測試，并分析測試結果。

4.2.1 非別名IP過濾測試

MLAR給出了用于非別名IP過濾的規(guī)則，為了驗證所設計規(guī)則的有效性，利用如4.1節(jié)所述的樣本，在獲取到所需相應數(shù)據(jù)后，本節(jié)利用這些規(guī)則進行過濾測試。表5給出了對分布于中國北京、上海及美國紐約、邁阿密的樣本的過濾結果，其中測試時4個城市的別名IP及非別名IP數(shù)量均為1×106對。

分析表5結果可得，僅有個別別名IP對被所設計的規(guī)則當作非別名IP對過濾掉，其中有41對位于中國上海的IP被規(guī)則3)過濾掉，有23對位于美國邁阿密的IP被規(guī)則4)過濾掉，被過濾掉的主要原因是一對IP中的其中一個IP可能由于分組丟失等原因?qū)е绿綔y不通，而另一個探測可達，該情況極少出現(xiàn)；通過規(guī)則1)~5)，4個城市中分別有83.4%、81.7%、84.6%、86.2%的非別名IP對被準確過濾掉。由此可以看出，MLAR給出的過濾規(guī)則能夠準確過濾掉大部分非別名IP對，同時保留別名IP對，使用該規(guī)則，能夠大大減少別名解析的工作量，從而提高效率。

表5 過濾結果

4.2.2 別名解析測試

表6 訓練、測試集構造及對應分類結果

由表6可得，總體而言，MLAR所獲得的正確率較高，漏報率和虛警率較低。上述3組共9次測試的正確率維持在95%~97%，測試a1~a3的平均正確率為95.9%，b1~b3的平均正確率約為96.4%，c1~c3的平均正確率為96.5%。由相同樣本量的測試結果可得，MLAR的性能具有一定的穩(wěn)定性。對比測試a1~a3，b1~b3與c1~c3可以看出，即使使用少量訓練樣本數(shù)據(jù)，也能獲得相對較好的分類模型及分類效果。

4.2.3 不同特征組合的分類效果測試

表7 不同特征組合的分類效果

由表7可得，在使用相同樣本時，利用不同特征組合的分類效果不同，單維特征的分類效果不如多維特征組合的分類效果，采用特征維數(shù)越多，分類效果越好。單維特征對分類的貢獻由高到低依次為：主機信息相似度4、路徑相似度2、Whois信息相似度3、時延相似度1。這主要是由于一段時間內(nèi)IP對應主機信息、探測路徑信息等相對穩(wěn)定可靠，在這些信息方面別名IP與非別名IP的差異明顯，而少量IP的Whois信息更新不及時，網(wǎng)絡擁塞等導致時延測量不夠準確，使在這兩類信息方面別名IP與非別名IP的差異相對弱一些。但由于存在部分非別名IP對應主機信息等高度相似，而其時延相似度可能有較大差異，或路徑信息相似而Whois信息差異明顯等情況，此時采用單維特征難以對別名IP及非別名IP進行分類，采用四維特征的組合進行分類效果更佳，這說明所設計的四維特征不是冗余的。

4.2.4 不同分類算法的分類效果測試

由表8可得，使用所構建的四維特征，采用SVM、LR、NBC這3種不同的分類模型，對不同種類數(shù)據(jù)集的分類正確率都較高。其中，對于CAIDA數(shù)據(jù)集，3種分類器所得平均正確率分別為96.4%、95.7%、95.5%，對于ISP數(shù)據(jù)集，3種分類器所得平均正確率分別約為97.2%、96.8%、97.1%，說明MLAR所構建的分類特征能夠較為可靠地區(qū)分別名IP及非別名IP。使用不同分類模型所得分類結果，漏報率、虛警率都較低，對于CAIDA數(shù)據(jù)集，平均漏報率分別約為3.5%、4.2%、4.4%，平均虛警率分別約為3.8%、4.4%、4.7%。對于ISP數(shù)據(jù)集，平均漏報率分別約為2.6%、3.2%、2.7%，平均虛警率分別約為3.0%、3.3%、3.2%，漏報率都低于虛警率，說明通過MLAR所構建的特征將非別名IP判為別名IP的可能性很小，能夠從路由器接口IP中準確識別出別名IP。

表8 不同分類算法的分類效果

4.3 與現(xiàn)有典型方法的比較

準確、高效的別名解析，對于獲取能夠反映真實網(wǎng)絡結構的路由器級網(wǎng)絡拓撲，從而支撐IP定位意義重大?，F(xiàn)有部分典型方法如RadarGun[19]、MIDAR[20]、TreeNET[24]等，在別名解析方面具有相對良好的效果。本節(jié)從別名解析的正確率和效率，以及對IP定位的幫助等方面，對這幾種方法與MLAR進行測試及對比分析。

4.3.1 別名解析準確性對比

為了驗證所提別名解析算法MLAR的準確性，從4.1節(jié)所述的樣本中取別名IP對及非別名IP對，其中分布于中國的樣本數(shù)量為3×107個，分布于美國的樣本數(shù)量為5×107個。分別利用RadarGun、MIDAR、TreeNET進行5次別名解析；對于MLAR，使用4.2.2節(jié)測試c1中訓練好的分類模型進行5次別名解析。表9給出了不同方法每一次測試對應的正確率、漏報率及虛警率。

由表9可以看出，RadarGun、MIDAR、TreeNET及MLAR都能夠獲得一定的效果，平均的正確率分別約為82.7%、91.4%、90.6%、95.8%，相對而言，MIDAR、TreeNET和MLAR的正確率較高。MLAR相比前3種方法正確率分別平均提高了15.8%、4.8%、5.7%。上述測試結果中， 4種方法的5次測試所得正確率的標準差分別為0.038 0、0.012 9、0.006 2、0.005 6，相比其他兩種方法，TreeNET及MLAR多次測試結果正確率較為一致，具有一定的穩(wěn)定性。此外，在測試時，將別名IP對作為正例樣本，非別名IP對作為負例樣本，結合4.2.2節(jié)的測試結果可得，對MLAR多次測試所得漏報率都低于虛警率，說明雖然MLAR存在將部分別名IP對誤判為非別名IP對的情況，但通過MLAR所獲取的別名IP對較為準確可靠，這對于IP定位尤為重要。

4.3.2 別名解析效率對比

為了驗證MLAR對別名解析的高效性，同樣采用4.1節(jié)所述的樣本數(shù)據(jù)，分別利用RadarGun、MIDAR、TreeNET及MLAR，對不同規(guī)模的網(wǎng)絡（即包含不同數(shù)量的接口IP），在相同的實驗環(huán)境下，分別進行3次測試，并對測試所用時長進行對比分析。考慮到MIDAR需分布式多源探測以提高效率，且MLAR需要通過多個探測源獲取相關數(shù)據(jù)，為了公平比較不同方法的效率，對于MIDAR及MLAR，通過相同配置的10臺主機配合完成測試，而對于RadarGun及TreeNET，則將每一次測試的樣本平均分為10份，分別在上述10臺主機上利用這兩種方法進行別名解析，并記錄10臺主機中的最長耗時。

當網(wǎng)絡規(guī)模不斷增大，接口IP數(shù)量由1×106個遞增到5×106個時，別名IP對的數(shù)量分別為7.325×106，1.901×107，2.421×107，2.944×107，3.602×107；非別名IP對的數(shù)量分別為7.903×108，1.311×109，2.404×109，3.224×109，4.003×109。對于RadarGun和TreeNET，對所有的IP對都要進行解析；MIDAR認為當從兩個目標IP獲得的IP-ID序列變化速率相似度低時，這兩個IP不可能共享IP-ID計數(shù)器，即不存在別名關系，依據(jù)該理論可過濾掉的IP對的比例分別為10.6%，15.3%，25.1%，19.9%，22.10%；而對于MLAR，通過規(guī)則過濾掉的不存在別名關系的IP對的比例分別為67.3%，72.7%，71.4%，69.9%，75.2%。圖5給出了不同方法需要進行解析的樣本數(shù)量，由圖5可以看出，MLAR需要解析的樣本數(shù)量最少。

表10及圖6給出了隨著網(wǎng)絡規(guī)模的增大，接口IP數(shù)量的增加，不同方法3次測試所用時長。

表9 不同方法多次測試結果對比

表10 不同方法效率對比

圖5 不同方法需要進行解析的樣本的比例

Figure 5 The proportion of aliases that need to be resolved by different methods

圖6 不同方法耗時

Figure 6 Duration of different methods

根據(jù)表10及圖6的結果可以看出，接口IP數(shù)量不同，各個方法所用時長不同，且隨著IP數(shù)量的增加，所用時長都在增加，每次測試RadarGun耗時最長，其次為MIDAR、TreeNET，MLAR。由圖中曲線的斜率變化可以看出，相比MLAR，RadarGun、MIDAR、TreeNET所用時長增長的速率較大，當接口IP數(shù)量為1×106個時，RadarGun、MIDAR、TreeNET的平均耗時分別約為MLAR的3.1倍，2.2倍，1.6倍，但當接口IP數(shù)量增加到5×106時，分別增加到了4.2倍，2.6倍，2.1倍。這是為了能夠獲取到IP-ID，RadarGun和MIDAR需要對每個IP進行大量探測，但MIDAR在別名解析前進行了初步的過濾，而RadarGun沒有使用任何過濾機制，因此MIDAR效率高。TreeNET沒有設定過濾規(guī)則，但其根據(jù)IP對探測的響應情況，不完全依賴于IP-ID，還綜合了基于路由器主機名的解析等方法，而這種無須探測的解析效率極高，因此TreeNET總體效率高于MIDAR。對于MLAR，在別名解析前，利用多個探測源的探測結果，平均過濾掉了71.3%的非別名IP對。本文對IP對應主機運行狀態(tài)監(jiān)測時長設定為2.5 h，在監(jiān)測的同時，并行獲取用于別名解析的時延、探測路徑等數(shù)據(jù)，可節(jié)省大量時間，效率最高，且僅當需要解析的IP數(shù)量較大時，耗時才出現(xiàn)明顯變化。

此外，曲線上“I”形的上端和下端分別表示耗時的正方差及負方差值，線上的點表示耗時的均值，通過對比4條曲線可以看出，對于相同接口IP數(shù)量的多次測試，RadarGun、MIDAR耗時最不穩(wěn)定，差異較大，而MLAR耗時相對穩(wěn)定。上述結果在一定程度上說明MLAR在別名解析效率方面有一定優(yōu)勢。

4.3.3 應用于IP定位的效果對比

為了進一步驗證所提別名解析算法MLAR的有效性，本節(jié)對上述幾種方法在實際IP定位中的應用效果進行對比。

文獻[4]提出SLG——一種逐層逼近的街道級定位方法，并在最后一層，將與目標IP存在最近共同路由器且相對時延最小的地標的位置，作為目標的位置估計。由于探測獲取的拓撲實際為路由器接口級拓撲，當?shù)貥伺c目標分別與最近共同路由器的不同接口IP相連時，如果不進行別名解析，則無法得知二者實際與同一路由器相連，因此無法通過地標的位置估計目標IP的位置，定位將失敗。文獻[5]尋找與目標IP存在最近共同路由器且相對時延最小的3個地標，并根據(jù)三點定位思想對目標IP進行街道級定位，與SLG面臨的問題類似，該算法的前提條件也是找到最近共同路由器，因此若想降低定位失敗率，在尋找共同路由器前需要進行別名解析。文獻[6]則利用劃分的PoP對目標IP進行城市級定位，該方法需要通過別名解析，將城市內(nèi)部本應屬于同一個大規(guī)模PoP的多個小PoP進行合并，提高PoP的完整性，并用于IP定位。因此，別名解析的效果將一定程度上決定所獲取PoP的完整性，從而決定IP定位的效果。

表11 定位測試結果對比

將不同的別名解析方法運用到上述3種典型的定位方法中，對實際網(wǎng)絡環(huán)境中的目標IP進行定位測試，并對定位結果進行分析。對于SLG與LENCR，分別在中國北京、美國加利福尼亞州取1 000、3 000個街道級地標作為待定位目標IP，對于PoPG，分別在中國北京、美國加利福尼亞州取50 000個城市級地標作為待定位目標IP，分別對3種方法在使用及不使用別名解析時對目標IP的定位效果進行對比，表11給出了具體的定位結果。

表11給出了在使用及不使用別名解析兩種情況下，3種定位算法對中國北京及美國加利福尼亞州的目標IP進行定位的失敗率。其中，每種定位算法下的數(shù)據(jù)表示在定位過程中，該定位算法使用對應的別名解析方法后，對目標IP定位的失敗率，當別名解析方法為無時，表示在該定位算法的定位過程中，不使用任何的別名解析方法。由表11可以得出，在使用別名解析方法前后，3種定位算法對兩個地區(qū)的目標IP的定位效果差別較大，使用別名解析后，定位失敗率明顯降低。其中，對于SLG，相比未使用別名解析，使用RadarGun、MIDAR、TreeNET及MLAR后定位失敗率平均分別降低了24.2%，45.0%，39.9%，65.5%；對于LENCR，分別平均降低了30.4%，48.4%，42.1%，64.1%；對于PoPG，分別平均降低了25.6%，42.4%，34.2%，58.1%。通過對比發(fā)現(xiàn)，使用所提別名解析算法MLAR后，3種定位算法的定位失敗率降低最多，間接說明了MLAR的別名解析效果最好。

5 結束語

現(xiàn)有一些典型的別名解析方法所需數(shù)據(jù)難以獲取，別名解析準確率難以保證，在解析前未對大量不可能存在別名關系的IP對過濾，別名解析的效率低，導致這些方法難以滿足大規(guī)模網(wǎng)絡的別名解析需求，難以支撐IP定位等實際應用。為此，本文提出了一種面向IP定位的大規(guī)模網(wǎng)絡別名解析算法MLAR。MLAR利用接口IP較易于獲取時延、路徑等相關數(shù)據(jù)，并基于目標區(qū)域內(nèi)別名IP與非別名IP在這些數(shù)據(jù)方面的統(tǒng)計差異，排除大量的非別名IP；利用機器學習對區(qū)域內(nèi)剩余IP對進行別名解析。結合MLAR，本文準確地刻畫大規(guī)模網(wǎng)絡中路由節(jié)點連接及拓撲，從而降低基于路由節(jié)點連接關系的IP定位方法的失敗率。本文采用CAIDA提供的分布于中國和美國一些城市的百萬級樣本數(shù)據(jù)對MLAR進行了測試實驗。結果表明與現(xiàn)有的RadarGun、MIDAR、TreeNET等典型方法相比，MLAR的正確率、效率更高，更適用于大規(guī)模網(wǎng)絡，能夠更好地幫助IP定位。但針對特定目標區(qū)域進行別名解析時，所提算法對區(qū)域內(nèi)已知樣本的數(shù)量仍有一定的要求。此外，網(wǎng)絡擁塞、路由變化、一些數(shù)據(jù)（如Whois）的更新頻率等因素會影響算法的效果。

[1] CANBAZ M A. Internet topology mining: from big data to network science[D]. Reno: University of Nevada, 2018.

[2] KARDES H, GUNES M H, SARAC K. Graph based induction of unresponsive routers in internet topologies[J]. Computer Networks, 2015, 81: 178-200.

[3] COSKUN I E, CANBAZ M A, GUNES M H. Efficient AS network topology measurement based on ingress to subnet reachability[C]// IEEE 41st Conference on Local Computer Networks Workshops. 2016: 87-95.

[4] WANG Y, BURGENER D, FLORES M, et al. Towards street-level client-independent IP geolocation[C]//Symposium on Network System Design and Implementation. 2011: 27-27.

[5] CHEN J, LIU F, SHI Y, et al. Towards IP location estimation using the nearest common router[J]. Journal of Internet Technology, 2018, 19(7): 2097-2110.

[6] YUAN F, LIU F, HUANG D, et al. A high completeness PoP partition algorithm for IP geolocation[J]. IEEE Access, 2019, 7: 28340-28355.

[7] KEYS K. Internet-scale IP alias resolution techniques[J]. ACM Sigcomm Computer Communication Review, 2010, 40(1): 50-55.

[8] MARCHETTA P, PESCAPé A. DRAGO: detecting, quantifying and locating hidden routers in traceroute IP paths[C]// Proceedings IEEE International Conference on Computer Communications. 2013: 3237-3242.

[9] LI R, SUN Y, HU J, et al. Street-level landmark evaluation based on nearest routers[J]. Security and Communication Networks, 2018(2): 1-12.

[10] HINGANT J, ZAMBRANO M, PéREZ F J, et al. HYBINT: a hybrid intelligence system for critical infrastructures protection[J]. Security and Communication Networks, 2018.

[11] 方濱興. 從層次角度看網(wǎng)絡空間安全技術的覆蓋領域[J]. 網(wǎng)絡與信息安全學報, 2015, 1(1): 2-7.

FANG B X. A hierarchy model on the research fields of cyberspace security technology[J]. Chinese Journal of Network and Information Security, 2015, 1(1): 2-7.

[12] 趙帆, 羅向陽, 劉粉林. 網(wǎng)絡空間測繪技術研究[J]. 網(wǎng)絡與信息安全學報, 2016, 2(9): 1-11.

ZHAO F, LUO X Y, LIU F L. Research on cyberspace surveying and mapping technology[J]. Chinese Journal of Network and Information Security, 2016, 2(9): 1-11.

[13] 李欲曉, 謝永江. 世界各國網(wǎng)絡安全戰(zhàn)略分析與啟示[J]. 網(wǎng)絡與信息安全學報, 2016, 2(1): 1-5.

LI Y X, XIE Y J. Analysis and enlightenment on the cybersecurity strategy of various countries in the world[J]. Chinese Journal of Network and Information Security, 2016, 2(1): 1-5.

[14] 郭莉, 曹亞男, 蘇馬婧, 等. 網(wǎng)絡空間資源測繪:概念與技術[J]. 信息安全學報, 2018, 3(4): 1-14.

GUO L, CAO Y, SU M J, et al. Cyberspace resources surveying and mapping: the concepts and technologies[J]. Journal of Cyber security, 2018, 3(4): 1-14.

[15] 王松, 張野, 吳亞東. 網(wǎng)絡拓撲結構可視化方法研究與發(fā)展[J]. 網(wǎng)絡與信息安全學報, 2018, 4(2): 1-17.

WANG S, ZHANG Y, WU Y D. Survey on network topology visualization[J]. Chinese Journal of Network and Information Security, 2018, 4(2): 1-17.

[16] GOVINDAN R, TANGMUNARUNKIT H. Heuristics for internet map discovery[C]//Proceedings IEEE International Conference on Computer Communications. 2000: 1371-1380.

[17] KEYS K. Iffinder, a tool for mapping interfaces to routers[EB].

[18] SPRING N, MAHAJAN R, WETHERALL D. Measuring ISP topologies with rocketfuel[J]. ACM Sigcomm Computer Communication Review, 2002, 32(4): 133-145.

[19] BENDER A, SHERWOOD R, SPRING N. Fixing ally's growing pains with velocity modeling[C]//Proceedings of the 8th ACM Sigcomm Conference on Internet Measurement. 2008: 337-342.

[20] KEYS K, HYUN Y, LUCKIE M, et al. Internet-scale IPv4 alias resolution with MIDAR[J]. IEEE/ACM Transactions on Networking, 2013, 21(2): 383-399.

[21] SHERWOOD R, SPRING N. Touring the internet in a TCP sidecar[C]//Proceedings of the 6th ACM Sigcomm Conference on Internet Measurement. 2006: 339-344.

[22] SHERRY J, KATZ-BASSETT E, PIMENOVA M, et al. Resolving IP aliases with prespecified timestamps[C]//Proceedings of the 10th ACM SIGCOMM Conference on Internet Measurement. 2010: 172-178.

[23] MARCHETTA P, PERSICO V, PESCAPè A. Pythia: yet another active probing technique for alias resolution[C]//Proceedings of the 9th ACM Conference on Emerging Networking Experiments and Technologies. 2013: 229-234.

[24] GRAILET J F, DONNET B. Towards a renewed alias resolution with space search reduction and IP fingerprinting[C]//Network Traffic Measurement and Analysis Conference. 2017: 1-9.

[25] GUNES M H, SARAC K. Analytical IP alias resolution[C]//IEEE International Conference on Communications. 2006: 459-464.

[26] AUGUSTIN B, CUVELLIER X, ORGOGOZO B, et al. Avoiding traceroute anomalies with paris traceroute[C]//Proceedings of the 6th ACM SIGCOMM Conference on Internet Measurement. 2006: 153-158.

[27] SPRING N, DONTCHEVA M, RODRIG M, et al. How to resolve IP aliases[D]. Seattle: University of Washington, 2004.

[28] 趙洪華, 白華利, 陳鳴, 等. 別名解析中的別名過濾技術[J]. 軟件學報, 2009 (8): 2280-2288.

ZHAO H, BAI H L, CHEN M, et al. Alias filtering technique in alias resolution[J]. Journal of Software, 2009 (8): 2280-2288.

[29] TOZAL M, SARAC K. TraceNET: an internet topology data collector[C]//Proceedings of the 10th ACM SIGCOMM Conference on Internet Measurement. 2010: 356-368.

[30] PADMANABHAN V N, SUBRAMANIAN L. An investigation of geographic mapping techniques for internet hosts[J]. ACM SIGCOMM Computer Communication Review, 2001, 31(4): 173-185.

[31] GUEYE B, ZIVIANI A, CROVELLA M, et al. Constraint-based geolocation of internet hosts[J]. IEEE/ACM Transactions on Networking, 2006, 14(6): 1219-1232.

[32] SCHAPIRA M, ZHU Y, REXFORD J. Putting BGP on the right path: a case for next-hop routing[C]// Proceedings of the 9th ACM SIGCOMM Workshop on Hot Topics in Networks. 2010: 3.

[33] LENCSE G, RéPáS S. Performance analysis and comparison of different DNS64 implementations for linux, openBSD and freeBSD[C]//IEEE 27th International Conference on Advanced Information Networking and Applications. 2013: 877-884.

[34] ZHAO F, LUO X, GAN Y, et al. IP geolocation based on identification routers and local delay distribution similarity[J]. Concurrency and Computation: Practice and Experience, 2018: 1-15.

MLAR: large-scale network alias resolution for IP geolocation

YUAN Fuxiang1,2, LIU Fenlin1,2, LIU Chong1,2, LIU Yan1,2, LUO Xiangyang1,2

1. School of Cyberspace Security, Information Engineering University, Zhengzhou 450001, China 2. State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China

In order to accurately and efficiently perform alias resolution on interface IP and support IP geolocation, a large-scale network alias resolution algorithm (MLAR) was proposed. Based on the statistical differences in delays, paths, Whois, etc. between alias IP and non-alias IP, before resolution, filtering rules were designed to exclude a large number of IPs that cannot be aliases and improve efficiency of resolution, alias resolution was transformed into classification, and four novel features such as delay similarity, path similarity, etc. were constructed for the classification of possible alias IP and non-alias IP after filtering. Experiments based on millions of samples from CAIDA show that compared with RadarGun, MIDAR, and TreeNET, the accuracy is improved by 15.8%, 4.8%, 5.7%, the time consumption can be reduced by up to 77.8%, 65.3%, and 55.2%, when the proposed algorithm is applied to IP geolocation, the failure rates of the three typical geolocation methods such as SLG, LENCR, and PoPG are reduced by about 65.5%, 64.1%, and 58.1%.

alias resolution, IP geolocation, network topology, network measurement, machine learning

s: The National Natural Science Foundation of China (U1636219, U1736214, U1804263), The National Key R&D Program of China (2016YFB0801303, 2016QY01W0105), The Plan for Scientific Innovation Talent of Henan Province (184200510018)

TP393

A

10.11959/j.issn.2096?109x.2020044

袁福祥（1991-），男，山東濟寧人，信息工程大學博士生，主要研究方向為網(wǎng)絡空間資源測繪與IP定位。

劉粉林（1964-），男，江蘇溧陽人，博士，信息工程大學教授、博士生導師，主要研究方向為網(wǎng)絡空間安全。

劉翀（1994-），男，遼寧撫順人，信息工程大學碩士生，主要研究方向為網(wǎng)絡空間資源測繪與IP定位。

劉琰（1979-），女，山東濟南人，博士，信息工程大學副教授，主要研究方向為網(wǎng)絡空間安全。

羅向陽（1978-），男，湖北荊門人，博士，信息工程大學教授、博士生導師，主要研究方向為網(wǎng)絡空間安全。

論文引用格式：袁福祥, 劉粉林, 劉翀, 等. MLAR：面向IP定位的大規(guī)模網(wǎng)絡別名解析[J]. 網(wǎng)絡與信息安全學報, 2020, 6(4): 77-94.

YUAN F X, LIU F L, LIU C, et al. MLAR: large-scale network alias resolution for IP geolocation[J]. Chinese Journal of Network and Information Security, 2020, 6(4): 77-94.

2020?01?25；

2020?03?19

袁福祥，rookieyfx@163.com

國家自然科學基金（U1636219, U1736214, U1804263）；國家重點研發(fā)計劃（2016YFB0801303, 2016QY01W0105）；河南省科技創(chuàng)新杰出人才計劃（184200510018）