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

袁福祥，劉粉林，劉翀，劉琰，羅向陽(yáng)

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

袁福祥1,2，劉粉林1,2，劉翀1,2，劉琰1,2，羅向陽(yáng)1,2

（1.信息工程大學(xué)網(wǎng)絡(luò)空間安全學(xué)院，河南 鄭州 450001；2. 數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室，河南 鄭州 450001）

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

別名解析；IP定位；網(wǎng)絡(luò)拓?fù)?；網(wǎng)絡(luò)測(cè)量；機(jī)器學(xué)習(xí)

1 引言

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

現(xiàn)有典型的別名解析方法分為基于主動(dòng)探測(cè)和基于被動(dòng)分析兩類。基于主動(dòng)探測(cè)的方法主要通過(guò)對(duì)接口IP的探測(cè)獲取響應(yīng)報(bào)文，并基于響應(yīng)報(bào)文首部源地址字段、標(biāo)識(shí)字段以及可選字段等特點(diǎn)，進(jìn)行別名解析；基于被動(dòng)分析的方法則基于路由器主機(jī)名的命名規(guī)則、IP地址指派慣例及網(wǎng)絡(luò)構(gòu)成，以及網(wǎng)絡(luò)圖結(jié)構(gòu)等分析結(jié)果，進(jìn)行別名解析。

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

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

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

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

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

1) 提出了一種面向IP定位的大規(guī)模網(wǎng)絡(luò)別名解析算法MLAR。MLAR可對(duì)大規(guī)模網(wǎng)絡(luò)中的路由器接口IP進(jìn)行準(zhǔn)確、高效的別名解析，從而對(duì)大規(guī)模網(wǎng)絡(luò)的路由器級(jí)網(wǎng)絡(luò)拓?fù)溥M(jìn)行準(zhǔn)確的刻畫(huà)，支撐基于網(wǎng)絡(luò)拓?fù)涞腎P定位等應(yīng)用。

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

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

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

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

2.1 直接時(shí)延

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

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

圖1 不同城市的別名IP與非別名IP時(shí)延差值對(duì)比

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

2.2 探測(cè)路徑

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

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

圖2 兩個(gè)IP的探測(cè)路徑相似性分析

Figure 2 Similarity analysis of probe paths between two IP

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

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

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

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

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

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

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

2.3 Whois信息

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

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

2.4 路由器主機(jī)信息

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

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

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

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

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

3 MLAR算法

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

3.1 MLAR基本原理與主要步驟

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

圖3 MLAR的原理框架

Figure 3 The principle framework of MLAR

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

輸出S中接口IP的別名解析結(jié)果

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

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

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

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

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

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

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

表3 特征集合

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

3.2 非別名IP過(guò)濾

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

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

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

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

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

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

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

3.3 分類特征表示

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

3.3.1 時(shí)延相似度

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

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

3.3.2 路徑相似度

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

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

對(duì)于兩個(gè)IP的探測(cè)路徑，分別取次探測(cè)中出現(xiàn)次數(shù)最多的路徑跳數(shù)作為從探測(cè)源N到該IP的探測(cè)路徑長(zhǎng)度，將從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路徑的長(zhǎng)度，A,，B,分別為兩個(gè)IP路徑上第跳出現(xiàn)的所有路由器接口IP構(gòu)成的集合。若IP, IP為別名IP，則應(yīng)有A,≈B,n，(A,n∩B,n)≈ (A,n∪B,)，且≈；若IP, IP為非別名IP，則A,與B,，與有一定差異。因此，將從N得到的IP, IP的路徑的相似度S表示為

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

3.3.3 Who is信息相似度

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

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

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

其中，<0.5＜，本文取=0.1，=0.9。對(duì)于IP與IP，設(shè)其相同信息項(xiàng)構(gòu)成集合為，則其Whois信息相似度S可表示為

3.3.4 主機(jī)信息相似度

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

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

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

4 實(shí)驗(yàn)設(shè)計(jì)及結(jié)果

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

4.1 實(shí)驗(yàn)設(shè)置

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

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

表4 實(shí)驗(yàn)設(shè)置

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

4.2 別名解析測(cè)試及結(jié)果分析

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

4.2.1 非別名IP過(guò)濾測(cè)試

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

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

表5 過(guò)濾結(jié)果

4.2.2 別名解析測(cè)試

表6 訓(xùn)練、測(cè)試集構(gòu)造及對(duì)應(yīng)分類結(jié)果

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

4.2.3 不同特征組合的分類效果測(cè)試

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

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

4.2.4 不同分類算法的分類效果測(cè)試

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

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

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

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

4.3.1 別名解析準(zhǔn)確性對(duì)比

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

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

4.3.2 別名解析效率對(duì)比

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

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

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

表9 不同方法多次測(cè)試結(jié)果對(duì)比

表10 不同方法效率對(duì)比

圖5 不同方法需要進(jìn)行解析的樣本的比例

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

圖6 不同方法耗時(shí)

Figure 6 Duration of different methods

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

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

4.3.3 應(yīng)用于IP定位的效果對(duì)比

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

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

表11 定位測(cè)試結(jié)果對(duì)比

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

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

5 結(jié)束語(yǔ)

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

[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)絡(luò)空間安全技術(shù)的覆蓋領(lǐng)域[J]. 網(wǎng)絡(luò)與信息安全學(xué)報(bào), 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] 趙帆, 羅向陽(yáng), 劉粉林. 網(wǎng)絡(luò)空間測(cè)繪技術(shù)研究[J]. 網(wǎng)絡(luò)與信息安全學(xué)報(bào), 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] 李欲曉, 謝永江. 世界各國(guó)網(wǎng)絡(luò)安全戰(zhàn)略分析與啟示[J]. 網(wǎng)絡(luò)與信息安全學(xué)報(bào), 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)絡(luò)空間資源測(cè)繪:概念與技術(shù)[J]. 信息安全學(xué)報(bào), 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èn)|. 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可視化方法研究與發(fā)展[J]. 網(wǎng)絡(luò)與信息安全學(xué)報(bào), 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] 趙洪華, 白華利, 陳鳴, 等. 別名解析中的別名過(guò)濾技術(shù)[J]. 軟件學(xué)報(bào), 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-），男，山東濟(jì)寧人，信息工程大學(xué)博士生，主要研究方向?yàn)榫W(wǎng)絡(luò)空間資源測(cè)繪與IP定位。

劉粉林（1964-），男，江蘇溧陽(yáng)人，博士，信息工程大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)榫W(wǎng)絡(luò)空間安全。

劉翀（1994-），男，遼寧撫順人，信息工程大學(xué)碩士生，主要研究方向?yàn)榫W(wǎng)絡(luò)空間資源測(cè)繪與IP定位。

劉琰（1979-），女，山東濟(jì)南人，博士，信息工程大學(xué)副教授，主要研究方向?yàn)榫W(wǎng)絡(luò)空間安全。

羅向陽(yáng)（1978-），男，湖北荊門(mén)人，博士，信息工程大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)榫W(wǎng)絡(luò)空間安全。

論文引用格式：袁福祥, 劉粉林, 劉翀, 等. MLAR：面向IP定位的大規(guī)模網(wǎng)絡(luò)別名解析[J]. 網(wǎng)絡(luò)與信息安全學(xué)報(bào), 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

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