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

孫亞洲，胡洛林

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

0 引言

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

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

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

1 算法思路

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

IPv6 網絡地址生成算法試圖挖掘已知地址的分布結構，并以此生成其他候選地址。二者之間極可能是依賴的，也可能是獨立的。在依賴模型中，種子地址之間存在依賴關系。因此，種子集里某個特定地址的存在可能影響了某些非種子地址是否是活躍地址的概率。在這種情況下，一個簡單的思路是算法可以對種子或者每個網絡前綴根據線性模型來產生目標地址。在獨立模型中，種子集被視為現實中活躍主機地址的獨立同分布（IID）隨機樣本。可以認為在這種情況下，現實里活躍地址密度最高的空間區域在種子集里也具有最高的種子密度。與依賴模型不同的是，獨立模型對特定種子的觀察并不影響其他潛在的活躍地址的狀態。

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

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

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

2 算法分析

2.1 概念定義

2.1.1 距離度量

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

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

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

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

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

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

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

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

2.1.2 簇范圍

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

圖2 展示的是用通配符創建和發展地址范圍的過程。

圖2 生成范圍

2.2 算法描述

2.2.1 簇初始化

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

代碼1：

2.2.2 簇的生長

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

代碼2：

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

迭代結束時，算法生成一個能產生最高種子密度的簇和候選種子對。當多個增長選項可以導致相同的最大密度時，算法優先考慮選擇范圍較小的生成簇，因為消耗的預算更少。

這個過程如函數GrowtCluster 所示。

代碼3：

2.2.3 生成地址

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

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

代碼4：

3 實驗結果分析

3.1 實驗環境

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

每個種子數據集中包含50 個種子地址，其情況如

表1 種子集

3.2 實驗結果及分析

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

表2 運行6Gen 后的實驗結果

例如，數據集Dataset R3 在運行算法后產生的簇有：

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 中的實驗數據，可以看到，除Dataset S3外，幾乎所有種子數據集在經過6Gen 算法運行之后，都生成了大量的新的IPv6 地址。其中在Dataset S5 數據集上更是生成了1040384 個IPv6 地址，這是原種子集中地址數目的約2 萬倍。此外，與生成的IPv6 地址數量相比，簇的數量很少。運行算法后產生簇最多的是Dataset S5，有45 個，最少的為Dataset S3，僅有1 個。

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

表3 不同來源種子集的實驗結果

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

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

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

4 結語

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