过去十年，路由器的容量和性能有了长足的发展[1-2]，其分析模型也有了很大进步[3-4]。可编程路由器正不断涌现[5]，并更加容易部署在新型网络拓扑中，但同时也伴随着安全隐患增加的风险。
最近几年，运行软件部署分组处理功能的路由器越来越容易受到攻击[6-12]。例如，思科路由器被报道发现了设备后门[13-14]，引起了政府部门和运营商很大关注。即使在路由器中所有模块和模块的调用被确认是正常的，模块也会被用来完成不期望的行为。例如，黑客能够获取管理权来操纵路由器行为或通过更新模块来改变路由器行为[15]。
以往的工作专注于代码安全和加密技术[16-17, 20]，用来促进路由器行为可信性。Dobrescu等提出了静态验证工具来检查软件数据层的安全隐患[16]。本文的范式路由器也是检查工具，但检查的是动态运行的数据层行为。Kim等使用源认证和路径验证来预防路由器的异常行为[17]。密钥算法需要部署代价和验证算法，对于路由器和端主机都要修改，成本较高，本文的范式路由器没有加密机制。
本文设计了在高速运行的路由器动态数据层之上，实时验证路由器行为的验证框架。首先，设计了验证局部构件取代了验证整体行为的思想，具有很高的性能优势。其次，使用集合和图论相关方法优化了验证思想，使得验证更加有效。然后，设计了位图的查找结构，占用了很少的存储容量。最后，设计了初始化机制，将白名单行为集合转化为范式表。
1 构件和行为的验证思想本文调研了路由器数据层的构件和行为，并且在此观察基础上设计了构件标识(component identifier, CID)和行为标识(action identifier, AID)来描述构件和行为。
1.1 路由器数据层的特点本文专注于软件路由器平台的安全问题。软件路由器平台由丰富的构件构成，本文的构件是数据层的功能模块，具有以下特征：首先，构件是分组相关的处理模块，它直接对分组进行操作；其次，它是在动态运行数据层的实时处理单元。因此一个行为被看做是构件的管道线。
通过调查Click路由器数据层的构件，本文将2类处理单元视为构件：一类是其成员函数对分组进行操作的元素，另一类是Packet类里的所有成员函数。通过运行TCP(transmission control protocol)和UDP(user datagram protocol)2个协议，从构件调用关系、构件特点、路由器行为特点3个方面观察了路由器行为，得到如下结论：1)路由器行为的最后一个构件必定是SendPacket或KillPacket，2)路由器数据层在运行时并不会调用很多构件，3)规范的路由器行为的集合仅仅是所有构件的组合的一小部分，4)一个行为内的构件数很少。
1.2 CTAG和WAID设计本文用CID来标识构件，用AID来标识行为。因为二进制数占用空间少并且可以快速计算查找，基于节1.1的调研，本文使用8位二进制数描述CID、构件权重(component weight，CW)、边权重(edge weight，EW)和行为权重(action weight，AW)。图 1为CTAG(component tag)和带有权重的AID(WAID)的格式。其中：AID是一个行为内调用的所有构件CID的有序序列，AW是一个行为内调用的所有构件的CW和EW之和。
|
| 图 1 CTAG和WAID格式 |
1.3 验证的高效性
AID暗示了CID之间的关系。为了验证当前AID是否是正常行为，本文提出验证两两相邻CID的关系。这样验证的代价比验证整个行为AID的要低。正常的CID-CID关系在RAT(ragulated action table)中作为验证标准。两两验证有效的前提是所有AID满足2个条件：AID内部没有有向环，AID之间没有交互。
1.4 验证的有效性1) 构件和边权重。
当正常AID有交互时，两两验证会失效。例如，2个正常AID分别是4-ABCE1和4-ADCE2，字母代表构件的CID，数字为AW，每个构件CW为1，EW为0。因此AB、BC、CE1和AD、DC、CE2是正常调用关系。但是当恶意行为ABCE2和ADCE1执行时，RAT会通过验证，认为是正常行为。
上述2个行为有相同AW并且他们还有交集(头尾除外)，就叫冲突行为。为解决冲突行为，本文对非共享节点CID修改CW，并将RAT的条目变成AW-CID-CID。在上面的例子中，B、D、E1和E2是非共享CID。通过对非共享的D的CW加1，变为2，则4-ABCE1和5-ADCE2的AW分别变成4和5，2个行为不再冲突。
当冲突的AID完全互相共享构件CID时，仅靠修改非共享节点的CW无法消除冲突行为。本文通过修改非共享边的EW，可以消除冲突行为。原理和使用CW的原理相同。分配权重的方法见节2.4。
引理1 对于带权有向图G，若G中所有的WAID互相不冲突，而且没有环，则带权验证两两关系，就可以确定一个行为的合法性。
证明：如图 2所示带权关系拓扑G，G中的带权行为WAID满足不冲突且无环。G中所有带权有向边构成了集合RAT。使用RAT重新遍历组合成新的所有可能行为，形成拓扑G′。根据构建关系，G′包含G。现在用反证法证明G包含G′。不妨设αw来自G′且从S1开始并在E2结束，且不属于G，将αw分为2段S1-A2和A2-E2，S1-A2属于图中最上面的S1-E1，A2-E2属于S1-E2，由于G无冲突，所以S1-E1和S1-E2有不同的权，即αw有2个不同的权，矛盾。因此G包含G′。最终G=G′。
|
| 图 2 权重的一般性证明 |
2) 正常AID中的环。
当一个行为内部有有向环时，恶意行为仍然可以逃过检查。例如，正常行为6-ABACAE，恶意行为6-ACABAE会逃过检查，因为2个行为边和节点完全共享，AW也相等。
为了解决这个问题，本文提出去除环的方法。首先当拼接CID组成AID时，先检查当前CID是否已经存在于要拼接的AID中。一旦发现同样的CID，就增加当前的CID序号。然后将当前CID加入AID尾部。最终计算行为的AW。这样同一个构件就拥有不同的CID，也就去除了环。上述例子中，去除环以后，最终的行为是6-ADBECG。
可以证明上述去环方法不会产生歧义或重复。上述方法定义为映射f(a)=A，a∈AID，A∈RAID。f定义为从左到右遍历a，当a存在重复节点C1，如…C1…C1…C1…时，f会对重复节点号增加k值，k是重复次数。于是A是…C10…C11…C12…，其中C1j=C1+j，0≤j≤T1，T1是C1在所有行为中的最大重复次数。C10，…，C1T1构成集合γ1。集合γi中，0≤i≤N，N是所有原始行为不同节点的数量，γ0=∅。可以证明当所有集合γi互不相交时，f是可逆映射。证明方法用可逆映射具有单射和满射性质，对于单射：AID不同的编码不同的重复次数会按照f会得到不同的RAID的编码，因为γi互不相交。对于满射，由于因为γi互不相交，对应的原始编码也不相等，故满射成立。证毕。
2 范式路由器设计 2.1 范式路由器架构如图 3所示，本文将验证方法部署在范式路由器，核心结构是集中管理器(centralized manager，CM)，它由5部分构成：Attacher模块是在临时分组头部附加CTAGs到WAID尾部；Ctable存储了所有的CTAGs；RAT是一个位图结构，存储了所有正常的WAID；Checker是检查WAID正确性的函数；Disabler则用来处理恶意行为。
|
| 图 3 范式路由器结构 |
2.2 Attacher和CTable
构件被调用时会把自身的8位CID拼接在分组临时头部的WAID的尾部，这个工作是Attacher完成的。另外，Attacher还有2个任务：一个是8位CW或EW的值加入AW，另一个是检查是同样的CIDs存在于同一个WAID。如果遇到同样的CID，Attacher会执行去除环的操作，最后把增值的CID拼接入WAID。
Ctable用来给每个构件分配CW和CID。CW和CID的值是从正常AID的集合计算出来的。当构件提交自己的信息到CM时，Ctable就会分配对应的CTAG给这个构件。
2.3 验证模块Checker和RATChecker用来验证是否当前AID是正常行为，实现方法见节1.3和1.4。RAT使用位图结构存储和查找目标。RAT的地址形式是AW-CID-CID，长24 b。RAT中的条目占1位，值为1表明正常，值为0是恶意。因此所有RAT占用了224 b即2 MB的空间。RAT在路由器运行时仅仅可读，以此防止被恶意修改。RAT的内容根据正常WAID计算得来。
2.4 Disabler处理恶意行为和生成RATDisabler被放在SendPacket构件。当发现恶意行为时，分组被释放，并记录日志信息。在生成RAT前，对所有构件遍历并递增编码CID，按照管理员定义生成正常AID集合，如图 4左边的AID Set。
|
| 图 4 初始化RAT |
图 4中，对AID集合生成RAID，使用节1.4的方法去除行为中的环。其次基于RAID，使用算法分配CW和EW，生成WRAID。分配算法是图遍历算法，算法目标是为每个CID计算CW和EW。算法遍历RAID所有节点，找到出度大于1的节点，调整合适的CW和EW改变冲突行为的AW直到不冲突。最后，使用WRIAD配置RAT、Ctable和Attacher。
当有新的行为需要更新RAT时，见图 4的步骤4。将新的WRAID恢复重复的CID并去除AW，生成对应的AID。这个步骤是步骤1和2的逆过程，在节1.4中已经证明去环方法可逆。
3 范式路由器的效果评价Click范式路由器部署在64位Ubuntu 12.04版本上，配备8核Intel Core i7-3770 CPU、8 GB DDR3内存和2个100 Mb/s RTL8139以太网适配器。DPDK范式路由器部署在64位Ubuntu 14.04.3版本上，带有8核Intel Core i7-4790K CPU、32 GB DDR3内存和4个Intel I350-T4 Gb/s网卡。
Click和DPDK路由器执行基本的路由功能。在Click路由器的实验中，5 MB和60 kB的数据在2个场景下传输：TCP场景、TCP和UDP混合的场景。在DPDK路由器实验中，路由器直接连接了Spirent TestCenter发包机(packet generator)[18]，发包机使用TCP进行吞吐率测试。
3.1 范式路由器的有效性为了调查Click范式路由器的有效性，本文在转发构件SendPacket中加入了3种恶意调用：复制分组、读取分组和随机丢弃分组(丢包概率为0.1)。每种调用运行在2种传输环境：TCP场景、TCP和UDP混合的场景。本文统计了范式路由器捕获的所有行为的次数。范式路由器对于复制分组和读取分组2个恶意调用的表现相似，故读取分组的图忽略不画。图 5的纵坐标每个值代表 1种行为类型，由于行为功能多样，纵坐标略去行为名称，以数字代表行为，但图 5a和5b的纵坐标不相关。
|
| 图 5 行为时间点 |
在图 5a中，只要正常行为调用了SendPacket构件，就会触发对应的恶意复制行为。在图 5a中0~10 ms，路由器会执行寻找地址等正常行为，这些行为只有少数会调用SendPacket，故触发了少数对应的恶意复制行为。图 5a中，10~50 ms时间内，路由器同一个路径的2个方向分别执行转发行为，对应图下方2种正常行为。它们触发了对应的2种恶意复制行为，对应图上方2种恶意行为。由于恶意复制行为并行于正常行为，它们并不影响正常行为。图 5b中，恶意行为发生的密度较小，因为恶意丢包调用发生的概率是0.1，并且它们会影响正常行为。在图b中，TCP由于重传机制而传输成功而UDP没有传输成功，因此诱发了比图 5a要多的正常行为类型。
3.2 范式路由器的性能对于Click范式路由器，本文使用iperf测量吞吐率[19]。对于DPDK，本文使用Spirent TestCenter发包机，配置TCP协议来测量吞吐率。对于2种路由器，分别都有7个实验：无范式路由器，有范式路由器且恶意行为发生概率分别为0、0.1、0.2、0.3、0.4、0.5。本文得到了恶意行为的归一化数量以及归一化吞吐率，如图 6所示。
|
| 图 6 范式路由器随恶意行为增多时的性能 |
在图 6a中，由范式路由器捕获的恶意行为数量基本正比于恶意行为的发生概率。在Click和DPDK路由器上的恶意行为的最大次数是55 572和38 400。Click部署了范式路由器涉及的构件更多，导致了比DPDK更多的行为。
在图 6b中，归一化的吞吐率会随着恶意行为的增多而轻微减小。主要是因为范式路由器需要将恶意行为信息写入文件，这个I/O操作导致了路由器的性能下降。Click范式路由器的吞吐率被影响的程度比DPDK范式路由器被影响的程度要小。因为Click是100 Mb/s带宽网卡，比DPDK范式路由器的1 Gb/s网卡的带宽要小很多，影响也会较小。Click和DPDK的最小、最大吞吐率分别是92.0、93.1 Mb/s和860.9、940.2 Mb/s。
4 结论本文提出了范式验证机制来保证路由器在动态运行时的行为可信性。基于对路由器数据层的行为的观察，以及恶意行为的特点，设计了一系列方法来监控动态行为。为了降低对转发性能的影响，范式路由器采用了分而治之的验证思想，并使用了位图结构。为了提高验证有效性，范式路由器使用了权重和去除有向环的思想。范式路由器部署在Click和DPDK路由器环境，评价结果显示范式机制在动态数据层捕获了恶意行为，同时也满足了路由器的性能和代价的要求。
| [1] |
YANG T, XIE G G, LI Y B, et al. Guarantee IP lookup performance with FIB explosion[C]//Proceedings of the 2014 ACM SIGCOMM Conference. Chicago, USA: ACM, 2014: 39-50.
|
| [2] |
APPENZELLER G, KESLASSY I, MCKEOWN N. Sizing router buffers[C]//Proceedings of the 2004 ACM SIGCOMM Conference. Portland, USA: ACM, 2004: 281-292.
|
| [3] |
MALTZ D A, XIE G, ZHAN J, et al. Routing design in operational networks: A look from the inside[C]//Proceedings of the 2004 ACM SIGCOMM Conference. Portland, USA: ACM, 2004: 27-40.
|
| [4] |
PAXSON V. End-to-end routing behavior in the Internet[J]. IEEE/ACM Transactions on Networking, 1997, 5(5): 601-615. DOI:10.1109/90.649563 |
| [5] |
XU K, CHEN W L, LIN C, et al. Towards practical reconfigurable router:A software component development approach[J]. IEEE Network, 2014, 28(5): 74-80. DOI:10.1109/MNET.2014.6915443 |
| [6] |
NSA/CSSM 1-52. Prism project[Z/OL]. [2018-01-15]. https://nsa.gov1.info/dni/prism.html.
|
| [7] |
MALTZ D A, ZHAN J, XIE G, et al. Structure preserving anonymization of router configuration data[C]//Proceedings of the 4th ACM SIGCOMM Conference on Internet Measurement. Taormina: ACM, 2004: 239-244.
|
| [8] |
ZHANG Y, PAXSON V. Detecting backdoors[C]//Proceedings of the 9th Conference on USENIX Security Symposium. Denver: USENIX Association Berkeley, 2000: 12-12.
|
| [9] |
SPARKS S, EMBLETON S, ZOU C C. A chipset level network backdoor: Bypassing host-based firewall & IDS[C]//Proceedings of the 4th International Symposium on Information, Computer, and Communications Security. Sydney: ACM, 2009: 125-134.
|
| [10] |
MOJO66. Backdoor found in arcadyan-based Wi-Fi routers[Z/OL]. [2018-01-15]. http://it.slashdot.org/story/12/04/26/1411229/backdoor-found-in-arcadyan-based-wifi-routers.
|
| [11] |
JC. RuggedCom-backdoor accounts in my SCADA network? you don't say…[Z/OL]. [2018-01-15]. http://seclists.org/fulldisclosure/2012/Apr/277.
|
| [12] |
COSTIN A, ZADDACH J, FRANCILLON A, et al. A Large-scale analysis of the security of embedded firmwares[C]//Proceedings of the 23rd USENIX Conference on Security Symposium. San Diego: USENIX Association Berkeley, 2014: 95-110.
|
| [13] |
GOODIN D. Malicious cisco router backdoor found on 79 more devices, 25 in the US[Z/OL]. [2018-01-15]. https://arstechnica.com/information-technology/2015/09/malicious-cisco-router-backdoor-found-on-79-more-devices-25-in-the-us/.
|
| [14] |
GOODIN D. Cisco routers in at least 4 countries infected by highly stealthy backdoor[Z/OL]. [2018-01-15]. https://arstechnica.com/information-technology/2015/09/attackers-install-highly-stealthy-backdoors-in-cisco-routers/.
|
| [15] |
HIGGINS P, KRISHNAN R. DEFCON router hacking contest reveals 15 major vulnerabilities[Z/OL]. [2018-01-15]. https://www.eff.org/ru/node/82002.
|
| [16] |
DOBRESCU M, ARGYRAKI K. Software dataplane verification[C]//Proceedings of the 11th USENIX Conference on Networked Systems Design and Implementation. Seattle: USENIX Association Berkeley, 2014: 101-114.
|
| [17] |
KIM T H, BASESCU C, JIA L, et al. Lightweight source authentication and path validation[C]//ACM SIGCOMM. Chicago: ACM New York, 2014: 271-282.
|
| [18] |
Spirent. Spirent packet generator[Z/OL]. [2018-01-15]. http://www.spirent.com/Products/TestCenter.
|
| [19] |
DUGA J, ELLIOTT S, MAH B A, et al. Iperf[Z/OL]. [2018-01-15]. https://iperf.fr/.
|
| [20] |
ABADI M, BUDIU M, ERLINGSSON U, et al. Control-flow integrity[C]//Proceedings of the 12th ACM Conference on Computer and Communications Security. Alexandria: ACM New York, 2005: 340-353.
|