高隨機化IPv6地址集合的地址模式過濾方法

鄧裕立 王軼駿 薛 質

(上海交通大學電子信息與電氣工程學院 上海 200240)

0 引 言

歐洲網絡資源協調中心(RIPE NCC)于2019年11月25日宣布最后的IPv4地址空間儲備耗盡[1]。一方面是IPv4地址資源的枯竭，另一方面是國內外對IPv6部署的大力推進。《中國IPv6發展狀況》白皮書顯示，截至2019年6月，國內的IPv6活躍用戶數已達1.30億，基礎電信企業已分配IPv6地址的用戶數達12.07億[2]。根據Cisco全球IPv6部署統計數據[3]，不少國家的IPv6網絡用戶比例在最近幾年穩步上升。

隨著互聯網向著IPv6逐步過渡，IPv6環境下的網絡測繪引起了一些研究者的關注。然而，長度為128位的IPv6地址相比32位的IPv4地址擁有更加龐大的地址空間，這導致活躍IP地址在網絡中的分布顯得十分稀疏。如果沿用以往在IPv4網絡測繪時所采用的地址空間遍歷掃描方法，不僅無法在可接受的時間內完成掃描工作，還難以發現活躍的IPv6地址。因此，IPv6環境下需要合理地選擇掃描的目標地址，針對這一問題研究者們提出了多種解決方案：(1) 從各種包含IPv6地址的數據集中采集目標地址[4-5]；(2) 借助DNS特性遍歷DNS反向域從中收集注冊的IPv6地址[6-7]；(3) 通過啟發式算法挖掘IPv6地址集合中可能存在的模式并生成符合相應模式的目標地址[8-11]。與前兩種方法相比，方法3更加靈活，能夠發現未被現有數據集記錄和不在DNS反向域中的新地址。不過，文獻[12]指出這些啟發式算法缺乏處理隨機化地址集合的能力。當地址集合中包含了較多的沒有明顯模式特征的隨機地址時，地址集合在整體上將呈現出高隨機性，算法會受到這類地址的干擾，很難甚至無法發現集合中其他地址存在的模式。

針對上述問題，本文提出一種從呈現高隨機化特點的IPv6地址集合中過濾具有潛在模式地址的方法，減少地址集合的隨機化程度，方便啟發式算法對地址集合進行處理。該方法通過比較地址集合與子集合的信息熵，利用熵值差異發現涉及地址模式的比特位和相應取值，然后根據這些信息從地址集合中過濾出符合條件的地址。

1 背景知識

1.1 IPv6地址

1.1.1IPv6地址類型

IPv6地址類型可以分為3類：

(1) 單播地址。用來唯一標識一個接口，單播地址具體類別如表1所示。

表1 IPv6單播地址類型

(2) 組播地址。用來標識一組接口，發送到組播地址的數據報文會到達此地址對應所有接口。

(3) 任播地址。用來標識一組接口，發送到任播地址的數據報文會到達此地址對應的某個接口，該接口是由相應路由協議計算出的距離源節點最近的一個接口。

在IPv6網絡測繪中，主要關注IPv6單播地址中的全球單播地址。根據文檔RFC3587[13]，全球單播地址由全球路由前綴、子網ID和接口ID三部分組成。全球路由前綴與子網ID通常由地址前64位表示，用于標識一個網段，接口ID由后64位表示，用于標識網段中的一個設備。

1.1.2IPv6地址分配策略

這部分介紹IPv6地址分配策略，主要關注單播地址后64位，即接口ID部分的分配方式。接口ID的分配并沒有統一固定的方式。有些分配方式具有規律性，能體現出地址模式特征，而另一些分配方式意圖消除模式特征，分配的接口ID呈現很高的隨機性。

RFC7707[14]總結了一些具有規律的接口ID分配方式，如表2所示。Modified EUI-64形式的接口ID分配方式是早期IPv6無狀態地址自動配置 (SLAAC) 采用的方案，后面幾類接口分配方式屬于人工配置IPv6地址的手段。表2列出的地址模式特征只是一部分，事實上，正因為接口ID分配沒有統一的標準，網絡管理員可以靈活地選擇分配方式，因此必然存在許多未公開的地址模式。文獻[11]的實驗也表明網絡中有大量不在表2之中的地址模式。大部分地址模式的共同點就是地址中某些比特位的值是恒定不變的，這也是目前的啟發式算法能夠挖掘的主要地址模式。

表2 一些具有規律的接口ID分配方式

出于安全和隱私保護方面的考慮，一些不體現任何地址模式特征的接口ID分配方式被提出，它們包括：

(1) 臨時地址。針對Modified EUI-64分配方法存在的MAC信息泄露、IP追蹤等安全問題，RFC4941[15]對SLAAC進行了擴展，該方案下SLAAC產生的地址接口ID為隨機生成，并且會隨著時間改變。

(2) 恒定且語義模糊的接口ID。Windows系統對RFC4941的一種實現，接口ID隨機生成，但不會隨著時間改變，并且該接口ID像Modified EUI-64產生的接口ID一樣，在設備遷移至另一個網段時不會發生改變。

(3) 穩定且語義模糊的接口ID。IETF在RFC 7217[16]中提出的另一種SLAAC方案，接口ID隨機生成，但不會隨著時間發生改變，但當設備遷移至另一個網段時，接口ID會發生變化。

(4) DHCPv6隨機生成。一些DHCPv6服務器從地址分配范圍內按順序分配IPv6地址，導致IPv6地址的生成容易被預測，因此RFC5157[17]建議DHCPv6服務器從一個很大的地址池中隨機選取地址進行分配。

這些隨機分配接口ID的方式本身就是為防止地址掃描而設計，即使掌握由這些方式生成的接口ID，也難以從中發現地址規律。因此隨機生成的接口ID對啟發式算法幾乎不起作用，并且還會對啟發式算法挖掘地址模式造成干擾，影響算法效果。

1.2 信息熵

熵是對信息不確定度的一種度量，一些研究者借助信息熵來研究IPv6地址結構，包括挖掘地址模式[9]、對IPv6網段進行分類[7]以及預測活躍網絡前綴[18]。對離散隨機變量X而言，如果X所有可能取值為{x1,x2,…,xn}，每種取值出現概率為p(xi)(1≤i≤n) ，那么X的信息熵H(X)為:

(1)

如果將IPv6地址按照m比特為一個單元進行劃分，每個單元的取值就是[0,2m-1]范圍內的整數。在地址集合中，某一個單元的熵值Hm(X)計算方式如下：用各個取值在地址集中出現頻率f(xi)(1≤i≤2m)替代式(1)中的概率p(xi)，并進行歸一化處理，如式(2)所示。顯然，熵值Hm(X)的取值范圍為[0,1]。

(2)

2 基于信息熵的地址模式過濾方法

2.1 基本假設

這部分介紹過濾方法涉及的一些基本假設：

(1) 地址集合。假設地址集合中的地址同屬于一個/64網段。因為地址的模式特征和隨機性均體現在接口ID的后64位，所以后文主要關注地址的接口ID部分。

(2) 地址模式。這里的地址模式僅指地址在某些位取值恒定不變的接口ID分配方式，并且恒定不變的比特位數目超過一定數量。根據地址模式生成的地址可以在非恒定地址位上任意取值。

(3) 隨機地址。隨機地址的設計初衷是為了消除地址呈現的語義特征，因此假設隨機地址的接口ID各個比特位之間為相互獨立關系，并且每個比特位取0和1的概率是相同的。

2.2 地址集合的隨機化

在介紹本文提出的過濾方法之前，先就隨機生成的IPv6地址對地址集合整體隨機性的影響進行說明。假設地址集合中一部分為具有某一共同地址模式的地址，其余的均是隨機生成的地址。將地址集合中地址的接口ID部分按照半字節 (即4比特) 進行劃分，從左至右依次編號為1,2,…,16。如果地址模式在編號為i(1≤i≤16)的半字節上保持恒定，那么地址集合在該半字節上的熵值Hm與隨機地址所占比例的關系如圖1所示，熵值通過式(2)計算得到。

圖1 不同隨機地址比例下的熵值

由圖1可以看出，隨機地址對地址集合整體表現出的隨機性影響十分明顯，當隨機地址比例達到60%時，半字節上的熵值Hm就已經達到了0.8，地址集合表現出很高的隨機性，目前的挖掘地址模式的啟發式算法面對這種情況很難發揮出效果。

2.3 過濾方法原理

本文提出的過濾方法基于地址集合與子集合的熵值差異，識別地址模式可能涉及的地址比特位以及比特位的取值，進而從地址集合中過濾出符合相應模式的地址。下面將從地址集合中只有一種地址模式和有多種地址模式兩種情況進行說明。

2.3.1單地址模式

首先將接口ID按照若干個比特位為一個單元進行劃分，并對劃分后形成的單元從左至右進行編號。為方便說明，這里以半字節進行劃分。地址模式表現為在若干個半字節上取值恒定，地址集合中一部分地址由某個地址模式生成，其余均為隨機生成的地址。將地址集合根據某個半字節上的取值不同劃分為多個子集合，每個子集合中的地址在劃分的半字節上取值相同，得到的子集合有3種類型：(1) 劃分的半字節不屬于地址模式；(2) 劃分的半字節屬于地址模式但取值不匹配；(3) 劃分的半字節屬于地址模式且取值匹配。

地址集合各個半字節的熵值根據式(2)計算得到。設地址模式對應地址在原始集合所占比例為p，地址集合在與地址模式無關的半字節上熵值為HN，與地址模式相關的半字節上熵值為HR。原始集合與不同類型的子集合的HN和HR隨比例p的變化曲線分別如圖2、圖3所示，其中origin表示原始集合，type1-type3分別表示3種類型的子集合。可以看出，不同類型的子集合與原始集合的HN差異都不大，熵值差異主要體現HR上。

圖2 與地址模式無關的半字節熵值HN隨比例p變化曲線

圖3 與地址模式相關的半字節熵值HR隨比例p變化曲線

3種子集合的HR熵值特征分別為：

(1) 劃分的半字節不屬于地址模式。子集合HR熵值與原始集合的HR熵值幾乎一致，因為劃分子集合的半字節與地址模式無關，所以子集合中包含地址模式的地址比例相比原始集合不會發生明顯變化。

(2) 劃分的半字節屬于地址模式但取值不匹配。子集合的HR熵值始終處于較高水平，因為原始集合除了一種地址模式生成的地址外，其余均為隨機地址。如果劃分子集合的半字節屬于地址模式，但子集合在該半字節上的取值與地址模式取值不匹配，就意味著子集合中幾乎全是隨機地址，因此會表現出較高的熵值。

(3) 劃分的半字節屬于地址模式且取值匹配。子集合的HR熵值明顯比原始集合的HR熵值小，因為這類子集合包含了所有通過地址模式生成的地址，隨機地址只在其中占很小一部分，造成HR熵值相比原始集合出現明顯下降。這類子集合與原始集合HR熵值之差與比例p的關系如圖4所示。由圖4可知，當比例p在4%～88%之間時，熵值差均不低于0.2。

圖4 第3類子集合HR熵值差隨比例p變化曲線

綜上，3種子集合與原始集合之間的不同熵值差異特征可以用來判別地址中哪些比特位可能屬于地址模式，并且可以進一步確定地址模式在相應位置上的取值。

2.3.2多地址模式

如果地址集合中包含多種地址模式，這些地址模式按照當前劃分子集合的半字節可以分為兩類：一類是與劃分子集合的半字節相關的地址模式，記為P1型模式；另一類是無關的地址模式，記為P2型模式。劃分的半字節不同，分類得到的P1型模式和P2型模式也不同。通過劃分得到的子集合會有以下4種類型：

(1) 劃分的半字節不屬于任何地址模式。這種情況與單字節模式的子集合類型(1)類似，由于劃分的半字節不屬于任何地址模式，子集合中各種地址模式所占比例不會出現明顯變化，從而表現為子集合與原始集合的熵值沒有明顯差異。

(2) 劃分的半字節屬于地址模式但取值與所有P1型模式都不匹配。該情況與單字節模式的子集合類型(2)類似。P1型模式地址都不會出現在子集合中，子集合中只有P2型模式地址和隨機地址，會導致子集合的熵值相比原始集合的熵值更大。

(3) 劃分的半字節屬于地址模式且取值僅與1個P1型模式匹配。該情況與單字節模式的子集合類型(3)類似。匹配的P1型模式地址會全部出現在子集合中，使得子集合中P2型模式地址和隨機地址的比例減小，造成與所匹配的P1型模式相關的半字節上熵值降低。

(4) 劃分的半字節屬于地址模式且取值與多個P1型模式匹配。子集合中會包含匹配的多種P1型模式地址，因為這些P1型模式各自相關的半字節和半字節上取值不全相同，可能會導致子集合在各個與模式相關的半字節上熵值減少量降低，特別是當這些匹配的P1型模式在集合中所占比例相近的時候，熵值減少程度會變得十分微小。不過這類子集合不會對地址模式過濾產生明顯影響，因為一個地址模式往往會關聯地址中多個半字節，只要不是所有半字節上都存在(4)這種情況，就可以區分出該地址模式。

通過以上分析可以認為地址模式過濾方法不僅適用于單地址模式的地址集合，也能應用于多地址模式的地址集合。

2.4 過濾方法實現

假設每個地址的接口ID部分按m比特劃分后形成的單元共有n個，從左至右依次編號為1,2,…,n。過濾方法中涉及3個臨界值，分別為：

(1) 子集合最小大小min_size。如果劃分得到的子集合大小小于min_size，則跳過該子集合與原始集合的熵值比較。當子集合過小時，各個取值的頻率很難反映出實際出現的概率，式(2)不再適用。

(2) 地址模式的最小熵值差D。如果原始集合與子集合在某個地址單元上的熵值之差不小于D，則認為該地址單元可能與地址模式相關。否則認為原集合與子集合在該地址單元上熵值差異不大。

(3) 一個地址模式中包含的最少地址單元數N。假設在子集合中，除劃分得到該子集合的地址單元外，有k個熵值差不小于D的地址單元。只有當k+1≥N時，才認為這k個地址單元加上劃分單元可能構成一個地址模式。

過濾方法的流程如圖5所示。

圖5 過濾方法流程

詳細步驟如下：

(1) 首先計算原始地址集合在各地址單元上的熵值，然后按照左至右的順序選取劃分的地址單元，根據每個地址在該地址單元上的不同取值將原始地址集合劃分為若干個子集合。

(2) 每次劃分后，對于所有大小不小于min_size的子集合，計算各自在非劃分地址單元上的熵值，并依次比較每個子集合與原始集合在非劃分地址單元上的熵值差異。對于一個子集合，如果熵值差超過D的非劃分地址單元數目不小于(N-1)，則可以構建出一個可能的地址模式。構建方法為，在劃分單元上取子集合對應的值，在熵值差超過D的非劃分地址單元上取子集合中出現頻率最高的值。一次劃分后，可能有不止一個子集合構建出地址模式。

(3) 如果一次劃分后得到至少一個可能的地址模式，則對這些地址模式進行驗證，否則進入下一步。驗證方法為在原始地址集中查找是否有符合相應模式的地址，如果存在就認為該地址模式有效。如果所有地址模式均無效，則進入下一步；如果至少有一個地址模式有效，則從原始集合中過濾出所有符合有效地址模式的地址，剩下的地址組成新一輪的原始地址，回到步驟1，尋找地址集合中可能存在的其他地址模式。

(4) 判斷進行劃分的地址單元序號是否為n，如果是則過濾過程結束，否則選擇下一個地址單元進行下一輪劃分，回到步驟(2)。

3 測試與分析

測試實驗采用模擬方法，包含以下3步：

(1) 地址集合生成。通過模擬程序生成測試的地址集合，由于集合中的地址同屬一個/64網段，因此只用生成后64位的接口ID部分。集合包含一個或多個隨機選擇的地址模式，除由地址模式生成的地址外，其他地址均是隨機地址。由地址模式生成的地址在地址模式相關地址單元上取值恒定，其他地址單元取值隨機，而隨機地址的每個地址單元上的取值都是隨機的。

(2) 地址模式過濾。用過濾方法從生成的地址集合中過濾出可能具有地址模式的地址。

(3) 過濾結果驗證。用生成階段選擇的地址模式對過濾結果進行驗證，分別記錄過濾結果中與生成時所用模式匹配的地址數Tm，和不匹配的地址數Tu。如果生成的地址集合中根據地址模式生成的地址數為Tg，則評價過濾結果的指標為：漏報數(Tg-Tm)、漏報率(Tg-Tm)/Tg、誤報數Tu、誤報率Tu/(Tm+Tu)。

測試情形分為3種：單地址模式、多地址模式且各地址模式比例相同、多地址模式且各地址模式比例不同。每次測試時，生成的地址集合中地址總數為10 000，劃分的地址單元為半字節，地址模式隨機確定。過濾方法的3個臨界值分別設為如下值：子集合最小大小min_size為30，熵值差閾值D為0.2，模式中最小地址單元數N為4。

3.1 單地址模式

生成地址集合時，地址模式對應地址在集合中所占比例p為1%～95%，變化梯度為1%。每種比例下各進行3次測試，每次測試隨機選擇一種地址模式，每個地址模式涉及的地址單元數4～10不等。

測試結果發現，當比例p在4%～89%之間時，過濾方法能成功過濾出所有具有模式的地址，漏報數和誤報數均為0；當比例p小于4%或者大于89%時，過濾出地址數量為0，漏報率為100%，這個現象符合圖4曲線，因為比例在這個范圍內引起的熵值差小于0.2。

將熵值差閾值D降低為0.15，檢出的比例范圍在4%～92%之間，表示對于隨機化程度極高的地址集合而言進一步減少D提升的過濾效果并不顯著，因此可以認為0.2是一個比較合適的熵值差閾值，在單地址模式情形下能夠從大部分高隨機化地址集合中過濾出與地址模式相關的地址。

3.2 多地址模式(比例相同)

在該項測試中，每次測試隨機選擇的地址模式數量為2～10不等，地址模式的總比例在5%與90%之間隨機選取，各個地址模式所占比例相同，測試共進行200輪。

在200輪測試中，有164輪成功過濾出所有具有模式的地址，其余36輪大部分過濾出的地址數量為0，少部分能過濾出一部分地址。在這些出現漏報的輪次中每個地址模式所占比例均小于4%。200輪測試里出現誤報的次數僅有3次，且誤報數均為1。因此對于比例相同的多地址模式這一情形，過濾方法的效果和單地址模式情形下一致。

3.3 多地址模式(比例不同)

以上兩種測試設定的條件都比較理想，實際上多種地址模式所占的比例一般是不同的，因此該項測試在測試2的基礎上，將各個地址模式所占比例更改為隨機確定，測試共進行200輪。測試結果的漏報率統計如表3所示。

表3 測試結果漏報率統計

在所有出現漏報的測試輪次中，漏報的地址模式在地址集合中所占比例基本上小于4%，比例在4%以上的漏報地址模式僅有3個，它們對應的漏報數量均在2以下。同時，200輪隨機測試中，出現誤報的測試輪次僅有2次，且誤報數均為1。所以可以認為在多地址模式情形下，該過濾方法能夠準確過濾出高隨機化地址集合中所占比例不低于4%的地址模式。

4 結 語

本文提出一種基于熵的從高隨機化IPv6地址集合中過濾地址模式相關地址的方法，該方法通過將地址集合劃分為子集合，比較原始集合與子集合的熵值，從而根據熵值差異識別出地址中可能與模式相關的部分以及相應取值，并以此為條件過濾出相關地址，達到降低地址集合隨機化程度的目的，方便啟發式算法進行具體的地址模式挖掘工作。實驗表明，該方法能夠從大部分高隨機化地址集合中過濾出與模式相關的地址，并且幾乎不會挑選出集合中的隨機地址，可見該方法具有良好的地址模式過濾能力。