网络安全范围查询协议

1相关工作

WSNs安全范围查询的研究内容包括以下两个方面：查询过程隐私性保护和查询结果完整性验证。其中前者需要满足①普通传感器节点收集到的数据不会丢失、泄露、被篡改、被伪造；②存储节点存储的数据和查询请求在查询过程中不会丢失、泄露、被篡改、被伪造；③数据和查询请求以及查询结果在传输过程中被窃取也不会泄露隐私。同时后者需要满足①满足查询条件的数据要全部包含在查询结果中；②查询结果一旦丢失、被删改、被伪造都可以被Sink节点有效检测出来。文献[4]首次提出了基于桶模式[5-6]的考虑隐私保护的范围查询，文献[7]改进了该范围查询，提出了Hybrid时空交叉验证方法。文献[8]提出了SMQ子树采样技术来完成范围查询的隐私保护。密歇根州立大学的CHENFei和LIUAX提出了一种全新的范围查询策略，即基于前缀成员验证技术的SafeQ[9]。对WSNs范围查询隐私保护研究的主流协议有两类，即基于桶模式和基于前缀成员验证技术。基于桶模式的范围查询有一个天然的缺陷，即一旦存储节点被俘获，虽然具体数据和查询结果泄露不了，但是攻击者可以根据分桶情况大概推断出查询的数据范围。所以这就从根本上决定了基于桶模式的范围查询的安全水平有限；基于前缀成员验证技术的SafeQ范围查询的安全性比桶模式完善，但其仍存在能耗较高的问题，由于传感器网络具有能量受限的关键特性，这就成了SafeQ推广的一个瓶颈。本文提出的SPQ属于第二类协议，天然上就比基于桶模式的协议有更高的安全性。另外SPQ通过改变查询策略和完整性验证方法来进一步降低能耗，使得SPQ有更低的能耗。

2网络模型

WSNs安全数据查询即隐私保护研究主要是基于两层传感器网络模型[10]（图1），范围查询也不例外。SPQ就是基于该模型的协议。图1两层无线传感器网络模型如图1所示，该网络模型高层由存储节点组成，存储节点(StorageNode)就是有较大存储空间和较强计算能力的传感器节点；底层由大量的普通传感器节点组成，普通节点资源受限且成本低。数据的查询过程如下：用户的查询要求(Query)通过Sink传到存储节点，普通节点收集到数据后将数据传到存储节点存储，然后在存储节点上进行查询计算，最后将满足条件的查询结果(Reply)回传给Sink并最终返回给用户。WSNs数据查询选用两层模型有如下好处：①普通传感器节点只需要将所有采集到的数据传输给附近的存储节点而不是通过很长的路径传输给Sink节点，这大大降低了能耗，避免Sink节点遭遇通信瓶颈；②Sink只和存储节点通信并可得到查询结果，这使查询过程更加有效率。

3WSNs安全范围查询协议

对于WSNs来说，能耗大小往往是考虑是否实施安全策略的掣肘。SPQ的目标就是在保证查询的安全同时尽量减少能耗。3.1关键技术3.1.1数据加密SPQ中，每个普通传感器节点si都将和Sink共享一个密钥ki，并且ki定期更换。普通节点si收集到的数据d1,···,dn在查询过程中都将被ki加密，即便是完成查询过程并收集查询结果上传给Sink的存储节点也无法得到具体的数据信息，这就保证了数据的私密性。3.1.2前缀成员验证存储节点在无法识别具体数据的情况下，仍然需要完成查询过程，这就应用了前缀成员验证技术。前缀成员验证技术就是将验证数据是否符合范围查询的条件转化为比较数据项的大小。例如判断数据12是否符合范围查询[11，15]。12的二进制表示是1100，首先对其构造前缀家族得到｛1100110*11**1*******｝，然后再进行前缀数值化得到｛1100111010111001100010000｝；于此同时[11,15]的二进制表示是[1011,1111]，即｛10111100110111101111｝，首先进行前缀转化得到｛101111**｝，再对其前缀数值化得到｛1011111100｝。在最终的前缀数值化组里，他们有相同的项11100，这就表明数据12符合范围查询[11,15]。反之如果其中没有相同数据项，则说明该数据不符合范围查询条件。在SPQ中，用三个哈希函数来应用前缀成员验证技术。三个哈希函数[11-13]分别是Φ，Ψ，Ω。3.1.3概率邻居验证SPQ的查询结果完整性验证通过概率邻居验证技术实现。即普通节点si得到查询结果后，生成消息（t,i,len)，并将该消息传给附近邻居节点。其中t是时间段，i是传感器编号，l是满足查询的数据项数目。然后每个邻居节点以一定概率p随机加入（t,i,len)到自己的查询结果中并加密上传，Sink接收到查询结果后根据各个（t,i,len)进行查询结果完整性验证。3.2SPQ一维数据查询过程WSNs范围查询通常可以根据数据项维度的不同分为一维数据查询和多维数据查询。一维数据查询过程最简单，随着维度的增加，往往多维数据查询的能量消耗呈指数增长。SPQ就要尽量避免这种情况，改善不同维度的能耗情况。対一维数据查询时，SPQ实现过程如下伪代码所示。其中Sink为汇聚节点，StorageNode为存储节点，si、sj为普通节点。具体查询细节如下：①普通节点si收集到一定数据并排序后得到d1,···,dn,应用第一个哈希函数Ψ加密得到定长的消息编码Ψ(d1,···,dn)并发送给存储节点。当Sink想要做出查询｛t,[a,b]｝时，会先用另外一个函数Ω对查询范围进行处理最终将会发送｛t,Ω([a,b])｝到存储节点。②存储节点处理查询时用到第三个函数Φ，当Φ(j,Ψ(d1,···,dn),Ω([a,b]))为真时，说明dj满足查询条件；为假时说明dj不满足查询条件，应当舍弃。存储节点将满足查询条件的最小数据和最大编号以及数据个数（min_d,max_d,len）i反馈给si。③si在收到反馈结果后，找出队列中包括编号min_d和max_d的所有中间数据dmin_d,···,dmax_d，并加入dmin-1（如min_d-1<1，则取dmin_d-1=-1），dmax_d+1（如max_d+1>n，则取dmax_d+1=∞）。si生成消息（t,i,len)，并将该消息传给附近邻居节点。其中t是时间段，i是传感器编号，len是满足查询的数据数目。④假如si收到邻居节点si_neighbor发送来的消息（t,i_neighbor,len)，将以一定概率p将此消息加入到自己需上传的查询结果中去，即最终上传{(t,i_neighbor,len)p,dmin_d,···,dmax_d}ki。其中ki是si和Sink共享的密钥。上传数据经过存储节点最终传到Sink，Sink再对所有查询结果进行完整性验证，至此SPQ结束。3.3SPQ多维数据查询过程因为现实应用中，范围查询应用场景往往是针对多维数据而言的，所以将SPQ协议应用到对多维数据查询也是非常必要的。下面简述多维数据下SPQ的查询过程：①普通节点si收集到n个m维数据(d11,d12,···,d1m）,···,(dn1,dn2,···,dnm)后,应用第一个哈希函数Ψ加密得到m个定长的消息编码Ψ(d11,···,dn1),Ψ(d12,···,dn2),Ψ(d1m,···,dnm)并发送给存储节点。当Sink想要做出查询｛t,([a1,b1],···,[am,bm])｝时，会先用另外一个函数Ω对查询范围进行处理最终将会发送｛t,Ω([a1,b1]),···Ω([am,bm])｝到存储节点。②存储节点处理查询时用到第三个函数Φ，当Φ(j,Ψ(d1t,···,dnt),Ω([at,bt]))为真时(其中1=<t<=m)，说明dj满足维度t上的查询条件；为假时说明dj不满足维度t的查询条件，应当舍弃。当把所有维度做完后，求编号的交集就得到最终的查询结果，存储节点将这些满足查询条件的数据编号最值{(min_d1,max_d1),···,(min_dm,min_dm),len}反馈给si。si在查询过程中对上传数据按随机某个维度t的值进行排序。在收到反馈结果后，根据查询结果找出所有符合条件数据并加密。③、④与一维数据查询过程相同。

4性能分析

4.1安全性分析因为普通节点数据量小，如被俘获对全局查询结果影响不大，所以现在主要考虑存储节点被俘后的情况，以此来验证SPQ的安全性能。由于查询结果已加密，所以存储被俘后无法获得有效的查询数据。被俘存储节点可以做的工作主要是丢弃数据和更改查询结果（min_d,max_d,len）i。这两者破坏都可以由Sink在完整性验证时检测出来。4.2能耗分析SPQ相对之前的范围查询协议在能耗上有改进，一个原因是由于查询过程和传输查询结果过程分离的结果，这样一来不符合查询条件的数据将不会上传到存储节点，这样就减低了很大一部分数据传输量，即减少了普通节点发送数据消耗的能量，又降低了存储节点接受数据所需的能耗，明显降低了安全范围查询的能量消耗。4.3仿真实验本文使用原始数据集在MATLAB平台上对SPQ和SafeQ进行仿真，在长宽均为300米的区域有100个普通节点随机分布，4个存储节点较均匀分布，居中一个Sink节点。假设传感器节点有效传输距离为75米，利用TAG（tinyaggregationserviceforadhocsensornetwork）算法建立路由路径，每个普通节点向存储节点传输数据平均需要1.8跳。每个节点平均有20个邻居节点，向每个邻居节点发送验证消息的概率为0.4。仿真实验中，能耗值是指具体能耗除以时间，即类似功率的一个衡量能耗水平的值；有效查询比为存储节点最终查询结果得到的有效数据量和消耗的能量的比值，其反映了协议的网络能量利用效率。实验主要是对比SPQ和SafeQ对不同维度数据进行查询时的能耗。为了保证实验结果的正确性，所有实验采用相同的真实数据集，一维数据集和二维数据集是从三维数据集中剥离的一个维度和两个维度，即不同维度的实验在单位时间内接收到的查询结果数据项数量应该是相同的。（1）一维数据查询第一组实验是在一维数据查询下，SPQ和SafeQ的能耗对比情况：通过实验结果图对比知，针对一维数据查询时，在相同数据集来源情况下，SPQ普通节点能耗值比SafeQ低3.2倍；SPQ存储节点能耗值比SafeQ低2.5倍。SPQ的有效查询比是SafeQ的2.2倍。在一维数据情况下，SPQ能耗水平明显低于SafeQ。（2）多维数据查询第二组实验是在多维数据查询下（本实验使用三维数据），SPQ和SafeQ的对比情况：图5三维数据查询的普通节点的平均能耗对比图6三维数据查询的存储节点的平均能耗对比图7三维数据查询的有效查询比的对比通过实验二结果图对比知，针对三维数据查询时，在相同数据集来源情况下，SPQ普通节点能耗值比SafeQ低3.64倍；SPQ存储节点能耗值比SafeQ低1.17倍。SPQ的有效查询比是SafeQ的1.1倍。在三维数据情况下，SPQ能耗水平也低于SafeQ。（3）不同维度数据查询对比第三组实验是在不同维度数据查询下，SPQ的表现情况对比：通过结果图对比知，在相同数据集来源情况下，SPQ普通节点对三种维度数据查询时能耗成线性增长；SPQ存储节点对三种维度数据查询时能耗也是成线性增长。即在多维数据查询情况下，SPQ的节能能力同样突出。

5结束语

本文提出的SPQ协议的数据隐私性保护通过前缀成员验证技术来实现，数据完整性验证则主要由概率邻居验证技术来完成，并通过一系列通信策略优化减少通信量即能耗，使其优于现有的SafeQ和基于桶模式的范围查询。虽然SPQ相比现有协议能耗更加低，安全性能也很好，但是相比不加隐私保护的查询策略，能耗仍然偏高，需进一步寻找安全策略或通信方式减少能耗，使安全数据查询可以更加好的推广。

作者：武佩宁 宋玲 伍文华 单位：广西大学 计算机与电子信息学院