基于云計(jì)算數(shù)據(jù)查詢的安全索引構(gòu)建方法*

邢文凱

(1. 鄭州大學(xué) 西亞斯國際學(xué)院， 河南 新鄭 451150； 2. 商丘職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)系，河南 商丘 476100)

云計(jì)算具有超強(qiáng)的數(shù)據(jù)處理能力，并且能夠?qū)崿F(xiàn)大容量數(shù)據(jù)的有效存儲，逐漸受到企業(yè)和個人數(shù)據(jù)管理的青睞.通過云端處理平臺，用戶能夠有效降低本地資源投入，節(jié)約日常維護(hù)時間成本，并且能夠在大數(shù)據(jù)統(tǒng)計(jì)和計(jì)算后為決策支持提供幫助[1].與保存于本地相比，用戶數(shù)據(jù)保存于云端更容易出現(xiàn)數(shù)據(jù)泄露或被破壞的可能[2]，所以云計(jì)算服務(wù)器數(shù)據(jù)資源的管理和隱私保護(hù)顯得尤為重要.當(dāng)前數(shù)據(jù)擁有者外包數(shù)據(jù)給云端管理的模式仍處于初級階段，大部分?jǐn)?shù)據(jù)仍由數(shù)據(jù)擁有者運(yùn)行維護(hù).

云計(jì)算數(shù)據(jù)量大且內(nèi)容豐富，用戶訪頻率高，在用戶查詢讀取數(shù)據(jù)過程中，如何保證用戶既能通過云端獲取需求信息，又能隱藏其他數(shù)據(jù)，防止關(guān)聯(lián)數(shù)據(jù)隱私泄露，是當(dāng)前云計(jì)算數(shù)據(jù)管理需要亟待解決的問題.文獻(xiàn)[3]從云計(jì)算數(shù)據(jù)安全架構(gòu)方面對云計(jì)算與大數(shù)據(jù)時代下的隱私保護(hù)提出了策略；文獻(xiàn)[4]從用戶屬性著手，進(jìn)行多項(xiàng)授權(quán)的安全云端登陸.當(dāng)前云計(jì)算加密方法主要有內(nèi)容感知加密和格式加密，前者是對關(guān)鍵信息設(shè)置加密策略，后者是對整段數(shù)據(jù)進(jìn)行加密.兩者共同點(diǎn)是均需要采用加密算法完成數(shù)據(jù)加密，比如橢圓加密，DES密鑰生成等，兩者差異主要表現(xiàn)在數(shù)據(jù)加密的范圍，前者針對關(guān)鍵數(shù)據(jù)，后者針對整個數(shù)據(jù)文本.這些加密手段都將重點(diǎn)放在數(shù)據(jù)傳輸及通信過程中，或者在云計(jì)算服務(wù)器端對數(shù)據(jù)采取加密保護(hù).本文以數(shù)據(jù)查詢的索引構(gòu)建作為切入點(diǎn)，將相似子圖查詢與哈希多關(guān)鍵字索引相結(jié)合，旨在提高用戶數(shù)據(jù)檢索過程中的數(shù)據(jù)安全性，在安全索引策略制定過程中，還需考慮云計(jì)算數(shù)據(jù)的查詢效率及數(shù)據(jù)管理的存儲成本.

1 云計(jì)算數(shù)據(jù)圖狀部署

云計(jì)算數(shù)據(jù)類型豐富，數(shù)據(jù)量大，對應(yīng)的數(shù)據(jù)操作方法也呈多樣化特點(diǎn).考慮到圖狀數(shù)據(jù)在結(jié)構(gòu)化復(fù)雜數(shù)據(jù)方面的獨(dú)特優(yōu)點(diǎn)[5]，本文采用圖狀數(shù)據(jù)對云計(jì)算數(shù)據(jù)進(jìn)行部署，對圖狀數(shù)據(jù)進(jìn)行操作和處理來挖掘云計(jì)算數(shù)據(jù)的關(guān)聯(lián)性，提高數(shù)據(jù)使用價值，具體查詢系統(tǒng)模型如圖1所示.

圖1 云計(jì)算數(shù)據(jù)查詢系統(tǒng)模型Fig.1 Model for data query system in cloud computing

在數(shù)據(jù)查詢過程中，不論是圖狀數(shù)據(jù)本身還是查詢關(guān)鍵字及索引，都是云平臺需要保護(hù)的數(shù)據(jù).在用戶訪問圖狀數(shù)據(jù)時，如何保證用戶數(shù)據(jù)不被竊取和替換是研究人員需要重點(diǎn)關(guān)注的問題，本文從索引構(gòu)建方面提高數(shù)據(jù)的安全性.

圖狀數(shù)據(jù)對結(jié)構(gòu)化復(fù)雜數(shù)據(jù)進(jìn)行部署，在用戶訪問云平臺進(jìn)行數(shù)據(jù)查詢過程中，提高了用戶獲取有效數(shù)據(jù)的效率.云平臺需要對龐大的圖狀數(shù)據(jù)建立合適的索引結(jié)構(gòu)，利用索引關(guān)鍵字進(jìn)行相似性計(jì)算.圖狀數(shù)據(jù)查詢過程中，節(jié)點(diǎn)之間的關(guān)聯(lián)性與約束節(jié)點(diǎn)的可達(dá)性是云臺數(shù)據(jù)保護(hù)的另一關(guān)鍵點(diǎn).

本文從相似子查詢過程中分析可能出現(xiàn)的數(shù)據(jù)泄露問題，并在數(shù)據(jù)建立索引過程中采取策略對這些問題進(jìn)行規(guī)避.

2 安全索引構(gòu)建

2.1 相似子圖查詢構(gòu)造

相似子圖查詢的定義如下：給定查詢圖Q和圖狀數(shù)據(jù)集合G=(G1，G2，…，Gm)，然后在G中找出所有近似包含Q的圖狀數(shù)據(jù)[5]，具體算法步驟如下：

1) 抽取需要查詢數(shù)據(jù)樣本的圖狀數(shù)據(jù)特征子結(jié)構(gòu)，對結(jié)構(gòu)進(jìn)行歸一化聚合處理得到FG=(f1，f2，…，fn)，然后將圖狀數(shù)據(jù)的特征向量表示為gi=(gi，1，gi，2，…，gi，n).特征子結(jié)構(gòu)主要分為兩類，頻繁子結(jié)構(gòu)和一般子結(jié)構(gòu)，劃分標(biāo)準(zhǔn)參考文獻(xiàn)[6-7]，則圖狀數(shù)據(jù)的索引向量可表示為I=(g1，g2，…，gm).

2) 采用圖狀數(shù)據(jù)的邊向量和被查詢量Q進(jìn)行模擬對比，找出兩者差異，然后對圖狀數(shù)據(jù)的邊向量進(jìn)行一系列邊操作，得到與被查詢量Q最接近的圖狀結(jié)構(gòu).在模擬對比過程中，由于對圖狀數(shù)據(jù)向量進(jìn)行了放松邊操作才能模擬得到與Q最相似的圖狀結(jié)構(gòu).放松邊操作是在距離計(jì)算過程中對Q的邊進(jìn)行添加、刪除、修改權(quán)值等操作[8]，在放松邊的操作過程中，必然造成圖狀數(shù)據(jù)與被查詢向量存在特征結(jié)構(gòu)差.在此將結(jié)構(gòu)差記為dmax，將dmax作為判斷查詢門限值標(biāo)準(zhǔn)，其值可通過遞歸函數(shù)求解.

3) 計(jì)算被查詢量Q與圖狀數(shù)據(jù)集合G中的結(jié)構(gòu)差異，具體計(jì)算為

(1)

式中，i和j取值范圍為1≤i≤m，1≤j≤n.當(dāng)qj≤gi，j時，表示圖狀數(shù)據(jù)集合G是包含被查詢數(shù)據(jù)對象Q的，則將兩者差異性記為0；當(dāng)qj>gi，j時，需要計(jì)算兩者特征子結(jié)構(gòu)的差異，還需要計(jì)算整體差異，計(jì)算規(guī)則為

(2)

當(dāng)d(Q，Gi)≤dmax時，則表示圖像數(shù)據(jù)集合G包含查詢數(shù)據(jù)對象集合Q，需要通過索引找到用戶查詢結(jié)果.如果用戶發(fā)現(xiàn)此次查詢結(jié)果并不全面，可以繼續(xù)重復(fù)上述操作，對圖狀數(shù)據(jù)進(jìn)行邊操作，但這種操作必然導(dǎo)致dmax的增大，造成相似誤差增大.

以上方法可以滿足云計(jì)算數(shù)據(jù)的相似查詢，但是對于安全性和隱私保護(hù)未采取任何方法規(guī)避，下文將對數(shù)據(jù)查詢的隱私保護(hù)制定策略.

為了方便描述查詢過程的隱私問題，需要對計(jì)算機(jī)陷門這個概念進(jìn)行說明.陷門是指在登陸系統(tǒng)時繞過口令檢查的登陸操作[9]，也可以理解為非授權(quán)訪問.這種非授權(quán)訪問對于云端數(shù)據(jù)泄露有很大影響，而且在數(shù)據(jù)查詢過程中，一旦攻擊者對圖狀數(shù)據(jù)的特征子結(jié)構(gòu)種類和數(shù)量進(jìn)行破解，那整個圖狀數(shù)據(jù)集合就很有可能會被解密，云端數(shù)據(jù)對于攻擊者變得透明.

對于圖狀數(shù)據(jù)集合G中的一個圖狀數(shù)據(jù)Gi，將其特征向量和隨機(jī)向量分別用gi和λi表示，然后運(yùn)用ASM-PH加密得到加密向量EK(gi)和EK(λi)，接著計(jì)算安全向量，即

EK(ψi)=EK(gi)EK(λi)

(3)

EK(ψi)是特征向量和隨機(jī)向量的乘積，形成密文數(shù)據(jù)，則有圖狀數(shù)據(jù)加密后的集合為

EK(ψ)={EK(ψ1)，EK(ψ2)，…，EK(ψm)}

(4)

在陷門處理方面，當(dāng)云平臺檢測到登錄信息后，將安全和查詢向量進(jìn)行對比，即

EK(α(qj，gi，j))=EK(qj)EK(λi)-EK(ψi)

(5)

然后根據(jù)EK(α(qj，gi，j))計(jì)算兩個圖的差異性，防止無授權(quán)訪問，最后對EK(d(Q，Gi))進(jìn)行判斷計(jì)算，其計(jì)算表達(dá)式為

EK(d(Q，Gi))=EK(dmax)EK(λi)-EK(gi)

(6)

若d(Q，Gi)≥0，表示圖狀數(shù)據(jù)集合G包含被查詢對象Q；若d(Q，Gi)<0，表示查詢對象Q不在圖狀數(shù)據(jù)集合G中.

2.2 哈希索引策略

哈希函數(shù)作為一種壓縮映射，廣泛用于數(shù)據(jù)加密算法中[10-11]，本文利用哈希函數(shù)將圖狀數(shù)據(jù)單個數(shù)據(jù)集的可達(dá)節(jié)點(diǎn)進(jìn)行哈希運(yùn)算，作為數(shù)據(jù)索引的第一級.設(shè)數(shù)據(jù)集合K={η，M1，M2，ξ，β}，M1、M2和β={β1，β2，…，βt}分別為(n+1)×(n+1)維可逆矩陣和隨機(jī)數(shù).

將查詢的路徑標(biāo)簽進(jìn)行向量轉(zhuǎn)換，向量轉(zhuǎn)換過程中引入隨機(jī)數(shù)[12-13]，然后計(jì)算查詢指示向量，其表達(dá)式為

(7)

式中：ξk為k維隨機(jī)向量；γi，j，k為圖狀數(shù)據(jù)向量γi，j的路徑標(biāo)簽值.

(8)

將得到的標(biāo)簽集合作為圖狀數(shù)據(jù)單集安全檢索的第二級檢索，即

Hi=(T1，T2，…，TK)

(9)

最后，結(jié)合哈希函數(shù)構(gòu)造的一級檢索和標(biāo)簽集合的二級檢索[14]，得到本文所構(gòu)建的安全索引為

I=(I1，I2，…，Im)

(10)

式中，Ii=(Ki，Hi).

3 實(shí)例仿真

本文采用8 GBit內(nèi)存，64位處理器作為云端服務(wù)器，采用Matlab進(jìn)行實(shí)例仿真.為了驗(yàn)證算法的通用性，實(shí)例仿真的5組圖狀數(shù)據(jù)集合均來自于隨機(jī)數(shù)發(fā)生器，為了保證樣本的差異性，5組數(shù)據(jù)集合的數(shù)量分別為2 000，4 000，6 000，8 000，10 000.被查詢對象數(shù)據(jù)選擇邊分別為8，16，20，24，32，頻繁子結(jié)構(gòu)(Struct A)和一般子結(jié)構(gòu)(Struct B)作為特征子結(jié)構(gòu)的兩個類型[6-7]，將不同子結(jié)構(gòu)規(guī)模、不同數(shù)據(jù)樣本及不同查詢對象情況的性能進(jìn)行實(shí)例仿真.首先，考慮到云計(jì)算數(shù)據(jù)量大的特點(diǎn)，分析了本文安全索引構(gòu)建方法的存儲成本，對5組圖狀數(shù)據(jù)集合仿真，其特征數(shù)量規(guī)模和所占內(nèi)存情況分別如圖2、3所示.

圖2 特征對象規(guī)模圖Fig.2 Scale of query objects

圖2是不同數(shù)量的圖狀數(shù)據(jù)集合進(jìn)行安全索引帶來的特征子結(jié)構(gòu)種類數(shù)量的變化情況.從圖2中可以看出，Struct A相對于Struct B在相同數(shù)量集合的條件下，種類數(shù)量更豐富，因此更耗存儲成本.隨著圖狀數(shù)據(jù)集合數(shù)量的增加，Struct A的種類緩慢增加，而Struct B的種類數(shù)量基本保持穩(wěn)定，這表明該索引構(gòu)建方法在大數(shù)據(jù)量情況下，存儲成本開銷并不大，而且增長比較慢.

圖3 不同規(guī)模圖狀數(shù)據(jù)集合索引所占內(nèi)存Fig.3 Memory occupied by index of graphdata set with different scales

由圖3可以看出，隨著圖狀數(shù)據(jù)量的增加，安全索引所占內(nèi)存呈線性增加，Struct A相比于Struct B增加速度較快.當(dāng)圖狀數(shù)據(jù)量達(dá)到10 000個時，Struct A約占用900 MBit的存儲空間，Struct B大約需要400 MBit，圖狀數(shù)據(jù)量越大，安全索引所占空間也越大，增大趨勢明顯.

在相似子圖查詢過程中，對圖狀數(shù)據(jù)進(jìn)行邊操作，然后對圖狀數(shù)據(jù)與被查詢對象進(jìn)行相似子圖比較，判斷該圖狀數(shù)據(jù)集合中是否包含被查詢對象.圖4為不同放松邊數(shù)的相似查詢結(jié)果，在放松1條邊的情況下，不論被查詢對象的結(jié)構(gòu)大小，幾乎可以得到確切的相似比較匹配答案，表明經(jīng)過加密和哈希等操作的安全索引并未增加相似匹配的難度和誤差.隨著放松邊數(shù)增加，相似誤差變大，圖狀數(shù)據(jù)集合中與被查詢對象匹配的子圖呈線性增加.在放松同樣邊數(shù)的情況下，特征子結(jié)構(gòu)結(jié)構(gòu)規(guī)模越大，相似匹配得到的結(jié)果越多，從這點(diǎn)來看，此方法更適合于模糊查詢.

圖4 不同放松邊數(shù)的相似查詢結(jié)果Fig.4 Similar query results of different relaxation edges

考慮了存儲成本和查詢效果之后，對時間成本進(jìn)行仿真.云計(jì)算數(shù)據(jù)量大且訪問用戶眾多，查詢效率也是索引構(gòu)建必須考慮的重要因素，圖5的橫坐標(biāo)表示查詢對象圖結(jié)構(gòu)規(guī)模大小，圖的規(guī)模大小按邊數(shù)個數(shù)來衡量，邊分別為8，16，20，24，32，即Q8、Q16、Q20、Q24、Q32.從圖5可以看出，Struct B并不隨著查詢對象規(guī)模的擴(kuò)大增加查詢時間，時間成本一直保持在3.2 s左右，而Struct A也保持在6～7 s之間，這表明查詢的時間成本并不隨著查詢對象規(guī)模的擴(kuò)大而增加.

圖5 不同規(guī)模查詢對象的查詢時間Fig.5 Query time for query objects with different scales

雖然被查詢對象的規(guī)模并不影響查詢時間，但隨著圖狀數(shù)據(jù)集合個數(shù)的增加，查詢時間逐漸增大.圖6為不同圖狀數(shù)據(jù)集數(shù)量下的查詢時間，從圖6可以看出，不同種類、不同規(guī)模的查詢對象在不同數(shù)量圖狀數(shù)據(jù)集合下查詢所消耗的時間差別較大.Struct A所耗時間比Struct B高，對于Struct B類查詢對象來說，結(jié)構(gòu)規(guī)模越大，時間成本越高，但時間成本的增加非常慢，即使圖狀樣本數(shù)據(jù)加倍，時間也增加非常少.

圖6 不同圖狀數(shù)據(jù)集數(shù)量下的查詢時間Fig.6 Time-consuming of query objects undergraph data set with different scales

4 結(jié) 論

本文利用相似子圖查詢和哈希函數(shù)構(gòu)建云計(jì)算數(shù)據(jù)安全索引，在構(gòu)建過程中，通過相似誤差判斷被查詢對象是否在圖狀數(shù)據(jù)集合中；在索引構(gòu)造中，引入ASM-PH加密算法對索引圖狀數(shù)據(jù)進(jìn)行加密.對圖狀集合數(shù)據(jù)可達(dá)節(jié)點(diǎn)進(jìn)行哈希散列作為一級檢索目錄，而標(biāo)簽集合作為二級檢索目錄，以該方法作為云計(jì)算數(shù)據(jù)的索引構(gòu)建，不論是在時間成本、存儲成本及查詢準(zhǔn)確度方面均有一定的優(yōu)勢，可廣泛用于大數(shù)據(jù)的云端寄存和管理.

[1] 劉艷秋，王浩，張穎，等.大數(shù)據(jù)背景下物流服務(wù)訂單分配 [J].沈陽工業(yè)大學(xué)學(xué)報(bào)，2016，38(2)：190-195.

(LIU Yan-qiu，WANG Hao，ZHANG Ying，et al.Order allocation of logistics service under background of big data [J].Journal of Shenyang University of Technology，2016，38(2)：190-195.)

[2] Boru D，Kliazovich D，Granelli F，et al.Energy-efficient data replication in cloud computing datacenters [J].Cluster Computing，2015，18(1)：385-402.

[3] 歐萍.數(shù)據(jù)庫索引技術(shù)應(yīng)用[J].電子科技，2011，24(9)：146-148.

(OU Ping.Database index technology application[J].Electronic Science and Technology，2011，24(9)：146-148.)

[4] Chen Y，Song L，Yang G.Attribute-based access control for multi-authority systems with constant size ciphertext in cloud computing [J].Communications China，2016，13(2)：146-162.

[5] 馬靜，王浩成.基于路徑映射的相似子圖匹配算法 [J].計(jì)算機(jī)科學(xué)，2012，39(11)：137-141.

(MA Jing，WANG Hao-cheng.Similarity subgraph matching algorithm based on path mapping [J].Computer Science，2012，39(11)：137-141.)

[7] 張煥生，崔炳德，王政峰，等.基于圖的頻繁子結(jié)構(gòu)挖掘算法綜述 [J].微型機(jī)與應(yīng)用，2009，28(10)：5-9.

(ZHANG Huan-sheng，CUI Bing-de，WANG Zheng-feng，et al.A survey of algorithms for mining frequent subgraph structures based on graphs [J].Microcomputer and Applications，2009，28(10)：5-9.)

[8] 馬茜，谷峪，李芳芳，等.順序敏感的多源感知數(shù)據(jù)填補(bǔ)技術(shù) [J].軟件學(xué)報(bào)，2016，27(9)：2332-2347.

(MA Qian，GU Yu，LI Fang-fang，et al.Order-sensitive missing value imputation technology for multi-source sensory data [J].Journal of Software，2016，27(9)：2332-2347.)

[9] 彭天強(qiáng)，栗芳.基于深度卷積神經(jīng)網(wǎng)絡(luò)和二進(jìn)制哈希學(xué)習(xí)的圖像檢索方法 [J].電子與信息學(xué)報(bào)，2016，38(8)：2068-2075.

(PENG Tian-qiang，LI Fang.Image retrieval based on deep convolutional neural networks and binary hashing learning [J].Journal of Electronics and Information Technology，2016，38(8)：2068-2075.)

[10]閆建華.格基簽密關(guān)鍵技術(shù)研究 [D].北京：北京郵電大學(xué)，2015.

(YAN Jian-hua.Lattice signcryption key technology research [D].Beijing：Beijing University of Posts and Telecommunications，2015.)

[11]倪劍兵.關(guān)鍵字搜索公鑰加密方案的分析與設(shè)計(jì) [D].成都：電子科技大學(xué)，2014.

(NI Jian-bing.Analysis and design of keyword search public key encryption scheme [D].Chengdu：University of Electronic Science and Technology of China，2014.)

[12]阮林林.基于局部線性嵌入和局部保持投影的圖像哈希算法 [D].桂林：廣西師范大學(xué)，2015.

(RUAN Lin-lin.Image hashing algorithm based on locally linear embedding and locality preserving projections [D].Guilin：Guangxi Normal University，2015.)

[13]余純武，郭飛，張健.輕量哈希函數(shù)HBL [J].計(jì)算機(jī)工程與應(yīng)用，2016，52(20)：1-4.

(YU Chun-wu，GUO Fei，ZHANG Jian.Lightweight hash function HBL [J].Computer Engineering and Applications，2016，52(20)：1-4.)

[14]孫德才，王曉霞.一種基于Bigram二級哈希的中文索引結(jié)構(gòu)[J].電子設(shè)計(jì)工程，2014(12)：1-4.

(SUN De-cai，WANG Xiao-xia.A chinese index structure based on Bigram two level Hash[J].Electronic Design Engineering，2014(12)：1-4.)