云計(jì)算中偏好top-k查詢的正確性驗(yàn)證

盛 剛，溫 濤，郭 權(quán)，印 瑩

（1.東北大學(xué)軟件中心，沈陽(yáng)110819；2.大連東軟信息學(xué)院遼寧省網(wǎng)絡(luò)安全與計(jì)算技術(shù)重點(diǎn)實(shí)驗(yàn)室，遼寧大連116023；3.東北大學(xué)信息科學(xué)與工程學(xué)院，沈陽(yáng)110819）

在云計(jì)算環(huán)境中，數(shù)據(jù)所有者將數(shù)據(jù)管理任務(wù)委托給云服務(wù)提供商。云服務(wù)提供商端的數(shù)據(jù)可能會(huì)遭到攻擊或者不忠實(shí)地執(zhí)行查詢，從而返回給客戶不正確的結(jié)果，因此，在向客戶返回查詢結(jié)果的同時(shí)還要返回驗(yàn)證對(duì)象以檢驗(yàn)查詢結(jié)果的正確性。

本文提出了云計(jì)算中偏好top-k查詢結(jié)果的正確性驗(yàn)證問(wèn)題。查詢結(jié)果的正確性包括兩方面：①查詢結(jié)果完全來(lái)自數(shù)據(jù)所有者，沒(méi)有被篡改、不是偽造的；②查詢結(jié)果中的數(shù)據(jù)沒(méi)有遺漏。

偏好top-k查詢根據(jù)客戶指定的評(píng)分規(guī)則計(jì)算得分最高的前k個(gè)數(shù)據(jù)。偏好top-k查詢具有廣泛的應(yīng)用領(lǐng)域，如Web搜索、數(shù)據(jù)挖掘等，已取得了豐富的研究成果［1］，如Onion［2］、Prefer［3］和DG［4］等。

在偏好top-k查詢的研究成果中，DG的效率較高并且呈現(xiàn)為規(guī)則的數(shù)據(jù)結(jié)構(gòu)。作者以DG為基礎(chǔ)提出了基于哈希的驗(yàn)證支配圖（Authenticated dominant graph with Hash，ADG-H）和基于數(shù)字簽名的驗(yàn)證支配圖（Authenticated dominant graph with signature，ADG-S）。ADG-H能有效地驗(yàn)證一次性偏好top-k查詢結(jié)果的正確性，但對(duì)于連續(xù)監(jiān)控，在更新頻繁和連續(xù)監(jiān)控?cái)?shù)量大的情況下會(huì)引起大量的網(wǎng)絡(luò)傳輸。而ADG-S，只有當(dāng)數(shù)據(jù)更新影響到連續(xù)監(jiān)控結(jié)果或驗(yàn)證對(duì)象時(shí)才與客戶進(jìn)行必要的網(wǎng)絡(luò)傳輸，大大減少了網(wǎng)絡(luò)傳輸量。

1 相關(guān)文獻(xiàn)

Zou Lei等［4］提出了支配圖（Dominant graph，DG）的概念，根據(jù)數(shù)據(jù)間的支配關(guān)系構(gòu)建支配圖。與其他偏好top-k查詢方法相比，支配圖具有查詢空間小、查詢速度快的特點(diǎn)［4］。

Hacigumus等［5］在ICDE 2002提出數(shù)據(jù)庫(kù)服務(wù)模型，可以認(rèn)為是云計(jì)算框架的一個(gè)組成部分。Merkle R首次提出了MH-Tree［6］，后來(lái)被用在對(duì)外包數(shù)據(jù)庫(kù)中的查詢結(jié)果進(jìn)行正確性驗(yàn)證［7］。查詢結(jié)果正確性驗(yàn)證研究領(lǐng)域中有眾多研究成果［8－13］，與本文最相關(guān)的是最鄰近查詢結(jié)果的驗(yàn)證。文獻(xiàn)［12］提出了MR-Tree用以驗(yàn)證最鄰近查詢結(jié)果的正確性，文獻(xiàn)［13］提出AMN和C-AMN對(duì)多步最鄰近查詢結(jié)果進(jìn)行驗(yàn)證。但最鄰近查詢與偏好top-k查詢?cè)趯?shí)現(xiàn)原理上有很大的不同，因此不能使用最鄰近查詢的驗(yàn)證方法對(duì)偏好top-k查詢進(jìn)行驗(yàn)證。

在連續(xù)監(jiān)控結(jié)果驗(yàn)證的研究領(lǐng)域中，文獻(xiàn)［14］提出了REF和CADS對(duì)外包數(shù)據(jù)庫(kù)普通查詢的連續(xù)監(jiān)控結(jié)果進(jìn)行正確性驗(yàn)證，有數(shù)據(jù)更新發(fā)生時(shí)向用戶發(fā)送新的驗(yàn)證對(duì)象，以確保用戶的結(jié)果是最新的。該文獻(xiàn)基于普通關(guān)系數(shù)據(jù)庫(kù)，其內(nèi)在機(jī)制與偏好top-k查詢及支配圖截然不同，提出的方法亦不適用于偏好top-k查詢的正確性驗(yàn)證。

2 基本概念與符號(hào)

相關(guān)符號(hào)及其含義為：D表示整個(gè)數(shù)據(jù)集；N表示支配圖中的節(jié)點(diǎn)；RS表示top-k查詢的結(jié)果集；R表示查詢結(jié)果集中的一個(gè)結(jié)果；VO表示驗(yàn)證對(duì)象；P（N）表示節(jié)點(diǎn)N的父節(jié)點(diǎn)集合；C（N）表示節(jié)點(diǎn)N的子節(jié)點(diǎn)集合。

接下來(lái)給出幾個(gè)定義，設(shè)N1、N2、N3為3個(gè)數(shù)據(jù)（在不引起混淆的情況下，也稱(chēng)數(shù)據(jù)為節(jié)點(diǎn)），每個(gè)數(shù)據(jù)都有相同數(shù)目的若干個(gè)分量。

定義1 支配［4］：兩個(gè)節(jié)點(diǎn)N1和N2，如果N1的每個(gè)分量都大于等于N2相應(yīng)的分量，并且至少有一個(gè)分量大于N2相應(yīng)的分量，則稱(chēng)N1支配N(xiāo)2。

定義2 支配圖［4］：按照數(shù)據(jù)間的支配關(guān)系，將互不支配的數(shù)據(jù)放在一層，將被支配的數(shù)據(jù)放在下一層，這樣構(gòu)建的結(jié)構(gòu)稱(chēng)為支配圖。

定義3 父節(jié)點(diǎn)：如果N1支配N(xiāo)2，則在支配圖中，N1為N2的父節(jié)點(diǎn)。

定義4 子節(jié)點(diǎn)：如果N1支配N(xiāo)2，則在支配圖中，N2為N1的子節(jié)點(diǎn)。

定義5 兄弟節(jié)點(diǎn)：如果N1支配N(xiāo)2和N3，則在支配圖中，N2和N3為兄弟節(jié)點(diǎn)。

例如，設(shè)N1＝（5，10），N2＝（1，8），N3＝（5，3），N4＝（6，7），構(gòu)建的支配圖如圖1所示。

圖1 節(jié)點(diǎn)間支配關(guān)系示意圖Fig.1 Example of dominance relationship between nodes

在圖1中，N1支配N(xiāo)2和N3，N1為N2和N3的父節(jié)點(diǎn)，N2和N3為N1的子節(jié)點(diǎn)，N2和N3互不支配、互為兄弟節(jié)點(diǎn)；N1和N4互不支配、互為兄弟節(jié)點(diǎn)，N4支配N(xiāo)3，N4為N3的父節(jié)點(diǎn)，N3為N4的子節(jié)點(diǎn)。

3 基于哈希的驗(yàn)證支配圖

為對(duì)云計(jì)算中偏好top-k的查詢結(jié)果進(jìn)行正確性驗(yàn)證，在支配圖的基礎(chǔ)上提出了ADG-H。

3.1 ADG-H的構(gòu)建

構(gòu)建ADG-H時(shí)，需要在DG構(gòu)建過(guò)程的基礎(chǔ)上計(jì)算節(jié)點(diǎn)哈希值，對(duì)根節(jié)點(diǎn)進(jìn)行數(shù)字簽名并為以后驗(yàn)證對(duì)象的提取工作做準(zhǔn)備，步驟如下：

（1）運(yùn)用DG構(gòu)建算法構(gòu)建ADG-H。與DG不同的是，ADG-H為每個(gè)節(jié)點(diǎn)增加一個(gè)哈希值項(xiàng)。

（2）增加根節(jié)點(diǎn)層。ADG-H的頂層現(xiàn)為L(zhǎng)ayer 1，為方便以后驗(yàn)證對(duì)象的提取，在Layer 1前增加一層Layer 0，并為該層增加一個(gè)節(jié)點(diǎn)Nroot作為整個(gè)ADG-H的根節(jié)點(diǎn)，Layer 1中所有節(jié)點(diǎn)皆為其子節(jié)點(diǎn)，該節(jié)點(diǎn)各分量的值置為整數(shù)或浮點(diǎn)數(shù)中的最大值。Nroot及其值為參與運(yùn)算的各方所共享。

（3）計(jì)算哈希值。從ADG-H的最后一層依次向前直至Layer 0，為每層中的每個(gè)節(jié)點(diǎn)計(jì)算哈希值，如果某節(jié)點(diǎn)沒(méi)有子節(jié)點(diǎn)，則該節(jié)點(diǎn)的哈希值為其值的哈希；如果有子節(jié)點(diǎn)，則該節(jié)點(diǎn)的哈希值為其值與其所有子節(jié)點(diǎn)的哈希值的連接的哈希，連接時(shí)按照子節(jié)點(diǎn)的序號(hào)從小到大排列。

（4）數(shù)字簽名。對(duì)Nroot的哈希值（記為hroot）進(jìn)行數(shù)字簽名，得到sig（hroot）。

3.2 ADG-H的數(shù)據(jù)更新

在ADG-H中，當(dāng)插入、刪除、修改等數(shù)據(jù)更新發(fā)生時(shí)需要進(jìn)行數(shù)據(jù)更新和哈希更新。數(shù)據(jù)更新按照DG更新算法進(jìn)行；隨后進(jìn)行哈希更新，重新計(jì)算在數(shù)據(jù)更新階段受影響的各節(jié)點(diǎn)的哈希值。

以插入為例，首先進(jìn)行數(shù)據(jù)更新。設(shè)要插入的數(shù)據(jù)為NI，首先按照DG的插入算法執(zhí)行插入：經(jīng)過(guò)搜索，NI應(yīng)該插入到Layer d中，將Layer d中受NI支配的節(jié)點(diǎn)插入到Layer d＋1中，對(duì)Layer d＋1及以后的各層做相同處理，設(shè)最終受影響的層為L(zhǎng)ayer u。簡(jiǎn)要插入算法見(jiàn)算法1，詳見(jiàn)文獻(xiàn)［4］。

算法1 Insert Algorithm.

輸入：DG；要插入的節(jié)點(diǎn)NI；

輸出：NI所在層d；插入到最后一層的節(jié)點(diǎn)集合S；最終影響的層編號(hào)u；

①初始化：建立兩個(gè)空集合S和T；

②經(jīng)過(guò)搜索，NI應(yīng)該插入到Layer d中；S＝｛NI｝；m＝d；

③將集合S中每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)放到T中；

④將T中的每個(gè)節(jié)點(diǎn)從Layer m中刪除；

⑤將S中的節(jié)點(diǎn)插入Layer m中，重新計(jì)算Layer m－1和Layer m兩層節(jié)點(diǎn)間父子關(guān)系；

⑥如果T為空，插入過(guò)程結(jié)束，轉(zhuǎn)⑦；否則，清空S，將T中節(jié)點(diǎn)放到S中，m加1，如果m值大于當(dāng)前DG最后一層的編號(hào)，新建一層Layer m，轉(zhuǎn)至③；

⑦插入過(guò)程結(jié)束，u＝m，返回S、d和u。

數(shù)據(jù)插入完成后進(jìn)行哈希更新，見(jiàn)算法2。首先計(jì)算插入到Layer u中的節(jié)點(diǎn)的哈希值，然后計(jì)算這些節(jié)點(diǎn)的父節(jié)點(diǎn)的哈希值，依次向前逐層更新各層中受影響的節(jié)點(diǎn)的父節(jié)點(diǎn)的哈希值，直至最后到達(dá)根節(jié)點(diǎn)Nroot，更新Nroot的哈希值。

算法2 Update Hash Algorithm.

輸入：DG；節(jié)點(diǎn)集合S；

輸出：根節(jié)點(diǎn)的數(shù)字簽名sig（hroot）；哈希值更新過(guò)的節(jié)點(diǎn)集合U；

①初始化：建立空集合T，U；

②重新計(jì)算S中每個(gè)節(jié)點(diǎn)的哈希值；U＝U∪S；

③將S中每個(gè)節(jié)點(diǎn)的所有父節(jié)點(diǎn)放到T中；

④清空S，將T中所有節(jié)點(diǎn)放到S中，清空T；

⑤如果S不為空，轉(zhuǎn)至②；

⑥重新計(jì)算根節(jié)點(diǎn)的數(shù)字簽名sig（hroot）；

⑦哈希值更新過(guò)程結(jié)束，返回sig（hroot）和U。

ADG-H中的刪除和修改與插入的過(guò)程類(lèi)似，首先執(zhí)行DG中的刪除和修改算法，將最后一層中受影響的節(jié)點(diǎn)返回，然后執(zhí)行算法2，更新相關(guān)節(jié)點(diǎn)的哈希值并重新計(jì)算根節(jié)點(diǎn)的數(shù)字簽名。

3.3 ADG-H中的查詢和驗(yàn)證對(duì)象的提取

收到客戶端查詢請(qǐng)求后，服務(wù)提供商端執(zhí)行查詢算法得到查詢結(jié)果RS。但是由于服務(wù)提供商端可能會(huì)遭到攻擊，數(shù)據(jù)可能會(huì)被篡改，服務(wù)器也可能由于某種原因而沒(méi)有忠實(shí)地執(zhí)行查詢，導(dǎo)致客戶端可能收到不正確的查詢結(jié)果。這就需要服務(wù)提供商根據(jù)RS從ADG-H中提取驗(yàn)證對(duì)象VO，以供客戶用來(lái)對(duì)RS的正確性進(jìn)行驗(yàn)證。

設(shè)RS為｛Nroot，R1，R2，…，Rk｝，為了表達(dá)順暢，RS中的Nroot也記為R0，即RS表示為｛R0，R1，R2，…，Rk｝，從R0到Rk按照得分從高到低排序。在MH-Tree和MR-Tree的查詢結(jié)果中一定存在葉子節(jié)點(diǎn)，而驗(yàn)證支配圖的查詢結(jié)果中則可能不存在葉子節(jié)點(diǎn)，因此，ADG-H中驗(yàn)證對(duì)象的提取與MH-Tree和MR-Tree相比更為復(fù)雜一些。

從驗(yàn)證支配圖中提取的驗(yàn)證對(duì)象只要能夠同時(shí)滿足真實(shí)性和有效性，即可以實(shí)現(xiàn)對(duì)RS的驗(yàn)證。

真實(shí)性：對(duì)于Rm∈RS，m為整數(shù)，且0≤m≤k，Rm為真實(shí)的、來(lái)自數(shù)據(jù)所有者，沒(méi)有被篡改、不是偽造的。

有效性：對(duì)于R0∈RS，R0為整個(gè)支配圖中得分最高的點(diǎn)；對(duì)于Rm＋1∈RS，m為整數(shù)，且0≤m＜k，Rm＋1為整個(gè)支配圖中Rm后得分最高的點(diǎn)。

為滿足真實(shí)性和有效性要求，經(jīng)過(guò)對(duì)驗(yàn)證對(duì)象的提取過(guò)程進(jìn)行觀察和分析，給出定理1用以指導(dǎo)驗(yàn)證對(duì)象的提取。

定理1 對(duì)于偏好top-k查詢結(jié)果RS中的每個(gè)節(jié)點(diǎn)R，將R的所有子節(jié)點(diǎn)放到VO中，可以同時(shí)滿足真實(shí)性和有效性。

證明（真實(shí)性） 在驗(yàn)證時(shí)，結(jié)合VO，從RS中處于最后一層的節(jié)點(diǎn)開(kāi)始逐層計(jì)算各層節(jié)點(diǎn)的哈希值，用最終得到的R0的哈希值對(duì)數(shù)字簽名進(jìn)行驗(yàn)證。如果驗(yàn)證通過(guò)，表明返回的RS和VO中所有節(jié)點(diǎn)的值為正確的；否則表明RS或VO中存在不正確的節(jié)點(diǎn)。證畢。

證明（有效性） 當(dāng)m＝0時(shí)，考慮R0。節(jié)點(diǎn)R0即Nroot的值為參與計(jì)算的各方所共知，且R0的值是整個(gè)支配圖中最大的，顯而易見(jiàn)，對(duì)所有查詢R0都必然在RS中。

當(dāng)m＝1時(shí)，考慮R1。由于Layer 0中只有一個(gè)節(jié)點(diǎn)R0，則R1必然在Layer 1中，且為R0的子節(jié)點(diǎn)。由于已經(jīng)將R0的所有子節(jié)點(diǎn)放到VO中，可以計(jì)算出R0的每個(gè)子節(jié)點(diǎn)的得分，能夠表明R1為R0后整個(gè)支配圖中得分最高的點(diǎn)。

當(dāng)m＝2時(shí)，考慮R2。可以區(qū)分為兩種情況：①R2為R0的子節(jié)點(diǎn)；②R2為R1的子節(jié)點(diǎn)。根據(jù)支配圖的原理，如果某節(jié)點(diǎn)在RS中，則該節(jié)點(diǎn)至少有一個(gè)父節(jié)點(diǎn)在RS中［4］。而在RS中，R2前只有R0和R1，R2要么為R0的子節(jié)點(diǎn)，要么為R1的子節(jié)點(diǎn)，不存在第三種情況。因此，不論R2為R0或R1的子節(jié)點(diǎn)，在處理R0和R1時(shí)已經(jīng)將R0和R1的所有子節(jié)點(diǎn)放到VO中，所以能夠表明R2為R1后整個(gè)支配圖中得分最高的點(diǎn)。

當(dāng)2＜m≤k時(shí)，對(duì)于Rm。Rm必然為｛Ri｜ 0≤i≤m－1｝中某節(jié)點(diǎn)的子節(jié)點(diǎn)，此m個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)都已經(jīng)放到VO中，所以能夠表明Rm為Rm－1后整個(gè)支配圖中得分最高的點(diǎn)。證畢。

重畫(huà)的文獻(xiàn)［4］中的圖1如圖2所示，其中圖2（a）為數(shù)據(jù)集，圖2（b）為增加了根節(jié)點(diǎn)Nroot的DG，根節(jié)點(diǎn)編號(hào)為－1，所在層為L(zhǎng)ayer 0。

用函數(shù)F＝0.6＊X＋0.4＊Y進(jìn)行top-2查詢，RS為｛－1，4，6｝，VO為｛－1（3，4，11），4（1，6），6（2）｝。

用函數(shù)F＝0.5＊X＋0.5＊Y進(jìn)行top-4查詢，RS為｛－1，4，3，6，11｝，VO為｛－1（3，4，11），4（1，6），3（1，5），6（2），11（1）｝。

圖2 支配圖示例Fig.2 Example of dominant graph

4 基于數(shù)字簽名的驗(yàn)證支配圖

一次性查詢是指客戶向服務(wù)提供商提交查詢后，服務(wù)提供商立即執(zhí)行查詢并將查詢結(jié)果和驗(yàn)證對(duì)象返回給客戶，查詢結(jié)束。連續(xù)監(jiān)控是指客戶向服務(wù)提供商注冊(cè)查詢后，服務(wù)提供商首先執(zhí)行查詢，并將查詢結(jié)果和驗(yàn)證對(duì)象返回給客戶，再對(duì)以后的數(shù)據(jù)更新進(jìn)行監(jiān)控，如果數(shù)據(jù)更新影響到查詢結(jié)果或驗(yàn)證對(duì)象，將受影響的查詢結(jié)果和驗(yàn)證對(duì)象返回給客戶，直至客戶注銷(xiāo)該連續(xù)監(jiān)控為止。

根據(jù)算法2，每次數(shù)據(jù)更新之后ADG-H根節(jié)點(diǎn)的數(shù)字簽名都會(huì)隨之更新。不論數(shù)據(jù)更新是否影響到監(jiān)控查詢的結(jié)果，至少需要發(fā)起一次網(wǎng)絡(luò)傳輸將最新的根節(jié)點(diǎn)的數(shù)字簽名發(fā)送給客戶。如果有較多的連續(xù)監(jiān)控和較頻繁的數(shù)據(jù)更新，會(huì)引起大量的網(wǎng)絡(luò)傳輸，也加大了服務(wù)器端的負(fù)擔(dān)。

為減少網(wǎng)絡(luò)傳輸量，作者提出了ADG-S。以DG為基礎(chǔ)，ADG-S為各節(jié)點(diǎn)增加數(shù)字簽名。

ADG-S的構(gòu)建過(guò)程與ADG-H類(lèi)似，不同的是：①ADG-S的每個(gè)節(jié)點(diǎn)中存放的是數(shù)字簽名；②對(duì)沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)直接對(duì)其值進(jìn)行數(shù)字簽名，對(duì)有子節(jié)點(diǎn)的節(jié)點(diǎn)則對(duì)節(jié)點(diǎn)的值和其子節(jié)點(diǎn)的值的連接進(jìn)行數(shù)字簽名。

4.1 ADG-S的更新

在ADG-S中，當(dāng)插入、刪除、修改等數(shù)據(jù)更新發(fā)生時(shí)，同樣需要進(jìn)行兩種類(lèi)型更新：數(shù)據(jù)更新和數(shù)字簽名更新。數(shù)據(jù)更新按照DG的更新算法執(zhí)行；數(shù)字簽名更新重新計(jì)算數(shù)據(jù)更新階段受影響的節(jié)點(diǎn)的數(shù)字簽名。

以插入為例。首先更新數(shù)據(jù)。設(shè)插入數(shù)據(jù)為NI，執(zhí)行算法1后，得到NI所在層的編號(hào)d、最終影響到的層編號(hào)u和插入到最后一層的節(jié)點(diǎn)集合S。然后更新數(shù)字簽名，重新計(jì)算在插入過(guò)程中受影響的節(jié)點(diǎn)的數(shù)字簽名，見(jiàn)算法3。先計(jì)算插入到Layer u中的節(jié)點(diǎn)的數(shù)字簽名，然后計(jì)算這些節(jié)點(diǎn)的父節(jié)點(diǎn)的數(shù)字簽名，逐層計(jì)算各層中受影響的節(jié)點(diǎn)的父節(jié)點(diǎn)的數(shù)字簽名，直至最后到達(dá)Layer d－1，更新NI的父節(jié)點(diǎn)數(shù)字簽名，數(shù)字簽名更新結(jié)束。算法3的時(shí)間復(fù)雜度在最壞情況下為O（｜D｜），即將驗(yàn)證圖中每個(gè)節(jié)點(diǎn)的數(shù)字簽名重新計(jì)算一次。

算法3 UpdateSignature Algorithm.

輸入：Insert算法的返回值S和d

輸出：新計(jì)算過(guò)數(shù)字簽名的節(jié)點(diǎn)集合P

①初始化：建立兩個(gè)空集合P和T，設(shè)變量m為S中節(jié)點(diǎn)所在層的編號(hào)；

②重新計(jì)算S中每個(gè)節(jié)點(diǎn)的數(shù)字簽名，P＝P∪S；

③將S中每個(gè)節(jié)點(diǎn)的所有父節(jié)點(diǎn)放到T中；

④清空S，將T中節(jié)點(diǎn)放到S中；

⑤如果m等于d－1，數(shù)字簽名更新結(jié)束，轉(zhuǎn)⑥；否則m減1，轉(zhuǎn)②；

⑥返回集合P。

計(jì)算節(jié)點(diǎn)N的數(shù)字簽名時(shí)，如果N已有數(shù)字簽名，需將現(xiàn)有的數(shù)字簽名作為N值的一部分參與計(jì)算。這樣，如果多次更新影響到某連續(xù)監(jiān)控的結(jié)果或驗(yàn)證對(duì)象，但服務(wù)器端沒(méi)有將某次更新發(fā)送給用戶，客戶會(huì)檢測(cè)到。

ADG-S中的刪除和修改與插入類(lèi)似，首先執(zhí)行刪除和修改算法，然后執(zhí)行算法3，重新計(jì)算刪除和修改過(guò)程中受影響的相關(guān)節(jié)點(diǎn)的數(shù)字簽名。

4.2 ADG-S處理連續(xù)監(jiān)控

定理1對(duì)使用ADG-S時(shí)驗(yàn)證對(duì)象的提取依然適用。用戶注冊(cè)連續(xù)監(jiān)控后，服務(wù)提供商執(zhí)行查詢算法，并提取驗(yàn)證對(duì)象，保存查詢結(jié)果和驗(yàn)證對(duì)象，并將查詢結(jié)果和驗(yàn)證對(duì)象發(fā)送到Client。在以后的數(shù)據(jù)更新過(guò)程中，如果某次更新影響到某監(jiān)控的結(jié)果或驗(yàn)證對(duì)象，則將受影響的節(jié)點(diǎn)信息發(fā)送到相應(yīng)的Client，否則不發(fā)送任何信息。與ADG-H相比，ADG-S只有在必要時(shí)才發(fā)送信息，大大減少了不必要的網(wǎng)絡(luò)傳輸。

5 實(shí)驗(yàn)驗(yàn)證

試驗(yàn)環(huán)境為Intel Core2 1.6 GHz，2 GB內(nèi)存的PC機(jī)，用Java語(yǔ)言實(shí)現(xiàn)了所用的數(shù)據(jù)結(jié)構(gòu)和算法，實(shí)驗(yàn)中隨機(jī)生成了呈均勻分布的數(shù)據(jù)集。實(shí)驗(yàn)以DG為基準(zhǔn)，比較ADG-H和ADG-S在構(gòu)建和更新兩方面的性能。比較ADG-H和ADGS在連續(xù)監(jiān)控方面的性能。由于DG、ADG-H和ADG-S具有相同的搜索空間，ADG-H和ADG－S具有相同的查詢時(shí)間和驗(yàn)證對(duì)象大小，不再進(jìn)行比較。

5.1 構(gòu)建實(shí)驗(yàn)

構(gòu)建實(shí)驗(yàn)以DG的構(gòu)建時(shí)間為基準(zhǔn)，結(jié)果如圖3所示。由于MD5的效率較高，選用MD5作為哈希函數(shù)構(gòu)建ADG-H，所用時(shí)間略多于DG，只有數(shù)據(jù)量很大時(shí)構(gòu)建ADG-H所用時(shí)間才明顯多于DG。構(gòu)建ADG-S時(shí)選用RSA作為數(shù)字簽名方案，由于RSA數(shù)字簽名方案代價(jià)較高，所用時(shí)間明顯比DG和ADG-H都多。

圖3 構(gòu)建時(shí)間比較Fig.3 Comparison of construction time

5.2 更新實(shí)驗(yàn)

更新實(shí)驗(yàn)同樣以DG的更新數(shù)據(jù)為基準(zhǔn)，圖4為插入所用時(shí)間，圖5為刪除所用時(shí)間。可以看出，ADG-H的更新時(shí)間比DG多，ADG-S的更新時(shí)間最多。

5.3 連續(xù)監(jiān)控實(shí)驗(yàn)

圖6為不同查詢比較，設(shè)k＝200，F(xiàn)1＝（0.3，0.7），F(xiàn)2＝（0.9，0.1），F(xiàn)3＝（0.5，0.5）?？梢钥闯?，ADG-H中，每一次更新都會(huì)影響連續(xù)監(jiān)控的驗(yàn)證對(duì)象，從而引起一次網(wǎng)絡(luò)傳輸；ADG-S中，只有當(dāng)本次更新影響到連續(xù)監(jiān)控的結(jié)果或驗(yàn)證對(duì)象時(shí)，才進(jìn)行一次網(wǎng)絡(luò)傳輸，網(wǎng)絡(luò)傳輸量明顯比ADG-H少得多。圖7為不同k，對(duì)k分別取100、200、500，設(shè)F＝（0.5，0.5），可以看出k越大，ADG-S中網(wǎng)絡(luò)更新次數(shù)越多。

圖4 插入所用時(shí)間Fig.4 Wasted time of inserting

圖5 刪除所用時(shí)間Fig.5 Wasted time of deleting

圖6 不同查詢比較Fig.6 Comparison of different query

圖7 不同k比較Fig.7 Comparison of different k

6 結(jié)束語(yǔ)

在支配圖的基礎(chǔ)上提出了ADG-H和ADGS兩種驗(yàn)證圖以解決云計(jì)算環(huán)境下偏好top-k查詢結(jié)果的正確性驗(yàn)證問(wèn)題。ADG-H能夠有效地驗(yàn)證一次性top-k查詢結(jié)果的正確性。ADG-S能夠有效地驗(yàn)證連續(xù)監(jiān)控結(jié)果的正確性。與ADGH相比，ADG-S只有當(dāng)數(shù)據(jù)更新影響到連續(xù)監(jiān)控的結(jié)果或驗(yàn)證對(duì)象時(shí)才發(fā)起網(wǎng)絡(luò)傳輸，向用戶發(fā)送最新結(jié)果，大大減少了網(wǎng)絡(luò)傳輸量，同時(shí)也降低了服務(wù)提供商端客戶端的負(fù)擔(dān)。我們未來(lái)將繼續(xù)研究如何提高ADG-S的更新效率，并對(duì)云計(jì)算環(huán)境下偏好top-k查詢的隱私保護(hù)進(jìn)行研究。

［1］Ilyas Ihab F，Beskales George，Soliman Mohamed A.A survey of top-k query processing techniques in relational database systems［J］.ACM Computing Surveys，2008，40（4）：1-58.

［2］Chang Yuan-chi，Lawrence Bergman，Vittorio Castelli，et al.The onion technique：indexing for linear optimization queries［C］∥Proc of the 2000 ACM SIGMOD，New York：ACM，2000：391-402.

［3］Hristidis Vagelis，Koudas Nick，Papakonstantinou Yannis.Prefer：a system for the efficient execution of multi-parametric ranked queries［C］∥Proc of the 2001 ACM SIGMOD，New York：ACM，2001：259-270.

［4］Zou Lei，Chen Lei.Dominant graph：an efficient indexing structure to answer top-k queries［C］∥Proc of the 24th ICDE，Washington：IEEE Computer Society，2008：536-545.

［5］Hacigumus H，Iyer B R，Mehrotra S.Providing database as a service［C］∥Proc of the 18th ICDE. Washingtong：IEEE Computer Society，2002：29-40.

［6］Merkle R.A certified digital signature［C］∥Advance in Cryptology-Crypto＇89，Berlin：Springer，LNCS 435，1990：218-238.

［7］Premkumar Devanbu，Michael Gertz，Charles Martel，et al.Authentic data publication over the internet［J］.Journal of Computer Security，2003，11（3）：291-314.

［8］Xie Min，Wang Hai-xun，Yin Jian，et al.Integrity auditing of outsourced data［C］∥Proc of the 33rd VLDB，New York：ACM，2007：782-793.

［9］張敏，洪澄，陳馳.一種服務(wù)器透明的外包數(shù)據(jù)庫(kù)查詢驗(yàn)證方案［J］.計(jì)算機(jī)研究與發(fā)展，2010，47（1）：182-190.

Zhang Min，Hong Cheng，Chen Chi.Server transparent query authentication of outsourced database［J］.Journal of Computer Research and Development，2010，47（1）：182-190.

［10］咸鶴群，馮登國(guó).外包數(shù)據(jù)庫(kù)模型中的完整性檢測(cè)方案［J］.計(jì)算機(jī)研究與發(fā)展，2010，47（6）：1107-1115.

Xian He-qun，F(xiàn)eng Deng－guo.An integrity checking scheme in outsourced database model［J］.Journal of Computer Research and Development，2010，47（6）：1107-1115.

［11］溫濤，盛剛，郭權(quán)，等.追加型數(shù)據(jù)庫(kù)外包中的查詢結(jié)果驗(yàn)證［J］.計(jì)算機(jī)研究與發(fā)展，2012，49（10）：2077-2085.

Wen Tao，Sheng Gang，Guo Quan，et al.Query results authentication of outsourced append-only databases［J］.Journal of Computer Research and Development，2012，49（10）：2077-2085.

［12］Yang Yin，Stavros Papadopoulos，Dimitris Papadias，et al.Authenticated indexing for outsourced spatial databases［J］.The VLDB Journal，2009，18（3）：631-648.

［13］Stavros Papadopoulos，Wang Li-xing，Yang Yin，et al.Authenticated multi-step nearest neighbor search［J］.IEEE Transactions on Knowledge and Data Engineering，2011，23（5）：641-654.

［14］Stavros Papadopoulos，Yang Yin，Dimitris Papadias.Continuous authentication on relational streams［J］.The VLDB Journal，2010，19（2）：161-180.