小范圍BGP路由異常特征分析

文/陸岳昆 張沛 李丹丹 馬嚴

針對BGP網絡中頻發的小規模路由異常問題，本文研究小規模BGP路由異常的特征規律，并利用Spark和Hadoop的高性能存儲與計算能力，設計一套包括UPDATE采集、事件采集、UPDATE存儲、特征計算模塊的BGP異常特征分析系統。基于此系統，討論8種BGP異常特征定義以及其計算方法，分析路由劫持和路由泄露這兩類異常發生時的特征表現，進而分析各個特征對異常檢測與分類的顯著性和差異性，對于今后小范圍BGP異常的檢測與分類具有參考價值。

小范圍BGP路由異常特征分析

文/陸岳昆 張沛 李丹丹 馬嚴

BGP域間路由異常事件包括攻擊、配置錯誤、大規模電源故障。這些異常導致錯誤的或無法控制的路由行為，影響了全局路由基礎架構。最常見的兩種BGP路由異常是路由劫持和路由泄露。有統計顯示，大約20%的路由劫持和路由泄露持續不超過10分鐘，但是卻能在2分鐘內影響到90%的互聯網。

目前，已經有學者對BGP異常的特征進行了研究，并應用到了模式識別和機器學習方法上，取得了不錯的成效。但是這些研究也存在著一些的缺陷：

1.目前的BGP異常特征研究集中在描述大范圍異常特征表現，但是小規模異常特征研究較少。小規模異常相對不容易被察覺，但是其發生的頻率更高。這類小規模的異常事件，除了持續時間短之外，還有只影響某個特定IP地址前綴，受影響的IP數量較少的特點。

2.樣本之間的相關性過強。若來自同一異常事件的樣本具有較強的相關性，可能導致特征中的偶然因素被放大。

3.不同異常發生的原因是不相同的，研究過程中應該按照異常類型區別對待。路由劫持是一種攻擊方式，由某個AS非法地宣告IP地址前綴造成。而路由泄露往往是由于配置錯誤，導致路由轉發策略違反了商業關系。不同的異常類型可能在特征上有不同的表現。不同類型的異常被簡單的歸為一類是不合適的。

鑒于以上對于BGP異常特征研究的缺陷，本文著重研究了小范圍的BGP路由異常事件的特征表現。為了解決樣本相關性較強的問題，本文從BGP Stream項目中選取了上百個小規模的路由劫持和路由泄露事件作為樣本，保證了樣本之間的獨立性。這些異常事件有著確定的受影響的IP地址前綴和發生時間，通過RIPE項目的BGP UPDATE報文，可以回溯出這些異常事件的特征值。同時為了突出不同異常的特征表現，在研究過程中對特征的異常類型進行了區分。在此基礎上，考察了8個BGP異常特征，使用基于Spark和Hadoop的系統架構完成研究。最終，北京郵電大學得到了若干小范圍BGP路由異常的特征規律和結論。這些規律和結論將有助于未來小范圍BGP異常的檢測和分類。

系統架構

系統分為RIPE路由器、UPDATE采集、UPDATE存儲、BGP Stream事件源、事件采集、特征計算六個功能模塊。

RIPE 路由器：RIPE（Regional Internet Registry for Europe）是歐洲、中東和中亞部分地區互聯網注冊機構，負責為服務提供商分配和注冊互聯網號碼資源。RIPE組織使用Quagga路由軟件收集了BGP路由器的原始數據，包括全量的路由表BVIEW數據（每八個小時更新一次）和差量的UPDATE數據（每五分鐘更新一次）。

UPDATE采集模塊：本模塊負責下載RIPE項目22個rrc（Route Reflector Client）的UPDATE數據。原始的UPDATE數據是以二進制的形式存儲的，本模塊使用RIPE提供的解析工具libBGPdump，把報文解析成可閱讀的形式。模塊將解析后的文件存入Hadoop。

UPDATE存儲模塊：Hadoop是一個軟件框架，它的作用是方便使用簡單的程序在大量的計算機上對數據集進行分布式處理。本文分析了RIPE項目一個月的UPDATE數據，數據文件大小為417.6GB。由于要從較大規模數據中發現BGP異常特征規律，所以需要一個可靠的、高效的數據存儲模塊。

BGP Stream異常事件源：BGP Stream收集了BGP網絡中有關路由劫持和路由泄露的免費資源。BGP Stream使用自動化方法選擇最大和最重要的異常。提供異常信息包括異常類型，涉及的IP地址前綴、AS號、發生時間等。

事件采集模塊：本模塊使用Python實現了爬取BGP Stream收集的異常事件，一起異常事件可以用三元組的方式描述：[prefix,time,type]。prefix表示受影響的IP地址前綴，time表示異常的發生時間，type表示異常類型。

圖1 系統架構

Spark特征計算模塊：Spark是一個基于MapReduce的快速的通用的大規模數據處理引擎。Spark建立在統一抽象的RDD之上。RDD是一個容錯的、并行的數據結構。RDD提供了map、filter、reduceByKey等數據操作方式。本模塊從Hadoop中讀取BGP UPDATE報文，結合從事件采集模塊收集的異常事件，分析若干異常特征。本研究將時間區間劃定為一天，分析器將統計異常發生當天的特征數據。系統架構如圖1所示。

特征選擇和計算方法

當一個BGP路由器發生異常時，其余的BGP路由器會為失敗的路由重新進行路由選擇算法。在路由重新選擇的過程中，BGP路由器會發布路由宣告和撤回消息。這些更新信息可以幫助我們發現BGP異常的特征規律。下文將討論以下特征以及其計算方法。

宣告/撤回數量

在過去大規模的BGP路由異常事件中，通常路由的不穩定性會表現在UPDATE報文中的宣告和撤回數量上。所以本研究將宣告和撤回數量作為一個BGP異常事件特征。宣告和撤回數量特征計算公式如下：

AVi和WVi表示事件集合中編號為i的事件宣告/撤回數量。RIPE項目22個rrc每五分鐘對外發布一次UPDATE報文文件，每個rrc每天生成288個報文文件。Xij和Yij代表著一個報文文件中的宣告/撤回數量序列。ENUM表示事件集合中的事件數量。

重復宣告/隱式撤回

宣告的類型可以分為三種。如果一條宣告聲明了一個原來不可達的IP地址前綴，那么這條宣告被稱作新的宣告。如果一條宣告聲明了一個可到達的IP地址前綴，并且具有相同的路由，即UPDATE中PREFIX域和ASPATH域相同，那么這條宣告被稱作重復宣告。如果一條路由替換了當前的路由，即PREFIX域和AS-PATH的源相同，但是AS-PATH發生了變化，那么這條宣告被稱為隱式撤回。當BGP路由異常發生時，路由處于不穩定的狀態，有時會伴隨重復宣告和隱式撤回。重復宣告計算公式如下：

DAVi表示事件i的重復宣告數量，PATHi是事件i所有UPADTE中所有ASPATH。上式證明了重復宣告數量等于宣告數量與路徑集合大小的差。

隱式撤回IWVi的計算，需要基于路由表的狀態，可以根據BGP UPDATE來維護路由表狀態。隱式撤回的計算方法如下：

步驟1 收集PREFIX域為prefix(i)，TIME域為time(i)的宣告UPDATE。

步驟2 將UPDATE按照（前綴，采集點，源）為鍵值，(時間,路徑)為值分組。

步驟3 分組后，對于每一個分組，都產生一個(時間,路徑)的序列。對每個序列應用如下算法：

步驟3.1 對元組序列按照時間升序排序。

步驟3.2 pre_path用于記錄分組路由，implicate_num用于記錄分組隱式撤回數量。算法1具體闡述求一個分組隱式撤回數量方法,如下所示。RETURN implicate_num

步驟4 將所有分組隱式撤回數相加，得到IWVi。

AS源數量

AS源數量是一個判定BGP路由異常的重要指標。多源自治域系統沖突發生當一個特定的IP地址前綴被超過一個AS自治域宣告為源。IP地址前綴的源可以從UPDATE的AS-PATH域獲得，AS-PATH從左往右的最后一個節點為前綴的源。AS源數量指標是計算時間窗口內，事件前綴不重復的源個數。AS源數量計算公式如下：

MUASi為事件i的AS源數量，pathi(-1)表示事件iUPDATE中AS-PATH域路徑從左往右第一個AS的集合。

宣告類型

UPDATE宣告中的ORIGIN是一個必須存在的字段，它定義了AS-PATH路徑起源的信息。ORIGIN的值有以下三種：

IGP：網絡層可達性信息來自ORGIN AS內部。

EGP：網絡層可達性信息獲得通過EGP協議。

INCOMPLETE：網絡層可達性信息獲得來自其他渠道。

不同的值在BGP路由選擇算法中有不同的權重，如果AS-PATH相同，優先選擇低等級的ORIGIN類型，優先等級IGP＜EGP＜INCOMPLETE。不同的異常發生可能在宣告的類型上也有區分。宣告類型特征計算公式如下：

ATij為事件宣告類型為j的特征值，ATij的含義是j類型宣告的比例。

路徑長度

當BGP重新選擇路由時，路徑長度有很大概率會發生改變。尤其當發生路由劫持或者路由泄露時，路徑長度的變化會更加明顯。路由劫持發生時，原有的路由線路不再可用，BGP路由器會嘗試新的替代線路。路由泄露發生時，雖然IP地址前綴所屬的AS沒有發生變化，但是由于路徑中間AS的轉發策略配置不當，違反了Valley-free的商業關系，往往會導致路徑長度變得更長。路徑長度特征計算公式如下：

PLij表示標號為i的異常事件，路徑長度為j的數量。同樣Xij表示一組報文數量的序列。MPL表示最大路徑長度。

路徑編輯距離

當BGP路由異常發生時，路由處于不穩定的狀態，采集點會檢測到大量來自同一AS源但路徑卻不相同的宣告。編輯距離是一種反應兩條路徑差異程度的量化特征指標，量化方法是一條路徑經過至少多少次操作可以變成另一條路徑。操作方式包括添加一個AS節點、刪除一個AS節點，替換一個AS節點。例如路徑[1,3,2,5,4]和路徑[1,3,6,4]的編輯距離為2，前者通過將2替換成6，刪除5，兩次操作可以得到后者。兩條路徑的編輯距離求解有基于動態規劃的多項式時間復雜度求解算法，狀態轉移方程如下：

d(i,j)表示長度為i的一條路徑（記為p1）與長度為j的一條路徑（記為p2）的編輯距離。如果P1(i)=P2(j)，則不需要任何操作，狀態轉移到(i-1,j-1)。

基于路徑編輯距離求解算法，我們定義最大路徑編輯距離特征如下：

PDLi表示編號為i的事件的最大編輯距離。對于同一IP地址前綴，采集點編號為j，宣告源編號為k。按照(i,j,k)對宣告進行分組，D表示組內最大編輯距離。p,q表示組內兩條宣告路徑，d表示兩條路徑的編輯距離。

特征采集結果分析

圖2 宣告數量。橫軸表示宣告數量的對數值，縱軸表示對應概率分布函數值F

本研究基于系統結構設計，對提出的小范圍BGP異常特征，按照所述定義與計算方法進行了實際采集與分析。其中UPDATE更新報文來自RIPE項目中采集，數據規模包括其全部22個rrc數據。本研究異常事件數據來自BGP Stream，一共考察了259起路由劫持事件和523起路由泄露事件。未被BGP Stream通報的IP地址前綴，其相關UPDATE被視為正常。本研究隨機抽樣了1000起正常事件，用于參照。正常事件同樣用三元組（prefix，time，type）表示。大部分小范圍BGP異常發生事件不超過一天，同時要考慮到BGP Stream通報異常發生時間和相關UPDATE收集時間，為了保證相關指標能夠被有效采集到，本研究選用24小時作為事件的采樣時隙。

圖2比較了路由泄露、路由劫持和正常情況下宣告數量。

圖2結果表明整體宣告數量上正常情況＜路由劫持＜路由泄露。正常情況下前綴的宣告數量集中在數量級以內（75.82%）。路由劫持事件發生時，有一定比例（47.32%）宣告數量在數量級以上。路由泄露事件發生時，前綴的宣告數量集中在至（80.15%）。圖2三條曲線形態有較大差異，表明當小范圍BGP異常發生時，宣告數量與正常情況有較大區別，同時路由泄露和路由劫持在宣告數量這個特征上有較高區分度。

圖3 撤回數量。橫軸表示撤回數量的對數值，縱軸表示對應概率分布函數值F

圖4 重復宣告。橫軸表示重復數量的比例，縱軸表示對應概率分布函數值F

圖5 隱式撤回。橫軸表示隱式撤回數量的比例，縱軸表示對應概率分布函數值 F

圖3比較了路由泄露、路由劫持和正常情況下撤回數量特征值。從圖3可以看出，正常情況下，一個前綴不會在短時間內出現大量的撤回，87.19%前綴撤回數量小于101。當路由發生時，撤回的數量這一比例開始下降，只有38.83%的被劫持前綴撤回數量小于101。路由泄露在撤回數量這一特征上與前兩者有著更明顯的差別，特征值集中在105的數量級上。

圖4比較了路由泄露、路由劫持和正常情況下重復宣告比例。從圖4可以看出無論是路由劫持還是路由泄露發生時，在重復宣告數量這一特征上不會產生明顯變化。

圖5比較了路由泄露、路由劫持和正常情況下隱式撤回比例。

當BGP路由異常發生時，隱式撤回的比例要小于正常情況。這表明異常會伴隨著連續的重復宣告。根據前文關于重復宣告和隱式撤回的定義，兩者的區別在于重復宣告沒有對UPDATE按照時間排序，而隱式撤回考慮到了UPDATE的到達先后順序。比較圖4和圖5正常情況下的曲線，兩條曲線是相似的。這說明正常情況下，相同的宣告產生與時間這一因素無關的。而異常情況下宣告方式與時間因素相關，可以分為兩個階段：第一個階段產生大量宣告，這些宣告大多互不相同；第二個階段開始連續產生相同的宣告。

表1 AS源數量

表2 宣告類型

圖6 路徑長度

圖7 最大路徑長度

表1比較了路由泄露、路由劫持和正常情況下AS源數量。對于正常情況和路由泄露，幾乎所有前綴只會有一個AS源。但是四成的被劫持前綴被觀測到在短時間內出現多個AS自治域相互“爭奪”一個IP地址前綴的現象。在AS源數量這一特征上，路由劫持異常具有顯著性。

表2比較了路由泄露、路由劫持和正常情況下宣告類型比例。研究中沒有發現帶有EGP標識的UPDATE。同時與正常情況相比，當小范圍的BGP路由異常發生時，宣告類型的比例沒有發生明顯變化。

圖6比較了路由泄露、路由劫持和正常情況下路徑長度。圖6橫軸表示路徑長度，縱軸表示數量以10為底的數量級。可以看出，三種情況下UPDATE路徑長度均集中在5附近（正常情況路徑平均長度5.24，路由劫持4.64，路由泄露6.71）,稍有不同的是數量上正常情況＜路由劫持＜路由泄露。但是根據圖7顯示的結果，路由泄露發生時的最大路徑長度顯著大于正常情況和路由劫持。綜上所述，雖然三種情況下整體路徑長度分布相似，但是路由泄露異常更容易產生不合理的超長的路徑。

圖8路由泄露、路由劫持和正常情況下路徑編輯距離。結果顯示編輯距離特征和最長路徑長度相似，與正常情況相比，路由劫持特征不顯著，路由泄露的編輯距離要大于前兩者。

圖8 編輯距離。橫軸表示編輯距離，縱軸表示對應概率分布函數值F

過濾式異常特征分析

北京郵電大學分別采集了BGP路由泄露、路由劫持、正常三類樣本，數量一共1782起，特征維度一共個58維度，形成了一個的特征矩陣。BGP異常分析受特征之間的相關性和冗余所影響，同時采集的特征維度過多浪費了計算資源。Fisher算法和mRMR是兩種常用的過濾式算法，用于解決特征相關性和冗余的過濾式方法。

1. Fisher過濾法

Fisher方法的關鍵思路是從特征中找出一些特征，滿足這些特征在樣本數據中，不同類別的數據點之間的距離盡可能大，而同一類的數據間的分數盡可能小。同一類別的數據的距離用類別方差和來描述，方差和越小說明對于該特征類別內數據越一致。不同類距離用特征均方和描述，均方和越大說明類別間區分度越好。Fisher分數實際就是前者與后者的比值。特征向量F={X1,X2…X58}，對于第r個特征，其Fisher分數公式如下：

其中c代表3種樣本類型，nk代表第k類樣本數量，μ代表對于特征r第k類的平均值，μr代表特征r整體平均值，σ 代表征r第k類標注差。

2. mRMR

mRMR方法的關鍵思想是最大化特征相對于目標類的相關性，同時最小化特征之間的冗余。mRMR方法基于互信息公式，對于兩個特征Χk和Χl，其概率密度及聯合概率密度為 p(Χk)、p(Χl) 和 p(Χk,Χl)。互信息的計算公式如下：

一般使用兩種變體mRMR算法：相互信息差異（MID），互信息（MIQ）。MID和

表3 特征過濾

MIQ評分公式如下：

V(I)和W(I)分別為：

Fisher方法和mRMR方法分別計算分數，表3列出了前15名特征。從表中數據可以看出宣告/撤回數量、重復宣告/隱式撤回、AS源數量、路徑長度均對異常分類具有幫助，宣告類型則沒有幫助。路徑長度的維度雖然有50維，然而對分類有幫助的的維度主要集中在長度小于20的維度。

基于本文討論的小規模BGP網絡異常特征的定義、采集方法和特征與異常類型的關聯分析，未來的工作重點將是如何進行小范圍BGP網絡異常檢測。

傳統的BGP網絡異常檢測單模型的檢測方法，例如De Urbina等人使用SVM方法進行BGP路由異常檢測。Huang提出了基于PCA的檢測算法。Deshpande提出了基于最大似然估計的檢測算法。

單模型方法的缺陷在于很難在檢測效率和準確度兩者之間做出適當的平衡。本研究計劃在未來采用雙模型組合的異常檢測策略，將本文采集的特征數據濾篩選后通過GBDT方法離線處理生成新的組合特征，然后使用LR邏輯回歸的方法進行分類。如何將本研究結果運用到具體的異常檢測算法中，將是今后的研究重點。

（責編：陶春）

為北京郵電大學網絡技術研究院）