网络编码的安全性综述

Survey on Security of Network Coding

摘要: 本文是针对网络编码的安全性问题的综述性文章，首先对现有的针对网络编码系统的恶意攻击进行了细致的定义和分类，总结了各类恶意攻击之间的联系和区别，说明了它们的基本防御思想；其次针对各类恶意攻击，阐述了一些经典的网络编码防御方案，并分析其优缺点；最后对现有的网络编码防御方案进行了总结并提出了改进思路。

Abstract: In this paper, we mainly summarize secure problems of network coding. Firstly, existing malicious attacks are discussed in detailed definition and classification, and then we describe the relationship and difference among them and point out the basic defense thought of all kinds of malicious attacks. Secondly, aiming at all kinds of malicious attacks, we introduce some classic network coding defense schemes and analyze their advantages and disadvantages. Finally, we summarize existing network coding defense schemes and propose some improvement ideas.

1. 引言

网络编码在2000年被Ahlswede等人[1] 首次提出后便凭借其巧妙的思想、广阔的前景，立刻成为业内的研究热点。网络编码最大的优势就是通过大幅提升网络吞吐量来提高有效性，这是传统的存储-转发中继模式所不具备的。并且，网络编码还能提高网络的鲁棒性和安全性，在一些特殊领域，比如军事和商业领域，安全性是至关重要的。虽然中间节点网络编码后的数据不是直接的有用数据，信宿需要进行译码，这在一定程度上提高了安全性，但是这只是指网络编码在防窃听方面具有得天独厚的优势，而从另一角度看，由于中间节点网络编码后各输入链路的数据组合在了一起，致使一条链路的错误可迅速向整个网络蔓延，这不仅浪费了网络资源，而且会导致信宿译码出错，得不到有用数据，所以网络编码系统的安全性对于主动攻击来说又是非常脆弱的。

本文主要的贡献是：一是对现有的恶意攻击进行了细致的分类和定义，并总结了它们之间的区别与联系，能够帮助读者准确理解概念性问题；二是针对每类恶意攻击，重点介绍了现有的经典网络编码防御方案，能够帮助读者掌握其基本防御思想；三是对现有的网络编码防御方案提出了一些改进思路，可供下一步研究参考。

2. 基本概念

恶意攻击的分类标准有很多，但最常用的是以主动攻击和被动攻击进行区分，其次也有以外部攻击和内部攻击进行区分。主动攻击是指恶意节点主动发送伪造的错误数据来干扰正常通信；被动攻击是指恶意节点并不主动产生并发送数据，只是通过窃听来获取有用数据，该类攻击又称之为窃听攻击。内部攻击是指发动攻击的恶意节点原本是网络内部的合法节点，但是被攻击者利用各种手段进行了策反；外部攻击是指发动攻击的恶意节点是网络外部的非法节点。

根据主动攻击和被动攻击的分类标准，我们将恶意攻击大致分为了熵攻击、广义污染攻击和窃听攻击，再根据内部攻击和外部攻击的分类标准，我们又将广义污染攻击细分为拜占庭攻击和污染攻击。因此，现有的对网络编码系统的恶意攻击可较为细致地分为熵攻击、拜占庭攻击、污染攻击和窃听攻击四类[2] [3] ，四类恶意攻击的分类见表1。

熵攻击：熵攻击是以降低网络编码后数据的差异性为手段，来加长信宿的解码时间，降低网络吞吐

量，而在信息论中，信息的差异性就是用信息熵来表示，所以命名此类攻击为熵攻击。熵攻击既可以从网络内部的恶意节点发起，又可以从网络外部的恶意节点发起，所以其既可以是内部攻击，又可以是外部攻击，但它一定是主动攻击。熵攻击可以看作是一种特殊的重放攻击，恶意节点把前时隙接收到的或者非法窃听到的旧数据在新时隙按合法的网络编码规则进行编码后发出(我们将发出的数据称之为非创新数据)，而不对当前时隙发送的新数据进行编码并发送。又因为非创新数据是旧的数据按照合法网络编码规则编码产生的，所以具有很强的隐蔽性。

见图1所示，若熵攻击为内部攻击，A在时隙和向下游节点分别发送了数据和，在接收到后立刻向B转发，在时隙，A向发送了新数据但没有立刻向B转发，而是利用旧数据按照合法网络编码规则产生了非创新数据并向B转发，即 (a和b是随机选取的编码系数)，这样就会导致B得不到但系统又难以检测；若为外部攻击，同理，外部攻击者C在非法窃听到A发送给下游节点和的数据和后，在时隙按照合法网络编码规则产生了非创新数据并发送给B，即(和是随机选取的编码系数)，这样就会干扰B得到时隙的新数据。

拜占庭攻击：拜占庭攻击是从网络内部发起的，所以其是内部攻击，也正因此，内部恶意节点既有能力窃取到网络传输的有用数据，又有能力主动发送伪造的错误数据来污染有用数据，达到干扰信宿译码，降低网络吞吐量的目的。虽然恶意节点既有窃听又有污染的能力，但是其危害性主要源于主动污染，所以我们将其归为主动攻击一类。因为拜占庭攻击是内部攻击，所以其很难察觉且危害巨大。

污染攻击：污染攻击是指网络外部攻击者向网络主动发送伪造的错误数据来污染有用数据，达到类似于拜占庭攻击的目的，所以其既是外部攻击，又是主动攻击。它和拜占庭攻击的区别除了一个是外部攻击，一个是内部攻击外，还在于一个不具有窃听的能力，而一个具有窃听的能力。图2描述了污染攻击在随机线性网络编码中的一个实例。

窃听攻击：对窃听攻击的理解就非常简单了，顾名思义，窃听攻击就是指外部攻击者非法地窃听到网络传输的有用数据。对于有线网络来说，外部攻击者是采用搭线窃听的手段，对于无线网络来说，外

部攻击者则是利用高频天线等手段进行窃听。也因为窃听攻击者不会主动发起攻击，所以其是被动攻击，也因此具有隐蔽性。并且人们通常说的被动攻击一般就是特指窃听攻击，见图3。

四类恶意攻击的联系与区别见表2。

Table 1. Classification of four malicious attacks

表1. 四类恶意攻击的分类

Figure 1. Entropy attack

图1. 熵攻击

3. 防御方案

目前，针对这四类恶意攻击，现有的网络编码防御方案主要是基于信息论和密码学。

对广义污染攻击来说，现有的网络编码防御方案可大致分为三类：污染纠错、污染检测和污染源定位，其中污染纠错主要是基于信息论，通过构建网络纠错码，而污染检测和污染源定位主要是基于密码学，通过利用同态哈希函数、同态签名、线性子空间签名和认证码等手段。

Figure 2. Pollution attack

图2. 污染攻击

Figure 3. Eavesdropping attack

图3. 窃听攻击

Table 2. Relationship and difference

表2. 联系与区别

对于窃听攻击来说，基于信息论的网络编码防御方案一般是通过限制窃听者的窃听能力来设计网络编码规则，使窃听者译码不出有用数据，从而达到弱安全。而基于密码学的网络编码防御方案一般是对信源数据或编码系数进行加密，使窃听者不能解出有用数据，从而达到弱安全。

3.1. 熵攻击

熵攻击的基本防御思想是通过各种手段来检测接收到的数据是否为非创新数据，若是则舍弃，若不是则进行译码得到有用数据。

Gkantsidis等人[4] 首次提出了熵攻击的概念，并设计了一种防御熵攻击的方案，即检测已编码数据间的线性相关性来判断哪个已编码数据为非创新数据，然后舍弃。但该防御方案的缺点是在一个很大的有限域内进行，所以其计算量很大，耗时很长，大幅降低了网络吞吐量。

Jiang等人[5] 基于自适应概率子集的线性相关性检测算法(S-PSLD)，设计了一种高效的非创新数据过滤方案来防御熵攻击，此方案改进了文献[4] 提出的防御方案，大幅降低了计算量。

缓冲监视(BM) [6] 的防御思想见图4所示，X是被怀疑需要监视的节点，W是监视节点，A，B，C是X的上游邻节点。实线表示用于数据传输的无线信道，虚线表示监视节点接收数据的信道。由于无线通信的广播性，W会接收到A，B，C三节点发给X的数据和X发给下游节点的数据，若W发现X发出的数据是非创新数据的话，就可以判定X为恶意节点。

3.2. 拜占庭攻击

针对拜占庭攻击的网络编码防御方案主要分为基于信息论和基于密码学两类。

3.2.1. 基于信息论的防御方案

Cai等人[7] 将经典纠错码的思想引入到网络编码系统中，提出了网络纠错编码这一概念，即在某一时刻通信网络中发生符号错误的链路数没有超出纠错能力范围时，信宿可以通过译码将错误进行纠正。

文献[8] [9] 给出了当信道存在噪声时网络纠错编码的具体编译码算法。

Jaggi等人[10] 设计了一种分布式随机网络编码防御方案对拜占庭攻击进行纠错。根据恶意节点攻击能力的不同，作者提出了三种算法，但三种算法的基本思想都是将恶意节点视为第二信源。因为信宿接收到的数据是来自信源和恶意节点数据的线性组合，所以只要信宿接收到足够多线性独立的编码数据，就可以译码出来自信源和来自恶意节点的数据，并根据一些限制条件判断出来哪些是来自信源的有用数据，哪些是来自恶意节点的污染数据。

基于信息论的防御方案的纠错或检错效率往往比较高，但是普遍都存在一些局限性：一是都是以攻

Figure 4. Defense of BM

图4. BM防御

击者的攻击能力受限为前提；二是攻击者的攻击能力越强，需要用来纠检错的冗余数据就越多，而冗余数据越多会导致编码率越低，消耗的网络资源越多；三是这些方案只能使信宿被动地对接收到的数据进行纠错或检测，而不能主动地定位、丢弃恶意节点，这样就加长了信宿的译码时间，降低了网络吞吐量。

3.2.2. 基于密码学的防御方案

两不相邻的监视方案[11] 假设信源和信宿是可信的，而其他任何中间节点都可能是恶意节点，但只有相邻节点可以共谋。见图5所示是两个X型的网络拓扑结构，从信源到信宿的数据流有两条：S₁到T₁，S₂到T₂。C₁和C₂是进行网络编码的中间节点。每条数据流被两个监视节点监视，因为两个监视节点不相邻，所以它们不能共谋。

以S₁到T₁这一数据流为例，R₁是被怀疑节点，S₁和R₂是两个不相邻监视节点，所以R₁和R₂，S₁和R₂之间都不能交流。在第一时隙，S₁将传输至R₁和C₁。在第二时隙，R₁将传输至T₁和C₂。在第三时隙，R₂从C₁接收到网络编码后的数据()，此时R₂利用第一时隙从S₂得到的即可解码得到。在第四时隙，R₂从C₂接收到网络编码后的数据()，此时R₂利用第二时隙它传输的即可解码得到。接下来进行判断，若，那么R₁就不是恶意节点，反之则是。

3.3. 污染攻击

由于污染攻击和拜占庭攻击同属于广义污染攻击，所以针对污染攻击的网络编码防御方案也主要分为基于信息论和基于密码学两类。

3.3.1. 基于信息论的防御方案

防御拜占庭攻击的基于信息论的方案对于污染攻击来说同样适用。

3.3.2. 基于密码学的防御方案

利用同态哈希函数的防御方案：Li等人[12] 利用同态哈希函数来检测污染攻击。在此方案中，见图6

Figure 5. Two X common topologies

图5. 两个X型网络拓扑结构

Figure 6. Homomorphic Hash and verification

图6. 利用同态哈希函数的防御方案

所示，数据x被分为这n块数据块，每块又被进一步分为这m块子数据块。。将哈希函数H(x)应用于上得到相应哈希值的，，，并且哈希函数H(x)具有同态性质即。这n个哈希值被提前发至各个节点。因为网络编码后的x应该是的线性组合，编码系数为，即，所以根据哈希函数的同态性，如果中间节点或信宿接收到的数据的哈希值等于，那么消息没被污染，反之则已被污染。

利用线性子空间签名的防御方案：基于正交向量检测污染攻击的网络编码防御方案[13] 的基本思想是计算出子空间的正交向量并将其发送给中间节点和信宿，这些节点可以利用正交向量检测接收到的数据向量是否被污染。比如，信源发送h个数据，每个数据是N维向量，那么信源发送的消息矩阵就是：

(1)

消息矩阵中，网络中边e上传输的数据是 的线性组合，记为，是全局编码向量，所以。因为向量且线性独立，所以它们可以构成一子空间X，由于y(e)是线性组合，所以。子空间X中的每一个向量都可以视为合法数据，那么求出满足的子空间X的正交向量。将正交向量v提前发给网络中的其它节点，若中间节点或信宿接收到的数据向量点乘v等于0则数据没有被污染，反之则已被污染。并且可以根据上游节点的点乘值来判断恶意节点的具体位置。

3.4. 窃听攻击

针对窃听攻击的网络编码防御方案也主要分为基于信息论和基于密码学两类。

3.4.1. 基于信息论的防御方案

Cai等人[14] 提出了搭线窃听的网络通信模型GSTW，并构造了在信息论意义下的安全网络编码防御方案，即窃听者无论窃听所给定窃听集内的哪个窃听子集都无法恢复出原始数据。随后，他们进一步提出了r-安全网络编码防御方案[15] [16] ，该方案也需限制窃听者的窃听能力，即窃听信道数小于加入的随机数个数r。

Bhattad等人[17] 适当合理地降低了安全条件，提出了弱安全网络编码的概念，只要窃听者无法获得任何有用数据即可。当窃听者不能获得信源发送的任何原始数据时，我们称之为信息论安全网络编码；当窃听者不能获得信源发送的任何有用数据时，我们称之为弱安全网络编码。由于弱安全网络编码放宽了安全条件，但又很好地保护了有用数据，相对于信息论安全网络编码来说，又提高编码的最大多播速率，因此，现在人们研究的防窃听网络编码防御方案基本上都是追求达到弱安全。

文献[18] 已知网络的拓扑结构，设计了防窃听的网络编码防御方案。图7是窃听者位置已知的简单双向通信防御方案：s为信源，d为信宿，e为窃听节点，假设e的窃听能力受限，因为e在靠近s的sd直线上，所以s广播给d的数据会被e窃听到，而d广播s的数据则不会。因此，根据此网络拓扑结构设计的网络编码防御方案是：第一步，d产生一个随机数k并发送给s，第二步，s利用接收到的k对有用数据x进行网络编码如c = x♁k，然后发送给d。则d有c和k即可解码出x，而e只有c而没有k则解码不出x。

图8是两个窃听者位置已知但不共谋的防御方案：s，d，a，b是合法节点，e₁，e₂是两个位置已知但不共谋的窃听节点，e₁在s到a的传输路线上，e₂在s到b的传输路线上。根据此网络拓扑结构设计的

网络编码防御方案是：a，b分别生成随机数k₁和k₂并发送给s和d，然后s将进行网络编码c = x♁k₁♁k₂并将c发送给a和b，最后由a或者b将c发送给d。d由于接收到c，k₁，k₂就可以解码出x，而e₁由于只窃听到c和k₁，e₂由于只窃听到c和k₂，所以都不能解码出x。

图9是两个窃听者位置未知但不共谋的防御方案：s，d，r₁，r₂，r₃，r₄是合法节点，e₁，e₂是两个位置未知但不共谋的窃听节点，并且窃听节点位置不会与合法节点位置相重。在此，我们假设两个窃听节点位于最好的窃听位置(见图9所示分别位于两个方格拓扑结构中央，这样就可以窃听到最大量的数据)。根据此拓扑结构设计的网络编码防御方案是：第一步，r₁，r₂分别生成随机数k₁，k₂并沿发送路径发送，第二步，s利用k₁，k₂进行网络编码c = x♁k₁♁k₂并沿发送路径发送。各路径传输完毕后可知，d由于接收到c，k₁，k₂所以可以解码出x，而e₁和e₂由于分别缺少k₂和k₁所以解码不出x。

3.4.2. 基于密码学的防御方案

基于信息论的防御方案以限制窃听者的窃听能力为前提，当它们面对窃听能力更强的窃听者时便不能保证网络的安全性。因此，用密码学手段来设计防窃听的网络编码防御方案受到了广泛的关注。

通过对编码后数据及编码向量进行排列加密操作的防窃听的网络编码方案，称之为P-Coding [19] 。其基本思想见图10所示，经过排列加密操作后，编码后数据和其编码向量可以混合和重新排序。由于在随机网络编码中的编码后数据是源数据的组合，要恢复出源数据就需要利用编码向量对其进行解码。而排列加密函数将编码向量的元素和编码后数据的元素随机混合后，窃听者很难定位到哪些是编码向量的

Figure 7. A simple two-way scheme

图7. 简单双向通信防御方案

Figure 8. Non-collaborating eavesdroppers of known location

图8. 两个窃听者位置已知但不共谋防御方

Figure 9. Eavesdroppers of unknown location

图9. 两个窃听者位置未知但不共谋防御方案

Figure 10. Permutation encryption on coded messages

图10. 在已编码数据上进行排列加密

元素，哪些是编码后数据的元素，也就无法解码出源数据。

防窃听的VSWNC方案[20] 要求信源信宿共享一个随机数生成器，其次信源可用随机数r在随机数生成器上生成一个范德蒙行列式P，随后用P对信源数据进行预编码处理，最后信宿可通过r得到P从而能够正确解码。把VSWNC方案应用于随机网络编码中，在牺牲少量带宽的情况下能保证以概率1达到弱安全。

信源编码：

信源在有限域Μ中选取一个随机数r，然后用r在随机数生成器上生成n − 1个随机数。这n − 1个数构成了范德蒙行列式。r是对窃听者绝对保密的。

(2)

X左乘P可得到。

(3)

在后加入单位冗余得到Y，其中为M上的随机数。

(4)

经过以上变换，信源就把Y发送出去。Y在网络中进行网络编码，即Z = FY。

信宿解码：

信宿收到Z后可用公式获得Y，然后得到r和。信宿再利用r访问随机数生成器，来获得，进而得到P。又因为，所以信宿就可以获得信源数据X了。

3.5. 万能攻击

就像我们会想方设法地保护网络的安全性一样，攻击者也会采取各种手段来达成他们的目的。在现实中，攻击者往往会采用多类恶意攻击来同时攻击网络，因此，设计出能同时防御多类恶意攻击的网络编码防御方案是大势所趋，我们称此类防御方案为抗万能攻击方案。

文献[21] 利用哈希函数和安全信道对随机单跳网络编码进行改进，采用一个维随机向量和两个哈希函数，来同时防御窃听攻击和广义污染攻击。该方案仅改变了信源和信宿的编解码方式，而未改变中间节点的网络编码方式。

信源编码：

信源产生的原始数据M要经过2次变换：

(5)

为原始数据向量，其中。在有限域上选取随机向量，且服从均匀分布。使用哈希函数使得。我们通过构建新的数据向量：

(6)

经过第一次变换，得到了新的数据矩阵。使用哈希函数：，得到哈希值并附加在数据向量之后，使之形成新的向量。

(7)

经过第二次变换后，信源形成了新的数据向量，每个数据向量由k + l位符号组成，前k位符号为数据消息，后l位符号由的哈希函数值构成。

信宿译码：

信宿收到一个消息矩阵D，其由n个线性独立的数据组成。

(8)

T为n个数据系数组成的系数矩阵，求出逆矩阵，解码出数据矩阵。数据向量的前k位是数据消息，通过安全信道接受到随机向量，信宿可以从中解出。稍后信宿通过哈希函数计算出，与收到的矩阵对比，如果值相同，则说明没有受到污染攻击。反之则受到，那么就丢弃此数据矩阵D。

对于窃听攻击，由于随机向量是由安全信道传输的，攻击者无法窃听到，即使攻击者窃听到n个线性独立的数据，解码出，但由于没有得到随机向量，因此无法解码出M，所以该方案防窃听攻击。并且，攻击者虽然知道了哈希函数，但是没有解码出M，因而无法得到正确的哈希值，所以该方案也防广义污染攻击。然而，信宿只能检测出污染并丢弃整个数据矩阵，而不能进行纠错，这样就延长了传输时间，降低了网络吞吐量。Xu等人[22] 先是利用稀疏矩阵对信源数据进行矩阵变换达到了防窃听的目的，再利用列表译码法在信宿处进行译码，有效地进行了纠错，也达到了防广义污染攻击的目的，并进一步缩短了传输时间。

在文献[5] 的基础上出现了一种增强型的抗万能攻击方案[23] 。该方案通过计算信宿接收到的数据的线性相关性来判断其是否为非创新数据，再检测其是否为污染数据，只要有一样是，就将其过滤掉，达到了既防熵攻击又防广义污染攻击的目的。

4. 总结

网络编码从根本上改变了通信网络的中继转发模式，具有巨大的潜力，而安全性作为限制其发展应用的一大制约指标，设计网络编码防御方案已成为一个研究热点。分析总结现有的网络编码防御方案，我们提出了一些改进思路，供读者参考：

1) 网络编码的最大优势是提高通信网络的有效性，而信道编码是提高可靠性，研究怎样将网络编码和信道编码完美结合则可以同时提高通信网络的有效性和可靠性。

2) 在防御广义污染攻击时，可以考虑建立集检错和纠错于一体的网络编码防御方案。

3) 大多数现有的网络编码防御方案只针对一类或两类恶意攻击，或者限制了攻击者的攻击能力。例如，针对拓扑结构设计的NC方案来防御窃听者们也是假设窃听者们不共谋罢了。随着攻击技术的快速发展，我们的防御方案也需要在深度上和广度上快速发展，最好能实现深度和广度的完美结合，达到真正意义上的抗万能攻击。

4) 一些防御方案需要特殊的网络拓扑结构或额外的安全信道，如方格网络拓扑结构、两个X型网络拓扑结构等。在现实的无线网络系统中，这些拓扑环境都很难满足，所以适用性更强的网络编码防御方案是未来的趋势。