基于拓?fù)渎窂骄垲?lèi)的城市級(jí)地標(biāo)評(píng)估方法

◆劉淵博 甘勇 張鶴林 賈東偉

基于拓?fù)渎窂骄垲?lèi)的城市級(jí)地標(biāo)評(píng)估方法

◆劉淵博1甘勇1，2張鶴林1賈東偉1

（1.鄭州輕工業(yè)大學(xué)（鄭州） 計(jì)算機(jī)與通信工程學(xué)院 河南 450002；2.鄭州工程技術(shù)學(xué)院（鄭州） 河南 450044）

從IP位置數(shù)據(jù)庫(kù)中獲得城市級(jí)地標(biāo)，是地標(biāo)獲取的最直接的方法。但由于當(dāng)前IP位置數(shù)據(jù)庫(kù)存在初始數(shù)據(jù)來(lái)源不明、數(shù)據(jù)庫(kù)構(gòu)建方法不公開(kāi)及地標(biāo)可靠性低的問(wèn)題，為此本文提出了一種基于拓?fù)渎窂骄垲?lèi)的城市級(jí)地標(biāo)評(píng)估方法，通過(guò)對(duì)IP2Location數(shù)據(jù)庫(kù)中地標(biāo)的存活性探測(cè)，以北京、上海、紐約、東京四個(gè)城市為例獲取數(shù)據(jù)庫(kù)中在線地標(biāo)的拓?fù)渎窂?，并將排序后的IP地址映射到路由器空間中，使用K-Means算法進(jìn)行聚類(lèi)，實(shí)現(xiàn)對(duì)地標(biāo)的可靠性評(píng)估。實(shí)驗(yàn)結(jié)果表明，評(píng)估后的地標(biāo)可靠性提高了15%以上，可用于支撐高可靠定位。

拓?fù)渎窂教綔y(cè)；地標(biāo)評(píng)估；聚類(lèi)算法

網(wǎng)絡(luò)實(shí)體定位技術(shù)是利用已知IP標(biāo)識(shí)的網(wǎng)絡(luò)實(shí)體設(shè)備來(lái)確定其地理位置，它可以用來(lái)提高網(wǎng)絡(luò)空間的安全，優(yōu)化網(wǎng)絡(luò)性能以及提供基于位置的服務(wù)等[1]。現(xiàn)如今，網(wǎng)絡(luò)實(shí)體地標(biāo)作為定位技術(shù)所需的關(guān)鍵數(shù)據(jù)，主要有兩類(lèi)：城市級(jí)地標(biāo)和街道級(jí)地標(biāo)，本文主要關(guān)注城市級(jí)地標(biāo)。網(wǎng)絡(luò)實(shí)體地標(biāo)是將網(wǎng)絡(luò)實(shí)體映射到地理位置的基準(zhǔn)點(diǎn)，根據(jù)現(xiàn)有的研究進(jìn)展，國(guó)內(nèi)外一些研究機(jī)構(gòu)組織并構(gòu)建了IP位置數(shù)據(jù)庫(kù)，如Whois[2]、MaxMind[3]、IP2Location[4]、百度[5]等。在上述數(shù)據(jù)庫(kù)中，此類(lèi)地標(biāo)多用于實(shí)驗(yàn)研究，實(shí)驗(yàn)通常選取交集，即選取多個(gè)位置數(shù)據(jù)庫(kù)中地理位置一致的IP 地址[6]。但是該方法存在很多限制條件，數(shù)據(jù)來(lái)源不準(zhǔn)確、可靠性差等問(wèn)題都會(huì)影響定位技術(shù)的準(zhǔn)確率，因此從IP 位置數(shù)據(jù)庫(kù)直接獲取地標(biāo)的方法需要更進(jìn)一步的研究改進(jìn)。

1 相關(guān)工作

針對(duì)當(dāng)前IP位置數(shù)據(jù)庫(kù)存在的問(wèn)題有很多學(xué)者做了大量研究，文獻(xiàn)[7]提出了一種基于Internet論壇的城市級(jí)地標(biāo)獲取算法，明顯提高了城市級(jí)網(wǎng)絡(luò)實(shí)體地理的準(zhǔn)確率。文獻(xiàn)[8]提出了一種基于投票的城市級(jí)地標(biāo)評(píng)估方法，該方法分析了中國(guó)大陸不同地理粒度的IP地址和數(shù)據(jù)塊的分布和特征，并進(jìn)行了比較，最后得到初步評(píng)估結(jié)果。文獻(xiàn)[9]提出了一種城市級(jí)地標(biāo)評(píng)估方法GeoCop（Geolocation Cop），利用邊緣路由器關(guān)聯(lián)的候選地標(biāo)，進(jìn)行位置投票確定路由器的位置，從而實(shí)現(xiàn)數(shù)據(jù)庫(kù)中城市級(jí)地標(biāo)的評(píng)估。文獻(xiàn)[10]提出了一種基于路由識(shí)別的城市級(jí)地標(biāo)評(píng)估算法，有效減少了路由器標(biāo)識(shí)的開(kāi)銷(xiāo)，城市級(jí)地標(biāo)的準(zhǔn)確率也更高。文獻(xiàn)[11]提出了基于 POP 網(wǎng)絡(luò)分析的城市級(jí)地標(biāo)評(píng)估方法，該方法根據(jù)節(jié)點(diǎn)的位置來(lái)進(jìn)行準(zhǔn)確性評(píng)估，評(píng)估結(jié)果可靠且效率高。綜上，結(jié)合路由器、POP網(wǎng)絡(luò)、多庫(kù)查詢(xún)的城市級(jí)地標(biāo)評(píng)估方法在一定程度上提高了地標(biāo)的準(zhǔn)確率，但這些方法在數(shù)據(jù)量不足的情況下是無(wú)法進(jìn)行有效評(píng)估的。

2 本文基本原理及主要步驟

本文首先對(duì)數(shù)據(jù)庫(kù)中聲稱(chēng)位于同一城市的在線IP進(jìn)行網(wǎng)絡(luò)路徑測(cè)量，獲得從探測(cè)源到各IP的網(wǎng)絡(luò)路徑；其次提取各IP網(wǎng)絡(luò)路徑上的路由器，將所有路徑上的路由器進(jìn)行排序，并以排序結(jié)果為基準(zhǔn)構(gòu)建多維路由器空間；其后根據(jù)IP的拓?fù)渎窂剑瑢P映射到路由器空間中，并使用K-Means算法對(duì)IP進(jìn)行聚類(lèi)，得到多個(gè)聚類(lèi)簇；最后，依據(jù)數(shù)據(jù)庫(kù)的平均準(zhǔn)確率選擇可靠的IP簇。主要分為以下幾個(gè)過(guò)程：

2.1 路由器排序

若：

分組內(nèi)排序：

分組間排序：

去重：

2.2 路徑聚類(lèi)

利用構(gòu)建的路由器空間及各IP的探測(cè)路徑，將各IP映射到路由空間中，并使用K-Means方法對(duì)IP進(jìn)行聚類(lèi)。在使用K-Means聚類(lèi)時(shí)，需要首先指定聚類(lèi)值。本文使用elbow-method獲得聚類(lèi)的最優(yōu)值為128，在最優(yōu)值下使用K-Means方法對(duì)IP進(jìn)行聚類(lèi)。SSE（Sum of the Squared Errors，誤差平方和）是elbow-method的核心指標(biāo)：

其中，是簇的個(gè)數(shù)，是第個(gè)簇，是簇中的點(diǎn)，m是簇中心。

在使用最優(yōu)值聚類(lèi)得到的個(gè)簇中，統(tǒng)計(jì)每個(gè)簇中屬于同一C類(lèi)網(wǎng)的節(jié)點(diǎn)數(shù)，計(jì)算與該C類(lèi)網(wǎng)中在線IP數(shù)量的比值：

若：

在篩選可靠簇時(shí)，將每個(gè)簇中的所有IP都是可靠的，則該簇為可靠簇。在得到可靠簇后，將簇中節(jié)點(diǎn)對(duì)應(yīng)的IP與城市的地理位置相關(guān)聯(lián)，得到可靠地標(biāo)，從而實(shí)現(xiàn)對(duì)地標(biāo)的可靠性評(píng)估。

3 方法分析

要實(shí)現(xiàn)數(shù)據(jù)包在網(wǎng)絡(luò)中的快速準(zhǔn)確轉(zhuǎn)發(fā)，路由器需要穩(wěn)定、簡(jiǎn)單的路由表。為此，ISP（Internet Service Provider，互聯(lián)網(wǎng)服務(wù)提供商）通常使用CIDR（Classless Inter Domain Routing，無(wú)類(lèi)別域間路由選擇）策略來(lái)減輕互聯(lián)網(wǎng)上路由器的負(fù)擔(dān)，同時(shí)，ISP通常采取穩(wěn)定的路由策略（即對(duì)同一IP開(kāi)展兩次路由測(cè)量，兩次測(cè)量的路徑相同）來(lái)提高路由器的轉(zhuǎn)發(fā)效率。這使得同一區(qū)域的網(wǎng)絡(luò)實(shí)體，其IP地址在網(wǎng)絡(luò)拓?fù)渖弦搀w現(xiàn)出區(qū)域性。本文方法利用這一特點(diǎn)，基于待評(píng)估地標(biāo)在網(wǎng)絡(luò)空間上的路徑相似性，實(shí)現(xiàn)地標(biāo)評(píng)估。

3.1 網(wǎng)絡(luò)路徑與地理位置相似性分析

當(dāng)前網(wǎng)絡(luò)構(gòu)架大致可分為分層和網(wǎng)狀兩種，如下圖1所示。

圖1 兩種網(wǎng)絡(luò)架構(gòu)

無(wú)論是分層架構(gòu)還是網(wǎng)狀架構(gòu)，當(dāng)從同一探測(cè)源出發(fā)，到兩個(gè)IP所經(jīng)過(guò)的路由相似時(shí)，說(shuō)明從探測(cè)源到IP所經(jīng)過(guò)的路徑大致相同，路徑的相似程度越高，說(shuō)明兩個(gè)IP的探測(cè)路徑上，最后一個(gè)相同的路由器距離IP越近。當(dāng)兩個(gè)IP所具有的最近路由器到IP的跳數(shù)越小，根據(jù)CIDR策略可知，這兩個(gè)IP在地理空間上的位置越接近。

3.2 路由穩(wěn)定性分析

為分析網(wǎng)絡(luò)中的路由穩(wěn)定性，本文使用探測(cè)源“8.210.164.165”對(duì)目標(biāo)IP“103.1.8.254”進(jìn)行了網(wǎng)絡(luò)路徑測(cè)量。探測(cè)源每間隔10秒對(duì)目標(biāo)發(fā)起一次路由測(cè)量，整個(gè)路由測(cè)量持續(xù)24小時(shí)，得到8640條路徑，包含5條不同路徑，各路徑所占的比例如下圖2所示。

圖2 各探測(cè)路徑占所有路徑的比例

由圖2可知，在對(duì)網(wǎng)絡(luò)中的目標(biāo)進(jìn)行網(wǎng)絡(luò)測(cè)量時(shí)，超過(guò)95%的數(shù)據(jù)包經(jīng)相同的路由器進(jìn)行轉(zhuǎn)發(fā)，這表明網(wǎng)絡(luò)中的路由是穩(wěn)定的。

4 實(shí)驗(yàn)

4.1 數(shù)據(jù)源

VP S探測(cè)源：8.210.164.165，位于中國(guó)香港，配置為Ubuntu 16.04，4核CPU，16G內(nèi)存，10M帶寬。

待評(píng)估IP段：北京、上海、紐約、東京，每個(gè)城市選擇8個(gè)B類(lèi)網(wǎng)段。

可靠地標(biāo)：用于驗(yàn)證評(píng)估后地標(biāo)的可靠性，北京、上海、紐約、東京四個(gè)城市，每個(gè)城市100個(gè)可靠地標(biāo)。

4.2 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)環(huán)境為Ubuntu 16.04，32核CPU，512G內(nèi)存，2*2080Ti顯卡，Python 3.7。

4.3 實(shí)驗(yàn)方法

分別對(duì)北京、上海、紐約、東京的8個(gè)B類(lèi)IP網(wǎng)段進(jìn)行存活性探測(cè)，得到各城市存活I(lǐng)P數(shù)量如表1所示。

表1 各城市IP存活情況

對(duì)四個(gè)城市的存活I(lǐng)P進(jìn)行網(wǎng)絡(luò)路徑測(cè)量，對(duì)每個(gè)城市的每個(gè)B類(lèi)網(wǎng)段，分別構(gòu)建路由器空間，并將對(duì)應(yīng)網(wǎng)段中的存活I(lǐng)P映射到路由器空間上。

4.4 實(shí)驗(yàn)結(jié)果

利用上述方法中得到的最優(yōu)k值，在每個(gè)城市的每個(gè)B類(lèi)網(wǎng)段中，進(jìn)行IP路徑探測(cè)，將IP地址映射到路由器空間后，使用K-Means聚類(lèi)方法對(duì)IP地址進(jìn)行聚類(lèi)。在每個(gè)聚類(lèi)簇中，統(tǒng)計(jì)屬于同一C類(lèi)網(wǎng)段的IP地址數(shù)量，并計(jì)算該IP數(shù)量值與存活性探測(cè)結(jié)果中該C類(lèi)網(wǎng)段中的存活I(lǐng)P數(shù)之比。將可靠簇中的IP與城市位置相關(guān)聯(lián)，則該地標(biāo)為可靠地標(biāo)，各城市的可靠地標(biāo)數(shù)量如表2所示。

表2 各城市可靠地標(biāo)數(shù)量

從表2可以看出，評(píng)估后的可靠地標(biāo)占比大于85%，該值相比于數(shù)據(jù)庫(kù)的可靠性70%，提高了15%以上。

為驗(yàn)證評(píng)估后地標(biāo)的可靠性，在北京、上海、紐約、東京四個(gè)城市分別使用評(píng)估后的地標(biāo)對(duì)100個(gè)已知地理位置的IP進(jìn)行城市級(jí)定位。城市級(jí)定位方法如下：從同一探測(cè)源，分別對(duì)目標(biāo)和地標(biāo)進(jìn)行網(wǎng)絡(luò)拓?fù)涮綔y(cè)，獲得網(wǎng)絡(luò)路徑。從探測(cè)源到目標(biāo)和地標(biāo)的網(wǎng)絡(luò)路徑上，提取最后3跳路由器IP構(gòu)成集合RT和RL，若RT與RL的交集不為空，則成功對(duì)目標(biāo)實(shí)現(xiàn)城市級(jí)定位，當(dāng)城市級(jí)定位結(jié)果與目標(biāo)實(shí)際城市位置相同，意味著對(duì)目標(biāo)實(shí)現(xiàn)了準(zhǔn)確定位。各城市的定位測(cè)試結(jié)果如表3所示。

表3 目標(biāo)城市級(jí)定位測(cè)試

由表3得出，使用評(píng)估后的地標(biāo)對(duì)目標(biāo)進(jìn)行城市級(jí)定位時(shí)，所有成功定位IP均被準(zhǔn)確定位，定位準(zhǔn)確率超過(guò)95%。由于定位準(zhǔn)確率依賴(lài)于地標(biāo)可靠性，因此，該實(shí)驗(yàn)從側(cè)面印證了本文評(píng)估方法的有效性。上述實(shí)驗(yàn)測(cè)試結(jié)果也表明了本文提出的方法能夠有效對(duì)在線地標(biāo)的城市級(jí)位置進(jìn)行評(píng)估，評(píng)估后的地標(biāo)能夠用于支撐網(wǎng)絡(luò)目標(biāo)的可靠定位。

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

本文基于IP拓?fù)渎窂缴系南嗨菩?，使用K-Means聚類(lèi)方法將IP進(jìn)行聚類(lèi)，從而實(shí)現(xiàn)對(duì)IP位置數(shù)據(jù)庫(kù)中在線IP的可靠性評(píng)估，實(shí)驗(yàn)結(jié)果表明，本章方法評(píng)估后的可靠地標(biāo)比例較數(shù)據(jù)庫(kù)的可靠性，提高了15%以上，使用評(píng)估后的可靠地標(biāo)進(jìn)行定位，城市級(jí)定位準(zhǔn)確率達(dá)到95%以上。

[1]王占豐，馮徑，邢長(zhǎng)友, 等. IP 定位技術(shù)的研究[J].軟件學(xué)報(bào)，2014.

[2]Whois. IP require. www.whois.com.

[3]IP2Location. http://www.ip2location.com/.

[4]MaxMind. http://www.maxmind.com/.

[5]Baidu. http://lbsyun.baidu.com.

[6]邢子娟. 基于多點(diǎn)路由器測(cè)量的IP定位方法研究與實(shí)現(xiàn)[D]. 東南大學(xué)，2019.

[7]Guo C，Liu Y，Shen W，et al.Mining the Web and the Internet for Accurate IP Address Geolocations[C].IEEE INFOCOM 2009.IEEE，2009：2841-2845.

[8]Li H，He Y，Xi R，et al.A Complete Evaluation of the Chinese IP Geolocation Databases[C].International Conference on Intelligent Computation Technology and Automation.IEEE，2016：13-17.

[9]Wang T，Xu K，Song J，et al.An Optimization Method for the Geolocation Databases of Internet Hosts Based on Machine Learning[J].Mathematical Problems in Engineering，2015（10）：1-17.

[10]Ma T，Liu F，Zhang F，et al.An Landmark Evaluation Algorithm Based on Router Identification and Delay Measurement[C].International Conference on Artificial Intelligence and Security.Springer，Cham，2019：163-177.

[11]Shavitt Y，Zilberman N.A Geolocation Databases Study[J].IEEE Journal on Selected Areas in Communications， 2011，29（10）：2044-2056.

[12]Manaf Gharaibeh，Anant Shah，Bradley Huffaker，et al.A Look at Router Geolocation in Public and Commercial Databases[C].Proceedings of ACM International Conference on Internet Measurement Conference，2017：463-469.

2018年重點(diǎn)聯(lián)合基金項(xiàng)目圖像隱蔽通信的行為發(fā)現(xiàn)與主體定位關(guān)鍵問(wèn)題研究（U1804263）