云計(jì)算加密數(shù)據(jù)關(guān)鍵詞代數(shù)簽名索引匹配搜索

蒲 在 毅

(西華師范大學(xué)網(wǎng)絡(luò)與信息化管理中心 四川 南充 637009)

0 引 言

隨著現(xiàn)代信息技術(shù)的發(fā)展，云端存儲呈現(xiàn)出數(shù)據(jù)量的爆炸式增長，特別是電子郵件數(shù)據(jù)量、隱私視頻數(shù)據(jù)量等。如果采取云存儲方式進(jìn)行數(shù)據(jù)存儲，則可大幅度降低數(shù)據(jù)處理開銷，實(shí)現(xiàn)處理效率提升。但由于云服務(wù)商和用戶之間存在信息的不對稱，導(dǎo)致其處于不同可信域內(nèi)，對于數(shù)據(jù)進(jìn)行外包處理存在較大安全性問題，因此云服務(wù)過程中的可信度是人們比較關(guān)心的重點(diǎn)。應(yīng)該嚴(yán)格避免信息意外泄漏給未授權(quán)客戶。但是在云計(jì)算過程中，存在短時間內(nèi)大量用戶數(shù)據(jù)檢索和數(shù)據(jù)外包可能性。明文環(huán)境下常用的搜索策略是利用關(guān)鍵詞檢索方式進(jìn)行加密文件的檢索和提取，但是在加密環(huán)境下對關(guān)鍵詞進(jìn)行直接搜索不現(xiàn)實(shí)，因?yàn)榧用苓^程限制這種搜索行為。

為實(shí)現(xiàn)對云計(jì)算過程中加密數(shù)據(jù)有效檢索，學(xué)者們提出采用關(guān)鍵詞索引的方式對文件檢索。創(chuàng)建磁盤工作版本是近年來研究的熱點(diǎn)，但由于參考位置的不良性、尋呼方案的復(fù)雜性以及插入結(jié)構(gòu)導(dǎo)致的結(jié)構(gòu)劣化，導(dǎo)致技術(shù)實(shí)現(xiàn)上存在較大的困難。后綴數(shù)組將指針存儲在按字典順序排序的后綴列表中，并使用二進(jìn)制搜索進(jìn)行模式匹配。然而，標(biāo)準(zhǔn)數(shù)據(jù)庫體系結(jié)構(gòu)以塊形式存儲記錄，且支持動態(tài)插入和刪除，這使得順序存儲維護(hù)變得困難。目前解決完全模式匹配搜索的磁盤索引方法主要有兩種：關(guān)鍵詞B-Tree算法和n-gram反向索引算法。前者的全局結(jié)構(gòu)是B+樹的結(jié)構(gòu)，其中鍵是指向數(shù)據(jù)庫中后綴的指針。每個節(jié)點(diǎn)被組織成一個Patricia單詞查找樹，這有助于指導(dǎo)搜索和插入操作。文本搜索需求的另一個方向是索引n-gram(n個連續(xù)符號)而不是整個單詞的索引。它們是“磁盤友好”的，因?yàn)槠湟蕾囉诳焖俚捻樞驋呙?，提供良好的引用位置，且易于適應(yīng)分頁和分區(qū)。然而，在數(shù)據(jù)庫的大小和模式大小上，搜索成本都是線性的。本文提出一種新的基于索引的全文檢索數(shù)據(jù)結(jié)構(gòu)，稱為代數(shù)簽名索引。它遵循基于n-gram的倒排文件路徑，將標(biāo)準(zhǔn)數(shù)據(jù)庫大規(guī)模索引(即散列)與基于代數(shù)簽名的新散列演算相結(jié)合。

本文方法創(chuàng)新點(diǎn)是利用在數(shù)學(xué)結(jié)構(gòu)中的字符作為符號的解釋。這種結(jié)構(gòu)(Galois字段)中的操作有助于開發(fā)新的計(jì)算技術(shù)，用于在恒定時間內(nèi)識別搜索的結(jié)果項(xiàng)。因此，所提云計(jì)算加密數(shù)據(jù)索引結(jié)構(gòu)具有吸引人的特性，目前就我們所知，這種特性是獨(dú)特的，即獨(dú)立于數(shù)據(jù)庫的大小和模式的長度，使用恒定數(shù)量的磁盤訪問來執(zhí)行記錄查找。

1 問題描述

使用大小為2f的伽羅瓦域(GF)GF(2f)，伽羅瓦域的元素是長度為f的位串。選擇利用代數(shù)簽名CII碼對云計(jì)算加密數(shù)據(jù)8位串處理，并使用Unicode碼對16位串處理，該運(yùn)算相互結(jié)合，具有中性元素0和1，且存在加性和乘性逆。在伽羅瓦域GF(2f)中，加法和減法被實(shí)現(xiàn)為按位異或。云計(jì)算加密數(shù)據(jù)日志/反日志表通常提供最實(shí)用乘法方法。采用通常的數(shù)學(xué)符號來表示以下操作。使用GF(2f)的基礎(chǔ)元素α，意味著α的冪枚舉伽羅瓦域的所有非零元素。令R=r0,r1,…,rM-1是具有M個符號的記錄，可將R解釋為GF元素的序列。

定義1記錄R的m符號代數(shù)簽名(代數(shù)簽名)是具有m坐標(biāo)(s1,s2,…,sm)向量ASm(R)，可定義為：

(1)

將R的m符號代數(shù)簽名表示為十六進(jìn)制符號中sm,…,s1的級聯(lián)。例如，如果s1=#34和s2=#12，則可將2符號代數(shù)簽名表示為s2s1=#1234。

定義2令l∈[0,M-1]為R中任意偏移位置。在CASm(R,l)上的累積代數(shù)簽名(C代數(shù)簽名)是rl結(jié)尾的前綴代數(shù)簽名，即CASm(R,l)=ASm(r0,r1,…,rl)。

從l′到l的部分代數(shù)簽名(P代數(shù)簽名)的值PASm(R,l′,l)=ASm(rl′,rl′+1,…,rl)，具有0≤l′≤1。最后，使用長度為n的子串P代數(shù)簽名，即，n-gram。

定義3對于l≥n-1，令l上R的n-gram代數(shù)簽名是NASm(R,l)=PASm(R,l-n+1,l)，進(jìn)而可得：

NASm(R,l)=(rl-n+1+…+rl×αn-1,

rl-n+1+…+rl×α2(n-1),

?

rl-n+1+…+rl×αm(n-1))

(2)

圖1給出在偏移l上定義的C代數(shù)簽名、P代數(shù)簽名和N代數(shù)簽名記錄的各個部分。以下代數(shù)簽名的簡單性質(zhì)，表示為坐標(biāo)i,1≤i≤m。注意到在l的C代數(shù)簽名的第i個符號作為CASm(l)i，且類似地進(jìn)行N代數(shù)簽名和P代數(shù)簽名。

CASm(l)i=CASm(l-1)i+rl×αil

(3)

(4)

(5)

(6)

圖1 代數(shù)簽名記錄示意

式(3)-式(5)可在掃描云計(jì)算加密數(shù)據(jù)輸入記錄或模式時增量地計(jì)算下一個C代數(shù)簽名和N代數(shù)簽名，而不是完全重新計(jì)算簽名，這大大提升了計(jì)算速度。表1總結(jié)了本文中使用的符號及其定義。

表1 符號定義

2 加密數(shù)據(jù)關(guān)鍵詞代數(shù)簽名索引

2.1 代數(shù)簽名索引

代數(shù)簽名是加密數(shù)據(jù)處理過程中具有代數(shù)性質(zhì)的數(shù)字簽名，它主要應(yīng)用在大規(guī)模存儲系統(tǒng)中的數(shù)據(jù)審計(jì)、奇偶校驗(yàn)和計(jì)算委托等任務(wù)中，具有可變長度磁盤駐留緩存的經(jīng)典哈希文件(見圖2)，系統(tǒng)散列目錄指向該緩存。這樣的文件具有簡單性和優(yōu)異性，得到廣泛關(guān)注，主要優(yōu)點(diǎn)是磁盤訪問次數(shù)不變，與文件和模式大小無關(guān)，對于降低數(shù)據(jù)訪問復(fù)雜度具有顯著作用。對于tree/trie訪問方法，不可能有一定數(shù)量磁盤訪問。每個緩存存儲條目列表，每個條目在數(shù)據(jù)庫中索引一些n-gram。代數(shù)簽名索引基本變體是密集的，索引為每個n-gram。為條目提供緩存的哈希函數(shù)使用n-gram值作為哈希鍵值。哈希函數(shù)是特殊的：它依賴于n-gram的代數(shù)簽名。在下文中，只處理靜態(tài)代數(shù)簽名索引，但是哈希結(jié)構(gòu)可使用標(biāo)準(zhǔn)機(jī)制來實(shí)現(xiàn)動態(tài)性、可伸縮性和分布。

圖2 基于代數(shù)簽名的匹配嘗試

根據(jù)圖2所示，對云計(jì)算加密數(shù)據(jù)模式P的搜索過程如下：首先，針對三個簽名對P進(jìn)行預(yù)處理：1) 初始n-gramS1；2) 最終n-gramS2；3) 在S1(包括S2)之后的P后綴Sp。在與S1簽名相同的數(shù)據(jù)庫中，定位緩存上S1的散列的每個條目e1可對n-gram進(jìn)行索引。同樣地，在S2上散列定位緩存，每個條目e2用S2簽名索引n-gram。只考慮對在同一記錄和正確距離之間的條目。因此，至少在簽名的初始和終端n-gram上找到任何關(guān)鍵詞S的匹配模式P。

最后，進(jìn)行AS(e1,e2,Sp)代數(shù)計(jì)算，決定Sp是否匹配S的后綴。這種計(jì)算是通過簽名的特定屬性實(shí)現(xiàn)的，這些屬性允許檢查一些語義屬性(例如，關(guān)鍵詞匹配)，盡管它們的表示非常緊湊，但是標(biāo)準(zhǔn)散列函數(shù)無法實(shí)現(xiàn)這一點(diǎn)。該方法本質(zhì)上是概率性的，假陽性的可能性很低?？梢酝ㄟ^模式與記錄的相關(guān)部分之間的符號比較來避免甚至極小的錯誤匹配的可能性。

通過利用第一個和最后一個n-grams可對磁盤進(jìn)行限制訪問，此時代數(shù)簽名索引搜索過程獨(dú)立于P的大小。上面概述的搜索過程的成本可降低到讀取兩個緩存的成本。哈希目錄本身通常可以緩存在RAM中，或者最多需要兩個額外的磁盤訪問。通過適當(dāng)?shù)膭討B(tài)哈希機(jī)制，可以均勻地分布結(jié)構(gòu)中的條目并優(yōu)雅地進(jìn)行縮放，緩存的大小可以保持足夠均勻，以使代數(shù)簽名索引獨(dú)立于數(shù)據(jù)庫大小在恒定時間內(nèi)運(yùn)行。

云計(jì)算加密數(shù)據(jù)庫由記錄標(biāo)識符(RID)和一些非關(guān)鍵字段記錄組成。假設(shè)非關(guān)鍵字段可由從伽羅瓦域解釋為符號的關(guān)鍵詞組成。當(dāng)討論偏移和代數(shù)簽名時，僅指非鍵字段。對于字段R中的字符ri，其偏移可表示為i。n-gram序列G=rl-n+1,…,rl是R中n個連續(xù)符號的任意序列。通過擴(kuò)展，將l稱為n-gram序列的偏移量。

定義4令G是在R中偏移o的n-gram，條目索引G，表示為E(G)，是一個三元組(rid,o′,c)，其中rid是R的記錄標(biāo)識符(RID)，c是累積代數(shù)簽名CAS1(R,o)，o′是偏移o的模2f-1。

通過取余數(shù)來保證條目具有恒定大小。對于所有伽羅瓦場元素χ，利用同一性度量χ2f-1=χ，可證明模的選擇。假設(shè)索引是“密集”的，即數(shù)據(jù)庫中的每一個n-gram都由一個不同的條目索引。為了構(gòu)造索引，在數(shù)據(jù)庫中處理所有的n-gram。索引是一個哈希文件，表示為D[0,1,…,L-1]，目錄長度L=2v為2的冪(見圖3)。

圖3 代數(shù)簽名索引指標(biāo)結(jié)構(gòu)

總之，代數(shù)簽名索引行結(jié)構(gòu)類似于反轉(zhuǎn)文件中的發(fā)布列表，除在每個條目中存在代數(shù)簽名c和偏移量l的特定表示之外。由于使用散列文件，所以行應(yīng)該具有沖突解決方法，例如使用指向溢出空間的指針的經(jīng)典單獨(dú)鏈接。這種技術(shù)適應(yīng)適度增長，但如果需要適應(yīng)大的增長，那么需要動態(tài)散列方法，比如線性散列。

2.2 代數(shù)簽名索引搜索過程

本節(jié)設(shè)計(jì)了基于代數(shù)簽名索引的云計(jì)算加密數(shù)據(jù)模式搜索，利用三個簽名對模式進(jìn)行預(yù)處理，并檢索(可能)匹配的代數(shù)簽名索引，有利于提高算法的執(zhí)行效率。首先，令P=p0,p1,…,pK-1是匹配模式。代數(shù)簽名索引搜索提供了包含P的數(shù)據(jù)庫中的每個記錄的RID。搜索算法先預(yù)處理P，然后檢索(可能)匹配的代數(shù)簽名索引。

預(yù)處理階段根據(jù)模式P計(jì)算三個簽名：1)P中的第一個n-gram的m符號代數(shù)簽名，稱為S1；2) 計(jì)算在第一個n-gram之后P的后綴1-符號P代數(shù)簽名，Sp=PAS1(P,n,K-1)；3)P中的最后一個n-gram的m符號代數(shù)簽名，稱為S2。對n-gram使用m符號代數(shù)簽名來獲得適合目錄長度的大范圍散列值，同時計(jì)算1-符號P代數(shù)簽名，為降低存儲成本，在條目中僅存儲1-符號C代數(shù)簽名值。圖4給出在運(yùn)行示例中確定簽名S1、S2和Sp的部分模式。設(shè)置n=5和m=4。預(yù)處理模式P=“University Paris Dauphine”，并得到：

1)S1=NAS4(P,4)(for 5-gram "Unive")；

2)S2=NAS4(P,24)(for 5-gram "phine")；

3)Sp=PAS1(P,5,24)。

這些信息可用于查找數(shù)據(jù)庫中出現(xiàn)的模式。

圖4 搜索算法

該代數(shù)簽名搜索過程見圖5所示。令i=hL(S1)，i′=hL(S2)。緩存D[i]中的每個條目(R,l1,c1)在記錄R中的n-gram索引G，其N代數(shù)簽名SG是hL(SG)=hL(S1)。同樣地，緩存D[i]中的每個條目(R,l2,c2)的n-gram索引G′，使得hL(G′)=hL(S2)。在可能的碰撞中，G和G′分別對應(yīng)于P中的第一個和最后一個n-gram。

圖5 搜索過程的代數(shù)簽名索引

只考慮配對(G,G′)可能的特征匹配關(guān)鍵詞S=P。這涉及到附加約束R′=R和l2=(l1+K-n)。G′中的最后分量c2必須與c1和Sp計(jì)算值相匹配：

c2=c1+αl1+1×Sp

(7)

算法1基于代數(shù)簽名索引搜索過程

輸入：模式P=p0,p1,…,pK-1，n-gram大小n

輸出：包含P的記錄列表

Begin

//預(yù)處理階段

//i是第一行索引

//i′是第二行索引

//搜索過程

For eachE(R,l1,c1)∈D[i] do

c2=c1+αl1+1×Sp;

l2=(l1+K-n) mod (2f-1);

If ?E′(R,l2,c2)∈D[i′] then

報(bào)告R搜索成功；

Endif

Endfor

End

該過程選擇性依賴于其操縱三個不同簽名的能力，S1、S2和Sp。因此，云計(jì)算加密數(shù)據(jù)模式的長度必須至少為n+1。作為一般散列，所提方法存在沖突傳遞的假陽性。為消除任何沖突，有必要對代數(shù)簽名搜索過程進(jìn)行后處理，試圖在識別為匹配的每個R中實(shí)際找到P。這需要在P和它假定匹配位置之間進(jìn)行符號與符號的比較。

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)設(shè)置

使用四種類型具有非常明顯特征的數(shù)據(jù)集來模擬云計(jì)算加密數(shù)據(jù)集關(guān)鍵詞的檢索過程，分別是：alpha，DNA，text和wikipedia。具體情況描述如下：

(1) alpha(Σ)類型數(shù)據(jù)集由合成代數(shù)簽名CII記錄組成，具有均勻的分布，遍歷字母表Σ作為擴(kuò)展代數(shù)簽名CII字符的子集。對于這些類型，組成的數(shù)據(jù)集范圍從20 MB到20 GB，每個復(fù)合了20個文件。

(2) dna包括從UCSC數(shù)據(jù)庫中提取的真實(shí)DNA記錄。這個數(shù)據(jù)集由97個文件組成，這些文件的大小范圍很大，從幾十KB到數(shù)百M(fèi)B，甚至幾個GB(對于兩個文件)，其總尺寸為9.9 GB。

(3) text類型文本由從加密數(shù)據(jù)庫中提取的大型英文圖書的代數(shù)簽名CII文件創(chuàng)建的真實(shí)文本記錄組成。文本記錄典型大小為0.5×2 MB，大小分布幾乎一致且在該范圍內(nèi)。創(chuàng)建大小為16.6 GB包含29個文件539文本的數(shù)據(jù)庫。

(4) wikipedia將免費(fèi)的維基百科百科全書進(jìn)行加密，并轉(zhuǎn)儲將維基百科的所有XML記錄附加到一個大小為24 GB的單個XML記錄中。

為限制由于字母表大小導(dǎo)致的n-gram格簽名的沖突，將DNA文件的n-gram格大小設(shè)置為8，維基百科為6，其他數(shù)據(jù)集為4。

3.2 簽名長度參數(shù)影響實(shí)驗(yàn)

在該實(shí)驗(yàn)中，對代數(shù)簽名的概率因子的影響問題進(jìn)行實(shí)驗(yàn)驗(yàn)證，假定實(shí)驗(yàn)過程中所要驗(yàn)證對象的大小所屬區(qū)間是1～1 000 GB，簽名長度參數(shù)設(shè)定的變化區(qū)間16 b～256 b。則隨著驗(yàn)證文件對象的大小變化，對數(shù)據(jù)驗(yàn)證過程中的計(jì)算成本進(jìn)行實(shí)驗(yàn)對比，結(jié)果見圖6。

圖6 影響實(shí)驗(yàn)

根據(jù)圖6所示實(shí)驗(yàn)曲線，對于具有較小尺寸的數(shù)據(jù)傳輸文件，例如10 GB以內(nèi)的數(shù)據(jù)文件，因?yàn)橛?jì)算硬件具有相對較高的配置，且?guī)拏鬏斎萘可形催_(dá)到，此時代數(shù)簽名長度變化不會對數(shù)據(jù)傳輸成本產(chǎn)生明顯的影響，但是當(dāng)數(shù)據(jù)文件增加到10 GB以上時，數(shù)據(jù)文件大小的變化會對數(shù)據(jù)傳輸成本產(chǎn)生相對明顯的影響，會導(dǎo)致數(shù)據(jù)傳輸成本大幅度的上升。

3.3 計(jì)算時間對比實(shí)驗(yàn)

對于搜索實(shí)驗(yàn)，從文件中提取模式，以確保找到至少一個結(jié)果。模式尺寸范圍從25個符號到200個符號。為避免初始化成本和來自其他OS進(jìn)程的諸如CPU或內(nèi)存爭用之類的副作用，重復(fù)執(zhí)行每次搜索直到搜索時間穩(wěn)定為止。報(bào)告運(yùn)行500個搜索操作的平均搜索時間。對比算法選取關(guān)鍵詞B-Tree算法(BT)和標(biāo)準(zhǔn)代數(shù)簽名索引算法(ASI)，其中選取ASI算法實(shí)驗(yàn)結(jié)果作為標(biāo)準(zhǔn)結(jié)果。實(shí)驗(yàn)結(jié)果如表2-表5所示。

表2 文件dna搜索時間 ms

表3 文件text搜索時間 ms

表4 文件wikipedia搜索時間 ms

表5 文件alpha(26)搜索時間 ms

對于選取的20 GB文件，關(guān)鍵詞B-Tree算法的高度是5，與字母表大小無關(guān)。根始終在緩存中，根以下級別的重要部分，取決于索引文件大小。關(guān)鍵詞B樹遍歷一般被減少到(5-2)=3個用于加載葉節(jié)點(diǎn)的磁盤訪問。此外，節(jié)點(diǎn)中的每個查找都需要對數(shù)據(jù)庫進(jìn)行附加的隨機(jī)磁盤訪問，以便獲取完整的關(guān)鍵詞。表2-表5中給出的搜索時間比，分別給出本文算法相對于代數(shù)簽名索引算法和關(guān)鍵詞B-Tree算法的加速比，可見本文算法可在相對恒定的時間內(nèi)實(shí)現(xiàn)對數(shù)據(jù)庫中任意長度模式關(guān)鍵詞的查找，驗(yàn)證了所提算法在計(jì)算效率上的優(yōu)勢。

3.4 數(shù)據(jù)完整性對比實(shí)驗(yàn)

為驗(yàn)證所提算法對于數(shù)據(jù)搜索過程完整性的影響，選取數(shù)據(jù)完整性驗(yàn)證指標(biāo)作為實(shí)驗(yàn)指標(biāo)，對比算法仍然選取ASI(加速比)和BT(加速比)兩種算法作為對比，實(shí)驗(yàn)文件的大小設(shè)定區(qū)間是2～10 GB，結(jié)果如表6所示。

表6 數(shù)據(jù)完整性對比數(shù)據(jù)

根據(jù)表6數(shù)據(jù)，本文算法在數(shù)據(jù)搜索完整性上相對于選取的兩種算法具有更好的性能表現(xiàn)。隨著實(shí)驗(yàn)數(shù)據(jù)文件變化，數(shù)據(jù)搜索的完整性出現(xiàn)下降，但是相對而言，變化的幅度并不大，這說明算法具有相對較好的魯棒性，而對比算法ASI(加速比)和BT(加速比)，本文算法具有相對較低的數(shù)據(jù)搜索完整性，算法的穩(wěn)定性能不佳。

4 結(jié) 語

本文提出一種基于代數(shù)簽名和代數(shù)計(jì)算的云計(jì)算加密數(shù)據(jù)庫中關(guān)鍵詞搜索的新方法。本文的貢獻(xiàn)在于提出了一種簡單、快速的搜索算法，該算法可以在任意大小的數(shù)據(jù)庫中，在相對恒定的時間內(nèi)找到任意長度的模式。這項(xiàng)工作從基礎(chǔ)理論角度，利用數(shù)學(xué)結(jié)構(gòu)中字符作為符號解釋來開發(fā)新的計(jì)算技術(shù)。索引的可擴(kuò)展和分布式是今后的一個有前途的研究方向。