杨婧婧 桂畅旎 刘 晴 杜 荣

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