別名解析技術研究進展

王占豐，程光，胡超，李晗，翁年鳳，曹華平

（1. 東南大學計算機科學與工程學院，江蘇 南京 211189；2. 東南大學網絡空間安全學院，江蘇 南京 211189；3. 解放軍陸軍工程大學指揮控制工程學院，江蘇 南京 210007；4. 國家計算機網絡應急技術處理協調中心，北京 100020；5. 南京電訊技術研究所, 江蘇 南京 210007）

1 引言

當前，互聯網已成為人類社會的基礎設施，政治、經濟、文化、科技、教育等無不因為互聯網的出現而發生深刻革命[1]。伴隨著接入技術的持續進步和硬件成本不斷下降，網絡深入到人類世界的任意角落，萬物互聯已成為現實。為了更好地使用和管控網絡，人們迫切地希望了解網絡拓撲結構[2-4]，網絡空間測繪與態勢感知成為一個炙手可熱的領域[5-9]，國內外一些知名企業紛紛開展相關研究，建立了許多態勢感知平臺和知識庫，如 Zoomeye、Censys、Shodan、FOFA等。

在網絡態勢分析中，只有將測量獲得的邏輯拓撲與物理拓撲進行映射，才能將觀測到的網絡事件與網絡設備進行關聯[10-19]，這就需要采用別名解析技術。具體來說，別名解析技術就是從網絡測量結果中找出屬于同一設備的IP地址集合，該項技術廣泛應用于路由器級拓撲發現、跟蹤溯源和態勢分析中。別名解析在 2000年左右曾受到廣泛關注，先后有Mercator、iffinder、Ally等著名的測量工具和平臺被提出，但這些測量工具和平臺存在測量開銷較大和使用范圍有限的問題[20-24]。由于IPv4地址在2016年已經耗盡，世界各國都在加緊推進IPv6網絡的建設。由于IPv4和IPv6相互不兼容，針對IPv4的別名解析技術無法完全適應新的網絡架構，從而涌現出一批新的研究成果。為了對別名解析技術形成較為全面的了解，通過 EI、SCI、知網、萬方等文獻檢索工具對別名解析（alias resolution）、別名、IPID、時間戳等關鍵詞的相關論文進行了檢索。在論文檢索過程中，以相關文獻綜述及重要的算法入手，并將所涉及的相關文獻進行了拓展閱讀，檢索內容覆蓋了國內外主要研究團隊的最新成果。

別名解析方法從原理上大體分為基于測量的別名解析算法、基于推斷的別名解析算法和綜合方法3類。基于測量的別名解析算法向不同的IP地址發送探測分組，通過分析響應分組的內容或特征來判定2個或多個IP是否屬于同一臺路由器。基于推斷的別名解析算法通過構建IP拓撲或IP接口名稱來推斷不同的IP地址是否屬于同一臺路由器。基于測量的別名解析方法更為準確，但是對于不響應測量或者響應不完整的網絡設備，基于推斷的別名解析算法也是一種補充。因此，綜合方法是將幾種別名解析方法組合起來從而進行更為全面和準確的判別[25]的一種方法。從技術發展過程看，別名解析方法逐漸從IPv4網絡發展到IPv6網絡，從小范圍的網絡擴展到整個IP地址空間。

2 IP別名解析概述

2.1 典型的別名關系

路由器一般有多個接口，每個接口配有不同的IP地址，如果用一個接口的IP地址代表該路由器，則其他接口的IP地址稱為別名[25]。 別名關系推斷是網絡測量中的一個難題，該問題最早由Pansiot等[26]提出。如圖1(a)所示，2個測量點S1和S2測量到目的主機 D的路徑時，得到的 IP路徑分別為S1→…→R11→R'31→R41→…→D 和 S2→…→R21→R31→R41→…→D。如果不能推斷路由器R'3和路由器R3為同一臺路由器，則會得到圖1(b)所示的拓撲結構。圖1中表示路由器的接口。

圖1 IP別名關系示意

文獻[27]將所有的IP別名關系分為3種情況。

1) 對稱路由別名關系。從不同方向測量2條路徑，如果在網絡中2個 IP處于對稱位置，如圖 2中的接口IP1y和IP2y、IP1z和IP2z屬于同一臺路由器，且互為別名，這種互為別名的IP往往具有相同的30 bit網絡標識。

圖2 IP路徑中存在對稱路段的別名關系

2) 相同后繼別名關系。若測量發現的IP邏輯鏈路＜IPx，IPy＞和＜IPw, IPy＞具有相同的后繼節點，則IPx和IPw互為別名，這種情況又稱為三角別名，如圖3所示。

3) 平行路徑別名關系。如圖 4中的 2條路徑L1=IP1x→…→IP1y→…→IP1z，L2=IP2x→…→IP2y→…→IP2z，若IP1y和IP2y屬于同一臺路由器，則這種情況稱為平行別名。這種情況出現在從同一個方向進行探測，出現負載均衡，或者由不同的路由器策略造成。

圖3 IP路徑中具有相同后繼的別名關系

圖4 平行路徑別名關系

2.2 別名解析基本思路

目前，別名解析算法已達 20余種，然而從別名解析過程來看，所有別名解析算法主要分為3個環節：1) 別名集合篩選，2) 數據探測與分析，3) 別名判定，如圖5所示。

圖5 別名解析算法的一般流程

別名集合篩選主要指將那些可能互為別名的IP地址集從探測目標網絡中過濾出來，從而減小搜索范圍，也稱為別名過濾技術[27-28]。這種別名過濾往往是通過分析潛在的別名關系或者 RFC文檔中關于路由器接口的分配規范來完成的，如Palmtree等算法在探測的目標集合構建時就考慮如何采用先驗知識來減少測量開銷。

數據探測與分析主要依據別名判定的原理進行數據測量與分析，如基于測量的別名解析算法通過測量獲取的響應分組的IPID[23]、路徑信息[29]、時間戳[30]等信息，而基于推斷的別名解析算法則分析網絡的路徑關系[31]和拓撲[32]來為別名判定做準備。

別名判定則是確定2個或多個IP是否為別名，主要依據是RFC文檔或者路由器的配置規范。伴隨著人工智能技術的發展和大數據技術的流行，一些基于機器學習的算法也逐步得到了應用，如TreeNet采用決策樹的思想來進行別名關系的判定[25]；DisCarte算法采用析取邏輯規劃來進行別名判定[33]，AliasCluster算法采用貝葉斯網絡推斷模型與鏈式推理邏輯來進行別名判定[34]。

某些別名解析算法對上述 3個環節進行了簡化 ， 如 Mercator[20]、 iffinder[21]、 Passenger[29]、DisCarte[33]、Pamplona-traceroute[35]等算法將前 2 個環節合并為一個步驟，即從探測數據中獲取可能的別名集合。本文將別名解析算法分為IPv4別名解析和IPv6別名解析兩大類，再分別將兩類算法進行細分，對典型算法的原理進行闡述。

3 IPv4別名解析技術

3.1 基于測量的別名解析方法

3.1.1 基于同源地址的別名解析算法

基于同源地址的別名解析算法是最早的一類別名解析方法，由 Pansiot等[26]提出，在網絡拓撲測量工具 Mercator[20]及別名解析工具 iffinder[21]中均采用了該方法。這種方法通過主動探測來解析IP地址別名。根據RFC1393[36]，向一個IP地址發送一個具有較高端口號、TTL為255的分組，如果返回的“端口不可達”ICMP分組源地址與目的地址不同，則說明該地址與被探測的目標地址是同一臺路由器上的2個別名，如圖6所示。對于2個可能互為別名的IP地址，若響應分組的原地址相同，也說明這2個IP地址互為別名。

圖6 基于同源地址的別名解析算法原理示意

這種別名解析方法的優點在于不會產生誤判，缺點是會受到路由器配置的影響，發現別名的完整性不高。在不考慮網絡擁塞的情況下，當出現以下2種情況時，該算法無法發現別名[21]：1) 如果路由器被配置為“采用收到分組的目的地址作為響應分組的源地址”，那么通過響應分組將無法發現別名；2) 路由器不響應高端口的ICMP測量，據統計網絡中約有 10%的核心路由器從來不響應未知高端口的探測分組。

為了提高IP別名的識別率，使用該技術時可以通過以下3個方面進行優化[20-21]：

1) 可對同一個接口重復發送多個探測分組，因為不同時刻的響應分組會有所不同；

2) 改變分組的封裝方式，因為不同系統在探測時返回的結果會有所不同；

3) 從不同的地理位置發起測量，因路由策略不同，從不同位置發起的探測響應情況會有所不同。

基于同源地址的別名解析算法雖然是為 IPv4網絡而設計，但是經改進后可以適用于 IPv6網絡中，適用的范圍較廣且準確度高。

3.1.2基于IPID的別名解析算法

基于IPID的別名解析算法主要通過IP分組的標識變化來進行別名關系判別。在網絡中，IP分組是通過分組首部的標識字段（簡稱IPID）來區別的，IPID可以標識不同IP分組的多個分片從而進行重裝。每個路由器都具有一個全局的計數器，每發送一個IP數據分組，IPID加1，全局計數器為路由器的多個網絡接口所共享。由于 IPID的值是單調遞增的，那么由同一臺路由器發出的連續分組應具有連續的 IPID值，據此原理，當對同一臺路由器的不同IP地址發送探測分組時，則返回分組的IPID值應該是連續或者相近的。這種方法不受路由器返回分組配置策略的影響。

1) Ally算法

文獻[23]在網絡測量系統 Rocketfuel中提出了基于IPID值進行別名解析的工具Ally。Ally是在Mercator的基礎上提出的，該算法同時綜合基于相同源地址的技術，分析路由器選擇的TTL初始值及路由器對速率限制(rate limiting)情形來對別名關系進行判別。圖7給出了Ally中使用IPID進行別名解析的基本過程。首先，對2個候選IP地址先后發送2個探測分組，從響應分組中獲取的IPID分別為x和y。然后，對上述2個IP再發送2個探測分組，獲得的響應分組的IPID分別為w和z。若返回的IPID滿足關系x＜y＜w＜z，且w與x的值十分接近，則說明2個IP互為別名。在實際網絡中，考慮分組的亂序等因素，只要x與y之差小于一定的閾值，仍可以認為2個IP為別名關系。Ally算法受閾值的影響較大，一般閾值設置為 200，可以根據發送分組間隔長短進行調整。文獻[23]的實驗證實了這種技術存在錯判和解析不完全的問題。同時，這種技術還有一個缺點，即效率比較低，需要O(n2)次的成對測試，在慢速網絡和不響應的路由器較多的情況下，別名解析的耗時會很長。

圖7 Ally別名判別的原理

為了提高別名解析的效率，文獻[23]對別名解析的范圍采用啟發式算法進行了限定：一是采用DNS系統中的層次化命名，對高度相似的域名進行別名判定，如chi-sea-oc12.chicago.isp.net與chi-sfooc48.chicago.isp.net；二是對于返回的 TTL值較為接近的IP進行別名關系判定；三是利用別名的傳遞關系進行判定，如若IP1與IP2互為別名，IP2與IP3互為別名，則說明IP1與IP3互為別名。

Ally算法的不足之處在于容易受到網絡性能影響，從而導致分組亂序，其應用范圍受到路由器是否采用共享IPID計數器的制約。

2) RadarGun算法

Bender等[37]發現共享一個IPID計數器的2個IP接口，在相近時間段內其響應分組的變化趨勢十分接近，從而提出了算法RadarGun。該算法不再對IPID值的連續性進行比較，而是為每個IP進行一組探測，分析不同IP響應結果構成的IPID時間序列變化趨勢的近似性。若變化趨勢一致，則認為 2個IP互為別名，否則不是別名關系，如圖8所示。RadarGun具體做法如下。

① 首先，對于n個待判別的IP接口，不是針對每2個進行測量，而是針對每個IP進行一個序列的探測，從而得到不同的IPID序列。設存在3個IP地址IPa、IPb、Pc，RadarGun依次對3個IP進行測量，返回的 IPID序列如下：A1,B1,C1,A2,B2,C2, …。如此，針對每個IP得到一個IPID序列，以IPa為例，表示為{ti,Ai}，其中，ti表示第i時刻，Ai表示第i時刻的IPID，0＜i＜N，N表示測量的次數。

② 為了保證算法的有效性，RadarGun會過濾一些無效的序列，如不響應的分組超過整個序列25%的、IPID為0或常數的、IPID為非線性序列的[37]等序列。

③ 對任意 2個有效的序列引入采樣距離函數進行檢驗，具體如下。

對于任意 2 個序列{ti,Ai}、{tj,Bj}，若tA,i＜tB,j＜tA,i+1，采用線性插值法獲得序列{ti,Ai}在tB,j時刻的IPID估值IDA,est，然后計算IDB,j與估值的距離δB,j=|IDA,est-IDB,j|，采用同樣的方法計算δA,j，最后計算2個序列的平均距離，如式(1)所示。

④判別2個IP地址是否為別名。如果ΔA,B＜200，則2個IP互為別名；如果ΔA,B＞1 000，則不是別名關系；如果200≤ΔA,B≤1 000，則需要進一步分析。

RadarGun雖然能夠解決分組亂序所帶來的問題，然而該算法仍然是基于閾值的，仍會受到網絡性能等因素的影響。

圖8 RadarGun別名判別的原理

3) MIDAR

Ally和RadarGun雖然在一定程度上能夠提高別名的解析效率，但是要對整個 IP地址空間或者大量IP地址進行解析，則需要做進一步優化。Keys等[38]對Ally和RadarGun算法從2個方面進行了改進：①如何對目標集進行測量，并對所有的O(N2)個別名關系進行判別；② 如何降低假陽率以提高別名解析的正確性。MIDAR（monotonic ID-based alias resolution tool）通過優化采樣間隔，引入單調邊界檢驗函數（MBT, the monotonic bounds test），采用多種探測方法來提高響應率，提出多個測量點協助測量及通過滑動平均窗口來提高算法的擴展性。

MIDAR的工作原理較為復雜，實際上是一個復雜的別名解析系統，適用于大型網絡測量平臺及大規模的別名解析，總體分為5個階段。

① 估計階段（estimation stage）

估算階段主要解決2個問題：一是對不同的目標主機選擇合適的測量方法；二是確定采樣時間間隔。測量時將所有待定的IP地址集合平均地分配到所有的測量點上，對每個目標IP采用所有的方法進行嘗試。

② 發現階段（discovery stage）

發現階段主要判斷 IP地址是否采用同一個IPID計數器。根據估計階段確定的測量速度來確定測量的滑動窗口，并采用最佳的測量方法對所有IP發起測量，對所有交疊時間序列進行檢測。檢測采用前文所述的MBT算法。

③ 消除階段（elimination stage）

對可能是別名關系的IP地址對重復使用MBT函數計算從而減少假陽率。為了進一步減少探測分組，將所有的IP構建在一棵拓撲樹上，對所有劃分在同一棵子樹的IP別名對進行探測，每棵子樹探測10次，其中，每棵子樹的間隔不超過整個樹空間距離的5%。實驗表明這種探測僅多使用15%的流量。

④ 驗證階段（corroboration stage）

驗證階段采用消除階段的方法對所有的 IP進行探測，但所驗證的IP地址僅是消除階段不能確定別名關系的IP地址集，因此輸入集合更小。

⑤ 別名推斷階段（final alias inference）

前3個階段對IP地址對進行了篩選，驗證階段僅對位于同一棵子樹上的IP接口進行別名檢驗，而別名推斷階段將對所有別名的關系進行分析從而進行綜合判定。如A和B互為別名，B和C也互為別名，然而判定出A和C不是別名關系，則說明判定中存在誤判，將這些可能存在誤判的別名從集合中移除。

4) Pamplona-traceroute

基于IPID的別名解析算法研究分為2個方面，一方面是不斷提高算法精度，另一方面是在控制預測精度的情況下，通過減少測量開銷，提高算法效率。Pamplona-traceroute在上述2個方面進行了嘗試，將測量與推斷隱含于 traceroute測量過程，基于IPID的間隔和變化規律來進行別名關系推斷[35]，具體分為3個階段。

第一階段進行測量，通過分析獲取響應的IP地址、TTL、響應分組的IPID和響應分組的時間戳。該算法支持UDP、TCP和ICMP等3種不同類型的探測，為了避免負載均衡的影響采用了成對的探測分組。

第二階段將所有測量數據發送到一個測量服務器，從這些數據中篩選出采用共享 IPID計數器的路由器。

第三階段進行別名解析，將所有的分組中時間戳較為接近的IP地址對按照類似于Ally的方式進行分析，如IPID必須是單調增加的、IPID必須小于一定的閾值、分組的時延小于一定的閾值等。

Pamplona-traceroute算法將拓撲測量與別名解析進行了融合，并通過對 traceroute進行了改造，從實驗對比結果看該算法精度高于其他算法。但是該算法需要大規模的測量設施并需要節點間的協調，因此在實施過程中存在一定的困難。

相比基于相同源地址的別名判別算法，基于IPID的別名判別算法可以提高別名解析的完整性，同時具有較高準確度，但同樣存在著漏判和誤判的不足，主要原因如下：① 算法中閾值的選擇受到網絡性能和設備特征的影響，此外探測分組在中間路由器重新排隊等因素都會對該閾值產生影響，如果閾值設置太大，解析的結果就會存在假陽，反之，就會漏報；② 一些路由器會將路由器的計數器設置為0或者不使用計數器，這種情況下此類算法失效；③ 有些路由器共享一個計數器但是為每個接口單獨計數，這樣互為別名的2個接口之間的IPID值就不再接近了；④ 存在與探測源跳數相同的2個不同路由器具有相近的 IPID值的情況，雖然這種情形的概率很小。

3.1.3 基于時間戳字段的別名解析算法

IP協議中包含一個預定義IP時間戳選項，啟用此選項后，若分組經過路由器的IP包含在預定義IP地址集中，則該路由器會在分組中添加自己的時間戳。使用該選項時，預定義IP數不能超過4個，而且路由器會按照預先定義的次序逐一進行標記。據此可知，如果2個IP互為別名，所添加的時間戳應該相同。根據上述發現，Sherry等[30]提出了一種基于時間戳的別名解析算法Timestamp。

Timestamp算法分為4步：首先向所有可能為別名的 IP發送分組(A|AXXX)排除那些會增加額外時間戳的分組，其中X表示一個不會出現在測量路徑上的IP地址；然后針對可能互為別名的2個IP地址A和B，從不同的測量點發送 2個探測分組(A|ABAB)和(B|BABA)，每個探測點測量5次；所有出現4次時間戳的IP地址為別名。對出現2次時間戳的2個IP進行時鐘測試，要求時間戳單調非減而且90%的時間戳都是相同的，通過時鐘測試后再判定其是否為循環路徑，從而判定其是否為別名。

由于Timestamp采用了ICMP協議，而ICMP的端口不可達會引發錯誤直接插入探測載荷中，再發回測量主機。Marchetta等[39]提出的 Pythia算法采用 UDP協議來構建分組，同時在一個測量過程中引入多個別名IP，從而減小測量開銷。Pythia算法分為2個階段：1) 預先準備階段；2) 別名解析。在預先準備階段采用與Timestamp相近的方式獲得支持時間戳路由器及相關IP集合，對別名集合進行過濾。在別名解析階段，具體分為3個步驟：① 從別名集合中選擇一個IP地址A作為基準，然后提取可能和該IP互為別名的IP集合β；② 從IP集合β中選擇4個IP構成分組(A|ABCD)，然后通過返回的時間戳發現別名，如果B不是別名，將B從IP集合β中移除，否則加入別名集合，同時重新構建探測分組，如(A|ACDE)；③ 重復上述過程直到對所有IP都進行了別名解析。與其他別名解析算法相比，Pythia算法一次可以最多測試4個IP地址的別名關系，提高了別名的發現效率。

Pythia算法的不足是測試別名的關系數目有限，而且僅限于網絡的前幾跳，因此，這種算法適用于網絡邊緣靠近測量點的地方，對于距離測量點較遠的路由器無法采用該方法進行探測，需部署大量測量節點才能得到較為全面的結果。

3.1.4 基于路由記錄的別名解析算法

Sherwood等[29]提了一種基于路由記錄來推斷別名的算法Passenger，該算法在traceroute分組的報頭中加入了路由記錄（RR, record route）選項，路由器收到分組后會將路由器地址加入到分組頭部中并更新頭部的偏移量。實際上 traceroute發現的路徑與路由記錄的路徑并不重合。RR記錄的是路由器出向接口(outgoing interface)的地址，而ICMP分組記錄的是進向接口(incoming interface)的地址，因此當TTL=1時，RR中不會有任何記錄，而當TTL=2時，RR中記錄的IP接口就是TTL=1時ICMP分組返回地址的別名，依次類推即可以進行別名推斷，具體如圖9所示。由于IP頭部長度有限，RR記錄的路徑長度最多不超過 9跳。在traceroute測量中引入使用分組路由記錄功能具有以下好處：1) 從某種程度上可以發現那些不響應ICMP測量的路由器；2) 可以發現隱藏的路由器；3)發現多連接的路由器；4) 發現中間路徑中前9跳內路徑的不穩定性。

圖9 Passenger算法原理

Sherwood等[33]又對 Passenger算法進行了改進，提出了DisCarte算法，在原有算法上引入了析取邏輯規劃（DLP, disjunctive logic programming）對別名推斷過程進行形式化表示。DisCarte算法的求解過程十分復雜，大致分為2個階段：1) 數據預處理，根據不同廠商對于路由記錄協議的實現對數據進行分析；2) DLP求解，也就是將所有的判別轉換為邏輯表達式，然后進行求解。

基于路由器記錄的別名解析算法雖然引入了新的別名解析思路，但也存在一些不足：1) 采用RR選項的分組會引起路由器的過濾，或被入侵檢測系統視為入侵流量；2) 不同的路由器廠商對于RFC791[40]的實現規則不盡相同，需要對不同廠商的協議實現細節進行分析，要考慮循環路由、防火墻、協議實現、隱匿節點、路徑長度等眾多因素。此類算法對路由器的要求較高，可以作為一種輔助的別名解析方法，用于提高解析的正確率。

3.1.5 基于IGMP的路由器別名解析方法

隨著多播技術被廣泛地應用于視頻、音頻等領域，越來越多的路由器開始支持網際組管理協議（IGMP, internet group management protocol）。高歌等[41]提出了一種基于IGMP的路由器別名解析方法，其工作原理是向目標路由器發送IGMP組播分組中的Ask_Neighbors分組，目標路由器收到探測分組后會返回給源地址一個 Neighbors_Reply分組。根據協議，目標路由器會將其接口信息、鄰居接口的信息及該路由器接口的相關屬性信息放入返回的分組中。以圖10為例，測量節點對目標路由器R1發起探測，路由器R1收到探測分組后發送一個響應分組，此分組信息包含路由器R1的接口地址和接口屬性信息，以及與其相連的鄰居路由器 R2～R4的接口地址和部分接口屬性信息。在某些情況下，分組返回的所有信息并不完整，可能是部分接口信息，因此需要對不同的端口進行探測從而保證完信息的整性。

圖10 基于IGMP的別名解析過程實例

高歌等[41]提出的算法是在 mrinfo工具上改進而來的，原始的mrinfo收到一個響應分組后就停止接收，當同時對多個目標進行探測時會導致數據丟失。為了避免上述情況的發生，改進后 mrinfo+按照IP地址對收到分組進行比對，如果收到來自相同源地址的分組則丟棄，否則進行處理提取接口作為別名。在測試環境中，此算法探測的效率和準確性方面要高于其他別名解析算法，但是其受到路由器是否支持IGMP協議的限制。根據文獻[41]對94 280個IP地址的探測結果表明，僅有9 797個目標地址響應探測，然而在實際網絡中這個響應比例可能會更低，并且大量的路由器會對IGMP探測進行過濾[42]。

此算法由于探測分組會被過濾而導致算法的可用程度大幅下降，僅可作為一種補充性的測量方法，無法在網絡中普遍使用。

3.2 基于推斷的別名解析算法

3.2.1 基于DNS域名的別名推斷算法

基于DNS域名的別名解析算法(DASAR, DNS based alias resolution)是對IP地址的域名進行DNS反向查詢，然后通過域名的語義分析來推斷域名的別名關系[32]。其基本思想是，對路由器的多個接口地址做反向 DNS地址查詢，將域名劃分為不同的段，然后按照逆序進行對比。例如，sl-bb21-lon-14-0.sprintlink.net和 sl-bb21-lon-8-0.sprintlink.net所對應的IP地址是別名，根據“lon”可以猜測2個域名屬于同一臺倫敦的主干路由器，而“14-0”“8-0”可能對應于路由器上的端口。

基于 DNS域名的別名推斷算法的準確性依賴于域名命名方式，不同ISP可能采用不同的命名方式，因此對于不同ISP需要設計不同的推理規則，同時域名信息更新的及時性和命名的范圍都會影響算法的使用范圍。這種算法雖然簡單，但是其準確性和使用范圍都有限。趙洪華等[28]對中國、日本、韓國等國家的路由器分析表明，路由器端口采用域名進行標注的在所有路由器端口中的比例很低，因此，這種算法無法大規模使用，可作為一種補充性的解析方法。

3.2.2 基于拓撲的別名推斷算法

基于拓撲的別名推斷算法利用 IP地址的連接關系和約束對 IP的別名關系進行推斷，其基本方法如下：對可能是別名關系的 IP地址對采用 traceroute測量路徑信息，然后將這些信息構建成一張有向圖，其中，節點為路由器接口的 IP地址，邊表示2個IP地址間是否存在一條鏈路，方向是從測量源到目的地址的測量方向。Spring等[32]總結出2條規則來進行別名關系分析，具體如下。

1) 具有相同直接后繼的IP地址可能互為別名一般路由器之間的連接為點對點方式，在這種情況下具有相同直接后繼的 IP地址可能互為是別名。通過拓撲測量獲得IPA、IPB、IPC的連接關系如圖 11(a)所示，其中 IPC為 IPA和 IPB相同后繼，如果路由器之間是點對點連接，則它們之間路由器拓撲如圖11(b)所示。

圖11 具有相同后繼的IP地址是別名

2) 在同一條traceroute路徑中出現的IP地址不是別名

這條規則的前提是網絡中不存在循環路徑，對于采用多路訪問技術或交換網絡連接路由器的情形，這種方法就會產生誤判。實際上這一規則并不用于判斷別名關系，而是用于排除不可能為別名關系的IP地址對，從而減少測量和判別的IP地址對的數目，對于一個長度為n的路徑，此規則就可以減少Cn2次判別計算。

基于以上原則，一些利用網絡拓撲結構來進行別名關系推測的算法被提出，如 AAR[31]、APAR[43]、Kapar[44]等。

1) AAR別名解析算法

基于上述規定，Gunes等[31]提出了AAR (analytical alias resolution)別名解析算法，其基本思想是對任意一條網絡路徑從2個方向進行測量，獲得該路徑上所有路由器兩側的IP地址，然后通過比較分析判定往返路徑中同一跳的IP是否滿足“/30”和“/31”的情況，對稱路由如圖12所示。

圖12 對稱路由示意

Gunes等[31]對南衛理公會大學（SMU,Southern Methodist University）和耶魯大學（Yale University）之間的往返路徑采用 traceroute進行了測量，得到的路徑如表1所示。通過檢驗，可以發現從第2行到第10行中往返2個方向上的IP地址均滿足屬于“/30”或“/31”的同一個子網，如 129.119.0.249和 206.223.141.90互為別名，206.223.141.89和206.223.141.69互為別名。由此，可以得到SMU和耶魯大學（表1和圖13中簡寫為Yale）的網絡連接拓撲，如圖13所示。

表1 trcaceroute雙向測量獲得的網絡路徑

圖13 SMU和耶魯大學的網絡連接拓撲

Gunes等[13]在Abilene網絡中對AAR別名解析算法進行了測試，與其他算法相比，該算法在開銷和完整性方面具有很大優勢。然而，這種算法在實際應用中存在著很大的局限性，因為其數據采集必須是端到端的雙向測量。為獲得這樣的數據，必須進行端與端之間2個方向的協作，因此在大規模網絡中，這種方法難以實施。

2) APAR

為了克服 AAR算法的不足，Gunes等[43]又提出一種基于分析和探測的別名解析器（APAR, analytic and probe-based alias resolver）。APAR 不僅考慮了路由器之間的點對點連接的情況，還考慮了多個連接的情況，這就意味著必須拓展子網的范圍。該算法共分為 2個步驟：① 從收集的路徑信息中提取可能是別名集合的數據集；② 使用別名子網對別名進行解析。

在子網段提取階段，APAR在traceroute探測到的大量地址中推斷子網信息。首先，將所有的IP地址中具有相同“/22”前綴的地址劃分為一個子網（或子集）。然后，檢驗這些地址是否滿足正確性約束、完整性及處理次序3個約束條件，其中準確性約束是指若這個子網中的任何一個廣播地址出現在traceroute數據中，則該子網不為真；完整性約束是指在 traceroute路徑中至少發現一半的子網地址；處理次序是指首先對完整率高的先處理，對于完整率相同的則處理涉及路徑較多的子集。

在形成子集后，對子集的判定又有3個規則，分別為：無循環路徑、相同鄰居節點和距離測度[45]。無循環路徑是指所有可能為別名的任意2個IP不能出現在同一跳路徑上。相同鄰居節點是指2個互為別名的IP具有相同的前繼節點或后繼節點，或者這些節點互為別名。距離測度是指從一個測量點到互為別名關系的 IP測量獲得路徑長度應該相同或者接近。其中，最后一個規則是個可選條件，在可以進行測量時使用。

3) Kapar算法

APAR具有更高的準確性，同時考慮了路由器多連接的情況。Keys等[44]對 APAR進行了改進和優化，提出了Kapar算法，該算法避免了將所有的路徑信息存儲到內存中，提高了算法性能。與APAR相反，Kapar算法在測量數據上通過一個檢測合并使用最少的信息，具體如下。

① Kapar將所有的路徑數據劃分為3跳分段數據。

② 通過分析路徑文件生成不可能存在別名關系的子網的列表，子網長度在24位以上。

③ 為每個路徑分配一個ID，存儲所有的IP信息，根據這些信息可以分析是否存在循環路徑。

此外，Kapar還從其他幾個方面改進了 APAR算法，具體如下。

① 可以使用其他來源的別名集合，如通過指紋解析獲得的別名集合。

② 在子網信息階段，采用了更加嚴格的算法來判定點到點的子網。

③ 在別名推測階段，對鄰接關系采用了更加嚴格的判定算法。

④ 綜合使用多個觀測點獲得TTL數據來降低別名解析假陽率。

總體而言，基于推斷的別名解析算法在原理上更加復雜，這些方法大多借助網絡的拓撲結構進行推斷，為了獲取全面的網絡拓撲地址信息，必須進行分布式測量，從而導致算法實現起來較為困難。因此，此類算法在有測量數據集或者分布式平臺的情況下才能更好地得到應用。

3.2.3 基于機器學習的別名推斷算法

在前期研究的結果上，AliasCluster算法[34]將機器學習的方法引入到別名解析中，試圖僅采用traceroute而不增加測量開銷來實現別名解析。該算法分為2個階段，具體如下。

階段1 通過traceroute測量收集數據，分析獲得的3個數據特征（IP子網、出入度、跳數等），采用貝葉斯網絡推斷模型推斷2個IP互為別名的概率。

階段2 考慮到一個路由器可能具有多個別名地址或者缺乏足夠推斷信息，引入鏈式推理方法將2個IP地址視為一個聚類，如果2個聚類的相似性較為接近就進行合并，從而通過推斷發現新的 IP地址別名關系。

AliasCluster算法采用了機器學習的方式，精度受到參數設置影響，但是為設計新的解析算法指明了方向，特別是在缺乏足夠探測信息的網絡條件下。

除了AliasCluster算法外，Grailet等[25]提出TreeNet和 Sherwood等[33]提出的 DisCarte算法也引入了機器學習的思想和方法，本文分別在3.3.2節和3.1.4節進行詳述。

綜上所述，機器學習方法的引入使別名解析過程中可以使用多種探測數據和指紋信息，采取更加復雜的邏輯推理，從而提高別名解析效率，因此如何更好地使用機器學習方法來進行別名解析將成為新的研究方向之一。

3.3 綜合測量法

實際上隨著基于測量和基于推斷兩類算法研究的不斷深入，為了減少測量復雜度，提高測量精度，一些綜合性的別名探測算法被提出，如Palmtree 算法[46]、TreeNet算法[25]。

3.3.1 Palmtree算法

Tozal等[46]綜合考慮路由器接口IP地址的分配方案與同源地址IP別名解析的原理，在此基礎上提出了Palmtree算法，該算法的基本思想如下。

1) 首先探測目標的IP地址是否活躍。

2) 如果探測的目標IP是活躍的，則分析探測節點到目標IP的跳數。

3) 根據RFC 4632中路由器接口的分配方案，對“/31”或“/30”的子網中的IP地址進行探測，然后采用同源地址的方法判斷別名關系。

該算法聲稱可以將探測的復雜度降低到線性復雜度，實際上在缺乏全局先驗知識的情況下，其探測復雜度也是較大的。因此，該算法可以適用于對特定網絡的別名判定。

3.3.2 TreeNet算法

Grailet等[25]提出了一種綜合各種測量方法的別名解析算法 TreeNet，該算法分為 3個步驟：首先，通過拓撲測量將所有的 IP別名劃分為小的集合，從而避免了大規模探測，劃分時所有IP節點的路徑跳數不能超過 1跳，拓撲探測中采用ExploreNET算法[47]；然后，采集所有別名的指紋信息，主要包括TTL值、端口不可達分組源地址、IPID、DNS的解析結果及時間戳信息；最后，將上述采集的信息，按照指紋信息的可信度進行分類，依次為UDP探測的響應、IPID序號、DNS解析結果等，從而進行綜合的別名解析。TreeNet算法可以看做是iffinder、Kapar等算法的結合體，實驗證明該算法可以采用較少的探測分組實現與MIDAR、Kapar類似的精度。

TreeNet算法需要集合多種別名解析工具，實現方法較為復雜，但其精度和準確度都是較高的，適用于大規模的別名解析。

4 IPv6別名解析技術

IPv6協議不僅擴展了IPv4地址空間的范圍，而且對 IP分組的分組格式等方面也做了修改[48]，如 IPv6網絡層不再支持大數據分組的再分組與重裝，而是由應用層負責完成，同時IPv6增強了對組播和流控制的支持、自動配置及更高的安全性和較小的路由表。由于種種原因，IPv6標準雖然已經提出了20多年，但是仍然沒有得到廣泛的部署和使用，僅在部分骨干網絡和試驗網絡中得到了應用[40]。隨著IPv4地址的耗盡，IPv6的部署進度不斷加快。據統計，全球IPv6的BGP（border gateway protocol）前綴通告呈現出指數級增長，超過 6 000個 AS（autonomous system）宣告了IPv6可達，約占所有AS數的15%，因此，研究IPv6的網絡拓撲及別名解析正變得更加緊迫[49]。

由于IPv6網絡與IPv4網絡設計上的差異，許多可以用于 IPv4網絡的別名解析技術無法應用于IPv6網絡。先后有一些研究者提出了基于源路由、誘發式IPID的IPv6別名解析技術和基于前綴的別名解析算法，如 Atlas[50]、RMP[51]、TBT[52]、Speedtrap[53]、UAv6[54]等算法。

4.1 基于源路由的別名解析算法

路由器在檢查分組跳數限制之前通常會先處理路由擴展頭部。Atlas對2個可能互為別名關系的IP地址對(x,y)，將向y發送跳數限制設置為到x跳數的UDP分組。如果2個IP互為別名，則會收到“跳數超出限制”和“端口不可達”的響應分組。文獻[51]發現在所有響應分組中，“跳數超出限制”的響應分組主要是由路由器的注入端口產生。因此，要發現y的別名，必須將分組的超時限制設置為y的跳數，從測量點V通過x和y向目標地址D發起測量，才會收到來自于y的超時響應分組，這樣就需要一個足夠大的地址集，來尋找互為別名的IP地址。Qian等[55]又提出在IPv6分組的頭部加入一個亂序的比特序列，從而通過多個測量點發起測量捕獲別名關系。

基于源路由的別名解析算法不足在于：1) 路由器是否支持源路由，若不支持則方法無效；2) 上述算法采用UDP協議，如果不支持UDP協議則方法無效。因此，基于源路由的別名解析算法只適用于部分路由器。

4.2 基于誘發式IPID的別名解析算法

4.2.1 TBT算法

Robert等[52]利用 IPv6的特點提出了一種誘發式IPID的別名解析算法（TBT, too-big trick），其基本過程如下。首先，測量點發送一個1 300 B的數據分組，這個分組超過了IPv6協議MTU的1 280 B限制，同時又小于IPv4協議的MTU限制的1 500 B，因此當接收者收到該數據分組時會將數據分組返回給發送者。此時，測量點再根據IPv6協議發出一個“Too Big”分組，探測目標收到此分組會將發送緩存設為1 280 B。然后，測量點再發送一個1 300 B的測量分組，探測目標會將分組拆分為2個分組進行發送并加入分段ID。此后，測量點發送的分組都會進行類似拆分，而同一個路由器不同端口發送的分組的ID必然相近，因此可以判定出別名關系。TBT算法如圖14所示。這種誘發式的別名探測方法準確率十分高，而且減少了測量數據。

TBT算法雖然具有較高的準確性，但是探測的數據量相對于IPv4的IPID方法的數據量要大很多，同時探測的次數隨著別名數的增加迅速增加，會帶來較大的網絡負載。

圖14 TBT別名解析算法原理

4.2.2 Speedtrap

Luckie[53]將誘發式的IPID探測技術與IPv4別名解析中的單調邊界測試函數相結合，提出了IPv6的別名解析工具Speedtrap，從而可以進行整個網絡范圍內的數據IP別名解析。Speedtrap別名解析的基本過程如下。

1) 通過測量確定響應分組中帶有 IPID的網絡接口集合，目的是過濾掉那些不響應測量和采用隨機計數器的路由器。實際上除了 Jupiter路由器外，華為、思科、惠普等多數路由器都響應測量。

2) 確定哪些接口可能共享一個計數器，即哪些 IP位于同一臺路由器上。將響應網絡接口的IPID按照時間劃分為不同的組，然后對不同的2個接口地址進行探測，形成備選的別名關系集合。

3) 將不同路由器上的計數器進行區分，對可能是別名的IP進行反復測量，這樣使不位于同一臺路由器的接口返回的IPID差距變大，若IPID不再滿足MBT約束則將其從別名集合中刪除。

4) 對IP別名進行探測和確認。對還在別名集合中的任意 2個接口進行測量，檢測其是否滿足MBT條件，從而進一步確認其別名關系。

采用Speedtrap對52 969個IP接口進行了測量和分析，共耗時9 h，其中5.5 h用于確定接口的響應分組是否包含IPID。實驗表明有17 002個接口響應測量，發現了11 181臺路由器。探測時間較長的原因是：為了誘發路由器對IPv6分組進行分組，需要發射的分組要比IPv4大46倍（至少1 280 B），由于數據量較大，故探測時間較長。在真實網絡的訓練集中測試發現，Speedtrap的正確性可以達到99%以上。

相對于TBT算法，Speedtrap的效率得到了提升，但是TBT算法和Speedtrap算法都需要接口共享計數器才能實現。統計表明，在實際部署的路由器中，僅有32%的路由器采用共享的計數器[53]，因此，這類算法只能適用于部分路由器。

4.3 基于前綴的別名解析算法

Padmanabhan等[54]通過對IPv6端到端的IP地址配置方式進行了研究，發現在 IPv6中采用了與IPv4相似的配置方式，多數采用“/126”前綴。基于此提出了UAv6算法，該算法分為2個階段，具體如下。

1) 進行可能的別名集合探測。對一個 IP的“/126”子網進行探測，如果該前綴所包括的4個IP地址均能響應ICMPv6的探測，則不會出現任何別名，當有2個IP地址響應時才能出現別名，設不響應的地址為X1、X2，返回的源地址為Y，將其記錄下來。

2) 對于可能的別名集合進行檢測。為了檢驗是否為別名，采用 traceroute或路徑的最大傳輸單元來進行檢測。如果某個X1位于Y的路徑上后一跳，則說明X1不可能為別名，反之亦然。

UAv6算法提出了一種新的別名解析方法，但是該算法的復雜度較高，同時與IPv4中的相同源地址方法原理基本相似，不受路由器計數器及源路由的影響，可以與其他IPv6別名解析算法進行互補，從而提高解析的全面性。

5 算法對比與分析

5.1 算法綜合分析

別名解析算法設計原理各異，適用于不同網絡環境。下面從算法的準確性、完整性、開銷、易用性、使用范圍等幾個不同的角度對這些算法進行綜合對比，從而發現別名解析算法研究趨勢，如表 2所示。

準確性：推斷的別名關系是否正確。

完整性：對別名是否能夠發現測量范圍內的所有別名關系。

開銷：用于探測別名所用探測分組的數量。當需要發送分組越多時，網絡流量和時間越多，效率越低，反之，效率就越高。

簡易性：算法使用是否簡易，是否需要很多外部條件支持，即算法實現的難易程度。

協議：算法適用的IP協議，包括IPv4和IPv6。

適用場景：算法的部署方式以及范圍。

時間：論文發表時間。

實際上在各種別名解析算法中，主要有3個影響算法使用的因素：適用范圍、準確性和效率。眾所周知，如果算法能夠集中部署，則大規模應用較為容易；如果需要分布式測量往往不易實現。基于探測的算法中，如基于同源地址的 Mercator[24]、iffinder[25]、Alas[50]算法，基于 IPID 的 Ally[23]、RadarGun[37]、MIDAR[38]、TBT[52]、Speedtrap[53]等均可以通過集中部署的方式來實現，而基于圖論或拓撲的算法往往需要大規模的分布式測量來實現，在實際操作中難以實現，因此，這些算法往往借助于Ark、PlanetLab等大型測量項目才可以部署。

為了對算法的準確性和效率有個全面的認識，對典型算法的精度和時間效率進行了對比，結果如圖 15所示，該結果綜合了 Garcia-Jimenez[35]、Padmanabhan[54]等實驗結果。考慮到實驗的差別，本文參照相關論文進行了定性對比。從圖中可以發現基于同源地址的算法最為準確，而采用 IPID的算法次之，基于網絡拓撲的推斷算法則需要較大的開銷，同時無法保證算法準確性，在以后的算法設計中應充分考慮上述因素。

為了進一步說明算法的演化過程理清研究思路，采用圖形進行了展示，具體如圖16所示。從算法的演化過程可以發現，基于IPID及拓撲的算法最多，也是發展最為迅速的研究方向，同時新的算法綜合考慮了各種要素，綜合運用各種別名指紋，而采用時間戳、路由記錄字段的算法則研究的較少。此外，可以發現針對IPv6的別名解析算法由于IPv6的快速部署而受到重視，成為這幾年研究的熱點。但IPv6別名解析算法主要集中在IPID或者是同源地址的方法，而采用拓撲推斷的算法較少。這主要是因為IPv6在近幾年才得到了大規模部署，其測量數據較少，缺乏必要的數據支撐。

5.2 未來研究方向

通過前文分析可以發現 IPv4別名解析研究比較成熟，而針對IPv6的研究則處于起步階段，為此結合別名解析中的3個階段提出如下建議。

表2 別名解析技術對比

圖15 不同算法精度和復雜度的對比

1) 別名空間的選擇

別名空間選擇目的在于縮小可能互為別名的 IP地址范圍，從而減少探測開銷，提高解析效率。在 IPv4空間中，由于地址空間有限，隨著計算能力的提高和網絡帶寬的擴展，一些快速掃描技術如 Zmap[56]、Masscan[57]等可以在很短時間內實現對網絡空間的掃描，從而為 IPv4的別名解析提供數據支撐。但是，IPv6地址空間十分巨大，按照現有的掃描速度需要1030年才能掃描結束[58]。在如此稀疏的 IP地址空間中要想縮小別名的搜索范圍有2種方法，一是挖掘路由器別名分配規律，二是通過全量測量發現所有活躍IP地址。

圖16 別名解析算法演化過程

針對如何發現路由器別名的分配規律，文獻[38]對IPv4別名進行了分析。圖17是22 515對IP別名中2個IP地址的距離的累計分布概率，即2個互為別名的IP地址如果將其轉換為整數后的差異。從圖中可以發現在一個“/24”（即 IP之間的差小于128）位IP子網內互為別名的IP地址不足30%，而一個“/16”（即IP之間的差小于65 536）位子網中互為別名的IP地址約為50%，這說明即便在密度很高的IPv4網絡中，IP地址別名的距離也較大。在IPv6網絡中，IP地址資源更為豐富，因此試圖發現路由器的別名的分配規律來縮小別名的探測范圍變得更加困難。

圖17 IP別名之間的距離累計分布函數

針對如何發現所有活躍IP地址的問題，解決方案為實現對 IPv6空間的快速探測，從而根據IPv6的接口分布規律來進行別名關系搜索。關于IPv6地址空間的快速探測研究有很多[59]，如DNS解析、被動流量解析、traceroute測量等方法。據統計，在國外IPv6網絡較為普及，如美國、印度等超過50%的流量為IPv6流量，而探測發現的活躍 IPv6地址僅有 5×107個[60]，僅為一小部分，因此未來如何快速探測活躍IP地址是影響IP別名解析效率的關鍵。

2) 算法指紋特征的選取

在進行別名解析算法的設計過程中，最主要的是設計別名識別的指紋特征。圖 16給出了主要別名解析算法的演化過程，這些算法大致可以分為 3類，即基于 IPID的算法、基于拓撲推斷的算法及其他算法。其中前兩類算法由于得到了多數路由器的支持而得到了廣泛的應用，而基于路由記錄、IGMP協議的算法由于多數路由器不支持甚至禁用，很難進一步研究。因此，在算法的指紋選擇時，要選擇更加具有代表性的指紋特征才能使算法在更加廣泛的范圍中應用。實際上，目前算法采用的很多指紋特征并沒有得到廣泛的支持。

Salutari等[61]通過大規模測量研究了路由器采用 IPID的情況，發現大多數路由器或主機采用常數IPID（39%）或局部計數器（34%），采用全局計數器的約占18%，無規律的約占7%和采用隨機數IPID的約占2%。在五類IPID中，只有采用全局模式的路由器才能用于定位，這一測量結果說明采用IPID進行大規模的別名解析并不具有普適性。同時，Marchetta等[62]對1 400多個AS中 32.7萬個目標進行了測量，經分析發現有32.4%的路由器支持時間戳字段。這說明目前作為 IP別名解析的主要方向的基于 IPID的方法僅能發現較小一部分的別名，而要提高 IP別名解析的準確性，則要借助于全面的指紋特征。特別是針對 IPv6協議進行深入分析，發現其在路由記錄、組播協議、時間戳等方面的特征，豐富別名判別的指紋特征集合。

3) 基于機器學習的判定方法

別名解析本質上是一個判別問題，即判定2個或者多個IP是否互為別名，其判別依據是IP的域名、TTL、拓撲位置、IPID連續性、出入度等，然而由于網絡中情況十分復雜，無法采用一種方式進行全面的分類，或者無法獲得完整的數據，必須采用多種指紋相結合的方式。在機器學習中，有很多基于多特征分類或判別的方法，或者實現復雜推理的算法，機器學習技術的引入應重點考慮以下2個方面。

① 不再借助于一個單獨的特征而是多個指紋特征，因此需要構建全面的推理過程，如算法DisCarte中采用了析取邏輯規劃[33]，用以進行復雜邏輯的推理，從而提高算法判別的全面性。

② 在算法中應當考慮不完全信息的處理，比如在拓撲分析中往往需要借助于大規模分布測量，但是現實中無法實現，如 AliasCluster算法中采用的鏈式推理邏輯，就可以避免信息不完全所帶來的別名誤判。因此，在推理中采用不確定性決策、灰色理論、貝葉斯網絡、決策樹等方法來構建完善的推理過程。

6 結束語

別名解析技術是實現網絡空間從邏輯拓撲到物理拓撲映射的關鍵步驟，同時也是網絡空間測量領域的技術難題。由于缺乏大規模的數據驗證，別名解析技術的準確性一直受到質疑。然而由于網絡空間安全戰略的需要，必須進一步提高別名解析算法的性能。別名解析不僅需要深入了解網絡協議細節、IP地址分配規律和網絡拓撲知識，還需要借助于大規模網絡測量基礎設施進行數據測量、收集及分析。特別是隨著IPv6的廣泛部署，在測量和分析上出現了許多新的問題，如在IPv6網絡空間中實現別名集合快速獲取，低開銷的快速測量、別名關系的準確推斷等。要解決這些新問題就必須采用新的方法，在算法的設計中應當采用多種特征信息，引入機器學習的方法，從而提高別名解析的準確性和完整性，為網絡空間拓撲構建、態勢感知、追蹤溯源等業務應用提供數據支撐。