采用无向图 G=(V, E)描述物联网。其中, V用于描述物联网中的节点, 主要包括路由器、交换机以及主机等; E用于描述 V中元素间的连接关系。

为了确保网络顺畅运行, 物联网被分成若干子网。各子网间通过路由器相连, 子网间通过交换机等网络元素相连^[5]。在实际物联网环境下, 物理路径或许有回路存在, 很容易造成网络瘫痪。为了避免此问题的发生, 采用生成树协议(STP)去掉网络中的环, 使部分交换机间的连接断开, 从而确保网络顺畅运行。图1描述的是STP协议网络构成的树状结构。

图1

Fig.1

	Figure Option ViewDownloadNew Window
	图1 物联网无向图Fig.1 Undirected graph of Internet of things

本文算法包括两个层次的拓扑发现, 分别是网络层拓扑发现和链路层拓扑发现, 在发现网络拓扑前, 需要进行真实性检测, 以抵抗路由欺骗攻击, 下面进行详细分析。

路由欺骗攻击会导致下述两种网络拓扑出现改变:

(1)已有链路的更新。在已有链路为更新状态时, 网络中会产生LSPID, 其与已有的LSP相似, 但比已有的LSP数据包要大^[6]。当前若某声明是虚假声明, 那么物联网里的真实源路由器会对虚假讯息进行抵抗, 产生序列号慢慢递增的冲突路由讯息。

(2)已有链路的删除。在对链路实施删除时, 运行SNMP协议的路由器会传输RemainingTime为0的LSP, 表示此链路不可使用, 经过LSPID对已经不可使用的LSP进行标识, 删除有关链路^[7]。若当前声明的已失效链路依然存在, 那么路由器会再次对此链路进行警告。

因此, 能使用PSNP请求向可疑路由信息的源路由器查询, 达到真实性检测的目的。这会导致路由拓扑的数据报文出现改变, 本节利用PSNP请求向源路由器确认, 在物联网无路由欺骗攻击的情况下, 源路由器的回复会与接收的更新报文相同; 否则, 物联网会出现相互冲突的链路状态报文。真实性检测流程如图2所示。

图2

Fig.2

	Figure Option ViewDownloadNew Window
	图2 真实性检测流程图Fig.2 Flow chart of authenticity test

在进行真实性测试时, 在采集数据中包含和当前路由信息集合 A冲突的特征信息U_c的情况下, 认为该路由数据报文存在异常, 需要完成对其的真实性检测。

1.3.1 路由器与交换机的判定

本节采用SNMP管理信息库MIB内的信息对路由器与交换机进行区分, 为网络层拓扑发现提供依据。MIB包括MIB、MIB-Ⅱ 以及Q-Bridge-MIB三大类别, 其中MIB-Ⅱ 是通过MIB转变得到的^[8]。由于当前大部分装置拥有MIB, 因此采用MIB能够实现网络管理。SNMP的MIB信息中共存在10个组, 其中interface 组与IP组是通过网络拓扑发现的。

通常根据interface组中的sysServiecs值判定装置类别, 这里sysServiecs值用 Ss表示。若 Ss=15,通过式(1)可求出 Bi=4,因此可知装置是具备数据转发功能的网络装置, 可初步认为相应装置为路由器。

Ss=∑i=1Bi2i-1(1)

由于某种情况下路由器的 Ss值或许为其他值, 因此只通过interface组中的 Ss值判定装置类别为路由器是不充分的。这时通常需引入IP组中的数据加以辅助^[9]。在MIB的IP组中, 若ipforwording值为1时, 即 If=1。则表明此装置能够实现转发; 若 If=0,则表明此装备无法实现转发。因此若装置为路由器, 则 If值等于1。通过结合 Ss值与 If值就能够实现路由器与交换机的区分^[10]。然而目前存在部分交换机同样能够转发数据, 与路由器一样为网络层装置, 这时根据测试装置能否实现Bridge-MIB对路由器与网络交换机进行区分, 若无法实现, 则认为是路由器; 否则, 认为是交换机。

1.3.2 网络层的拓扑发现算法

完成路由器与交换机的判定后, 就能够实现网络层拓扑发现。路由器的路由表中含有路由信息, 尽管单一路由器对网络层拓扑的表述是局限的, 但把整个网络中各路由器的路由表信息收集在一起就能够得到网络层的全部拓扑结构信息^[11]。该算法的基本思想为:通过 SNMP 协议采集路由器中的路由信息, 并对得到的信息进行分析, 确定网络层中各元素间的连接关系。

SNMP协议拓扑发现算法的具体过程如下:

(1)依据SNMP协议对网络层中的路由器施行判定, 把确定的路由器放置在待发现路由器序列中。

(2)在待发现路由器序列里挑出一个路由器, 将此路由器当成起点。采用SNMP协议查询此时路由器的MIB信息库, 并获取其中的路由器地址表。

(3)找出地址表中最大的IP地址, 并将其当成路由器ID, 把该ID录入至完成访问路由器序列中, 同时把待发现路由器序列中与次路由器接口IP一致的地址去掉^[12]。

(4)访问此时路由器MIB信息库中 ipAddrTable表中的各条记录, 若记录中ipAddrTable等于4, 即I_AT=4, 则说明此路由器与子网直接相连, 对目的IP地址(ipRouteDest)和目的子网掩码(ipRouteMask)进行“ 与” 运算, 获取与其直接连接的子网信息和路由器与子网的连接信息。

(5)若此时路由器MIB信息库中 ipRouteType值为5, 即I_RT=5, 则说明此路由器与子网间接连接, 挑出与此路由器直接连接的 n+1跳路由器(ipRouteNextHop), 同时将其放入待发现路由器序列, 把此时路由器添加至完成发现路由器序列中。

(6)从待发现路由器序列中访问路由器, 并循环步骤(2)~(5), 直到待发现路由器序列为∅。

本节结合网桥转发表和网桥生成树算法实现链路层拓扑发现, 该算法可解决恶劣环境下的拓扑发现问题, 实用性较强。

为了描述链路层拓扑发现算法, 首先给出以下指代描述:用dot1dCompatibleAgents队列描述允许生成树协议的二层设备集合; 用ipSets描述地址空间集合^[13]。SnmpPingPosix函数与SnmpPing函数基本相同, 区别是 SnmpPingPosix函数选用既定OID, 同时通过多线程形式对设备是否兼容SNMP协议进行判断^[14]; 而GatherBridgeInfoAll 函数主要用于对网桥数据进行采集, 可返回IEEE8021D类型的节点。

用hostSets描述网络层拓扑发现算法获取的主机地址集合, 则链路层拓扑发现算法实现过程如下:

(1)对dot1dCompatibleAgents队列与ipSets集合进行初始化处理, 令其为空集; 对链路层拓扑发现地址空间进行读取, 同时将其添加至ipSets。

(2)对集合ipSets和集合hostSets进行交集处理, 将处理结果储存至ipSets。

(3)如果ipSets是空集, 则算法结束; 反之, 通过SnmpPingPosix函数完成对ipSets对象的响应测试, 同时将地址储存至dot1dCompatibleAgents队列。

(4)如果dot1dCompatibleAgents是空集, 则进行步骤(5); 反之, 将dot1dCompatibleAgents的队头QA取出, 通过GatherBridgeInfoAll函数对QA的生成树信息info_stp和地址转发表信息info_stp进行采集, 将得到的节点当成二维链表的纵向节点串接, 将info_stp等链表当成横向节点串接。

(5)对网桥转发二维链表进行分析以求出链接关系, 从网桥生成树链表中两两选择节点, 且需满足下述条件:①属于不同设备; ②指定网桥一致; ③端口可随时执行转发操作; ④两个节点依次归属指定端口与非根桥根端口; ⑤节点链接标志位是0^[15]。

用 P描述非根桥根端口的节点, 用 Q描述剩余节点, 通过查找接口信息链表, 求出定义 PIP地址接口的MAC地址。在 Q的地址转发表链表中获取相应MAC地址的端口; 如果获取成功, 则记录“ 设备、端口-设备、端口” 之间的链接关系; 反之, 通过负数对链接关系进行描述。将 P、 Q两个节点的链接标志位设置为1。

(6)对链接标志位进行复位处理, 再次对生成树信息链表进行分析, 得到满足条件的节点。

(7)算法结束。

实验在物联网环境下进行, 环境为仿真的动态网络, 其节点数量为15个, 图3描述的是其拓扑结构, 所有链路容量都是1.5 Mbit/s, 仿真周期是2 ms。假设所有节点均依据泊松分布形成数据包, 平均大小是1024 B。

图3

Fig.3

	Figure Option ViewDownloadNew Window
	图3 实验网络拓扑结构Fig.3 Topological structure of experimental network

形成拓扑结构后, 利用路由器模拟软件伪造链路7和链路16的失效报文, 分别采用本文算法、广度优先遍历算法和子树交汇算法发现网络拓扑, 得到的结果如图4所示。

图4

Fig.4

	Figure Option ViewDownloadNew Window
	图4 三种算法的拓扑发现结果Fig.4 Topology discovery results of three algorithms

分析图4可知, 广度优先遍历算法将链路7删除, 子树交汇算法将链路7和链路16全部删除, 只有本文算法未删除链路7和链路16, 这是因为本文算法对链路删除报文进行真实性验证, 在验证过程中接收源路由器对链路7和链路16的存在性判断结果, 使得路由欺骗攻击想要删除的链路得以保留, 说明本文算法能够抵抗路由欺骗攻击。

一种有效的网络拓扑发现算法不仅要保证网络的安全性, 还需在性能上体现高优越性。本节将发现时间、初始化时间、平均占用网络带宽、发现率、适应能力作为指标, 将广度优先遍历算法和子树交汇算法作为对比, 对本文算法性能进行验证, 结果如表1所示。

表1

Table 1

表1(Table 1)

表1 三种算法的性能比较 Table 1 Performance comparison of three algorithms 指 标 本文算法 广度优先 遍历算法 子树交 汇算法 发现时间/s 0.92 1.37 1.95 初始化时间/s 3.15 6.98 7.32 平均占用网络带宽/unit 202.3 236.87 221.07 发现率/% 98.25 91.33 86.52 适应能力 高 中 低

表1 三种算法的性能比较 Table 1 Performance comparison of three algorithms

分析表1可知, 本文算法的发现时间和初始化时间分别为0.92 s和3.15 s, 与广度优先遍历算法、子树交汇算法相比明显更低, 说明本文算法发现效率高。本文算法适应能力也优于广度优先遍历算法和子树交汇算法, 说明本文算法适应能力强。除此之外, 本文算法平均占用网络带宽更低, 发现率更高。综合上述分析可知, 本文算法具有发现效率高、适应能力强、节省资源的特性, 整体性能优越。