胡曉燕,王靜宇,李海榮

1.內(nèi)蒙古科技大學(xué) 工程訓(xùn)練中心,內(nèi)蒙古 包頭 014010; 2.內(nèi)蒙古科技大學(xué) 網(wǎng)絡(luò)中心,內(nèi)蒙古 包頭014010)(*通信作者電子郵箱hxy123@imust.cn)

面向外包空間數(shù)據(jù)庫(kù)的范圍查詢驗(yàn)證

胡曉燕1*,王靜宇2,李海榮1

1.內(nèi)蒙古科技大學(xué) 工程訓(xùn)練中心,內(nèi)蒙古 包頭 014010; 2.內(nèi)蒙古科技大學(xué) 網(wǎng)絡(luò)中心,內(nèi)蒙古 包頭014010)(*通信作者電子郵箱hxy123@imust.cn)

針對(duì)空間范圍查詢驗(yàn)證方法(例如VR-tree和MR-tree)普遍存在驗(yàn)證對(duì)象(VO)中包含大量的節(jié)點(diǎn)驗(yàn)證信息,造成服務(wù)器到客戶端的傳輸代價(jià)較大以及客戶端驗(yàn)證效率較低等問(wèn)題,提出一種新的驗(yàn)證索引結(jié)構(gòu)(ADS)MGR-tree。首先利用拆分思想,通過(guò)在Grid-tree的葉子節(jié)點(diǎn)中嵌入R-tree,并結(jié)合Merkle哈希樹(shù)的驗(yàn)證方法,極大地減小VO的大小,提高查詢和驗(yàn)證的效率。在此基礎(chǔ)上,利用Hilbert曲線降維的特性,構(gòu)建了優(yōu)化的索引結(jié)構(gòu)MHGR-tree,并提出一種過(guò)濾策略,進(jìn)一步提高驗(yàn)證的效率。實(shí)驗(yàn)結(jié)果表明,所提方法具有更好的表現(xiàn)。在最好情況下,MHGR的VO大小和驗(yàn)證時(shí)間僅為MR的63%和19%。

移動(dòng)互聯(lián)網(wǎng);位置服務(wù);數(shù)據(jù)庫(kù)外包;查詢驗(yàn)證;驗(yàn)證對(duì)象

0 引言

對(duì)于數(shù)據(jù)庫(kù)外包服務(wù)或云計(jì)算服務(wù),數(shù)據(jù)所有者(Data Owner, DO)失去對(duì)數(shù)據(jù)的直接操作和控制的能力,隨之產(chǎn)生諸多的數(shù)據(jù)安全隱患問(wèn)題[1]。例如,在基于位置服務(wù)(Location-Based Service, LBS)查詢應(yīng)用中,服務(wù)提供商(Services Provider, SP)是不可信的,商家為了贏得更多利益,在用戶(Client)不知情的情況下,與服務(wù)提供商相互勾結(jié),篡改用戶的查詢結(jié)果或返回不完整的結(jié)果,損害用戶的權(quán)益。因此,如何向用戶提供真實(shí)結(jié)果以及驗(yàn)證結(jié)果的正確性和可靠性顯得尤為重要。

目前,已經(jīng)存在的查詢驗(yàn)證方法主要分為兩類[2-12]:基于數(shù)字簽名技術(shù)和基于Merkle哈希樹(shù)(Merkle Hash Tree, MHT)。Pang等[3-4]提出了簽名鏈的方法,將相鄰數(shù)值連接形成一個(gè)簽名,通過(guò)重新計(jì)算結(jié)果集里每個(gè)數(shù)值的簽名并與標(biāo)記的該數(shù)值簽名匹配,實(shí)現(xiàn)完整性的驗(yàn)證。值得注意的是,數(shù)字簽名的方法在構(gòu)建、存儲(chǔ)和更新數(shù)據(jù)索引時(shí)會(huì)造成較大的計(jì)算開(kāi)銷。為了解決這個(gè)問(wèn)題,Narasimha等[5]提出數(shù)字簽名聚合和鏈接的方法。由于傳統(tǒng)簽名驗(yàn)證的方法都是驗(yàn)證一維數(shù)據(jù)的可靠性,Cheng等[6]提出了基于空間分割的VKD-tree(Verifiable KD-tree) 和基于數(shù)據(jù)分割的VR-tree(Verifiable R-tree) 用于驗(yàn)證多維數(shù)據(jù)庫(kù)查詢;MHT最廣泛的應(yīng)用就是與其他索引結(jié)構(gòu)相結(jié)合。對(duì)于一維數(shù)據(jù)查詢驗(yàn)證,Li等[7]提出了MB-tree,通過(guò)在原始B+-tree的基礎(chǔ)上,每個(gè)節(jié)點(diǎn)上都包含了一個(gè)hash值,hash值的計(jì)算與MHT相似。為了進(jìn)一步減小驗(yàn)證對(duì)象(Verification Object, VO)的大小,Li等[7]又提出了MB-tree的變形EMB-tree。而針對(duì)多維數(shù)據(jù)查詢驗(yàn)證,Yang等[8-9]在MHT和R*-tree的基礎(chǔ)上提出了MR-tree。相對(duì)于VR-tree,MR-tree在索引構(gòu)建時(shí)間、存儲(chǔ)空間消耗、查詢處理和查詢驗(yàn)證等性能方面都有了較大的提升。與此同時(shí),Mouratidis等[10]提出了一種部分實(shí)體化摘要的策略(Partially Materialized Digest, PMD),可以與多種索引驗(yàn)證結(jié)構(gòu)結(jié)合,既可以應(yīng)用于一維的數(shù)據(jù)查詢驗(yàn)證,同時(shí)也適用于多維空間查詢驗(yàn)證。謝晴晴等[11]利用PDM策略改進(jìn)了MHT,實(shí)現(xiàn)了數(shù)據(jù)流范圍查詢驗(yàn)證。除此之外,Hu等[12]實(shí)現(xiàn)了在進(jìn)行范圍查詢驗(yàn)證時(shí),對(duì)查詢數(shù)據(jù)的隱私保護(hù)。

本文在MR-tree的研究基礎(chǔ)上,主要的工作包括以下三個(gè)方面:1)提出了一種改進(jìn)的驗(yàn)證方案,通過(guò)建立一種新的MGR-tree驗(yàn)證索引結(jié)構(gòu),提升了MR-tree在驗(yàn)證時(shí)間以及驗(yàn)證對(duì)象大小等方面的性能；2)在此基礎(chǔ)上,提出了一種優(yōu)化的索引結(jié)構(gòu)MHGR-tree,通過(guò)用Hilbert曲線遍歷Grid-tree,降低了搜索空間的維度,從而加快了查詢和驗(yàn)證的過(guò)程；3)基于Hilbert曲線一維線性的特性,提出一種優(yōu)化的過(guò)濾策略,進(jìn)一步加快了驗(yàn)證的過(guò)程。

1 背景知識(shí)

定義1 單向哈希函數(shù)。給定哈希函數(shù)H(·),其作用于任意長(zhǎng)度的字符串消息M,并返回固定長(zhǎng)度的輸出H(M)。它滿足兩個(gè)性質(zhì):1)單向性。給定H(·)和H(M),反向計(jì)算M是不可行的。2)無(wú)碰撞性。給定M,找到消息M′滿足H(M)=H(M′)是不可行的。

例如,目前最常用的哈希函數(shù)是SHA1,其固定輸出160bit字符串消息。

定義2 數(shù)字簽名。簽名者產(chǎn)生一對(duì)密鑰(私有密鑰和公有密鑰),數(shù)據(jù)所有者利用私有密鑰對(duì)數(shù)字消息簽名,并將公有密鑰公開(kāi)發(fā)布,消息接收者利用公有密鑰對(duì)接收到的消息進(jìn)行可靠性驗(yàn)證。

例如,目前最常用的公鑰加密算法是RSA(Rivest、Shamir和Adleman),其產(chǎn)生128B的消息簽名。

定義3Merkle哈希樹(shù)(MHT)。MHT[2]是一棵二叉樹(shù),通過(guò)分層的自底向上計(jì)算所有節(jié)點(diǎn)的哈希值,并對(duì)根節(jié)點(diǎn)的哈希值進(jìn)行數(shù)字簽名。

MHT的結(jié)構(gòu)如圖1所示,其中涵蓋了四條數(shù)據(jù)記錄d1～d4,MHT的節(jié)點(diǎn)哈希值計(jì)算如下:1)如果節(jié)點(diǎn)N是葉子節(jié)點(diǎn),其哈希值為H(dN),dN是數(shù)據(jù)記錄。2) 如果節(jié)點(diǎn)N是非葉子節(jié)點(diǎn),其哈希值為H(dL|dR),dL和dR分別為節(jié)點(diǎn)N的左、右孩子節(jié)點(diǎn)的哈希值,“|”為字符串連接符。對(duì)于給定的范圍查詢Q(如圖1中矩形框所示),覆蓋數(shù)據(jù)記錄d1和d2,且d1和d2分別為范圍的左右邊界。VO(圖1中深色節(jié)點(diǎn))包含了從根節(jié)點(diǎn)到左(右)邊界的路徑上節(jié)點(diǎn)的所有兄弟節(jié)點(diǎn)的摘要(如圖節(jié)點(diǎn)N2)。通過(guò)VO和查詢結(jié)果重新構(gòu)建根節(jié)點(diǎn)的哈希值,如果與數(shù)據(jù)所有者簽名的哈希值匹配,則查詢結(jié)果是正確的,沒(méi)有被篡改。

圖1 MHT結(jié)構(gòu)

2 范圍查詢驗(yàn)證策略

本章主要介紹了MGR-tree和MHGR-tree索引結(jié)構(gòu)的構(gòu)建算法,并描述了在MHGR-tree上的查詢和驗(yàn)證的過(guò)程。

2.1MGR-tree

在構(gòu)建R-tree時(shí),不同節(jié)點(diǎn)間的最小邊界矩形(MinimumBoundRectangle,MBR)會(huì)出現(xiàn)相交的情況；而且隨著數(shù)據(jù)量增大,節(jié)點(diǎn)間的MBR相交數(shù)目會(huì)增多。因此在執(zhí)行范圍查詢時(shí),會(huì)訪問(wèn)不必要的節(jié)點(diǎn),影響查詢的效率。若R-tree的結(jié)構(gòu)比較大時(shí),其產(chǎn)生的驗(yàn)證對(duì)象VO也比較大,影響驗(yàn)證的效率。而VO的大小是系統(tǒng)最重要的評(píng)價(jià)準(zhǔn)則,它衡量了服務(wù)提供商到客戶端的傳輸代價(jià),是系統(tǒng)性能的決定因素。通過(guò)實(shí)驗(yàn)觀察,把R-tree拆分成多棵結(jié)構(gòu)較小的R-tree時(shí),對(duì)產(chǎn)生的驗(yàn)證對(duì)象的大小有明顯的影響,結(jié)果如圖2所示(其中,數(shù)據(jù)基數(shù)為2×106,26×26和27×27表示分別將R-tree拆分成26×26和27×27棵小的R-tree)。

圖2 劃分的R-tree對(duì)VO大小的影響

從圖2中看出,隨著查詢范圍的增大,驗(yàn)證對(duì)象VO包含的節(jié)點(diǎn)數(shù)目不斷增加。當(dāng)查詢范圍大于5%時(shí),基于拆分方法產(chǎn)生VO的大小很大程度上小于MR-tree的方法,并且隨著拆分的分辨率越高,產(chǎn)生的VO越小?；谏鲜龅膶?shí)驗(yàn)事實(shí),提出了一種新的驗(yàn)證索引結(jié)構(gòu)MGR-tree,該索引結(jié)構(gòu)結(jié)合了Grid-tree和R-tree的結(jié)構(gòu)特點(diǎn),實(shí)現(xiàn)了對(duì)R-tree的有效劃分。MGR-tree的索引結(jié)構(gòu)如圖3所示。

MGR-tree首先利用Grid-tree將搜索空間劃分網(wǎng)格,并將空間數(shù)據(jù)點(diǎn)映射到相應(yīng)的網(wǎng)格內(nèi),然后用R-tree索引相應(yīng)網(wǎng)格內(nèi)的數(shù)據(jù)點(diǎn)。MGR-tree節(jié)點(diǎn)摘要的計(jì)算方法同文獻(xiàn)[7]相似,不同的是對(duì)Grid-tree節(jié)點(diǎn)摘要的處理。對(duì)于葉子節(jié)點(diǎn),將節(jié)點(diǎn)內(nèi)嵌套R(shí)-tree根節(jié)點(diǎn)摘要直接作為葉子節(jié)點(diǎn)摘要;而對(duì)于非葉子節(jié)點(diǎn),則是將該節(jié)點(diǎn)的孩子節(jié)點(diǎn)摘要和節(jié)點(diǎn)網(wǎng)格區(qū)域連接,并利用哈希函數(shù)H(·)計(jì)算摘要。MGR-tree的構(gòu)建過(guò)程如算法1所示。

算法1MGR-tree的構(gòu)建算法。

輸入:空間區(qū)域R、空間數(shù)據(jù)點(diǎn)集P。 輸出:MGR-tree索引。

1)

將空間區(qū)域進(jìn)行網(wǎng)格劃分(h為預(yù)設(shè)最大層數(shù)),設(shè)置整個(gè)空間區(qū)域?yàn)楦?jié)點(diǎn)。

2)

for(Grid-tree的層數(shù)≤h)

//在區(qū)域網(wǎng)格上建立Grid-tree

3)

依次將每個(gè)未劃分的節(jié)點(diǎn)區(qū)域分層。

4)

將空間數(shù)據(jù)點(diǎn)依次映射到相應(yīng)的網(wǎng)格內(nèi)(Grid-tree的葉子節(jié)點(diǎn)內(nèi))。

5)

if 節(jié)點(diǎn)內(nèi)的點(diǎn)的數(shù)目不為0

6)

在每個(gè)網(wǎng)格對(duì)應(yīng)的節(jié)點(diǎn)內(nèi)嵌入R-tree。

7)

從MGR-tree的葉子節(jié)點(diǎn)層開(kāi)始,直至根節(jié)點(diǎn),計(jì)算每個(gè)節(jié)點(diǎn)的摘要。

8)

返回MGR-tree索引。

2.2 MHGR-tree

雖然MGR-tree在VO的大小和驗(yàn)證效率等方面的性能都有了提高，尤其是減小的VO,不僅縮短了查詢驗(yàn)證時(shí)間,同時(shí)也降低了傳輸開(kāi)銷。但是,客戶端在驗(yàn)證時(shí),仍然要遍歷VO中所有節(jié)點(diǎn)的MBR或節(jié)點(diǎn)的網(wǎng)格區(qū)域判斷是否與查詢范圍相交。而且,隨著空間維度的增加,查詢判斷和驗(yàn)證的代價(jià)都將增大。于是,在MGR-tree的基礎(chǔ)上,提出了優(yōu)化的MHGR-tree索引結(jié)構(gòu)。MHGR-tree是結(jié)合了MGR-tree和Hilbert曲線的一種索引結(jié)構(gòu),主要是通過(guò)將空間網(wǎng)格用Hilbert曲線遍歷,把Hilbert值映射到Grid-tree的每個(gè)節(jié)點(diǎn),并在Grid-tree的每個(gè)非空葉子節(jié)點(diǎn)中嵌入一棵R-tree。MHGR-tree的索引結(jié)構(gòu)如圖4所示。

圖3 MGR-tree的索引結(jié)構(gòu)

圖4 MHGR-tree的索引結(jié)構(gòu)

MHGR-tree通過(guò)Hilbert曲線將Grid-tree的多維空間降低到一維空間,并且通過(guò)Hilbert曲線的遍歷,每個(gè)節(jié)點(diǎn)都與相應(yīng)的網(wǎng)格區(qū)域Hilbert值對(duì)應(yīng)。如圖4所示,MHGR-tree的根節(jié)點(diǎn)對(duì)應(yīng)網(wǎng)格區(qū)域?yàn)檎麄€(gè)空間,即映射的Hilbert值區(qū)間為[0,15]；Grid-tree的葉子節(jié)點(diǎn)對(duì)應(yīng)最小網(wǎng)格劃分(如N33),其Hilbert值區(qū)間為[10,10]。

當(dāng)創(chuàng)建MHGR-tree時(shí),在Grid-tree的基礎(chǔ)上,計(jì)算每個(gè)節(jié)點(diǎn)的Hilbert值范圍(NodeHilbertRange,NHR),與MGR-tree不同的是摘要的計(jì)算。對(duì)MHGR-tree節(jié)點(diǎn)摘要的計(jì)算分為兩個(gè)部分:Grid-tree和R-tree。其中,R-tree中的節(jié)點(diǎn)摘要計(jì)算方法與MGR-tree相同。對(duì)Grid-tree的葉子節(jié)點(diǎn)L,其摘要DigL計(jì)算為:

DigL=H(Dig(Root)|Hil(L))

其中:Dig(Root)為葉子節(jié)點(diǎn)內(nèi)嵌入R-tree根節(jié)點(diǎn)的摘要,Hil(L)為葉子節(jié)點(diǎn)L所覆蓋網(wǎng)格的Hilbert值范圍。對(duì)Grid-tree的非葉子節(jié)點(diǎn),其摘要DigI計(jì)算為:

DigI=H(Dig1|Dig2|…|Dig4|Hil(I))

其中:Dig1～Dig4表示該非葉子節(jié)點(diǎn)的孩子節(jié)點(diǎn)的摘要;Hil(I)表示非葉子節(jié)點(diǎn)I所覆蓋網(wǎng)格的Hilbert值范圍。在迭代計(jì)算到根節(jié)點(diǎn)后,利用數(shù)據(jù)所有者的私有密鑰對(duì)根節(jié)點(diǎn)的摘要進(jìn)行簽名。

2.3 查詢處理

基于MHGR-tree進(jìn)行多維范圍查詢時(shí),主要考慮兩個(gè)部分:Grid-tree和R-tree的查詢過(guò)程。分別在兩棵樹(shù)上利用棧進(jìn)行深度優(yōu)先遍歷,判斷是否與查詢范圍相交,并將查詢結(jié)果和驗(yàn)證時(shí)所必需的信息返回。VO的計(jì)算是在查詢的過(guò)程中進(jìn)行的。VO中主要包含了在查詢過(guò)程與查詢范圍不相交的節(jié)點(diǎn)信息(對(duì)于Grid-tree,VO包含了節(jié)點(diǎn)摘要和Hilbert值范圍;對(duì)于R-tree,則包含了節(jié)點(diǎn)摘要和MBR)。具體過(guò)程如算法2所示。

算法2 MHGR-tree的查詢和創(chuàng)建VO算法。

輸入:空間查詢范圍R,MHGR-tree索引結(jié)構(gòu)。 輸出:查詢結(jié)果集Result Set和VO。 1)將空間查詢范圍R映射為Hilbert值范圍(HilbertRange,HR) 2)將MHGR-tree根節(jié)點(diǎn)入棧S3)WhileS非空 4)S.pop();

//出棧 5)if Grid-tree節(jié)點(diǎn)是非葉子節(jié)點(diǎn) 6)if Grid-tree節(jié)點(diǎn)的NHR與HR相交 7)S.push(節(jié)點(diǎn)的孩子節(jié)點(diǎn));

//入棧 8)else 將節(jié)點(diǎn)的摘要和NHR加入VO中 9)if Grid-tree節(jié)點(diǎn)是葉子節(jié)點(diǎn) 10)S.push(R-tree根節(jié)點(diǎn))

//入棧 11)if R-tree節(jié)點(diǎn)是非葉子節(jié)點(diǎn) 12)if 節(jié)點(diǎn)MBR與范圍R相交 13)S.push(節(jié)點(diǎn)的孩子節(jié)點(diǎn));

//入棧 14)else將節(jié)點(diǎn)的摘要和MBR加入VO中 15)if R-tree節(jié)點(diǎn)是葉子節(jié)點(diǎn) 16)if節(jié)點(diǎn)MBR與范圍R相交 17)將包含于范圍R內(nèi)的點(diǎn)P加入Result Set 18)else 將范圍外的點(diǎn)P的摘要和MBR加入VO中 19)Return Result Set and VO

算法2描述了范圍查詢的完整過(guò)程,首先將查詢范圍R映射為Hilbert范圍(第1)行),從MHGR-tree的根節(jié)點(diǎn)開(kāi)始判斷是否與查詢范圍相交(第2)～4行))。在Grid-tree上,通過(guò)判斷節(jié)點(diǎn)的Hilbert值范圍NHR與查詢范圍HR是否相交(第6)行),相對(duì)于多維屬性的相交判斷,一維Hilbert值的比較可以在一定程度上加快查詢。若相交,則將該節(jié)點(diǎn)的孩子節(jié)點(diǎn)入棧(第7)行);否則,將該節(jié)點(diǎn)的摘要和NHR加入VO(第8)行)。在R-tree上,則通過(guò)判斷節(jié)點(diǎn)的MBR是否與查詢范圍R相交。若與非葉子節(jié)點(diǎn)相交,則將該節(jié)點(diǎn)的孩子節(jié)點(diǎn)入棧(第11)～13)行);否則,將該節(jié)點(diǎn)的摘要和MBR加入VO(第14)行)。若與葉子節(jié)點(diǎn)相交,則將包含于范圍R內(nèi)的所有點(diǎn)加入結(jié)果集Result Set(第15)～17)行);否則,將位于范圍R外的所有點(diǎn)的摘要和MBR加入VO中。以圖4為例,查詢Q從MHGR-tree的根節(jié)點(diǎn)開(kāi)始迭代的訪問(wèn)與深色矩形范圍框相交的節(jié)點(diǎn){N,N3,N33,N34,R1,R2,R5,R6}(注:圖中只標(biāo)記了與Q相交的一棵R-tree,未標(biāo)記的R-tree的訪問(wèn)節(jié)點(diǎn)未列舉)。訪問(wèn)結(jié)束后,驗(yàn)證對(duì)象VO包括{(N1.H,N1.NHR),(N2.H,N2.NHR),(N4.H,N4.NHR),(N31.H,N31.NHR),(N32.H,N32.NHR),(R3.H,R3.MBR),(R4.H,R4.MBR)}和結(jié)果集{P5,P6,P7,P8}。服務(wù)提供商將VO、Result Set和根節(jié)點(diǎn)摘要簽名傳輸給客戶端。

2.4 查詢驗(yàn)證

在驗(yàn)證查詢結(jié)果時(shí),客戶端需要對(duì)結(jié)果進(jìn)行可靠性驗(yàn)證,主要包括以下兩個(gè)方面:1)完整性。所有被查詢范圍覆蓋的點(diǎn)P都包含在結(jié)果集Result Set中,沒(méi)有被遺漏。2)健壯性。返回的結(jié)果集中所包含的結(jié)果都是真實(shí)的結(jié)果,且沒(méi)有被篡改?？蛻舳私柚?yàn)證對(duì)象VO對(duì)查詢結(jié)果進(jìn)行上述兩方面的驗(yàn)證。

算法3 VO驗(yàn)證算法。

輸入:Result Set和VO。 輸出:Verification Result。

1)

for(從R-tree 的葉子層開(kāi)始至R-tree根節(jié)點(diǎn)所在層)

2)

計(jì)算R-tree每一層的節(jié)點(diǎn)的摘要至根節(jié)點(diǎn)

3)

for(從Grid-tree 的葉子層開(kāi)始至Grid-tree根節(jié)點(diǎn)所在層)

4)

計(jì)算Grid-tree每一層的節(jié)點(diǎn)的摘要至根節(jié)點(diǎn)

5)

利用DO的公鑰密匙解密MHGR-tree根節(jié)點(diǎn)摘要的簽名

6)

if(計(jì)算的根節(jié)點(diǎn)摘要與DO簽名的摘要匹配)

7)

return true

8)

else return false

算法3描述了查詢結(jié)果健壯性驗(yàn)證的過(guò)程。以圖3和圖4為例,客戶端首先掃描VO和Result Set,從R-tree的葉子層開(kāi)始,通過(guò){P5,P6}和{P7,P8}可以得到R5和R6的摘要和MBR。依次向上,通過(guò)VO中的{R3,R4}和計(jì)算的R5和R6可以得到R1和R2的摘要和MBR。最后計(jì)算得出R-tree根節(jié)點(diǎn)的摘要。在Grid-tree上,計(jì)算方法與R-tree類似,將R-tree節(jié)點(diǎn)的MBR用Grid-tree節(jié)點(diǎn)的Hilbert值范圍NHR替代,然后迭代計(jì)算MHGR-tree根節(jié)點(diǎn)的摘要,并與數(shù)據(jù)所有者簽名的摘要進(jìn)行匹配。而在完整性驗(yàn)證時(shí),需要判斷：1)Result Set中的每個(gè)點(diǎn)都在查詢范圍R內(nèi)；2)VO中的節(jié)點(diǎn)的NHR或MBR都不與查詢范圍R相交。

在驗(yàn)證查詢結(jié)果的完整性和健壯性時(shí),如果對(duì)于Result Set中的一點(diǎn)P被篡改,而P是計(jì)算根節(jié)點(diǎn)摘要時(shí)的組成部分,如果P的值是錯(cuò)誤的,根據(jù)哈希函數(shù)的無(wú)碰撞性,計(jì)算得到的MHGR-tree根節(jié)點(diǎn)摘要與DO簽名的摘要必然不匹配,故不滿足健壯性。如果對(duì)于一點(diǎn)P,P包含于查詢范圍R內(nèi),但Result Set不包含P,在滿足健壯性前提下,P包含于VO中,故不滿足完整性驗(yàn)證的條件。若P不包含于查詢范圍R內(nèi),但Result Set包含P,故也不滿足完整性驗(yàn)證的條件。

3 優(yōu)化策略

在驗(yàn)證查詢結(jié)果的可靠性時(shí),需要判斷VO中的Grid-tree的節(jié)點(diǎn)NHR不與查詢范圍的HR相交。如圖5所示,查詢Q所覆蓋網(wǎng)格對(duì)應(yīng)的Hilbert值范圍為[27, 28],查詢產(chǎn)生的Grid-tree上的驗(yàn)證對(duì)象VO為集合{N4,N34,N33,N324,N323,N322,N313,N314,N311,N2,N1}中每個(gè)節(jié)點(diǎn)的摘要和NHR,客戶端需要依次判斷節(jié)點(diǎn)NHR是否與查詢Q的HR相交。實(shí)際中,查詢范圍只覆蓋了少數(shù)的幾個(gè)網(wǎng)格,因此VO中包含了較多的冗余節(jié)點(diǎn),而造成驗(yàn)證時(shí)間變長(zhǎng)和驗(yàn)證效率下降。

圖5 基于Hilbert曲線的線性變化

于是,本文提出了一種優(yōu)化的過(guò)濾策略,通過(guò)該策略可以減少客戶端的比較次數(shù),縮短驗(yàn)證時(shí)間。從圖5可看出,每個(gè)空間網(wǎng)格都被Hilbert曲線遍歷并被賦予一個(gè)Hilbert值,從而將具有空間位置關(guān)系的網(wǎng)格轉(zhuǎn)換為一維線性位置關(guān)系的網(wǎng)格。在判斷節(jié)點(diǎn)與查詢Q是否相交時(shí),將空間坐標(biāo)的判斷轉(zhuǎn)換為一維Hilbert值的比較,從而也加快了比較的速度,縮短了驗(yàn)證時(shí)間。值得注意的是,通過(guò)Hilbert曲線的映射,每個(gè)空間網(wǎng)格間都具有一種線性關(guān)系,例如N4、N3和N2的Hilbert值范圍分別為[0, 15]、[16, 31]和[32, 47],它們之間的線性關(guān)系為N4

4 實(shí)驗(yàn)與分析

為了評(píng)價(jià)提出的MGR-tree和MHGR-tree的表現(xiàn),本文在一個(gè)真實(shí)的數(shù)據(jù)集CAR[7]上進(jìn)行測(cè)試,其中CAR為California的道路分割,包含了2 096 702個(gè)不同位置的坐標(biāo)點(diǎn)。在實(shí)驗(yàn)中,將這些坐標(biāo)點(diǎn)當(dāng)作不同物體的位置。實(shí)驗(yàn)在配置為IntelCore2DuoCPUE7500 2.93GHz和8GB內(nèi)存的WindowsXP系統(tǒng)上運(yùn)行。系統(tǒng)代碼用Java編寫,哈希函數(shù)采用160bit的SHA1算法,數(shù)字簽名采用128B的RSA算法。在構(gòu)建MGR-tree和MHGR-tree時(shí),Grid-tree的默認(rèn)的樹(shù)的高度為7,查詢范圍默認(rèn)為10%的空間覆蓋率,R-tree的節(jié)點(diǎn)大小設(shè)置為4 096B。

實(shí)驗(yàn)中,主要針對(duì)如下兩個(gè)方面進(jìn)行測(cè)試:1)查詢范圍對(duì)系統(tǒng)性能的影響;2)數(shù)據(jù)集大小對(duì)系統(tǒng)系能的影響；并且系統(tǒng)性能主要包含了VO的大小和驗(yàn)證時(shí)間等方面。

實(shí)驗(yàn)主要與文獻(xiàn)[7]方法(簡(jiǎn)稱MR)進(jìn)行對(duì)比,將本文提出的方法稱為MGR和MHGR。

隨著用戶查詢范圍的改變,系統(tǒng)性能會(huì)發(fā)生變化。實(shí)驗(yàn)中測(cè)試了當(dāng)查詢范圍在整個(gè)空間的1%至20%之間變化時(shí),VO大小和驗(yàn)證時(shí)間的變化,其中Grid-tree樹(shù)高h(yuǎn)=7,數(shù)據(jù)量大小為2×106。從圖6可以看出,當(dāng)查詢范圍很小時(shí),MGR和MHGR較MR表現(xiàn)出了一定的優(yōu)勢(shì),隨著查詢范圍的增大,這種優(yōu)勢(shì)更加明顯。尤其是,當(dāng)查詢范圍發(fā)生變化時(shí),MR的VO大小和驗(yàn)證時(shí)間發(fā)生明顯改變,而MGR和MHGR與之相反。例如,當(dāng)查詢范圍分別為1%和20%時(shí),MR的VO大小和驗(yàn)證時(shí)間的差值分別為756 KB和114 ms,而MHGR僅為474 KB和16 ms。值得注意的是,在最好情況下,MHGR的VO大小和驗(yàn)證時(shí)間僅為MR的63%和19%。

如圖7所示,當(dāng)數(shù)據(jù)量比較小時(shí),MGR和MHGR在查詢時(shí)間、VO大小和驗(yàn)證時(shí)間等方面已經(jīng)明顯比MR要好。當(dāng)數(shù)據(jù)量很大時(shí),MGR和MHGR的優(yōu)勢(shì)更加明顯,都保持了較低的水平。尤其是當(dāng)數(shù)據(jù)量為400 000時(shí),MHGR的VO大小和驗(yàn)證時(shí)間僅為MR的33%和26%。

圖6 查詢范圍對(duì)不同算法在系統(tǒng)性能方面的影響(h=7,|D|=2×106)

圖7 數(shù)據(jù)量對(duì)不同算法在系統(tǒng)性能方面的影響(h=7,r=10%)

5 結(jié)語(yǔ)

隨著移動(dòng)互聯(lián)網(wǎng)絡(luò)的普及和高速發(fā)展,例如4G網(wǎng)絡(luò)等,極大地推動(dòng)了基于位置服務(wù)(LBS)的進(jìn)展。而面對(duì)客戶日益復(fù)雜的查詢服務(wù)需求,數(shù)據(jù)所有者已無(wú)法滿足要求。為了更好地解決這個(gè)矛盾,將數(shù)據(jù)庫(kù)外包給LBS提供商成為了必然的選擇。但是,在LBS提供商給客戶提供更高級(jí)的查詢服務(wù)的同時(shí),由于LBS提供商是不受信任的,為了提供可靠的查詢服務(wù),LBS服務(wù)商應(yīng)以一種可驗(yàn)證的方式提供查詢服務(wù),即客戶可以對(duì)查詢結(jié)果進(jìn)行可靠性驗(yàn)證。在大數(shù)據(jù)的背景下,如何快速響應(yīng)查詢服務(wù)請(qǐng)求,以較小的數(shù)據(jù)傳輸代價(jià)給客戶提供更可靠的查詢結(jié)果變得至關(guān)重要。針對(duì)上述問(wèn)題,提出新的索引結(jié)構(gòu)MGR-tree,結(jié)合了Grid-tree和R-tree的特點(diǎn),極大地改善了VO過(guò)于龐大的問(wèn)題,降低了服務(wù)提供商和客戶之間的傳輸消耗,并且有效地縮短了驗(yàn)證時(shí)間；在此基礎(chǔ)上,通過(guò)Hilbert的降維特性,還提出了優(yōu)化的MHGR-tree,并提出了一種過(guò)濾策略,有效地改善了系統(tǒng)性能。實(shí)驗(yàn)結(jié)果表明,在數(shù)據(jù)量和查詢范圍都比較大時(shí),MGR-tree和MHGR-tree在VO大小和驗(yàn)證時(shí)間等方面都表現(xiàn)出了明顯的優(yōu)勢(shì)。

References)

[1] DEVANBU P, GERTZ M, MARTEL C, et al. Authentic third-party data publication[M]// THURAISINGHAM B, VAN DE RIET R, DITTRICH K R, et al. Data and Application Security. Berlin: Springer, 2000: 101-112.

[2] MERKLE R C. A certified digital signature [C]// CRYPTO 1989: Proceedings on Advances in Cryptology. Berlin: Springer, 1989: 218-238.

[3] PANG H H, TAN K L. Authenticating query results in edge computing [C]// Proceedings of the 20th International Conference on Data Engineering. Piscataway, NJ: IEEE, 2004: 560-571.

[4] PANG H H, JAIN A, RAMAMRITHAM K, et al. Verifying completeness of relational query results in data publishing[C]// SIGMOD 2005: Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2005: 407-418.

[5] NARASIMHA M, TSUDIK G. DSAC: integrity of outsourced databases with signature aggregation and chaining [C]// CIKM 2005: Proceedings of the 14th ACM International Conference on Information and Knowledge Management. New York: ACM, 2005: 235-236.

[6] CHENG W, PANG H H, TAN K. Authenticating multi-dimensional query results in data publishing [C]// DBSEC 2006: Proceedings of the 20th IFIP WG 11.3 Working Conference on Data and Applications Security. Berlin: Springer, 2006: 60-73.

[7] LI F, HADJIELEFTHERIOU M, KOLLIOS G, et al. Dynamic authenticated index structures for outsourced databases [C]// SIGMOD 2006: Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2006: 121-132.

[8] YANG Y, PAPADOPOULOS S, PAPADIAS D, et al. Authenticated indexing for outsourced spatial databases [J]. The VLDB Journal, 2009, 18(3): 631-648.

[9] YANG Y, PAPADOPOULOS S, PAPADIAS D, et al. Spatial outsourcing for location-based services [C]// ICDE 2008: Proceedings of the 2008 IEEE 24th International Conference on Data Engineering. Washington, DC: IEEE Computer Society, 2008: 1082-1091.

[10] MOURATIDIS K, SACHARIDIS D, PANG H H. Partially materialized digest scheme: an efficient verification method for outsourced databases [J]. The VLDB Journal, 2009, 18(1): 363-381.

[11] 謝晴晴, 王良民.基于PMD的外包數(shù)據(jù)流范圍查詢驗(yàn)證方案[J]. 計(jì)算機(jī)科學(xué)與探索, 2015, 9(10): 1209-1218.(XIE Q Q, WANG L M. Data stream range query authentication scheme based on PMD in outsourced database[J]. Journal of Frontiers of Computer Science and Technology, 2015, 9(10): 1209-1218.)

[12] HU H, XU J, CHEN G, et al. Authenticating location-based services without compromising location privacy [C]// SIGMOD 2012: Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2012: 301-312.

This work is partially supported by the National Natural Science Foundation of China (61462056,71363040), the Natural Science Foundation of Inner Mongolia (2016MS0609).

HU Xiaoyan, born in 1980, M. S., lecturer. Her research interests include cloud computing, database management.

WANG Jingyu, born in 1976, Ph. D., associate professor. His research interests include cloud computing, information security.

LI Hairong, born in 1976, M. S., associate professor. Her research interests include cloud storage.

Range query authentication for outsourced spatial databases

HU Xiaoyan1*, WANG Jingyu2, LI Hairong1

(1. Engineering Training Center, Inner Mongolia University of Science and Technology, Baotou Nei Mongol 014010, China;2. Information and Network Center, Inner Mongolia University of Science and Technology, Baotou Nei Mongol 014010, China)

In existing spatial range query authenticating methods such as VR-tree and MR-tree, the transmission cost of the server to the client is high and the verification efficiency of the client is low because the Verification Object (VO) contains too much authentication information. To resolve these problems, a new index structure MGR-tree was proposed. First of all, by means of embedding a R-tree in each leaf node of Grid-tree, the size of VO decreased, and the efficiency of query and authentication was improved. In addition, an optimal index MHGR-tree which takes advantage of the property of Hilbert curve and a filter policy were proposed to accelerate the verification. Experimental results show that the proposed method has a better performance compared with MR-tree. In the best case, the verification object size and authentication time of MHGR are 63% and 19% of MR respectively.

mobile Internet; location-based service; database outsourcing; query authentication; Verification Object (VO)

2016- 10- 31;

2016- 12- 20。

國(guó)家自然科學(xué)基金資助項(xiàng)目(61462056,71363040);內(nèi)蒙古自然科學(xué)基金資助項(xiàng)目(2016MS0609)。

胡曉燕(1980—),女,內(nèi)蒙古涼城人,講師,碩士,主要研究方向:云計(jì)算、數(shù)據(jù)庫(kù)管理; 王靜宇(1976—),男,河南開(kāi)封人,副教授,博士,CCF會(huì)員,主要研究方向:云計(jì)算、信息安全; 李海榮(1976—),女,內(nèi)蒙古巴彥淖爾人,副教授,碩士,主要研究方向:云存儲(chǔ)。

1001- 9081(2017)04- 1021- 05

10.11772/j.issn.1001- 9081.2017.04.1021

TP311

A