搭線竊聽(tīng)下網(wǎng)絡(luò)安全路徑及安全網(wǎng)絡(luò)編碼的研究

朱聯(lián)祥，朱艷艷，曹 錚

（重慶郵電大學(xué)信號(hào)與信息處理重慶市重點(diǎn)實(shí)驗(yàn)室，重慶 400065）

0 引言

網(wǎng)絡(luò)編碼的出現(xiàn)，帶來(lái)了不可忽視的安全問(wèn)題。按照攻擊者對(duì)網(wǎng)絡(luò)安全的攻擊方式分，主要包括污染和竊聽(tīng)兩類，其中污染為主動(dòng)攻擊，搭線竊聽(tīng)為被動(dòng)攻擊。由于被動(dòng)攻擊不對(duì)消息做任何修改，因而是難以檢測(cè)到的，已有不少學(xué)者對(duì)竊聽(tīng)攻擊做了大量的研究。

Cai和Yeung［1］提出了一種基于安全網(wǎng)絡(luò)編碼的網(wǎng)絡(luò)竊聽(tīng)模型，并給出一個(gè)利用網(wǎng)絡(luò)編碼實(shí)現(xiàn)網(wǎng)絡(luò)安全的充分條件。K.Jain［2］在Cai和Yeung提出的竊聽(tīng)模型的基礎(chǔ)上，證明了只要存在一條從源節(jié)點(diǎn)到宿節(jié)點(diǎn)的路徑不被竊聽(tīng)，網(wǎng)絡(luò)就是安全的。Bhattad和Narayanan［3］首次分析了一種弱安全模型，當(dāng)竊聽(tīng)者竊聽(tīng)到的信道數(shù)小于網(wǎng)絡(luò)的最大流時(shí)，設(shè)計(jì)了一種弱安全的網(wǎng)絡(luò)編碼。Lima等［4］則考慮了竊聽(tīng)者竊聽(tīng)節(jié)點(diǎn)而不是信道這樣一種更一般的情形。

目前網(wǎng)絡(luò)編碼最主要的2種實(shí)現(xiàn)方式是線性網(wǎng)絡(luò)編碼［5］和隨機(jī)網(wǎng)絡(luò)編碼。從線性網(wǎng)絡(luò)編碼代數(shù)構(gòu)造角度構(gòu)造的安全網(wǎng)絡(luò)編碼是一種確定性編碼方案，在進(jìn)行網(wǎng)絡(luò)編碼時(shí)需要知道網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。隨機(jī)網(wǎng)絡(luò)編碼是一種分布式的編碼方案，設(shè)計(jì)者不需知道整個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)就可以進(jìn)行編碼。本文是基于給定的網(wǎng)絡(luò)拓?fù)鋱D進(jìn)行的研究，將采用線性網(wǎng)絡(luò)編碼代數(shù)構(gòu)造方法。

1 竊聽(tīng)攻擊下網(wǎng)絡(luò)的安全路徑

1.1 思想背景

搭線竊聽(tīng)，是指攻擊者以竊聽(tīng)為手段獲取網(wǎng)絡(luò)中信源到信宿某些路徑上傳送的信息。網(wǎng)絡(luò)被竊聽(tīng)時(shí)，安全的網(wǎng)絡(luò)編碼是必要的。通常，設(shè)計(jì)者假設(shè)竊聽(tīng)者知道通信雙方的編碼方案，并能根據(jù)自己的知識(shí)盡可能地選取竊聽(tīng)路徑。一般地，將這個(gè)竊聽(tīng)動(dòng)作看成是攻擊者能夠獲取一個(gè)邊集合的某個(gè)子集中的所有邊上的信息，當(dāng)這個(gè)子集中的元素最多有P個(gè)時(shí)，竊聽(tīng)者每次最多能獲取P條邊上的信息。竊聽(tīng)者一次只能竊聽(tīng)到竊聽(tīng)類集A={A1，A2，…，An}中的一個(gè)子集Ai，其中Ai?A，而設(shè)計(jì)者只知道竊聽(tīng)類集A，卻不知道究竟其中的哪個(gè)子集被竊聽(tīng)。

因此，第一種情況，當(dāng)網(wǎng)絡(luò)的全部路徑被竊聽(tīng)時(shí)，該網(wǎng)絡(luò)一定不安全，這是最嚴(yán)重的情況;第二種情況，當(dāng)一個(gè)給定的通信網(wǎng)絡(luò)遭到竊聽(tīng)攻擊時(shí)，若找不到一條安全的從源到宿（多播網(wǎng)絡(luò)時(shí)為多個(gè)宿）的路徑，則該網(wǎng)絡(luò)仍然是不安全。由此可見(jiàn)，在設(shè)計(jì)編碼方案前，首先要判斷網(wǎng)絡(luò)是否有安全路徑存在。

Kamal Jain［2］在文獻(xiàn)中針對(duì)單源單宿網(wǎng)絡(luò)提出了一個(gè)安全定理，該定理假定竊聽(tīng)者僅具有有限的計(jì)算能力。

令S?V是節(jié)點(diǎn)的集合，且s∈S，t?S，δ0（S）表示集合S到集合）的截邊集，即表示集合到 集 合S的 截 邊 集，即

定理1 對(duì)于一個(gè)竊聽(tīng)集Ai∈Α，如果對(duì)于任意的集合S（s∈S，t?S），有δ（S）?Ai，即至少存在一條邊e∈δ（S），但e?Ai，則竊聽(tīng)者獲得不了關(guān)于信源的任何有用信息。

這個(gè)定理的本質(zhì)是要求源和宿之間至少有一條安全路徑，從而通過(guò)拓展這條安全路徑來(lái)構(gòu)造安全網(wǎng)絡(luò)編碼。

文獻(xiàn)［7］結(jié)合上述的安全定理，不考慮修剪過(guò)后網(wǎng)絡(luò)圖的方向性，介紹了一種基于廣度優(yōu)先算法（breadth first search，BFS）的尋找單源單宿網(wǎng)絡(luò)中安全路徑的算法。該算法僅適用于尋找單源單宿網(wǎng)絡(luò)的安全路徑，并不適用于單源多宿網(wǎng)絡(luò)，有一定的局限性［7］。

本文中我們通過(guò)考慮網(wǎng)絡(luò)拓?fù)鋱D的有向性，并利用有向圖生成樹(shù)算法的思想，提出了一種新的算法。新的算法不僅可將竊聽(tīng)網(wǎng)絡(luò)圖中從源節(jié)點(diǎn)到宿節(jié)點(diǎn)的所有安全路徑找出，而且算法適用于單源單宿網(wǎng)絡(luò)和單源多宿網(wǎng)絡(luò)。對(duì)于單源多宿網(wǎng)絡(luò)，只要有一個(gè)宿節(jié)點(diǎn)和源節(jié)點(diǎn)間不存在一條不被竊聽(tīng)的安全路徑，網(wǎng)絡(luò)沒(méi)有達(dá)到多播的目的，該網(wǎng)絡(luò)就不是安全的。

1.2 尋找單源單宿及多宿網(wǎng)絡(luò)安全路徑的算法

定義1 除源節(jié)點(diǎn)和宿節(jié)點(diǎn)之外的一組節(jié)點(diǎn)集，它們分別既有從源節(jié)點(diǎn)到該節(jié)點(diǎn)的路徑又有從該節(jié)點(diǎn)到宿節(jié)點(diǎn)的路徑，稱這些節(jié)點(diǎn)和路徑為網(wǎng)絡(luò)拓?fù)鋱D的相關(guān)部分。除此之外的，均稱為不相關(guān)部分。

如圖 1 所示，圖 1a中節(jié)點(diǎn)a，b，c及邊 （s，a），（b，t），（s，c），（t，c）均為網(wǎng)絡(luò)不相關(guān)部分，其中a，b為懸掛節(jié)點(diǎn)，（s，a），（b，t）為懸掛邊。修剪掉這些網(wǎng)絡(luò)不相關(guān)部分，可得修剪后的網(wǎng)絡(luò)拓?fù)鋱D如圖1b所示。

圖1 網(wǎng)絡(luò)的不相關(guān)部Fig.1 Not relevant parts of the network

由于網(wǎng)絡(luò)不相關(guān)部分不傳送任何信息，它們是否被竊聽(tīng)無(wú)關(guān)緊要，所以本文研究的網(wǎng)絡(luò)拓?fù)鋱D均為修剪過(guò)的網(wǎng)絡(luò)圖。對(duì)于給定的一個(gè)通信網(wǎng)絡(luò)，刪除掉網(wǎng)絡(luò)不相關(guān)部分，把修剪過(guò)的網(wǎng)絡(luò)仍用G=（V，E）表示。

令每條邊上的權(quán)值

則單源單宿及多宿網(wǎng)絡(luò)拓?fù)鋱D中尋找從源到宿安全路徑的算法可描述如下。

1）輸入:修剪后的網(wǎng)絡(luò)拓?fù)鋱D的關(guān)聯(lián)矩陣G，源節(jié)點(diǎn)s和宿節(jié)點(diǎn)t（單宿）或t1，…，tn（多宿），以及相應(yīng)的權(quán)值矩陣F，并初始化最終安全路徑拓?fù)鋱D的鄰接矩陣W為空陣。

2）檢查源節(jié)點(diǎn)下游節(jié)點(diǎn)的安全性。若源節(jié)點(diǎn)所有鄰接路徑均被竊聽(tīng)，即權(quán)值F（（u，v））=0，則W為空陣，跳出程序;若源節(jié)點(diǎn)所有鄰接路徑不全被竊聽(tīng)，即鄰接路徑F（（u，v））不全為0，跳入3）。

3）檢查除宿節(jié)點(diǎn)之外的所有節(jié)點(diǎn)下游鄰接邊的安全性，即權(quán)值 F（（u，v）），若 F（（u，v））=1，則 W（（u，v））=1 。

4）由3）中得到的鄰接矩陣W可得新的網(wǎng)絡(luò)拓?fù)鋱D，去除此時(shí)圖中的懸掛邊。在由3）得到的鄰接矩陣W的基礎(chǔ)上，若某一W（（u，v））=1，v為u的鄰接下游節(jié)點(diǎn)，不滿足 W（s，…）=W（…，u）=W（（u，v））=W（v，…）=W（…，ti）=1（單宿時(shí)，i=1;多宿時(shí)，i∈1，…，n），則 W（s，…）=W（…，u）=W（（u，v））=W（v，…）=W（…，ti）=0 。跳出程序。

最后的鄰接矩陣W只有2種情況:第1種情況，W為空陣，說(shuō)明網(wǎng)絡(luò)不是安全的;第2種情況，從W中可以得到所有的從源到宿的安全路徑，W（s，…）=W（…，u）=W（（u，v））=W（v，…）=W（…，ti）=1（多宿時(shí)，i∈ 1，…，n）。

該算法也有一定的局限性。應(yīng)用該算法的前提是要已知竊聽(tīng)子集，若只知道竊聽(tīng)類集而不知道具體的竊聽(tīng)子集，則無(wú)法應(yīng)用該算法。

2 存在從源到宿安全路徑的單源多宿網(wǎng)絡(luò)

2.1 信息論安全與弱安全

抗搭線竊聽(tīng)的安全網(wǎng)絡(luò)編碼大體上分為2種，一種是信息論意義下的安全網(wǎng)絡(luò)編碼，一種是弱安全的安全網(wǎng)絡(luò)編碼。設(shè)X為源信息，M為竊聽(tīng)者竊聽(tīng)到的信息，若有I（X;M）=0，則竊聽(tīng)者沒(méi)有得到關(guān)于X的任何信息，稱為信息論意義的安全;若有I（X;M）≠0，I（xi;M）=0，其中xi∈X，則竊聽(tīng)者沒(méi)有得到關(guān)于X的任何有意義的信息，稱為弱安全。

弱安全的網(wǎng)絡(luò)編碼是由K Bhattad［3］提出的，例如，竊聽(tīng)者得到了關(guān)于源的2個(gè)比特的異或，他雖然得到了關(guān)于源的一個(gè)比特的信息，但卻無(wú)法得到關(guān)于源的任何“有意義”的信息。在實(shí)際應(yīng)用中這樣的安全性就足夠了，這樣的安全性是弱于信息論安全的，故稱之為“弱安全”。

當(dāng)網(wǎng)絡(luò)遇到竊聽(tīng)攻擊時(shí)，在存在從源到宿安全路徑的情況下要考慮的是此時(shí)網(wǎng)絡(luò)還是否安全。對(duì)于單源單宿網(wǎng)絡(luò)，只要找到一條通向宿節(jié)點(diǎn)不被竊聽(tīng)的路徑，網(wǎng)絡(luò)就是安全的。而對(duì)于單源多宿網(wǎng)絡(luò)，即使存在一組到各宿節(jié)點(diǎn)不被竊聽(tīng)的路徑時(shí)，網(wǎng)絡(luò)也可能是不安全的，那么竊聽(tīng)者是不能得到有關(guān)源的任何信息即信息論意義上的安全，還是不能得到有關(guān)源的任何有意義的信息即弱安全，還是完全能夠恢復(fù)出源消息。從而安全的網(wǎng)絡(luò)編碼方案起到關(guān)鍵性作用。設(shè)計(jì)者的任務(wù)是設(shè)計(jì)一個(gè)安全網(wǎng)絡(luò)編碼方案，使得網(wǎng)絡(luò)在已被攻擊者竊聽(tīng)的情況下，要么達(dá)到信息論意義下的安全，要么達(dá)到弱安全。

2.2 線性網(wǎng)絡(luò)編碼代數(shù)構(gòu)造方法

本節(jié)先介紹線性網(wǎng)絡(luò)編碼代數(shù)構(gòu)造方法的基本思想，然后以一通信實(shí)例說(shuō)明單源多宿網(wǎng)絡(luò)，即使存在一組到各宿節(jié)點(diǎn)不被竊聽(tīng)的路徑時(shí)，網(wǎng)絡(luò)也可能是不安全的［6，8］。

2.2.1 數(shù)學(xué)模型

源節(jié)點(diǎn)s上生成的μ（S）個(gè)離散隨機(jī)過(guò)程X（s，l），1≤l≤μ（S）的集合用 X（S）={X（s，1），X（s，2），…，X（s，μ（S））}表示。ν（t）個(gè)隨機(jī)過(guò)程 Z（t，l）的集合 Z（t）={Z（t，1），Z（t，2），…，Z（t，v（t））}表示宿節(jié)點(diǎn)的輸出信息。當(dāng)有n個(gè)宿節(jié)點(diǎn)時(shí)，輸出信息 Z={Z（t1，1），…，Z（t1，ν（t1）），…，Z（tn，1），…，Z（tn，ν（tn））}。

令G=（V，E）表示無(wú)延遲線性通信網(wǎng)絡(luò)，長(zhǎng)度為m的任何二進(jìn)制向量可以被認(rèn)為是域F2m（包含2m個(gè)元素的有限域）中的元素，如果G的所有邊上傳輸?shù)碾S機(jī)過(guò)程Y（e），e=〈v，v'〉∈E滿足條件

（2）式中編碼系數(shù) αe，l和 βe'，e是有限域F2m的元素，則稱G是一個(gè)F2m線性網(wǎng)絡(luò)。

任何宿節(jié)點(diǎn)t的輸出 Z（t，l），l∈ {1，2，…，v（t）}都是由隨機(jī)過(guò)程Y（e），e∈ΓI（t）構(gòu)成，定義Z（t，l）是Y（e），e∈ΓI（t）的線性組合，即

（3）式中，編碼系數(shù) εe，j是F2m的元素。

F2m無(wú)延遲線性通信網(wǎng)絡(luò)的最重要的結(jié)論是用系統(tǒng)轉(zhuǎn)移矩陣來(lái)描述輸入向量X和輸出向量Z之間的關(guān)系。用M表示輸入向量X和輸出向量Z網(wǎng)絡(luò)的系統(tǒng)轉(zhuǎn)移矩陣Z=XM。

定義2 給定網(wǎng)絡(luò)編碼數(shù)學(xué)模型，即對(duì)于一個(gè)網(wǎng)絡(luò)編碼問(wèn)題，如果存在編碼系數(shù) αe，l，βe'，e和 εe，j，并將這些編碼系數(shù) αe，l，βe'，e和 εe，j用系統(tǒng)轉(zhuǎn)移矩陣M 表示，如果能夠找到合適的編碼系數(shù) αe，l，βe'，e和εe，j使得轉(zhuǎn)移矩陣M滿秩，則這網(wǎng)絡(luò)編碼問(wèn)題是可解的，即信源節(jié)點(diǎn)可以成功譯碼，且X=ZM－1，稱一組編碼系數(shù) αe，l，βe'，e和 εe，j即為一個(gè)編碼方案。

2.2.2 通信實(shí)例

如圖 2所示，假設(shè)竊聽(tīng)類集為 {A1，A2}={{e4，e6，e7，e9}，{e6，e7，e10，e13}}。

圖2 單源多宿網(wǎng)絡(luò)拓?fù)鋱DFig.2 Single soure and multi－ sink network

設(shè)計(jì)者只知道竊聽(tīng)類集，而不知道具體的竊聽(tīng)子集。無(wú)論是竊聽(tīng)子集A1還是A2，利用2.2節(jié)中的算法，可得最終的安全路徑鄰接矩陣為

可以找到從源到2個(gè)宿節(jié)點(diǎn)的不被竊聽(tīng)的全部安全路徑。當(dāng)竊聽(tīng)子集為A1時(shí):s→1→4→t1（t2），s→3→5→t2（t1）;當(dāng)竊聽(tīng)子集為A2時(shí):s→3→5→t1，s→1→4→t2，s→1→t1，s→3→t2。

由網(wǎng)絡(luò)最大流最小割定理可知，圖2的最大傳輸容量為3。源節(jié)點(diǎn)s上的輸入過(guò)程用向量X={X（s，1），X（s，2），X（s，3）}表示，宿節(jié)點(diǎn)t的輸出過(guò)程用向量 Z={Z（t，1），Z（t，2），Z（t，3）}表示。

由Z=XM并結(jié)合（4）各式，我們可以得到

若要讓宿而且是每一個(gè)宿都能準(zhǔn)確恢復(fù)信源消息，那么在編碼時(shí)，不僅矩陣M需滿秩，而且分塊矩陣ab1c，ab2d均需滿秩，即a，b1，b2，c，d均要滿秩。則b1=1，b6=1，且b3，b4不能為0。

竊聽(tīng)子集A1={e4，e6，e7，e9}的竊聽(tīng)矩陣為P1:

要使竊聽(tīng)者得不到關(guān)于信源的信息，即不能使竊聽(tīng)者還原出源消息，則P1和P2均不能滿秩。前面已分析出a滿秩，b1=1，b6=1，b3=1，b4=1，則P1必滿秩;而在M滿秩的情況下P2能夠不滿秩。說(shuō)明當(dāng)竊聽(tīng)者竊聽(tīng)到邊集A1={e4，e6，e7，e9}時(shí)，可以還原源消息，網(wǎng)絡(luò)一定是不安全的;當(dāng)竊聽(tīng)到邊集A2={e6，e7，e10，e13}時(shí)，網(wǎng)絡(luò)的安全性是弱安全。

通過(guò)以上分析，可以得到這樣一個(gè)結(jié)論，當(dāng)存在一組數(shù)使竊聽(tīng)矩陣不滿秩而系統(tǒng)轉(zhuǎn)移滿秩，則網(wǎng)絡(luò)是安全的;當(dāng)不存在一組數(shù)使竊聽(tīng)矩陣不滿秩而系統(tǒng)轉(zhuǎn)移滿秩，則網(wǎng)絡(luò)是不安全的。線性網(wǎng)絡(luò)編碼的代數(shù)構(gòu)造方法，不需要知道確切的竊聽(tīng)子集，并且給定了在檢驗(yàn)到網(wǎng)絡(luò)安全時(shí)宿節(jié)點(diǎn)恢復(fù)出源消息的方法。

2.3 一種改進(jìn)的線性網(wǎng)絡(luò)編碼代數(shù)構(gòu)造方法

對(duì)線性網(wǎng)絡(luò)編碼代數(shù)構(gòu)造方法的運(yùn)用，是以竊聽(tīng)者知道設(shè)計(jì)者的編碼方案為前提的。在這種情況下，如果竊聽(tīng)者竊聽(tīng)到了網(wǎng)絡(luò)的全部路徑，或網(wǎng)絡(luò)中不存在從源到宿的安全路徑，網(wǎng)絡(luò)一定是不安全的。若使信源產(chǎn)生的信息為X'，X'為X的某種變換，竊聽(tīng)者不知道這種變換方式，而其他節(jié)點(diǎn)的編碼方式仍用線性網(wǎng)絡(luò)編碼的代數(shù)構(gòu)造方法，則即使竊聽(tīng)者竊聽(tīng)到全部的網(wǎng)絡(luò)路徑，根據(jù)第2.1節(jié)提到的弱安全性，I（X;M）=I（X;X'）≠0，而I（xi;X'）=0，達(dá)到了網(wǎng)絡(luò)弱安全。

改進(jìn)的源節(jié)點(diǎn)對(duì)源信息的變換方法。

1）選取一對(duì)角矩陣

2）源信息X左乘T。

3）對(duì)2）中得到的結(jié)果每個(gè)信息包中加入一個(gè)單位的冗余，得到

信宿的譯碼方法:首先運(yùn)用X'=ZM－1將源信息變換后的消息 X'譯出，可以得到t1，t2，…，tk，從而可以得到對(duì)角矩陣T，然后，信宿對(duì)去掉冗余后得到的信息左乘T－1，就可得到原始的源信息X。

3 結(jié)束語(yǔ)

長(zhǎng)久以來(lái)通信網(wǎng)絡(luò)的安全問(wèn)題一直受到人們的關(guān)注，污染攻擊和搭線竊聽(tīng)攻擊是威脅網(wǎng)絡(luò)安全的主要方式。竊聽(tīng)與污染不同，它不能夠被檢測(cè)到，抗擊這種攻擊的重點(diǎn)在于防范。防竊聽(tīng)的安全網(wǎng)絡(luò)編碼具有廣泛的發(fā)展前景。本文最后提出的改進(jìn)的線性網(wǎng)絡(luò)編碼代數(shù)構(gòu)造方法，雖然很好地解決了網(wǎng)絡(luò)在竊聽(tīng)情況下的安全問(wèn)題，但是該編碼方法在應(yīng)用于大型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)時(shí)，編碼復(fù)雜度較高，如何降低其編碼復(fù)雜度，還有待進(jìn)一步研究。

［1］CAIN，YEUNG R W.Secure network coding［C］//In IEEE International Symposium on Information Theory.Lausanne，Switzerland:IEEE Press，2002:323.

［2］JAIN K.Security based on network topology against the wiretapping attack［J］.IEEEWireless Communications，2004，11（1）:68-71.

［3］ BHATTAD K，NARAYANAN K R.Weakly secure network coding［C］//Proceedings of FirstWorkshop on Net-work Coding.Italy:IEEE，2005.

［4］ LIMA L，MEDARD M，BARROS J.Random linear network coding［C］//IEEE International Symposium on Information Theory.France:IEEE Press，2007:546-550.

［5］ LISY R，YEUNG RW，CALN.Linear network coding［J］.IEEE Transactions on lnformation Theory，2003，49（2）:371-381.

［6］ KOETTER R，MEDARD M.Beyond routing:An algebraic Approach to network coding［C］//Proceedings of Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies.Massachusetts:IEEE Press，2002:122-130.

［7］趙慧，卓新建，陸傳賚.一種基于網(wǎng)絡(luò)拓?fù)涞陌踩W(wǎng)絡(luò)編碼算法的分析［C］//中國(guó)通信學(xué)會(huì)青年工作委員會(huì)主編，通信理論與技術(shù)新發(fā)展——第十三屆全國(guó)青年通信學(xué)術(shù)會(huì)議論文集，北京:國(guó)防工業(yè)出版社，2008:844-846.

ZHAO Hui，ZHUO Jian-xin，LU Chuan-lai.Analysis of algorithms for security network coding based on network topology［C］//Youth Committee of Chinese Institute of Communications.Communication Theory and New Technology Development-the Thirteenth National Conference on Youth Communication Proceedings.Beijing:National Defense Industry Press，2008:844-846.

［8］ 趙慧.安全網(wǎng)絡(luò)編碼的研究［D］.北京:北京郵電大學(xué)，2009.

ZHAO Hui.Research on secure network conding［D］.Beijing:Beijing University of Posts and Telecommunications，2009.