產(chǎn)毛寧， 張 宇

(哈爾濱工業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院， 哈爾濱 150001)

0 引 言

互聯(lián)網(wǎng)向基于 IPv6 的下一代互聯(lián)網(wǎng)演進已成為全球普遍共識，目前IPv6的部署和使用正在飛速增長，但是由于IPv6 地址空間巨大，地址規(guī)劃復(fù)雜，地址空間劃分政策多樣，以及地址實際使用率低等這些不同于IPv4 的問題，使得IPv6 網(wǎng)絡(luò)拓?fù)錅y量成為一個巨大的挑戰(zhàn)。作為IPv6 網(wǎng)絡(luò)拓?fù)錅y量的輸入，IPv6 拓?fù)錅y量目標(biāo)選擇技術(shù)研究如何通過有效地選擇目標(biāo)來提高拓?fù)錅y量的有效性和完整性。

為了克服上述問題，大量的研究工作從IPv6存活地址列表收集、IPv6地址分析、IPv6地址生成和IPv6網(wǎng)絡(luò)拓?fù)錅y量的角度展開。IPv6 存活地址列表(Hitlists)的收集技術(shù)包括主動技術(shù)如隨機探測::1[1]，完整探測每個聲明的/32前綴中的每個/48中的::1地址[2]，rDNS zone 游走，被動技術(shù)如基于BGP update或從流量中獲取[3,4]。Gasser等觀察到存活地址列表本身包含聚類，從均衡性和無偏性的角度提出了TUM Hitlist[5]；Ullrich等使用遞歸的算法來發(fā)現(xiàn)和提取IPv6地址模式[6]；Foremski等提出了Entropy/IP 系統(tǒng)，使用了貝葉斯模型和聚類分析的機器學(xué)習(xí)技術(shù)來發(fā)現(xiàn)IPv6地址結(jié)構(gòu)[7]；Murdock等設(shè)計了6Gen目標(biāo)生成器，利用地址局域性，迭代識別高密集區(qū)域[8]。上述工作的主要目標(biāo)為IPv6網(wǎng)絡(luò)主機發(fā)現(xiàn)，而非IPv6網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)。CAIDA Ark利用分布式測量點對每個全球聲明的BGP可路由的/48或更短前綴中1個::1地址和1個隨機地址做ICMP-Paris traceroute，但實踐中無法細(xì)粒度地抽樣，同時存在大量冗余探測。與本文類似，Beverly等將存活地址列表用于IPv6 接口級網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)[9]，但缺少預(yù)測存活地址前綴列表的獨立研究。

本文從IPv6存活地址列表的角度，首先探究多源的IPv6存活地址列表收集技術(shù)，用盡可能多的來源保證IPv6存活地址的完整性；然后從多角度分析收集到的IPv6存活地址列表的特征，觀察并總結(jié)該列表所體現(xiàn)出特性以及針對IPv6網(wǎng)絡(luò)拓?fù)錅y量的使用上的指導(dǎo)，為了補充列表采集中的可能缺失和猜測未來可能增長的地址空間，提出IPv6 存活地址前綴列表的預(yù)測算法并評估；最后給出IPv6網(wǎng)絡(luò)拓?fù)錅y量目標(biāo)生成的技術(shù)方案，研究的總體流程如圖1所示。本文的主要貢獻如下：

(1)利用IPv6存活地址列表指導(dǎo)IPv6網(wǎng)絡(luò)拓?fù)錅y量目標(biāo)選取。

(2)提出存活地址前綴預(yù)測算法。

(3)提出IPv6網(wǎng)絡(luò)拓?fù)錅y量目標(biāo)選取的綜合方案。

圖1 目標(biāo)選取技術(shù)總體流程設(shè)計

1 IPv6網(wǎng)絡(luò)拓?fù)錅y量目標(biāo)選取技術(shù)

1.1 IPv6存活地址列表收集與融合

類似于IPv4，IPv6存活地址列表(Hitlist)指一組能夠大體上覆蓋和代表IPv6網(wǎng)絡(luò)的地址集合，并具有存活性，地址被分配、部署并在使用中；完整性，覆蓋所有存活的IPv6地址空間；穩(wěn)定性，地址列表隨著時間變化盡可能小。本文嘗試從5種不同的地址來源獲取IPv6存活地址列表，包括：

(1)Rapid7_FDNS：FDNS數(shù)據(jù)是Rapid7的Project Sonar公開數(shù)據(jù)一部分，本文采用其中的fdns_any數(shù)據(jù)，包括所有對ANY 查詢的回復(fù)，通過提取其中的AAAA記錄，最終得到IPv6地址。

(2)CAIDA_Ark：IPv6 拓?fù)鋽?shù)據(jù)集作為CAIDA Ark 平臺測量數(shù)據(jù)的一部分，通過使用Paris Traceroute技術(shù)探測所有聲明的/48或者更短的IPv6前綴中的隨機地址。本文從CAIDA 2月的IPv6拓?fù)鋽?shù)據(jù)里提取路徑中出現(xiàn)所有IPv6地址。

(3)Bitnodes：Bitnodes 通過發(fā)現(xiàn)網(wǎng)絡(luò)中的所有可達節(jié)點來評估比特幣網(wǎng)絡(luò)的大小，本文使用Bitnodes提供的API，從節(jié)點名稱中提取IPv6地址。

(4)TUM_Responsive：德國TUM 大學(xué)通過對IPv6 存活地址列表的研究，提供IPv6 Hitlist服務(wù)，本文直接采用服務(wù)提供的回復(fù)的IPv6地址。

(5)TUM_Seeds：德國TUM大學(xué)的Hitlist服務(wù)作為一個收集項目，本身也采用了不同的收集源，根據(jù)其倉庫中的實際數(shù)據(jù)，包括有Alexa、CAIDA_dnsname、CT(Certifcate Transparency)、Zonefiles、Openipmap和Traceroute，其中前4個根據(jù)提取的域名，查詢AAAA記錄，來獲取IPv6地址；Openipmap為從RIPE ipmap 項目中提取的IPv6地址；Traceroute為對所有其它源中的地址Traceroute再提取所有的路由器IPv6地址。本文將該倉庫里不同來源地址綜合作為一個收集源。

最后對不同來源存活地址列表清洗再合并，得到融合后的IPv6地址存活列表。由于收集到的地址中還包括特殊目的的全球單播地址，如過渡方案中的6to4地址等，需根據(jù)IANA提供的最新全球單播地址分配做篩選。

1.2 IPv6存活地址特征分析

為了探究IPv6 存活地址列表在IPv6網(wǎng)絡(luò)拓?fù)錅y量上的最佳實踐，有必要對收集到的IPv6存活地址列表深度分析，觀察IPv6地址空間的部署和使用，揭示IPv6地址結(jié)構(gòu)上的聚類，總結(jié)IPv6存活地址列表對IPv6網(wǎng)絡(luò)拓?fù)錅y量目標(biāo)選取上的指導(dǎo)作用。IPv6地址一般可以分為網(wǎng)絡(luò)前綴和接口標(biāo)識兩部分。

1.2.1 IPv6網(wǎng)絡(luò)前綴分析

IPv6網(wǎng)絡(luò)前綴一般指IPv6地址的前64比特。本文為了拓展討論將前綴長度放寬至128比特，選擇長度范圍[32,128]來分析前綴，/32作為下屆，因為/32前綴通常是區(qū)域性互聯(lián)網(wǎng)注冊機構(gòu)(Regional Internet Registries，RIRs)分配給本地互聯(lián)網(wǎng)注冊機構(gòu)(Local Internet Registries，LIRs)的最小塊，128是IPv6地址的最大長度。輸入為不同來源的IPv6存活地址列表，并嘗試從頻率分布，相鄰長度前綴關(guān)聯(lián)性，密度3個角度分析IPv6前綴。首先從IPv6存活地址列表中提取不同長度前綴列表，再依次進行以下分析：

(1)不同長度前綴頻率分布分析。統(tǒng)計不同長度前綴列表中的不同前綴頻率。

(2)相鄰長度前綴關(guān)聯(lián)性分析。Plonka等介紹了前綴聚集計數(shù)比率(Aggregate Count Ratio，ACR)[10]，對于給定的N個地址，將其聚合成不同長度的前綴，接著對于給定前綴長度p，聚集計數(shù)np作為不同/p包含的地址數(shù)量，并設(shè)定p為0時np為1，則rp=np+x/np，其中x代表相鄰前綴的長度差，單位為比特。本文依次取x為 4、8、12和16計算ACR。

(3)不同前綴長度密度分析。統(tǒng)計不同長度前綴列表中不同前綴包含的IPv6存活地址數(shù)M，再計算各長度前綴列表中M的四分位數(shù)。

1.2.2 IPv6接口標(biāo)識分析

IPv6接口標(biāo)識一般指IPv6地址的后64比特，從生成類別上可以分為人工指定和算法自動生成兩種，不同的生成方案見表1。張千里等總結(jié)了不同的接口標(biāo)識生成方案，其中人工指定的方案包括[11]：

(1)基于低字節(jié)的接口標(biāo)識(Low-byte)生成方案，一般指的是除最低兩個字節(jié)外接口標(biāo)識的大部分設(shè)為0。

(2)基于IPv4地址(Embed-IPv4)的生成方案，一般指將IPv4地址作為接口標(biāo)識的最后4個字節(jié)或者將IPv4地址的每個字節(jié)對應(yīng)編碼到最后的4個16比特中。

(3)基于服務(wù)、端口號(Embed-port)的生成方案，一般指將服務(wù)器的端口號或編號嵌入到接口標(biāo)識中。

(4)基于單詞(wordy-based)的生成方案，一般指使用易于記憶的單詞代替16進制數(shù)字作為接口標(biāo)識。

算法自動生成的方案包括：

(1)基于MAC地址的IEEE EUI-64(IEEE-based)的生成方案，通常由48位的硬件地址，中間嵌入0xfffe得到，使得接口標(biāo)識綁定機器硬件且全局唯一。

(2)保護用戶隱私的生成方案，一般隨機生成且隨時間變化而變化。

(3)穩(wěn)定、語義不透明的生成方案，目的是為了解決臨時地址變化頻繁導(dǎo)致的復(fù)雜的網(wǎng)絡(luò)管理和部署問題，接口標(biāo)識隨機生成但對同一子網(wǎng)、同一網(wǎng)絡(luò)接口產(chǎn)生地址相同。

(4)綁定地址與主機的生成方案，源于局域網(wǎng)內(nèi)安全風(fēng)險與多宿主機，生成IID隨機，一般有加密生成接口標(biāo)識方案和基于哈希的地址生成方式。本文使用addr6工具統(tǒng)計融合后IPv6存活地址列表中不同接口標(biāo)識生成方案的占比，分析不同方案的實際部署和使用情況。

表1 常見的接口標(biāo)識生成方案

1.3 IPv6存活地址前綴列表預(yù)測

考慮到IPv6存活地址列表由于收集來源的缺失如不包括非公開數(shù)據(jù)源，和限制如缺少長時間的積累，可能帶來的不完整性，以及IPv6地址部署和使用的快速增長帶來的滯后性，有必要設(shè)計一種方法能夠根據(jù)已知收集的IPv6存活地址列表，預(yù)測未被收集的潛在存活和未來可能部署和使用的地址，作為IPv6網(wǎng)絡(luò)拓?fù)錅y量目標(biāo)的補充來提高拓?fù)浒l(fā)現(xiàn)的完整性。IPv6存活地址前綴列表指一組包含IPv6存活地址的前綴集合。本文為了更完整地探測特定IPv6可路由前綴R下的目標(biāo)網(wǎng)絡(luò)拓?fù)洌谑占腎Pv6存活地址列表，從網(wǎng)絡(luò)拓?fù)錅y量中按前綴均勻抽樣的常用方法出發(fā)，提出IPv6存活地址前綴列表預(yù)測算法PrefixPrediction，即根據(jù)IPv6存活地址列表提取前綴集合，再結(jié)合多層級密度聚類和啟發(fā)式后綴拓展，來預(yù)測未被收集的IPv6存活地址前綴列表，最終作為拓?fù)錅y量目標(biāo)生成的一部分。

根據(jù)實踐中地址分配體現(xiàn)出的層級性，以半字節(jié)即4比特為單位劃分；和局部聚集性，分配的地址聚集在相鄰或相近的前綴下，本文提出的算法核心思想為針對特定IPv6可路由前綴R下的目標(biāo)網(wǎng)絡(luò)，根據(jù)R包含的IPv6 存活地址列表HL中提取的IPv6 存活地址前綴列表，預(yù)測固定長度為L的IPv6 存活地址前綴列表。R的長度LR∈[32,64]，L∈{40,48,…,64}。對于用32位16進制數(shù)xj表示的IPv6地址Xi，則包含n個地址的HL形式化表示(1)：

HL={X1,X2,…,Xi,…,Xn}，

(1)

(1)多層級密度聚類。按不同前綴長度32～64，以8位間隔來劃分層級，采用32作為最小長度，而64比特的位置一般作為網(wǎng)絡(luò)標(biāo)識和接口標(biāo)識的分界。對于層級Levelp形式化表示(2)：

(2)

(3)

(4)

(5)

結(jié)合(1)(2)步，得到Levelp的預(yù)測的IPv6存活前綴列表HPLp，形式化表示為式(6)：

(6)

最終合并不同HPLp得到輸出HPL。

1.4 IPv6網(wǎng)絡(luò)拓?fù)錅y量目標(biāo)選取

在IPv6網(wǎng)絡(luò)拓?fù)錅y量目標(biāo)選取一般采用對BGP路由前綴列表均勻隨機抽樣的策略?；谶@種均勻隨機抽樣的方法，本文從IPv6存活地址列表的角度出發(fā)，分為兩步選取IPv6網(wǎng)絡(luò)拓?fù)錅y量的目標(biāo)：

(1)對存活地址列表按/64前綴均勻隨機抽??；

(2)根據(jù)IPv6存活地址前綴列表預(yù)測算法，得到預(yù)測的/64前綴列表，并對每個前綴拼接隨機接口標(biāo)識，最終合并這兩步的輸出?；贗Pv6存活地址列表的IPv6網(wǎng)絡(luò)拓?fù)錅y量目標(biāo)選取的綜合方案如圖2所示。

圖2 目標(biāo)選取的綜合方案

2 實驗結(jié)果與分析

2.1 IPv6存活地址列表收集與融合

合并不同來源的存活地址列表，得到融合的IPv6存活地址列表約17M。不同來源的IPv6存活地址列表統(tǒng)計結(jié)果見表2，可以觀察到不同來源在融合的IPv6 存活地址列表中貢獻的差異。其中，獨占：融合的IPv6 存活地址列表中僅由該源提供的地址數(shù)量；占比：采用該源的地址與融合的IPv6 存活地址列表交集數(shù)占融合的IPv6 存活地址列表的比例?？梢园l(fā)現(xiàn)不同來源占比以及獨占比差距不大，CAIDA_Ark 甚至基本一致，說明這些不同來源背后采集技術(shù)的不同，導(dǎo)致不同來源存活地址列表獨立性強，都應(yīng)該被采用。

表2 IPv6存活地址列表統(tǒng)計

2.2 IPv6存活地址特征分析

IPv6存活地址特征主要針對最終融合的IPv6存活地址列表。

2.2.1 IPv6網(wǎng)絡(luò)前綴分析

不同長度前綴頻率分布結(jié)果如圖3所示。數(shù)據(jù)包括最終融合的IPv6存活地址列表Total及其最主要的3個收集來源，Rapid7_FDNS、CAIDA_Ark和TUM_Responsive，可以觀察到不同來源IPv6存活地址列表的頻率分布存在共性，隨著前綴長度的增加，在[32,64]的區(qū)間內(nèi)呈現(xiàn)明顯的上升趨勢，而在[64,128]的區(qū)間內(nèi)趨于平緩，表明存在大量的IPv6存活地址聚集在64長度以下的IPv6前綴中。

圖3 IPv6存活地址列表不同長度前綴頻率分布

融合IPv6存活地址列表的不同長度前綴ACR值分布如圖4所示?？梢杂^察到不同相鄰前綴的長度差下ACR值隨著前綴長度的增長，總體在[32,64]區(qū)間變化大且多呈現(xiàn)下降趨勢，在[64,128]區(qū)間變化較小且增減交替，相鄰前綴的長度差越小，ACR值變化越多，表明相鄰前綴的長度差越小，越能反應(yīng)相鄰前綴的差異。

圖4 IPv6存活地址列表不同長度前綴ACR值分布

融合IPv6存活地址列表的不同長度前綴密度分布如圖5所示?？梢杂^察到[32,64]區(qū)間內(nèi)前綴長度越短，相對地址密度越大，在前綴長度[40,128]區(qū)間包含存活地址數(shù)的中位數(shù)都為1，甚至在[60,128]上四分位數(shù)和下四分位數(shù)也為1，表明該區(qū)間的大多數(shù)前綴僅包含1個存活地址，同時[32,40]區(qū)間的中位數(shù)都不超過10，表明IPv6存活地址列表中不同長度的特定前綴包含存活地址都偏少，數(shù)值在1～10之間，呈現(xiàn)出低密度性。

圖5 IPv6存活地址列表不同長度前綴密度分布

2.2.2 IPv6 接口標(biāo)識分析

IPv6接口標(biāo)識(IID)分析的結(jié)果見表3?？梢杂^察到，隨機化的地址在不同來源中占據(jù)大部分，為50%～80%，表明大多數(shù)接口標(biāo)識是隨機的，而基于IPv4地址和端口號的生成方案地址在不同來源中占比較小，基于低字節(jié)和IEEE EUI-64方案的地址占比相對較多。此外，不同收集來源下接口標(biāo)識生成方案占比分布不同，除隨機化地址外，Rapid7_FDNS中基于低字節(jié)方案的地址最多，而CAIDA_Ark 和 TUM_Responsive 中EUI-64地址最多。

表3 不同IID模式在存活地址列表中占比統(tǒng)計

綜上，融合的IPv6存活地址列表呈現(xiàn)高聚集，即大量地址聚集在較短的前綴中；多層次，即長度差越小，越能反應(yīng)相鄰前綴的差異性；低密度，即不同長度前綴包含存活地址數(shù)的中位數(shù)為1～10；接口標(biāo)識不可預(yù)測性，即大部分接口標(biāo)識是隨機的。

2.3 IPv6存活地址前綴列表預(yù)測

為了評估預(yù)測算法的效果，針對特定/32前綴網(wǎng)絡(luò)，對IPv6存活地址列表過濾得到/64存活前綴列表，對該列表的隨機50%作為訓(xùn)練集，剩余50%作為測試集，計算本文算法PrefixPrediction(PP)的正確率，并與Entropy/IP(EIP)結(jié)果作比較。預(yù)測集：輸出的與測試集相同數(shù)量的預(yù)測前綴列表；正確率：預(yù)測集與測試集的交集占測試集的比例。本文在3個數(shù)據(jù)集H1、H2和H3做實驗，實驗結(jié)果見表4。

表4 PrefixPrediction與Entropy/IP實驗結(jié)果對比

實驗結(jié)果表明，本文的前綴預(yù)測算法PrefixPrediction正確率相比Entropy/IP 高，在1.4～5.5倍之間，同時二者預(yù)測前綴的交集小，有強互補性。預(yù)測集增長下的正確率變化趨勢如圖6所示，可以發(fā)現(xiàn)隨著預(yù)測集增長，PrefixPrediction比Entropy/IP正確率都要高，二者的正確率都呈現(xiàn)線性增趨勢，表明兩種算法的預(yù)測能力都具有穩(wěn)定性。

圖6 預(yù)測集增長下正確率變化趨勢

2.4 IPv6拓?fù)錅y量目標(biāo)選取

為了驗證本文基于IPv6存活地址列表的IPv6網(wǎng)絡(luò)拓?fù)錅y量目標(biāo)選取方法的效果，針對特定/32可路由前綴的目標(biāo)網(wǎng)絡(luò)，分別采用本文方法HS和按/64均勻隨機抽樣方法URS，對一定數(shù)量目標(biāo)采用ICMP-paris的探測方法，對比結(jié)果的節(jié)點數(shù)和鏈接數(shù)。目標(biāo)網(wǎng)絡(luò)包括T1(2001:16b8::/32)、T2(2a02:06b8::/32)和T3(240e:00e0::/32)。本文方法中對存活地址列表按/64均勻隨機抽樣數(shù)的2倍，相應(yīng)的URS為從均勻隨機抽樣的地址中再隨機抽取該數(shù)量；traceroute路徑中發(fā)現(xiàn)的不同IPv6接口地址數(shù)；traceroute路徑中發(fā)現(xiàn)的不同IPv6接口地址連接數(shù)。本文對3個數(shù)據(jù)集T1、T2和T3分別采用不同測量點做實驗，實驗結(jié)果見表5。

實驗結(jié)果表明，本文基于IPv6存活地址列表的IPv6網(wǎng)絡(luò)拓?fù)錅y量目標(biāo)選取方法HS比均勻隨機抽樣方法URS明顯提高了拓?fù)浒l(fā)現(xiàn)的完整性，拓?fù)湫掳l(fā)現(xiàn)率在94%以上，拓?fù)浒l(fā)現(xiàn)結(jié)果隨探測目標(biāo)增長變化如圖7和圖8所示，HS相比URS結(jié)果表現(xiàn)一直要好。拓?fù)涞耐暾约窗l(fā)現(xiàn)的節(jié)點數(shù)和鏈接數(shù)，拓?fù)湫掳l(fā)現(xiàn)率即HS相比URS新發(fā)現(xiàn)的節(jié)點和鏈接占HS的比率。

表5 HS和URS 實驗結(jié)果對比

圖7 發(fā)現(xiàn)節(jié)點數(shù)隨探測測量目標(biāo)數(shù)增長變化

圖8 發(fā)現(xiàn)鏈接數(shù)隨探測目標(biāo)數(shù)增長變化

3 結(jié)束語

本文提出一種IPv6 網(wǎng)絡(luò)拓?fù)錅y量目標(biāo)選取技術(shù)，用于提高IPv6網(wǎng)絡(luò)拓?fù)錅y量的有效性和完整性。首先，收集并融合不同來源的IPv6存活地址列表得到約17M的地址；其次，分析了IPv6存活地址列表的特征，發(fā)現(xiàn)融合存活地址列表呈現(xiàn)出高聚集、多層次、低密度和接口標(biāo)識不可預(yù)測性，提出了IPv6 存活地址前綴列表的預(yù)測算法PrefixPrediction，對比Entropy/IP預(yù)測的正確率更高，發(fā)現(xiàn)二者結(jié)果具有強互補性；最后，給出了IPv6網(wǎng)絡(luò)拓?fù)錅y量目標(biāo)選取的綜合方案HS，對比URS明顯提高拓?fù)浒l(fā)現(xiàn)的完整性，拓?fù)湫掳l(fā)現(xiàn)率超過94%。未來將進一步豐富收集技術(shù)，提高IPv6存活地址列表的完整性，結(jié)合多種IPv6存活地址前綴預(yù)測算法來提高預(yù)測正確率，從而更深入地進行IPv6網(wǎng)絡(luò)拓?fù)錅y量的研究。