AODV协议是 MANET中的一种响应路由协议，主要由UDP或者IP协议传输的路由请求(RREQ)、路由回复(RREP)和路由错误(RERR)这3种分组中各个数据段的定义和变化来实现路由发现和路由维护等功能。

RREQ分组的结构为${P_{\rm {REQ}}} = ( T,h\left( v \right),{\rm {ID}},{{\rm IP}_D},$${{\rm Seq}_D},{{\rm IP}_S},{{\rm Seq}_S})$，$T = 1$用于指示分组类型RREQ；$h = h\left( v \right)$表示从源节点$S$开始跳转至本节点$v$的跳数(hops)；$\rm ID$是本次路由请求的标识，与源节点地址${{\rm IP}_S}$共同唯一确定一个路由请求；${{\rm IP}_D}$表示目的节点地址；${{\rm Seq}_D}$和${{\rm Seq}_S}$分别表示目的节点序列号以及源节点序列号。

RREP分组的结构为${P_{\rm REP}} = ( T,h\left( v \right),{{\rm IP}_D},{{\rm Seq}_D},$${{\rm IP}_S},{\rm TTL})$，$T = 2$表示分组类型；$\rm TTL$表示本次路由回复分组的生存时间。

RERR分组的结构为${P_{\rm {RER}}} = ( {T,{{\rm IP}_{{\rm {UR}_1}}},{\rm {Seq}_{{\rm {UR}_1}}}} )$，$T = 3$表示分组类型；${{\rm IP}_{{\rm UR}_1}},{\rm {Seq}_{{\rm {UR}_1}}}$分别表示不可达节点的地址和序列号。

AODV协议机制分为两个工作阶段。首先是路由发现阶段，源节点通过发送用于请求连接的RREQ分组和接收用于响应连接请求的RREP分组来确定路由连接链路；第二个阶段是路由维护阶段，这个阶段中通过发送RERR分组来广播失效或者堵塞的节点以避免之后的路由寻找、查询或者使用这些“坏”节点。

AODV协议的路由发现过程是：源节点广播RREQ分组，中间节点接收此分组之后查询到达目的节点的下一跳路由链路；若中间节点也没有到下一跳节点的路由链路则将RREQ分组中的跳数加一并继续广播该分组；若中间节点存在到达目的节点的路由，则将RREQ分组转发至能够到达目的节点的下一跳路由节点；所有网络节点如此接续，寻求从源节点到目的节点的路由；参与路由的全体中间节点同时更新自己的路由表条目，该条目将用于建立反向路径并通过这条反向路径重播RREQ分组；目标节点在接收到RREQ分组之后，使用反向路径将自身序列号加一，然后建立RREP分组，返回至源节点。

当源节点同时收到多个RREP分组时，它会选择目的序列号最高的分组来更新自己的路由表。

常规AODV协议既不存在对发送分组的保护机制，也不存在对传输与接收分组的节点身份的安全保护机制。如果网络中间节点被劫持或者网络被渗入攻击性的中间节点，则所有这些恶意节点可以以窃听、欺骗、修改数据分组等方式来实现对AODV协议以致对网络的攻击。

黑洞攻击是指恶意节点通过使用具有更高序列号的路由回复分组对源节点进行欺骗，可将整条路由导向自己，并将路由连接之后的数据分组实施丢弃处理，它是一种欺骗攻击，造成的后果是丢弃所有接收到的传输数据。

采取丢弃策略的黑洞攻击过程细节可描述如下。

1)源节点$S$广播RREQ，即：$S \to *:{P_{\rm REQ}}\! =\! $$( T,h\left(\! V \right),{\rm ID},{{\rm IP}_D},{{\rm Seq}_D},{{\rm IP}_S},{{\rm Seq}_S})$。

2)恶意节点$M$收到RREQ并通过更改RREP分组中的序列号字段，回复一个更高目的序列号的RREP至源节点，即：

3)源节点$S$忽略接收到的其它RREP，建立起与恶意节点的连接并进行载荷消息$P$的传输，即：$S \to M:P = {\rm {Message}}$。

4)恶意节点$M$丢弃所有接收到的载荷消息$P$，即$M:{\rm drop}{\rm{ }}P$。

由此过程可知，针对AODV协议的黑洞攻击能够成功的前提是AODV协议没有有效的节点认证机制。即源(或发送)节点在广播机制下无法指证目的(或某个接收)节点的合法性，或者在获得一个RREP分组时没有机制去认证此RREP分组的来源合法性。

递归函数$F$是一个二元组$F = \left( {f,\sigma } \right)$，记$\sigma \left( n \right)$为递归函数$f$在第$n$时刻(或者时序或者计数序)的状态或者递归输出，则：

递归函数$f$可逆，是指$\sigma \left( n \right) = {f^{ - d}}\left[ {\sigma \left( {n + d} \right)} \right]$，$n,d \in \mathbb{N} $。

线性反馈移位寄存器(linear feedback shift register, LFSR)是一类简单的递归函数，由一个$n$级移位寄存器和一组线性组合逻辑电路构成，电路结构如图1所示。

图  1  LFSR结构

由图1结构产生的LFSR序列为$\left( {{a_k}} \right) = \left( {{Q^{\left( n \right)}}} \right) = $$ \left( {{x_0}\left( k \right)} \right),k \geqslant 0$；LFSR由当前状态(或者第$k$状态) $\left( {{x_0},{x_1}, \cdots ,{x_{n - 1}}} \right) = \left( {{x_0}\left( k \right),{x_1}\left( k \right), \cdots ,{x_{n - 1}}\left( k \right)} \right)$转移至下一个状态(或者第$k + 1$状态)$\left( {{{x'}_0},{{x'}_1}, \cdots ,{{x'}_{n - 1}}} \right) =$$ \left( {{x_0}\left( {k + 1} \right),{x_1}\left( {k + 1} \right), \cdots ,{x_{n - 1}}\left( {k + 1} \right)} \right)$的状态转移关系为：

式中，${x_n} = f\left( {{x_0},{x_1}, \cdots ,{x_{n - 1}}} \right) = \displaystyle\sum\limits_{j = 0}^{n - 1} {{c_j} {x_j}} $称为LFSR的连接反馈函数；$g\left( x \right) = \displaystyle\sum\limits_{j = 0}^{n - 1} {{c_j} {x^j}} $称为LFSR的连接反馈多项式。

当$n$级LFSR序列具有最大周期${2^n} - 1$时，称该序列为m序列。

线性复杂度是任意序列安全性的最基本度量指标，表示采用线性移位寄存器结构的序列发生器去重构或者复现一个给定序列所需要的最小级数或连接反馈多项式的最小阶数^[19]。例如，一个$n$级m 序列的线性复杂度恰为$n$。

如果一个序列的线性复杂度为$L$，则只需知道该序列的任意$2L$个连续元素，即可通过解线性方程组或借助 B-M 算法找到该序列所满足的连接反馈多项式，进而可确定整个序列^[19]。

通常无线网络节点(即路由中的节点总数)跳数不超过16，所以即使采用m序列，只要其反映状态转移关系安全性的线性复杂度大于认证链上的节点数的两倍，就可以保障有相应序列确立的路由节点之间的关联关系，从而提供可信赖的安全可认证性。

在节点集合$V$和链(边)集合$E$确定的网络$\left( {V,E} \right)$中，一条$N$长的路由$R$是一个可连接$N$个网络节点$v$(或者$v\left( n \right)$)，或者$N - 1$个接续的节点串$\left( {v\left( n \right),v\left( {n + 1} \right)} \right)$所构成的序列，即：

节点标识${\rm ID} ={\rm ID}\left( v \right)$是赋予节点$v$的某种特定属性或者赋予节点$v$的某种唯一性标识。例如，由互联网IP地址确定的节点标识为${\rm ID} ={\rm ID}\left( v \right) ={ \rm IP}\left( v \right)$。

若节点标识由某种递归函数$F$生成，则称此节点为链标识节点，描述为$v = \left( {F,{\rm ID}\left( v \right)} \right) = \left( {\left( {f,\sigma } \right),{\rm ID}\left( v \right)} \right)$，递归函数状态$\sigma = \sigma \left( v \right)$称为节点状态。

安全链标识节点是指链标识节点的递归函数结构$f$保密且在节点标识和节点状态即$\left( {{\rm ID},\sigma } \right) = \left( {{\rm ID}\left( v \right),\sigma \left( v \right)} \right)$均公开的条件下难以解析其结构$f$。

路由认证的主体可以是网络服务提供者、也可以是用户自己。路由认证的客体(对象)是整个路由的节点串$R$，而非单个节点$v\left( n \right)$，也非节点链路$\left( {v\left( n \right),v\left( {n + 1} \right)} \right)$。由于路由$R$是序列数据结构，所以路由认证一定是一类链型结构的数据认证，或者是对一类数据向量或者数据序列的认证。

根据路由建立的过程，构建认证链是逐个可信节点的认证过程。因而，一种直觉的采用对称密码体制的认证链构建思路是节点链路间认证的级联。但是使用该体制的缺陷在于完成路由认证必然伴随着庞大的传输数据的扩展。

由于递归函数可以建立前后状态之间的唯一关联关系，所以采用安全递归函数结构(由有限个状态值难以重构函数结构)的节点认证所传递的认证数据可以不存在数据扩展。

具有认证功能的分组${P_S}$仍然是链上传输数据的最小数据单元，设计为：

式中，$r = r\left( v \right)$表示在本节点$v$处生成的一个随机数；$A = A\left( v \right)$表示在本节点$v$处生成的节点认证值，它由节点状态$\sigma \left( v \right)$与分组的消息摘要${\rm MD}\left( v \right)$模二加生成，$A\left( v \right) = \sigma \left( v \right) \oplus {\rm MD}\left( v \right)$；$h = h\left( v \right)$为从源节点$S$开始跳转至本节点$v$的跳数，即从源节点开始计算的链长。

本文将$\left( {r\left( v \right),A\left( v \right)} \right)$定义为认证数据分组的认证扩展字段，与标准的AODV协议分组的异同点在于在使用AODV协议分组的基础上，将认证扩展字段扩展到AODV协议分组后面，形成安全路由请求消息分组，即${P_S} = \left( {{P_{\rm REQ}},r\left( v \right),A\left( v \right)} \right)$。本文使用的安全路由请求消息分组如图2所示，其中认证字段类型0xFFFF表示该分组为认证数据分组。安全路由回复和安全路由错误分组格式同理可得。

图  2  安全路由请求消息分组格式

每个节点之间通过线下分配或者其他安全方式共享两个能够生成m序列的参数$\alpha $和$\beta $，由有限域上迹函数描述的m序列${{a}}$为：

式中，级数为$n$的m序列的周期为${2^n} - 1$；生成m序列的本原元$\alpha \in {\rm GF}\left( {{2^n}} \right)$；确定m序列初始状态的任意非零元素$\,\beta \in {\rm GF}\left( {{2^n}} \right)$，$\,\beta \notin 0 $。

源节点$v\left( 0 \right)$建立安全路由请求消息分组$P_S^{\left( 0 \right)} = ( {P_{\rm REQ}^{\left( 0 \right)},r\left( {v\left( 0 \right)} \right),A\left( {v\left( 0 \right)} \right)} )$，分组中，$P_{\rm REQ}^{\left( 0 \right)}$是源节点$v\left( 0 \right)$建立的RREQ分组，格式如4.1小节定义；$r\left( {v\left( 0 \right)} \right)$表示节点$v\left( 0 \right)$产生的随机数；跳数字段初始化为$h\left( {v\left( 0 \right)} \right) = 0$；$ A\left( {v\left( 0 \right)} \right) = \sigma \left( {v\left( 0 \right)} \right) \oplus {\rm MD}\left( {v\left( 0 \right)} \right) ={f^r}\left( 0 \right) \oplus $$ {\rm MD}\left( {v\left( 0 \right)} \right) $为节点$v\left( 0 \right)$计算的节点认证值；本方案中节点状态值$\sigma \left( v \right)$由链生成函数${f^r}\left( x \right)$生成，而链生成函数${f^r}\left( x \right)$由式(3)表示，即$ \sigma \left( v \right) = {f^r}\left( h \right) = ( {\rm {Tr}}\,( {\beta\, {\alpha ^{r + h}}} ),\, $$ {\rm {Tr}}\,( {\beta \,{\alpha ^{r + h + 1}}} ),\, \cdots ,\, {\rm {Tr}}\,( \beta $${\alpha ^{r + h + 31}} ) ) $，是一个32位的二元序列；$\alpha ,\beta $是在4.2小节提前共享的；${\rm MD}\left( {v\left( 0 \right)} \right) = $${\rm Hash}( {P_{\rm REQ}^{\left( 0 \right)}} )$为RREQ分组的消息摘要值，用来保证RREQ分组的完整性。

本文将源节点生成的随机数$r\left( {v\left( 0 \right)} \right)$和节点认证值$A\left( {v\left( 0 \right)} \right)$一起填入安全路由回复消息分组的认证扩展字段中，然后将建立好的安全路由请求消息分组${P_S}^{(0)}$广播出去。

中间节点在接收到安全路由请求消息分组和安全路由回复分组之后分别做出如下操作。

中间节点$v^{\left( * \right)}$接收到安全路由请求分组${P_S}^{\left( * \right)} = ( {P_{\rm REQ}^{\left( * \right)},{r^{\left( * \right)}},{A^{\left( * \right)}}} )$后，进行如下动作：

1)查找路由表，判断是否存在到目的节点$D$的路由，若不存在，则将RREQ分组中的跳数加一，并继续广播安全路由请求消息分组${P_S}^{( * )}$；否则，进行步骤2)。

2)获取并验证安全路由请求分组${P_S}^{\left( * \right)}$，由提前共享的参数计算节点认证值$A'$，判断与分组中的节点认证值${A^{\left( * \right)}}$是否相同，若不相同则丢弃该分组；否则，进行步骤3)。

3)生成新的字段值，计算$h = {h^{( * )}} + 1$；生成新的随机数$r = r\left( v \right)$；计算本节点认证值A，即：

4)节点认证值$A$生成完毕之后，将其和新生成的随机数$r$填入安全路由请求消息的认证扩展字段中，形成新的安全路由请求消息分组${P_S}^{\left( * \right)}$继续向目的地址转发。

当节点$v^{\left( * \right)}$接收到安全路由请求消息分组${P_S}^{\left( * \right)} = ( {P_{\rm REP}^{\left( * \right)},{r^{\left( * \right)}},{A^{\left( * \right)}}} )$后，进行如下动作：

1)节点$v^{\left( * \right)}$根据提前共享的参数计算节点认证值$A'$，判断与分组中的节点认证值${A^{\left( * \right)}}$是否相同，若不相同则丢弃该分组；否则，进行步骤2)。

2)认证成功之后，将RREP分组中的跳数加一并计算新的随机数和节点认证值，生成新的安全路由回复消息分组，沿反向路径转发至源节点。

目的节点$D$收到目的节点地址为${{\rm IP}_D}$的安全路由请求消息分组${P_S}^{\left( * \right)} = ( {P_{\rm REQ}^{\left( * \right)},{r^{\left( * \right)}},{A^{\left( * \right)}}} )$，则获取该分组${P_S}^{\left( * \right)}$，进行如下动作：

1)根据提前共享的参数计算节点认证值$A'$，判断与分组中的节点认证值${A^{\left( * \right)}}$是否相同，若不相同则丢弃该分组；否则，进行步骤2)。

2)认证成功之后，目的节点$D$将自身序列号加一，构建新的安全路由回复消息分组$P_S^{\left( D \right)} =$$ ( {P_{\rm REP}^{\left( D \right)},r\left( {v\left( D \right)} \right),A\left( {v\left( D \right)} \right)} )$，其中新的节点认证值为$A\left( {v\left( D \right)} \right) = \sigma \left( {v\left( D \right)} \right) \oplus {\rm MD}\left( {v\left( D \right)} \right) = {f^r}\left( 0 \right) \oplus {\rm MD}\left( {v\left( D \right)} \right) $。

攻击者主要有两种攻击方式：1) 修改分组中的某些字段试图获取发送方信任；2) 窃听分组中的节点认证值$A$，试图反推出递归函数结构$f$。

对于攻击方式1)，本文设计的安全认证分组由消息摘要来保护消息的完整性，一旦攻击者更改数据分组，则无法通过消息摘要的验证，另一方面，若攻击者将修改后的分组生成消息摘要，但是由于攻击者不具备生成节点状态值的共享参数，无法获得正确的节点认证值，则无法通过合法节点的认证，从而无法实施黑洞攻击。

对于攻击方式2)，假设攻击者通过窃听获取了所有节点的节点认证值，并通过计算消息摘要得到了所有的节点状态值，但是，本文在方案中加入了随机数，使得在路由中传输的节点认证值所包含的节点状态值不会是连续的，根据2.2小节的描述，只要攻击者无法获取线性复杂度两倍以上的序列的连续状态值，则无法解构递归函数结构$f$，从而无法得到合理的节点状态值从而欺骗合法节点。

综上所述，本文的方案能够抵御AODV路由协议中的黑洞攻击。

本文提出了基于认证链机制的路由认证来完成对AODV路由协议中黑洞攻击的抵抗，在分析了AODV协议的基础上，建立了路由认证的数学模型并实现了路由认证的目标。进一步地，本文修订了AODV的路由发现机制，提出了一种用于AODV的路由认证链方法，实现了MANET中的路由保护，本路由认证方案使得黑洞节点无法得到安全链标识节点的信任，从而无法实施攻击。由于黑洞攻击节点无法获取线性复杂度两倍以上的伪随机序列的连续状态值，因而不能实现依赖状态转移的欺骗。所以，本文方案在路由发现和数据传输阶段都能够很好地抵抗黑洞攻击，同时，认证传输数据量没有随着路由节点的增多而增加，对协议本身只做出小的扩展，所以更容易部署。