XSeluge:一个基于网络编码的安全在线代码分发算法*

谢满德，张国萍

（1.浙江工商大学计算机与信息工程学院 杭州 310018；2.浙江理工大学信息电子学院 杭州310018）

1 引言

无线传感器网络（wireless sensor network,WSN）是由部署在监测区域内部或附近的大量廉价的、具有通信、感测及计算能力的微型传感器节点通过自组织构成的智能测控网络，是近年来兴起的新型网络。其在国防军事、农业、环境监测、生态保护、医疗卫生、工业、智能交通、建筑物监测、空间探索等领域有着广阔的应用前景和巨大的应用价值，被认为是未来改变世界的10大技术之一。无线传感器网络应用的特点决定了传感器节点一旦部署完毕通常将会长期工作于无人看守的环境中。随着时间的推移,经常需要增加一些功能或者修复软件中存在的问题,这就需要对整个网络进行重编程。在一些网络规模较大或者是节点部署环境较恶劣的情况下，如深海、核辐射区、沙漠等，人工手动地对所有节点编程将是一项非常耗时、耗力甚至是不可能完成的任务。因此在WSN中需要一种机制能够通过无线的方式远程对节点软件进行更新。WSN在线代码分发（online code dissemination）技术（又称网络重编程（network reprogramming）技术）就是一种有效的解决途径。WSN在线代码分发是在传感器网络首次部署完成后对其进行远程任务再分配、节点软件更新和网络功能再配置的过程。由于WSN的无线特性，使得其在线代码分发技术迥异于有线网络，其相关算法研究面临着巨大的挑战，尤其是安全和节能方面更是受到了国内外众多学者的广泛关注，并迅速成为了业内研究的热点。

2 相关工作

Culler等[1]提出的增量式多跳代码分发算法Deluge，是早期代码分发算法的代表。其很多思想，比如对更新程序进行分页、分组处理的策略，页按序传输、页内数据分组允许乱序传输，通过NACK请求数据分组以及Advertise-Request-Update的3步工作过程等思想被后面的算法所广泛采用。然而，Deluge没有考虑任何安全方面的问题。为此，很多基于Deluge框架的、考虑抗多种攻击的安全在线代码分发算法被提了出来。Lanigan等[2]在WSN中最先提出了网络代码分发安全认证方案Sluice。Sluice利用散列函数的单向性来确保更新代码的完整性和正确性，利用数字签名来认证更新代码的合法性。Sluice能一定程度上防御网络中节点被俘获的内部攻击，某种程度上，满足了WSN的特点。但是，由于Sluice方案采用粗粒度的“页级”散列方法，认证失败后将被迫重传整个页。Dutta等[3]提出了与Sluice类似的代码分发安全认证方案。不同于Sluice方案，Dutta等采用了细粒度的“分组级”散列。然而Dutta要求数据分组必须有序到达。但是，WSN中分组丢失和分组乱序到达却是一种常见现象。Deng等[4]针对这种分组的乱序到达问题，提出了一个基于散列树的代码分发安全认证方案。这种方法需要为更新代码这样的大数据对象构建一棵散列树，而且需要保留大量的内存空间来存储树中的节点值。更重要的是这种方法为了保证散列树的正确传输，要求对其逐层传输，所以它们没有完全解决分组的乱序到达问题。虽然这些文献没有完全解决代码分发中的安全问题，但是他们却反映了安全代码分发的演变过程，很多思想在随后的研究中包括本文所广为采用，比如代码映像分发前的预处理思想和分发框架。

[6～11]针对代码分发中的DoS（deny of service）攻击提出了多种解决方法。Park等[5]提出了一个应用增补散列的方法来增强无线传感器网络代码分发的安全性，然而它增大了通信负载，且只部分解决了时延认证问题。Shaheen等[6]提出了一个利用单向密钥链来对更新程序进行加密的代码分发协议，然而该算法只能处理单跳的代码分发，另外算法易受多种DoS攻击。Dong等[7]针对基于数字签名的DoS攻击，提出了基于群和基于密钥链的两种过滤方法，但是这两种过滤方法都严重依赖于发送者和接收者之间密钥对的建立，而这将引入新的安全风险。Tan等[8]针对WSN中的代码信息可能具有敏感性的特点，提出了同时考虑机密性和抗DoS攻击的多跳代码分发协议。针对代码分发中的DoS攻击，Sangwon等[9,10]提出了一个安全的抗DoS攻击的代码分发算法。算法通过引入Merkle散列树来进行数据分组的即时认证，通过引入MSP（message special puzzle）弱认证机制来防御针对数字签名的DoS攻击。近来也有基于网络编码的在线代码分发算法被提出来[12～14]。Wang[11]和Hou[12]主要是利用网络编码的思想来降低代码分发过程中的能耗和均衡负载。Law[13]和Zhang[14]则进一步考虑了安全性。Law提出了一个安全的无率Deluge算法，算法能有效抵御污染攻击，Zhang在参考文献[10]的基础上提出了一个LR-Seluge算法，算法除了有Seluge的安全属性外，还能有效抵御分组丢失攻击等。参考文献[12～14]与本文最为相关，受益于它们的启发，本文针对在线代码分发设计了一种新的网络编码方案，并提出了一个基于网络编码的安全在线代码分发算法。为了防御DoS攻击，算法在网络编码方案中集成并改进了参考文献[6～11]提出的多种技术，比如计数技术、MSP弱认证机制等。

3 安全在线代码分发算法XSeluge设计

XSeluge以Seluge为安全框架，也采用Advertise-Request-Update的3步工作流程。在进行代码分发之前，发起代码分发的节点（通常是基站）首先对待分发的程序映像进行预处理，然后通过一个数字签名来发起真正的数据传输。在数据传输过程中，节点根据收到的NACK请求，进行编码、发送；节点接收到数据分组后解码，并进行即时的数据分组验证。为了防止恶意节点，故意地反复请求数据分组或多次传送伪造的数据分组，XSeluge引入了计数器机制。接下来将详细介绍XSeluge的几个关键思想。

3.1 代码分发端数据预处理

对代码映像的预处理，XSeluge采用了Seluge[11]方法。为了保证内容的自包含性，这里对代码映像的处理方法进行简要描述。Seluge算法也基于Deluge框架，基站首先将代码映像分成固定大小的页，每一个页进一步被分成固定大小的数据分组。然后基站从最后一个页面开始，通过选定的散列函数计算页内每个数据分组的散列值，不过每个分组的散列值不是内嵌到前一个数据分组，而是内嵌到前一页位置相对应的分组中，如此重复直到第一页，其工作过程如图1所示。当算法处理到第一页的时候，Seluge在第一页所有分组的散列值基础上，建立一个Merkle散列树，其建立过程如图2所示。首先通过联合操作，将固定数量的散列值联合成一个数据分组，并计算该数据分组的散列值。然后，将刚计算出来的散列值，两两联合成一个数据分组，并计算散列值。这个过程不断重复，直到最后只剩一个散列值，将该散列值嵌入到数字签名分组，并通过数字签名分组来发起一次代码分发。如图2所示，将H(Pkt1,1)到H(Pkt1,6)6个散列值联合得到一个数据分组V0,1，其散列值为e1。然后将e1和e2联合，并计算其散列值得到e1～2，这个过程不断重复直到得到e1～8。另外Seluge算法还引入了MSP（message special puzzle）弱认证机制，以避免节点进行无谓的数字签名认证操作，有效防御针对数字签名的DoS攻击。

3.2 编码和发送

为了减少节点传输和接收的数据量，XSeluge引入了网络编码的思想。节点首先对待发送的数据分组进行编码，再发送编码后的数据分组。假定节点的邻居数为n，分别记为：P1,P2,…，Pn，一个待分发的代码页被分成了t个固定大小的数据分组，分别记为：M1,M2,…，Mt。节点引入一个邻居节点表来记录邻居节点的状态，每个邻居在表格中对应一条记录，该记录包含一个长度为t的位向量，其中每一位对应一个消息，如果该邻居没有相应的消息，该位置为1，否则置为0。为了不失一般性，记邻居节点Pi的位向量为：Pi(mi1,mi2,…,mit),mij∈(0,1),i=1,2,…,n,j=1,2,…,t。最终每个节点维护一个表1所示的邻居节点表。初始状态该表为空，当接收到邻居节点的NACK请求后，首先检查该表中是否已经有了对应的记录，如果没有则添加一条记录，如果有则更新相应的记录。

表1 节点维护的邻居记录

基于上述邻居节点表，算法采用XOR的异或网络编码方法。假设d1和d2为待分发的数据分组，异或编码的总体思想是：节点一次发送数据分组d1茌d2，这样有d1数据分组的节点可以通过简单的异或操作d1茌d1茌d2，解码得到d2数据分组，有d2数据分组的节点，则可以通过简单的异或操作d2茌d1茌d2，解码得到d1数据分组。因此，发送一个数据分组，不同的节点能获得不同的数据分组，从而在总体上减少数据分组的传送数量。接下来，详细阐述基于上述邻居节点表，怎样确定最佳的异或编码方案。

3.2.1 编码问题建模

为了描述的方便，首先给出以下定义。

定义1 编码方案k，指该编码方案中，参与异或编码的消息个数为k。比如编码方案1指该异或编码方案只选择了1个消息参与编码，编码方案2指该异或编码方案选择了2个消息参与编码，依此类推。编码方案只与选择参与编码的消息个数有关，与消息的顺序无关，因此对于有t个消息的情况，编码方案最多有t种。

论文中引入的其他符号的含义如表2所示。

基于上述定义和符号说明，可以将最优化编码方案的优化目标形式化为：

约束条件为：

在优化目标中，式（1）表示采用编码方案k编码组合s情况下，所有节点能成功解码数据分组的个数；式（2）表示在编码方案k的所有编码组合中，所有节点能成功解码数据分组的最大个数；式（3）表示在所有编码方案中，所有节点能成功解码数据分组的最大个数。因此优化目标可总结为：从所有编码方案的所有编码组合中，找出能成功解码出一个数据分组的节点个数最多的方案。

约束条件中，式（4）是确保在编码方案k中，参与编码的消息分组的个数为k；式（5）是确保如果一个消息分组已经被所有节点成功接收，则不参与编码；式（6）指出节点能成功解码一个消息分组的条件之一是该消息分组已经被当前编码方案选中，而且是该节点目前所没有接收到的消息；式（7）指出节点能成功解码一个消息分组的另一个条件是被选中参与编码的消息分组只有一个还没有被成功接收，否则根据异或编码理论节点就不能正确接受该消息；式（8）是确保任何节点最多能成功解码一个消息分组，因为根据异或编码的原理，一个节点一次最多能成功解码一个数据分组。

3.2.2 编码问题复杂度

朴素的搜索最优编码方案的方法为枚举法，即搜索所有可能编码方案的所有可能编码组合。如上所述，编码方案1的可能编码组合数为，编码方案2的可能编码组合数为，以此类推，编码方案k的可能编码组合数为。因此，总的编码组合数为：

其中t为待分发代码页的数据分组数，在进行代码分发之前，就是一个确定的常量，因此，该问题是一个P问题。

3.2.3 问题样例

假设节点的当前邻居表快照如表3所示，采用的编码方案为3。根据式（4），可以设定编码方案3的第一种的编码组合为向量X13=[0 1 0 1 1]，也就是消 息 M2，M4，M5参与编码。根据式（6）和（7），可以获得如表4所示的各邻居节点成功解码的消息。根据式（8），在表3所示的快照情况下，M3不可能参与编码，因为其已经被所有节点全部接收。根据表4，可以计算出Y13=2。由于不能参与编码，所以==4。在 X23=[1 0 0 1 1]，X33=[1 1 0 1 0]，X43=[1 1 0 0 1]情况下，可以分别计算出：Y23=2，Y33=2，Y43=2。因此，Y3=2。按照同样的方法可计算出Y2=5，Y4=0，Y2=5对应的编码组合为X12=[1 1 0 0 0]，这就是对应表3所示邻居表快照的最优编码方案。

表3 邻居表快照

3.3 解码和验证

由于安全框架基本沿用了Seluge，所以除了需要无缝地集成数据分组解码操作以外，整体的数据分组验证流程基本与Seluge相似。源节点通过一个包含了Merkle散列树根节点的数字签名分组来发起代码分发。之后，源节点首先传输第一个页面所有数据分组的散列值，为了保证每个数据分组散列值能得到即时验证，如图2所示，算法每次传输Merkle散列树的叶子节点V0，i和该叶子节点到根节点路径上每层的兄弟节点。当收到一个数据分组，验证时只需从Merkle散列树的叶子节点开始计算散列值，再结合同层的兄弟节点不断进行散列值计算，直到树根，最后将计算出来的树根值与数字签名中收到的该值进行比较，即可进行认证。例如传输V0，1时，传输的数据分组是：V0，1||e2||e3～4||e5～8。当节点收到数据分组时，依次计算各散列值：e1=Hash(V0，1),e1～2=Hash(e1||e2),e1～4=Hash(e1～2||e3～4)，e1～8=Hash(e1～4||e5～8)，e1～8就是散列树的根节点，只要比较它与通过数字签名分组收到的值是否一致就可以了。通过这种方法可以保证第一个代码页所有数据分组的值都能正确验证。

表4 对应表3的成功解码

在接下来传输第一个代码页中的数据分组时，传输节点在最优编码方案确定后，将参与编码的数据分组编号进行MAC保护后，连接到异或编码后的数据分组末尾。节点接收到数据分组后，首先解析出参与编码的数据分组编号，再进行异或解码得到数据分组。由于数据分组的散列值都已经事先正确接收，所以第一个代码页的所有数据分组都能得到即时的验证。依次类推，由于代码页按序传输，所以在传输Pagei时，页Pagei-1必定已经可靠接收。在传输Pagei时，任何一个数据分组设其为Pkti,k接收后，可以通过判断H(Pkti,k)是否与存储在页Pagei-1第k个数据分组中的该值相等来验证。扩展后的邻居表见表5。

表5 扩展后的邻居表

3.4 防DoS攻击的计数器设计

代码分发过程中，如果存在恶意节点，不断地重复向某个节点请求数据分组，或不断地向其他节点分发伪造的数据分组，则节点能量将很快耗尽，将不能工作。针对这种类型的攻击，算法引入了计数器的方法。算法首先在3.2节的邻居表的基础上，额外引入了两个域SC和RC分别表示向对应的邻居节点发送消息的个数和从对应邻居节点接收消息的个数，如果SC或RC超过了某个阈值，则将该节点标记为恶意节点，将其阻塞一段时间，在这段时间都不向该节点发送消息或接收消息，该方法只是在原有邻居表的基础上添加了两个域，因此具有较小的开销。

4 实验结果

本文通过MATLAB对算法进行了仿真，以验证算法的性能。安全方面，像上面分析的一样，算法能进行即时的数据分组验证，从而能有效防御基于时延的DoS攻击；通过引入MSP弱认证机制，能有效防御针对数字签名的DoS攻击；通过引入接收和发送计数器，能有效防御基于重复请求的DoS攻击。由于基于Seluge安全框架，所以安全性能基本与Seluge相似，不需要通过实验进一步验证。接下来，将主要验证编码方法的有效性。

为了进行有效性比较，本实验中，引入了另外两个算法：一个是没有采用任何编码策略的代码分发算法，简称为Dissem_WC；一个是采用随机编码策略的代码分发算法，简称为Dissem_RC；主要测试了两个性能指标：一个是在一个时间槽内，随节点总数的变化，接收到一个新数据分组的实际节点数，一个是随着代码映像尺寸的变化，完成整个代码分发需要传送的总的数据分组数。在第一个实验中，假定每个数据分组的负载为102 byte（满足IEEE 802.15.4规范），总的数据分组数为60个（代码映像总共被分成了10个代码页，每个代码页进一步被分成了6个数据分组），假设每个时间槽内，节点数在10～45范围变化。进一步，为了模拟无线数据传输的不可靠性，假定传输过程中分组丢失的概率为20%。实验结果如图3所示。XSeluge具有最好的性能，远远高于Dissem_RC和Dissem_WC，Dissem_RC 次之，Dissem_WC 最差。

第二个实验中，假定节点个数为20个，同样为了模拟通信的不可靠性，假定分组丢失率为20%，待传送的代码映像数据分组在60～100 byte变化。实验结果如图4所示。XSeluge需要的数据分组最少，远远低于Dissem_RC和Dissem_WC，Dissem_RC次之，Dissem_WC需要的数据最多。

5 结束语

无线传感器网络在线代码分发由于其传输中的无线特性，相关算法的研究面临着巨大的挑战。本论文以Seluge为安全框架，结合XOR网络编码提出了一个安全的在线代码分发算法XSeluge。XSeluge也采用Advertise-Request-Update的3步工作流程。在进行代码分发之前，发起代码分发的节点（通常是基站）首先对待分发的程序映像进行预处理，包括分页、分组以及用于验证的分组散列值计算和放置，然后通过一个数字签名来发起真正的数据传输。在数据传输过程中，节点根据收到的NACK请求，建立邻居节点表，并基于此确定最优的编码方案，以最大化每次能成功解码的数据分组的个数；节点接收到数据分组后解码，通过散列值计算和比较进行即时的数据分组验证。为了防止恶意节点故意地反复请求数据分组或多次传送伪造的数据分组，XSeluge在扩展原有邻居节点表结构的基础上引入了计数器机制。论文最后给出了实验验证。XSeluge安全性能方面与Seluge相似，但是能大大地减少代码分发过程总的数据分组的传输。本文工作中留待解决的两个开放性问题是：更有效的编码方案；在编码方案确定情况下，更多先进安全方案的集成或有针对性的安全方案的提出。这也是下一步工作的方向。

参考文献

1 HuiJW,CullerD.The dynamic behaviorofa data dissemination protocolfor network programming atscale.Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems (SenSys’04),Baltimore,MD,United States,November 2004:81～94

2 Lanigan P E,GandhiR,Narasimhan P.Sluice:secure dissemination ofcode updatesin sensornetworks.IEEE InternationalConference on Distributed Computing Systems(ICDCS’06),Lisbon,Portu2gal,July 2006

3 Dutta P K,Hui J W,Chu D C,et al.Securing the deluge network programming system.Proceedings of the 5th International Conference on Information Processing in SensorNetworks(IPSN’06),Nashville,TN,United States,April 2006:326～333

4 Deng J,Han R,Mishra S.Secure code distribution in dynamically programmable wireless sensor networks.ACM/IEEE Conference on Information Processing in SensorNetworks,Nashville,TN,April 2006:292～300

5 Park K,Lee J H,Kwon T Y,et al.Secure dynamic network reprogramming using supplementary hash in wireless sensor networks.Proceedings of Ubiquitous Intelligence and Computing-4th International Conference(UIC’07),2007:653～662

6 Shaheen J,Ostry D,Sivaraman V,et al.Confidential and secure broadcast in wireless sensor networks.Proceedings of IEEE 18th International Symposium on Personal,Indoor and Mobile Radio Communications(PIMRC’07),Hong Kong,July 2007:653～662

7 Dong Q,Liu D G,Ning P.Pre-authentication filters:providing DoS-resistance for signature-based broadcast authentication in sensor networks.Proceedings of the First ACM Conference on Wireless Network Security （WiSec’08）,New York,NY,USA,March 2008:2～13

8 Tan H L,Ostry D,Zic J,et al.A confidential and DoS-resistant multi-hop code dissemination protocol for wireless sensor networks.Proceedings of the 2nd ACM Conference on Wireless Network Security(WiSec’09),Zurich,Switzerland,March 2009:245～252

9 Hyun S W,Ning P,Liu A,et al.Du.Seluge:secure and DoS-resistant code dissemination in wireless sensor networks.Proceedings of the 5th International Conference on Information Processing in Sensor Networks(IPSN’08),St Louis,MO,United States,April 2008:445～456

10 Ning P,Liu A,Du W L.Mitigating DoS attacks against broadcast authentication in wireless sensor networks.ACM Trans Sen Netw,2008,4(1):1～35

11 Wag X M,Wang J P,Xu Y L.Data dissemination in wireless sensor networks with network coding.EURASIP Journal on Wireless Communications and Networking,2010，27（3）:1～14

12 Hou I H,Tsai Y,Tarek F A,et al,AdapCode:adaptive network coding for code updates in wireless sensor networks(INFOCOM 2008),Phoenix,AZ,United States,April 2008:2189～2197

13 Law Y W,Zhang Y,Jin J,et al.Secure rateless deluge:pollution-resistant reprogramming and data dissemination for wireless sensor networks.EURASIP Journalon Wireless Communications and Networking,2011(5):1～22

14 Zhang R,Zhang Y C.LR-Seluge:loss-resilient and secure code dissemination in wireless sensor networks.Proceedings of 31st International Conference on Distributed Computing Systems (ICDCS 2011),Minneapolis,MN,United States,June 2011:497～506