一种基于压缩短零向量的抵抗网络编码中污染攻击的方法

摘要

本发明公开了一种基于压缩短零向量的抵抗网络编码中污染攻击的方法，采用网络编码的数据传输系统中包括有源结点、中间结点和宿结点，其特征在于，数据传输的方法包括：(1)源结点向网络分发数据包及验证信息；(2)中间结点对收到的包进行检测和编码传输操作；(3)宿结点对收到的包进行检测；同时，当收到

说明书

技术领域

本发明涉及网络通信安全领域，特别涉及一种基于压缩短零向量抗网络编码中污染攻 击的方案设计。

背景技术

网络编码是一种融合了路由和编码的信息交换技术，它的核心思想是在网络中的各个 结点上对各条信道上收到的信息进行线性或者非线性的处理，然后转发给下游结点，中间 结点扮演着编码器或信号处理器的角色。网络编码主要特征是允许结点对数据包进行编码 操作。该思想的提出，引起了学界广泛关注，主要体现在其相较于传统存储转发机制，在 吞吐量、数据机密性、数据流的不可追踪性、鲁棒性等性能上的显著优势。目前大多数研 究集中于线性网络编码。

虽然网络编码的引入能带来很多好处，但如果网络中存在恶意结点发起污染攻击 （pollution attacks），那么，整个系统的各方面性能将会大大下降。污染攻击是主动攻 击中的一种，这种攻击方式通常也会被称为干扰攻击（jamming attacks）或拜占庭攻击 （byzantine attacks）。这种攻击方式的特点是，恶意结点作为攻击者通过篡改或伪造数 据包来生成污染数据包，并将这些污染包传播到网络中，经由其它结点编码达到污染整个 系统的目的。正确的数据包和错误的数据包经由合法的结点的编码操作会生成新的污染包， 导致污染的扩散。如果不对数据包进行错误检测或纠错，那么宿结点（即，接收结点）将 很难解码以恢复原数据。

针对污染攻击，已有的方案可大致分为2大类：1.端到端的错误检测与纠错；2.实 时污染检测。由于第一大类方案的检测存在滞后性，在攻击者较多或网络较大时无法有效 控制污染的扩散，同时会浪费系统带宽及计算资源，所以主要考虑的是第二大类方案。

实时污染检测这一大类方法的主要特征是，它们都提供了使中间结点能实时检测单个 收到的包的方法，从而能及时检测出污染包并丢弃它们，使污染得到有效控制。这一大类 方法可以大致分为3小类：

（1）基于离散对数问题的同态方案。例如，Gkantsidis等人设计了一种基于同态哈 希函数的合作方案以抵抗污染攻击。这一子类的优点是它们的安全性较好，即，攻击者根 据源结点提供的检测污染包的信息很难构造出能通过检测的污染包，缺点是，检测时的计 算开销大，以至于检测导致的延时会成为系统的性能瓶颈。

（2）基于拓扑的污染检测和攻击者定位方案。这类方案能有效定位攻击者，从剔除 污染源的角度抵抗污染攻击。优点是，能使系统很快从污染中恢复，缺点是，这类方案一 般需要更为复杂的信息共享机制以确保中间结点发布的信息的可信度，而且对于动态性较 大的网络适应性不好，因此在规模较大或动态性较大的网络中，例如P2P网络，就很难达 到上述两个要求。

（3）基于线性网络编码性质的零向量（null keys）方案。这类方案中，中间结点通 过正交性质来检测收到的包。优点是，检测时计算开销小，系统简单易实现，无需复杂信 息共享机制。缺点是，现有的这些方案或者是安全性不够高；或者是无法脱离C/S架构（即， 客户机/服务器架构）；或者是需要将零向量通过离散对数问题的难解性加以保护：

（3.1）其中安全性不够高指的是，攻击者根据源结点提供的零向量的信息很容易构 造出能通过检测的污染包。由于零向量是按网络编码形式在网络中传输的，而源结点发放 的零向量仅仅是满零空间的一部分（主要因为要使发放的零向量构成满零空间所需的零向 量的量一般比要分发的数据包总量的还大很多，其中，满零向量空间指的是全部零向量构 成的线性空间），网络中的结点既然能很好地恢复原数据（这一点可由使用网络编码所带来 的高鲁棒性保证），那么这些结点要获得源结点分发的全部零向量所构成的线性空间也是很 容易的，很难保证这些结点中没有攻击者。而且如果再考虑攻击者间相互勾结以共享零向 量信息，那么能获得源结点分发的全部零向量所构成的线性空间的结点就更多了。而一旦 攻击者获得了这样的线性空间，由于这个线性空间并不是完整的零空间，攻击者可以通过 构造正交于这个线性空间且不在原来数据包构成的线性空间中的向量作为污染包，并在网 络中传播这些污染包，此时，整个系统中任何一个结点都无法检测出这些包是污染包，使 得整个系统被污染。

（3.2）无法脱离C/S架构指的是，源结点分发零向量时按一对多结构分发，对于不 同结点分发不同零向量，以实现零向量的隔离保护。在某些技术方案中，源结点还需要保 存各结点已有的零向量的部分信息以进行零向量更新，且零向量通过加密形式传输，所以 源结点负载较大。在网络规模变大时这种架构的方案适应性会变差。

（3.3）需要将零向量通过离散对数问题的难解性加以保护指的是，源结点选取某个 零向量并利用离散对数问题的难解性将零向量设计成大数的指数形式加以保护，由于攻击 者无法得知用于检测的零向量，从而保证安全性。这样设计后，会存在类似第（1）子类方 案的问题。

发明内容

本发明的发明目的是提供一种基于压缩短零向量的抵抗网络编码中污染攻击的方法， 以在分布式大规模网络环境中保持原有零向量方案分布式特性好、检测计算开销小的优点 的同时，提高系统的性能。

为达到上述发明目的，本发明采用的技术方案是：一种基于压缩短零向量的抵抗网络 编码中污染攻击的方法，采用网络编码的数据传输系统中包括有源结点、中间结点和宿结 点，其特征在于，网络中数据传输的方法包括：

(1)源结点向网络分发数据包及验证信息；

源结点分发的数据包及验证信息主要通过初始化、生成数据包和用作验证数据的压缩 零向量、同态哈希压缩零向量三个子步骤得到；

(2)中间结点对收到的包进行检测和编码传输操作；

所述收到的包包括数据包形式的包和压缩零向量形式的包，中间结点对收到的数据包 及压缩零向量分别进行检测和编码；

当收到的包是压缩零向量时，利用同态哈希函数的同态性检测压缩零向量的正确性， 如正确则进行保存，不正确则丢弃；

当收到的包是数据包形式时，利用向量的正交性质通过该结点已有的通过检测的压缩 零向量检测该数据包，若此时本结点并无一通过验证的数据包，则直接检测收到的数据包； 若本结点已有通过验证的数据包，则检测该数据包的前m个元素构成的向量和已通过验证 的各数据包的前m个元素构成的向量组的线性相关性，m为2到100间的整数，若相关则 直接丢弃收到的数据包，若不相关再用该结点已通过验证的压缩零向量检测收到的数据包； 如果该结点没有任何通过检测的压缩零向量存在，则默认该包通过检测；

中间结点对正确的数据包及压缩零向量分开进行随机线性网络编码操作，再进行传 输；

(3)宿结点对收到的包进行检测，检测方法与步骤(2)相同；同时，当收到m个线性无 关的通过检测的数据包时，宿结点进行解码操作。

具体方案解释如下：

结点分为源结点、中间结点、宿结点。其中，源结点是整个网络中的数据源，负责分 发数据包和提供验证数据。中间结点负责对收到的零向量包和数据包加以检测，丢弃错误 的包，对通过检测的包进行随机线性网络编码并传输编码后的包。宿结点除了有中间结点 的操作，还包括解码操作，以恢复源结点传播的数据。

其中，可能存在恶意结点。恶意结点根据收到的包和源结点提供的验证数据构造污染 包以最大程度污染网络。恶意结点既可以是中间结点，也可以是宿结点。最大程度污染网 络是指，污染包不被中间结点检测出来的概率最大，以使这些包能经由正常的编码操作扩 散污染。

一、源结点执行的操作。

源结点，是整个数据通信的数据源，主要负责向网络分发数据包及验证信息。其分发 的数据包及验证信息主要通过初始化、生成数据包和CNKs、同态哈希CNKs三个子步骤得到。 具体过程如下：

1.初始化相关参数、数据和所需函数。

（1）选定q，m，n，u，seed_ini的值。其中，q是一个大素数（q的长度大于等于 256bit，大素数可以通过重复使用Rabin-Miller算法生成，具体过程可参考关于现代密码 学的书籍），用于确定执行随机线性网络编码操作和数据包的检测操作所使用的素数域F_q； 选取正整数m和n，n远大于m。选取正整数u满足（在实际选定u的时候， 越大的u值系统的性能越好，且建议选定m|n，即选定m，n的值使得n能整除m，原因是 这样选定的参数能使方案获得更高的安全性）。

选取正整数seed_ini用作函数srand₂的输入。srand₂是伪随机发生器rand₂的种子函数用于初 始化rand₂，即seed_ini是伪随机发生器的种子。

（2）生成m×n的矩阵B。需传输的原始数据中每位表示为F_q中的一个元素； 每个元素组成一个数据段。若映射得到的元素个数不是整倍数，则最后剩余的元素补上元素0组成长为个元素的数据段，该数据 段的数据长度定义为除补上的元素以外的元素个数。将每个数据段的数据长度值映射为F_q中的个元素。个元素跟该数据段中的个元素， 共m×n个元素，构成一个向量，其前个元素对应数据长度，后个元素对应数据。最后，将m×n个元素中每n个构成一个向量，共得到m个向量，第i个 向量用b_i表示，称为原始数据块（original data block）。b_i=[b_i,j]_1×n,其中b_i,j表示b_i中第j个元素，b_i,j∈F_q。以b_i为行向量生成的m×n的矩阵记为B。

（3）选定伪随机发生器rand₁，rand₂，并初始化伪随机发生器rand₂，初始化的目的 是使伪随机发生器rand₂产生一串随机的数。rand₁用于生成F_q内的随机数，srand₁函数是 伪随机发生器rand₁的初始化函数。rand₂用于生成随机正整数，srand₂函数是伪随机发生 器rand₂的初始化函数。源结点执行srand₂(seed_ini)以初始化rand₂（具体过程可参考陈建平 等，《C++程序设计教程》，高等教育出版社，中2.4.2节）。

2.生成m×(m+n)的矩阵V，的矩阵T和1×u的向量Seed。下 面是生成V，T和Seed的具体过程：

即，在矩阵B前面 附加一个m×m的单位阵I，并将新生成的矩阵记作V，处于矩阵V中第i行第j列的元素记 作v_i,j，处于矩阵V中第i行的向量记作v_i，v_i即为原始数据包（original data packet）。

（2）V'是一个m×(m+n)的矩阵，将其最左侧的m×m子矩阵赋值为单位阵，矩阵中 其他元素的取值任意。形式为：处于矩阵V'中第i行第j列的元素为v'_i,j，其中标识为x_i,j的元素表示处于矩阵中第i行第j 列的元素取值为F_q中的任意值。

（3）将矩阵T中最顶部的子矩阵赋值为单位阵，矩阵中其他元素的取值 任意。T的形式为：

标识为x'_i,j的元素取值为F_q中的任意值。

（4）生成向量S_w，$\forall w\in \{1,...,u\}.$对于$\forall w\in \{1,...,u-n\mathrm{mod}u\},$

对于

$\forall w\in \{u-n\mathrm{mod}u+1,···,u\},$

（5）生成m×(m+|S_w|)的矩阵P_w，其中|S_w|表示向量S_w的长度， 即S_w所含的元素个数。针对每个矩阵P_w，将P_w中的第k列赋值为V中的第S_w,k列，S_w,k表 示S_w中的第k个元素的值，P_w的形式为：

（6）操作（6.1）-（6.11）使各P_w满秩化，更新矩阵V'，并更新矩阵T。对于P_w， $\forall w\in \{1,···,u\}:$

（6.1）将m×m的矩阵T₁赋值为P_w最右侧的m×m子矩阵。T₁的形式为：

（6.2）m×m的矩阵T₂等于T₁。

（6.3）seed=Inf，选取Inf为不在rand₂的输出范围中的一个数。

（6.4）如果T₂满秩，则执行操作（6.5）；如果T₂不满秩，执行操作seed=rand₂()， srand₁(seed)，并且对于T₂中的每个元素T₂[i,j]，T₂[i,j]表示位于 T₂中第i行第j列的元素，执行操作$T_2[i,j]=T_1[i,j]+{\mathrm{rand}}_1\left(\right)=v_{i,S_{w,S_w-m+j}}+{\mathrm{rand}}_1\left(\right),$该加法是有 限域F_q上的加法，其中，T₁[i,j]表示位于T₁中第i行第j列的元素，最后继续执行操作（6.4）。

（6.5）更新V'。对于将P_w中的第k列赋值给V'中的第S_w,k列； 对于将T₂中的第k-|S_w|+m列赋值给V'中的第S_w,k列。

（6.6）Seed[k]=seed，其中Seed[k]表示Seed中的第k个元素。

（6.7）P_w'是一个m×|S_w|的矩阵。将P_w中的前|S_w|-m列赋值给P_w'的前|S_w|-m列， 将T₂中的m列赋值给P'_w剩下的m列。即P_w'的形式为：

（6.8）T₃是一个|S_w|×(|Sw|-m)的矩阵。求解得到中的|S_w|-m个基向量。将T₃中|S_w|-m个列向量赋值为|S_w|-m个基向量。

（6.9）通过高斯消元法（Gaussian elimination）对T₃做列变换，使得T₃的顶部的 (|S_w|-m)×(|S_w|-m)子矩阵成为单位阵。

（6.10）如果nmodu≠0且w≤u-nmodu，则对T₃做列填充，即，在T₃的最左侧填 充一个全部元素为零的列向量，使得T₃=[0,T₃]。

（6.11）对于将T₃中的第行赋值给T中的第 行。

（7）将V'赋值给V，V中的m个行向量构成代。同一代的每个行向量或这些向量的 任意线性组合均称为该代中的数据包（data packet）。整个网络中所有结点的编码操作均 只在同一代的数据包之间进行。矩阵T的每个列向量或这些向量的任意线性组合均称为这 代数据包的CNK（compressed null key，压缩零向量），CNKs的编码操作也只能在属于同 一代的CNKs间进行。

3.生成CNKs的验证信息(使用C.Gkantsidis等，文献“Cooperative security for  network coding file distribution”，INFOCOM，2006中提出的方法计算)。

（1）选定一个大素数r，r的长度大于等于1024bit，且使r-1能整除q。

（2）从素数域F_q中随机选定mu个数构成1×mu的向量g，其中g_k表示g中第k个元 素，k∈{1,…,mu}。

（3）对T中每一列列向量求哈希值。具体过程如下：T[i,j]表示位于T中第i行第j列 的元素，h(T_j)表示第j列的哈希值，则h(T)表示T中各列CNK 的哈希值所构成的向量，则有

4.向下游结点分发数据包和验证信息。

（1）首先源结点将参数q，m，n，u，r，函数srand₁，rand₁，向量Seed，g，及 h(T)以广播的形式传播至网络中的所有结点。

（2）接着，源结点对矩阵T进行转置然后，对所有的行向量进行随机线性网络编码 发送给该结点的部分邻居结点（邻居结点的选择由具体路由协议决定）。将矩阵V的所有行 向量进行随机线性网络编码发送给该结点的部分邻居结点。每次用随机网络编码操作生成 新的数据包时，随机从F_q中选取m个数作为编码系数，记作α₁,α₂,…,α_m，生成的数据包y为： $y=\underset{i=1}{\overset{m}{\Sigma }}{\alpha }_i{v}_i=[\underset{i=1}{\overset{m}{\Sigma }}{\alpha }_i{v}_{i,1},\underset{i=1}{\overset{m}{\Sigma }}{\alpha }_i{v}_{i,2},...,\underset{i=1}{\overset{m}{\Sigma }}{\alpha }_i{v}_{i,m+n}]=[{\alpha }_1,{\alpha }_2,...,{\alpha }_m,\underset{i=1}{\overset{m}{\Sigma }}{\alpha }_i{v}_{i,m+1},\underset{i=1}{\overset{m}{\Sigma }}{\alpha }_i{v}_{i,m+2},...,\underset{i=1}{\overset{m}{\Sigma }}{\alpha }_i{v}_{i,m+n}]$。同理，对CNKs执行的随机线性网络编码操作也一样。

二、中间结点执行的操作。

这类结点主要对收到的数据包和CNKs进行检测和编码传输操作。其中，中间结点对 收到的数据包及CNKs分开进行检测和编码。编码传输操作具体指：对收到的数据包（或CNKs） 进行随机线性网络编码操作，得到新的数据包（或CNKs）后传输给其邻居结点。

1.中间结点对收到的包的检测过程如下：

（1）收到的包是CNK，利用同态哈希函数的同态性检测CNK的正确性。检测方法如下： 若此时本结点并无一通过验证的CNK，则直接检测收到的CNK；若本结点已有通过验证的CNK， 则检测该CNK的前个元素构成的向量和已经过验证的各CNK的前个元素构成的 向量组的线性相关性，若相关则直接丢弃收到的CNK，若不相关则将该CNK存入缓存。本结 点从缓存中随机抽取一定数量的待验证的CNKs进行随机线性编码产生一个新的CNK，然后 对其进行验证，这个过程称为对缓存内的CNKs的打包验证。从缓存中抽取的CNK的数量由 本结点按安全性需求高低以及自身的计算负载情况设定。该值既可设定为定值，也可动态 按需更新。

具体的验证过程如下：设用τ表示待检测的CNK，τ是一个的行向量。 先求h(τ)，其中h(τ)表示τ的哈希值，表示τ中第个元素。再求比较两者是否相等，如果相等，则τ通过检测，否则τ是错 的。如果检验不是打包检验，则上述检验过程给出的结果表明接收到的CNKτ是否有差错。 否则，上述检验过程给出的结果若是对的，则所有生成CNKτ的CNKs都是无差错的；若没 有通过检验，则表示生成CNKτ的CNKs中有错的CNKs存在。本结点可根据自身安全性与计 算负载情况选择丢弃本组CNKs，或仍将本组的各CNKs按一定概率保留在缓存以在下次打包 检测中检测。

（2）收到的包是数据包，则利用向量的正交性质通过该结点已有的通过检测的CNKs 检测该数据包，若此时本结点并无一通过验证的数据包，则直接验证收到的数据包；若本 结点已有通过验证的数据包，则检测该数据包的前m个元素构成的向量和已通过验证的各 数据包的前m个元素构成的向量组的线性相关性，若相关则直接丢弃收到的数据包；若不 相关再用该结点已通过验证的CNKs检测收到的数据包。如果该结点没有任何通过检测的CNK 存在，则默认该包通过检测。设用y表示该数据包，用CNKs检测的具体操作如下：

（2.1）将用于检测的CNKs解压缩。对于给定的CNK的解压缩如下：根据该CNK，可 得到u个零向量。ζ_w表示得到的第w个零向量，如果nmodu≠0且w≤u-nmodu，则 否则，根据上述方法，每个CNK均可解压缩得到u个零向量，这种零向量的长度比E.Kehdi等 （“Null keys:limiting malicious attacks via null space properties of network  coding”，INFOCOM,2009）,提出的方案中的长度短，检测的元素个数少，称之为短零向量。

（2.2）用解压缩得到的每一个短零向量对数据包中部分位置上的元素进行检测，直 至检测出该包是污染包，或该包通过所有短零向量的检测为止，若是污染包则直接丢弃该 包。检测方法如下，若用ζ_w检测y，则计算若该值为0，则y通过ζ_w的 检测，否则y为污染包，其中S_w,k表示S_w中第k个元素的值，yS_w,k表示y中第S_w,k个元素的 值，ζ_w,k表示ζ_w中第k个元素的值。

2.中间结点对正确的数据包及正确的CNKs分别进行随机线性网络编码操作，并将得 到新的数据包和CNKs后传输给其邻居结点。如果本结点有l(1≤l≤m)个通过检测的线性无 关的数据包，记作y₁,y₂,…,y_l，则对数据包执行的随机线性网络编码操作类似于源结点， 即，随机从F_q中选取l个数作为编码系数，记作α₁,α₂,…,α_l，以生成数据包y，同理，对CNKs执行的随机线性网络编码操作也一样。

三、宿结点执行的操作。

宿结点除了执行中间结点的操作外，一旦收到m个线性无关的通过检测的数据包，则 进行解码操作以恢复源结点需发给它的数据。解码操作如下：

（1）首先以m个线性无关的通过检测的数据包为行向量构成矩阵，然后对矩阵进行 高斯消元使其最左侧的m×m子矩阵为单位阵。此时的矩阵即是矩阵V（此矩阵是在源结点 操作中1.（7）中的矩阵V）。

（2）而后根据伪随机发生器解码得到矩阵B，具体步骤如下：

（2.1）将矩阵V的右侧m×n子矩阵按列分成u个子矩阵，其中，第w个子矩阵所包 含的列记录在S_w中，即第w个子矩阵共包含|S_w|列，且子矩阵的第k列是 V中的第S_w,k列，对得到的每个子矩阵做操作（2.1.1）和（2.1.2）。

（2.1.1）移除该子矩阵中最左侧的m×m子矩阵。

（2.1.2）如果Seed[w]是Inf，则该子矩阵已处理完毕，得到的矩阵记作B_w；否则， 执行操作srand₁(Seed[w])初始化rand₁，最后，对经过（2.1.1）处理过的子矩阵的最右侧 m×m子矩阵中的每一个元素在F_q上减rand₁()，得到的矩阵记作B_w。

（2.2）通过（2.1）得到的u个子矩阵B_w，可构造出m×n的矩阵B， 即B=[B₁,…,B_u]。

（2.3）m×n的矩阵B中一共存储了mn个元素，将各行向量按行的升序排列成一个 1×mn的行向量，将其中前个元素表示的一个q进制的值映射到十进制，则该 值为数据长度,记为从1×mn的行向量中的第个元素开始，取出个元 素，将每个元素从q进制映射到一个位的二进制数，这映射得到的个位 的二进制数组成的数据串即为恢复出的源结点所传输的原始数据。

下面分析恶意结点攻击时可能会执行的操作，并讨论本方案抵抗恶意结点攻击时的安 全性，恶意结点可以通过污染零向量来攻击系统，零向量的安全性由同态哈希函数保证， 因此具有很高的安全性，在接下来的部分主要分析恶意结点通过污染数据包来攻击系统时 的安全性。

恶意结点可以是中间结点，也可以是宿结点，即，可以从网络中获取数据包和零向量 以及源结点发布的验证信息，也可以经由宿结点才有的解码操作恢复由源结点发布的原始 数据。它们通过以下三种攻击方法中最有可能造成污染的方法构造污染包并传播污染包。

1.随机攻击。恶意结点构造污染包时随机选定包中各元素的取值。可以证明，在结 点存在t个线性无关的正确CNKs的时候，随机攻击构造出来的污染包成功通过检测的概率 至多为然而，如果使用的是原零向量，那么结点同样存在t个线性无关 的正确原零向量的时候，随机攻击构造出来的污染包成功通过检测的概率为显 然在抵抗随机攻击时，使用CNKs进行验证的安全性不会比使用原零向量进行验证时低。

2.基于零向量攻击。受害者结点上游的恶意结点收集流经自己的CNKs，并与受害者 共享数据流的上下游恶意结点分享CNKs信息，以最大限度地预估受害者结点可能拥有的 CNKs信息，记线性无关的CNKs构成的集合为CK。如果上游的恶意结点共享后的CNKs满 秩，则本攻击退化成随机攻击；否则，恶意结点求取选取其中不属于Π_V的向量作为 污染包，并通过输出链路传播这些污染包。如果恶意结点共享CNKs后，它们的正确的CNKs 构成的矩阵记作K_malic，受害者结点拥有的正确的CNKs构成的矩阵记作K_node，那么与 交集空间的基向量个数就为则该结点能被基于零向量攻击攻 击成功的概率至多为$\frac{q^{m+n-(\dim \left(K_{\mathrm{malic}}\right)+\dim \left(K_{\mathrm{node}}\right)-\dim ({\Pi }_{K_{\mathrm{malic}}}\cap {\Pi }_{K_{\mathrm{node}}}))u+u-n\mathrm{mod}u}-q^m}{q^{m+n-\dim \left(k_{\mathrm{malic}}\right)u+u-n\mathrm{mod}u}}.$然而，如果使用的是原 零向量，那么在与交集空间的基向量个数同样为的时候， 该结点能被基于零向量攻击攻击成功的概率至多为显然在抵抗基于零向量攻击时，使用CNKs进行验证的安全性不会比使用原零向量进行验证 时低。

3.部分篡改攻击。恶意结点对一个正确包部分位置上的元素进行篡改，其他位置上 的元素保持不变。篡改的时候可以结合随机攻击，即，随机选定篡改位置上各元素的取值， 也可以结合基于零向量攻击，即，根据共享的CNKs信息构造篡改位置上的各元素。由于构 造CNKs时做过数据填充，可以证明结合随机攻击时篡改位于S_w,w∈{1,2,…,u-nmodu}中 的元素所指示的位置上的数据成功攻击的概率会比随意篡改或篡改 S_w,w∈{u-nmodu+1,u-nmodu+2,…,u}中的元素所指示的位置上的数据高，而结合基于 零向量攻击时两者成功攻击的概率是一样的，具体如下：

（1）结合随机攻击。可以证明，在结点存在t个线性无关的正确CNKs的时候，恶意 结点用随机选取的值篡改S_w,w∈{1,2,…,u-nmodu}中所示的数据以构造污染包时（假设篡 改了可能的S_w中的l个，被篡改的S_w的下标w记在集合W中），则该污染包能通过检测的 概率至多为而如果恶意结点仅篡改 S_w,w∈{u-nmodu+1,u-nmodu+2,…,u}中所示的数据以构造污染包时（假设篡改了可能 的S_w中的e个，被篡改的S_w的下标w记在集合E中），则该污染包能通过检测的概率至多 为而如果恶意结点仅随意篡改的话（假设篡改了w∈{1,2,…,u-nmodu} 中的l个S_w，被篡改的S_w的下标w记在集合W中，篡改了 w∈{u-nmodu+1,u-nmodu+2,…,u}中的e个S_w，被篡改的S_w的下标w记在集合E中）， 则构造出的污染包能通过检测的概率至多为因此结合随机 攻击的部分篡改攻击在篡改同样个数S_w时，仅篡改位于S_w,w∈{1,2,…,u-nmodu}中的元 素所指示的位置上的数据成功攻击的概率会比随意篡改或仅篡改 S_w,w∈{u-nmodu+1,u-nmodu+2,…,u}中的元素所指示的位置上的数据高。

（2）结合基于零向量攻击。如果上游的恶意结点共享后的CNKs满秩，则本攻击退化 成（1），即结合随机攻击的部分篡改攻击；否则，恶意结点根据共享的CNKs信息构造篡改 位置上的各元素以获得更高的成功攻击概率。如果恶意结点共享CNKs后，它们的正确的CNKs 构成的矩阵记作K_malic，受害者结点拥有的正确的CNKs构成的矩阵记作K_node，恶意结点用 基于零向量的攻击方法篡改S_w,w∈{1,2,…,u-nmodu}中所示的数据以构造污染包时（假设 篡改了可能的S_w中的l个，被篡改的S_w的下标w记在集合W中），则该污染包能通过检测 的概率至多为而如果恶意结点仅篡改 S_w,w∈{u-nmodu+1,u-nmodu+2,…,u}中所示的数据以构造污染包时（假设篡改了可能 的S_w中的e个，被篡改的S_w的下标w记在集合E中），则该污染包能通过检测的概率至多 为而如果恶意结点仅随意篡改的话（假设 篡改了w∈{1,2,…,u-nmodu}中的l个S_w，被篡改的S_w的下标w记在集合W中，篡改了 w∈{u-nmodu+1,u-nmodu+2,…,u}中的e个S_w，被篡改的S_w的下标w记在集合E中）， 则构造出的污染包能通过检测的概率至多为 因此 结合基于零向量攻击的部分篡改攻击在篡改同样个数S_w时，仅篡改位于 S_w,w∈{1,2,…,u-nmodu}中的元素所指示的位置上的数据成功攻击的概率和随意篡改或 仅篡改S_w,w∈{u-nmodu+1,u-nmodu+2,…,u}中的元素所指示的位置上的数据的成功攻 击的概率是一样的。

然而，如果使用的是原零向量，由于数据包中每个元素都同等地位地参与验证，所以 部分篡改攻击会退化为基于零向量攻击（鉴于基于零向量攻击的成攻击概率比随机攻击的 高），那么在与交集空间的基向量个数同样为的时候，该 结点能被部分篡改攻击成功的概率等于该结点能被基于零向量攻击攻击成功的概率，至多 为显然在抵抗基于零向量攻击时，使用CNKs进行验 证的安全性不会比使用原零向量进行验证时低。

由于t=dim(K_node)≥dim(K_node)-dim(K_malic∩K_node)，所以2中的基于零向量攻击成功 攻击的概率要比1中的随机攻击成功攻击的概率高；3中的（2）的结合基于零向量攻击的 部分篡改攻击成功攻击的概率要比3中的（1）的结合随机攻击的部分篡改攻击成成功攻击 的概率高；且3中的（2）的结合基于零向量攻击的部分篡改攻击成功攻击的概率要比2中 的基于零向量攻击成功攻击的概率高，因此最有效的攻击方法为结合基于零向量攻击的部 分篡改攻击。而在使用原零向量的方案中最有效的攻击方法为基于零向量的攻击，从上面 的理论分析可以看出，即便是在抵抗本方案最有效的攻击方法下，本发明的安全性都不会 比原零向量方案在抵抗其方案中最有效攻击方法下的安全性低。

可以看出使用CNKs能缩小污染的范围，首先由于以网络编码形式进行传输会使零向 量有很好的鲁棒性，即，经由随机线性网络编码后的零向量能很大概率的保证零向量的线 性无关性，大大减少了重复传输零向量的可能性，从而使零向量信息能在传输过程中被很 好地分布式保存；其次，本方案分发的零向量涵盖了整个零向量空间，而零向量的鲁棒性 保证了网络中局部存在这样的结点组，组内的结点所拥有的正确零向量能构成整个零向量 空间；最后，因为本方案减少了满秩零向量空间基向量的数量，使得构成这样的结点组需 要的结点个数变少，而正如前面提到的，能够证明，在CNKs满秩时只有正确的数据包才能 通过所有这些CNKs的检测，所以无论恶意结点通过什么方式构造污染包，这些污染包都不 可能通过整个结点组的验证，因此使用CNKs缩小能污染的范围，更好地抵抗勾结攻击。

下面的是对参数值选定的分析。鉴于由于n不能整除u时会降低CNKs抵抗部分篡改攻 击的安全性，所以建议在取定参数值的时候使n能整除u。另外，由于u取值越大方案所能 降低的零向量的开销越多，控制污染扩散范围的能力越强，所以，建议u取同时 考虑到上述两个建议，则有，在取定参数值时，取n能整除m，取u=n/m。n与m的差值 越大越能体现出使用CNKs相较于使用原零向量的优势。

附图说明

图1是实施例中的方案流程图；

图2是实施例中划分原数据包的子图；

图3是实施例中满秩化划分得到的数据包的子图；

图4是实施例中构造满秩化后数据包的子图；

图5是实施例中生成CNKs的子图；

图6是实施例中原数据包的示例图；

图7是实施例中满秩化后数据包的示例图；

图8是实施例中原零向量方案生成的零向量的示例图；

图9是实施例中生成的CNKs的示例图；

图10是实施例中网络拓扑示例图；

图11是实施例中方案运作过程图。

具体实施方式

下面结合附图及实施例对本发明作进一步描述：

实施例：

图中：带^T符号的符号：某向量或矩阵的转置。

标识为v_i,的矩形条：原数据包。

V：由原数据包v_i作为矩阵的第i行组成的矩阵。

标识为p_w,i,的矩形条：划分原数据包得到的数据包， 以下也称为短数据包。

P_w：由短数据包p_w,i作为矩阵的第i行组成的矩阵。

带阴影的矩形框：阴影标识的子矩阵中存储的数据构成单位阵。

白色的矩形框：白色标识的子矩阵中存储的数据是原始数据块中对应位置的数据。

标识为p'_w,i,的矩形条：经过满秩化操作后的短数据包。

P'_W：由短数据包p'_w,i作为矩阵的第i行组成的矩阵。

p_w,i,k：短数据包中数据的一般化表示。p_w,i,k表示短数据包p_w,i中的第k个数据。

p'_w,i,k：满秩化后的短数据包中数据的一般化表示。p'_w,i,k表示满秩化后的短数据包p'_w,i中的第k个数据。

rand()：伪随机发生器，随机生成域F_q上的数。

浅灰色的矩形框：浅灰色标识的子矩阵中存储的数据是原始数据块中对应位置的数据 在域F_q上加上rand()后得到的数据。

标识为v'_i,的矩形条：由满秩化后的短数据包构造出的数据包。

V'：由数据包v'_i作为矩阵的第i行组成的矩阵。

v'_i,j：构造出的数据包中数据的一般化表示。v'_i,j表示v'_i中的第j个数据， $\forall j\in \{\mathrm{1,2},...,562\}.$

矩阵P'_w的行向量所构成线性空间的正交线性空间，亦即， 矩阵P'_w的行向量的原零向量所构成的线性空间。

Π_CK：CK表示以CNKs为列向量构成矩阵，Π_CK表示矩阵CK的列向量所构成的线性 空间。

用大括号标注的数据：表示括出的范围中所含的数据元素的个数。

深灰色的矩形框：深灰色标识的矩阵中存储的数据是用于构造CNKs的数据。

以“部分w”标识的圆角矩形框，用于标识构造CNKs的对应部分 所用到的数据所在的位置。

标识在矩形条中的数字：各向量对应位置上的数据值。

带s的圆圈：源结点。带1或2的圆圈：中间结点，恶意结点。带3或4的圆圈：中间 结点。带r₁或r₂的圆圈：宿结点。

本发明旨在改进原有的基于零向量的抗污染攻击方案，以减少由于零向量的引入而导 致的开销。为了便于理解，首先对将描述的具体实施例作以下几点说明：

1.关于数值示例的参数选定。由于直接使用参数范围内的参数值（如，q取为一个 256bit的大素数，m取50，n取512等）用作数值示例的话，并不便于突出方案的实施 步骤和说明方案的设计原理。因此，除了选取各取值范围内的参数值（结合图2-图5）对 本方案作一般化说明外，为使整个实施过程更直观并易于理解，还提供了选取小数值作为 参数值（即，q取为素数7，m取2，n取4等）的数值示例（结合图6-图9）来具体阐述 本方案。

2.默认零向量的传输不被截断。本方案的应用环境主要针对规模较大、动态性较强 的网络，因此网络中零向量的传输因为恶意结点的蓄意不传而致使零向量的传输被完全截 断的可能性很小。所以在本方案中，默认零向量的传输不被截断是合理的。

3.关于网络拓扑示例的选定。在示例中采用了蝴蝶拓扑用以介绍恶意结点分别采用3 种攻击方法以及每种方法构造出的污染包和合法结点会采取的检测措施（结合图10），而并 未使用本方案所适用的规模较大、动态性较强的网络拓扑来介绍，其原因和采用小数值作 为参数值做数值示例的原因是一样的，即，为了使整个实施过程更直观并易于理解。

本发明的运作过程进一步描述如下，方案的流程图如图1所示，包括如下步骤：

一、源结点执行的操作。

源结点，是整个数据通信的数据源，主要负责向网络分发数据包及验证信息。而分发 的数据包及验证信息主要通过初始化、生成数据包和CNKs、同态哈希CNKs三个子步骤得到。 具体过程如下：

1.初始化相关参数、数据和所需函数。

（1）源结点选定q为一个长度为256bit的大素数，选定m为50，n为512，u为10， seed_ini为0。

（2）生成50×512的矩阵B。首先需传输的原始数据中每位表示为F_q中的一 个元素。然后，每个元素组成一个数据段。若映射得到的元素个数不 是整倍数，则最后剩余的元素补上元素0组成长为 个元素的数据段，该数据段的数据长度定义为除补上的元素以外的元 素个数。将每个数据段的数据长度值映射为F_q中的个元素。个 元素跟该数据段中的个元素，共25600个元素，构成一个向量，其前 个元素对应数据长度，后个元素对应数据。最后，将 25600个元素中每512个构成一个向量，共得到50个向量，第i个向量用b_i表示，称为原始 数据块（original data block）。b_i=[b_i,j]_1×512,其中b_i,j表示b_i中第j个元素， b_i,j∈F_q。以b_i为行向量生成的50×512的矩阵记为B。

（3）选定伪随机发生器rand₁，rand₂。srand₁函数是伪随机发生器rand₁的初始化函 数。srand₂函数是伪随机发生器rand₂的初始化函数。执行srand₂(0)以初始化rand₂。

2.生成50×562的矩阵V，552×52的矩阵T和1×10的向量。在图2-图5中给出了 按1中的（1）设定参数时本方案的执行步骤。

（1）V=[I,B]，即，在矩阵B前面附加一个50×50的单位阵I，将新生成的矩阵记 作V，处于矩阵V中第i行的向量记作v_i，v_i即为原始数据包，如图2所示。

（2）V'是一个50×562的矩阵，将其最左侧的50×50子矩阵赋值为单位阵，矩阵中其 他元素的取值为F_q中的任意值。

（3）将矩阵T中最顶部的52×52子矩阵赋值为单位阵，矩阵中其他元素的取值为F_q中 的任意值。

（4）生成向量S_w,对于S_w=[1,2,…,50,51w,51w+1,…,51w+50]；对于S_w=[1,2,…,50,52w-9,52w-8,…,52w+42]。即，S₁到S₈的长度均为101，而S₉，S₁₀的长 度均为102。

（5）生成50×(50+|S_w|)的矩阵P_w，其中|S_w|表示向量S_w的长度， 即S_w所含的元素个数。针对每个矩阵P_w，将P_w中的第k列赋值为V中的第S_w,k列，S_w,k表 示S_w中的第k个元素的值，各P_w赋值后的结果如图2所示。

（6）操作（6.1）-（6.11）使各P_w满秩化（满秩化后得到的对应的矩阵P'_w如图3所 示）,更新矩阵V'（更新过后的矩阵V'如图4所示），并更新矩阵T（更新过后的矩阵T如 图5所示）。对于P_w，

（6.1）将50×50的矩阵T₁赋值为P_w最右侧的50×50子矩阵。

（6.2）50×50的矩阵T₂等于T₁。

（6.3）seed=Inf，选取Inf为不在rand₂的输出范围中的一个数。

（6.4）如果T₂满秩，则执行操作（6.5）；如果T₂不满秩，执行操作seed=rand₂()， srand₁(seed)，并且对于T₂中的每个元素T₂[i,j]，T₂[i,j]表示 位于T₂中第i行第j列的元素，执行操作T₂[i,j]=T₁[i,j]+rand₁()，该加法是有限域F_q上的加 法，其中，T₁[i,j]表示位于T₁中第i行第j列的元素，最后继续执行操作（6.4）。

（6.5）更新V'。对于将P_w中的第k列赋值给V'中的第S_w,k列； 对于将T₂中的第k-|S_w|+50列赋值给V'中的第S_w,k列。

（6.6）Seed[k]=seed，其中Seed[k]表示Seed中的第k个元素。

（6.7）P'_w是一个50×|S_w|的矩阵。将P_w中的前|S_w|-50列赋值给P'_w的前|S_w|-50列， 将T₂中的50列赋值给P'_w剩下的50列。

（6.8）T₃是一个|S_w|×(|S_w|-50)的矩阵。求解得到中的|S_w|-50个基向量。将T₃中|S_w|-50个列向量赋值为|S_w|-50个基向量。

（6.9）通过高斯消元法（Gaussian elimination）对T₃做列变换，使得T₃的顶部的 (|S_w|-50)×(|S_w|-50)子矩阵成为单位阵。

（6.10）由于512mod10=2≠0，所以只要w≤8，则对T₃做列填充，即，在T₃的最 左侧填充一个全部元素为零的列向量，使得T₃=[0,T₃]，可以从图5中标识“部分1”，“部 分2”的矩阵块从箭头左侧迁移到箭头右侧的情况看出，箭头在右侧的“部分1”，“部分2” 的左边多了一列向量，这列向量即为填充的全0列，而相比之下，标识为“部分10”的矩 阵块就没有做填充。

（6.11）对于将T₃中的第52+w₁行赋值给T中的第(50w+2+w₁)行。

（7）将V'赋值给V，V中的m个行向量构成代。同一代的每个行向量或这些向量的 任意线性组合均称为该代中的数据包。矩阵T的每个列向量或这些向量的任意线性组合均 称为这代数据包的CNK。

由于生成满秩化的数据包矩阵V'（为区别于原来的V，用V'表示）和CNKs构成的矩 阵T的步骤较复杂，在此结合图6-图7、图9的示例图给出较为直观的数值化示例。

在用于说明的数值化示例中选定各参数值q为7，m为2，n为4，u为2。假定经过 映射和划分后得到一代数据中的2个原始数据块分别为：b₁=[1,2,1,5]，b₂=[6,5,0,6]。即 有$B=\left(\begin{array}{cccc}1& 2& 1& 5\\ 6& 5& 0& 6\end{array}\right).$

由B生成以原始数据包为行向量的矩阵V，即，在B前面附加单位阵I_2×2， $v=\left(\begin{array}{cccccc}1& 0& 1& 2& 1& 5\\ 0& 1& 6& 5& 0& 6\end{array}\right),$即有，v₁=[1,0,1,2,1,5]，v₂=[0,1,6,5,0,6]，如图6所示。

将V中的B分成2块，各块在最左边附上I_2×2，则有$P_1=\left(\begin{array}{cccc}1& 0& 1& 2\\ 0& 1& 6& 5\end{array}\right),$$P_2=\left(\begin{array}{cccc}1& 0& 1& 5\\ 0& 1& 0& 6\end{array}\right).$P₁最右侧的2×2子矩阵$\left(\begin{array}{cc}1& 2\\ 6& 5\end{array}\right)$的秩为1（因为(6×2)mod7=5），而P₂最 右侧的2×2子矩阵$\left(\begin{array}{cc}1& 5\\ 0& 6\end{array}\right)$的秩为2，所以需要对P₁的子矩阵进行随机化，即，每个元素加 上一个随机值，以使该子矩阵满秩。

假设用srand₂(0)初始化rand₂后，rand₂()输出的随机数的值为5，用5作为srand₁的 输入以初始化rand₁，假设调用4次rand₁()，输出的4个素数域F₇内的随机数的值为2,3,3,6， 此时最右侧的2×2子矩阵$\left(\begin{array}{cc}3& 5\\ 2& 4\end{array}\right)$的秩为2，即有$P_1^{\prime }=\left(\begin{array}{cccc}1& 0& 3& 5\\ 0& 1& 2& 4\end{array}\right),$记录Seed[1]=5。而由 于P₂最右侧的子矩阵已经满秩，所以有P'₂=P₂，Seed[2]=Inf。合并P'₁与P'₂最左侧的单位 阵，于是有$V^{\prime }=\left(\begin{array}{cccccc}1& 0& 3& 5& 1& 5\\ 0& 1& 2& 4& 0& 6\end{array}\right),$其中，v'₁=[1,0,3,5,1,5]，v'₂=[0,1,2,4,0,6]，如图7 所示。然后，将V'赋值给V。

接下来，生成P'₁与P'₂对应的原零向量构成的矩阵，合并2个矩阵最上侧出现的单位阵 以得到T。可以求得的两个基向量（可由求解线性方程组求得），这两个基向量的一种 取值可以为[1,0,5,1]^T，[0,1,6,2]^T，即可得到P'₁对应的原零向量构成的矩阵为${\left(\begin{array}{cccc}1& 0& 5& 1\\ 0& 1& 6& 2\end{array}\right)}^T,$的两个基向量，这两个基向量的一种取值可以为[1,0,6,0]^T，[0,1,2,1]^T，即可得到P'₂对 应的原零向量构成的矩阵为${\left(\begin{array}{cccc}1& 0& 6& 0\\ 0& 1& 2& 1\end{array}\right)}^T,$合并两个矩阵最上侧的I_2×2则有V的CNKs构成 的矩阵$\mathrm{CK}={\left(\begin{array}{cccccc}1& 0& 5& 1& 6& 0\\ 0& 1& 6& 2& 2& 1\end{array}\right)}^T,$其中，ck₁=[1,0,5,1,6,0]^T，ck₂=[0,1,6,2,2,1]^T，如图9 所示。而如果直接生成未经由满秩化的V的原零向量，则有四个基向量，这四个基向量 的一种取值可以为k₁=[4,5,1,0,0,0]^T，k₂=[2,3,0,1,0,0]^T，k₃=[6,0,0,0,1,0]^T， k₄=[2,1,0,0,0,1]^T，如图8所示。

3.生成CNKs的验证信息。(使用C.Gkantsidis等，文献“Cooperative security for  network coding file distribution”，INFOCOM，2006中提出的方法计算)。

（1）选定一个大素数r，r的长度大于等于1024bit，且使r-1能整除q。

（2）从素数域F_q中随机选定500个数构成1×500的向量g，其中g_k表示g中第k个元 素，k∈{1,…,500}。

（3）对T中每一列列向量求哈希值。具体过程如下：T[i,j]表示位于T中第i行第j列 的元素，h(T_j)表示第j列的哈希值，则h(T)表示T中各列CNK 的哈希值所构成的向量，则有h(T)=[h(T₁),…,h(T₅₂)]。

4.向下游结点分发数据包和验证信息。

（1）首先源结点将参数q，m，n，u，r，函数srand₁，rand₁，向量Seed，g，及 h(T)以广播的形式传播至网络中的所有结点。

（2）接着，源结点对矩阵T进行转置然后，对所有的行向量进行随机线性网络编码 发送给该结点的部分邻居结点（邻居结点的选择由具体路由协议决定）。将矩阵V的所有行 向量进行随机线性网络编码发送给该结点的部分邻居结点。每次传播数据包时随机从F_q中 选取50个数作为编码系数，记作α₁,α₂,…,α₅₀，生成的数据包y为： $y=\underset{i=1}{\overset{50}{\Sigma }}{\alpha }_i{v}_i=[\underset{i=1}{\overset{50}{\Sigma }}{\alpha }_i{v}_{i,1},\underset{i=1}{\overset{50}{\Sigma }}{\alpha }_i{v}_{i,2},...,\underset{i=1}{\overset{50}{\Sigma }}{\alpha }_i{v}_{i,562}]=[{\alpha }_1,{\alpha }_2,...,{\alpha }_{50},\underset{i=1}{\overset{50}{\Sigma }}{\alpha }_i{v}_{i,51},\underset{i=1}{\overset{50}{\Sigma }}{\alpha }_i{v}_{i,52},...,\underset{i=1}{\overset{50}{\Sigma }}{\alpha }_i{v}_{i,562}]$。同理，对CNKs执行的随机线性网络编码操作也一样。

二、中间结点执行的操作。

这类结点主要对收到的包进行检测和编码传输操作，其中，中间结点对收到的数据包 及CNKs分开进行检测和编码。编码传输操作具体指：对收到的数据包（或CNKs）进行随机 线性网络编码操作，得到新的数据包（或CNKs）后传输给其邻居结点。

1.中间结点对收到的包的检测过程如下：

（1）收到的包是CNK，利用同态哈希函数的同态性检测CNK的正确性。检测方法如下： 若此时本结点并无一通过验证的CNK，则直接检测收到的CNK；若本结点已有通过验证的CNK， 则检测该CNK的前52个元素构成的向量和已经过验证的各CNK的前52个元素构成的向量组 的线性相关性，若相关则直接丢弃收到的CNK，若不相关则将该CNK存入缓存。本结点从缓 存中随机抽取一定数量的待验证的CNKs进行随机线性编码产生一个新的CNK，然后对其进 行验证，这个过程称为对缓存内的CNKs的打包验证。从缓存中抽取的CNK的数量由本结点 按安全性需求高低以及自身的计算负载情况设定。该值既可设定为定值，也可动态按需更 新。

具体的验证过程如下：设用τ表示待检测的CNK，τ是一个1×552的行向量。先求h(τ)， 其中h(τ)表示τ的哈希值，τ_52+k表示τ中第52+k个元素。再求 比较两者是否相等，如果相等，则τ通过检测，否则τ是错的。如果检验 不是打包检验，则上述检验过程给出的结果表明接收到的CNKτ是否有差错。否则，上述 检验过程给出的结果若是对的，则所有生成CNKτ的CNKs都是无差错的；若没有通过检验， 则表示生成CNKτ的CNKs中有错的CNKs存在。本结点可根据自身安全性与计算负载情况选 择丢弃本组CNKs，或仍将本组的各CNKs按一定概率保留在缓存以在下次打包检测中检测。

（2）收到的包是数据包，则利用向量的正交性质通过该结点已有的通过检测的CNKs 检测该数据包，若此时本结点并无一通过验证的数据包，则直接验证收到的数据包；若本 结点已有通过验证的数据包，则检测该数据包的前50个元素构成的向量和已通过验证的各 数据包的前50个元素构成的向量组的线性相关性，若相关则直接丢弃收到的数据包；若不 相关再用该结点已通过验证的CNKs检测收到的数据包。如果该结点没有任何通过检测的CNK 存在，则默认该包通过检测。设用y表示该数据包，用CNKs检测的具体操作如下：

（2.1）将用于检测的CNKs解压缩。对于给定的CNK的解压缩如下：根据该CNK，可 得到10个短零向量。ζ_w表示得到的第w个短零向量,由于 512mod10=2≠0，所以如果w≤8，则ζ_w=[τ₁,…，τ₅₁,τ_50w+3,…,τ_50w+52]，否则， ζ_w=[τ₁,…,τ₅₂,τ_50w+3,…,τ_50w+52]。根据上述方法，每个CNK均可解压缩得到10个短零向量。

（2.2）用解压缩得到的每一个短零向量对数据包中部分位置上的元素进行检测，直 至检测出该包是污染包，或该包通过所有短零向量的检测为止，若是污染包则直接丢弃该 包。检测方法如下，若用ζ_w检测y，则计算若该值为0，则y通过ζ_w的 检测，否则y为污染包，其中S_w,k表示S_w中第k个元素的值，yS_w,k表示y中第S_w,k个元素的 值，ζ_w,k表示ζ_w中第k个元素的值。

2.中间结点对正确的数据包及正确的CNKs分别进行随机线性网络编码操作，并将得 到新的数据包和CNKs后传输给其邻居结点。如果本结点有20个通过检测的线性无关的数据 包，记作y₁,y₂,…,y₂₀，则对数据包执行的随机线性网络编码操作类似于源结点，即，随机 从F_q中选取20个数作为编码系数，记作α₁,α₂,…,α₂₀，以生成数据包y，同理， 对CNKs执行的随机线性网络编码操作也一样。

三、宿结点执行的操作。

宿结点除了执行中间结点的操作外，一旦收到50个线性无关的通过检测的数据包，则 进行解码操作以恢复源结点需发给它的数据。解码操作如下：

（1）首先以50个线性无关的通过检测的数据包为行向量构成矩阵，然后对矩阵进行 高斯消元使其最左侧的50×50子矩阵为单位阵。此时的矩阵即是矩阵V（此矩阵是在源结 点操作中1.（7）中的矩阵V）。

（2）而后根据伪随机发生器解码得到矩阵B，具体步骤如下：

（2.1）将矩阵V的右侧50×512子矩阵按列分成10个子矩阵，其中，第w个子矩阵 所包含的列记录在S_w中，即第w个子矩阵共包含|S_w|列，且子矩阵的第k 列是V中的第S_w,k列，对得到的每个子矩阵做操作（2.1.1）和（2.1.2）。

（2.1.1）移除该子矩阵中最左侧的50×50子矩阵。

（2.1.2）如果Seed[w]是Inf，则该子矩阵已处理完毕，得到的矩阵记作B_w；否则， 执行操作srand₁(Seed[w])初始化rand₁，最后，对经过（2.1.1）处理过的子矩阵的最右侧 50×50子矩阵中的每一个元素在F_q上减rand₁()，得到的矩阵记作B_w。

（2.2）通过（2.1）得到的10个子矩阵B_w，可构造出50×512的矩阵B， 即B=[B₁,…,B₁₀]。

（2.3）矩阵B中一共存储了50×512个元素，将各行向量按行的升序排列成一个 1×25600的行向量，将其中前个元素表示的一个q进制的值映射到十进制，记 该值为数据长度，从1×25600的行向量中的第个元素开始，取出数据长度个 元素，将每个元素从q进制映射到一个位的二进制数，这映射得到的数据长度个 位的二进制数即为恢复出的源结点所传输的原始数据。

下面分析恶意结点攻击时可能会执行的操作，并讨论本方案抵抗恶意结点攻击时的安 全性。在有恶意结点时整个方案的运作过程如图11所示，其中的带箭头的直线表示网络中 数据可能出现的流向及经过的操作步骤，箭尾标识出了数据可能流出的操作步骤，箭头标 识出了数据可能流入的操作步骤。

恶意结点除了具有一般中间结点或宿结点的操作外，这类还具有构造并传播污染包的 操作。为便于读者理解，下面将结合图6-图9的数值示例和图10的网络拓扑示例直观地介 绍结点恶意结点通过以下三种攻击方法中最有可能造成污染的方法构造污染包并传播污染 包的操作过程。

在图10中，圆圈表示结点，直线表示链路，其上的箭头方向表示数据的传输方向。s 是源结点，结点1和结点2是恶意结点，结点3和结点4是中间结点。结点r₁和r₂是宿结点。

在此，假定结点1和结点2在此示例中仍会传输正确的零向量。其仍会正确传输零向量 的假定主要建立在先前提到的零向量的传输不被截断的假定之上，在本方案的实际使用过 程中，恶意结点可以不传输零向量，也可以传输篡改过的零向量，其中，某个零向量是否 被篡改会由同态哈希函数检测，从而能很好地保证零向量的正确性，而恶意结点不传输零 向量的行为并不会对整个网络中传输零向量的情况产生很大影响，这主要因为其他合法结 点会传输零向量，并且零向量是以网络编码的形式在网络中传输的，有很好的鲁棒性。但 如果在这个简单示例中仍将恶意结点篡改或者蓄意不传输零向量考虑在内，整个示例网络 中的零向量传输就被截断了，即便是数据包都会被截断，而这不是方案所针对的重点，因 此假定结点1和结点2在此示例中仍会传输正确的零向量。

现假定在图10中s发至结点1的数据包为[1,2,0,6,1,3]，CNK（以行向量形式发送）为 [3,1,0,5,6,1]，s发至结点2的数据包为[5,4,2,6,5,0]，CNK为[2,4,6,3,6,4]。由于恶意结点采 取不同的攻击方式构造出的污染包不同，传播的污染包的具体值将在介绍三种攻击方式时 给出。结点1把自己的零向量发至结点3和结点r₁，结点2把自己的零向量发至结点3和结点 r₂。[3,1,0,5,6,1]和[2,4,6,3,6,4]能通过同态哈希检测，因此结点3会对它们随机线性编码得 到一个新的CNK，假定其为[6,3,6,5,0,3]，接着结点3会将新生成的CNK传给结点4，结点4 把自己的零向量发至结点r₁和结点r₂。

1.随机攻击。恶意结点构造污染包时随机选定包中各元素的取值，在示例中各数都 随机生成的包[2,5,0,1,6,4]就属于这一类攻击构造出的数据包。可以证明，在结点存在t个 线性无关的正确CNKs的时候，随机攻击构造出来的污染包成功通过检测的概率至多为 然而，如果使用的是原零向量，那么结点同样存在t个线性无关的正确原零向 量的时候，随机攻击构造出来的污染包成功通过检测的概率为显然在抵抗随机 攻击时，使用CNKs进行验证的安全性不会比使用原零向量进行验证时低。

2.基于零向量攻击。受害者结点上游的恶意结点收集流经自己的CNKs，并与受害者 共享数据流的上下游恶意结点分享CNKs信息，以最大限度地预估受害者结点可能拥有的 CNKs信息，记线性无关的CNKs构成的集合为CK。如果上游的恶意结点共享后的CNKs满 秩，则本攻击退化成随机攻击；否则，恶意结点求取选取其中不属于Π_V的向量作为 污染包，并通过输出链路传播这些污染包。例如，在图10中恶意结点1和2试图污染结点4 （没有选定结点3作为受害者结点的原因是，结点3此时已经达到CNKs满秩，而能够证明， 在CNKs满秩时只有正确的数据包才能通过所有这些CNKs的检测，结点4此时仅从3处获得 一个CNK，选定结点4作为受害者结点更具普遍性，从而也更能体现本方案的优势），但结 点1和2共享CNKs信息后会发现CNKs满秩，此时本攻击退化成随机攻击。现在考虑在网络 中传输的是原零向量时的情况：现假定在图10中s发至网络的数据包仍旧是图7中v'₁，v'₂的随机线性组合，s仍旧分发2个线性无关的零向量到网络中，假定s发向结点1的原零向 量（以行向量形式发送）为[5,5,2,1,3,6]，s发至结点2的原零向量为[1,1,1,2,1,4]。此时如果 恶意结点1和2构造这两个原零向量的垂直向量空间，就可以在该垂直向量空间找到不属于 数据包空间的向量，例如向量[1,2,0,2,5,4]，如果将这些向量作为污染包，那么整个网络中 将没有结点能检测出它们。如果要避免这种情况出现则需要分发元零向量空间的所有线性 无关的基向量，本发明的方案能使所需要的零向量的量从562×512减小到552×52。如果恶 意结点共享CNKs后，它们的正确的CNKs构成的矩阵记作K_malic，受害者结点拥有的正确的 CNKs构成的矩阵记作K_node，那么与交集空间的基向量个数就为 则该结点能被基于零向量攻击攻击成功的概率至多为 $\frac{q^{562-10(\dim \left(K_{\mathrm{malic}}\right)+\dim \left(K_{\mathrm{node}}\right)-\dim ({\Pi }_{K_{\mathrm{malic}}}\cap {\Pi }_{K_{\mathrm{node}}}))+8}-q^{50}}{q^{562-10\dim \left(K_{\mathrm{malic}}\right)+8}}.$然而，如果使用的是原零向量，那么在与 交集空间的基向量个数同样为的时候，该结点能被基于零向量 攻击攻击成功的概率至多为$\frac{q^{562-\dim \left(K_{\mathrm{malic}}\right)-\dim \left(K_{\mathrm{node}}\right)+\dim ({\Pi }_{K_{\mathrm{malic}}}\cap {\Pi }_{K_{\mathrm{node}}})}-q^{50}}{q^{562-\dim \left(K_{\mathrm{malic}}\right)}},$显然在抵抗基于零向量 攻击时，使用CNKs进行验证的安全性不会比使用原零向量进行验证时低。

3.部分篡改攻击。恶意结点对一个正确包部分位置上的元素进行篡改，其他位置上 的元素保持不变。在示例中，结点2可篡改数据包[5,4,2,6,5,0]第3，第4位上的数据而操 持其他位置上的数据不变从而生成污染包，例如[5,4,1,2,5,0]。篡改的时候可以结合随机攻 击，即，随机选定篡改位置上各元素的取值，也可以结合基于零向量攻击，即，根据共享 的CNKs信息构造篡改位置上的各元素。由于构造CNKs时做过数据填充，可以证明结合随 机攻击时篡改位于S_w,w∈{1,2,…,8}中的元素所指示的位置上的数据成功攻击的概率会比 随意篡改或篡改S_w,w∈{9,10}中的元素所指示的位置上的数据高，而结合基于零向量攻击 时两者成功攻击的概率是一样的，具体如下：

（1）结合随机攻击。可以证明，在结点存在t个线性无关的正确CNKs的时候，恶意 结点篡改S_w,w∈{1,2,…,8}中所示的数据以构造污染包时（假设篡改了8个可能的S_w中的l 个，被篡改的S_w的下标w记在集合W中），则该污染包能通过检测的概率至多为 而如果恶意结点仅篡改S_w,w∈{9,10}中所示的数据以构造污染包时（假设篡 改了2个可能的S_w中的e个，被篡改的S_w的下标w记在集合E中），则该污染包能通过检 测的概率至多为而如果恶意结点仅随意篡改的话（假设篡改了w∈{1,2,…,8} 中的l个S_w，被篡改的S_w的下标w记在集合W中，篡改了w∈{9,10}中的e个S_w，被篡改 的S_w的下标w记在集合E中），则构造出的污染包能通过检测的概率至多为 因此结合随机攻击的部分篡改攻击在篡改同样个数S_w时，仅篡改位于 S_w,w∈{1,2,…,8}中的元素所指示的位置上的数据成功攻击的概率会比随意篡改或仅篡改 S_w,w∈{9,10}中的元素所指示的位置上的数据高。

（2）结合基于零向量攻击。如果上游的恶意结点共享后的CNKs满秩，则本攻击退化 成（1），即结合随机攻击的部分篡改攻击；否则，恶意结点根据共享的CNKs信息构造篡改 位置上的各元素以获得更高的成功攻击概率。如果恶意结点共享CNKs后，它们的正确的CNKs 构成的矩阵记作K_malic，受害者结点拥有的正确的CNKs构成的矩阵记作K_node，恶意结点用 基于零向量的攻击方法篡改S_w,w∈{1,2,…,8}中所示的数据以构造污染包时（假设篡改了可 能的S_w中的l个，被篡改的S_w的下标w记在集合W中），则该污染包能通过检测的概率至 多为$\frac{q^{(50-(\dim \left(K_{\mathrm{malic}}\right)+\dim \left(K_{\mathrm{node}}\right)-\dim ({\Pi }_{K_{\mathrm{malic}}}\cap {\Pi }_{K_{\mathrm{node}}}))l+2l)}-q^{50}}{q^{(20+2l-\left(\dim \left(k_{\mathrm{malic}}\right)\right)l)}},$而如果恶意结点仅篡改S_w,w∈{9,10}中所示 的数据以构造污染包时（假设篡改了可能的S_w中的e个，被篡改的S_w的下标w记在集合E 中），则该污染包能通过检测的概率至多为$\frac{q^{(50-(\dim \left(K_{\mathrm{malic}}\right)+\dim \left(K_{\mathrm{node}}\right)-\dim ({\Pi }_{K_{\mathrm{malic}}}\cap {\Pi }_{K_{\mathrm{node}}}))e+2e)}-q^{50}}{q^{(50+2e-\dim \left(k_{\mathrm{malic}}\right)e)}},$而如 果恶意结点仅随意篡改的话（假设篡改了S_w,w∈{1,2,…,8}中的l个S_w，被篡改的S_w的下 标w记在集合W中，篡改了w∈{9,10}中的e个S_w，被篡改的S_w的下标w记在集合E中）， 则构造出的污染包能通过检测的概率至多为 $\frac{q^{(50-(\dim \left(K_{\mathrm{malic}}\right)+\dim \left(K_{\mathrm{node}}\right)-\dim ({\Pi }_{K_{\mathrm{malic}}}\cap {\Pi }_{K_{\mathrm{node}}}))l+2l-(\dim \left(K_{\mathrm{malic}}\right)+\dim \left(K_{\mathrm{node}}\right)-\dim ({\Pi }_{K_{\mathrm{malic}}}\cap {\Pi }_{K_{\mathrm{node}}}))e+2e)}-q^{50}}{q^{(50+2l-\left(\dim \left(K_{\mathrm{malic}}\right)\right)l+2e-\dim \left(K_{\mathrm{malic}}\right)e)}}.$因此结合基于零 向量攻击的部分篡改攻击在篡改同样个数S_w时，仅篡改位于S_w,w∈{1,2,…,8}中的元素所 指示的位置上的数据成功攻击的概率和随意篡改或仅篡改S_w,w∈{9,10}中的元素所指示的 位置上的数据的成功攻击的概率是一样的。

然而，如果使用的是原零向量，由于数据包中每个元素都同等地位地参与验证，所以 部分篡改攻击会退化为基于零向量攻击（鉴于基于零向量攻击的成攻击概率比随机攻击的 高），那么在与交集空间的基向量个数同样为的时候，该 结点能被部分篡改攻击成功的概率等于该结点能被基于零向量攻击攻击成功的概率，至多 为显然在抵抗基于零向量攻击时，使用CNKs进行验 证的安全性不会比使用原零向量进行验证时低。