基于路由選擇的防搭線竊聽安全網絡編碼

楊婧婧 桂暢旎 劉 晴 杜 榮

1(中國信息安全測評中心 北京 100085)2(上海交通大學信息安全學院 上海 200240)

基于路由選擇的防搭線竊聽安全網絡編碼

楊婧婧1桂暢旎1劉 晴1杜 榮2

1(中國信息安全測評中心 北京 100085)2(上海交通大學信息安全學院 上海 200240)

相對于傳統的以路由為基礎的網絡理論，網絡編碼技術有著許多特點和優勢。與此同時，它也遭受著各種各樣的網絡攻擊，其中搭線竊聽攻擊就是最典型的攻擊之一。提出一種基于路由選擇的防搭線竊聽安全網絡編碼方法，在已知被竊聽鏈路位置(不可信鏈路位置)的情況下，對被竊聽鏈路的傳送消息進行分析。在保證網絡最大流不變的前提下，盡量移除較少被竊聽鏈路或者正常鏈路，以保證竊聽者無法得到完整的網絡源信息，而信宿節點能夠正常地接收到所有的信息。根據得到的安全網絡拓撲構造新的系統傳輸矩陣，從而獲得安全網絡編碼，達到抵御搭線竊聽攻擊的目的。仿真實驗證實提出的方法能夠有效地抵御搭線竊聽攻擊。

搭線竊聽攻擊 網絡編碼 網絡拓撲 路由選擇

0 引 言

2000年 Ahlswede等人[1]首次提出了網絡編碼理論, 并且指出與傳統的以路由為基礎的網絡理論相比, 網絡編碼有著許多獨有的特點和優勢。自此網絡編碼便成為了網絡通信傳輸領域的熱點方向之一。隨后，在2003年，Li等[2]證明了線性網絡編碼就可以實現網絡的最大流。2006年,T.Ho[3]等人也提出了隨機網絡編碼理論，網絡編碼理論不斷走向完善。

網絡編碼實際上是一種在信息論基礎上融合了路由和編碼的信息交換方法，網絡編碼的重大意義在于它打破了獨立比特不能再被壓縮的經典理論，告訴人們網絡信息流是可以被壓縮的，網絡中間節點是可以被利用來獲取帶寬的。因此，網絡編碼的本質是利用中間節點的緩存資源和計算資源換取這個網絡的帶寬資源利用率。網絡編碼在提高網絡吞吐量、減少節點能量消耗、提高容錯性和魯棒性、提高網絡糾錯能力等方面也都有著明顯的優勢。

然而，隨著網絡編碼的發展以及應用，網絡編碼傳輸中的安全問題也隨之突顯出來。

現今網絡編碼安全的研究重點主要針對網絡層網絡編碼攻擊行為，根據攻擊方式的不同，網絡層網絡編碼攻擊主要劃分為兩大類：搭線竊聽攻擊和污染攻擊，也就是通常所說的被動攻擊與主動攻擊。本文主要研究的對象就是搭線竊聽攻擊。

1 網絡編碼基本概念

1.1 網絡編碼概述

網絡編碼的目的在于提高網絡傳輸能力，使網絡傳輸能力能夠達到容量上限，蝶形網是研究網絡編碼的經典網絡類型。下面，將對蝶形網進行介紹。

圖1是一個蝶形網的例子。傳統的通信網絡中，中間節點只能進行復制轉發，如圖1(a)所示，當源節點s需要同時傳送b1和b2到信宿節點Y和Z，數據傳輸到中間節點X時必須經過2個單位時間才能夠將2比特數據流b1和b2多播到信宿節點Y和Z。假設網絡中每條鏈路的容量都是單位容量，圖1(a)的最大流為2，而實際應用中的網絡流量僅為1。

在利用網絡編碼后，中間節點可以進行編碼和代數運算等。如圖1(b)，要把信源s發出的2比特數據流b1和b2多播到信宿節點Y和Z，可采取如下解決方案：讓鏈路ST、TW、TY攜帶比特流b1，鏈路SU、UW、UZ攜帶比特流b2，而鏈路WX、XY、XZ對數據流b1和b2進行簡單的編碼，最終攜帶比特流b1+b2(b1和b2的模二加)，而信宿節點Y和Z可以通過(b1,b1+b2)和(b2,b1+b2)解碼得到信源s發出的數據流b1和b2，達到同時多播到節點Y和Z的傳播目的，傳輸速率能達到多播速率2比特每單位時間，達到了這個網絡的最大流理論上限。

圖1 蝶形網工作原理

1.2 系統模型

1.3 攻擊模型及安全目標

本文提出的網絡編碼安全方法從路由選擇角度出發，假設網絡中有一系列的位置已知的中間節點被竊聽，或者，可以認為網絡中存在一系列的不可信節點，竊聽者能夠竊聽到的節點M=[M1,M2,…,Mn]，不包括信源節點和信宿節點，M∈V，n代表竊聽者能竊聽到的節點個數。竊聽者通過解碼這些節點的信息然后以求獲得信源節點發出的所有信息。

安全目標：本文考慮的是基于路由選擇的安全網絡編碼，選用普通的線性確定性網絡編碼，構造時不經過任何加密處理。在此，防竊聽的目的是保證竊聽者無法得到所有信息的情況下，允許竊聽者獲得一部分的有用信息，亦即安全模型是弱安全模型。

2 防搭線竊聽安全網絡編碼策略

2.1 設計動機與基本思想

現有的防搭線竊聽網絡方法通常是從編碼的角度出發，通過構造高復雜度的安全編碼滿足不同的安全需要[4-8]。構造安全網絡編碼過程通常先確定網絡拓撲結構然后再進行編碼傳輸，由此可見，拓撲對安全網絡編碼構造也是有重要影響的。網絡現有的安全研究也有從網絡拓撲角度出發，文獻[9]提出一種通過網絡拓撲構造抵御搭線竊聽攻擊的單播安全隨機網絡編碼，文獻[10]也提出基于路由選擇的線性網絡編碼的多數據流弱安全單播最優方法等。然而該方面的研究起步相對較晚，研究成果相對較少，且主要針對單個被竊聽節點的單播安全問題。有鑒于此，本文從網絡拓撲角度出發，考慮單播/多播以及多個被竊聽節點情形，對安全網絡編碼展開進一步深入研究。

為了說明網絡傳輸拓撲對網絡安全的影響，我們以圖2為例。

圖2 網絡最大流為3的單播線性網絡編碼示例

圖3是一個多播確定性網絡編碼的例子。圖3(a)中，網絡有一個信源節點s和兩個信宿節點d1和d2，其中CG(s,d1)=CG(s,d2)=3。假設搭線竊聽攻擊者能夠同時竊聽到節點2、6、7。

圖3 網絡最大流為3的確定性多播網絡編碼示例

仔細觀察上面2個例子，可以發現一些現象。

在圖3中，被竊聽節點2、6、7不能有2個或2個以上的節點同時被移除出網絡，為了達到弱安全，在刪除了被竊聽節點2的情況下，還要對被竊聽節點的4條入邊也進行了刪減，使入邊總數小于網絡最大流，保證網絡達到弱安全。

2.2 方法步驟

基于上述設計思路和系統模型、攻擊模型以及安全模型，并令網絡中需要傳輸信息X=[X1,X2,…,Xl]，總共l個字符，可以給出方法如下：

第一步 對于給定的多播有向無環網絡G=(V,E)，利用Ford-Fulkerson算法(Ford-Fulkerson算法是目前計算網絡最大流的通用算法，本文后續對網絡最大流的計算也都是采用該算法)計算出網絡的最大流CG(s,d)=k，此時根據k與l的數值分2種情況討論：

當k≤l時：網絡最多只能達到k的容量上限，單位時間內只能傳輸k個字符，多出的字符只能等待下個單位時間進行傳送。然后在給定的網絡圖中需找k條不相關的路由，如果存在，則繼續執行第二步，如果不存在，則需隨機找k-1,k-2,…條不相關路由和1,2,…條相關路由，直到找到最多不相關路由為止。

當k>l時：網絡只需要找l條不相關的路由即可，如果存在，則繼續執行第二步，如果不存在，則需隨機找l-1,l-2,…條不相關路由和1,2,…條相關路由，直到找到最多的不相關路由為止。

第二步 定義傳輸矩陣Q為一個(m+1)×(m+1)的矩陣，m為中間節點的個數。在經過第一步的路由尋找后，Qi,j代表從節點i傳送到節點j的消息。傳輸矩陣最后一行代表從源節點發出的所有信息，最后一列則代表目標節點接收到的信息。對矩陣Q的值填充分為3種情況：

Qi,j=(x,y,…)n=anx+bny+…：經過路由尋找后，節點i到節點j的鏈路是存在于網絡并且傳輸信號，稱之為被激活的，Qi,j的值為該鏈路上傳輸的關于信源發出的信息。

Qi,j=1：節點i到節點j的鏈路是存在于網絡但是并沒有傳輸信號，稱之為未被激活，Qi,j的值用1來表示，例如圖3、圖4中虛線所示。

Qi,j=0：節點i到節點j的鏈路是不存在的，對于該類Qi,j的值用0來表示。

第三步 生成網絡的傳輸矩陣Q，對被竊聽的(不可信的)節點或者鏈路在傳輸矩陣中進行分析，找出所有能夠保證被竊聽鏈路集合無法獲得完整的傳輸信息而目標節點可以得到所有源節點發出的信息的安全路由方法。

第四步 重新構造傳輸矩陣Q，其中元素是通過經過路由選擇后的拓撲結構生成的，對所有求解出的安全路由進行比較，其中占用鏈路資源最少的路由便是最優解。

第五步 根據得到的安全路由最優解，重構網絡系統鄰接矩陣F′，其矩陣元素如式(1)所示：

(1)

M′=A(I-F′)-1BT

(2)

最后通過新的系統轉移矩陣重新編碼傳輸。

圖4是一個多播容量為3的多播網絡，在圖4中，有1個信源節點s和2個信宿節點d1、d2。CG(s,d1)=CG(s,d2)=3，即多播容量最大流為3。

圖4 容量為3的多播網絡圖

假設被竊聽節點為節點2、6、7。對方法進行逐步分析：

由于多播的網絡容量為3，因此可以先找出3條不相交的路由。對于多播網絡，可以將信源節點到不同的信宿節點分開進行。對于G(s,d1)，3條不相交路由分別為{s→1→6→d1}{s→4→8→d1}、{s→5→2→3→d1}。對于G(s,d2)，3條不相交的路由為{s→4→2→3→d2}{s→1→7→d2}、{s→5→9→d2}。由于是多播網絡，所以不同的子網絡間路由相交通常是不可避免的。

接著就可以構建傳輸矩陣Q。

1) 單獨刪除鏈路{4→2}或者{5→2}，竊聽者將無法得到信息x或z。

2) 將兩條鏈路{6→1,7→1}全部刪除則竊聽者無法獲得信息y。

方案1 刪除節點2，那么傳輸矩陣Q中第二行與第二列的值將全變成0和1，節點2只有節點3一個下游節點，從第三行可以看出，節點3只有節點2一個上游節點，下游則有2個目標節點，這3個點的值全置為1，此時的傳輸矩陣Q變為：

觀察此時的傳輸矩陣，由于節點2已經被移除了網絡拓撲結構，而2個目標節點無法獲得足夠的信息，所以必須激活節點3使目標節點獲得足夠的信息。從傳輸矩陣第三列可以看到，節點3上游除去節點2一共有5個未被激活的鏈路，分別包括節點4、5、6、7到節點3的鏈路。由于節點6、7是被竊聽了的節點，排除出考慮范圍，鏈路{4→3}和{5→3}被激活。節點4、5有共同的上游節點1，鏈路{1→4}和{1→5}被激活。此時，網絡圖變為如圖5所示。

圖5 方案1下的安全網絡拓撲圖

方案2 刪除節點6和節點7，使用同樣的方法，最終得到的安全網絡拓撲圖如圖6所示。

圖6 方案2下的安全網絡拓撲圖

對比2個方案，方案1總共使用鏈路17條，而方案2使用鏈路18條，一般情況下選取占用鏈路較少的方案為最優解。

最后，通過所得到的安全網絡拓撲圖得到新的系統轉移矩陣，根據新的系統轉移矩陣進行編碼，得到了多播安全網絡編碼。

3 實驗結果

本文實驗使用NS-2仿真平臺以及Matlab軟件來驗證上述提出方法的性能。本文使用的是未經過加密的確定性網絡編碼，討論被竊聽節點數量以及多播目標節點數量對傳輸成功率的影響。

在仿真過程中，定義4個性能參數。網絡中的中間節點數量m,竊聽者能夠竊聽到的節點數量占總中間節點數的百分比p，多播環境下目標節點數量n以及成功傳輸率r。其中多播傳輸率為：min(CG(s,dn)，且max(CG(s,dn))-min(CG(s,dn))≤1以盡量保證仿真結果的真實性。根據不同的參數變化一共進行2組仿真，其中網絡中的節點都是隨機產生的，信源節點和目標節點在生成了中間節點后加入網絡拓撲圖。

在圖7中，設m=[20,50],p=0.2，n的值在[1,6]間變化。

圖7 不同m值時rvs.n

在圖8中，設m=40,p=[0.2-0.5]，n的值在[1,6]間變化。

圖8 不同p值時rv s.n

我們將分別從安全性以及網絡參數對網絡成功傳輸的影響兩個方面對基于路由選擇的安全網絡編碼方法的性能進行分析。

1) 安全性

本文提出的多播安全網絡編碼方法，在拓撲構造過程中，對所有被竊聽節點得到的信息進行分析，保證被竊聽節點得到的關于源信息的多項式數量小于傳輸的信息個數，或者得到的多項式中缺失了某些傳輸的信息。由于被竊聽節點無法獲得足夠的多項式，或者能夠得到足夠的多項式，但多項式中缺失了部分源信息，使得竊聽者無法完整還原源節點發出的所有信息，從而保證了傳輸的弱安全性。如果網絡拓撲中無法找到安全的傳播路由，那么方法將顯示傳輸失敗。

2) 網絡參數對網絡成功率的影響

網絡節點數量不變的情況下，被竊聽節點數量增加使得網絡中正常節點數量將減少，安全路由拓撲可用鏈路數量的減少將導致傳輸成功率的下降。

被竊聽節點數量占中間節點數百分比不變的情況下，網絡的增大(節點數量增加)會使網絡中正常節點的數量增加，以及使安全路由拓撲可用鏈路數量增加，如此將會使傳輸的成功率上升。

網絡大小，被竊聽節點數量不變時，多播安全網絡編碼方法可以看成是多個單播安全網絡編碼方法的集合，多播目標節點數量的增加意味著要同時滿足的單播數量增加，必然將導致傳輸成功率的下降。

從圖7的仿真中可以看出，當網絡中被竊聽節點數量與所有中間節點比值一定p=0.2時，網絡的大小程度能在一定程度上影響網絡傳輸的成功率。網絡越大，傳輸成功率越高，但相對而言整體上影響不大。原因在于當網絡節點變得更加密集后，網絡中正常節點的數量增加使得網絡傳輸可用正常鏈路變得更多，成功率也隨之升高。從圖8的仿真中可以看出，當網絡規模一定時，被竊聽節點數量的增加會嚴重影響網絡傳輸的成功率，當被竊聽節點數量與所有中間節點比值超過0.2時，網絡很難保證傳輸的成功率。在被竊聽鏈路數量與所有中間節點比值小于0.2時，被竊聽節點數相對于中間節點數目較少時，方法能夠很好地滿足安全傳輸的要求。從兩個圖中，能夠清晰看到，隨著目標節點數量的增加，網絡傳輸成功率也是呈下降趨勢的。

我們提取出所有能夠成功找到安全拓撲的網絡圖，竊聽節點都無法從這些網絡中獲取完整的源信息，在能找到安全拓撲的情況下，網絡都能保證弱安全。

4 結 語

本文針對被忽視的安全網絡拓撲結構構造問題進行了深入的研究，給出了一種被竊聽節點位置已知的基于路由選擇的單播安全網絡編碼方法，方法滿足了網絡的弱安全需求。并將該方法擴展到多播情形中，分析了方法的計算復雜度，安全性以及網絡環境中多播目標節點數量、被竊聽鏈路數量、網絡大小等因素對方法成功率的影響。今后的工作是要致力于研究進一步提高方法的成功率。

[1]AhlswedeR,CaiN,SYRLi,etal.Networkinformationflow[J].IEEETrans.Inf.Theory,2000,46(4):1204-1216.

[2]LiYR,YeungRW,CaiN.LinearNetworkCoding[J].IEEETransonInfTheory,2003,49(2):371-381.

[3]HoT,MedardM,KoetterR,etal.Arandomlinearnetworkcodingapproachtomuhicast[J].IEEETransonInformationTheory,2006,52(10):4413-4430.

[4]ZhangJ,ShaoJ,LingY,etal.Efficientmultiplesourcesnetworkcodingsignatureinthestandardmodel[C]//ConcurrencyCompute:Pract.Exper.2014.

[5]PfennigS,FranzE.Securenetworkcoding:Dependencyofefficiencyonnetworktopology[C]//2013IEEEInternationalConferenceonICC,2013:2100-2105.

[6]GlisicSG.AdvancedRoutingandNetworkCoding,FutureEvolvingTechnologies[C]//ThirdEdition,JohnWiley&Sons,Ltd,Chichester,UK.2011.

[7]QiliangLiang,WeiWang,JMu,etal.LightweightSecurityforWSNBasedonNetworkCoding,Communications,SignalProcessing,andSystems[M].LectureNotesinElectricalEngineeringVolume202,2012:115-123.

[8]KurosawaK,OhtaH,KakutaK.HowtoConstructStronglySecureNetworkCodingScheme[C]//InformationTheoreticSecurityLectureNotesinComputerScience2014:1-17.

[9]LijuanGeng,FengLu,YingchangLiang,etal.SecureMulti-PathConstructioninWirelessSensorNetworksusingNetworkCoding[C]//Personal,IndoorandMobileRadioCommunications,2008.IEEE19thInternationalSymposiumon,2008:1-5.

[10]WangJ,WangJP,LuK,etal.OptimalDesignofLinearNetworkCodingforInformationTheoreticallySecureUnicast[C]//Proceedingsofthe30thIEEEInternationalConferenceonComputerCommunications,IEEEINFOCOM,ShangHai,China,2011.

SECURE NETWORK CODING SCHEME AGAINST WIRETAPPING ATTACKBASED ON ROUTE SELECTION

Yang Jingjing1Gui Changni1Liu Qing1Du Rong2

1(ChinaInformationTechnologySecurityEvaluationCenter,Beijing100085,China)2(SchoolofInformationSecurity,ShanghaiJiaotongUniversity,Shanghai200240,China)

Compared with the traditional network theory based on route, network coding technology has lots of characteristics and advantages. At the same time, it also suffers from a variety of network attacks, including the most typical one called wiretapping attack. This paper proposes a secure network coding scheme against wiretapping attack based on route selection. In the case that eavesdropped link position (unreliable link position) is known, we analyse the messages transmitted by eavesdropped links. Under the premise of ensuring the maximum network flow, we try to remove less eavesdropped links or normal links to ensure that the eavesdropper cannot get complete network source information while the destination node can normally receive all the information. According to the obtained topological structure of secure network, we construct new system transfer matrix and get the secure network code, so as to achieve the purpose of resisting wiretapping attack. Simulation results show that the proposed scheme can effectively resist wiretapping attack.

Wiretapping attack Network coding Network topology Route selection

2016-01-22。中國信息安全測評中心項目(cnitsec-ky-2014-001/1)。楊婧婧，研究實習員，主研領域：開源信息分析。桂暢旎，研究實習員。劉晴，助理研究員。杜榮，博士。

TP393

A

10.3969/j.issn.1000-386x.2017.03.054