面向双层传感网的安全Top-k查询协议

马行坡 梁俊斌 马文鹏 李 银 李 然 奎晓燕

1(信阳师范学院计算机与信息技术学院 河南信阳 464000) 2(广西大学计算机与电子信息学院 南宁 530004) 3 (中南大学信息科学与工程学院 长沙 410083) (maxingpo@xynu.edu.cn)

随着电子元件、通信协议等软、硬件技术的发展，物联网正逐渐由概念提出阶段走向实际实现阶段.在层次划分上，物联网可分为感知层、对象抽象层、服务管理层、应用层和商业管理层[1].在这些层次中，感知层负责直接从物理对象获取数据信息，是实现物联网“万物互联”关键环节.目前，物联网的感知系统主要包括：无线传感器网络(wireless sensor networks， WSNs)[2]、双层传感器网络(two-tiered wireless sensor networks，TWSNs)[3-4]、RFID系统[5]、NFC系统[6]等.其中，TWSNs是由WSNs发展而来的一种新型网络系统，它通过将大量的传感器节点进行单元划分并在每个单元内部署资源相对丰富、计算能力相对更强的主管节点(master node)来提高网络的可扩展性，未来将在物联网感知系统中扮演重要角色.

然而，目前有关TWSNs的研究处于起步阶段，仍存在一些问题需要解决，尤其是数据的隐私性和完整性保护问题.在TWSNs中，上层主管节点既负责收集本单元内传感器节点的感知数据，又负责响应来自Sink的查询请求，是TWSNs中的关键节点.因此，在敌对环境中，主管节点易受到攻击而变为恶意节点.一旦主管节点被恶意化，整个网络的数据隐私性和完整性将面临威胁.

本文主要研究在主管节点被攻击者捕获而成为恶意节点的情况下，如何保护Top-k查询处理过程中的数据隐私性以及如何检验Top-k查询结果的真实性和完整性问题，并提出了一种新的安全Top-k查询协议VPP(verifiable privacy-and-integrity preser-vation).基于对称密钥加密技术(symmetric ciphering， SC)[7]、顺序保留加密技术(order preserving encryption scheme， OPES)[8]和数据关联技术，VPP通过在TWSNs各个层次上配置特定的数据处理和检验方法来实现Top-k查询的数据隐私性和完整性保护，这些方法主要包括：传感器节点上的感知数据预处理方法、主管节点上的Top-k查询处理方法以及Sink端(Top-k查询结果接收端)的Top-k查询结果数据完整性检测方法.概括而言，本文的主要贡献有3个方面：

1) 面向TWSNs，提出了一种能够同时实现数据隐私性保护和数据完整性保护的安全Top-k查询处理协议VPP，详细描述了VPP的具体内容，给出了VPP在对Top-k查询结果进行数据完整性验证时所采用的具体检验方法.

2) 理论分析了VPP在Top-k查询的数据隐私性保护和数据完整性保护方面的效果.在传感器节点相对安全而主管节点被恶意化的情况下，证明了VPP能够以100%的概率侦测出不具有数据完整性的Top-k查询结果.

3) 通过大量仿真实验验证了该协议的高效性.实验结果显示，VPP能够显著降低TWSNs中为了提高Top-k查询的安全性而额外增加的通信开销.

1 相关工作

目前，TWSNs中已有的Top-k查询数据隐私性保护方法主要有：基于数字扰动技术的方法[9-10]、基于域分割加密的方法[11]、基于对称密钥直接加密的方法[12]等.其中，基于数字扰动技术的隐私保护方法通过在正常数据中加入干扰数据并结合对称密钥加密技术来实现TWSNs Top-k查询的数据隐私性保护，这种方法需要传感器节点与Sink之间通过主管节点进行多次交互，查询效率较低；基于域分割加密的方法将所有传感器节点产生的感知数据划分到多个阈值区间，并通过将属于同一阈值区间的数据进行加密来实现TWSNs Top-k查询的数据隐私性保护，这种方法缺陷在于难以实现精确Top-k查询；基于对称密钥直接加密的方法则直接利用传感器节点与Sink节点之间共享的对称密钥对传感器节点产生的前k个数据项进行加密，并将所有加密数据通过主管节点发送给Sink.由于当k值较大时需要传输的加密数据项较多，因此，基于对称密钥直接加密的方法主要用于Top-1查询，即最大或最小值查询[12].

TWSNs中Top-k查询的数据完整性保护方法主要包括：基于消息验证码的验证方法[3,13-15]、基于数据项加密链的验证方法[16]、基于顺序号加密的数据完整性验证方法[17]、基于仿造感知数据(dummy readings)的验证方法[18]等.其中，基于消息验证码的方法要求每个数据项都绑定一个消息验证码作为其真实性的验证信息，其主要缺陷是额外增加的通信开销较大；基于数据项加密链的验证方法的核心思想是，将每个数据项与其大小相邻的数据项的一个备份进行加密绑定，从而形成一个加密数据链，Sink节点根据加密链的连贯性是否被破坏来验证Top-k查询结果是否具备数据完整性,这种验证方法需要增加的证据信息量通常大于感知数据项本身的通信开销，额外通信开销也较大；基于顺序号加密的数据完整性验证方法则是通过直接将每个数据项所对应的权重值与其对应的大小顺序号进行直接加密绑定来构建数据关联关系，进而实现Top-k查询的数据完整性保护，然而，这种方法未能实现面向数据项本身的数据隐私性保护；基于仿造感知数据的验证方法要求传感器节点在向数据存储节点发送真实感知数据前向真实感知数据集中加入部分仿造数据，利用数据存储节点不能分辨传感器节点发来的数据报告中数据的真假这一特点来实现Top-k查询的数据完整性保护.根据文献[18]中的实验结果，基于仿造感知数据的验证方法需要牺牲一定的正确验证概率来提高系统的能效性.

综上所述，TWSNs中已有关于Top-k查询的安全性解决方案仍存在不足，尤其是在如何提高Top-k查询结果的正确侦测概率和如何降低因实现Top-k查询的安全性而额外增加的通信开销问题上有较大的研究空间.

2 网络模型与相关定义

2.1 网络模型

TWSNs的网络模型如图1所示.假设网络中共存在N个传感器节点和M个主管节点，则整个TWSNs部署区域被划分为M个单元，第c(1≤c≤M)个单元内部署一个主管节点Hc和Nc(N=N1+N2+…+Nc+…+NM-1+NM)个传感器节点{S1,c,S2,c,…,SN-1,c,SN,c}.Si,c(1≤i≤N,1≤c≤M)可以通过单跳或多跳的方式与Hc进行通信.为便于描述，下文将Si,c简写为Si.令T表示TWSNs的网络生命周期，T被均匀划分为x个大小相等的时隙Tt(1≤t≤x)，即|T|=|T1|+|T2|+…+|Tt|+…+|Tx-1|+|Tx|,且|T1|=|T2|=…=|Tt|=…=|Tx-1|=|Tx|.其中，|Tt|(1≤t≤x)表示时间区间Tt的宽度.在每个时隙结束时，传感器节点将其在本时隙内采集到的感知数据发送给其所在单元内的主管节点.本文假设网络中存在唯一的数据项权重计算函数f(*)[19]且不同感知数据项对应的权重不同,并假设Top-k查询依据数据项对应的权重对数据项进行排序.令Di,j表示Si在Tt内产生的任意数据项，di,j根据表示数据项Di,j对应的权重，则有:

Di,j=f(di,j),

(1)

令μi,t表示Si在Tt内产生的数据项的个数，则Si在Tt内产生的感知数据项集合可表示为{Di,1,Di,2,…,Di,μi,t-1,Di,μi,t}，假设这些数据项所对应的权重满足：

di,1

(2)

Fig. 1 Network model of TWSNs图1 TWSNs网络模型

Sink节点可通过按需无线链路(on demand wireless link， ODWL)[3]向Hc(1≤c≤M)发送查询请求，并从Hc获取查询结果.由于涉及多个单元的复杂Top-k查询可以被分解为多个涉及单个单元的Top-k查询，因此，本文只关注单个单元的Top-k查询.一个Top-k查询原语可表示为

Qt=c,t,k,QS,

(3)

其中，c表示被查询单元的单元号，t表示被查询的时隙序号，k表示被查询节点在第t个时隙内所产生的数据项中所对应的权重最大的数据项的个数，QS表示被查询节点的节点ID号所构成的集合.

同文献[3]，本文重点关注传感器节点相对安全而主管节点被恶意化的情况.在主管节点被恶意化的情况下，主要考虑数据窃取、数据造假、数据丢弃等攻击类型.

2.2 相关定义

定义1. Top-k数据项与非Top-k数据项、Top-k节点与非Top-k节点.给定一个Top-k查询Qt=c,t,k,QS，在QS内在第t个时隙产生的所有数据项中权重最大的前k个数据项为Top-k数据项，其余为非Top-k数据项.在QS内，产生Top-k数据项的节点被称为Top-k节点，其余节点称为非Top-k节点.

定义2. TWSNs中Top-k查询的数据隐私性和完整性.如果被恶意化的主管节点在Top-k查询处理过程中既不能获知传感器节点所产生感知数据的具体数值，又不能获知其对应的权重值，则称这样的Top-k查询处理方式具备数据隐私性；如果Top-k查询结果中包含所有的Top-k数据项且其中所有的数据项都是真实可靠的，则称这样的Top-k查询具有数据完整性.

3 VPP的内容

VPP通过在传感器节点层、主管节点层以及Sink节点上制定特定的数据处理与安全检测方法来实现TWSNs中Top-k查询的数据完整性和隐私性保护，主要包含的方法有：传感器节点上的感知数据预处理方法、主管节点的Top-k查询处理方法和Sink节点的Top-k查询结果数据完整性检验方法.

3.1 传感器节点的数据预处理方法

(4)

1) 如果μi,t=0,有:

(5)

2) 如果μi,t≠0，有:

(6)

3.2 主管节点的Top-k查询处理方法

当主管节点Hc收到来自Sink的Top-k查询请求Qt=c,t,k,QS后，首先根据被OPES加密方案加密过的数据项权重的密文值在自身存储的数据中查找满足Qt查询要求的Top-k数据项密文，然后将这些数据项的密文连同部分安全检测信息一同发送给Sink.令ni,t表示Si(∀I∈QS)在第t个时隙内产生的满足Qt查询要求的Top-k数据项的个数，ξti表示Hc从Si的数据报告中获得且准备作为查询结果的一部分向Sink转发的数据包，则根据ni,t取值的不同，ξti的值分别讨论如下：

1) 如果ni,t=μi,t=0,有:

ξti=;

(7)

2) 如果ni,t=0,μi,t>0,有:

ξti=;

(8)

3) 如果0

ξti=

;

(9)

4) 如果0

ξti=

.

(10)

令Rt表示Hc向Sink发送的关于Qt=c,t,k,QS的Top-k查询结果，则Rt可表示为

Rt={ξti|∀i∈QS}.

(11)

3.3 Sink节点上Top-k查询结果的完整性检验

Sink进一步地检验Rt的数据完整性.假设Rt中所有数据项的最小权重为ds.对于任意传感器节点Si(∀i∈QS)，令γi表示Rt中由Si产生的数据项的个数.Sink节点检验每个节点Si(∀i∈QS)在Rt中的数据信息是否满足4个条件之一：

当满足4个条件之一时，认为Si(∀i∈QS)包含在Rt中的数据信息通过完整性检验.只有当QS内的所有传感器节点包含在Rt中的数据信息都通过完整性检验时，Rt才被认为是完整的，否则认为Rt不具有数据完整性.

4 VPP的安全性、能效性与计算复杂性分析

4.1 VPP的安全性分析

在本文中，VPP协议的安全性主要是指，在传感器节点相对安全的情况下，当主管节点能够被捕获并成为恶意节点时，在TWSNs系统中进行Top-k查询过程中VPP协议对数据的隐私性和完整性的保护性能.

命题1. 在TWSNs中，在传感器节点相对安全而主管节点被恶意化的情况下，采用VPP进行Top-k查询，恶意化的主管节点既不能获知任何感知数据项及其对应权重的具体数值信息，又不能获知任何Top-k节点的ID信息.

证明. 传感器节点的ID及其所产生数据项是经过传感器与Sink节点之间的对称密钥加密的，主管节点在传感器节点不被妥协的条件下无法获得传感器节点与Sink节点之间的对称密钥，因此，主管节点也无法获知感知数据项以及传感器节点ID的值.另外，由于数据项对应的权重已被利用OPES加密方案进行加密，而能够解开OPES的密钥参数只有Sink节点才拥有，因此，主管节点也无法获知数据项对应权重的具体数值.

证毕.

命题2. 在双层传感器网络中，在传感器节点相对安全而主管节点被恶意化的情况下，利用VPP进行Top-k查询，Sink节点能够以100%的概率侦测出任何不具备数据完整性的Top-k查询结果.

证毕.

4.2 VPP的能效性分析

表1中列出了本文在分析VPP各项性能时用到的一些符号及其含义.

Table 1 Notations Used in Performance Analysis表1 性能分析需要用到的符号

本文需要用到的能效性评价标准主要包括：

1) 单元内的额外通信代价Cv_sm.单元内的所有传感器节点在一个时隙内向对应主管节点传输用于Sink进行Top-k查询结果数据完整性检测的额外数据信息所需要的通信代价.

2) 单元外的额外通信代价Cv_mw.在响应单个Top-k查询请求的过程中，主管节点与Sink节点之间传输用于Sink进行Top-k查询结果数据完整性检测所需要的通信代价.

3) 冗余比Rvs.额外传输安全检测信息的通信代价与在不考虑安全性条件下传输必要数据信息的通信代价之间的比值.

(12)

根据Cv_sm的含义，可得：

(13)

令Cd_sm表示单元c内的传感器节点在第t个时隙内向Hc传输感知数据所带来的通信代价，则有:

(14)

从而可得出Cv_sm对应的Rvs的值：

(15)

推导Cv_mw以及其对应Rvs的过程与推导Cv_sm及其所对应Rvs的过程类似.假设Hc收到的查询原语为Qt=C,t,k,QS,向Sink发送的查询结果为Rt，其中由Si产生的Top-k数据项的个数为ni,t，令表示在Hc和Sink之间传输由节点Si∈QS产生的安全检测信息的通信代价，根据式(7)～(10)，有:

(16)

Hc和Sink之间由于传输所有QS内的传感器节点产生的安全检测信息所带来的通信代价为

(17)

其中，xi∈QS(0

Cd_mw=2×k×ldata.

(18)

综上，可得Cv_mw所对应的Rvs为

(19)

4.3 VPP的计算复杂性分析

1) VPP在传感器节点上的计算复杂性.对于任意传感器节点Si，每个时隙内Si需要进行一次Hash操作，以获取下一个时隙内自身与Sink节点之间的对称秘钥.同时，根据式(5)和式(6)，当μi,t=0时，Si需要加密的数据总位数为lID；当μi,t≠0时，Si需加密的数据总位数为lID+2×μi,t×lID+μi,t×lID.

2) VPP在主管节点上的计算复杂性.由于主管节点能够根据数据权重值的OPES加密值直接进行Top-k查询处理，因此，VPP对主管节点而言所增加的额外计算开销可忽略不计.

3) VPP在Sink节点上的计算复杂性.Sink收到Top-k查询结果时首先利用对称密钥对查询结果中的密文进行解密.假设被查询单元为第c(1≤c≤M)单元，根据式(7)～(10)，Sink节点需要解密的密文共Nc+k项，需要解密的数据总位数长度近似为Nc×(lID+lscore)+k×(ldata+lscore).接着，Sink需要检验Rt中的每个感知数据项的权重值是否与其在Rt中对应的权重值相等.由于Rt中的感知数据项个数为k，因此，这一过程的计算复杂度为O(k).另外，根据VPP协议在Sink节点上的数据完整性检验方法，Sink还需要检验每个传感器节点Si(∀i∈QS，QS表示被查询节点的ID号所构成的集合)在Rt中的数据信息是否满足3.3节给出的4个条件，此过程的计算复杂度与|QS|的值呈线性关系.

Fig. 2 Impact of μi,t on Cv_sm and its corresponding Rvs图2 参数μi,t对Cv_sm和Cv_sm所对应的Rvs的影响

5 实验与分析

实验所采用的仿真工具为OMNET++，所用到的部分默认参数设置如表2所示，其余参数的默认参数设置同文献[3].文献[3]是自2010年以来有关双层传感器网络中Top-k查询的安全问题而产生的最优秀的研究成果之一，因此，本文选择文献[3]中提出的2种方案作为比较对象.文献[3]中提出的方案1在Cv_sm(即文献[3]中的CT)方面表现最好，因此，本文在测试VPP在Cv_sm及其对应Rvs方面的表现时选择文献[3]中的方案1作为比较对象；又因为文献[3]中的方案2在Cv_mw(即文献[3]中的CV)方面的表现相对其他2个方案而言效果更好，因此本文在测试VPP在Cv_mw及其对应Rvs方面的表现时选择文献[3]中的方案2作为比较对象.为便于描述，下文称文献[3]中的方案1为Z&R-1，称文献[3]中的方案2为Z&R-2.另外，为了将Cv_sm和Cv_mw分别对应的Rvs区分开来，本文用Rvs_sm表示Cv_sm所对应的Rvs，用Rvs_mw表示对应的Rvs.

Table 2 Default Settings of Parameters表2 参数的默认设置

为便于对实验结果进行分析，本文将每个传感器节点产生的安全检测信息分成2部分：Vhead={密钥ID,节点ID}和Vbody={感知数据项的权重集合}.

第1组实验测试参数μi,t对Cv_sm及其对应Rvs的影响，实验结果如图2所示.图2(a)显示，随着传感器节点在一个时隙内采集数据的轮数的增加，无论是VPP还是Z&R-1，Cv_sm的值随之增大.这是因为VPP和Z&R-1都需要为每个感知数据增加相应的安全检测信息，这样，随着传感器节点向主管节点传输感知数据量的增大，所需要传输的安全检测信息的量也会增大.然而，从图2(a)中可以看出，μi,t固定时，VPP对应的Cv_sm的值要远远小于Z&R-1中Cv_sm的值,原因是VPP不需要在安全检测信息中为每个感知数据添加长度值较大的消息认证码.图2(b)显示，VPP和Z&R-1中Cv_sm对应的Rvs的值随μi,t的增大的变化趋势是:开始有些下降，随后基本保持不变.这一现象可作如下解释:当μi,t较小时，Vbody较小，Vhead在整个安全检测信息中占有的比重较大；随着μi,t的增大，Vhead在整个安全检测信息中占有的比重越来越小，直至可以忽略不计，此时有:

(20)

虽然VPP和Z&R-1中Cv_sm对应的Rvs的值变化趋势相同，但从图2(b)中可以看出，VPP能够明显降低Cv_sm对应的Rvs的值.

第2组实验测试参数Nc(1≤c≤M)对Cv_sm及其对应Rvs的影响，实验结果如图3所示.图3(a)显示，随着单元内传感器节点的增多Cv_sm的值越来越大.这是因为，在其他参数值固定不变时，单元内传感器节点个数越多,一个时隙内节点产生的感知数据个数越多，单元内节点所需要传输的安全检测信息量越大.图3(b)显示，Cv_sm所对应Rvs的值随着Nc的增大而基本保持不变，原因是因节点个数的增多而带来的安全检测信息的增加量与感知数据的增加量保持某种比例.图3表明:无论Nc的取值为多少，相对于Z&R-1，VPP都能够显著降低传输安全检测信息的通信代价.

第3组实验测试参数μi,t对Cv_mw以及其对应的Rvs的影响，实验结果如图4所示.由图4可以看出，对于VPP，参数μi,t对Cv_mw及其对应的Rvs的影响不大，几乎可忽略.然而，对于Z&R-2，当μi,t较小时，μi,t对Cv_mw及其对应的Rvs的影响较大，随着μi,t的逐渐变大，μi,t对Cv_mw及其对应的Rvs的影响逐渐减弱.这是因为，Z&R-2需要将每个数据项与某些节点ID的集合进行绑定，并且多数情况下查询结果中每个Top-k节点产生的安全检测信息需要包含一个非Top-k数据项作为尾巴(tail)数据.当μi,t较小时，Top-k节点产生的数据全是Top-k数据的概率较大，而当Top-k节点产生的数据都是Top-k数据时，尾巴数据项是一个设定的小于任何感知数据的数据值，以至于尾巴数据项需要绑定的节点ID的个数很大，从而增大安全检测信息的量.随着μi,t的增大，Top-k节点产生的数据全是Top-k数据的概率降低，μi,t对Cv_mw以及其对应的Rvs的影响减弱.图4表明，相对于Z&R-2，VPP在Cv_mw以及其对应的Rvs方面的表现更加稳定，并且都要优于Z&R-2.

Fig. 3 Impact of Nc on Cv_sm and its corresponding Rvs图3 参数Nc对Cv_sm和Cv_sm所对应的Rvs的影响

第4组实验测试参数k对Cv_mw以及其对应的Rvs的影响，实验结果如图5所示.图5(a)显示，对于VPP而言，随着k值的增加Cv_mw增加的幅度很小.原因是对于VPP而言,假设k值的增加量为Δk，主管节点向Sink节点发送的安全检测信息的位数长度仅需要增加Δk×lscore.而对于Z&R-2而言，Cv_mw随k值的增大而增大的幅度比较明显，主要原因是，在Z&R-2中，每个数据项需要一个160 b长的消息认证码作为安全检测信息的一部分，并且每个数据项需要与其他部分传感器节点ID组成的集合进行绑定，当单元内传感器节点个数较多时，每个数据项需要绑定的节点ID集合较大，从而使得Z&R-2中主管节点向Sink节点发送的安全检测信息的量随k值增大而显著增大.图5(b)显示，当k较小时，VPP中Cv_mw对应的Rvs大于Z&R-2中Cv_mw对应的Rvs;而随着k值的增加，VPP中Cv_mw对应的Rvs明显小于Z&R-2中Cv_mw对应的Rvs，这与Z&R-2中Cv_mw随k值的增大而显著增大有密切关系.

Fig. 5 Impact of k on Cv_mw and its corresponding Rvs图5 参数k对Cv_mw和Cv_mw所对应的Rvs的影响

第5组实验测试参数|QS|(即单元内被查寻节点的个数)对Cv_mw以及其对应的Rvs的影响，实验结果如图6所示.在图6中，当采用VPP时，Cv_mw及其对应Rvs的值随着|QS|的增大有明显上升趋势，这是因为VPP需要在查询结果中包含每个被查寻节点的安全检测信息，当被查询节点个数增大时Cv_mw会随之增大，在相同的k值的情况下，Cv_mw对应的Rvs的值也会随着|QS|的增大而增大.当采用Z&R-2时，Cv_mw及其对应Rvs的值随着|QS|的增大而变化的趋势不是十分明显，主要原因是Z&R-2仅需要在查询结果中包含Top-k节点的安全检测信息.尽管如此，总体上说，当采用VPP时Cv_mw及其对应Rvs的值都要明显低于采用Z&R-2时Cv_mw及其对应Rvs的值.

Fig. 6 Impact of the parameter |QS| on Cv_mw and its corresponding Rvs图6 参数|QS|对Cv_mw和Cv_mw所对应的Rvs的影响

6 总 结

TWSNs是物联网感知系统中的一个重要组成部分.本文针对TWSNs中的Top-k查询数据隐私性和完整性保护问题，提出了一种新的安全处理协议VPP，对其安全性和能效性进行了分析，并通过仿真实验对其在实现Top-k查询数据隐私性和完整性保护方面的能效性进行了测试.理论分析表明，相对于已有方案，VPP具有更好的安全性.VPP不仅能够确保Top-k查询的数据隐私性(数据项、数据项对应的权重以及节点ID的隐私性均得到保护)，还能够以100%的概率检测出不具有数据完整性的Top-k查询结果.

实验结果显示，无论是在传感器节点与主管节点之间，还是在主管节点与Sink之间，VPP都能够显著降低用于传输安全检测信息的额外通信代价，降低了安全检测信息与必要感知数据之间的冗余比.因此，VPP在实现Top-k查询的数据隐私性和完整性保护方面效率更高.