一種基于6Gen 算法的IPv6 地址生成方法

孫亞洲，胡洛林

（中國人民解放軍66018 部隊，天津300380）

0 引言

隨著全球IP 地址空間探測的不斷推進，網(wǎng)絡(luò)測量工作的發(fā)展日新月異，取得了很大的成就。由于IPv4地址空間的密度和規(guī)模有限，以現(xiàn)在的掃描速度，研究人員已經(jīng)能夠利用相關(guān)工具完全枚舉所有可能的IPv4地址[1]，從而實現(xiàn)對IPv4 地址空間的全面探測。然而，IPv6 具有更大的地址空間，以目前的掃描與計算能力，想用同樣的辦法來對它進行徹底的探測是完全不可行的[2]。保守估計，如果以每秒完成一次探測來算，完整的IPv6 探測可能需要大約50 億年才能完成。因此，如何獲得某種程度上的全面的IPv6 地址情況成為一道難題。對IPv6 網(wǎng)絡(luò)地址生成算法的研究，能為IPv6測量提供更多更好的有效地址數(shù)據(jù)，減少對無效地址的測量，削減資源的浪費，同時還能提高效率，讓研究人員獲得某種程度上的全面的IPv6 地址情況。

目前IPv6 地址生成方面已有的研究工作大致可以分為三類。一是研究從可公開訪問的數(shù)據(jù)源（如DNS 記錄）中提取IPv6 地址的方法。Fiebig 等人通過遞歸查詢PTR 記錄中的地址前綴，從DNS 服務(wù)器中挖掘IPv6 地址[3]；Gasser 等人研究從各種主動和被動來源收集更廣泛的地址，這些來源包括歐洲互聯(lián)網(wǎng)交換節(jié)點的網(wǎng)絡(luò)分流器和慕尼黑科學(xué)網(wǎng)的上行鏈路、Rapid7和Caida 的DNS 數(shù)據(jù)集等[4]。這種方式工作量巨大且存在較大的局限性。二是識別已知地址以掌握其IPv6地址分配模式，進而獲得活躍主機地址。Czyz 等人通過在Rapid7 DNS Any 數(shù)據(jù)集中對域名執(zhí)行DNS A 和AAAA 查詢識別出了520K 個雙棧服務(wù)器，并對CAI?DA Ark 路由測試數(shù)據(jù)集里的主機執(zhí)行相同的DNS 查找，找到了25K 個雙棧路由器[5]；Plonka 和Berger 提出了一種從給定的可用于掃描的地址中識別密集網(wǎng)絡(luò)前綴的方法[6]。這種方法僅考慮了網(wǎng)絡(luò)前綴，而沒有覆蓋任何地址空間區(qū)域。三是設(shè)計能夠生成待探測地址的算法。Ullrich 等人開發(fā)了一種遞歸算法，以一組種子地址和一個閾值N 作為輸入，并確定IPv6 地址范圍中除N 位以外的其余所有位的值[7]；Foremski 等人提出了一種在一組IPv6 地址上集中發(fā)現(xiàn)地址結(jié)構(gòu)的Entropy/IP 算法[8]。這些算法目前看來產(chǎn)生了一些效果，但總體上講效率仍不夠高。

鑒于已有的幾種方法存在的問題，Austin Murdock等人提出了一種6Gen 算法[9]。這種算法盡可能多地將相似的種子聚類到具有高種子密度的地址空間區(qū)域，并最終將這些區(qū)域的地址作為掃描目標(biāo)輸出，從而獲得大量的有效IPv6 地址。實驗表明該算法效率較高，邏輯簡單，具有很強的實用性。

1 算法思路

通常在考慮IPv6 地址生成的算法時，一般的思路是嘗試反向分析IP 分配方案[10]。然而，這種方法有幾個難點：一是從有限數(shù)量的種子地址中確定IPv6 地址分配模式比較困難；二是在一個網(wǎng)絡(luò)中同一地址空間區(qū)域的IPv6 地址可能使用了多個分配策略（例如基于主機類型等）；三是難以確定不同的獨立網(wǎng)絡(luò)之間的界限。

IPv6 網(wǎng)絡(luò)地址生成算法試圖挖掘已知地址的分布結(jié)構(gòu)，并以此生成其他候選地址。二者之間極可能是依賴的，也可能是獨立的。在依賴模型中，種子地址之間存在依賴關(guān)系。因此，種子集里某個特定地址的存在可能影響了某些非種子地址是否是活躍地址的概率。在這種情況下，一個簡單的思路是算法可以對種子或者每個網(wǎng)絡(luò)前綴根據(jù)線性模型來產(chǎn)生目標(biāo)地址。在獨立模型中，種子集被視為現(xiàn)實中活躍主機地址的獨立同分布（IID）隨機樣本?？梢哉J(rèn)為在這種情況下，現(xiàn)實里活躍地址密度最高的空間區(qū)域在種子集里也具有最高的種子密度。與依賴模型不同的是，獨立模型對特定種子的觀察并不影響其他潛在的活躍地址的狀態(tài)。

6Gen 算法考慮到了上述問題，它采用了獨立模型，并假設(shè)種子的稠密區(qū)域與現(xiàn)實中活躍地址的稠密區(qū)域是正相關(guān)的，將種子地址視為活躍地址的獨立同分布隨機樣本[11]。算法識別種子的密集區(qū)域。這種方法與假設(shè)種子地址之間存在依賴關(guān)系的方法明顯不同，它可以使IPv6 地址生成更簡單和更靈活。

6Gen 算法的原理可以概括如下：算法盡可能多地將相似的種子地址聚類到具有高種子密度的地址空間區(qū)域，并最終將這些地址區(qū)域內(nèi)的地址作為生成地址輸出。該算法可以迭代操作，首先識別最相似的種子，然后將能夠形成最密集區(qū)域的種子聚集在一起，直到聚集區(qū)域的規(guī)模增長到超過事先設(shè)定的掃描預(yù)算[12]。也就是說，算法將掃描預(yù)算分配給具有許多類似種子的“熱點”區(qū)域。在種子密度與活躍主機密度正相關(guān)的假設(shè)下，這樣可以使生成的IPv6 地址的有效性大大提高。此外，目前的6Gen 算法沒有學(xué)習(xí)模式[13]。

需要注意的是，6Gen 算法并不是純密度驅(qū)動的。它首先要識別相似的種子，然后才將它們聚集成密集區(qū)域。事實上，也許在距離較遠（即相似度不那么高）的種子之間聚類可能產(chǎn)生更高密度的區(qū)域，但6Gen 優(yōu)先考慮相似性。之所以如此，主要是為了節(jié)約預(yù)算，因為越相似的種子形成的集群區(qū)域越小，消耗的預(yù)算也更少。

2 算法分析

2.1 概念定義

2.1.1 距離度量

為了聚類相似的地址，6Gen 算法定義了一個地址相似性的度量。這個度量使用地址之間的nybble（半字節(jié)）級的漢明（Hamming）距離來表示。

該度量計算兩個地址之間不同的nybble 位置數(shù)。為了計算IP 地址空間中兩個區(qū)域之間的距離，算法定義其他數(shù)字與通配符（？）的距離為零。例如：

3002:db6::73 和3002:db6::71 之間的距離是一；

3002:db6::73 和3002:db6::7？之間的距離是零。

可以看到，如果將兩個地址聚集在一個范圍內(nèi)，產(chǎn)生的新的動態(tài)地址的數(shù)量等于Hamming 距離的數(shù)值。如：3002:db6::73 和3002:db6::7？之間的距離是零；將這兩個地址聚集在一個范圍內(nèi)后可以用3002:db6::7？來表示，此時產(chǎn)生的新的動態(tài)地址的數(shù)量也是零。二者在數(shù)值上是相等的。

直觀地說，這個度量可以表明地址之間的相似程度，如果距離度量很大，則顯然我們需要更大的區(qū)域來封裝它們。

圖1 中的地址有三個nybbles 不同，可以形成3 個動態(tài)地址，可以用一個范圍4::?:?0?來表示。

算法在nybble 粒度上計算距離的原因是尋址方案可能在這個程度上進行分配[14]。同時，nybble 粒度可以幫我們找到位級漢明距離一樣時，直觀上看起來不太相似的地址對。例如，2::20 和201::相隔兩位，2::和2::3也是相隔兩位。然而直觀上看第二對更為相似，因為它們都在2::？這個范圍內(nèi)[15]。

2.1.2 簇范圍

如圖1 所示，6Gen 使用一個地址范圍將種子封裝在集群（即簇）中。雖然用通配符（？）能接受任何合法值來表示IPv6 地址的范圍，但是算法也允許使用有界值的通配符，即用[1-2,8-a]這種語法表示特定的nybble值范圍[16]。

圖2 展示的是用通配符創(chuàng)建和發(fā)展地址范圍的過程。

圖2 生成范圍

2.2 算法描述

2.2.1 簇初始化

6Gen 接受一組種子地址輸入，并以此產(chǎn)生一組集群。集群由一個能包含該集群中種子的地址空間區(qū)域范圍和一個位于集群范圍內(nèi)的種子集構(gòu)成。算法為每個種子實例化一個集群，包括單個種子的集群。集群的生長是獨立的。在每次連續(xù)的迭代中，算法都計算集群添加下一個最緊密的種子后會產(chǎn)生的影響。此外，算法不會合并類似的集群。相反，它允許種子屬于多個集群。如函數(shù)InitClusters 所示。

代碼1：

2.2.2 簇的生長

算法首先根據(jù)Hamming 距離來識別離每個集群最近的種子，如函數(shù)FindCandidateSeeds 所示。

代碼2：

算法考慮將所有最小等距的非簇種子作為候選種子。每個候選種子的潛在簇將開始增長，簇范圍將擴大，潛在地將候選種子之外的其他種子也包含進來，從而使簇種子集生長。用生長的簇的完整種子集大小除以其范圍大小，即可計算此時該簇的種子密度：

迭代結(jié)束時，算法生成一個能產(chǎn)生最高種子密度的簇和候選種子對。當(dāng)多個增長選項可以導(dǎo)致相同的最大密度時，算法優(yōu)先考慮選擇范圍較小的生成簇，因為消耗的預(yù)算更少。

這個過程如函數(shù)GrowtCluster 所示。

代碼3：

2.2.3 生成地址

6Gen 算法會一直迭代，直到簇范圍大小之和等于事先提供的探測預(yù)算或者所有種子都已屬于某個集群。如果最后產(chǎn)生的那個集群超出了探測預(yù)算，算法會通過隨機選擇新增長的簇中不在已有簇預(yù)增長范圍的地址來精確消耗預(yù)算。

需要指出的是由于簇在潛在增長時每個非簇種子都會被考慮，而且簇的增長是獨立的，所以算法產(chǎn)生的簇可能會有重疊區(qū)域。此外，算法沒有將部分重疊的簇合并，因為這可能會導(dǎo)致最后產(chǎn)生的簇的密度顯著降低。算法6Gen 允許簇部分重疊，但會刪除那些被另一個簇完全包含的簇。算法會將一個新生成的簇的范圍與所有其他簇的范圍進行比較，以確保不存在任何嚴(yán)格子集（真子集）。

代碼4：

3 實驗結(jié)果分析

3.1 實驗環(huán)境

為了驗證6Gen 的有效性，實驗基于Python 語言初步實現(xiàn)了文中的算法原型。實驗設(shè)定探測預(yù)算bud?get 為16 的5 次冪，即約100 萬。實驗選取P.Forems?ki 等人在Entropy/IP 算法中評估使用的Reports for Servers、Reports for Routers 的10 個數(shù)據(jù)集作為種子地址[17]。

每個種子數(shù)據(jù)集中包含50 個種子地址，其情況如

表1 種子集

3.2 實驗結(jié)果及分析

對上述10 個數(shù)據(jù)集分別運行算法，得到的實驗結(jié)果如表2 所示。

表2 運行6Gen 后的實驗結(jié)果

例如，數(shù)據(jù)集Dataset R3 在運行算法后產(chǎn)生的簇有：

2001:0db8:00??:000?:000?:0000:0000:0012

2001:0db8:??0?:000?:0000:0000:0000:0001

2001:0db8:?10?:000?:000?:0000:0000:1fd8

…

等10 個，生成的IPv6 地址有：

2001:0db8:0000:0000:0000:0000:0000:0001

2001:0db8:0000:0001:0000:0000:0000:0001

2001:0db8:0000:0002:0000:0000:0000:0001

…

等655360 個。

分析表2 中的實驗數(shù)據(jù)，可以看到，除Dataset S3外，幾乎所有種子數(shù)據(jù)集在經(jīng)過6Gen 算法運行之后，都生成了大量的新的IPv6 地址。其中在Dataset S5 數(shù)據(jù)集上更是生成了1040384 個IPv6 地址，這是原種子集中地址數(shù)目的約2 萬倍。此外，與生成的IPv6 地址數(shù)量相比，簇的數(shù)量很少。運行算法后產(chǎn)生簇最多的是Dataset S5，有45 個，最少的為Dataset S3，僅有1 個。

不同類型和來源的種子集運行算法后的結(jié)果也有差別。如表3 所示，總的來說，來自服務(wù)器的種子集產(chǎn)生的地址數(shù)目要多于來自路由器的種子集。二者平均生成的IPv6 地址數(shù)相差超過了25 萬，平均產(chǎn)生的簇相差6.8 個。需要指出，這些數(shù)據(jù)的計算都包含了Da?taset S3，如果將其排除，二者的差距將更加巨大。

表3 不同來源種子集的實驗結(jié)果

根據(jù)實驗結(jié)果，總的來說，6Gen 算法平均可以生成原種子集地址數(shù)量的8599.1 倍的IPv6 地址。其中，來自服務(wù)器的5 個種子集（Reports for Servers）平均生成的IPv6 地址數(shù)量是原來種子集地址的11150.4 倍，來自路由器的5 個種子集（Reports for Routers）平均生成的IPv6 地址數(shù)量是原來種子集地址的6047.7 倍。圖3 可以直觀地看出兩種數(shù)據(jù)集在6Gen 算法下生成IPv6 地址的能力。

圖3 生成IPv6地址能力的比較

在實驗中，Dataset S3 僅僅產(chǎn)生了一個簇，生成了16 個IPv6 地址，這個結(jié)果顯然存在異常。經(jīng)過分析，可能是由于該種子集中地址分布較為特殊，導(dǎo)致算法在生成簇范圍的過程中只產(chǎn)生一個簇就停止了迭代。這也說明算法在簇的產(chǎn)生方面還有待進一步優(yōu)化。

4 結(jié)語

針對IPv6 地址生成存在的問題，研究了一種基于6Gen 算法的IPv6 地址生成方法。算法定義了一個使用地址之間的nybble（半字節(jié)）級漢明距離來表示地址相似性的度量，并使用一個地址范圍將種子封裝在集群（即簇）中。算法接受一組種子地址輸入，并以此產(chǎn)生一組簇。算法迭代操作，首先識別最相似的種子，然后將能夠形成最密集區(qū)域的種子聚集在一起，直到聚集區(qū)域的規(guī)模增長到超過事先設(shè)定的掃描預(yù)算。算法盡可能多地將相似的種子地址聚類到具有高種子密度的地址空間區(qū)域，并最終將這些區(qū)域內(nèi)的地址作為生成地址輸出。實驗結(jié)果表明，6Gen 算法平均可以生成原種子集地址數(shù)量的8599.1 倍的IPv6 地址，這大大提高了IPv6 地址生成算法的效率。不同類型和來源的種子集運行算法后的結(jié)果也有差別，來自服務(wù)器的種子集產(chǎn)生的地址數(shù)目要多于來自路由器的種子集。下一步將根據(jù)實驗結(jié)果中發(fā)現(xiàn)的問題，對算法在簇的產(chǎn)生方面進行進一步優(yōu)化，同時對生成的地址結(jié)果進行活躍檢測，以進一步評估算法的有效性。